Теория и практика параллельных вычислений



   http://www.financemasters.ru            

Определение подзадач и выделение информационных зависимостей - часть 2


Как результат, общее количество итераций может быть сокращено, и для фиксации таких моментов необходимо введение некоторого управляющего процессора, который определял бы состояние набора данных после выполнения каждой итерации сортировки. Однако трудоемкость такой коммуникационной операции (сборка на одном процессоре сообщений от всех процессоров) может оказаться столь значительной, что весь эффект от возможного сокращения итераций сортировки будет поглощен затратами на реализацию операций межпроцессорной передачи данных.

Таблица 9.1. Пример сортировки данных параллельным методом чет-нечетной перестановки

№ и тип итерациПроцессоры1234
Исходные данные13 55 59 8829 43 71 852 18 40 754 14 22 43
1 нечет (1, 2), (3, 4)13 55 59 8829 43 71 852 18 40 754 14 22 43
13 29 43 5559 71 85 882 4 14 1822 40 43 75
2 чет (2, 3)13 29 43 5559 71 85 882 4 14 1822 40 43 75
13 29 43 552 4 14 1859 71 85 8822 40 43 75
3 нечет (1, 2), (3, 4)13 29 43 552 4 14 1859 71 85 8822 40 43 75
2 4 13 1418 29 43 5522 40 43 5971 75 85 88
4 чет (2, 3)2 4 13 1418 29 43 5522 40 43 5971 75 85 88
2 4 13 1418 22 29 4043 43 55 5971 75 85 88




Содержание  Назад  Вперед