Тема 3_2010_Функционирование МВС при решении сложных задач (Лекции (ещё одни)), страница 2

3, можно сделать вывод, что критический путь графа сучетом передач изменился -1; 3; 7; 10; 11; 12, а Tтin = 46.Рассмотрим теперь алгоритм поиска КП для графа задачи с учетомпередач на МВС с распределенной памятью (рис. 4). Отметим, чторассматриваемая задача аналогична задаче, граф которой приведен на рис.3.Следует обратить внимание на то, что целью вычисления КП при реализациизадачи на МВС с распределенной памятью является определение среди узловпоследователей (r=1...v) (см.

рис. 1) узла, который назначается на процессор,выполняющий узел-предшественник. В этом случае данные от узлапредшественника не передаются узлу-последователю (Тjr приравнивается к нулю).Рис. 3. Определение критического пути для графа задачи с учетом передач наМВС с общей памятьюСледующие допущения являются основными при реализации графа задачина МВС с распределенной памятью.1. Граф реализуется на системе с неограниченными ресурсами.2.

От каждого узла графа данные могут передаваться параллельно поисходящим ветвям.3. Каждый узел графа может принимать данные параллельно повходящим ветвям.4. Каждый узел графа может иметь не больше одной входящей и небольше одной исходящей ветви, времени передачи по которой врезультате поиска КП присваивается значение равное нулю.Алгоритм определения КП для графа задачи, выполняемой на МВСс распределенной памятью, состоит в том, что при вычислении по формуле (1)минимально возможного времени начала выполнения i-гo узла Тmin i определяетсяодна из входящих в него ветвей, времени передачи по которой присваиваетсязначение равное нулю.

При этом это должна быть такая ветвь, которая вноситмаксимальный эффект в уменьшении Тmin i. Очевидно, что не всегда с первой жепопытки можно определить Тmin i. Например, определив ветвь di, входящую в i-йузел, обуславливающую Тmin i необходимо провести анализ узла d, из которогоисходит эта ветвь. Если у этого узла уже есть одна исходящая ветвь, которойРис. 4.

Определение критического пути для графа задачи с учетом передач наМВС с распределенной памятьюприсвоено значение Tdk=0 (т.е. определен k-й узел - последователь d-гoузла, и, следовательно, процессор оставил необходимые данные для выполненияк-го узла в своей локальной памяти), то ветвь di из рассмотрения исключается.Находится следующая по значению эффективности ветвь, входящая в i-й узел ит.д.Если у d-гo узла нет исходящей ветви, которой присвоено значениеравное нулю, то для этого d-гo узла определяется присутствие такой ветви, укоторой τdk > τdi.

Если такая ветвь есть, то i-й узел исключается израссмотрения до тех пор, пока не будет принято решение о присвоении илине присвоении ветви dk значения Tdk=0. Если такой ветви нет, то Tdi присваиваетсязначение, равное нулю, и уже с учетом этого определяется Тmin i.Следует обратить внимание на следующее. Если k-й узел расположен наболее низком ярусе графа чем i-й узел, то при нахождении Tmin k анализируютсявсе пути от вершины d к вершине к, а значение 0 может быть присвоено ( илине присвоено) в соответствии с правилами, изложенными выше для узла i, однойиз ветвей, исходящих из узла d (необязательно для ветви dk).Максимально возможное время начала выполнения узла Тmax i вычисляетсяпо формуле (2) при обратном движении по графу уже с учетом определенныхвыше нулевых ветвей. Данные ветви помечены на рис.

4 стрелкой (например,3→0). В приведенном примере граф задачи имеет единственный КП 1-4-10-11-12, длина которого равна Тmin =27.Из рассмотренных примеров видно, что длина критического пути (Тmin)является основным параметром, характеризующим информационно-логическуюструктуру вычислительного процесса (ВП), реализующего решение заданнойприкладной задачи.

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

Под ресурсами понимаются: модули обработки(процессоры), модули памяти (она может быть распределенной, общей илисмешанной), внутрисистемный интерфейс (общая шина, мультиплексная шина).При построении алгоритмов назначения в отказоустойчивых МВС в модельдолжны быть введены средства, описывающие систему обеспеченияотказоустойчивости МВС. Например, средства, обеспечивающие введениедополнительных копий узлов графа задачи и дополнительных процессоров.Рассмотрим наиболее простой случай.Пусть в качестве ресурсов в модели используется только набороднотипных процессоров, имеющих равное быстродействие. На данном наборепроцессоров выполняется вычислительный процесс, имеющий сетевуюструктуру и представляющий собой совокупность отдельных алгоритмов(сегментов задачи) Z = {zi}.Формально модель выполнения задачи Z можно представить совокупностью{Z, <, T, W, Θ},где Z = { zi , zL } - множество сегментов задачи, выполняемых в системе(узлы графа);< - означает задание в множестве Z отношения частичногопорядка, которое определяет последовательность выполнения сегментов иинформационные связи между ними (связность узлов);Т = {t1, …, tL} - вектор времен выполнения сегментов на процессоре сзаданным быстродействием;W = {w1, …, wL} - вектор коэффициентов важности сегментов,соответствующих коэффициентам относительных потерь эффективности из-заневыполнения сегментов задачи вследствие отказа процессора, на которомвыполняется данный сегмент;|| Θ || = || τiq ||, i = 1 … L, q = 1 ...

L-1 - матрица времен занятости шины сзаданной пропускной способностью при передаче данных между узлами i и q.Величина τiq является характеристикой не только структуры графазадачи и пропускной способности шины, но и способа организации МВС.Как было отмечено выше, в качестве модели задачи используетсянаправленный граф, узлы которого отображают сегменты задачи.

Припостроении алгоритмов, реализующих задачу назначения, направленный графпреобразуется в таблицу связности, элементы которой1, если выходная информация узла zi является входнойAij = для узла zj0 в противном случае.В качестве критериев оптимальности распределения узлов в МВСприменяются обычно либо минимум времени выполнения задачи (набора задач)при ограничении на число процессоров, либо минимум числа требуемыхпроцессоров при ограничении на время решения задачи (набора задач).В качестве производных от этих критериев используются следующие –• максимум загрузки каждого процессора ( K загр i),• минимум простоев каждого процессора (K пр i).K загр i = Ti / T вып,(3)где Ti – время, в течение которого i-й процессор занят обработкой задачи;Tвып - время выполнения задачи;K пр i = 1 - K загр i .(4)Следует отметить при этом, что эффективность как алгоритмовраспределения узлов задачи, так и выбранной структуры МВС можно оценить спомощью коэффициента ускорения (Куск), показывающего ускорение временирешения задачи на n процессорах в сравнении с временем решения этой же задачина одном процессореKуск = Tmax / Tn,(5)где Tmax – время решения задачи на одном процессоре;Tn – время решения задачи на n процессорах.Втеоретическомпланеприпостроенииалгоритмовоптимальных расписаний могут быть использованы математическиеметоды, например, динамического программирования.

Однако этодостаточно сложная проблема, так как необходимо решать задачибольшой размерности, при этом они относятся к NP -полным. На практикеоптимальные расписания с использованием таких методов построены дляпростых типов прикладных задач сравнительно небольшой размерности,причем в основном для двухпроцессорных систем. Поэтому обычноприменяются методы приближенной оптимизации, в частности,эвристические методы. Эвристические методы построения расписанийхарактеризуются тем, что они приспосабливаются как к информационнологической структуре ВП, так и к структурной организации МВС, иотносятся к классу приоритетного распределения.