Трансляция (параллельный шаблон)

Широковещательная рассылка — это коллективный коммуникационный примитив в параллельном программировании для распространения программных инструкций или данных на узлы в кластере, это обратная операция сокращения. ^[1] Широковещательная операция широко используется в параллельных алгоритмах, таких как умножение матрицы на вектор, ^[1] исключение Гаусса и поиск кратчайших путей . ^[2]

Сообщение длины n должно быть распространено от одного узла ко всем другим узлам.${\ Displaystyle М [1.. м]}$${\ Displaystyle р-1}$

${\ Displaystyle Т _ {\ текст {байт}}}$это время, необходимое для отправки одного байта.

${\ Displaystyle Т _ {\ текст {начало}}}$это время, необходимое сообщению для перемещения к другому узлу, независимо от его длины.

Следовательно, время отправки пакета от одного узла к другому равно . ^[1]${\ displaystyle t = size * T _ {\ text {байт}} + T _ {\ text {начало}}}$

${\ Displaystyle р}$это количество узлов и количество процессоров.

Трансляция биномиального дерева

Конвейерная трансляция

Конвейерная широковещательная передача двоичного дерева

Визуализация трансляции двух деревьев

Примеры древовидных структур в зависимости от количества процессоров

Построение дерева с помощью "Shifting"

Построение дерева с использованием зеркалирования