- •Оглавление
- •1. Архитектура, технологические характеристики, принципы работы, проблемы развития компьютеров и вс. 3
- •2. Принципы, языки, технологии параллельного программирования. 16
- •3. 3. Реализация параллельных языков программирования 34
- •Архитектура, технологические характеристики, принципы работы, проблемы развития компьютеров и вс.
- •Краткая история развития параллелизма в архитектуре эвм.
- •Введение и основные понятия.
- •Ряд основных понятий и определений.
- •Архитектурный облик современного компьютера.
- •Режимы работы компьютера и связь с работой процессора.
- •Два вида параллелизма.
- •Показатели вс, сравнение.
- •Принципы, языки, технологии параллельного программирования.
- •Параллелизм задач, его особенности и характеристики.
- •Процессы, их характеристики.
- •Типы и характеристики параллелизма.
- •Типы и особенности параллелизма.
- •Процессы модели и языки.
- •Сети Петри
- •Событийная модель; статические процессы.
- •Расширение сети Петри
- •1. Одновременность.
- •2. Сети с порождение процессов.
- •3. Расширение: рекурсивные сети
- •4. Раскрашивание сети
- •Модели взаимодействующих последовательных процессов Хоара
- •3. Реализация параллельных языков программирования
- •Примитивы и языки параллельного программирования
- •Язык граф - схемного потокового параллельного программирования (ягспп)
- •Функциональное параллельное программирование
- •3.4.1.1. Операции композиции
- •3.4.1.2. Задание данных и базисных функций
- •Модель асинхронного выполнения функциональных программ
Типы и особенности параллелизма.
Явный параллелизм –
векторные команды;
операторы с условиями синхронизации (условие готовности , как только оно выполнено,можно выполнить);
fork – join;
Нити;
MPI – процессы.
Неявный параллелизм –
последовательная программа;
функциональная программа;
логическая программа.
язык программа (текст)денотационная семантика (содержание текста программы, исходя из свойств операций)операционная семантика (последовательность выполнения программы (последовательное применение программы: входвыход)).
2. Параллелизм последовательных, функциональных, логических программ, ОО и др.
Коммутативный –
Некоммутативный –
Пример. Функция голосования.
Параллельная функция, которую нельзя вычислить последовательно:
В идеале - надо вычислять параллельно.
SIM END – коммутативный оператор, так как можно вычислять в любом порядке.
- некоммутативный оператор.
Упреждающий –
Без упреждения –
При чем - обязательно надо вычислить,- возможно потребуются, то есть мы их вычисляем с упреждением.
- вычисления без упреждения.
- с упреждением.
Можно получать ускорение до 50%. .
Пространственный параллелизм –
Конвейерный параллелизм –
Можно организовать конвейерное выполнение команд. m копий программы, ко всем применять независимопространственный параллелизм (ускорениеmax в m раз).
Конвейер – самая экономичная схема с точки зрения загрузки ресурсов (каждая единица всегда работает). Пространственный параллелизм более объемен.
Задачи.
Сеточные задачи.
- задана на границе. - некая функция от соседних точек.
Можно разбить на области, и каждый компьютер считает свою область.
СЛАУ
Метод Ньютона плохо параллелится Но параллельно решать задачу возможно, при условии: если A хорошо определены.
задаем начальные значения
- критерий останова. Данная схема является синхронной.
Может быть асинхронная схема.
Как только хотя бы одно новое появляется, то дальше вычисляем с нимвыигрыш. Эта задача является задачей с регулярными связями.
Процессы модели и языки.
Событийные модели, то есть модели отвлеченные от времени с сохранением причинно-следственных связей между актами.
Вопросы:
Порождение процессов.
Допускает ли система порождение процессов или все статистики предопределены.
Взаимодействие процессов.
Fact – точки-места взаимодействия.
Состояние процессов.
активный (выполняется);
не может порождаться по логическим причинам (нет данных для дальнейшей работы);
нет ресурсов - пассивен;
временной фактор пассивен.
Сети Петри
Событийная модель; статические процессы.
Позволяют представить конечные автоматы, многие вычислительные задачи.
Сеть Петри:
Можно задать таблицей:
p1 |
… |
p1 |
место |
n1 |
… |
nk |
количество фишек |
Пример Сети Петри
p1 |
p2 |
p3 |
1 |
1 |
0 |
Процесс (правила) функция сети – смена её разметок (последовательно).
- фиксирует состояние процесса правила смены (перехода из состояния в состояние) разметок: переход считается готовым для срабатывания, если во всех его входных местах есть хотя бы по одной фишке. Входные места те, где есть стрелки ведущие в переход. При срабатывании перехода из всех его входных мест изымается по одной фишке и добавляется по одной фишке во все входные места перехода, если имеется стрелка из этого перехода.
Переход: a.
На входе: p1;
На выходе: p1,p2; и т.д.
Возникают вопросы:
В данном случае, какой из переходов сработает?
Если есть (1) и (2), то хотелось бы, чтобы они сработали параллельно.
В математической модели есть некий «оракул», который видит эту сеть и выбирает произвольным образом переход, который должен сработать. В один момент времени работает только один переход.
Эквивалентности сетей.
Одновременность.
оракул выполняет переходы мгновенно;
два перехода могут срабатывать одновременно.
Пример.
begin real r1, r2, z,
real array a, b, c, d [1...100]
S: r1 := r2 := z := 0;
par begin
A: for I := 1 step 1 until n to
r1 := r1 + a[i] b[i]
B: for j := 1 step 1 until n to
r2 := r2 + c[i] d[i]
end
E: z := r1 + r2 ;
output (z)
end
- взаимоисключение.
Пример.
Семафоры Дейкстры.
par begin semaphore
S1, S2, S3;
S1 := 0; S2 := 0; S3 := 1;
Пр1: begin L1 : P(S1); P(S3);
занести данные в буфер
V(S3); V(S2); goto L1;
end;
Пр2: begin L2 : P(S2); P(S3);
прочитать данные из буфера
V(S3); V(S1); goto L2;
end;
end.
S1 – количество пустых мест в буфере;
S2 – количество пустых мест в буфере;
S3 – семафор взаимного исключения;
P – проверка, можем ли войти в критическую область (S>0);
V – S : = S+1.
Пример.
Обедающие философы.
Дано:
Стол, 5 философов, 5 мест, 5 вилок.
Для того, чтобы один из философов мог пообедать, ему необходимо взять две вилки.
Задача состоит в синхронизации процессов.
Вводится ограничение: больше четырех философов в столовой быть не может.