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


Определение времени выполнения параллельного алгоритма - часть 2


использовать величину

где операция минимума берется по множеству всех возможных последовательных алгоритмов решения данной задачи.

Приведем без доказательства теоретические положения, характеризующие свойства оценок времени выполнения параллельного алгоритма (см. [22]).

Теорема 1. Минимально возможное время выполнения параллельного алгоритма определяется длиной максимального пути вычислительной схемы алгоритма, т.е.

T?(G)=d(G).

Теорема 2. Пусть для некоторой вершины вывода в вычислительной схеме алгоритма существует путь из каждой вершины ввода. Кроме того, пусть входная степень вершин схемы (количество входящих дуг) не превышает 2. Тогда минимально возможное время выполнения параллельного алгоритма ограничено снизу значением

T?(G)=log2n,

где n есть количество вершин ввода в схеме алгоритма.

Теорема 3. При уменьшении числа используемых процессоров время выполнения алгоритма увеличивается пропорционально величине уменьшения количества процессоров, т.е.

q=cp, 0<c<1TpcTq.

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

pTp<T?+T1/p.

Теорема 5. Времени выполнения алгоритма, которое сопоставимо с минимально возможным временем T?, можно достичь при количестве процессоров порядка p~T1/T?, а именно,

pT1/T?Tp2T?.

При меньшем количестве процессоров время выполнения алгоритма не может превышать более чем в 2 раза наилучшее время вычислений при имеющемся числе процессоров, т.е.

Приведенные утверждения позволяют дать следующие рекомендации по правилам формирования параллельных алгоритмов:

  1. при выборе вычислительной схемы алгоритма должен использоваться граф с минимально возможным диаметром (см. теорему 1);
  2. для параллельного выполнения целесообразное количество процессоров определяется величиной p~T1/T? (см. теорему 5);
  3. время выполнения параллельного алгоритма ограничивается сверху величинами, приведенными в теоремах 4 и 5.

Для вывода рекомендаций по формированию расписания по параллельному выполнению алгоритма приведем доказательство теоремы 4.




Начало  Назад  Вперед



Книжный магазин