Высокопроизводительные вычисления в прикладном численном моделировании

Что такое суперкомпьютер? Оксфордский толковый словарь по вычислительной технике (1986 год): Суперкомпьютер - это очень мощная ЭВМ с производительностью свыше 10 MFLOPS (миллионов операций с плавающей запятой в секунду). Начало 90-х годов MFLOPS. Начало 90-х годов MFLOPS год - 5 GFLOPS

Что такое суперкомпьютер? Суперкомпьютер – это система, цена которой выше 1-2 млн. долларов Суперкомпьютер – это компьютер, мощность которого всего на порядок меньше необходимой для решения современных задач Суперкомпьютер - это устройство, сводящее проблемы вычислений к проблемам ввода/вывода (Кен Батчер (Ken Batcher) 2001 г).

«Основы…» или не «Основы…»? Архитектура современных многопроцессорных вычислительных машин; Архитектура современных многопроцессорных вычислительных машин; Системное программное обеспечение параллельных ЭВМ и сетей; Системное программное обеспечение параллельных ЭВМ и сетей; Технология программирования на параллельных ЭВМ; Технология программирования на параллельных ЭВМ; Параллельные алгоритмы; Параллельные алгоритмы; Математическое моделирование и параллельный вычислительный эксперимент Математическое моделирование и параллельный вычислительный эксперимент

Цель курса Не бояться распараллеливать свои (или не свои) программы

Введение в распараллеливание алгоритмов и программ

А зачем? Московский Государственный Университет (Ломоносов) – TFLOP Суперкомпьютерный центр – TFLOP Московский Государственный Университет (Чебышев) – 60 TFLOP РНЦ «Курчатовский институт» – 34.2 TFLOP Московский физико-технический институт – 6.5 TFLOP

Кластер МФТИ-60

А зачем? Московский Государственный Университет (Ломоносов) – TFLOP Суперкомпьютерный центр – TFLOP Московский Государственный Университет (Чебышев) – 60 TFLOP РНЦ «Курчатовский институт» – 34.2 TFLOP Московский физико-технический институт – 6.5 TFLOP DoE - Oak Ridge National Laboratory – PFLOP USA – объявлено о начале разработки эксафлопного компьютера

А зачем? Прогноз погоды. Уравнение Навье-Стокса. При размере ячейки 1 кубическая миля, 10 ячеек по высоте, для расчета прогноза на 10 дней с шагом 1 минута требуется FLOP ~ 10 дней работы компьютера с производительностью 10 GFLOP. Прогноз погоды. Уравнение Навье-Стокса. При размере ячейки 1 кубическая миля, 10 ячеек по высоте, для расчета прогноза на 10 дней с шагом 1 минута требуется FLOP ~ 10 дней работы компьютера с производительностью 10 GFLOP. Квантовая хромодинамика – вычисление массы протона – примерно FLOP ~ 0.5 года работы обычного компьютера Квантовая хромодинамика – вычисление массы протона – примерно FLOP ~ 0.5 года работы обычного компьютера Астрофизика – моделирование развития галактики из звезд ~ 1 год на 1 шаг по времени Астрофизика – моделирование развития галактики из звезд ~ 1 год на 1 шаг по времени Биофизика – моделирование образования белка ~ машинных инструкций ~ 10 6 веков на одноядерной персоналке 3.2 GHzБиофизика – моделирование образования белка ~ машинных инструкций ~ 10 6 веков на одноядерной персоналке 3.2 GHz

А зачем? To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem. E. Dijkstra, 1972 Turing Award Lecture

Первый кризис software Время: е годы Проблема: Программирование на языке ассемблера Компьютеры стали способны обрабатывать более сложные задачи Появилась необходимость перехода на более высокий уровень абстракции и переносимости программ Решение – развитие языков высокого уровня для фон- Неймановской архитектуры

Второй кризис software Время: е годы Проблема: Невозможность создания и поддержки сложных и надежных программных комплексов, содержащих несколько миллионов строк кода и написанных сотнями программистов Компьютеры стали способны обрабатывать более сложные задачи Решение – развитие объектно-ориентированных языков, разработка инструментария для поддержки больших программных проектов

Закон Мура (1965 год) Количество транзисторов на кристалле и производительность процессоров удваиваются каждые полтора – два года Очевидные проблемы: Скорость передачи информацииСкорость передачи информации ТеплоотводТеплоотвод С 2005 года – появление многоядерных процессоров

Новый закон Мура Количество ядер на одном процессоре удваивается каждые полтора года Multicore processors – ( 2 – 10х ядер ) Manycore processors – ( 100 – 100x ядер ) Myriacore processors – ( ? ядер )

Третий кризис software Время: ??-е годы Проблема: Необходимость смены парадигмы программирования Компьютеры стали способны обрабатывать более сложные задачи Решение – А кто ж его знает????

История параллельности Охотники на мамонтов – коллективное решение задачи - универсальность и специализация Форд - конвейер Первое предложение об использовании параллельности для вычислений – 1842 год – аналитическая машина Бэббиджа

История параллельности EDSAC год Кембридж - время такта 2 микросекунды (2*10 -6 секунды), выполнял в среднем 100 арифметических операций в секунду Современные процессоры – тактовая частота 3GHz – время одного такта ~ 3* секунды – но производительность по сравнению с EDSAC существенно больше, чем в раз

История параллельности Разрядно-параллельная память и разрядно-параллельная арифметика (IBM 701 (1953), IBM 704 (1955 )) Первый этап развития вычислительной техники (ВТ) Второй этап развития ВТ – spooling. IBM 709 (1958): 6 независимых устройств ввода-вывода Ускорение доступа к памяти за счет разделения ее на банки памяти IBM STRETCH (1961г.) Мультипрограммирование – начало третьего этапа развития ВТ. Появление DMA. ЭВМ ATLAS (1962г.) конвейер выполнения команд (4 ступени). Мультипрограммирование – начало третьего этапа развития ВТ. Появление DMA.

История параллельности Выборка команды Выборка команды Декодирование и увеличение программного счетчика Декодирование и увеличение программного счетчика Вычисление адреса операндов Вычисление адреса операндов Выборка операндов Выборка операндов Операция Операция Сохранение результата Сохранение результата Введение отдельных устройств для каждой стадии обработки команды позволяет организовать конвейер

