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

Тема 3Исследование функционирования МВС с различнойорганизацией при решении сложных задач, моделируемыхвзвешенным орграфом, и анализ производительности взависимости от структуры МВС и стратегии решения задач.1.ВВЕДЕНИЕ .............................................................................................................................................................. 12.ОПРЕДЕЛЕНИЕ КРИТИЧЕСКОГО ПУТИ НА ГРАФЕ ЗАДАЧИ.............................................................. 23.ПОСТАНОВКА ЗАДАЧИ НАЗНАЧЕНИЯ...................................................................................................... 101.ВведениеЦикл лабораторных работ посвящен одному из основных разделовкурса, связанному с организацией параллельных вычислений вмногопроцессорных вычислительных системах (МВС).

Рассматриваемыесистемы относятся к классу "множественный поток команд, множественныйпоток данных" (МКМД). Основными компонентами современных МВСявляются:•решающее поле, состоящее из однородных или разнородныхпроцессоров, со своей локальной памятью (или без нее);•коммутационная сеть, позволяющая вести обмен даннымикак между процессорами, так и между процессорами и общей памятью;•общая память модульного типа;•иерархическая система управления, позволяющая реализоватьпараллелизм обработки данных на уровне независимых задач, независимыхветвей задач, команд и операций.В качестве параметров компонент системы используются:•решающее поле – число процессоров (в данном циклелабораторныхработрассматриваютсяМВСсодинаковымипроцессорами), характеризующихся относительным временем выполнениянезависимых ветвей задачи, определяемым быстродействием процессоров;•локальная память (ЛП) процессора - емкость (предполагается, чтобыстродействие ЛП таково, что не вносит задержку при обращении к нейпроцессора за данными, которые в ней находятся);•коммутационная сеть (КС) – определяется типом (общая шина илимультиплексная шина), числом шин, пропускной способностью при передачеданных(характеризуетсяотносительнымвременемзанятиясформированного канала: процессор - процессор, процессор - общая память,общая память – процессор);•общая память - число модулей памяти, быстродействие, косвенноотображаемое временем занятия канала процессор - общая память, общая память- процессор.Зат рат ы на управление в моделях не учит ывают ся.На вход такой МВС в общем случае может поступать набор независимыхвходных задач, каждая их которых имеет свой приоритет.В качестве модели задачи используется направленный граф, узлыкоторого отображают подзадачи.

Каждой подзадаче соответствует часть(ветвь) программы, начав выполнение которой процессор заканчивает еебез прерываний. Дуги графа моделируют связи по данным междусоответствующими подзадачами (ветвями программы).Узлы графа взвешиваются целыми числами, соответствующимивременам их выполнения в условных единицах (например, тактах) напроцессорах. Дуги графа взвешиваются тоже целыми числами,соответствующими временам занятия канала связи (шины) при передачеданных от одного узла графа к другому.В настоящем цикле лабораторных работ рассматриваются графы задачбез обратных связей, с различным соотношением времен выполнения узловграфа (tp) и передачи данных (tn). В соответствие с этим соотношениемразличают слабосвязанные задачи (tp » tn), среднесвязанные (tp ≈ tn),сильносвязанные (tp « tn).Каждая задача может характеризоваться максимальным временемвыполнения Тmax и минимальным временем Тmin.

Например, для задач, у которыхдля всех узлов tn = 0, Тmax вычисляется как сумма времен выполнения всех узловграфа (следует иметь в виду, что это справедливо, если все узлы графавыполняются на одном и том же процессоре), а Тmin - как сумма временвыполнения узлов графа, принадлежащих его критическому пути. Рассмотрималгоритм поиска критического пути графа, реализованный в программныхмоделях для данного цикла лабораторных работ.2.Определение критического пути на графе задачиСуть алгоритма заключается в определении минимальновозможного и максимально возможного времени начала выполненияузлов графа.

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

1) определяется минимальновозможное время начала выполнения каждого узла по формуле:sTmin i = max (T min j + t j+ T ij)(1)j=1где s - число узлов-предшественников i-го узла;Tmin i (j) - минимально возможное время начала выполнения i-го (j-го) узла;t j - время выполнения j -го узла;T ji - время передачи данных между узлами j и i, которому присваиваетсяодно из значений множества {0, τjiь 2τji }B зависимости от способа организациипамяти, где τji - время передачи данных между узлами j и i, задаваемое наисходном графе задачи.j=1j=stiTmin iTmax ir=1r=vРис. 1.

