Лекция 16. Алгоритмларнинг коммуникацион мураккаблигини баҳолаш

Маълумотларни узатиш асосий операция ларининг мураккаблигини таҳлил қилиш

• Тармоқдаги битта процессордан бошқа барча процессорларга маълумотларни узатиш(передача сообщений)

Для гиперкуба рассылка может быть выполнена в ходе N- этапной процедуры передачи данных. На первом этапе процессор-источник сообщения передает данные одному из своих соседей – в результате после первого этапа имеется два процессора, имеющих копию пересылаемых данных. На втором этапе два процессора, задействованные на первом этапе, пересылают сообщение своим соседям по второй размерности и т.д.
В результате такой рассылки время операции уменьшается в разы Гиперку́б — обобщение куба на случай с произвольным числом измерений. Гиперкубом размерности Ν называется множество точек в Ν-мерном евклидовом пространстве .
Маълумотларни узатиш асосий операция ларининг мураккаблигини таҳлил қилиш

• Тармоқдаги битта процессордан бошқа барча процессор ларга маълумотларни узатиш(передача пакетов)…

Халқа топологияси учун тарқатиш алгоритми гиперкуб кўрини шида тармоқнинг халқа структураси тасвирини мантиқий кўри ниш йўли билан олиш мумкин.Натижада тарқатиш босқичида хабар процессор-манбаси p/2 масофада жойлашган тарқата ётган процессордан маълумотларни узатади.Кейин иккинчи босқичда иккала процессор (энди уларда тарқатилаётган маълумотлар мавжуд) хабарларни p/4 масофада жойлашган процессорларга узатади Бу жараён шу йўсинда давом этаверади.
Для топологии типа кольца алгоритм рассылки может быть получен путем логического представления кольцевой структуры сети в виде гиперкуба. В результате на этапе рассылки процессор-источник сообщения передает данные процессору, находящемуся на расстоянии p/2 от исходного процессора. Далее, на втором этапе оба процессора, уже имеющие рассылаемые данные после первого этапа, передают сообщения процессорам, находящиеся на расстоянии p/4 и т.д.