абстрактная параллельная ЭВМ с общей памятью
PRAM
При оценке эффективности параллельного алгоритма широко используется модель абстрактной параллельной ЭВМ с общей памятью – PRAM (Parallel Random Access Machine). Модель предполагает, что все процессоры PRAM идентичны. Имеется три типа PRAM, отличающихся моделью того, что происходит при одновременном обращении нескольких процессоров к одной ячейке памяти: модель EREW PRAM – одновременная запись и чтение из одной ячейки запрещены; модель CREW PRAM – разрешается одновременное чтение из одной ячейки памяти, но не разрешается одновременная запись; модель CRCW PRAM – разрешается как одновременное чтение из одной ячейки памяти, так и одновременная запись. Эффективность алгоритма для PRAM определяется временем исполнения, как функцией длины входного вектора задачи n и количества процессоров N.
EREW PRAM
Имеется три типа абстрактной параллельной ЭВМ с общей памятью (PRAM), отличающихся моделью того, что происходит при одновременном обращении нескольких процессоров к одной ячейке памяти. В модели EREW PRAM запрещены одновременная запись и чтение из одной ячейки памяти.
CREW PRAM
Имеется три типа абстрактной параллельной ЭВМ с общей памятью (PRAM), отличающихся моделью того, что происходит при одновременном обращении нескольких процессоров к одной ячейке памяти. В модели CREW PRAM разрешается одновременное чтение из одной ячейки памяти, но не разрешается одновременная запись.
CRCW PRAM
Имеется три типа абстрактной параллельной ЭВМ с общей памятью (PRAM), отличающихся моделью того, что происходит при одновременном обращении нескольких процессоров к одной ячейке памяти. В модели CRCW PRAM разрешается как одновременное чтение из одной ячейки памяти, так и одновременная запись.
эффективный параллельный алгоритм
Одной из центральных проблем науки о параллельных вычислениях является выделение классов задач, для решения которых существуют эффективные параллельные алгоритмы – алгоритмы, которые могут быть решены на абстрактной параллельной ЭВМ с общей памятью (PRAM) c числом процессоров O(n) за полиномиальное время. Здесь n-длина входного вектора задачи.
класс задач NC
Задача принадлежит классу задач NC, если существуют такие константы a, b и такой алгоритм ее решения, что на и такой алгоритм ее решения, что на абстрактной параллельной ЭВМ с общей памятью (PRAM), имеющей O(n^a) процессоров, задача может быть решена за время O(log n)^b. Здесь ^ - символ возведения в степень. Имеет место следующее утверждение: класс NC не зависит от модели PRAM.
класс задач P
Класс задач P - это класс задач, разрешимых на однопроцессорной ЭВМ за полиномиальное время. Для многих задач класса P оказана их принадлежность классу NC, например, для задачи линейного программирования. Однако до настоящего времени вопрос о совпадении этих классов остается открытым. Совпадение этих классов означало бы, что любая задача, принадлежащая классу P, допускает эффективное распараллеливании.
средняя степень параллелизма
Средней степенью параллелизма называется отношение общего числа операций алгоритма к высоте ЯПФ алгоритма.
ускорение параллельного алгоритма
ускорение алгоритма
Ускорение параллельного алгоритма является его наиболее информативной характеристикой, которая показывает во сколько раз применение параллельного алгоритма уменьшает время решения задачи по сравнению с последовательным алгоритмом. Ускорение параллельного алгоритма определяется величиной SN=T1/TN, где T1 - время выполнения алгоритма на одном процессоре, TN - время выполнения алгоритма на N процессорах.
эффективность параллельного алгоритма
эффективность алгоритма
Эффективность параллельного алгоритма определяется величиной EN=SN/N, где SN - ускорение данного параллельного алгоритма, N - количество процессоров в системе.
закон Амдала
Закон Амдала задается формулой SN=1/(a+(1-a)/N), где SN - ускорение данного параллельного алгоритма на N процессорной ЭВМ, a - доля операций, выполняемых на одном процессоре. Из закона Амдала следует, что если, к примеру, a=0.1, т.е. всего 10% операций программы выполняется последовательно, то при любом, как угодно большом количестве используемых процессоров N ускорение, превышающее 10, принципиально получить невозможно.
сетевой закон Амдала
Закон Амдала не учитывает возможный дисбаланс загрузки процессоров. Сетевой закон Амдала учитывает это дисбаланс и имеет вид SN=1/(a+b(1-a)/N), где SN - ускорение данного параллельного алгоритма на N процессорной ЭВМ, a - доля операций, выполняемых на одном процессоре, b - коэффициент дисбаланса загрузки процессоров.
«парадокс» параллелизма
"Парадокс» параллелизма" состоит в достижении ускорения и эффективности параллельного алгоритма, превышающих значения N и 1, соответственно. Другими словами, «парадокс» параллелизма состоит в «суперлинейном» росте производительности параллельной вычислительной системы с ростом количества N ее процессоров.