Что такое findslide.org?

FindSlide.org - это сайт презентаций, докладов, шаблонов в формате PowerPoint.

Для правообладателей

Обратная связь

Email: Нажмите что бы посмотреть 

Яндекс.Метрика

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

Содержание

Модель PRAMМодель PRAM: Parallel Random-Access MemoryПозволяет учитывать ограничения, связанные с одновременным доступом к памятиЯвляется идеализированной моделью архитектуры SMP (Symmetric MultiProcessor, Shared Memory Processor)
Построение и анализ параллельных алгоритмовPRAM: модель параллельных вычислений с общей памятью Модель PRAMМодель PRAM: Parallel Random-Access MemoryПозволяет учитывать ограничения, связанные с одновременным доступом Модель PRAMПроцессоры П0, П1, …, Пp–1 используют общую память, состоящую из множества Модель PRAMОдин шаг (такт) работы PRAM-машины синхронизирован по фазам:Чтение данных из памяти.Обработка данных.Запись результата в память. Режимы чтения и записиРежимы чтения данных из памяти:Одновременное (Concurrent Read)Исключающее (Exclusive Read)Режимы Варианты одновременной записиОдновременная запись одинакового значенияПроизвольная запись: сохраняется произвольное значение из множества Виды PRAM машин и алгоритмов ЗАДАЧА НАХОЖДЕНИЯ КОРНЕЙ ДВОИЧНОГО ЛЕСАПример CREW-алгоритма Пример CREW-алгоритмаДано: Лес, состоящий из бинарных деревьев. Деревья заданы следующим образом: для Пример CREW-алгоритмаПредставление входных данных:вершины пронумерованы, ребра деревьев заданы с помощью массива parent: Пример CREW-алгоритмаРезультат работы алгоритма — массив root. В ячейке root[i] хранится вершины, CREW-алгоритмДля каждого процессора Pi выполнить Если parent[i] = NIL, то Анализ CREW-алгоритмаВременная сложность алгоритма: O(log2 d), где d — наибольшая глубина дерева НАХОЖДЕНИЕ МАКСИМАЛЬНОГО ЭЛЕМЕНТА В МАССИВЕПример CRCW-алгоритма Пример CRCW-алгоритмаДано: Массив n элементовТребуется: Найти максимальный элемент Пример CRCW-алгоритмаСпособ решенияКоличество процессоров: n2. Каждый процессор нумеруется парой индексов.Процессор с номером CRCW-алгоритмДля всех i от 0 до n–1 выполнить: m[i] := true;Для всех Анализ CRCW-алгоритмаБез использования параллельного чтения невозможно решить эту же задачу быстрее, чем Рекомендуемые источникиАдигеев М.Г. Анализ сложности параллельных алгоритмов. Метод. указания. — Ростов-на-Дону: Изд-во
Слайды презентации

Слайд 2 Модель PRAM
Модель PRAM: Parallel Random-Access Memory
Позволяет учитывать ограничения,

Модель PRAMМодель PRAM: Parallel Random-Access MemoryПозволяет учитывать ограничения, связанные с одновременным

связанные с одновременным доступом к памяти
Является идеализированной моделью архитектуры

SMP (Symmetric MultiProcessor, Shared Memory Processor)

Слайд 3 Модель PRAM
Процессоры П0, П1, …, Пp–1 используют общую

Модель PRAMПроцессоры П0, П1, …, Пp–1 используют общую память, состоящую из

память, состоящую из множества ячеек.
Время доступа каждого процессора

к каждой ячейке памяти одинаково и не зависит от количества процессоров.



Слайд 4 Модель PRAM
Один шаг (такт) работы PRAM-машины синхронизирован по

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

фазам:
Чтение данных из памяти.
Обработка данных.
Запись результата в память.

Слайд 5 Режимы чтения и записи
Режимы чтения данных из памяти:
Одновременное

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

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

(Exclusive Write)

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

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

произвольное значение из множества записываемых
Запись в зависимости от приоритетов

процессоров
Комбинация записываемых значений

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

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

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

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

Слайд 9 Пример CREW-алгоритма
Дано: Лес, состоящий из бинарных деревьев. Деревья

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

заданы следующим образом: для каждой вершины имеется указатель на

её родителя. Для корней деревьев этот указатель пуст.
Требуется: для каждой вершины найти корень дерева, которому она принадлежит

Слайд 10 Пример CREW-алгоритма
Представление входных данных:
вершины пронумерованы,
ребра деревьев заданы

Пример CREW-алгоритмаПредставление входных данных:вершины пронумерованы, ребра деревьев заданы с помощью массива

с помощью массива parent: элемент parent[i] представляет номер вершины,

являющейся родителем для вершины с номером i.

Слайд 11 Пример CREW-алгоритма
Результат работы алгоритма — массив root. В

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

ячейке root[i] хранится вершины, являющейся корнем дерева, в которое

входит вершина i.

Массивы parent и root хранятся в общей памяти.