История параллельности Независимые функциональные устройства для выполнения различных операций - CDC 6600 (1964) Независимые функциональные устройства для выполнения различных операций - CDC 6600 (1964) время такта 100нс, производительность 2-3 млн. операций в секунду, оперативная память разбита на 32 банка по ти разрядных слов, цикл памяти 1мкс, 10 независимых функциональных устройств. Суперскалярные процессоры. Появление VLIW- процессоров.

История параллельности Выполнение сложения с плавающей точкой: Выполнение сложения с плавающей точкой: Сравнение порядков Выравнивание порядков Сложение мантисс Нормализация Округление Округление Конвейерные функциональные устройства - CDC 7600 (1969)

История параллельности матричные процессоры: ILLIAC IV : Проект (1967): 256 процессорных элементов (ПЭ) = 4 квадранта по 64ПЭ, возможность реконфигурации: 2квадранта по 128ПЭ или 1квадрант из 256ПЭ, такт 40нс, производительность 1Гфлоп ; Реально:конец 1971 г. - изготовлена система из 1 квадранта, в 1974г. она введена в эксплуатацию, доводка велась до 1975 года. Функционировала до 1982 года.

История параллельности Векторно-конвейерные ЭВМ CRAY 1 (1976): В 1972 году С.Крэй покидает CDC и основывает свою компанию Cray Research, которая в 1976 г. выпускает первый векторно-конвейерный компьютер CRAY-1: время такта 12.5нс, 12 конвейерных функциональных устройств, пиковая производительность 160 миллионов операций в секунду, оперативная память до 1Мслова (слово - 64 разряда), цикл памяти 50нс. Главным новшеством является введение векторных команд, работающих с целыми массивами независимых данных и позволяющих эффективно использовать конвейерные функциональные устройства.

История параллельности Многопроцессорные вычислительные комплексы Кластеры Высокопроизводительные системы на графических процессорах

Классификация вычислительных систем Персональные ЭВМ Персональные ЭВМ Рабочие станции Рабочие станции МиниЭВМ МиниЭВМ Большие универсальные ЭВМ (mainframe) Большие универсальные ЭВМ (mainframe) Супер--ЭВМ Супер--ЭВМ Минисупер--ЭВМ Минисупер--ЭВМ Эта классификация позволяет, быть может, примерно прикинуть стоимость компьютера

Классификация вычислительных систем Классическая систематика Флинна Классическая систематика Флинна По количеству потоков команд и данных : SISDSIMDMISDMIMD

Классификация вычислительных систем SISD (single instruction stream / single data stream) - одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины, или иначе, машины фон-неймановского типа, например, PDP-11 или VAX 11/780. В таких машинах есть только один поток команд, все команды обрабатываются последовательно друг за другом и каждая команда инициирует одну операцию с одним потоком данных. Не имеет значения тот факт, что для увеличения скорости обработки команд и скорости выполнения арифметических операций может применяться конвейерная обработка - как машина CDC 6600 со скалярными функциональными устройствами, так и CDC 7600 с конвейерными попадают в этот класс.

Классификация вычислительных систем SIMD (single instruction stream / multiple data stream) - одиночный поток команд и множественный поток данных. В архитектурах подобного рода сохраняется один поток команд, включающий, в отличие от предыдущего класса, векторные команды. Это позволяет выполнять одну арифметическую операцию сразу над многими данными - элементами вектора. Способ выполнения векторных операций не оговаривается, поэтому обработка элементов вектора может производится либо процессорной матрицей, как в ILLIAC IV, либо с помощью конвейера, как, например, в машине CRAY-1..

Классификация вычислительных систем MISD (multiple instruction stream / single data stream) - множественный поток команд и одиночный поток данных. Теоретическая категория. В природе не встречается.

Классификация вычислительных систем MIMD (multiple instruction stream / multiple data stream) - множественный поток команд и множественный поток данных. Этот класс предполагает, что в вычислительной системе есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных..

Последовательная парадигма программирования Содержательная задача Математическая модель Алгоритм Программа Процессы или threadы

Модели программирования Модель программирования: Модель программирования: определяет основные идеи программной реализации; определяет основные идеи программной реализации; абстрагируется от языка программирования, который будет использоваться, и, частично, от hardware. абстрагируется от языка программирования, который будет использоваться, и, частично, от hardware. Названия моделей программирования до конца в литературе не устоялись Названия моделей программирования до конца в литературе не устоялись

Модели параллельного программирования Последовательная модель: П оследовательная программа для автоматического распараллеливания компилятором или специальными программными средствами. Преимущество – знакомая парадигма программирования Преимущество – знакомая парадигма программирования Недостаток – ограниченные возможности автоматического распараллеливания Недостаток – ограниченные возможности автоматического распараллеливания

Модели параллельного программирования Модель передачи сообщений: Работающее приложение состоит из набора процессов с различными адресными пространствами. Процессы обмениваются сообщениями с помощью явных send- receive операций. Преимущество – полный контроль над выполнением Преимущество – полный контроль над выполнением Недостаток – сложность программирования Недостаток – сложность программирования

Модели параллельного программирования Модель разделяемой памяти: Приложение состоит из набора threadов, использующих разделяемые переменные и примитивы синхронизации Явные нити исполнения: программирование с использованием библиотечных или системных вызовов для threadов Явные нити исполнения: программирование с использованием библиотечных или системных вызовов для threadов o Преимущество – переносимость o Недостаток – сложность программирования Программирование на языке высокого уровня с применением прагм. Программирование на языке высокого уровня с применением прагм. o Преимущество – легкость программирования o Недостаток – сложность контроля над выполнением

Модели параллельного программирования Модель разделенных данных: Приложение состоит из набора процессов, каждый работает со своим набором данных, обмена информацией при работе нет. Преимущество – легкость реализации Преимущество – легкость реализации Недостаток – производительность зависит от конкретной реализации Недостаток – производительность зависит от конкретной реализации

Параллельная парадигма программирования Содержательная задача Математическая модель Алгоритм Программа Процессы или threadы ) Декомпозиция (decomposition)

