Построение и анализ параллельных алгоритмов - презентация, доклад, проект скачать

Нажмите для полного просмотра!

Построение и анализ параллельных алгоритмов, слайд №1

Построение и анализ параллельных алгоритмов, слайд №2

Построение и анализ параллельных алгоритмов, слайд №3

Построение и анализ параллельных алгоритмов, слайд №4

Построение и анализ параллельных алгоритмов, слайд №5

Построение и анализ параллельных алгоритмов, слайд №6

Построение и анализ параллельных алгоритмов, слайд №7

Построение и анализ параллельных алгоритмов, слайд №8

Построение и анализ параллельных алгоритмов, слайд №9

Построение и анализ параллельных алгоритмов, слайд №10

Построение и анализ параллельных алгоритмов, слайд №11

Построение и анализ параллельных алгоритмов, слайд №12

Построение и анализ параллельных алгоритмов, слайд №13

Построение и анализ параллельных алгоритмов, слайд №14

Построение и анализ параллельных алгоритмов, слайд №15

Построение и анализ параллельных алгоритмов, слайд №16

Построение и анализ параллельных алгоритмов, слайд №17

Построение и анализ параллельных алгоритмов, слайд №18

Построение и анализ параллельных алгоритмов, слайд №19

Содержание ▲

Вы можете ознакомиться и скачать презентацию на тему Построение и анализ параллельных алгоритмов. Доклад-сообщение содержит 19 слайдов. Презентации для любого класса можно скачать бесплатно. Если материал и наш сайт презентаций Mypresentation Вам понравились – поделитесь им с друзьями с помощью социальных кнопок и добавьте в закладки в своем браузере.

Слайды и текст этой презентации

Слайд 1

Описание слайда:

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

Слайд 2

Описание слайда:

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

Слайд 3

Описание слайда:

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

Слайд 4

Описание слайда:

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

Слайд 5

Описание слайда:

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

Слайд 6

Описание слайда:

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

Слайд 7

Описание слайда:

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

Слайд 8

Описание слайда:

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

Слайд 9

Описание слайда:

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

Слайд 10

Описание слайда:

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

Слайд 11

Описание слайда:

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

Слайд 12

Описание слайда:

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]]; }

Слайд 13

Описание слайда:

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

Слайд 14

Описание слайда:

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

Слайд 15

Описание слайда:

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

Слайд 16

Описание слайда:

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

Слайд 17

Описание слайда:

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.

Слайд 18

Описание слайда:

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

Слайд 19

Описание слайда:

Рекомендуемые источники Адигеев М.Г. Анализ сложности параллельных алгоритмов. Метод. указания. — Ростов-на-Дону: Изд-во Ростовского гос. ун-та, 2007 г. — 37 с. Кормен Т.Х., Лейзерсон Ч.И., Ривест Р.Л. Алгоритмы: построение и анализ. — М.: Бином, 2004. — 960 с. Кузюрин Н.Н. Эффективные алгоритмы и сложность вычислений. Bertsekas D.P., Tsitsiklis J.N. Parallel and Distributed Computation. Numerical Methods. — Prentice Hall, Englewood Cliffs, New Jersey, 1989 Foster I. Designing and Building Parallel Programs.