Вопросы для самопроверки и обсуждений по темам

ВОПРОСЫ ДЛЯ САМОПРОВЕРКИ И ОБСУЖДЕНИЙ ПО ТЕМАМ

·  В чем заключаются основные способы достижения параллелизма?

·  В чем могут состоять различия параллельных вычислительных систем?

·  Что положено в основу классификации Флинна?

·  В чем состоит принцип разделения многопроцессорных систем на мультипроцессоры и мультикомпьютеры?

·  Какие классы систем известны для мультипроцессоров?

·  В чем состоят положительные и отрицательные стороны симметричных мультипроцессоров?

·  Какие классы систем известны для мультикомпьютеров?

·  чем состоят положительные и отрицательные стороны кластерных систем?

·  Какие топологии сетей передачи данных наиболее широко используются при построении многопроцессорных систем?

·  В чем состоят особенности сетей передачи данных для кластеров?

·  Каковы основные характеристики сетей передачи данных?

·  Какие системные платформы могут быть использованы для построения кластеров?

·  Как определяется модель "операции — операнды"?

·  Как определяется расписание для распределения вычислений между процессорами?

·  Как определяется время выполнения параллельного алгоритма?

·  Какое расписание является оптимальным?

·  Как определить минимально возможное время решения задачи?

·  Что понимается под паракомпьютером и для чего может оказаться полезным данное понятие?

·  Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?

·  Как определить минимально возможное время параллельного решения задачи по графу "операнды – операции"?

·  Какие зависимости могут быть получены для времени параллельного решения задачи при увеличении или уменьшении числа используемых процессоров?

·  При каком числе процессоров могут быть получены времена выполнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?

·  Как определяются понятия ускорения и эффективности?

·  Возможно ли достижение сверхлинейного ускорения?

·  В чем состоит противоречивость показателей ускорения и эффективности?

·  Как определяется понятие стоимости вычислений?

·  В чем состоит понятие стоимостно-оптимального алгоритма?

·  В чем заключается проблема распараллеливания последовательного алгоритма суммирования числовых значений?

·  В чем состоит каскадная схема суммирования? С какой целью рассматривается модифицированный вариант данной схемы?

·  В чем состоит различие показателей ускорения и эффективности для рассматриваемых вариантов каскадной схемы суммирования?

·  В чем состоит параллельный алгоритм вычисления всех частных сумм последовательности числовых значений?

·  Как формулируется закон Амдаля? Какой аспект параллельных вычислений позволяет учесть данный закон?

·  Какие предположения используются для обоснования закона Густавсона – Барсиса?

·  Как определяется функция изоэффективности?

·  Какой алгоритм является масштабируемым? Приведите примеры методов с разным уровнем масштабируемости.

·  Какие основные характеристики используются для оценки топологии сети передачи данных? Приведите значения характеристик для конкретных типов коммуникационных структур (полный граф, линейка, решетка и др.).

·  Какие основные методы применяются при маршрутизации передаваемых данных по сети?

·  В чем состоят основные методы передачи данных? Приведите для этих методов аналитические оценки времени выполнения.

·  Какие операции передачи данных могут быть выделены в качестве основных?

·  В чем состоят алгоритмы выполнения передачи данных от одного процессора всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.

·  В чем состоят алгоритмы выполнения передачи данных от всех процессоров всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.

·  В чем состоят возможные алгоритмы выполнения операции редукции? Какой из алгоритмов является наилучшим по времени выполнения?

·  В чем состоит алгоритм выполнения операции циклического сдвига?

·  В чем состоит полезность использования логических топологий? Приведите примеры алгоритмов логического представления структуры коммуникационной сети.

·  В чем состоит различие моделей для оценки времени выполнения операций передачи данных в кластерных вычислительных системах? Какая модель является более точной? Какая модель может быть использована для предварительного анализа временной трудоемкости коммуникационных операций?

·  В чем состоят исходные предположения для возможности применения рассмотренной в лекции методики разработки параллельных алгоритмов?

·  Каковы основные этапы проектирования и разработки методов параллельных вычислений?

·  Как определяется модель "подзадачи – сообщения"?

·  Как определяется модель "процессы – каналы"?

·  Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов?

·  В чем состоят основные действия на этапе выделения подзадач?

·  Каковы основные действия на этапе определения информационных зависимостей?

·  В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач?

·  В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы?

·  Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер – исполнитель"?

·  Какой метод параллельных вычислений был разработан для решения гравитационной задачи N тел?

·  Какой способ выполнения операции обобщенного сбора данных является более эффективным?

·  Назовите основные способы распределения элементов матрицы между процессорами вычислительной системы.

·  В чем состоит постановка задачи умножения матрицы на вектор?

·  Какова вычислительная сложность последовательного алгоритма умножения матрицы на вектор?

·  Почему при разработке параллельных алгоритмов умножения матрицы на вектор допустимо дублировать вектор-операнд на все процессоры?

·  Какие подходы могут быть предложены для разработки параллельных алгоритмов умножения матрицы на вектор?

·  Представьте общие схемы рассмотренных параллельных алгоритмов умножения матрицы на вектор.

·  Проведите анализ и получите показатели эффективности для одного из рассмотренных алгоритмов.

·  Какой из представленных алгоритмов умножения матрицы на вектор обладает лучшими показателями ускорения и эффективности?

·  Может ли использование циклической схемы разделения данных повлиять на время работы каждого из представленных алгоритмов?

·  Какие информационные взаимодействия выполняются для алгоритмов при ленточной схеме разделения данных? В чем различие необходимых операций передачи данных при разделении матрицы по строкам и столбцам?

