Теория и практика параллельных вычислений
Краткий обзор лекции
Данная лекция посвящена оценке коммуникационной сложности параллельных алгоритмов.
В подразделе 3.1 представлена общая характеристика алгоритмов маршрутизации и методов передачи данных. Для подробного рассмотрения выделены метод передачи сообщений и метод передачи пакетов, для которых определены оценки времени выполнения коммуникационных операций.
В подразделе 3.2 определены основные типы операций передачи данных, выполняемых в ходе параллельных вычислений. К основным коммуникационным операциям относятся:
- передача данных между процессорами сети;
- передача данных от одного процессора всем остальным процессорам сети и двойственная ей операция приема на одном процессоре сообщений от всех остальных процессоров сети;
- передача данных от всех процессоров всем процессорам сети и двойственная ей операция приема сообщений на каждом процессоре от всех процессоров сети;
- обобщенная1) передача данных от одного процессора всем остальным процессорам сети и обратная операция обобщенного приема сообщений на одном процессоре от всех остальных процессоров сети;
- обобщенная передача данных от всех процессоров всем процессорам сети.
Для всех перечисленных операций передачи данных рассмотрены алгоритмы их выполнения на примере топологий кольца, решетки и гиперкуба. Для каждого из представленных алгоритмов приведены оценки их временной трудоемкости как для метода передачи сообщений, так и для метода передачи пакетов.
В подразделе 3.3 рассмотрены методы логического представления топологий на основе конкретных (физических) межпроцессорных структур. Использование логических топологий позволяет получить более простое изложение для ряда алгоритмов передачи данных, снизить затраты на реализацию коммуникационных операций и т.п.
В подразделе 3.4 более подробно обсуждаются модели, при помощи которых могут быть получены оценки времени выполнения операций передачи данных для кластерных вычислительных систем. Точность формирования временных оценок сравнивается при помощи проведения вычислительных экспериментов. По результатам экспериментов определена наиболее точная модель (модель B). Кроме того, отмечается, что для предварительного анализа временной трудоемкости коммуникационных операций целесообразно использовать более простую модель – модель C (модель Хокни).