Разделение вычислений и данных на части Разделение вычислений и данных на части Декомпозиция по данным (параллелизм по данным) Декомпозиция по данным (параллелизм по данным) разделяем данные на области ответственности разделяем данные на области ответственности определяем, как вычисления связаны с данными определяем, как вычисления связаны с данными Декомпозиция по вычислениям (функциональный параллелизм) Декомпозиция по вычислениям (функциональный параллелизм) разделяем вычисления на области ответственности разделяем вычисления на области ответственности определяем, как данные связаны с вычислениями определяем, как данные связаны с вычислениями

Параллельная парадигма программирования Содержательная задача Математическая модель Алгоритм Программа Процессы (threads) Декомпозиция (decomposition) Назначение (assignment)

Определение способов распределения задач по процессорам. Определение способов распределения задач по процессорам. Цели: Цели: балансировка загрузки исполнителей балансировка загрузки исполнителей уменьшение обменов данными между исполнителями уменьшение обменов данными между исполнителями сокращение накладных расходов на само назначение сокращение накладных расходов на само назначение Разновидности по времени назначения Разновидности по времени назначения статическое – на этапе написания программы, компиляции или старта программы ( до реального исполнения вычислений) статическое – на этапе написания программы, компиляции или старта программы ( до реального исполнения вычислений) динамическое – в процессе выполнения вычислений динамическое – в процессе выполнения вычислений

Параллельная парадигма программирования Содержательная задача Математическая модель Алгоритм Программа Процессы (threads) Декомпозиция (decomposition) Назначение (assignment) Дирижирование (orchestration)

Реализация в выбранной программной модели и на выбранном языке программирования. Реализация в выбранной программной модели и на выбранном языке программирования. Определяет Определяет имена данных и способы доступа к ним имена данных и способы доступа к ним обмен данными обмен данными синхронизацию обмена синхронизацию обмена

Параллельная парадигма программирования Содержательная задача Математическая модель Алгоритм Программа Процессы (threads) Декомпозиция (decomposition) Назначение (assignment) Дирижирование (orchestration) Отображение (mapping)

Отображение (mapping) Отображение (mapping) Отображение процессов (нитей исполнения) на процессоры. Выполняется либо пользователем, либо операционной системой Отображение процессов (нитей исполнения) на процессоры. Выполняется либо пользователем, либо операционной системой Для общей памяти – ОС Для общей памяти – ОС Для распределенной памяти – пользователь или ОС Для распределенной памяти – пользователь или ОС

Параллельная парадигма программирования Содержательная задача Математическая модель Алгоритм Программа Процессы (threads) Декомпозиция (decomposition) Назначение (assignment) Дирижирование (orchestration) Отображение (mapping)

Асимптотический анализ Основные принципы Игнорировать зависимость от конкретной ЭВМ:Игнорировать зависимость от конкретной ЭВМ: использование моделей вычислительных систем Анализировать изменение T(n) при n :Анализировать изменение T(n) при n : интересует время работы алгоритма при больших размерностях задачи Анализ темпа роста:Анализ темпа роста: что лучше T(n)=10 6 n 2 или T(n)=n 3 ?

Асимптотический анализ Форма записи Пусть f(n) и g(n) – положительные функции целочисленного аргумента f(n) = O(g(n)) c > 0, n 0 > 0 : f(n) cg(n) n n 0 f(n) = (g(n)) c > 0, n 0 > 0 : cg(n) f(n) n n 0 f(n) = (g(n)) c 1, c 2, n 0 > 0 : c 1 g(n) f(n) c 2 g(n) n n 0

Асимптотический анализ Сравнение алгоритмов Пусть T 1 (n) и T 2 (n) – времена работы алгоритмов 1 и 2 соответственно, T 0 (n) – теоретическая оценка времени решения задачи снизу Если T 1 (n) = O(T 2 (n)), то по поведению алгоритм 1 не хуже алгоритма 2 Если T 1 (n) = (T 2 (n)), то по поведению алгоритм 1 не лучше алгоритма 2 Если T 1 (n) = (T 2 (n)), то алгоритм 1 и алгоритм 2 одинаковы по поведению Если T 1 (n) = (T 0 (n)), то алгоритм 1 – оптимален

Асимптотический анализ. Пример. Задача выбора Рассмотрим S = { s 1, s 2, …, s n } – множество, на котором задан линейный порядок. |S| = n – мощность множества. Элемент s i называется элементом ранга k (1 k n), если он является k-м наименьшим элементом множества S. Поиск максимума – нахождение значения элемента n-го рангаПоиск максимума – нахождение значения элемента n-го ранга Поиск минимума – нахождение значения элемента первого рангаПоиск минимума – нахождение значения элемента первого ранга Поиск медианы – нахождение значения элемента с рангомПоиск медианы – нахождение значения элемента с рангом Общая задача – нахождение значения элемента ранга kОбщая задача – нахождение значения элемента ранга k

Асимптотический анализ. RAM (Random Access Machine) 1.Один процессор с одним ядром. 2.Ячейки памяти доступны в произвольном порядке. 3.Время доступа к памяти есть (1), независимо от того чтение это или запись. 4.Время выполнения основных операций на процессоре есть (1).

Асимптотический анализ. Пример. Задача выбора Шаг 1: если |S| < q, элемент k-го ранга ищем сортировкой, иначе делим S на |S|/q подмножеств S i из q элементов каждое (кроме, быть может, последнего) иначе делим S на |S|/q подмножеств S i из q элементов каждое (кроме, быть может, последнего) … s1s1s1s1 s2s2s2s2 s3s3s3s3 s4s4s4s4 snsnsnsn s1s1s1s1 … sqsqsqsq s q+1 … s 2q … snsnsnsn

Асимптотический анализ. Пример. Задача выбора Шаг 2: Сортировкой ищем медиану в каждом подмножестве …

Асимптотический анализ. Пример. Задача выбора Шаг 3: Строим множество всех медиан M. Рекурсивно находим его медиану m 0. Рекурсивно находим его медиану m 0.

Асимптотический анализ. Пример. Задача выбора Шаг 4: Строим множества L: s i L s i < m 0 L: s i L s i < m 0 E: s i E s i = m 0 E: s i E s i = m 0 G: s i G s i > m 0 G: s i G s i > m 0

