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

Дисциплины:






Модель мультипотоковых вычислений Блумова-Лейзерсона



Это модель динамических мультипотоковых вычислений, в ходе которых один поток может прождать друшие и т.д. Каждый поток представляется как последовательность элементарных задач (единичных, то есть выполняющихся за один такт процессорного времени). Модель представляется в виде графа, в котором вершинами являются элементарные задачи.

 

3 типа дуг:

1) дуги следования, определяющие строгую последовательность задач в потоке (из а1 в а2);

2) дуги порождения, кот. показывают порождения одного потока другим (из а3 в b1);

3)
дуги зависимости, кот. накладывают дополнительные условия на выполнение потока (например: дуга из b3 к a4 показывает. Что для перехода к a4 необоходимо не только выполнение а3 из потока А, но и b3 из потока В).

Ограничения, наклыдываемые на граф:

1) «strict» - дуги зависимости могут идти только от потомков к предкам; таким образом граф становистся ориентированным ациклическим графом;

2) «fully strict» - дуги зависимости могут идти только от потомка к родителю (т. е. дуги от с2 к а3 быть не может, а с2 — b3 может быть).

В качестве ресурса — память — это кадр активации потока. В любой момент времени можно определить, сколько места занимают потоки. Активационная глубина потока — это количество кадров активации самого потока и всех его предков. Активационная глубина вычисления — максимальная активационная глубина потоков в вычислении.

Модель мультипотоковых вычислений позволяет давать оценки:

1) время выполнения;

2) минимальный объем ресурсов памяти, кот. необходим для этого вычислений;

3) характер масштабируемости вычислений (идеал — линейный рост производительности при увеличении числа процессоров.

W – объем вычислительной работы при выполнении параллельного вычисления — сумма всех элементарных задач во всех потоках. Глубина вершины в графе — это максимально длинный путь от корневой вершины до рассматриваемой. Самый длинный путь в графе называют критическим.

33. Планирование мультипотоковых вычислений. «Жадный планировщик».

Система с Р процессорами. На каждом шаге вычисления, имея Р свободных процессоров и N готовых к выполнению потоков, планировщик делает один из двух шагов:

1) полный шаг, когда потоков больше или столько же, сколько процессоров → процессор берет из пула любые Р потоков и распределяет по процессорам;

2) неполный шаг, когда потоков меньше, чем процессоров → все потоки отправляются на процессоры.

В случае, если ресурсы ограничены, то это планировщик не очень хорош.

34. Планирование мультипотоковых вычислений. «Занятые листья».

Планировщик один, имеет общий пул готовых потоков. Обеспечивает обязательное выполнение потоков-листьев (св-во «занятые листья»). Главный минус — это централизованный алгоритм, что мешает масштабированию системы.



Пусть В породил поток А.

1) Если А порождает новый поток Х, то процессор выдается на выполнения потока Х, а А снимается с процессора и складывается в общий пул готовых потоков.

2) Если поток А простаивает в ожидании события, то он снимается с процессора, а планировщик отправляет на выполнение произвольный поток из пула.

3) Если поток А завершается, то процессор освобождается, а планировщик проверяет родителей (поток В) — если у В нет потомков, он не выполняется на каком-то другом процессоре и готов к выполнению, а процессор свободен, то на выполнение ставится В.

 

35. Планирование мультипотоковых вычислений. «Похитетель работ».


По сути — те же самые «занятые листья», но распределенный — это сеть планировщиков (в каждом вычислительном модуле по одному). Нет общего пула — неупорядоченного множества - готовых потоков. Вместо этого в каждом модуле реализован дек.

Пусть В породил поток А.

1) Если А порождает Х, то процессор отдается Х, а поток А помещается в дек, как в стек слева.

2) Если А в ходе выполнения создал условия готовности для своего родителя В. То поток В помещается в дек, как в стек.

3а) Если поток А завершился или завис в ожидании, то А снимается с процессора, а на процессор идет поток, извлеченный из дека, как из стека.

3б) Если свой дек пуст, то планировщик данного модуля случайным образом выбирает «жертву» в деке другого модуля и, если там не пусто, то забирает поток оттуда себе (справа).

«Похититель работ» гарантирует выполнение сввойства «занятые листья», то есть обязательное выполнение всех потоков-листьев.

 





sdamzavas.net - 2019 год. Все права принадлежат их авторам! В случае нарушение авторского права, обращайтесь по форме обратной связи...