Параллельные вычисления
 Скачать 1.75 Mb.
|
|
язность (connectivity) - показатель, характеризующий наличие разных маршрутов передачи данных между процессорами сети; конкретный вид показателя может быть определен, напр., как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области. • Ширина бинарного деления (bisection width) - показатель, определяемый как минимальное количество дуг, которое надо удалить для разделения сети передачи данных на две несвязные области одинакового размера. • Стоимость определяется, напр., как общее количество линий передачи данных в многопроцессорной вычислительной системе. Количественные значения этих показателей для различной топологии се- тей приведены в работе [3]. Естественным представляется объединение преимуществ систем с общей (относительная простота создания параллельных программ) и распределен- ной памятью (высокая масштабируемость); решением этого вопроса явилось создание компьютеров с архитектурой NUMA (Non Uniform Memory Access); в этом смысле классические SMP-компьютеры обладают архитектурой UMA (Uniform Memory Access). При этом применяется механизм (обычно аппарат- ного уровня – что быстрее), позволяющий пользовательским программам рассматривать всю (физически) распределенную между процессорами память как единое адресное пространство. Примерами NUMA-компьютеров является построенная еще в 70-x г.г. и содержащая объединенный межкластерной ши- ной набор кластеров система Cm* и объединяющий 256 процессоров ком- плекс BBN Butterfly (1981, фирма BBN Advanced Computers). Недостатками NUMA-компьютеров является все же значительная разница времени обращения к собственной (локальной) памяти данного процессора и памяти сторонних процессоров, а также проблема кэша (cache coherence problem) - в случае сохранения процессором П 1 некоего значения в ячейке N 1 при последующей попытке прочтения данных из той же ячейки N 1 про- цессором П 2 последний получит значение из кэша процессора П 1 , которое может не совпадать с истинным значением переменной в ячейке N 1 , если кэш процессора П 1 еще не ‘сброшен’ в память (о чем процессор П 2 ‘знать’ не обязан). Для решения проблемы когерентности (соответствия, одинаковости) кэша предложена и реализована архитектура ccNUMA (cache coherent NUMA), по- - 40 - зволяющая (прозрачными для пользователя) средствами достигать соответст- вия кэшей процессоров (что требует дополнительных ресурсов и, соответст- венно, снижает производительность). Типичным образцом ccNUMA-машины является HP Superdome (2 ÷ 64 суперскалярных процессора P-8600/P-8700 с возможностью дальнейшего наращивания, 256 Гбайт оперативной памяти, пиковая производительность 192 Гфлопс в 64-процессорном варианте, http://www.hp.com/go/superdome ). В системах с архитектурой COMA (Cache-Only Memory Architecture) на вычислительных узлах предусмотрены дополнительные (построенные по- добно структуре кэш-памяти) и называемые AM (Attraction Memory, ‘притя- гивающая память’) локальные модули памяти. При обращении к фрагменту памяти стороннего процессора поступивший фрагмент размещается как в кэш-памяти запрашивающего процессора, так и в его AM (ранее размещен- ный фрагмент при этом может быть выгружен); при неудачном поиске (про- махе) в кэш-памяти контроллер памяти просматривает AM и, если нужного фрагмента нет и там, инициирует запрос на его копирование из локальной памяти соответствующего вычислительного узла [4]. 2.2 Распределение вычислений и данных в многопроцессорных вы- числительных системах с распределенной памятью В случае наличия в составе многопроцессорной вычислительной системы (не-NUMA структуры) вычислительных узлов с локальной оперативной па- мятью кроме распределения частей вычисления по отдельным ВУ важно ра- циональным образом распределить по имеющимся ВУ данные (например, блоки обрабатываемых матриц значительной размерности). Дело в том, что затраты времени на обмен данными между обрабатывающими эти данные ВУ и ВУ, хранящими эти данные в своей локальной ОП, может на порядки за- медлить процесс вычислений. Ясно, что расположение большого пула данных на одном (например, пер- вом в списке) ВУ вряд ли целесообразно вследствие неизбежной значитель- ной потери времени на организацию пересылок отдельных блоков этих дан- ным обрабатывающим ВУ (не говоря уже о возможной нехватке ОП). С дру- гой стороны, чисто формальное разбиение данных на равное числу ВУ число блоков чревато тем же. Рациональное распределение данных по локальным ОП вычислительных узлов должно совершаться с учетом частоты обращения каждого ВУ к каждому блоку данных, расположенных на соответствующих ВУ при стремлении к минимизации числа обменов, что требует определения тонкой информационной структуры алгоритма. Казалось бы, в общем случае возможно построение некоей функции тру- доемкости (например, в смысле времени) вычислений, учитывающей как ре- - 41 - сурсные затраты на собственно вычисления так и трудоемкость обменов при заданном распределении данных по ВУ и дальнейшей минимизации этой функции по параметру (параметрам) распределения данных; причем само распределение может являться изменяемым (динамическим). Реально по- строение подобной функции затруднено вследствие необходимости количе- ственного (для конкретной вычислительной системы) определения времен- ных параметров выполнения операций (в т.ч. сетевых, с учетом реальной за- висимости скорости обмена от длины сообщения, тем более при учете неод- нородности вычислительных узлов) и выявлении значимых параметров оп- тимизации. Претендентом на роль подобной функции может служить, напр., вышеописанный сетевой закон Амдаля. Некоторые системы программиро- вания (напр., mpC, см. подраздел 4.1) обладают встроенными средствами для осуществления балансировки производительности. В стандартных пакетах решения задач линейной алгебры ScaLAPACK и AZTEC используются основанные на теоретическом анализе и долговремен- ной практике методы распределения данных по вычислительным узлам (включая специальные технологии, напр., блочное распределение с теневыми гранями, [3,5]). 2.3 Классификация параллельных вычислительных систем Классификация архитектур вычислительных систем преследует цели выяв- ление как основных факторов, характеризующих каждую архитектуру, так и взаимосвязей параллельных вычислительных структур [1]. Попытки выстро- ить (возможно непротиворечивые) классификации начались после опублико- вания в конце 60-х г.г. М.Флинном первого варианта классификации. Классификация М.Флинна (М.Flynn). Основой этой классификации (1966 г.) является понятие потока как последовательности команд (Instruction stream) и данных (Data stream), обрабатываемая процессором. SISD (Single Instruction stream / Single Data stream) – одиночный поток ко- манд и одиночный поток данных; к SISD-классу относятся классические по- следовательные (фон-Неймановского типа) машины (напр., всем известная PDP-11). В таких машинах имеется только один поток (последовательно об- рабатываемых) команд, каждая из которых инициирует одну скалярную опе- рацию. В этот класс попадают и машины с технологией конвейерной обра- ботки. SIMD (Single Instruction stream / Multiple Data stream) – одиночный поток команд наряду со множественным потоком данных. При этом сохраняется один поток команд, но включающий векторные команды, выполняющие одну арифметическую операцию сразу над многими данными (напр., отдельными элементами вектора). Выполнение векторных операций может производиться матрицей процессоров (как в машине ILLIAC IV) или конвейерным способом - 42 - (Cray-1). Фактически микропроцессоры Pentium VI и Xeon c набором инст- рукций MMX, SSE, SSE2 являются однокристалльными SIMD-системами [4]. Из отечественных SIMD-систем следует назвать ПС-2000 (Институт проблем управления РАН, И.В.Прангишвили, 1972 ÷ 1975) – высокопараллельная ком- пьютерная система для обработки информации с производительностью до 200 млн.оп./с. MISD (Multiple Instruction stream / Single Data stream) – множественный поток команд и одиночный поток данных. Архитектура подразумевает нали- чие многих процессоров, обрабатывающих один и тот же поток данных; счи- тается, что таких машин не существует (хотя с некоторой натяжкой к этому классу можно отнести конвейерные машины). MIMD (Multiple Instruction stream / Multiple Data stream) – множественные потоки как команд, так и данных. К классу MIMD принадлежат машины двух типов: с управлением от потока команд (IF - instruction flow) и управле- нием от потока данных (DF - data flow); если в компьютерах первого типа ис- пользуется традиционное выполнение команд последовательно их располо- жения в программе, то второй тип предполагает активацию операторов по мере их текущей готовности (подробнее см. подраздел 2.5 данной работы). Класс предполагает наличие нескольких объединенных в единый комплекс процессоров, работающий каждый со своим потоком команд и данных. Клас- сический пример - система Denelcor HEP (Heterogeneous Element Processor); содержит до 16 процессорных модулей (PEM, Process Execution Module), че- рез многокаскадный переключатель связанных со 128 модулями памяти дан- ных (DMM, Data Memory Module), причем все процессорные модули могут работать независимо друг от друга со своими потоками команд, а каждый процессорный модуль может поддерживать до 50 потоков команд пользова- телей. Отечественный представитель машины MIMD-архитектуры – вычис- лительные системы ЕС-2704, ЕС-2727 (конец 80-х г.г., НИЦЭВТ), позволяю- щий одновременно использовать сотни процессоров. Классификация P.Хокни (R.Hockney). В этом случае классифицируются (более подробно) компьютеры класса MIMD по Флинну [1]. Основа класси- фикации - выделение способов реализации множественного потока команд: единым работающим в режиме разделения для каждого потока конвейерным устройством или несколькими устройствами, обрабатывающими каждое свой поток. Второй вариант представлен двумя реализациями – с переключа- телями, дающими возможность осуществить прямую связь между всеми про- цессорами и системами, в которых прямая связь каждого процессора воз- можна только с ближайшими соседями (доступ к удаленным процессорам осуществляется специальной системой маршрутизации сообщений); каждая реализация имеет подклассы. Классификация T.Фенга (T.Feng, 1972). Каждая вычислительная система описывается парой чисел (n,m), где n - число параллельно обрабатываемых - 43 - единой командой бит в машинном слове, m - число одновременно обрабаты- ваемых слов; произведение P=n × m суть максимальная степень параллелизма вычислительной системы (величина, пропорциональная пиковой производи- тельности). Все вычислительные системы т.о. делятся на: • разрядно-последовательные, пословно-последовательные (n=m=1), • разрядно-параллельные, пословно-последовательные (n>1, m=1), • разрядно-последовательные, пословно параллельные (n=1, m>1), • разрядно-параллельные, пословно-параллельные (n>1, m>1) Классификацию Фенга считают устаревшей и далеко неполно учитываю- щей специфику современных многопроцессорных вычислительных систем, однако ее преимущество состоит во введении единообразного числового па- раметра для сравнения вычислительных систем (далее идея сия развита в классификации Хандлера). Согласно классификации В.Хaндлера (W.Handler) каждая вычислительная система характеризуется тройкой чисел (в расширенной варианте – тройкой групп чисел и арифметико-логических выражений), количественно характе- ризующей возможности вычислительной системы по параллельной и конвей- ерной обработке данных (при этом не уточняется тип связей между процес- сорами и блоками памяти - априорно предполагается, что коммуникационная сеть адекватно выполняет свои функции). Тройка определяет три уровня об- работки данных: • уровень выполнения программы - на основе данных счетчика команд и дополнительных регистров устройство управления (УУ) производит вы- борку и дешифрацию инструкций, • уровень выполнения команд - арифметико-логическое устройство (АЛУ) исполняет очередную команду, выданные УУ, • уровень битовой обработки - элементарной логические схемы (ЭЛС) процессора выполняют операции над отдельными битами данных, со- ставляющих машинное слово При обозначении числа УУ через k, в каждом из них число АЛУ символом как d и число ЭЛС в каждом АЛУ через w, то конкретная вычислительная система кодируется тройкой чисел (k,d,w), например: • IBM 701 → (1,1,36) • SOLOMON → (1,1024,1) • ILLAIC IV → (1,64,64) - 44 - Расширения системы классификации Хандлера позволяют более точно конкретизировать вычислительные системы (учесть число ступеней конвейе- ра, альтернативные режимы работы вычислительной системы и др., [1]). Классификация Д.Скилликорна (D.Skillicorn, 1989) предполагает описание архитектуры компьютера как абстрактной структуры, состоящей из компо- нент 4 типов (процессор команд, процессор данных, иерархия памяти, ком- мутатор): • процессор команд (IP, Instruction Processor) - функциональное устройство, работающее как интерпретатор команд (в системе может отсутствовать), • процессор данных (DP, Data Processor) - функциональное устройство, вы- полняющее функции преобразования данных в соответствии с арифмети- ческими операциями, • иерархия памяти (IM, Instruction Memory; DM, Data Memory) - запоминаю- щее устройство, хранящее пересылаемые между процессорами данные и команды, • переключатель – (абстрактное) устройство, обеспечивающее связь между процессорами и памятью (Скилликорном определены четыре типа пере- ключателей). Классификация Д.Скилликорна состоит из двух уровней. На первом уров- не она проводится на основе восьми характеристик: 1. Количество процессоров команд (IP). 2. Число запоминающих устройств (модулей памяти) команд (IM). 3. Тип переключателя между IP и IM. 4. Количество процессоров данных (DP). 5. Число запоминающих устройств (модулей памяти) данных (DM). 6. Тип переключателя между DP и DM. 7. Тип переключателя между IP и DP. 8. Тип переключателя между DP и DP. На втором уровне уточняется описание первого уровня путем добавления возможности конвейерной обработки команд и данных в процессорах. Скилликорном объявлено, что цель классификации архитектур заключает- ся в выпуклости показа, за счет каких особенностей структуры достигается повышение производительности различных вычислительных систем; это важно не только для выявления направлений совершенствования аппаратной части компьютеров, но и для создания эффективных параллельных программ. Дополнительные данные по классификации архитектур вычислительных систем (включая и не цитируемые здесь классификации) см. http://parallel.ru/computers/taxonomy/index.htm - 45 - 2.4 Многопроцессорные вычислительные системы с распределенной памятью С последнего десятилетия 20 века наблюдается тенденция к монополиза- ции архитектур супер-ЭВМ системами с распределенной памятью, причем в качестве процессоров на вычислительных узлах все чаще применяются лег- кодоступные готовые устройства. Основными преимуществами таких систем является огромная масштабируемость (в зависимости от класса решаемых задач и бюджета пользователь может заказать систему с числом узлов от не- скольких десятков до тысяч); что привело к появлению нового названия для рассматриваемых систем – массивно-параллельные компьютеры (вычисли- тельные системы архитектуры MPP - Massively Parallel Processing). Дэнни Хиллис, основатель компании Thinking Machines, в 1982 г. проде- монстрировал первый суперкомпьютер с массивной параллельной обработ- кой (massive multiprocessing). Система, получившая название Connection Ma- chine (СМ-1), была оснащена 64 тыс. процессоров, каждый из который имел собственную память. На своей первой презентации СМ-1 выполнила скани- рование 16 тыс. статей со сводками последних новостей за 1/20 сек. и разра- ботала интегральную схему процессора с 4 тыс. транзисторов за три минуты. Выпуклыми представителями MPP-систем являются суперкомпьютеры се- рии Cray T3 (процессоры Alpha, топология ‘трехмерный тор’, Cray Inc., http://www.cray.com ), IBM SP ( http://www.ibm.com, http://www.rs6000.ibm.com/sp.html, соединенные иерархической системой высо- копроизводительных коммутаторов процессоры PowerPC, P2SC, Power3), In- tel Paragon ( http://www.ssd.intel.com, двумерная прямоугольная решетка про- цессоров i860) и др. МРР-система состоит из однородных вычислительных узлов (ВУ), вклю- чающих: • один (иногда несколько) центральных процессоров (обычно архитектуры RISC - Reduced Instruction Set Computing, для которой характерно длинное командное слово для задания операций, сокращенный набор команд и выполнение большинства операций за один такт процессора), • локальную память (причем прямой доступ к памяти других узлов невоз- можен), • коммуникационный процессор (или сетевой адаптер), • жесткие диски (необязательно) и/или другие устройства ввода/вывода К системе добавляются специальные узлы ввода-вывода и управляющие узлы. Вычислительные узлы связаны некоторой коммуникационной средой (высокоскоростная сеть, коммутаторы и т.п.). - 46 - Техническое обслуживание многопроцессорных систем является непро- стой задачей – при числе ВУ сотни/тысячи неизбежен ежедневный отказ не- скольких из них; система управления ресурсами (программно-аппаратный комплекс) массивно-параллельного компьютера обязана обрабатывать по- добные ситуации в обход катастрофического общего рестарта с потерей кон- текста исполняющихся в данный момент задач. |