Добавил:
Upload Опубликованный материал нарушает ваши авторские права? Сообщите нам.
Вуз: Предмет: Файл:
Konspekt_Trsipv_Ch_2.doc
Скачиваний:
1
Добавлен:
01.07.2025
Размер:
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 Распараллеливание программ с использованием понятия модели вычислительного процесса Понятие операции и выражения

Операция – некоторое элементарное неделимое вычислительно е действие. Выражение – это совокупность элементарных действий, образующих последовательный участок программы. Последовательное выражение характеризуется наличием отношений строгого порядка между операторами в нем. Метод предполагает формирование ярусно-параллельной формы программы (ЯПФ). ЯПФ – это ориентированный граф, узлами которого являются некоторые операции. ЯПФ определяет наличие уровней, операторы на которых могут выполняться независимо. Последовательность ярусов определяет порядок последовательного выполнения задач.

Достоинства:

  1. Максимальный параллелизм достигается совместным распараллеливанием участков, входящих в разные выражения программы.

  2. Реализация распараллеливания обеспечивается уникальным именованием, входящих в выражение переменных результатов.

  3. Метод позволяет реализовать автоматическое распараллеливание программ.

Анализируемая последовательная программа в результате применения метода может быть представлена в виде управляющего графа 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 на участке . Дуги характеризуют передачу управления от одной вершины к другой.

Соседние файлы в предмете [НЕСОРТИРОВАННОЕ]