Каждый процессор Pi вычисляет di[u] = min{d[v]v  (V – VT) Vi} за каждую итерацию цикла while. Затем вычисляется общий минимум из всех di[u] (уменьшение типа «все к одному», т. е. из результатов, получившихся на каждом процессоре, вычисляется один итоговый результат) и запоминается в процессоре P0. Процессор P0 сейчас содержит новую вершину u, которая будет вставлена в VТ. Процессор P0 пересылает u всем процессорам (трансляция «один ко всем», т. е. широковещательная передача данных от одного процессора всем). Процессор Pi, ответственный за вершину u, отмечает, что u принадлежит множеству VT. В итоге каждый процессор обновляет значения d[v] для своих локальных вершин.
Когда новая вершина u внесена в VT, значения d[v] для v  (V – VT) должны быть обновлены. Процессор, вычисляющий значение для v, должен знать вес ребра (u, v). Поэтому каждому процессору Pi нужно хранить столбцы взвешенной матрицы смежностей, соответствующие множеству Vi вершин, присвоенных ему. Объем памяти для хранения необходимой части матрицы смежностей на каждом процессоре равен (n2 / p).




Любая работа на ваш выбор. Быстрый и удобный поиск работы.