Асимптотический анализ. Пример. Задача выбора Шаг 5: Если |L| k – рекурсивно ищем в L значение элемента ранга k, иначе, если |L|+|E| k – искомое значение есть m 0, иначе – рекурсивно ищем в G значение элемента ранга k-|L|-|E|

Асимптотический анализ. Пример. Задача выбора Шаг 1: если |S| < q, элемент k-го ранга ищем сортировкой T 1 (n) = (1) = C 0 иначе делим S на |S|/q подмножеств S i из q элементов каждое (кроме, быть может, последнего) иначе делим S на |S|/q подмножеств S i из q элементов каждое (кроме, быть может, последнего) T 1 (n) = C(n/q) = C 1 n

Асимптотический анализ. Пример. Задача выбора Шаг 2: Сортировкой ищем медиану в каждом подмножестве T 2 (n) = C 2 n …

Асимптотический анализ. Пример. Задача выбора Шаг 3: Строим множество всех медиан M. Рекурсивно находим его медиану m 0. Рекурсивно находим его медиану m 0. T 3 (n)=T(n/q)

Асимптотический анализ. Пример. Задача выбора Шаг 4: Строим множества L: s i L s i < m 0 L: s i L s i < m 0 E: s i E s i = m 0 E: s i E s i = m 0 G: s i G s i > m 0 G: s i G s i > m 0 T 4 (n) = C 3 n

Асимптотический анализ. Пример. Задача выбора Шаг 5 : Если |L| k – рекурсивно ищем в L значение элемента ранга k, иначе, если |L|+|E| k – искомое значение есть m 0,иначе – рекурсивно ищем в G значение элемента ранга k-|L|-|E| В множестве M НЕ МЕНЕЕ |M|/2= n/(2q) медиан m i, превышающих или равных m 0. В каждом из соответствующих S i НЕ МЕНЕЕ |S i |/2=q/2 элементов множества S не меньших m i. Стало быть, |E|+|G| (n/(2q))*(q/2) = n/4 и |L| 3n/4. Аналогично, |G| 3n/4.

Асимптотический анализ. Пример. Задача выбора Шаг 5 : Если |L| k – рекурсивно ищем в L значение элемента ранга k, иначе, если |L|+|E| k – искомое значение есть m 0,иначе – рекурсивно ищем в G значение элемента ранга k-|L|-|E| T 5 (n) = T(3n/4)

Асимптотический анализ. Пример. Задача выбора Оценим время выполнения T(n) Шаг 1: T 1 (n) = C 1 n Шаг 2: T 2 (n) = C 2 n Шаг 3: T 3 (n) = T(n/q) Шаг 4: T 4 (n) = C 3 n Шаг 5: T 5 (n) = T(3n/4) Окончательно T(n) = C 4 n + T(n/q) + T(3n/4) Шаманские танцы 1: Пусть n/q +3n/4 < n, тогда q 5. Положим q=5

Асимптотический анализ. Пример. Задача выбора Оценим время выполнения T(n) Шаг 1: T 1 (n) = C 1 n Шаг 2: T 2 (n) = C 2 n Шаг 3: T 3 (n) = T(n/q) Шаг 4: T 4 (n) = C 3 n Шаг 5: T 5 (n) = T(3n/4) Окончательно T(n) = C 4 n + T(n/5) + T(3n/4) Шаманские танцы 2: Предположим, что T(n) С 5 n, при С 5 =20С 4 получаем: T(n) C 4 n + 20C 4 n/5 + 60C 4 n/4 = С 5 n.

Асимптотический анализ. Пример. Задача выбора Мы получили T(n) C 5 n, стало быть T(n) = O(n). Теоретическая оценка снизу: T 0 (n) = n. Так как T 0 (n) T(n), то T(n) = (n). Окончательно, T(n) = Θ(n). Предложенный алгоритм является оптимальным.

Асимптотический анализ. Основная теорема Если T(n) = aT(n/b) + f(n), где a 1, b > 1, f(n) > 0 и n принимает целые неотрицательные значения, то 1. Если, ε > 0, то 2. Если, то 3. Если, ε > 0 и 0 0: из (n/b) > N af(n/b) cf(n), то из (n/b) > N af(n/b) cf(n), то

Асимптотический анализ. PRAM (Parallel Random Access Machine) 1.Много процессоров и/или много ядер. Память общая. 2.Ячейки памяти доступны в произвольном порядке. 3.Время доступа к памяти есть (1), независимо от того чтение это или запись. 4.Время выполнения основных операций на процессоре есть (1). 5.В зависимости от того, разрешены ли одновременное чтение из одной ячейки памяти или одновременная запись, существует 4 разновидности модели компьютера.

Асимптотический анализ. PRAM (Parallel Random Access Machine)-конфликты памяти 1.EREW – Exclusive Read Exclusive Write – наиболее строгая модель PRAM 2.CREW – Concurrent Read Exclusive Write - наиболее употребительная модель PRAM 3.CRCW – Concurrent Read Concurrent Write 4.ERCW – Exclusive Read Concurrent Write – невразумительная модель PRAM

Асимптотический анализ. PRAM (Parallel Random Access Machine)-конфликты памяти CW : схемы разрешения конфликта 1.Общая – запись разрешается только при всех одинаковых записываемых значениях 2.Объединяющая – реально записывается значение некоторой функции от всех значений, которые пытались записать (max, min, среднее значение и т.д.) 3.Произвольная – записывается одно из предлагаемых значений, выбранное произвольно 4.С приоритетами – у каждого исполнителя есть приоритет, запись произведет процессор с наибольшим приоритетом

Асимптотический анализ. Определения для параллельных систем Ускорение = (время работы наилучшего последовательного алгоритма при наихудших начальных данных) / (время работы параллельного алгоритма при тех же начальных данных) Для N исполнителей ускорение N, так как в противном случае последовательный алгоритм не был наилучшим. В реальной жизни часто ускорение считается для последовательной и параллельной версий одного и того же алгоритма на одном наборе данных.