Пояснения к определению критических узловПри повторном анализе графа при проходе от конечной вершины кначальной определяется максимально возможное время начала выполнения узлапо формулеvTmax i = min (T max r - t i - T ir)(2)r=1где v - число узлов-последователей i-го узла;Tmax i (r) - максимально возможное время начала выполнения i-го (r-го) узла;t i - время выполнения i-ro узла;Tir - время передачи данных i-го узла узлу r, значение которомуприсваивается аналогично T ijПри этом для начальной вершины (вершин) Tmin i = 0, а для конечнойвершины минимально возможное время начала ее выполнения совпадает смаксимально возможным временем начала выполнения - Tmax i = Tmin i.i -й узел является критическим , если выполняется равенство Tmax i = Tmin iКритическим путем графа является множество последовательныхузлов, начинающихся входной вершиной и заканчивающихся выходнойвершиной, удовлетворяющих условию Tmax i = Tmin i, причем для каждой парыузлов принадлежащих КП соотношения (1) и (2) определяются соседнейвершиной в паре.Длина критического пути определяет минимальное возможноевремя выполнения графа задачи на МВС.Граф задачи при выполнении ее на МВС с различной организацией можетиметь различные критические пути вследствие изменения времени передачмежду узлами.

Последнее определяется способом организации памяти.Например, в МВС только с общей памятью (без локальной памяти процессоров)при определении критического пути время передачи данных от j-ro узла i-му иот i-го узла r-му необходимо удваивать. Двойной учет этого времени происходитпотому, что при передаче данных, во-первых, необходимо время τji, чтобыпередать данные j-ro узла в общую память, и, во-вторых, время τji чтобы забратьданные из общей памяти и передать i -му узлу, даже в случае выполнения i -гои j -го узлов в одном процессоре. В МВС с распределенной памятью каждыйпроцессор имеет локальную память, в которой могут храниться промежуточныерезультаты.

При этом если узлы j и i обрабатываются одним процессором, товремя обмена между ними считается равным 0 (то есть Tij = 0), если разными, товремя обмена между узлами равно τji. Выполнение этих дополнительных условийдолжно учитываться при решении задачи назначения.Рассмотрим пример поиска критического пути для графа задачи без учетавремен передач (рис. 2). Цифра внутри каждого кружка (узел графа) - номерузла, цифра над кружком - время выполнения узла tj. Дуги графа не взвешены,следовательно, T ji = T ir = 0.Основным допущением при поиске КП на графе являетсяследующее; граф задачи реализуется на системе с неограниченнымиресурсами, в данном случае на МВС с неограниченным числом процессоров.Рис.

2. Определение критического пути для графа задачи без учета передачПри движении по графу от начальной вершины к конечнойслева от узла записывается минимально возможное время началавыполнения этого узла Tmin i. Например, узел 6-может начать выполняться, когдавыполнятся 2 и 3 узлы. Тогда Tmin 6 = 7, так как минимально возможное времяначала выполнения 6-го узла является максимальным из времен окончания 2-го(Tmin 2 + t 2) и 3-го (Tmin 3 + t 3) узлов.При движении по графу назад от конечной вершины к первой, справа отузла записывается максимально возможное время начала выполнения этогоузла Tmax i . Например, для узла 2 по формуле (2) находимTmax 5 - t 2 =11-3=8;Tmax 6 - t 2 =7-3=8.Следовательно, Tmax 2 = min (Tmax 5 , Tmax 6) = 4.Таким образом, для графа, изображенного на рис.

2 , имеются двакритических пути 1; 2; 6; 9; 11; 12 и 1; 4; 10; 11; 12. При этом путь 1; 2; 9;11; 12 не является критическим, в частности, потому что для пары узлов 2 и 9соотношения (1) и (2) не определяются соседним в паре узлом. Например, Tmin 9определяется не узлом 2, а узлом 6, аналогично и Tmax 2 не определяется узлом 9 ,т.е.Tmin 9 ≠ Tmin 2 + t 2= 4+3 = 7;Tmax 2 ≠ Tmax 9 - t 2= 12-3 = 9.Следовательно, для данной прикладной задачи Tmin = 23, Тmах = 48.Рассмотрим теперь пример определения КП для графасреднесвязанной задачи с учетом передач (рис.

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