- •Теории параллельных вычислений
- •Часть 2
- •Теории параллельных вычислений. Часть 2. Методические указания / Сост. К.В.Кротов - Севастополь: Изд-во СевНту, 2009.- 81 с.
- •Содержание
- •1. Понятия отношений. Классы эквивалентности
- •2. Понятие зависимостей между операторами программы
- •Отношениями зависимости и независимости операций
- •3.1 Непосредственная (сильная) зависимость операций
- •Понятие линейной программы
- •Понятие множеств переменных, используемых в программе
- •Понятие входных переменных в программе
- •3.2 Слабая зависимость операций
- •3.3 Слабая независимость операций
- •3.4 Сильная независимость операций
- •Свойства отношений зависимости и независимости между операциями
- •Алгоритм распараллеливания последовательных программ путем приведения их к полной параллельной форме (ппф)
- •4.1 Условия приводимости к ппф
- •Упрощенная интерпретация условия
- •Пояснение к условию
- •Правило изменения порядка:
- •4.2 Процедура приводимости к ппф
- •Алгоритм преобразования программы к ппф
- •4.3 Метод формирования параллельных групповых операторов
- •Особенности распараллеливания программы путем приведения ее к ппф
- •5.1 Понятие двумерной модели вычислительного процесса
- •5.2 Уточнение множеств двумерной модели вычислительного процесса
- •6 Распараллеливание программ с использованием понятия модели вычислительного процесса Понятие операции и выражения
- •6.1 Постановка задачи распараллеливания
- •Правила построения таблицы для распараллеливания
- •6.2 Условия формирования множества *Aк (функция f1 - функция двумерной модели)
- •Условие бесконфликтности
- •6.3 Правила построения япф программы
- •6.4 Формализация условий вынесения операций ai на k-ый ярус япф
- •Операции с тремя входами
- •7 Распараллеливание программ на основе понятий примитивно-вычислимых и частично-вычислимых функций Понятие вычислимых и рекурсивных функций
- •7.1 Задание рекурсивных функций (Формирование процесса задания алгоритма вычислимых функций)
- •7.2 Суперпозиция вычислимых функций Задание области определения для оператора суперпозиции вычислимых функций
- •7.3 Оператор примитивной рекурсии
- •7.4 Распараллеливание алгоритмов примитивной рекурсии
- •7.5 Распараллеливание простейших аддитивных и мультипликативных функций
- •7.6 Операторы представления суперпозиции и примитивной рекурсии
- •Суперпозиция
- •Оператор рекурсии
- •7.7 Обобщенная форма операторов суперпозиции и рекурсии
- •7.8 Обобщенный вид оператора рекурсии
- •7.9 Обобщенный вид оператора суперпозиции для множественного потока данных
- •8 Распараллеливание программ с использованием моделей вычислительных процессов Модели программ
- •8.1 Граф управления
- •Информационный граф программы
- •8.2 Понятие графа зависимости между операторами
- •8.3 Граф влияния
- •8.4 Теоретико-графовый подход к распараллеливанию алгоритмов
- •8.5 Транзитивные замыкания
- •Формирование транзитивного замыкания
- •Формализация транзитивного замыкания (транзитивного образа вершины)
- •Формализация процедуры определения транзитивного прообраза вершины
- •8.6 Алгоритм формирования параллельной формы программы по графу управления на основе понятия транзитивного образа замыкания вершины
- •8.7 Алгоритм распараллеливания на основе понятия прообраза
- •8.8 Приведение стандартной схемы программы к ярусно-параллельной форме
- •Модели параллельных процессов
- •9 Сети петри
- •Алгоритм функционирования сети Петри
- •Возможности применения сетей Петри
- •10 Графовые модели. Общие понятия
- •10.1 Модель биологического графа
- •Правило функционирования моделей биологических графов
- •10.2 Модель модифицированного биологического графа
- •11.1 Алгоритм формирования а-схемы
- •11.2 Понятие спусковых и управляющих функций
- •11.3 Функционирование a-схем
- •11.4 Понятие вычислительного процесса
- •Аксиомы вычислительного процесса
- •Требования информационного обеспечения оператора а
- •11.5 Понятие конечного автомата (ка)
- •11.6 Логические рассуждения. Комментирование функционирования ка
- •12 Параллельные операторные схемы
- •Правило функционирования операторных схем
5.2 Уточнение множеств двумерной модели вычислительного процесса
Множество *At может быть определено
*At
=
*At1
*At2
Множество *At1 – это множество операций, для которых до момента t было дано разрешение на включение, но они не были включены в силу отсутствия свободных ресурсов [0; t-1].
At2 - множество операций, которым разрешение на включение дано в момент времени t.
Множество операций +At выбираются с учетом свободных ресурсов и приоритетов выполнения действий.
+At
=
{
j
*At
|
dj
= max
{dl}},
где
- число свободных процессов момент
времени t;
dj – приоритет включающихся операций, являющихся максимальными среди всех операций, готовых к выполнению;
Число свободных процессоров определяется в виде:
nt = n - nj | tjн + tj >t,
aj PAt
где tjн - момент времени включения j-ой операции;
tj - время выполнения j–ой операции;
n – общее число процессоров;
nj - число процессоров, занятых выполнением j-ой операции.
При это операция aj является работающей и к текущему моменту времени t она не завершила своего выполнения.
Множество операций PAt определяется:
PAt = ( PAt-1 +At) \ -At-1.
Множество операций, работающих в момент времени t, образуется из множества работавших операций на (t-1) шаге и множества включившихся операций на (t-1) шаге, при исключении выключившихся на (t-1) шаге операций.
Множество операций -At формируется с учетом текущего времени t и времени обработки.
-At = aj pAt | tjн + tj t,
tj - время обработки.
-At - это те, для которых сумма значений времени начала работы и интервала времени обработки меньше, чем текущее значение.
6 Распараллеливание программ с использованием понятия модели вычислительного процесса Понятие операции и выражения
Операция – некоторое элементарное неделимое вычислительно е действие. Выражение – это совокупность элементарных действий, образующих последовательный участок программы. Последовательное выражение характеризуется наличием отношений строгого порядка между операторами в нем. Метод предполагает формирование ярусно-параллельной формы программы (ЯПФ). ЯПФ – это ориентированный граф, узлами которого являются некоторые операции. ЯПФ определяет наличие уровней, операторы на которых могут выполняться независимо. Последовательность ярусов определяет порядок последовательного выполнения задач.
Достоинства:
Максимальный параллелизм достигается совместным распараллеливанием участков, входящих в разные выражения программы.
Реализация распараллеливания обеспечивается уникальным именованием, входящих в выражение переменных результатов.
Метод позволяет реализовать автоматическое распараллеливание программ.
Анализируемая последовательная программа в результате применения метода может быть представлена в виде управляющего графа G(U,V), где
U – Множество вершин графа (операций);
V – Множество связей передачи управления.
Аналогичным образом, некоторый участок может быть представлен в виде подграфа: G (U, V)
aj U
aj U
Через
U
U,
U
U
могут
быть обозначены декартово произведение
вершин графа и подграфа, тогда множество
связей в графе определяется на основе
V
U
U.
Множество связей участка определяется:
C = (in U out U) \ (in U out U)
Множество связей между вершинами:
С = (in aj out ai) , i < j
Выражение С определяет дуги между вершинами ai и aj на участке . Дуги характеризуют передачу управления от одной вершины к другой.
