Теория и практика параллельных вычислений

         

Выделение информационных зависимостей


С учетом выбора базовых подзадач общая схема параллельного выполнения алгоритма Прима будет состоять в следующем:

  • определяется вершина t графа G, имеющая дугу минимального веса до множества VT. Для выбора такой вершины необходимо осуществить поиск минимума в наборах величин di, имеющихся на каждом из процессоров, и выполнить сборку полученных значений на одном из процессоров;
  • номер выбранной вершины для включения в охватывающее дерево передается всем процессорам;
  • обновляются наборы величин di с учетом добавления новой вершины.

Таким образом, в ходе параллельных вычислений между процессорами выполняются два типа информационных взаимодействий: сбор данных от всех процессоров на одном из процессоров и передача сообщений от одного процессора всем процессорам вычислительной системы.



Содержание  Назад  Вперед







Forekc.ru
Рефераты, дипломы, курсовые, выпускные и квалификационные работы, диссертации, учебники, учебные пособия, лекции, методические пособия и рекомендации, программы и курсы обучения, публикации из профильных изданий