Принципы построения параллельных вычислительных систем

1. В чем заключаются основные способы достижения параллелизма?
2. В чем могут состоять различия параллельных вычислительных систем?
3. Что положено в основу классификация Флинна?
4. В чем состоит принцип разделения многопроцессорных систем на мультипроцессоры и мультикомпьютеры?
5. Какие классы систем известны для мультипроцессоров?
6. В чем состоят положительные и отрицательные стороны симметричных мультипроцессоров?
7. Какие классы систем известны для мультикомпьютеров?
8. В чем состоят положительные и отрицательные стороны кластерных систем?
9. Какие топологии сетей передачи данных наиболее широко используются при построении многопроцессорных систем?
10. В чем состоят особенности сетей передачи данных для кластеров?
11. Каковы основные характеристики сетей передачи данных?
12. Какие системные платформы могут быть использованы для построения кластеров?

Модели вычислений и методы анализа эффективности

1. Как определяется модель "операция - операнды"?
2. Как определяется расписание для распределения вычислений между процессорами?
3. Как определяется время выполнения параллельного алгоритма?
4. Какое расписание является оптимальным?
5. Как определить минимально возможное время решения задачи?
6. Что понимается под паракомпьютером и для чего может оказаться полезным данное понятие?
7. Какие оценки следует использовать в качестве характеристики времени последовательного решения задачи?
8. Как определить минимально возможное время параллельного решения задачи по графу "операнды – операции"?
9. Какие зависимости могут быть получены для времени параллельного решения задачи при увеличении или уменьшения числа используемых процессоров?
10. При каком числе процессоров могут быть получены времена выполнения параллельного алгоритма, сопоставимые по порядку с оценками минимально возможного времени решения задачи?
11. Как определяются понятия ускорения и эффективности?
12. Возможно ли достижение сверхлинейного ускорения?
13. В чем состоит противоречивость показателей ускорения и эффективности?
14. Как определяется понятие стоимости вычислений?
15. В чем состоит понятие стоимостно-оптимального алгоритма?
16. В чем заключается проблема распараллеливания последовательного алгоритма суммирования числовых значений?
17. В чем состоит каскадная схема суммирования? С какой целью рассматривается модифицированный вариант данной схемы?
18. В чем различие показателей ускорения и эффективности для рассматриваемых вариантов каскадной схемы суммирования?
19. В чем состоит параллельный алгоритм вычисления всех частных сумм последовательности числовых значений?
20. Как формулируется закон Амдаля? Какой аспект параллельных вычислений позволяет учесть данный закон?
21. Какие предположения используются для обоснования закона Густавсона-Барсиса?
22. Как определяется функция изоэффективности?
23. Какой алгоритм является масштабируемым? Приведите примеры методов с разным уровнем масштабируемости.

Анализ коммуникационной трудоемкости параллельных алгоритмов

1. Какие основные характеристики используются для оценки топологии сети передачи данных? Приведите значения характеристик для конкретных типов коммуникационных структур (полный граф, линейка, решетка и др.).
2. Какие основные методы применяются при маршрутизации передаваемых данных по сети?
3. В чем состоят основные методы передачи данных? Приведите для этих методов аналитические оценки времени выполнения?
4. Какие операции передачи данных могут быть выделены в качестве основных?
5. В чем состоят алгоритмы выполнения передачи данных от одного процессора всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.
6. В чем состоят алгоритмы выполнения передачи данных от всех процессоров всем процессорам сети для топологий кольца, решетки и гиперкуба? Приведите оценки временной трудоемкости для этих алгоритмов.
7. В чем состоят возможные алгоритмы выполнения операции редукции? Какой из алгоритмов является наилучшим по времени выполнения?
8. В чем состоят алгоритм выполнения операции циклического сдвига?
9. В чем состоит полезность использования логических топологий? Приведите примеры алгоритмов логического представления структуры коммуникационной сети?
10. В чем различие моделей для оценки времени выполнения операций передачи данных в кластерных вычислительных системах? Какая модель является более точной? Какая модель может быть использована для предварительного анализа временной трудоемкости коммуникационных операций?

Технология разработки параллельных программ для многопроцессорных систем с распределенной памятью (стандарт передачи сообщений MPI)

