Ю.М. Руденко
6
Рис. 3.
Диаграмма размещения нитей на поле процессоров вычислительной
системы типа «Циркулянт»
G
(11, 1, 2, 5)
Для реализации граф-схемы, представленной на рис. 1, как следу-
ет из диаграммы рис. 3, требуется семь процессоров без учета по-
строения связей между ними. Образовались следующие нити:
T0 1, 2, 5 ,
T1 6 ,
T2 7 ,
T3 8 ,
T4 9 ,
T5 10 ,
T6 3, 11, 12 ,
Т7 4 ,
Т8 13 ,
Т9 14 ,
Т10 15 .
Элементами множеств, образующих нити, являются программные
блоки рассматриваемой граф-схемы. Блок 1 нити Т0 связан с нитями
Т6 (блок 3) и Т7 (блок 4) в момент времени
6
t
. Заштрихованная
часть блока 3 обозначает простой процессора 7. Этот простой связан с
необходимостью одновременного прихода данных в блок 11. Характер
построенной диаграммы позволяет объединить нити Т3 и Т10, Т4 и Т9,
а также Т7, Т5 и Т8. Простои вычислительных модулей 4, 5, 6 опреде-
ляются структурой решаемой задачи и не могут быть исключены.
Рассмотрим структуру вычислительной системы типа «Цирку-
лянт»
G
(11, 1, 2, 5). Матрица дистанций для этой структуры, вычис-
ленная по формуле (1), представлена на рис. 4.
Покажем размещение нитей на вычислительной системе типа
«Циркулянт»
G
(11, 1, 2, 5), используя рис. 5. Вычислительные модули,
загруженные нитями, размещены на графе в виде закрашенных вершин.
Вначале размещаются нити цикла алгоритма Т0…Т6. Затем дела-
ется попытка разместить все остальные нити. На отметке времени
6
t
(см. рис. 3) осуществляется обмен данными между нитями Т0 и
Т6, Т7: вначале между нулевым и шестым вычислительными моду-
лями с помощью прямой связи (см. рис. 5), затем между нулевым и
седьмым модулями через транзитный модуль 9. При значении време-
ни
11
t
(см. рис. 3) необходимо обеспечить связь между нитями Т0
и Т1, Т2, Т3, Т4, Т5. Соединение нитей Т0, Т1, Т2, Т5, Т6 осуществ-