·  Какие информационные взаимодействия выполняются для блочного алгоритма умножения матрицы на вектор?

·  Какая топология коммуникационной сети является целесообразной для каждого из рассмотренных алгоритмов?

·  Дайте общую характеристику программной реализации алгоритма умножения матрицы на вектор при разделении данных по строкам. В чем могут состоять различия в программной реализации других рассмотренных алгоритмов?

·  Какие функции библиотеки MPI оказались необходимыми при программной реализации алгоритмов?

·  В чем состоит постановка задачи умножения матриц?

·  Приведите примеры задач, в которых используется операция умножения матриц.

·  Приведите примеры различных последовательных алгоритмов выполнения операции умножения матриц. Отличается ли их вычислительная трудоемкость?

·  Какие способы разделения данных используются при разработке параллельных алгоритмов матричного умножения?

·  Представьте общие схемы рассмотренных параллельных алгоритмов умножения матриц.

·  Проведите анализ и получите показатели эффективности ленточного алгоритма при горизонтальном разбиении перемножаемых матриц.

·  Какие информационные взаимодействия выполняются для алгоритмов при ленточной схеме разделения данных?

·  Какие информационные взаимодействия выполняются для блочных алгоритмов умножения матриц?

·  Какая топология коммуникационной сети является целесообразной для каждого из рассмотренных алгоритмов?

·  Какой из рассмотренных алгоритмов характеризуется наименьшими и наибольшими требованиями к объему необходимой памяти?

·  Какой из рассмотренных алгоритмов обладает наилучшими показателями ускорения и эффективности?

·  Оцените возможность выполнения матричного умножения как последовательности операций умножения матрицы на вектор.

·  Дайте общую характеристику программной реализации алгоритма Фокса. В чем могут состоять различия в программной реализации других рассмотренных алгоритмов?

·  Какие функции библиотеки MPI оказались необходимыми при программной реализации алгоритмов?

·  Что представляет собой система линейных уравнений? Какие типы систем вам известны? Какие методы могут быть использованы для решения систем разных типов?

·  В чем состоит постановка задачи решения системы линейных уравнений?

·  В чем идея параллельной реализации метода Гаусса?

·  Какие информационные взаимодействия имеются между базовыми подзадачами для параллельного варианта метода Гаусса?

·  Каковы показатели эффективности для параллельного варианта метода Гаусса?

·  В чем состоит схема программной реализации параллельного варианта метода Гаусса?

·  В чем состоит идея параллельной реализации метода сопряженных градиентов?

·  Какой из алгоритмов обладает большей коммуникационной сложностью?

·  В чем состоит постановка задачи сортировки данных?

·  Приведите несколько примеров алгоритмов сортировки. Какова вычислительная сложность приведенных алгоритмов?

·  Какая операция является базовой для задачи сортировки данных?

·  В чем суть параллельного обобщения базовой операции задачи сортировки данных?

·  Что представляет собой алгоритм чет-нечетной перестановки?

·  В чем состоит параллельный вариант алгоритма Шелла? Каковы основные отличия этого параллельного алгоритма сортировки от метода чет-нечетной перестановки?

·  Что представляет собой параллельный вариант алгоритма быстрой сортировки?

·  Что зависит от правильного выбора ведущего элемента для параллельного алгоритма быстрой сортировки?

·  Какие способы выбора ведущего элемента могут быть предложены?

·  Для каких топологий могут применяться рассмотренные алгоритмы сортировки?

·  В чем состоит алгоритм сортировки с использованием регулярного набора образцов?

·  Приведите определение графа. Какие основные способы используются для задания графов?

·  В чем состоит задача поиска всех кратчайших путей?

·  Приведите общую схему алгоритма Флойда. Какова трудоемкость алгоритма?

·  В чем состоит способ распараллеливания алгоритма Флойда?

·  В чем заключается задача нахождения минимального охватывающего дерева? Приведите пример использования задачи на практике.

·  Приведите общую схему алгоритма Прима. Какова трудоемкость алгоритма?

·  В чем состоит способ распараллеливания алгоритма Прима?

·  В чем отличие геометрических и комбинаторных методов разделения графа? Какие методы являются более предпочтительными? Почему?

·  Приведите описание метода покоординатного разбиения и алгоритма разделения с учетом связности. Какой из этих методов является более простым для реализации?

·  Как определяется задача Дирихле для уравнения Пуассона?

·  В чем состоят основные положения метода конечных разностей?

·  Какие способы распараллеливания сеточных методов могут быть использованы для многопроцессорных вычислительных систем с общей памятью?

·  В каких ситуациях необходима синхронизация параллельных вычислений?

·  Как характеризуется поведение параллельных участков программы при наличии условий состязания потоков?

·  В чем состоит проблема взаимоблокировки?

·  Какие методы могут быть использованы для достижения однозначности результатов параллельных вычислений для сеточных методов?

·  Как изменяется объем вычислений при применении методов волновой обработки данных?

·  Как повысить эффективность методов волновой обработки данных?

·  Как очередь заданий позволяет улучшить балансировку вычислительной нагрузки процессоров?

·  Какие проблемы приходится решать при организации параллельных вычислений на системах с распределенной памятью?

·  Какие основные схемы распределения данных между процессорами могут быть использованы для сеточных методов?

·  Какие основные операции передачи данных используются в параллельных методах решения задачи Дирихле?

·  Каким образом организация множественной волны вычислений позволяет повысить эффективность волновых вычислений в системах с распределенной памятью?