Слайд 12 CREW-алгоритм
Для каждого процессора Pi выполнить
Если

CREW-алгоритмДля каждого процессора Pi выполнить Если parent[i] = NIL, то

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

Анализ CREW-алгоритмаВременная сложность алгоритма: O(log2 d), где d — наибольшая глубина

— наибольшая глубина дерева в заданном лесе.

Можно показать, что

ни один EREW-алгоритм не может решить эту задачу за время, меньшее O(log2 n), где n — количество вершин в лесе

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

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

Слайд 15 Пример CRCW-алгоритма
Дано: Массив n элементов

Требуется: Найти максимальный элемент

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

Слайд 16 Пример CRCW-алгоритма
Способ решения

Количество процессоров: n2.
Каждый процессор нумеруется

Пример CRCW-алгоритмаСпособ решенияКоличество процессоров: n2. Каждый процессор нумеруется парой индексов.Процессор с

парой индексов.
Процессор с номером (i,j) сравнивает A[i] и A[j].


Используется вспомогательный булевский массив m[i]. После выполнения сравнений m[i]=true ⇔ A[i] — наибольший элемент массива.
Результат помещается в переменную max.


Слайд 17 CRCW-алгоритм
Для всех i от 0 до n–1 выполнить:

CRCW-алгоритмДля всех i от 0 до n–1 выполнить: m[i] := true;Для


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-алгоритма
Без использования параллельного чтения невозможно решить эту

Анализ CRCW-алгоритмаБез использования параллельного чтения невозможно решить эту же задачу быстрее,

же задачу быстрее, чем за время O(log n).
Представленный

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


  • Имя файла: postroenie-i-analiz-parallelnyh-algoritmov.pptx
  • Количество просмотров: 129
  • Количество скачиваний: 0
- Предыдущая Программа развития транспортной системы Санкт – Петербурга и Ленинградской области на период до 2020года
Следующая - Организация досуга детей с ограниченными возможностями

Похожие презентации

Открытый показ интегрированного занятия. Ведущая область - познание. план-конспект занятия по математике (младшая группа) Открытый показ интегрированного занятия. Ведущая область - познание. план-конспект занятия по математике (младшая группа) 82
Урок математики. презентация к уроку по математике (1 класс) по теме Урок математики. презентация к уроку по математике (1 класс) по теме 113
Презентация по математике. Тест: Счёт в пределах 20. презентация к уроку по математике (1 класс) Презентация по математике. Тест: Счёт в пределах 20. презентация к уроку по математике (1 класс) 85
Презентация задач на сложные банковские проценты с пополнением вклада Презентация задач на сложные банковские проценты с пополнением вклада 111
Десятичные дроби Десятичные дроби 98
Презентация Теорема Пифагора Презентация Теорема Пифагора 117
Деление обыкновенных дробей Деление обыкновенных дробей 86
Сложение и вычитание смешанных чисел Сложение и вычитание смешанных чисел 91
Величины. Масса Величины. Масса 93
Промежуточный срез по математике, 1 класс, Школа России презентация к уроку по математике (1 класс) Промежуточный срез по математике, 1 класс, Школа России презентация к уроку по математике (1 класс) 125
Первый урок математики в 6 классе Первый урок математики в 6 классе 77
Смешанное число Смешанное число 101
Презентация внеклассного мероприятия Магический квадрат Презентация внеклассного мероприятия Магический квадрат 114
Закрепеление и повторение материала Закрепеление и повторение материала 100
Математика. Множители. Произведение Математика. Множители. Произведение 90
Конспект НОД по ФЭМП Мишка в стране математики план-конспект занятия по математике (средняя группа) по теме Конспект НОД по ФЭМП Мишка в стране математики план-конспект занятия по математике (средняя группа) по теме 116
Округление десятичных дробей 6 класс Округление десятичных дробей 6 класс 123
Деление с остатком. Закрепление презентация к уроку по математике (3 класс) по теме Деление с остатком. Закрепление презентация к уроку по математике (3 класс) по теме 166
Проект Математика вокруг нас 4 класс презентация к уроку по математике (4 класс) Проект Математика вокруг нас 4 класс презентация к уроку по математике (4 класс) 151
m urok55 m urok55 125
Физико-математический бой Физико-математический бой 87
Лобачевский и его геометрия Лобачевский и его геометрия 106
Модуль Модуль 127
Устный счёт В стране Джингл – сити - 7 Устный счёт В стране Джингл – сити - 7 90
Экономические понятия на уроках математики Экономические понятия на уроках математики 88
treugolniki treugolniki 92
Сравнение трехзначных чисел Сравнение трехзначных чисел 102
Таблица сложения презентация к уроку по математике (1 класс) по теме Таблица сложения презентация к уроку по математике (1 класс) по теме 78
Сложение и вычитание рациональных чисел Сложение и вычитание рациональных чисел 113
тренажёр для отработки знания таблицы умножения тест (математика, 2 класс) по теме тренажёр для отработки знания таблицы умножения тест (математика, 2 класс) по теме 104