Асимптотический анализ. Определения для параллельных систем Ускорение = (время работы наилучшего последовательного алгоритма при наихудших начальных данных) / (время работы параллельного алгоритма при тех же начальных данных) Стоимость = (время работы параллельного алгоритма) x (число исполняющих элементов) Пусть время работы последовательного алгоритма T s (n) = (f(n)), и стоимость параллельного алгоритма есть тоже (f(n)), тогда параллельный алгоритм является оптимальным по стоимости

Асимптотический анализ. EREW - Broadcast Пусть есть N исполнителей, которые используют одно и то же данное. Для считывания данного им понадобится время (N). d1 p1 p2p3p4 p5p6 p7 p8

Асимптотический анализ. EREW - Broadcast Пусть есть N исполнителей, которые используют одно и то же данное. Другой вариант: размножим это данное в разные ячейки памяти по количеству процессоров. Для считывания данного им понадобится время (logN). d1 d2d3d4 d5d6 d7 d8 p1 p2p3p4 p5p6 p7 p8

Асимптотический анализ. Частичные суммы Пусть есть N исполнителей и N значений – a1, a2, …, aN. Нам необходимо, чтобы k-й исполнитель мог использовать сумму a1+…+ak. Для расчета всех сумм потребуется время (N). a1 a2a3a4 a5a6 a7 a8 p1 p2p3p4 p5p6 p7 p8 + a12 + a123a1…4 + a1…5a1…6a1…7a1…8

Асимптотический анализ. Частичные суммы a1 a2a3a4 a5a6 a7 a8 p1 p2p3p4 p5p6 p7 p8 Пусть есть N исполнителей и N значений – a1, a2, …, aN. Нам необходимо, чтобы k-й исполнитель мог использовать сумму a1+…+ak. Способ 2. + a a23a34a45a56a67 a78

Асимптотический анализ. Частичные суммы a1 p1 p2p3p4 p5p6 p7 p8 Пусть есть N исполнителей и N значений – a1, a2, …, aN. Нам необходимо, чтобы k-й исполнитель мог использовать сумму a1+…+ak. Способ 2. a a23 a34a45 a56a67a78 + a123 a1..4a2..5a3..6a4..7a5..8

Асимптотический анализ. Частичные суммы a1 p1 p2p3p4 p5p6 p7 p8 Пусть есть N исполнителей и N значений – a1, a2, …, aN. Нам необходимо, чтобы k-й исполнитель мог использовать сумму a1+…+ak. Способ 2. Для расчета всех сумм потребуется время (logN). a a123a1..4a2..5a3..6a4..7a5..8 a1..5 a1..6a1..7a1..8

Асимптотический анализ. Параллельный выбор 1.Размерность задачи – n, количество исполнителей – N < n. Положим N = n 1-x, 0 < x < 1. Точнее максимальное N определим позже. 2. Каждый исполнитель умеет вычислять x и использовать последовательный алгоритм для решения задачи выбора. 3. Исполнители совместно умеют выполнять broadcast и считать частичные суммы.

Асимптотический анализ. Параллельный выбор Шаг 1: если |S| 4, элемент k-го ранга ищем сортировкой, иначе делим S на подмножества S i по количеству исполнителей. Получаем |S| 1-x множеств из q = |S| x элементов каждое (кроме, быть может, последнего) иначе делим S на подмножества S i по количеству исполнителей. Получаем |S| 1-x множеств из q = |S| x элементов каждое (кроме, быть может, последнего) … s1s1s1s1 s2s2s2s2 s3s3s3s3 s4s4s4s4 snsnsnsn s1s1s1s1 … sqsqsqsq s q+1 … s 2q … snsnsnsn S 1, |S 1 | =|S| x S 2, |S 2 | =|S| x S v, v = |S| 1-x, |S v | |S| x …

Асимптотический анализ. Параллельный выбор Шаг 2: Каждое Si поручаем своему исполнителю. С помощью процедуры последовательного выбора ищем медиану в каждом подмножестве. …

Асимптотический анализ. Параллельный выбор Шаг 3: Строим множество всех медиан M. Параллельно рекурсивно находим его медиану m 0. Параллельно рекурсивно находим его медиану m 0.

Асимптотический анализ. Параллельный выбор Шаг 4: Строим множества L: s i L s i < m 0 L: s i L s i < m 0 E: s i E s i = m 0 E: s i E s i = m 0 G: s i G s i > m 0 G: s i G s i > m 0

Асимптотический анализ. Параллельный выбор Шаг 5: Если |L| k – параллельно рекурсивно ищем в L значение элемента ранга k, иначе, если |L|+|E| k – искомое значение есть m 0, иначе – параллельно рекурсивно ищем в G значение элемента ранга k-|L|-|E|

Асимптотический анализ. Параллельный выбор Шаг 0: с помощью процедуры broadcast рассылаем всем исполнителям значения n, N, k и адрес массива S. Вычисляем x, для которого N=n 1-x. T 0 (n) = clog(N)= clog(n 1-x )=C 0 log(n)

Асимптотический анализ. Параллельный выбор Шаг 1: если |S| 5, элемент k-го ранга ищем сортировкой если |S| 5, элемент k-го ранга ищем сортировкой T 1 (n) = (1) иначе делим S на подмножества S i по количеству исполнителей. Получаем |S| 1-x множеств из q = |S| x элементов каждое (кроме, быть может, последнего) иначе делим S на подмножества S i по количеству исполнителей. Получаем |S| 1-x множеств из q = |S| x элементов каждое (кроме, быть может, последнего) T 1 (n) = Θ(1)

Асимптотический анализ. Параллельный выбор T 2 (n) = T seq (|S| x )=C 2 n x … Шаг 2: Каждое S i поручаем своему исполнителю. С помощью процедуры последовательного выбора ищем медиану в каждом подмножестве.

Асимптотический анализ. Параллельный выбор Шаг 3: Строим множество всех медиан M. Параллельно рекурсивно находим его медиану m 0, рассылаем ее broadcastом. T 3 (n)=T(|S| 1-x )+C 3 log(n)=T(n 1-x )+C 3 log(n)

Асимптотический анализ. Параллельный выбор Шаг 4: Строим множества L: s i L s i < m 0 L: s i L s i < m 0 E: s i E s i = m 0 E: s i E s i = m 0 G: s i G s i > m 0 G: s i G s i > m 0 Сначала строим множества L a, E a, G a на каждом процессоре, время – c 4 |S| x = c 4 n x. Далее, используя частичные суммы, объединяем их, время для вычисления адреса ~ log(n 1-x ), для копирования ~ n x. Итого T 4 (n) = C 4 n x +C 5 log(n)

