Лекции по параллельным вычислениям. Гергель В.П - 100 стр.

UptoLike

Составители:

Рубрика:

100

Лекция 8

Распараллеливание алгоритмов

по информационному графу

8.1 Постановки задач распараллеливания

Как уже отмечалось выше, основная проблема конструирования эффектив-

ных параллельных алгоритмов, по существу, всегда сводится к решению, с той

или иной степенью строгости, проблемы отображения графа алгоритма на ар-

хитектуру вычислительной системы. В рамках подхода, основанного на исполь-

зовании взвешенных направленных графов, обычно рассматриваются следую-

щие две взаимно обратные задачи.

Задача 1. Для данного алгоритма, которому соответствует информацион-

ный граф G со скалярными весами вершин, и для времени T, отведенного для

его выполнения, найти наименьшее необходимое число n процессоров, входя-

щих в состав однородной вычислительной системы (ВС), и план выполнения

операторов на них.

Задача 2. Для данного алгоритма, которому соответствует информацион-

ный граф G со скалярными весами вершин, найти минимальное время T и план

реализации этого алгоритма на данной однородной ВС, в состав которой входят

n процессоров.

При решении этих задач в настоящей лекции не будем учитывать потери

времени на обмен информацией между процессорами. Такая ситуация может

соответствовать отсутствию обмена данными между процессорами или нали-

чию в ВС либо общей оперативной памяти, либо высокоскоростных каналов

обмена данными, так что временем межпроцессорного обмена можно пренеб-

речь.