1. Какой минимальный набор средств является достаточным для организации параллельных вычислений в системах с распределенной памятью?
2. В чем состоит важность стандартизации средств передачи сообщений?
3. Что следует понимать под параллельной программой?
4. В чем различие понятий процесса и процессора?
5. Какой минимальный набор функций MPI позволяет начать разработку параллельных программ?
6. Как описываются передаваемые сообщения?
7. Как можно организовать прием сообщений от конкретных процессов?
8. Как определить время выполнения MPI программы?
9. В чем различие парных и коллективных операций передачи данных?
10. Какая функция MPI обеспечивает передачу данных от одного процесса всем процессам?
11. Что понимается под операцией редукции?
12. В каких ситуациях следует применять барьерную синхронизацию?
13. Какие режимы передачи данных поддерживаются в MPI?
14. Как организуется неблокирующий обмен данными в MPI?
15. В чем состоит понятие тупика? В каких ситуациях функция одновременного выполнения передачи и приема гарантирует отсутствие тупиковых ситуаций?
16. Какие коллективные операции передачи данных предусмотрены в MPI?
17. Что понимается под производным типом данных в MPI?
18. Какие способы конструирования типов имеются в MPI?
19. В каких ситуациях может быть полезна упаковка и распаковка данных?
20. Что понимается в MPI под коммуникатором?
21. Для чего может потребоваться создание новых коммуникаторов?
22. Что понимается в MPI под виртуальной топологией?
23. Какие виды топологий предусмотрены в MPI?
24. Для чего может оказаться полезным использование виртуальных топологий?
25. В чем состоят особенности разработки параллельных программ с использованием MPI на алгоритмическом языке Fortran?
26. Какие основные дополнительные возможности предусмотрены в стандарте MPI-2?

Принципы разработки параллельных методов

1. В чем состоят исходные предположения для возможности применения рассмотренной в разделе методики разработки параллельных алгоритмов?
2. Каковы основные этапы проектирования и разработки методов параллельных вычислений?
3. Как определяется модель "подзадачи-сообщения"?
4. Как определяется модель "процессы-каналы"?
5. Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов?
6. В чем состоят основные действия на этапе выделения подзадач?
7. Каковы основные действия на этапе определения информационных зависимостей?
8. В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач?
9. В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы?
10. Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер - исполнитель"?
11. Какой метод параллельных вычислений был разработан для решения гравитационной задачи N тел?
12. Какой способ выполнения операции обобщенного сбора данных является более эффективным?

Параллельные численные алгоритмы для решения типовых задач вычислительной математики (матрично-векторное умножение)

1. Назовите основные способы распределения элементов матрицы между процессорами вычислительной системы.
2. В чем состоит постановка задачи умножения матрицы на вектор?
3. Какова вычислительная сложность последовательного алгоритма умножения матрицы на вектор?
4. Почему при разработке параллельных алгоритмов умножения матрицы на вектор допустимо дублировать вектор-операнд на все процессоры?
5. Какие подходы могут быть предложены для разработки параллельных алгоритмов умножения матрицы на вектор?
6. Представьте общие схемы рассмотренных параллельных алгоритмов умножения матрицы на вектор.
7. Проведите анализ и получите показатели эффективности для одного из рассмотренных алгоритмов.
8. Какой из представленных алгоритмов умножения матрицы на вектор обладает лучшими показателями ускорения и эффективности?
9. Может ли использование циклической схемы разделения данных повлиять на время работы каждого из представленных алгоритмов?
10. Какие информационные взаимодействия выполняются для алгоритмов при ленточной схеме разделения данных? В чем различие необходимых операций передачи данным при разделении матрицы по строкам и столбцам?
11. Какие информационные взаимодействия выполняются для блочного алгоритма умножения матрицы на вектор?
12. Какая топология коммуникационной сети является целесообразной для каждого из рассмотренных алгоритмов?
13. Дайте общую характеристику программной реализации алгоритма умножения матрицы на вектор при разделении данных по строкам. В чем могут состоять различия в программной реализации других рассмотренных алгоритмов?
14. Какие функции библиотеки MPI оказались необходимыми при программной реализации алгоритмов?

Параллельные численные алгоритмы для решения типовых задач вычислительной математики (матричное умножение)

1. В чем состоит постановка задачи умножения матриц?
2. Приведите примеры задач, в которых используется операция умножения матриц.
3. Приведите примеры различных последовательных алгоритмов выполнения операции умножения матриц. Отличается ли их вычислительная трудоемкость?
4. Какие способы разделения данных используются при разработке параллельных алгоритмов матричного умножения?
5. Представьте общие схемы рассмотренных параллельных алгоритмов умножения матриц.
6. Проведите анализ и получите показатели эффективности ленточного алгоритма при горизонтальном разбиении перемножаемых матриц.
7. Какие информационные взаимодействия выполняются для алгоритмов при ленточной схеме разделения данных?
8. Какие информационные взаимодействия выполняются для блочных алгоритмов умножения матриц?
9. Какая топология коммуникационной сети является целесообразной для каждого из рассмотренных алгоритмов?
10. Какой из рассмотренных алгоритмов характеризуется наименьшими и наибольшими требованиями к объему необходимой памяти?
11. Какой из рассмотренных алгоритмов обладает наилучшими показателями ускорения и эффективности?
12. Оцените возможность выполнения матричного умножения как последовательности операций умножения матрицы на вектор.
13. Дайте общую характеристику программной реализации алгоритма Фокса. В чем могут состоять различия в программной реализации других рассмотренных алгоритмов?
14. Какие функции библиотеки MPI оказались необходимыми при программной реализации алгоритмов?