Асимптотический анализ. Параллельный выбор Шаг 5 : Если |L| k – рекурсивно ищем в L значение элемента ранга k, иначе, если |L|+|E| k – искомое значение есть m 0,иначе – рекурсивно ищем в G значение элемента ранга k-|L|-|E| В множестве M не менее |M|/2= n 1-x /2) медиан m i, превышающих или равных m 0. В каждом из соответствующих S i не менее |S i |/2=n x /2 элементов множества S не меньших m i. Стало быть, |E|+|G| (n 1-x /2)*(n x /2) = n/4 и |L| 3n/4. Аналогично, |G| 3n/4.

Асимптотический анализ. Параллельный выбор Шаг 5 : Если |L| k – рекурсивно ищем в L значение элемента ранга k, иначе, если |L|+|E| k – искомое значение есть m 0,иначе – рекурсивно ищем в G значение элемента ранга k-|L|-|E| T 5 (n) = T(3n/4)

Асимптотический анализ. Параллельный выбор Оценим время выполнения T(n) Шаг 0: T 0 (n) = C 0 log(n) Шаг 1: T 1 (n) = Θ(1) Шаг 2: T 2 (n) = C 2 n x Шаг 3: T 3 (n) = T(n 1-x )+C 3 log(n) Шаг 4: T 4 (n) = C 4 n x +C 5 log(n) Шаг 5: T 5 (n) = T(3n/4) Окончательно T(n) = C 6 n x + T(n 1-x ) + T(3n/4) С помощью шаманских танцев можно показать, что T(n)=Θ(n x )

Асимптотический анализ. Параллельный выбор Стоимость параллельного алгоритма – cost = Θ(n x )*N = Θ(n x )*n 1-x = Θ(n) Время работы последовательного алгоритма было Θ(n). Предложенный алгоритм является оптимальным по стоимости.

Декомпозиция. Запись алгоритма Запись на естественном языке: «Макароны положить в кипящую воду (не менее 1 литра воды на 100 г. продукта), помешивая, варить до готовности». Что такое «готовность»? Вербальная запись алгоритма часто содержит неоднозначности, которые разными исполнителями могут трактоваться по-разному.

Декомпозиция. Запись алгоритма Запись формулой или на алгоритмическом языке : S = a[1] + a[2] + a[3]; Каков порядок выполнения операций? S = (a[1] + a[2]) + a[3] или S = a[1] + (a[2] + a[3]) ? Крокодила измеряем от головы до хвоста или от хвоста к голове?

Декомпозиция. Запись алгоритма Запись формулой или на алгоритмическом языке : Пусть мантисса может хранить только 4 десятичных разряда. a[1] = *10 4, a[2] = *10 4, a[3] = 0.6*10 0. Первый порядок сложения: a[1] + a[2] = 0,1024* *10 4 = *10 4 = 0.1*10 1 a[1] + a[2] = 0,1024* *10 4 = *10 4 = 0.1*10 1 (a[1] + a[2]) + a[3] = 0.1* * 10 0 = 1* *10 0 = 1.6*10 0 = 0.16*10 1 (a[1] + a[2]) + a[3] = 0.1* * 10 0 = 1* *10 0 = 1.6*10 0 = 0.16*10 1

Декомпозиция. Запись алгоритма Запись формулой или на алгоритмическом языке : Второй порядок сложения: a[2] + a[3] = * *10 0 = -1023* *10 0 = *10 0 = *10 4 = *10 4 a[2] + a[3] = * *10 0 = -1023* *10 0 = *10 0 = *10 4 = *10 4 a[1] + (a[2] + a[3]) = * * 10 4 = *10 4 = 0.2*10 1 a[1] + (a[2] + a[3]) = * * 10 4 = *10 4 = 0.2*10 1 Крокодил длиной 1.6 метра от головы к хвосту и длиной 2 метра от хвоста к голове!

Декомпозиция. Запись алгоритма Граф алгоритма, реализованного программой Каждой операции в алгоритме сопоставим вершину графа. Для наглядности отдельными вершинами отразим операции ввода и вывода. Если результат одной операции используется как данное при выполнении другой операции, то свяжем эти вершины направленным ребром. a[1] a[2]a[3] ++S a[3] a[2]a[1] ++S S = (a[1] + a[2]) + a[3] S = a[1] + (a[2] + a[3])

Декомпозиция. Запись алгоритма Граф алгоритма. Свойства 1.Граф является ациклическим. В программах реализуются только явные вычисления. 2.Граф может быть мультиграфом. 3.Граф является параметрическим. Он всегда зависит от размерности задачи, определяющей общее количество вершин в графе. a b *+S S = (a*a) + b

Декомпозиция. Запись алгоритма Граф алгоритма Граф является детерминированным, если он описывает алгоритм, лишенный условных переходов. Если граф недетерминированный, то: если под ветвлениями содержится небольшое количество операций, то операции можно укрупнить; если под ветвлениями содержатся большие детерминированные куски – занимаемся этими кусками. a +5y if (a>0) y=a+5 else y=a-1 ay > 0? +5 : -1

Декомпозиция. Строгая параллельная форма графа Пусть задан ориентированный ациклический граф, имеющий n вершин. Существует число s n, для которого все вершины графа можно так пометить одним из индексов 1, 2, …, s, что если дуга из вершины с индексом i идет в вершину c индексом j, то i < j. Так размеченный граф называется строгой параллельной формой графа

Декомпозиция. Строгая параллельная форма графа Группа вершин в строгой параллельной форме с одинаковым индексом называется ярусом. Для двух вершин, принадлежащих к одному ярусу, в графе не существует связывающего их пути. Следовательно, соответствующие им операции могут быть выполнены параллельно. Количество вершин в ярусе – его ширина. Число ярусов – высота параллельной формы

