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

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. 14.4 Обеспечение надежности вычислений Время простоя процессоров можно использовать для контроля исправности оборудования за счет дублирования выполнения одних и тех же вершин на разных процессорах (во время их простоя). Для нашего примера Робн. ош. = 10/29 – это максимально возможное значение вероятности обнаружения ошибки при полном заполнении времени простоя второго процессора (10 мт) решением узлов, выполняемых первым процессором. Ошибка – событие, заключающееся в получении результата вычислений, отличного от правильного из-за сбоев и отказов оборудования. Сбой – самоустраняющийся отказ, приводящий к кратковременному нарушению работоспособности. Отказ – событие, заключающееся в постоянном нарушении работоспособного состояния объекта. Пример заполнения времени ожидания (простоя) процессоров для графа задачи, изображенного на рис. 14.5 копиями уже выполненных вершин (времена выполнения вершин приняты одинаковыми для простоты), представлен на этом же рисунке. Выполнение узла 1 1 Ожидание Процессор1 2 1 2 3` 5 1` 3 4 2` 3 4 Процессор2 5 Рис. 14.5 Пример заполнения времени простоя 77 4` Если нужно обнаруживать ошибки с вероятностью Робн. ош.=1, то требуется продублировать выполнением все вершины (дублируемые вершны должны выполняться на разных процессорах). Обнаруживать ошибки можно: А) с точностью до вершины, тогда граф задачи преобразуется так, как это показано на рис….., на котором показаны только 2 вершины из 5 соответствующие операции сравнения результатов; Б) с точностью до всей задачи, тогда граф задачи преобразуется так, как это показано на рис.14.6 , при этом необходимо сравнение результатов для всей задачи. 1 1 1 1 = 2 3 4 5 СО = СО 2 2 3 3 4 4 5 5 2 3 4 = 5 СО А) С точностью до узла Б) С точностью до задачи Копия задачи Копия задачи Рис. 14.6 Пример дублирования графа задачи В варианте А матрица связности 15 на 15. В варианте Б матрица связности 11 на 11. СО – сигнал ошибки. Помимо обнаружения ошибки, за счѐт ещѐ большего увеличения количества используемого оборудования, а возможно и увеличения времени решения задачи можно сделать и исправление ошибки. В этом случае задача представляется в виде графа рис.14.7. 78 Таблица истинности МО X1 X2 X3 Y 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 X1 X2 1 1 1 X3 МО 2 3 2 3 2 3 4 4 4 5 5 5 Y CO Рис. 14.7 Пример троирования графа задачи СО- сигнал ошибки МОмажоритарный орган. Y- результат (уже исправленный). Однако, следует помнить, что отказать может и исправляющая система, поэтому вычисления не могут быть абсолютно надѐжными. 14.5 Многозадачный режим функционирования Многопроцессорной Вычислительной Системы Допустим на вход МВС поступил набор (пакет) задач рис. 14.8 , который необходимо выполнить. Если эти задачи будут решаться последовательно (друг за другом), то тогда время решения набора задач равно сумме времѐн решения каждой задачи по отдельности. Трнз=Трз1+Трз2 79 Но при решении первой задачи могут появиться простои процессоров, которые можно заполнить решением второй задачи. Именно этим занимается так называемый планировщик многозадачного режима. 1 2 1 1` 2 2 3 3 1 2` 3 1 4` 3` 3 4 4 5` Задача1 Задача2 Набор задач Рис. 14.8 Набор из двух графов задач Задачи из набора могут быть как с равным приоритетом, так и с различным. Последовательность выбора вершины, готовой к исполнению, при выполнении набора задач определяется не только выбранной стратегией назначения, но и соответствующим критерием:  Тзад.наб. – заданное время решения набора задач.  Тзад. пр. задач- заданный приоритет задач. t  min 1  КП1  4 5 t  min 2 max T   min н T max н.з.  КП 2  t  i  i 1 t j j т.е. минимальное время выполнения набора задач равно длине наибольшего критического пути, а максимальное время выполнения набора задач равно сумме времени выполнения всех вершин всех задач в наборе. При поступлении в МВС, каждый набор задач снабжается паспортом. Паспорт набора задач содержит следующие данные:  количество задач;  приоритет задач;  количество необходимых ресурсов;  стратегия назначения. Каждая задача также имеет свой паспорт, в котором присутствует таблица связности, необходимые ресурсы и др. При решении задачи назначения, в зависимости от числа задач в наборе и их приоритетов, формируются очереди готовых к исполнению вершин 80 задач. В нашем случае получается 2 очереди выполнения вершин (с учѐтом приоритетов). Сначала рассматривается задача с высшим приоритетом. Существует два механизма: 1. Готовая исполнению вершина выбирает себе процессор из очереди свободных. 2. Освободившийся процессор выбирает себе следующую вершину из очереди готовых. Временная диаграмма примера (стратегия- максимальное время выполнения; задача 1 имеет высший приоритет) представлена на рис . Процессор1 1 3 1 Процессор2 4 1` 7 2 1 5 2` 3 К =1 заг2 5` 3` 2 Процессор3 Кзаг1=7/9 4 Кзаг3=4/9 4` 4 Время решения приоритетной 9 5 Т =9 р.нз. задачи Трз.приор.=7 Рис. 14.9 Диаграмма Ганта при многозадачном режиме Кзаг.мзр i≥ Кзаг.озр i Коэффициент загрузки в многозадачном режиме всегда больше или равен коэффициенту загрузки в однозадачном режиме. При выборе стратегии назначения для набора задач выбирается та, которая на конкретной задаче даѐт наибольший выигрыш. Например, анализируем стратегии минимального и максимального времени выполнения: -для каждой задачи определяется время по min и max стратегиям и из большего вычитается меньшее (определяется выигрыш). -для каждой задачи сравниваются эти выигрыши. Есть два режима распределения вершин (составления расписания):  Статический- распределение вершин осуществляется перед выполнением задачи.   Динамический- распределение вершин осуществляется по ходу выполнения задачи. 15. Системы коммутации Существует большое число разнообразных способов соединений компонентов вычислительных систем [1]. Тип организации таких соединений зависит не только от требовании к их пропускной способности, но и от таких количественных характеристик ВС как число процессоров, модулей памяти, каналов ввода вывода, а также и от особенностей структурной организации самих ВС. Например, существенным является то каким компонентам необходимо связываться друг с другом (процессор-процессор, процессорпамять). Так для систем класса ОКМД основной задачей параллельных вычислений на множестве процессоров является параллельная доставка данных (разных операндов) из общей памяти в локальную память каждого процессора. Чтобы связь между множеством процессоров и памятью была гибкой и достаточно быстродействующей, необходимо иметь большое число параллельно функционирующих линий связи со сложной системой их коммутации (СК). Как правило, для такого рода ВС прибегают к созданию специализированных СК на основе так называемых многоступенчатых коммутаторов, соответствующих их конкретному назначению. С одной стороны это приводит к значительному удорожанию ВС, а с другой стороны к обеспечению высокой пропускной способности СК. Для систем класса МКМД важным вопросом при построении СК является то, как организована память таких ВС, т.е. это организация с общей памятью или с распределѐнной памятью. Так для систем с общей памятью, обладающей физически единым адресным пространством, и являющейся разделяемым ресурсом ВС, СК строится, как правило, с использованием одной или нескольких шин и соответствующих коммутаторов, встроенных в процессоры и модули памяти, а сам обмен данными осуществляется с помощью выполнения команд «записи» «считывания».Для систем с распределѐнной памятью характерно то, что обмен данными осуществляется по схеме «обмен сообщениями» и, следовательно, существует огромное число видов построения СК, начиная от применения общей шины, одноступенчатых и многоступенчатых коммутаторов и заканчивая построением сложных сетей коммутации, таких, как например, гиперкуб большой размерности. Компоненты системы коммутации бывают 2-х типов: 1) активные (контроллеры шин, адаптеры, коммутаторы) 2) пассивные (магистрали, шины) Таким образом, рассматривая СК и абстрагируясь от типа ВС, можно сделать вывод о том, что основными компонентами СК являются активные компоненты. (Коммутаторы иногда являются пассивными). Коммутаторы могут быть реализованы с одной стороны как распределѐнные, например в системах с общей памятью, так и сосредоточенные, например в системах ОКМД, а с другой стороны как одноступенчатые, так и многоступенчатые. 82 Пропускную способность системы чаще всего определяют пассивные компоненты. 15.1 Шинные структуры Шинной структурой (ШС) называется такая организация системы коммутации, при которой для передачи данных между компонентами вычислительной системы используются одна или несколько общих (а в частном случае и индивидуальных) информационных магистралей. Самым простым случаем организации ШС является одношинная структура - общая шина, к которой подсоединены компоненты ВС, как это показано на рис. 15.1. P1 PBB P2 Pn П1 Пm Рис. 15.1 Структура «общая шина» В этой ВС - n процессоров P, m модулей памяти П и процессор вводавывода PВВ объединены общей шиной ОШ. Системы коммутации, использующие шинные структуры, могут применяться как для ВС с общей памятью, так и для ВС с распределѐнной памятью. Сами шины представляют собой пассивные элементы, а управлением передачей данных по шинам занимаются либо передающие и принимающие устройства компонент ВС, либо специализированное устройство управления шиной, называемое контроллером шины, при этом часть функций управления остаѐтся за передающими и принимающими устройствами (адаптеры шины). Основной трудностью при организации обмена данными между устройствами системы по одной общей магистрали является состязание за право использования общего ресурса - самой шины, которое приводит к возникновению конфликтов при одновременном запросе на передачу данных от нескольких устройств системы. Для разрешения конфликтов 83 используются такие приѐмы, как назначение каждому устройству уникального приоритета, постановка запросов в очередь с различными дисциплинами обслуживания, например. FIFO - "первый пришел, первый вышел", соединение устройств в цепь или в кольцо и, следовательно, физической фиксацией их взаимных приоритетов. Следует отметить однако, что возможна организация логического кольца при физическом подсоединении каждого устройства к общей шине. Как правило, информационная магистраль (шина) состоит из 3-х групп линий - линии управления, линии адреса (шина адреса) и линии данных (шина данных). При этом в большинстве случаев достаточно 4-х линий управления: линия запроса шины (ЗШ), линия занятости шины (зан. Ш), линия предоставления шины (ПШ) и линия готовности получателя (ГП). Число линий шины данных (ШД) и шины адреса (ША) определяется техническими характеристиками ВС: числом параллельно передаваемых разрядов информационного слова, размером адресного пространства памяти, числом процессоров и другими компонентами системы. На следующем рис. 15.2 представлена типичная схема организации системы коммутации "общая шина". P1 P2 Pn П1 PBB Пm Рис.15.2 Схема организации системы коммутации "общая шина" Иногда адреса и данные передаются по одной шине с разделением времени. В этом случае необходим специальный механизм их различения. 84 Например, вводится ещѐ одна линия управления. Функционирование системы коммутации "общая шина" заключается в том, что по заявкам от устройств, желающих передать данные тому или иному адресату, арбитр шины (специальное устройство, входящее в состав контроллера шины при централизованном еѐ управлении) в соответствии с принятой дисциплиной обслуживания при незанятой шине, предоставляет еѐ одному из отправителей данных. После этого отправитель должен установить связь с получателем, который распознаѐт свой адрес, установленный отправителем на шине адреса. В случае готовности получателя к приѐму данных (о чѐм он сообщает по линии готовности), отправитель выставляет данные на шине данных, которые и принимаются адресатом. После завершения обмена шина освобождается. Основным недостатком СК с общей шиной является то, что она является общим критическим ресурсом как с точки зрения пропускной способности, так и надѐжности СК. В случае, когда пропускной способности одной шины не хватает для организации обменов данными между компонентами ВС или требуется более высокая надѐжность системы коммутации, может быть введено ещѐ несколько шин. В этом случае каждая компонента должна иметь в своѐм составе коммутатор, позволяющий соединять передающее и принимающее устройства по одной из свободных шин системы (см. рис. ниже). 85 P1 PBB P2 Pn П1 Пm Рис.15.3 Схема организации системы с несколькими шинами В качестве примера можно привести организацию многошинной системы коммутации многопроцессорного вычислительного комплекса (МВК) "Эльбрус-2" (см. рис. ниже). Данный комплекс относится к классу МКМД с общей памятью. В его состав может входить до 10 центральных процессоров (P), до 4-х периферийных процессоров (PP) и 8 секций общей памяти (СП). 86 P1 P10 PP1 PP4 Рис.15.4 Многошинная система коммутации МВК "Эльбрус-2" Таким образом, каждый из 14 процессоров имеет в своѐм составе коммутатор на 8 направлений, а каждая секция памяти имеет коммутатор на 14 направлений. При этом система коммутации считается 8-мишинной с распределѐнным однокаскадным коммутатором. Иногда такую СК называют полносвязной. Как видно из представленных на рисунках структурных схем, рассматривались ВС с общей памятью. Для систем с распределѐнной памятью организация СК с шинной структурой с точки зрения построения физического канала принципиально не отличается от такой же СК для систем с общей памятью. Следует однако напомнить, что сам механизм обмена данными в системах с распределѐнной памятью основан на принципе обмена сообщениями, а в качестве компоненты ВС выступает процессор (или группа 87 процессоров) со своей локальной памятью, т.е. вычислительный модуль (ВМ). В качестве примера приведѐм два способа организации полносвязной СК для ВС с распределѐнной памятью: с распределѐнным коммутатором коммутация каждый с каждым (см. рис. ниже) Рис.15.5 Полносвязная СК с распределѐнным коммутатором (коммутация каждый с каждым) и центральным коммутатором (ЦК) - соединение типа "звезда" (см. рис. ниже). Рис.15.6 Полносвязная СК с центральным коммутатором (соединение типа "звезда") 88 Первый случай более надѐжен, т.к. отсутствует общий ресурс, а второй случай более простой, но менее надѐжен из-за присутствия общего ресурса - ЦК. Рассматривая шинные структуры, приведѐнные выше, можно сделать один главный вывод - при обеспечении высокой пропускной способности СК вычислительной системы с большим числом процессоров приходится вводить большое число коммутируемых линий связи и сложные коммутаторы, что резко усложняет и повышает стоимость ВС. Поэтому шинные структуры применяются в ВС с небольшим числом процессоров, обычно не более 16-ти. 15.2 Матричные структуры Системы коммутации матричных структур основаны на использовании множества распределенных одноступенчатых коммутаторов в ВС с высокой степенью распараллельности и с большим числом однородных процессоров. Исторически матричные структуры впервые были использованы в матричных процессорах, относящихся к классу ОКМД. Основное преимущество матричных структур – однородность элементов обработки и регулярность системы коммутации, что дает существенный экономический эффект при реализации матричных процессоров на кристалле. Применение матричных процессоров обычно связано с решением задач цифровой обработки сигналов и изображений и поэтому они рассматриваются как специализированные процессоры в составе мощной высокопроизводительной системы. Базовое соединение элементов процессорной матрицы происходит так, как это показано на рис. 15.7. Иногда такое соединение называют 2-мерный тор. Каждый узел данной матрицы представляет собой процессор со своей локальной памятью и коммутатором на 4 направления. Коммутатор может быть как встроенным в процессор, так и внешним по отношению к процессору и может быть реализован в виде специального связного процессора. В матричных структурах обмен данными между соседними процессорами происходит с большой скоростью, которая обуславливается однокаскадным их соединением. Однако, соединение между любыми двумя удалѐнными процессорами матрицы требует большего числа каскадов по каналу от источника к приѐмнику. В редких случаях, когда требуется высокая пропускная способность СК, применяется так называемая сильносвязная матрица процессоров с магистральным принципом обмена данными, которая изображена на рис. 15.9. Преимуществом, хотя и дорогостоящим, такой структуры является возможность организации обмена между любыми двумя процессорами, в том числе и в разных строках и столбцах, за один цикл магистрального обмена. 89 Рис 15.7 2-мерный тор. Структура элемента матрицы показана ниже, на рис. 15.8. ПР Локальная память магистраль для обмена данными с внешним миром и получения команд Коммутатор каналы для осуществления внутриматричного обмена Рис.15.8 Структура элемента матрицы. Как было отмечено выше, матричные структуры по своей сущности являются специализированными. Но ещѐ большая специализация достигается в систолических структурах, в которых соединение между процессорами выбираются исходя из особенностей параллельного представления конкретной прикладной задачи, для которой и проектируется данная система обработки данных. (Термин «систолический» заимствован у физиологов. Им обозначается ритмичное сокращение сердца, необходимое для нормальной циркуляции крови в организме животного). Узел систолической структуры, содержащий процессор, ведѐт циклическую обработку данных перед тем как 90 циклически же передать результат обработки одному или нескольким соседям в соответствии с программой решения заданной прикладной задачи. Рис.15.9 Магистральная матрица. Таким образом, матричные структуры, применяемые, как правило, в системах ОКМД, дают высокие показатели производительности на узком классе задач. Расширение этого класса требует усовершенствования матричных структур. Главной особенностью такого усовершенствования является их применение в ВС, строящихся по принципу МКМД. Например, российская многопроцессорная система МВС-1000 разработана как масштабируемый (легко расширяемый) массив процессорных узлов. Каждый узел содержит процессор с локальной памятью и коммуникационный процессор, имеющий 4 внешних канала (линка). Процессорные узлы связаны между собой по оригинальной схеме, сходной с топологией двумерного тора, представленной на рис. 15.10. Данная структура представляет собой модуль системы, состоящий из 16 узлов. При этом 4 угловых узла матрицы соединяются через линки по диагонали попарно. Оставшиеся 12 линков предназначаются для подсоединения внешних устройств – 4 угловых линка и 8 для соединения с себе подобными модулями Характерной особенностью такого соединения в структурном модуле 4х4 является то, что максимальная длина пути (число каскадов) от одного узла матрицы к другому равна трѐм. 91 для внешних связей для связи с аналогичной матрицей (расширение матрицы) Рис.15.10 Структура МВС-1000. В качестве примера матричной структуры можно также привести кластер МГУ, структура которого показана на следующем рис. На схеме показан вывод для расширения матрицы. В каждом узле – 2 процессора Pentium III с общей локальной памятью. Рис.15.11 Кластер МГУ. 15.3 Кубические структуры Кубические структуры предназначены для организации ВС с РП, состоящих из большого числа узлов. Они основаны на гиперкубах, организуемых либо в булевском, либо в евклидовом пространстве. В случае булевского пространства n-мерный куб образуется как декартово пространство кубов меньшей степени. Таким образом, гиперкуб nго порядка представляет собой два гиперкуба (n-1)-го порядка, соединенных одноименными вершинами. Рассмотрим вычислительную систему состоящую из большого числа вычислительных модулей (ВМ) (процессор со своей локальной памятью). На рис. 15. 12 показана условная схема ВС на примере гипер-куба 4 порядка. В 92 этой схеме ВМ располагаются в вершинах многомерного куба и соединяются с соседями ребрами этого куба. Для 4-х мерного куба ВС состоит из 16 ВМ (16 вершин), для 12 –и мерного куба из 4096 ВМ (4096 вершин). Соответственно, в первом случае из вершины исходит 4 ребра, во втором – 12 рѐбер. Очевидно, что К- мерный куб может включать 2 в степени К ВМ, а максимальный длины путь прохождения сообщений между двумя любыми ВМ составит К рѐбер. Рассмотрим более подробно принцип коммутации в схеме соединений типа гипер-куб. Каждый куб следующей размерности строится на основе двух кубов предыдущей размерности соединением двух одноимѐнных вершин куба предыдущей размерности. Таким образом, каждый раз увеличивая размерность куба на единицу, увеличивается число вершин в 2 раза. Поэтому такой куб называют «булев-К-куб». Булев-К-куб представляет собой очень удобную структуру по следующим причинам. Во-первых, если ВМ располагаются в вершинах 12 –куба, то ни один вычислительный модуль не отстаѐт более чем на 12 рѐбер куба (т.е. линий связи) ни от какого другого ВМ, что значительно облегчает задачу создания эффективных коммуникаций в системе. Гиперкубы: 0го порядка: 1 узел; 1-го порядка: 2 узла; 2-го порядка: 4 узла; 3-го порядка: 8 узла; 4-го порядка: 16 узлов; 0111 0000 и т.д. Рис. 15.12 Принцип образования К-куба 93 Во-вторых, структура соединений в К-кубе хорошо согласуется с двоичной логикой ЭВМ. Как было отмечено выше, каждый куб в К-кубе имеет два подкуба предыдущей размерности. Если их обозначить значениями булевой переменной 0 и 1, то в результате такого представления каждая вершина имеет единственный, отличный от других, двоичный адрес разрядности К. В-третьих, одно из ценных свойств К-куба состоит в том, что между любой парой ВМ есть сразу несколько с одинаковым числом рѐбер путей коммутации. Например, если мы имеем дело со структурой 12-куб, то каждая вершина имеет 12 разрядный адрес, первый разряд которого указывает какой из двух 11-кубов содержит данную вершину, второй разряд указывает на соответствующий 10-куб и т.д. до последнего разряда адреса. Этими двоичными адресами можно воспользоваться для того, чтобы направлять сообщение в сеть адресуясь к приѐмнику. Получив сообщение, маршрутизатор источника анализирует старший разряд адреса для определения подкуба и, если канал свободен, отправляет сообщение по этому каналу. Если канал занят, маршрутизатор анализирует следующий по старшинству разряд и так до тех пор пока не обнаруживается свободный канал. Так действуют все маршрутизаторы вершин куба по пути от источника к приѐмнику. СМ1- первая система, имеющая процессор кубической архитектуры 12-й 12 степени, состоящий из 4096 узлов (2 = 4096). Это система с распределенной памятью. Сколько степеней, столько должно быть и коммутационных выводов у каждого процессора. В этой машине впервые был использован router на 12 выходов. ВС такого типа уже имеет сетевую архитектуру. Одним из преимуществ такой схемы коммутации является простота адресации: каждому узлу соответствует определенный 12-разрядный адрес. Каждый разряд соответствует подкубу по старшинству. При передаче данных существует большое количество альтернативных путей. Вычислительный модуль системы показан на следующем рис. 15.13. Р Маршрутизатор ... 1 2 12 Рис.15.13 Вычислительный модуль системы СМ1. К кубическим структурам тесно примыкают многомерные торы (в одномерном случае это кольцевая структура, в двумерном – матрица, которые были рассмотрены выше). Торы образуются из n-мерных кубов 94 путѐм введения рѐбер между соответствующими вершинами граничных областей по некоторым или всем координатам, как это показано на рис. 15.14. Адресация происходит по координатам. Например, сначала по Y, потом по X и в конце по Z. X эти связи образуют тор Y Z Cray T3e/900 serial Number 6702 3-х мерный тор Рис.15.14 Трѐхмерный тор Используется принцип коммутации каналов. Обычно шина двунаправленная. Для того, чтобы уменьшить значение максимального числа каскадов, соединяющих любые два узла тора, используется так называемое соединения узлов с чередованием. (Если узлов много, то чередование через одного) Соединение узлов с чередованием Рис.15.15 Соединение с чередованием 15.4 Многоступенчатые коммутаторы При необходимости соединения относительно большого числа (до нескольких десятков) 2N процессоров друг с другом или N процессоров с N модулями памяти и требованием на снижение затрат на систему коммутации по сравнению с полносвязной одноступенчатой коммутацией, применяются многоступенчатые коммутаторы (МК) (чаще всего в ОКМД системах). Время передачи между двумя каждыми элементами ВС должно быть одинаковым. Поэтому число линий связи, соединяющих два элемента из двух множеств тоже должно быть одинаковым. Основной принцип их построения – создание сложного единого коммутатора с большим числом входов и выходов на основе соответствующим образом объединения простых стандартных коммутаторов. Как правило, МК строятся из коммутаторов 2х2 (рис. 15.16) с двумя входами и двумя выходами, соединяя один из выходов одного коммутатора с одним из входов другого коммутатора (так называемое соединение «точка-точка»). Таким образом, если необходимо построить коммутатор NхN (N входов и N выходов), то число каскадов (ступеней), двух множеств элементов по N элементов в каждом l  log 2 N . Число элементов в каскаде N/2. Таким образом, особенностью такого коммутатора является одинаковое время передачи данных между любой парой элементов ВС. Причѐм это время пропорционально числу каскадов МК. Обычно коммутаторы 2х2 имеют два состояния – прямое соединение одноимѐнных входов и выходов и их перекрѐстное соединение (рис. 15.16). Комутатор 2 на 2 Варианты настройки комутатора: - рзмножение Рис.15.16 Примеры соединений входов и выходов Состоянием коммутатора необходимо управлять, поэтому каждый из коммутаторов 2х2 имеет свою схему управления, в функции которой входит переключение состояния коммутатора в зависимости от заявок на соединение на каждый из его входов и арбитраж запросов двух входов, если необходимо их соединить с одним и тем же выходом (рис.15.17 ). 96 вход1 запрос выхода 1 занято/свободно Система управления комутатором вход2 Запрос на следующий вход занято/свободно запрос выхода 2 Запрос на следующий вход занято/свободно занято/свободно вход1 выход1 вход2 выход2 Рис.15.17 Коммутатор со схемой управления 15.5 Сеть Омега - Коммутатор Omega ILLIAC-IV Сеть Омега была разработана для применения в качестве многоступенчатого коммутатора в ВС матричного типа для параллельной доставки данных из внешней памяти в локальную память процессоров. Соединения входов и выходов в каждой ступени осуществляется по типу «полная тасовка». На рис. 15.8 представлен такой коммутатор 8х8. 000 000 001 001 010 011 010 011 100 100 101 101 110 110 111 111 1 . Комутационная сеть Omega ILLIAC-IV Рис.15.18 Схема коммутатора 8х8 Полная тасовка выполняется так. Первые четыре выхода каждой ступени соединяются с четырьмя верхними входами коммутаторов 2х2 следующей ступени (входы первой ступени соединяются таким же образом с выходами устройств источников запросов). Остальные четыре выхода 97 ступени соединяются с нижними входами следующей ступени. Таким образом, формируются каналы передачи данных от определѐнных источников к заданным приѐмникам. Для того чтобы реализовать на МК требуемое отображение входов на выходы, необходимо выполнить приведѐнный выше алгоритм одновременно для всех входов и выходов. При этом некоторые каналы могут быть пересекающимися. В этом случае схема управления коммутатора, в котором возник конфликт, по определѐнной заранее системе приоритетов предоставляет право на соединение одному из его входов или выходов. Например, высший приоритет назначается верхнему входу коммутатора. В этом случае второй запрос на соединение будет находиться в режиме ожидания освобождения коммутатора. Существует такой алгоритм управления состоянием коммутаторов. Допустим, что необходимо произвести коммутацию входа S= 101 (s1,s2,s3) с выходом D=100 (d1,d2,d3). Установим коммутатор первой ступени МК, с которым связан вход с номером 101, в состояние соединения этого входа на верхний выход, если d1=0 и на нижний, если d1=1. На следующей ступени коммутации продолжаем действовать по тому же правилу. Вход коммутируем на верхний выход, т.к. d2=0. На последней ступени, в соответствии с тем, что d3=0, коммутатор устанавливает связь с верхним выходом. Следовательно, произошло соединение входа 101 с выходом 100. Коммутационная сеть Омега относится к системам блокирующего типа, т.е. не всегда можно соединить все восемь входов с восьмью выходами, поскольку необходимо ждать пока нужные коммутаторы разблокируются. Линии связи могут быть двунаправленными, тогда для коммутации выходов со входами используется тот же алгоритм.. 15.6 Коммутационная сеть flip (сеть перестановок) Коммутационная сеть Flip применяется в машине баз данных STARAN. Принцип соединения – полная тасовка. 000 000 001 001 010 011 010 011 100 100 101 101 110 110 111 111 F= 1 Комутационная сеть flip Рис.15.19 Пример настройки сети перестановок 98 Особенность в том, что сразу настраивается весь «столбец», а не отдельный коммутатор. Состоит из коммутаторов 2 на 2, настраивающихся по следующему принципу: f=0 где f управляющий сигнал f=1 Всего возможно 8 перестановок, но авторам коммутационной сети flip это показалось недостаточным. Был введѐн дополнительный управляющий сигнал S (Shift), образующий из столбца циклический регистр. Получается ещѐ 8 комбинаций. Итого получилось 64 различных комбинации. Недостатком системы является то, что эта система блокирующего типа. 16. ВС на основе векторных процессоров Как было отмечено выше, ВС на основе векторных процессоров относятся к классу ОКМД систем. Главный принцип вычислений в такой системе состоит в выполнении некоторой элементарной операции или комбинации из нескольких элементарных операций, которые должны многократно применяться к разным данным. Такие операции отображают векторные команды, которые входят в состав системы команд векторного процессора и операндами которых являются вектора. Таким образом, модель вычислений векторного процессора – одиночная операция выполняется над большим блоком данных. Обычное проявление этой вычислительной модели в исходной программе – циклы на элементах массива, в которых значения, вырабатываемые на одной итерации цикла, не используются на другой итерации цикла. Основой выполнения векторной команды является конвейер операций. Так как при выполнении векторной команды одна и та же операция применяется ко всем элементам вектора (или чаще всего к соответствующим элементам пары векторов), для настройки конвейера на выполнение конкретной операции может потребоваться некоторое установочное время, однако затем операнды могут поступать в конвейер с максимальной скоростью, допускаемой возможностями памяти [7]. Обычно такие ВС называют супер-ЭВМ; минимальная конфигурация – один векторный и один скалярный процессор. Обычно это системы с общей памятью. СПр – скалярный процессор ВПр – векторный процессор БПА – блок подготовки адресов ЦУУ – центральное УУ ОП – общая память CR – набор скалярных регистров BR – набор векторных регистров Система команд: 1. скалярные команды; 2. векторные команды. Минимальное число векторных регистров – 8; длина слова – 64 разряда. Возможно выполнение операций над полусловами (32 разряда) и двойными словами (128 разрядов). Обработкой более мелких единиц информации (байты и т.д.) занимается скалярный процессор. 100 Длина одного векторного регистра – 6464 разряда (64 операнда, длина каждого операнда – слово). Изначально векторные регистры были однопортовыми, потом им на смену пришли двупортовые – регистры, из которых можно считывать загруженные данные, не дожидаясь окончания загрузки (записи) всего регистра! Обратное недопустимо! Особенность: можно одной векторной командой загрузить векторный регистр, одной командой суммировать содержимое регистров и одной командой сохранить результат в памяти, т.е. C := A + B – за 4 команды! Принцип зацепления. Если для каждой операции выделить автономное специализированное исполнительное устройство (ИУ), использующее принцип конвейера операций, и если последовательность векторных команд такова, что результат q-й команды используется в (q+1)-й, то этот результат можно подавать непосредственно с выхода ИУ, выделенного для q-й операции, на вход ИУ, выделенного для (q+1)-й операции. Под конвейером операций здесь понимается следующее: если стадию Е выполнения операций, время исполнения которой больше одного МТ, разбить на этапы, равные одному МТ, и выделить на исполнение каждого этапа автономный функциональный узел, то эту стадию можно конвейеризировать. Таким образом, если выполняется конвейер операций умножения, то первый результат умножения двух элементов векторов появится, например, через 4 МТ (это время называется латентным периодом), а последующие результаты будут появляться через 1 МТ! Пример. Z := AB + C Пусть размерность векторов – 64 элемента. Тогда первый результат (z1) будет получен через 6 тактов, а все последующие – с интервалом в один такт. Вся операция над векторами будет выполнена за (6 + 163) тактов! Отметим, что такой выигрыш в производительности на векторных процессорах можно получить только на операциях над векторами; скалярные данные и вектора малых размерностей выгоднее обрабатывать на скалярных процессорах. Принципы скалярной обработки. Командное слово i считывается из памяти команд в регистр команд скалярного процессора. В адресном поле А командного слова содержится указание на данные j. Одновременно со считыванием данных j из памяти данных, считываются данные k из регистра, заданного в поле R командного слова i. Над данными j и k а АЛУ выполняется операция, задаваемая в поле КОП командного слова. Результаты операции заносятся в регистр R. В этом примере данные j, представляющие собой единичные элементы обработки и размещѐнные в 101 памяти независимо друг от друга, называются скалярными. Команды, инициирующие операции над скалярными данными, называются скалярными командами. Процессор, выполняющий скалярные команды, называется скалярным процессором. Схема скалярной обработки приведена на рисунке ниже. Рис.16.1 Схема скалярной обработки Принципы векторной обработки. Командное слово i считывается из памяти команд в регистр команд векторного процессора. Отличительной особенностью векторного процессора ос скалярного процессора является наличие в его системе команд векторных команд и аппаратных средств поддержки их реализации. Очевидно, что векторные команды предназначены для выполнения операций над векторными данными, которые представляют собой еэлементные наборы чисел, размещѐнные в памяти с определѐнной регулярностью и над которыми должны выполняться одни и те же действия. Векторные данные имеют особо важное значение для реализации высокоскоростной числовой обработки, т.к. с помощью одной команды можно указать операцию над множеством данных, а в процессоре приводить в действие различные механизмы параллельной обработки. Указание командным словом векторных данных в векторных процессорах осуществляется по-разному, но при этом прямо или косвенно должны быть заданы: 1. адрес А базы векторных данных; 2. значение приращения адреса d между элементами векторных данных; 3. число элементов и длина вектора е. 102 Для записи считываемых из памяти векторных данных процессор должен иметь регистры, ѐмкостью достаточной для хранения данных вектора длиной е. Эти регистры называются векторными. Следует обратить внимание на то, что устройства, ведущие непосредственную обработку данных (АЛУ), могут быть в СПр и ВПр одинаковыми. Таким образом, при векторной обработке предварительные действия перед непосредственным выполнением операций требуют большого объѐма работ, связаны с начальной установкой различных регистров (длина вектора – е, смещение d, которое может быть переменным для элементов вектора). Рис.16.2 Схема векторной обработки Однако эти предварительные действия не предваряют выполнения всего цикла, как это происходит при скалярной обработке, и рассредоточены в стадиях выполнения векторных команд. Преимуществом же векторной обработки перед скалярной является то, что для выполнения одной и той же операции над е элементами вектора выбирается из памяти векторная команда один раз. Следовательно, именно этот фактор даѐт возможность одной командой инициировать е-кратное выполнение одной операции над различными данными. Таким образом, появляется принципиальная возможность эффективного использования конвейерных исполнительных устройств процессора. 103 1. 2. 3. 4. Производительность ВПр возможно увеличить за счѐт: введения многомодульной памяти с возможностью параллельной выборки операндов; применение конвейерных исполнительных устройств (конвейер операций); введение нескольких конвейерных исполнительных устройств (либо одинаковых, либо специализированных для отдельных операций); организация принципа зацепления операций. 17. ВС класса ОКМД на основе матричных процессоров Исторически понятие «матричный процессор» возникло при создании многопроцессорной вычислительной системы, предназначенной для решения задач, в которых присутствует большая доля операций над матрицами. При этом структура физических связей между процессорами (т.к. эти процессоры первоначально были достаточно простыми, они получили название «процессорный элемент») не обязательно соответствует матричным соединениям. В настоящее время матричные процессоры (МП) применяются для решения таких задач как цифровая обработка сигналов, обработка изображений, ядерной физики и т. д. В качестве примера можно привести задачу обработки изображений в реальном масштабе времени с алгоритмами опознавания объекта и проверки соответствия его геометрических и физических свойств заранее заданным характеристикам. Такая прикладная задача обычно в качестве составляющей части включает анализ кадра изображения, например, состоящего из 1024х1024 пикселей, со скоростью 1000 кадров в секунду. Это означает, что за секунду необходимо обработать около миллиарда пикселей изображения. Если, например, анализ каждого пикселя требует 10 операций, то суммарное быстродействие системы должно превышать 10 миллиардов операций в секунду. Так как любая задача содержит, как правило, и другие части с меньшим параллелизмом, но требующих тоже высокого быстродействия, то МП обычно является составной частью (приставкой) мощной системы обработки данных. Структура такой СОД содержит обычно следующие составляющие. Главная вычислительная машина (ГВМ). Интерфейсная система, связывающая ГВМ с МП. Коммутационная система, связывающая компоненты МП друг с другом и периферийными устройствами. Матричный процессор, обычно состоящий из большого числа ПЭ, например 8х8. ВС на основе матричных процессоров строится как система с распределенной памятью (каждый ПЭ имеет локальную память) в составе СОД с общей памятью, структура которой представлена на рис. 17.1.Условные обозначения на этом рисунке. 1 – Мощная коммутационная сеть с буферами и коммутаторами. 2 – Матрица процессорных элементов (матричный процессор). Все элементы работают синхронно – это ОКМД в чистом виде. Обычно матричный процессор состоит из элементов с сокращѐнным набором команд 105 главная вычислительная машина обычно это супер ЭВМ 1 Контроллер ввода-вывода Коммутор (комутационная сеть) Множественный поток данных (МД) Программа управления задачей Одиночный поток команд (ОК) 2 Центральное устройство управления Рис. 17.1 Структурная схема ВС на основе матричного процессора . 1. 2. 3. 4. Функции ЦУУ (Центрального Устройства Управления): Дешифрация команды и еѐ рассылка всем процессорным элементам матрицы. Все ПЭ выполняют одну и ту же команду со своими данными. Генерация адресов и данных и передача их процессорным элементам. Особенность матричных процессоров – т.к. на все процессорные элементы поступает одна команда, то и адрес, по которому надо записать (считать) данные тоже один. Поэтому при выполнении команды, связанной с доступом к памяти, в этой команде указывается только один адрес, но каждый ПЭ, обладая индексным регистром, модифицирует его и обращается к своей локальной памяти по своему адресу. Данные и программа поступают в локальную память каждого процессора. Но программа одна, поэтому если она большая, то она распределяется между локальными памятями процессорных элементов. 106 Центральное управляющее устройство обеспечивает считывание команд из локальной памяти процессорных элементов в нужном порядке. 5. Организация связи между процессорными элементами и ПЭ с внешней памятью системы.. 6. Приѐм и обработка сигналов прерываний от ПЭ, устройств вводавывода и ГВМ. Связь между ПЭ друг с другом осуществляется синхронно через сеть связи (матрица), используя механизмы коммутации каналов. Так, если i-му ПЭ нужны данные, хранящиеся в памяти j-го ПЭ, то необходимо сначала проложить маршрут (скоммутировать канал) между ними, а затем передать данные. Очевидно, что для организации параллельных вычислений на множестве ПЭ, одновременно должно коммутироваться множество каналов, что должно быть отражено в самой прикладной программе. Именно это является одной из основных трудностей параллельного программирования для ВС, построенных на основе матричных процессоров. Основной же трудностью организации связи между ПЭ и внешней памятью, является параллельная доставка в локальные памяти множества ПЭ различных данных. Имеет место проблема условных переходов: пока одна ветвь программы работает, процессоры другой ветви стоят. Получается, что если программа богата разветвлениями, то часть процессорных элементов постоянно простаивает. 17.1 Структурная схема ILLIAC- IV Б – буферы В6500 –вычислительная машина, на которой функционирует операционная система, транслятор (подготовка программного кода, который будет исполняться на данной ВС). ЦУ – центральное устройство управления (своѐ в каждом процессоре). КВВ – контроллер ввода-вывода. Ком – коммутаторы. Оказалось что магистраль (для подкачки операндов) оказалась настолько узким местом, что использовался только один (!) матричный процессор. Поэтому реально выпускали систему с одним матричным процессором (8 на 8). 107 8 на 8 8 на 8 ЦУ ЦУ 8 на 8 8 на 8 ЦУ ЦУ Магистраль 1024 бита (16*64) Ком КВВ 2*256 48 Б 2*256 HDD Б В6500 Структурная схема ILLIAC - IV Пример: перемножение матрицы X и Y размером 4*4, результат в матрицу Z. Реализация на ILLIAC-IV. Каждый процессорный элемент имеет свои АЛУ и регистры. Пусть А и Врегистры под операнды, а S – регистр для хранения промежуточных результатов. Из матрицы 8*8 нам достаточно 4, т.е. возьмѐм столбец процессоров. Распределение памяти для хранения элементов этих матриц в локальной памяти процессорных элементов представлено в таблице. Используются следующие обозначения - ПЭ1, ПЭ2, ПЭ3, ПЭ4- 4 процессорных элемента матрицы процессоров, к – номер ячейки локальной памяти. Следует обратить внимание, что графически матрицы представлены по столбцам, а логически по строкам. пэ \ к ПЭ1 ПЭ2 ПЭ3 ПЭ4 11 х11 x12 x13 x14 X 12 13 14 х21 х31 х41 x22 x32 x42 x23 x33 x43 x24 x34 x44 Y 21 22 23 24 y11 y21 y31 y41 y12 y22 y32 y42 y13 y23 y33 y43 y14 y24 y34 y44 108 31 z11 z12 z13 z14 Z 32 33 z21 z31 z22 z32 z23 z33 z24 z34 34 z41 z42 z43 z44 Замечание: размещение элементов матрицы в памяти – отдельная проблема, которая решается отдельно для каждой задачи. Программа, реализующая рассматриваемый алгоритм, может быть описана следующим способом: Организуется внешний цикл i от 1 до 4 (по числу строк матрицы Х) и внутренний цикл j от 1 до 4 (по числу строк матрицы).  i = 1 первая строка матрицы Х передаѐтся в ЦУУ (все ПЭ выполняют одну и туже команду, в результате чего содержимое ячеек с номером к=11 оказывается в ЦУУ(т.е. х11, х12, х13, х14)).    j = 1 из ЦУУ значение х11 передаѐтся в А-регистры всех ПЭ.  третья команда. Все ПЭ выполняют команду загрузки из своей ЛП в регистр В содержимого ячейки к =21. Таким образом, в В - регистрах четырѐх ПЭ оказываются соответственно у11, у12, у13, у14.   Перемножить содержимого регистров А и В на всех ПЭ.  Прибавление результатов умножения к содержимому S-регистров (у каждого процессора свой регистр S, т.е. адреса регистров одинаковые, но находятся они в разных процессорах).    ……….  После завершения внутреннего цикла в регистрах S всех ПЭ оказывается значение элементов первой строки результирующей матрицы z11, z12, z13, z14. Эти значения переписываются в ЛП в ячейки с номером к =31.   Изменяя значение i, запоминаются последовательно все строки матрицы Z, значение каждого элемента, который высчитывается по формуле: 4 Z  x *y ij  il lj l 1 Заметим, что параллельное выполнение алгоритма возможно в том случае, если элементы матриц пересылаются из различных ПЭ в ЦУУ параллельно, а сами элементы строк матриц размещены в ЛП процессорных элементов в ячейках памяти с одинаковыми адресами. При выполнении различных операций с матрицами задача размещения их элементов в памяти является довольно сложной. Для облегчения этой задачи в ряде МП используется специальный механизм индексации адресов локальной памяти в каждом ПЭ. Рассмотренный простой пример раскрывает возможность параллельной работы ПЭ, организованной в соответствии функционирования ВС типа ОКМД, не затрагивая вопросы обмена данными между ПЭ. Однако ту же задачу на том же матричном процессоре можно реализовать таким образом, что одни ПЭ выполняют операции умножения, другие и умножение и сложение. В этом случае обмен между ПЭ неизбежен. Таким образом, составляя параллельный алгоритм и его программную реализацию на данном типе ВС, необходимо оценить различные варианты и выбрать тот, который даѐт наименьшее время выполнения данной прикладной задачи. 109 17.2 Нисходящее проектирование матричных процессоров Как было отмечено выше, МП представляет собой специализированную приставку к ВС высокой производительности. Следовательно, должен создаваться как вычислитель, эффективно выполняющий узкий класс заранее известных прикладных задач. Основные требования, которые предъявляют к МП при его проектировании следующие: 1. МП представляет собой регулярный массив ПЭ, выполняющих на протяжении каждого машинного такта одинаковые вычислительные операции с пересылкой результатов вычислений своим соседям. 2. Соединительные линии между ПЭ должны быть короткими. 3. ПЭ должны эффективно выполнять основные (базовые) операции, характерные для заданного класса прикладных задач. 4. Должно быть установлено оптимальное соотношение между ALU процессорного элемента и пропускной способностью памяти. 5. Наличие соответствующего языка параллельного программирования. Таким образом, если задана прикладная задача и поставлена цель создания МП, эффективно его реализующего, необходимо сначала разработать параллельный алгоритм, ориентированный на реализацию с использованием МП, а затем решить проблему формализованного перехода от описания алгоритма к структуре МП. При этом описание параллельного алгоритма должно быть с одной стороны таким, чтобы было просто для понимания пользователями, а с другой стороны было бы исходным материалом для системы автоматизированного проектирования , которая осуществляет компиляцию в эффективную структуру процессорной матрицы на СБИС. На рис. 17.2 представлена схема так называемого нисходящего проектирования процессорной матрицы, которое начинается с формализованного описания алгоритма с учѐтом присущих ему свойств рекурсии и параллелизма и заканчивается описанием аппаратной реализации конфигурации СБИС. Нисходящее проектирование означает разбиение процесса проектирования на этапы с помощью перехода от описания алгоритма к структуре матрицы. Целевая функция: 1. Определение процессорного элемента, т.е. определение состава команд и процесса обработки (последовательный или параллельный). 2. Выбор такой топологии, которая позволила бы для данной конкретной задачи минимизировать число линий связи, задействованных в решении этой задачи. 110 Схема процесса нисходящего проектирования матричного процессора структурно (льное - Функциональный компилятор Функциональное представление ) ( алгоритм архитектураописанифункециона ) (4) (1) задачи Взаимосвязи ПЭ (5) (2) Сам процессорный элемент (6) Уровень побитной обработки (3) Параллельный алгоритм Выделение базовых операций Булева функция выполнения каждой операции (9) Уровень топологических ячеек (окончательный вариант топологии, которая будет выращена на кристале) (8) Топологический рисунок, включая процессорный элемент Кремниевый компилятор (7) Система топологических связей на пластине Система топологических связей Рис.17.2 Схема нисходящего проектирования матричного процессора Распишем алгоритм нисходящего проектирования матричных процессоров более подробно: Этап 1. Есть некоторое функциональное представление задачи (Завершается построение алгоритма). Шаг1. Представление алгоритма в параллельном виде. (В основном выполняется вручную). Шаг2. Выделение базовых операций (этот шаг и все следующие в основном выполняются автоматически). Шаг3. Булевы функции для каждой из базовых операций. 111 Этап2. Функциональный компилятор осуществляет отображение исходного алгоритма в структурно-функциональное описание процессорной матрицы. Т.е. создаѐтся архитектура процессорной матрицы. Шаг4. Взаимосвязи процессорных элементов. Связи обычно задаются жѐстко, т.к. конечный продукт – это приставка к более сложной ВС, которая обычно выполняет какую-нибудь определѐнную функцию, например цифровую обработку видео сигнала. Шаг5. Сам процессорный элемент. Шаг6. Уровень побитной обработки данных (последовательной или параллельной). Этап3. Кремниевый компилятор отображает структурнофункциональное описание в топологию СБИС. Шаг7. Система топологических связей на пластине. Шаг8. Топологический рисунок на пластине (включая процессорные элементы). Шаг9. Уровень топологических ячеек. Представляет собой заключительный вариант топологии, которая будет выращена на кристалле. Свойства полученной структуры: 1. Короткие линии связи между процессорными элементами, что позволяет повысить пропускную способность. 2. Регулярность самой структуры (одинаковые процессорные элементы и линии связи). Это позволяет увеличить плотность упаковки на кристалле и упростить его производство. 3. Высокая степень распараллеливания вычислений. Факторы, на которые при разработке матричного процессора надо обращать особое внимание:   Разработчик должен обеспечить быстрое выполнение базовых функций – это его основная задача.   Нужно учитывать принцип конвейеризации. Каждый процессорный элемент должен совершать операции в конвейерном режиме.   Нужно выбрать оптимальное соотношение между производительностью процессора и пропускной способностью памяти.   Должны создаваться специальные языки параллельного программирования, ориентированные на матричные процессоры. Пример: машина ПС2000 (создана для управления атомными электростанциями). (см. рис. 17.3) 112 1 8 1 8 УУ Дополнительный быстрый канал КВВ УК Контроллер Внешняя память Рис.17.3 Структурная схем ПС-2000 По сути – это матричная система. Идеологически система строится как матрица 8 на 8, но процессорные элементы здесь гораздо мощнее, чем в ILLIAC-IV. Конструктивно – это совокупность линеек из восьми процессорных элементов. Может использоваться от одной до восьми линеек. Линейки процессорных элементов соединяются специальным быстрым каналом связи. Каждый процессор имеет свою локальную память. Особенности: 1. Одна из первых в мире масштабируемых систем. 2. В устройстве управления (УУ) впервые применено ПЗУ базовых микрокоманд и загружаемая память микрокоманд. т.е. система имеет возможность перепрограммирования для выполнения другой совокупности микрокоманд. Замечание: в системах, называемых «адаптивными» адаптация чаще всего происходит именно так. 3. УК – управляющий комплекс, основная функция – подготовка задач для реализации в матричной системе и еѐ мониторинг. Пример: СМ-1 (connection machine) фирмы thinking machines. В основе лежит гиперкуб двенадцатой степени (4096 узлов). Система строилась для обработки трѐхмерных изображений. Конструктивно выполнена из 8 подкубов. Каждый узел состоит из 16 процессорных элементов. Каждый процессорный элемент может работать автономно. Каждый процессорный элемент имеет одно одноразрядное АЛУ, которое может выполнять всего 4 операции и 7 одноразрядных регистров. Каждый процессор обрабатывает одну точку изображения. 113 память (16кбит) память (16кбит) ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ ПЭ Router на 12 связей память (16кбит) память (16кбит) Рис.17.4 Схема узла СМ-1 Рис. 17.5 Структурная схема СМ-1 ГУМ – главная управляющая машина ПЭ – процессорные элементы, 64К штук, соединены гиперкубом ЛП – локальная память, 4К БК – быстрые коммуникации Т – терминал, через который оператор управляет ВС 114 17.3 Оценка эффективности ВС на основе матричных процессоров Синхронная параллельная обработка элементов массивов может выполняться на матричных процессорах типа ILLIAC-4 или векторных процессорах типа CRAY или CYBER-205 [6]. Системы типа ILLIAC-4 в своѐ время получили распространение, и они действительно давали очень высокое быстродействие на определѐнном классе задач, например, быстрого преобразования Фурье и задач математической физики. С другой стороны, для многих задач применение процессоров такого типа не приносит требуемого эффекта, хотя задачи хорошо распараллеливаются. Для них выгодно применять векторные процессоры. Поясним это на примере. Обозначим через р число ПЭ в системе типа ILLIAC-4, а через ТР – время, необходимое для выполнения вычислений при использовании р процессоров. При этом под ТР будем понимать не физическое время, которое аналитически определить трудно, а число "шагов вычисления". Если последовательность вычислений представить в виде дерева, то шаг вычислений будет соответствовать ярусу дерева. Среднее ускорение за счет применения р процессорных элементов определим из соотношения: T SP = 1 – среднее ускорение за счет применения р ПЭ T P EP = SP P – степень полноты загрузки р ПЭ. Определим эффективность применения такого типа процессоров на примере перемножения матриц. Число параллельных операций, выполняемых при перемножении векторов, равно числу процессорных элементов р, которые могут быть задействованы при вычислении вектора.  NC =  n  – число шагов необходимое для вычисления вектора P  результата, состоящего из n элементов; [x] – ближайшее целое, большее х. NO = [log2n] + 1 – число операций сложения элементов вектора, полученного в результате умножения двух векторов, при условии, что число ПЭ достаточно для проведения вычислений (пересылки между ПЭ и другие вспомогательные операции не учитываются). Определим ускорение вычислений произведения двух матриц размерности ln и nq с использованием векторных операций и параллельного вычисления сумм элементов векторов для 64 процессоров. Пусть n = q = l = 64. На однопроцессорной машине для вычисления двух матриц надо выполнить 2lqn операций. На параллельной машине с p процессорами надо выполнить lq[n/p] векторных умножений и lq([log2n] + 1) сложений (при условии n  p). Ускорение при выполнении вычислений определяется соотношением: 115 2lpq SP = n lq P  log 2  n1  S64 ~ 18  19 E64 ~ 0,3 Для p = 64 и n = 64 Таким образом, даже в одном из самых благоприятных для системы случаев производительность 64 процессорных элементов оказалось равной только 19. Надо отметить, что процессорные элементы ILLIAC-4 достаточно дорогие, поскольку выполняют некоторые функции устройств управления и имеют собственную относительно большую память. Вообще же даже для наиболее хороших задач ситуация оказывается далеко не такой благоприятной, как в этом примере. В результате анализа некоторого числа задач была получена статистика, показанная в таблице. № группы программ 1 2 3 4 Процент векторных Процент скалярных операций Не выполняемых параллельно 4 8 9 11 операций Выполняемых параллельно 27 18 3 69 92 73 86 Операции, показанные в столбце 3, которые можно выполнить параллельно, в большинства случаев разнородные. Например, сложение и умножение на матричном процессоре могут быть выполнены только последовательно (не могут быть совмещены по времени). Процент скалярных операций определяется суммой столбцов 2 и 3 таблицы. Для группы задач: №1 №2 №3 №4 1  31 % 1  8 % 1  27 % 1  14 % S64  3 S64  11 S64  3,5 S64  6,1 E64  0,05 E64  0,2 E64  0,05 E64  0,09 Отсюда видно, какой вес в снижении производительности матричных процессоров играет даже относительно небольшой процент скалярных операций. Указанные свойства вычислительных систем типа ILLIAC-4 позволяют рассматривать их как проблемно-ориентированные процессоры, показывающие высокую производительность при решении ряда важных задач статистической обработки и математической физики. Большое внимание в последнее время уделяется векторным процессорам. Одна из их особенностей – введение в процессор векторных команд. Векторные команды и векторное задание операндов позволяют 116 эффективно организовать магистральную обработку данных и легко рассчитывать адреса элементов вектора в процессе выполнения векторной команды. Использование векторной команды вместо циклического выполнения скалярных команд резко сокращает число обращений к оперативной памяти за командами и экономит время на обработку команд. Интересным является векторный процессор BSP (Burroughs Scientific Processor) с быстродействием до 500 млн. операций, с плавающей запятой в секунду. Процессор BSP рассматривается как векторный процессор, расширяющий возможности высокопроизводительных вычислительных систем B7800/B7700. В нем имеется 16 процессорных элементов, которые работают под общим управлением, но связаны с общей для всех процессорных элементов памятью с параллельным доступом, кроме этого, есть мощный процессор для обработки скалярных команд. Параллельная обработка скалярных величин резко повышает эффективность распараллеливания. Процессор для скалярных вычислений может обрабатывать параллельно 3 операции и 16 процессорных элементов обрабатывают векторные команды. Используя данные таблицы, получим следующие оценки эффективности выполнения программ для группы задач: №1 №2 №3 №4 S19 S19 S19 S19 6  7,6  5,3  3,9 E19  0,32 E19  0,4 E19  0,28 E19  0,21 Т.е. для этих задач эффективность использования аппаратуры на векторных процессорах типа BSP или CRAY значительно выше, чем на системах типа ILLIAC-4. 18. Супер-ЭВМ семейства CRAY (ВС с ОП) Появление векторных процессоров обусловлено наличием прикладных задач, в составе которых в значительной части присутствуют операции над векторами и матрицами большой размерности (явный параллелизм) или обработка множества циклов. Несмотря на то, что в последнее время появились высокопроизводительные скалярные (суперскалярные) процессоры, имеющие в своѐм составе несколько ядер, каждый из которых имеет параллельно функционирующие исполнительные узлы, а команды выбираются из памяти в виде связок, представляющих собой длинное слово (содержащее, например три команды, которые могут быть выполнены параллельно), их производительность и свойства оказываются востребованными. В 1976 году под руководством Сеймура Р. Крея была создана первая супер-ЭВМ CRAY-1, идеология векторной обработки которой используется до сих пор [7]. CRAY-1 – впервые применена векторная идеология (векторноконвейерная). Была применена водяная система охлаждения: сначала использовалась дистилированная вода, позднее – вода с теплоѐмкими 2 добавками, ещѐ позднее – газ. Процессор вместе с памятью занимал ~6 м , кэш-память отсутствовала. Базовая модель – однопроцессорная ВС. ТCY P = 12,5 нс (CRAY-1) ТCY P = 4,1 нс (CRAY-2) Модели CRAY-3 и CRAY-4 были заявлены, но не были построены из-за дороговизны изготовления и сложности технологических процессов (кристалл необходимо было выращивать в космосе). В настоящее время не существует даже макетов упомянутых моделей. CRAY-XMP – идеология CRAY-1, но ВС многопроцессорная. Число процессоров: 8, 16, 32… Базовая ОС – ОС Unix, базовый язык программирования – Fortran 77. Структурная схема ВС CRAY-1 на базе одного процессора приведена на рис. 18.1. Команда трѐхадресная: <1-й операнд>, <2-й операнд>, <результат> В буферы команд (всего их 4) за один машинный такт записывается 4 слова памяти. Одновременно может работать 12 функциональных устройств, (впервые был применѐн принцип зацепления), разделѐнных на 4 группы. Группа адресных исполнительных устройств. 1. сложение целых чисел (2 такта); 2. умножение целых чисел(6 тактов). Исполнительные устройства подготавливают адреса операндов; непосредственного участия в решении прикладных задач не принимают. 118 Группа скалярных операций. 1. сложение целых чисел (3 такта); 2. логические операции (1 такт); 3. сдвиг (12 такта); 4. счѐтчик (2 такта); возможен счѐт по модулю. Группа операций с плавающей точкой. 1. Сложение (6 тактов); 2. Умножение(7 тактов); 3. вычисление обратной величины (эквивалент деления) (14 тактов). Группа операций над векторами. 1. сложение чисел (3 такта); 2. логические (2 такта); 3. сдвиг (4 такта). Вектора целочисленные. Если элементы вектора – действительные числа, то обработка идѐт на блоках 3. Все функциональные устройства полностью сегментированы. Это означает, что в каждый такт на вход устройства может поступать новый операнд (или набор операндов), не связанный с предыдущим, при этом в устройстве может продолжаться обработка предыдущих операндов. Все системы CRAY имеют в своѐм составе множество различных регистров, в том числе, адресные регистры (А), скалярные (S), промежуточные адресные (В), промежуточные скалярные (Т), векторные (V) и большое число вспомогательных регистров. CRAY-2 строилась как многопроцессорная. Общая память. Общая оперативная память (ОП), построенная на МОП-транзисторах, содержит порядка 256 млн. слов. ОП состоит из 128 блоков с чередующимися адресами по 2 млн. слов в каждом. Как и в других машинах семейства CRAY, слово содержит 64 информационных и 8 контрольных разрядов. Произвольный доступ к ОП имеют любой из четырѐх процессоров нижнего уровня и любой из быстрых каналов и каналов общих данных. Все операции доступа к памяти выполняются автоматически на аппаратном уровне. Любая программа пользователя может обращаться как ко всей памяти, так и к любой еѐ части. Общий поток обмена информацией с памятью – 64 Гбайт/с. Локальная память. Ёмкость LM в каждом процессоре нижнего уровня составляет 16384 64-разрядных слова. Эта сверхбыстродействующая память служит для хранения скалярных операндов в течение всего времени счѐта и для временного хранения элементов векторов, когда они используются для вычислений с помощью векторных регистров более одного раза. LM обменивается данными с адресными регистрами, а также со скалярными и векторными регистрами, заменяя тем самым регистры В и Т, существовавшие в ранних моделях систем. 119 Рис. 18.1 Структурная схема вычислительной системы CRAY-1 120 Время передачи данных из LM в регистры А и S или в обратном направлении составляет один машинный такт. Начальное заполнение векторного регистра занимает пять тактов. После завершения заполнения данные могут поступать в регистр в каждом такте. Обращения в LM могут перекрываться с обращениями к ОП. Обмен с памятью осуществляется страницами. Работать можно с одной страницей, а параллельно заполнять другую. Используется принцип старения. Каждый процессор нижнего уровня выполняет арифметические и логические операции. Эти операции, так же как и прочие функции процессора нижнего уровня, координируются устройством управления. Резюме: CRAY-2 – отличается от CRAY-1 тем, что блоки Т и В заменены на локальную память. Также есть отличия в функциональных блоках. Существует четыре процессора нижнего уровня (минимум), причѐм на четыре процессора нижнего уровня есть один процессор верхнего уровня. 121 18.1 CRAY C-90 Рис.18.2 Общая схема компьютера CRAY C-90 Блоки «Векторные ФУ» и «ФУ обработки вещественных чисел» имеют по два конвейера! (впервые в CRAY применена идеология NEC) 1. 2. 3. 4. Векторные ФУ (5–7 штук): сложение/вычитание; сдвиг; логические; умножение битовых матриц и т.д. ФУ обработки вещественных чисел: 1. сложение/вычитание; 2. умножение; 3. обратная величина (эквивалент операции деления). 122 1. 2. 3. 4. Скалярные ФУ: сложение/вычитание; умножение; логические; сдвиг. Адресные ФУ: 1. сложение; 2. умножение. Ёмкость буфера команд: 8 блоков  16 (32) слов – одна страница. Пример. С := А + В На рис. 18.3 изображѐн принцип конвейерного выполнения операций над элементами вектора, разделѐнных на чѐтные и нечѐтные, с одними работает один сумматор (+), с другими другой. Рис. 18.3 Выполнение операции над векторами Благодаря этому производительность по сравнению с CRAY-1 выросла в два раза! В скалярном процессоре это бессмысленно, ведь каждый раз надо подавать команду, а здесь – ОКМД. Оценка производительности. Рассмотрим операции с вещественными числами (ведь они самые длинные). ТCY. P. CRAY-2 = ТCY. P. CRAY C-90 = 4,1 нс. Для трѐх ФУ получаем Т = 4,1 / 3 = 1,3 нс – это для одного процессора. Всего 16 процессоров, следовательно, Т = 1,3 / 16 = 0,08125 нс, т.е. f = 12,3 ГГц! 123 Разрядность слова – 64 разряда. Имеется 16 исполнительных устройств. ОП имеет 164 портов и разделена на 8 секций, а каждая секция – на 8 подсекций, в каждой подсекции 16 банков. Получаем 8816 расслоений памяти. Адреса в секцию записываются так: 00, 11, …, 77, 80… Если длина вектора кратна степени двойки, то возможны конфликты между процессорами, т.к. два процессора могут обратиться к одной секции! Конфликт в секции памяти устраняется за один такт, в подсекции – за 6 тактов, в банке – несколько десятков тактов! В настоящее время это ограничение накладывает весьма значительные ограничения на архитектуру ВС – пока не научились делать эффективные ВС с числом процессоров, больше 16-и (из-за конфликтов памяти)! Зависимость производительности от длины вектора здесь имеет нелинейный характер… 18.2 СуперЭВМ NEC SX (16) ВС с ОП NEC SX-6 обладает самой высокой производительностью! ТС = 1 нс (реально, скорее всего, немного больше). ВС состоит из 128 узлов, в каждом из которых 8 процессоров. Эта машина относится к классу 3Т (терабайтные КС, ѐмкость памяти – сотни терабайт, f ~ ТГц). Внутри порядка 40 векторных регистров, которые играют роль кэш-памяти. Система может работать в режимах: 1. пакетной обработки; 2. случайного потока задач с любых терминалов; 3. предполагается удалѐнный доступ. После того, как программа введена, управляющий процессор компилирует еѐ и выполняет привязку входных данных к заданию; происходит анализ кода, векторизация (преобразование циклов в векторные команды) и т.д. Система команд насчитывает около 150 векторных и скалярных команд. Исполнительные устройства могут работать только с регистрами. 124 Рис.18.4 Структурная схема ВС NEC SX-2 125 Рис.18.5 Структурная схема ВС NEC SX-6 126 Векторный процессор имеет четыре устройства по четыре одинаковых устройства; скалярный процессор имеет по одному такому устройству. Итого: 44 + 4 = 20 устройств. Предусмотрено выделение четырѐх векторных регистров на каждый вектор, благодаря этому операции выполняются в четыре раза быстрее. Реализован принцип зацепления (заимствован из CRAY). Память с расслоением (4 операции, следовательно, 8 операндов). Если операнды расположены подряд, тогда всѐ хорошо, но если имеет место смещение, то необходима операция индексации. В ВС CRAY это реализовано аппаратно, т.е. векторный процессор не занимается адресацией. Здесь подобных блоков нет. Оценка производительности ВС NEC SX-6: f = 1 (процессор)  8 (операндов за раз)  128 (узлов) ГГц!