Постановка задачи назначения

14. Постановка задачи назначения Объект исследования – это ВС, которая в одном случае организована как система с общей памятью, а в другом как система с распределенной памятью, и прикладные задачи, которые поступают для решения на вход ВС. Для каждого случая задача назначения должна решаться с учетом характеристик выбранной системы и параметров задач. Предмет исследования – это способ размещения работ (например, вычислений, передач), необходимых при выполнении, поступивших на вход ВС прикладных задач, на выделенные ресурсы ВС. Выбор способа размещения работ получил название «решение задачи назначения». Этой проблеме посвящены лабораторные работы, которым посвящены методические указания. На рис. 14.1 представлены ресурсы ВС, участвующие в выполнении прикладных задач. P – процессор ЛП – локальная память процессора КС – коммутационная сеть МП – модуль оперативной памяти Рис. 14.1 Ресурсы вычислительной системы 70 Множество процессоров – решающее поле. Каждый процессор может обладать своей локальной памятью LM, являющейся элементом единой памяти системы, тогда система определяется как система с распределенной памятью. Либо все процессоры имеют общую память, организованную как автономная оперативная многомодульная память BM. Связь в такой системе между ее компонентами и внешним миром осуществляется с помощью коммутационной сети. Считается, что ВС однородная, т.е. все процессоры и модули памяти одинаковые, причѐм Б1=Б2, т.е. локальная память не вносит задержку в работу процессора. Это важное допущение! Оперативная память в ВС строится по модульному принципу, причѐм число модулей m не превышает число шин (при шинной структуре КС). В ВС с общей памятью (ОП) имеет место единое адресное пространство, обращение к которому осуществляется посредством выполнения команд записи считывания. ОП – это общий ресурс, разделяемый процессорами. В ВС с распределѐнной памятью, в которой имеет место распределѐнное адресное пространство, обмен данными осуществляется с помощью передачи сообщений, поэтому такие ВС иногда называют ВС с сетевой архитектурой. Прикладные задачи – внешняя среда по отношению к ВС. Способ поступления прикладных задач на вход ВС: 1. набор прикладных задач – на вход поступает от 1 до L задач, оформленных в виде пакета; 2. случайный поток задач – на вход поступает одна или несколько задач в случайные моменты времени. 14.1 Модели представления задач Наиболее распространена ярусно-параллельная форма (ЯПФ) представления задач. В этом случае прикладная задача представляется в виде направленного графа, в котором каждая вершина отображает некоторую часть (сегмент) задачи, а дуги – информационные связи между ними. Число ярусов определяет высоту графа, а максимальное число вершин яруса – ширину. Ширина графа влияет на выбор количества процессоров, необходимых для решения данной задачи. Каждая вершина графа взвешивается числом операций, необходимых для выполнения соответствующего сегмента задачи, а дуги объемом данных, передаваемых по соответствующей информационной связи. Это внешние параметры задачи инвариантные относительно вычислительной системы, на которой она будет выполняться. 71 Рис. 14.2 Пример ярусно-параллельной формы Внутренние параметры – это время выполнения сегмента задачи, соответствующего вершине графа, на данном типе процессора – tобр. узла и время передачи данных tпередачи по каналу связи с заданной пропускной способностью, соответствующего дуге графа. На рис. 14.2 изображен граф задачи, состоящий из 4 вершин, номер вершины внутри кружка, сверху кружка цифра, соответствующая времени выполнения данного сегмента задачи в условных единицах, цифра у дуги – время передачи данных в тех же условных единицах. По соотношению времени выполнения сегмента задачи и времени передачи данных задачи можно разделить на: 1. слабосвязные (tобр. узла >> tпередачи); 2. среднесвязные (tобр. узла  tпередачи); 3. сильносвязные (tобр. узла << tпередачи); Постановка задачи назначения в общем виде рассматривается как одна из двух задач оптимизации : 1. при заданных ресурсах ВС (число процессоров, число каналов передачи данных) распределить части прикладных задач по этим ресурсам (рассматривая заданный тип ВС (с общей или распределѐнной памятью) и определенный набор прикладных задач), так, чтобы время решения набора задач (Трешения)min; 2. при заданном (допустимом) времени решения набора задач (Tдоп) распределить части прикладных задач по ресурсам ВС (рассматривая заданный тип ВС (с общей или распределѐнной памятью) и 72 определенный набор прикладных задач) так, чтобы найти минимальные ресурсы, на которых возможно решение задач за допустимое время. Производные показатели: 1. Куск – коэффициент ускорения решения задачи Т К уск  1P , где Т – время решения задачи на одном процессоре, Т 1P nP ТnP – на n процессорах. 2. Кз – коэффициент загрузки оборудования Т обработки Кз  , Tобработки –время, в течении которого данное оборудование Т решения занято выполнением функций при решении задачи (набора задач), Tрешения общее время решения задачи (набора задач). – 14.2 Алгоритм поиска критического пути графа Для оценки минимально возможного времени решения задачи применяется алгоритм поиска критического пути, суть которого заключается в определении минимально возможного и максимально возможного времени начала выполнения узлов графа. При начальном проходе от начальной вершины графа к конечной определяется минимально возможное время начала выполнения каждого узла по формуле: Tmin i = max (Tmin j + tj + Tji) (1) j 1 s – число вершин-предшественников i-ой вершины; Tmin i (j) – минимально возможное время начала выполнения i-ой (j-ой ) вершины; tj – время выполнения j-ой вершины; Tji – время передачи данных между вершинами j и i, которому приписывается одно из значений множества {0, ji, 2ji} в зависимости от способа организации памяти, где ji – время передачи данных между вершинами j и i, задаваемое на исходном графе задачи. При повторном анализе графа при проходе от конечной вершины к начальной определяется максимально возможное время начала выполнения вершины по формуле: Tmin i = min (Tmax r – ti – Tir) (2) r 1 v – число вершин-последователей i-ой вершины; ti – максимально возможное начало выполнения i-ой (r-ой ) вершины; Tir – время передачи данных i-ой вершины вершине r, значение которому присваивается аналогично Tji. 73 При этом для начальной вершины (вершин) Tmin i = 0, а для конечной вершины минимально возможное время начала еѐ выполнения совпадает с максимально возможным временем начала выполнения – Tmax i = Tmin i Вершина является критической, если выполняется равенство: Tmax i = Tmin i Критическим путѐм графа является множество последовательных вершин, начинающихся входной вершиной и заканчивающихся выходной вершиной, у которых Tmax i = Tmin i, в котором для каждой пары вершин графа соотношения (1) и (2) определяются соседней вершиной в паре. Т.е. это такой путь, который имеет максимальное время выполнения среди всех путей графа задачи. И, следовательно, он определяет минимально возможное время выполнения всей задачи при неограниченных ресурсах вычислительной системы, на которой она выполняется. Пример. Определение критического пути. Допустим, каждой вершине графа рис. 14.3 поставлено в соответствие еѐ время выполнения на данном типе процессора в машинных тактах, указанное над вершиной. Тогда, по указанному выше алгоритму, определены минимально (слева от вершины) и максимально (справа от вершины) времена начала соответствующей вершины. 74 Рис. 14.3 Граф задачи Критический путь по определению будет: 1-2-6-9-11-12 Tmin = 23 мт (машинных тактов) - минимально возможное время решения задачи. N Tmax = T j = 48 (N – число вершин графа, т.е. Tmax – время решения j 1 задачи на одном процессоре). Допустим, что необходимо решить задачу за Tдоп =25мт. Для того, чтобы не делать полного перебора при выборе числа процессоров n, определим начальное его значение, необходимое для решения задачи за Tдоп (Tдоп  Tmin, иначе задачу невозможно решить за требуемое время): n = Tmax / Tдоп = 48 / 25  2 75 14.3 Применение стратегий назначения при решении задачи назначения Как назначить готовые к исполнению вершины графа задачи на процессоры? Например, это можно сделать на основе теории расписания, часто прибегая к эвристическим методам, позволяющим найти результат, близкий к оптимальному. Эти методы определяются следующими стратегиями выбора готовых к исполнению вершин и назначения их на свободные процессоры: 1. равновероятный выбор; 2. с максимальным временем исполнения узла; 3. с минимальным временем исполнения узла; 4. на основе принадлежности узла критическому пути. Для автоматического решения задачи назначения граф задачи представляется в виде таблицы связности размерностью NxN, в ячейки которой заносятся признаки связи соответствующих вершин. Будем считать, что на вход многопроцессорной вычислительной системы поступают задачи, относящиеся к классу слабосвязных. Тогда временем передачи данных можно пренебречь. Рассмотрим задачу назначения на основе принадлежности критическому пути, а в случае наличия нескольких готовых к исполнению вершин, не принадлежащих критическому пути, стратегии с минимальным временем выполнения вершины для графа задачи, представленного на рис. На рис. 14.4 представлена диаграмма Ганта, на которой изображены временные диаграммы работы двух процессоров. Рис. 14.4 Диаграмма Ганта В данном случае не уложились в Tдоп =25 мт, следовательно, необходим третий процессор. Изменение стратегии назначения, скорее всего, не поможет, т.к. один процессор занят полностью, а другой вынужден какоето время простаивать. Эмпирически доказано, что чем больше процессоров задействовано в решении задачи, тем больше простаивает каждый из них. Для рассматриваемого случая Tрешения=29 мт, следовательно, Куск = 48/29, Кз первого процессора равен 1 , а второго 19/29.