uzluga.ru
добавить свой файл
  1 2 3 4 ... 13 14

Оценка наиболее быстрого исполнения алгоритма (при использовании паракомпьютера – системы с неограниченным числом процессоров):



Время выполнения последовательного алгоритма для заданной вычислительной схемы:

  • Время выполнения последовательного алгоритма для заданной вычислительной схемы:

  • Время выполнения последовательного алгоритма:

  • Время последовательного решения задачи:



Теорема 1

  • Теорема 1

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



Теорема 2

  • Теорема 2

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

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



Теорема 3

  • Теорема 3

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



Теорема 4

  • Теорема 4

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



Теорема 5



Рекомендации

  • Рекомендации

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


Строгая параллельная форма

  • Строгая параллельная форма

    • Вершины графа помечаются одним из индексов 1,2,…,s, s<n,
    • Разметка должна быть такой, что, если из вершина i есть дуга в вершину j, то i<j


Каноническая параллельная форма

  • Каноническая параллельная форма

    • Максимальная длина пути для вершины i равна i-1


Пример: Граф операции матричного умножения

  • Пример: Граф операции матричного умножения

  • for (i=0; i

  • for (j=0; j

  • a[i][j] = 0;

  • for (k=0; k

  • a[i][j] = a[i][j] +

  • b[i][k]*c[k][j];

  • }



Задача нахождения частных сумм последовательности числовых значений



<< предыдущая страница   следующая страница >>