Модель HBJ

В информатике модель Хелмана -Бейдера-ДжаДжа. ^[1] представляет собой краткую модель параллельных вычислений с передачей сообщений , определяемую следующими параметрами:

$p$ количество процессоров.
$n$ размер проблемы.
$m$ количество машинных слов в пакете, отправляемом по сети.
$\tau$ — это задержка или время, необходимое процессору для инициации связи в сети.
$\sigma$ — это пропускная способность или время на одно машинное слово, с которым процессор может вводить или получать $m$ машинные слова из сети.
$T_{comp}$ — это наибольшее время вычислений, затрачиваемое процессором.
$T_{comm}$ это время, проведенное в общении в сети.

Эта модель предполагает, что для любого подмножества $q$ процессоры, перестановка блоков среди $q$ процессоры занимают $(\tau +\sigma m)$ время, где $m$ — размер самого большого блока.

Анализ распространенных параллельных алгоритмов [ править ]

Сложности распространенных параллельных алгоритмов, содержащихся в библиотеках MPI : ^[2]

Связь «точка-точка»: $O(\tau +\sigma m)$
Снижение : $O(log(p)(\tau +\sigma m))$
Транслировать: $O(log(p)(\tau +\sigma m))$
Параллельный префикс: $O(log(p){n \over p}(\tau +\sigma m))$
Все всем: $O(p(\tau +\sigma m)))$

Ссылки [ править ]

^ Дэвид Р., Хелман; Дэвид А., Бадер; ДжаДжа, Джозеф (1998). «Рандомизированный алгоритм параллельной сортировки с экспериментальным исследованием» (PDF) . Журнал параллельных и распределенных вычислений . 52 : 1–23. дои : 10.1006/jpdc.1998.1462 . HDL : 1903/835 . Проверено 26 октября 2012 г. ^{[ мертвая ссылка ]}
^ Бадер, Дэвид А.; Джаджа, Джозеф (1996). «Практические параллельные алгоритмы для динамического перераспределения данных, поиска и выбора медианы». Материалы 10-го Международного симпозиума IEEE по параллельной обработке : 292–301.

Эта по информатике статья незавершена . Вы можете помочь Википедии, расширив ее .

[1] Дэвид Р., Хелман; Дэвид А., Бадер; ДжаДжа, Джозеф (1998). «Рандомизированный алгоритм параллельной сортировки с экспериментальным исследованием» (PDF) . Журнал параллельных и распределенных вычислений . 52 : 1–23. дои : 10.1006/jpdc.1998.1462 . HDL : 1903/835 . Проверено 26 октября 2012 г. ^{[ мертвая ссылка ]}

[2] Бадер, Дэвид А.; Джаджа, Джозеф (1996). «Практические параллельные алгоритмы для динамического перераспределения данных, поиска и выбора медианы». Материалы 10-го Международного симпозиума IEEE по параллельной обработке : 292–301.

[1]

[2]