Декомпозиция. Строгая параллельная форма графа При выполнении алгоритма на последовательной машине в каждый момент времени выполняется ровно одна операция. Перенумеровав в графе алгоритма вершины в порядке их выполнения, получим строгую параллельную форму. Все ее ярусы имеют ширину 1, ее глубина – n. Для любой другой архитектуры можно также поставить в соответствие строгую параллельную форму, и наоборот – для любой строгой параллельной формы можно придумать подходящую архитектуру. Для любой другой архитектуры можно также поставить в соответствие строгую параллельную форму, и наоборот – для любой строгой параллельной формы можно придумать подходящую архитектуру. В модели PRAM с временем выполнения операций 1 время выполнения алгоритма есть глубина соответствующей формы.

Декомпозиция. Строгая параллельная форма графа Если ошибки округления при выполнении операций определяются только значениями операндов, то при выполнении операций в порядке, задаваемом строгой параллельной формой, для различных строгих параллельных форм будут получаться одинаковые результаты. Выполнение графа алгоритма приведет к одинаковым результатам на машинах разной архитектуры. Выполнение графа алгоритма приведет к одинаковым результатам на машинах разной архитектуры.

Декомпозиция. Каноническая параллельная форма графа Если в строгой параллельной форме для вершины с индексом k максимальная из длин путей, оканчивающихся в этой вершине, есть k-1, то такая параллельная форма называется канонической параллельной формой. Каноническая параллельная форма единственна. Она имеет ярусы максимальной ширины и обладает минимальной глубиной

Декомпозиция. Каноническая параллельная форма графа Максимально возможное ускорение при распараллеливании алгоритма в модели PRAM есть количество вершин в графе, деленное на глубину канонической параллельной формы Максимальное ускорение = 13/8

Активности и атомарные операции Отрезать ломтик хлеба Отрезать ломтик хлеба Отрезать ломтик колбасы Отрезать ломтик колбасы Намазать хлеб маслом Намазать хлеб маслом Положить колбасу на хлеб Положить колбасу на хлеб Активность - последовательное выполнение ряда действий, направленных на достижение определенной цели Активность : приготовление бутерброда Атомарные или неделимые операции

Interleaving Активность P: a b c Активность Q: d e f Последовательное выполнение PQ: a b c d e f Псевдопараллельное выполнение (режим разделения времени) : ? a b c d e f a b d c e f a b d e c f a b d e f c... d e f a b c

Детерминированные и недетерминированные наборы активностей Недетерминированный набор – при одинаковых начальных данных возможны разные результаты Недетерминированный набор – при одинаковых начальных данных возможны разные результаты Детерминированный набор – при одинаковых начальных данных всегда один результат Детерминированный набор – при одинаковых начальных данных всегда один результат P: x=2 y=x-1 Q: x=3 y=x+1 (x, y): (2, ) (2, 1) (3, 1) (3, 4) (2, ) (3, ) (3, 4) (3, 2) (2, 3) (2, 1)

Условия Бернстайна (Bernstain) P: 1) x=u+v 2) y=x*w Входные переменные R 1 = {u, v} R 2 = {x, w} Выходные переменные W 1 = {x} W 2 = {y} R(P)={u, v, x, w} W(P)={x, y} Если: 1)W(P) W(Q) = {ø} 2) W(P) R(Q) = {ø} 3) R(P) W(Q) = {ø} то набор активностей {P, Q} является детерминированным Если для двух операторов в программе, динамически непосредственно следующих друг за другом, выполнены условия Бернстайна, то их можно исполнять параллельно.

Нарушение условий Бернстайна 1)W(P) W(Q) = {ø} 2) W(P) R(Q) = {ø} 3) R(P) W(Q) = {ø} оператор P динамически предшествует оператору Q оператор P динамически предшествует оператору Q 1)W(P) W(Q) {ø} P: x = e + 2z Q: x = 2f + z Зависимость по выходным данным P δ 0 Q PQ Способ борьбы: переименование переменных. Распараллеливанию принципиально не мешает. P: x = e + 2z Q: y = 2f + z

Нарушение условий Бернстайна 1)W(P) W(Q) = {ø} 2) W(P) R(Q) = {ø} 3) R(P) W(Q) = {ø} оператор P динамически предшествует оператору Q оператор P динамически предшествует оператору Q P: x = e + 2z Q: z = 2f + y Антизависимость P δ -1 Q PQ Способ борьбы: перед исполнением размножить значение z Распараллеливанию принципиально не мешает 3) R(P) W(Q) {ø}

Нарушение условий Бернстайна 1)W(P) W(Q) = {ø} 2) W(P) R(Q) = {ø} 3) R(P) W(Q) = {ø} оператор P динамически предшествует оператору Q оператор P динамически предшествует оператору Q P: x = e + 2z Q: y = 2f + x Истинная или потоковая зависимость P δ Q PQ Способ борьбы: не существует. Распараллеливание невозможно. 2) W(P) R(Q) {ø}

Другие виды зависимостей S1: m = sin(x) if (m > 0) then S2: y = 2 + x else S3: y = 6 – x endif if (m > 0) then S2: y = 2 + x else S3: y = 6 – x endif Зависимость по управлению S1 δ c S2, S1 δ c S3 S1S2 Способ борьбы: сводим к зависимостям по данным. S3 c c S1: m = sin(x) S2: where (m>0) y = 2 + x S3: where (m0) y = 6 – x Истинная зависимость S1 δ S2, S1 δ S3 S1: a = b/c S2: d = e/f Одно устройство деления Зависимость по ресурсам S1 δ R S2 S1S2 R

Составление графа зависимостей S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1 S2 S3 S4 S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x S1: x = e + 2z S2: y = 2f + x S3: z = z + y S4: y = z + x

Зависимости в невложенных циклах do i =1, u do i =1, u S1: …a(f(i))… S2: …a(g(i))… enddo enddo Если k, : 0 k, u и f(k)= g( ), то есть зависимость в операторах цикла. Нужно решить диофантово уравнение. S 1 k – источник (source) зависимости, S 2 λ – сток (sink) зависимости d = - k (из итерации стока вычитаем итерацию источника) – это расстояние зависимости. do i =1, u do i =1, u S1: a(f(i)) = … S2: … = a(g(i)) enddo enddo S 1 1 : …a(f(1))… S 2 1 : …a(g(1))… S 1 2 : …a(f(2))… S 2 2 : …a(g(2))… S 1 3 : …a(f(3))… S 2 3 : …a(g(3))… S 1 1 : a(f(1)) = … S 2 1 : … = a(g(1)) S 1 2 : a(f(2)) = … S 2 2 : … = a(g(2)) S 1 3 : a(f(3)) = … S 2 3 : … = a(g(3))

