🗊Презентация Построение и анализ параллельных алгоритмов

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

Модель PRAM Модель PRAM: Parallel Random-Access Memory Позволяет учитывать ограничения, связанные с одновременным доступом к памяти Является идеализированной моделью архитектуры SMP (Symmetric MultiProcessor, Shared Memory Processor)

Модель PRAM Процессоры П0, П1, …, Пp–1 используют общую память, состоящую из множества ячеек. Время доступа каждого процессора к каждой ячейке памяти одинаково и не зависит от количества процессоров.

Модель PRAM Один шаг (такт) работы PRAM-машины синхронизирован по фазам: Чтение данных из памяти. Обработка данных. Запись результата в память.

Режимы чтения и записи Режимы чтения данных из памяти: Одновременное (Concurrent Read) Исключающее (Exclusive Read) Режимы записи в память: Одновременная (Concurrent Write) Исключающая (Exclusive Write)

Варианты одновременной записи Одновременная запись одинакового значения Произвольная запись: сохраняется произвольное значение из множества записываемых Запись в зависимости от приоритетов процессоров Комбинация записываемых значений

Виды PRAM машин и алгоритмов

ЗАДАЧА НАХОЖДЕНИЯ КОРНЕЙ ДВОИЧНОГО ЛЕСА Пример CREW-алгоритма

Пример CREW-алгоритма Дано: Лес, состоящий из бинарных деревьев. Деревья заданы следующим образом: для каждой вершины имеется указатель на её родителя. Для корней деревьев этот указатель пуст. Требуется: для каждой вершины найти корень дерева, которому она принадлежит

Пример CREW-алгоритма Представление входных данных: вершины пронумерованы, ребра деревьев заданы с помощью массива parent: элемент parent[i] представляет номер вершины, являющейся родителем для вершины с номером i.

Пример CREW-алгоритма Результат работы алгоритма — массив root. В ячейке root[i] хранится вершины, являющейся корнем дерева, в которое входит вершина i. Массивы parent и root хранятся в общей памяти.

CREW-алгоритм Для каждого процессора Pi выполнить Если parent[i] = NIL, то root[i] := i; Пока существует узел i, для которого parent[i]  NIL, выполнять: Для каждого процессора i выполнить Если parent[i]  NIL, то { root[i] := root[parent[i]]; parent[i] := parent[parent[i]]; }

Анализ CREW-алгоритма Временная сложность алгоритма: O(log2 d), где d — наибольшая глубина дерева в заданном лесе. Можно показать, что ни один EREW-алгоритм не может решить эту задачу за время, меньшее O(log2 n), где n — количество вершин в лесе

НАХОЖДЕНИЕ МАКСИМАЛЬНОГО ЭЛЕМЕНТА В МАССИВЕ Пример CRCW-алгоритма

Пример CRCW-алгоритма Дано: Массив n элементов Требуется: Найти максимальный элемент

Пример CRCW-алгоритма Способ решения Количество процессоров: n2. Каждый процессор нумеруется парой индексов. Процессор с номером (i,j) сравнивает A[i] и A[j]. Используется вспомогательный булевский массив m[i]. После выполнения сравнений m[i]=true  A[i] — наибольший элемент массива. Результат помещается в переменную max.

CRCW-алгоритм Для всех i от 0 до n–1 выполнить: m[i] := true; Для всех i от 0 до n–1 и для всех j от 0 до n–1 выполнить: Если A[i] < A[j], то m[i] := false; Для всех i от 0 до n–1 выполнить: Если m[i] = true, то max := A[i]; Вернуть max.

Анализ CRCW-алгоритма Без использования параллельного чтения невозможно решить эту же задачу быстрее, чем за время O(log n). Представленный CRCW-алгоритм работает за время O(1) и требует n2 процессоров. Наилучший последовательный алгоритм работает за время O(n). Поэтому эффективность составляет 1/n, т.е. алгоритм не является эффективным по затратам.

Рекомендуемые источники Адигеев М.Г. Анализ сложности параллельных алгоритмов. Метод. указания. — Ростов-на-Дону: Изд-во Ростовского гос. ун-та, 2007 г. — 37 с. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л. Алгоритмы: построение и анализ. — М.: Бином, 2004. — 960 с. Кузюрин Н.Н. Эффективные алгоритмы и сложность вычислений. http://discopal.ispras.ru/ru.book-advanced-algorithms.htm) Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical Methods. — Prentice Hall, Englewood Cliffs, New Jersey, 1989 http://web.mit.edu/dimitrib/www/pdc.html. Foster I. Designing and Building Parallel Programs. http://www-unix.mcs.anl.gov/dbpp/text/node1.html