Теория и практика параллельных вычислений
Выделение информационных зависимостей
Выполнение вычислений в подзадачах становится возможным только тогда, когда каждая подзадача (i, j) содержит необходимые для расчетов элементы Aij, Aik, Akj матрицы A. Для исключения дублирования данных разместим в подзадаче (i, j) единственный элемент Aij, тогда получение всех остальных необходимых значений может быть обеспечено только при помощи передачи данных. Таким образом, каждый элемент Akj строки k матрицы A должен быть передан всем подзадачам (k, j), 1jn, а каждый элемент Aik
столбца k матрицы A должен быть передан всем подзадачам (i, k), 1in,– см. рис. 10.3.
Рис. 10.3. Информационная зависимость базовых подзадач (стрелками показаны направления обмена значениями на итерации k)
С учетом выбора базовых подзадач общая схема параллельного выполнения алгоритма Прима будет состоять в следующем:
- определяется вершина t графа G, имеющая дугу минимального веса до множества VT. Для выбора такой вершины необходимо осуществить поиск минимума в наборах величин di, имеющихся на каждом из процессоров, и выполнить сборку полученных значений на одном из процессоров;
- номер выбранной вершины для включения в охватывающее дерево передается всем процессорам;
- обновляются наборы величин di с учетом добавления новой вершины.
Таким образом, в ходе параллельных вычислений между процессорами выполняются два типа информационных взаимодействий: сбор данных от всех процессоров на одном из процессоров и передача сообщений от одного процессора всем процессорам вычислительной системы.
