Анализ трудоемкости операций передачи данных. Методы логического представления топологии коммуникационной среды. Построение алгоритма маршрутизации. Организация взаимодействия раздельно функционирующих процессов. Эффективность параллельных вычислений.
Аннотация к работе
3. Оценка коммуникационной трудоемкости параллельных алгоритмовОбщая характеристика механизмов передачи данных......................................................1 Передача данных между двумя процессорами сети.................................................3 3.2.2. Передача данных от одного процессора всем остальным процессорам сети .......3 3.2.3. Передача данных от всех процессоров всем процессорам сети.............................4 Как уже отмечалось ранее, временные задержки при передаче данных по каналам связи для организации взаимодействия раздельно функционирующих процессов могут в значительной степени определять эффективность параллельных вычислений.Так, для двумерной решетки такой подход приводит к маршрутизации, при которой передача данных сначала выполняется по одному направлению (например, по горизонтали до достижения вертикали процессоров, в которой располагается процессор назначения), а затем данные передаются вдоль другого направления (данная схема известна под названием алгоритма XY-маршрутизации). Для гиперкуба покоординатная схема маршрутизации может состоять, например, в циклической передаче данных процессору, определяемому первой различающейся битовой позицией в номерах процессоров, на котором сообщение располагается в данный момент времени и на который сообщение должно быть передано. Основной набор параметров, описывающих время передачи данных, состоит из следующего ряда величин: - время начальной подготовки (тн) характеризует длительность подготовки сообщения для передачи, поиска маршрута в сети и т.п.; При таком подходе процессор, содержащий сообщение для передачи, готовит весь объем данных для передачи, определяет процессор, которому следует направить данные, и запускает операцию пересылки данных. Важно отметить также, что в рамках подобного базового набора для большинства операций коммуникации существуют процедуры, обратные по действию исходным операциям (так, например, операции передачи данных от одного процессора всем имеющимся процессорам сети соответствует операция приема в одном процессоре сообщений от всех остальных процессоров).
Список литературы
Гергель, В.П., Стронгин, Р.Г. (2001). Основы параллельных вычислений для многопроцессорных вычислительных систем. - Н.Новгород, ННГУ (2 изд., 2003).
Culler, D.E., et al. (1996). LOGP: A practical model for parallel computation. - Comm. Of the ACM, 39, 11, pp. 75-85.
Hockney, R. (1994). The communication challenge for MPP: Intel Paragon and Meiko CS-2. - Parallel Computing, 20 (3), pp. 389-398.
Kumar V., Grama, A., Gupta, A., Karypis, G. (1994). Introduction to Parallel Computing. - The Benjamin/Cummings Publishing Company, Inc. (2nd edn., 2003)
Quinn, M. J. (2004). Parallel Programming in C with MPI and OPENMP. - New York, NY: MCGRAW-Hill.
Skillicorn, D.B., Talia, D. (1998). Models and languages for parallel computation. - ACM Computing surveys, 30, 2.