Зависимости в невложенных циклах = 2, k =1, d = - k = 1 = 2, k =1, d = - k = 1 Истинная зависимость Общее утверждение: если d > 0, то имеет место истинная зависимость между операторами цикла, исполняющимися на разных итерациях. d = 1 – параллельное выполнение итераций цикла на разных процессорах невозможно! do i =1, u do i =1, u S 1 : a(i) = d(i)+5*i S 2 : c(i) = a(i-1)*2 enddo enddo S 1 1 : a(1) = … S 2 1 : …

Зависимости в невложенных циклах = 3, k =1, d = - k = 2 = 3, k =1, d = - k = 2 Истинная зависимость 1 -> 3 -> 5 -> 7-> … 2 -> 4 -> 6 -> 8 -> … Возможно распараллеливание для 2-х исполнителей do i =1, u do i =1, u S 1 : a(i) = d(i)+5*i S 2 : c(i) = a(i-2)*2 enddo enddo S 1 1 : a(1) = … S 2 1 : …

Зависимости в невложенных циклах = 1, k =2, d = - k = -1. Антизависимость = 1, k =2, d = - k = -1. Антизависимость Общее утверждение: если d < 0, то имеет место антизависимость между операторами цикла, исполняющимися на разных итерациях. Параллельное выполнение итераций цикла на разных процессорах возможно при дублировании необходимых входных данных. do i =1, u do i =1, u S 1 : a(i) = d(i)+5*i S 2 : c(i) = a(i+1)*2 enddo enddo S 1 1 : a(1) = … S 2 1 : …

Зависимости в невложенных циклах Зависимость не связана с наличием цикла – loop independent dependence. Зависимость сконцентрирована в пределах одной итерации. Возможно параллельное исполнение различных итераций. do i =1, u do i =1, u S 1 : a(i) = d(i)+5*i S 2 : c(i) = a(i)*2 enddo enddo Что произойдет при d = 0? = k, d = - k = 0 = k, d = - k = 0 Истинная зависимость do i =1, u do i =1, u S 1 : c(i) = a(i)*2 S 2 : a(i) = d(i)+5*i enddo enddo = k, d = - k = 0 = k, d = - k = 0Антизависимость

Зависимости в невложенных циклах do i =1, u do i =1, u S 1 : a(2*i) = d(i)+5*i S 2 : c(i) = 2*a(i) enddo enddo f(1) = g(2), f(2) = g(4), f(3) = g(6), d = ? Расстояние неопределенное, d = *, но d > 0. Истинная зависимость S11: a(2) = … S21: …

Зависимости во вложенных циклах for (j1= 0; j1 < M1; j1++){ for(j2 = 0; j2 < M2; j2++){ a[f1(j1,j2),f2(j1,j2)] = …; … = a[g1(j1,j2),g2(j1,j2)]; {} Пространство итераций: (0,0), (0,1), …, (0,M2), (1,0), …, (1,M2), … (M1, 0), …, (M1,M2) Вектора итераций – (j1,j2) - упорядочены

Зависимости во вложенных циклах Раскрутка a[f1(0,0),f2(0,0)]=…; … = a[g1(0,0), g2(0,0)]; a[f1(0,1),f2(0,1)]=…; … = a[g1(0,1), g2(0,1)]; и т.д. и т.д. Если вектора итераций k и из пространства итераций: f1(k) = g1( ), f2(k) = g2( ), то в цикле имеет место зависимость. Вектор расстояний D = k - Вектор расстояний D = k - Вектор направлений d: if Di di = > if Di == 0 -> di = = if Di > 0 -> di = 0 -> di =

Устранение истинных зависимостей Разделение цикла Loop Distribution D0 I = 1, N S1: A(I+1) = B(I) + C S2: D(I) = A(I) + E ENDDO Наблюдаем истинную зависимость: S1 δ S2, расстояние зависимости D = -1. Преобразование, снимающее зависимость DO I = 1, N S1: A(I+1) = B(I) + C ENDDO DO I = 1, N S2: D(I) = A(I) + E ENDDO

Устранение истинных зависимостей Выравнивание цикла Loop Alignment do i=2,n S1: a(i)= b(i)+2 S2: c(i)= a(i-1) * 2 enddo Наблюдаем истинную зависимость: S1 δ S2, расстояние зависимости D = -1. Преобразование, снимающее зависимость do i=1,n S1: if (i>1) a(i)= b(i)+2 S2: if (i

Устранение истинных зависимостей Реплицирование кода Code Replication do i=1,n S1: a(i+1)= b(i)+2 S2: c(i)= a(i+1) * a(i) enddo Истинная зависимость между S1 и S2 мешает параллелизму. После преобразования do i=1,n a(i+1)= b(i)+2 if (i=1) t=a(1) else t=b(i-1)+2 c(i)= a(i+1) * t enddo

Устранение истинных зависимостей Приватизация скалярных переменных Privatization INTEGER J DO I = 1, N J = … A(I) = J ENDDO После преобразования INTEGER J, Jx(N) DO I = 1, N Jx(I) = … A(I) = Jx(I) ENDDOJ=Jx(N)

Устранение истинных зависимостей Подстановка индукционных переменных Induction Variable Substitution DO I = 1, N J = J + K A(I) = J ENDDO После преобразования DO I = 1, N A(I) = I*K ENDDO Может изменить полученный результат !!!!!

Устранение истинных зависимостей Подстановка индукционных переменных REDUCTION(op:list) DO I = 1, N sum = sum + A(I) ENDDO После преобразования DO I = 1, N Reduction(ADD, A, N, sum) ENDDO Может изменить полученный результат !!!!!

Управление распределением задач 1.Статическая схема 2.Потоковая схема – master-worker, все непараллельные части выполняет только мастер 3.Динамическая схема – master-worker, непараллельные части выполняют все исполнители 4.Pool of works (набор работ) 5.Competition (соревнование)

Спасибо за внимание !