Параллельные численные алгоритмы для решения типовых задач вычислительной математики (решение систем линейных уравнений)

1. Что представляет собой система линейных уравнений? Какие типы систем вам известны? Какие методы могут быть использованы для решения систем разных типов?
2. В чем состоит постановка задачи решения системы линейных уравнений?
3. В чем идея параллельной реализации метода Гаусса?
4. Какие информационные взаимодействия имеются между базовыми подзадачами для параллельного варианта метода Гаусса?
5. Какие показатели эффективности для параллельного варианта метода Гаусса?
6. В чем состоит схема программной реализации параллельного варианта метода Гаусса?
7. В чем состоит идея параллельной реализации метода сопряженных градиентов?
8. Какой из алгоритмов обладает большей коммуникационной сложностью?

Параллельные численные алгоритмы для решения типовых задач вычислительной математики (сортировка данных)

1. В чем состоит постановка задачи сортировки данных?
2. Приведите несколько примеров алгоритмов сортировки? Какова вычислительная сложность приведенных алгоритмов?
3. Какая операция является базовой для задачи сортировки данных?
4. В чем суть параллельного обобщения базовой операции задачи сортировки данных?
5. Что представляет собой алгоритм чет-нечетной перестановки?
6. В чем состоит параллельный вариант алгоритма Шелла? Какие основные отличия этого варианта параллельного алгоритма сортировки от метода чет-нечетной перестановки?
7. Что представляет собой параллельный вариант алгоритма быстрой сортировки?
8. Что зависит от правильного выбора ведущего элемента для параллельного алгоритма быстрой сортировки?
9. Какие способы выбора ведущего элемента могут быть предложены?
10. Для каких топологий могут применяться рассмотренные алгоритмы сортировки?
11. В чем состоит алгоритм сортировки с использованием регулярного набора образцов?

Параллельные численные алгоритмы для решения типовых задач вычислительной математики (обработка графов)

1. Приведите определение графа. Какие основные способы используются для задания графов?
2. В чем состоит задача поиска всех кратчайших путей?
3. Приведите общую схему алгоритма Флойда. Какова трудоемкость алгоритма?
4. В чем состоит способ распараллеливания алгоритма Флойда?
5. В чем заключается задача нахождения минимального охватывающего дерева? Приведите пример использования задачи на практике.
6. Приведите общую схему алгоритма Прима. Какова трудоемкость алгоритма?
7. В чем состоит способ распараллеливания алгоритма Прима?
8. В чем отличие геометрических и комбинаторных методов разделения графа? Какие методы являются более предпочтительными? Почему?
9. Приведите описание метода покоординатного разбиения и алгоритма разделения с учетом связности. Какой из этих методов является более простым для реализации?

Параллельные численные алгоритмы для решения типовых задач вычислительной математики (уравнения в частных производных)

1. Как определяется задача Дирихле для уравнения Пуассона?
2. Как метод конечных разностей применяется для решения задачи Дирихле?
3. Какие способы определяют организацию параллельных вычислений для сеточных методов на многопроцессорных вычислительных системах с общей памятью?
4. В чем состоит проблема синхронизации параллельных вычислений?
5. Как характеризуется поведение параллельных участков программы, которое именуется состязанием потоков (race condition)?
6. В чем состоит проблема взаимоблокировки?
7. Какой метод гарантирует однозначность результатов сеточных методов независимо от способа распараллеливания, но требует использования большого дополнительного объема памяти?
8. Как изменяется объем вычислений при применении методов волновой обработки данных?
9. Что такое фрагментирование (chunking)?
10. Как повысить эффективность методов волновой обработки данных?
11. Как очередь заданий позволяет балансировать нагрузку процессорам?
12. Какие проблемы приходится решать при организации параллельных вычислений на системах с распределенной памятью?
13. Какие механизмы могут быть задействованы для передачи данных?
14. Каким образом организация множественной волны вычислений позволяет повысить эффективность волновых вычислений в системах с распределенной памятью?

<< вернуться  |   Документ от: 04.09.2007 13:35