Параллельные вычисления
 Скачать 1.75 Mb.
|
|
ылок, при этом важное зна- чение начинает играть время ‘разгона’ канала связи. Время T (сек) передачи сообщения длиной X (Мбайт) от узла A узлу B при пропускной способности сети S (Мбайт/сек) при условии, что никаких иных обменов в сети не происходит, с хорошей точностью описывается формулой: Рисунок 14 — Качественный график за- висимости производительности сети от размера передаваемых сообще- ний - 54 - L S X T + = , (5) где L – время ‘запуска’ обмена (латентность); причем L не зависит от длины сообщения X, при X →0 или S ∞ → имеем T→L (именно влиянием латентности определяется вид кривой рис.14). Цена обмена P оценивает число байт, ‘потерянных’ каналом вследствие наличия латентности (естественно стремиться к всемерному снижению ла- тентности): S L P × = Лишь для SMP-машин можно принять S → ∞ и L→0); оценочные данные для некоторых известных технологий межпроцессорного обмена представле- ны в табл.3 [5,6]. Таблица 3 — Характеристики некоторых распространенных коммуни- кационных сетей для типичных представителей MPP- комплексов – вычислительных кластеров. Сетевая технология Fast Ethernet SCI (Scalable Coherent Interface, http://www.dolphinics.com ) Myrinet (Myricom, Inc., http://www.myri.com ) Латентность, мксек 40 ÷70 3 ÷10 17 Пропускн а я способ- ность аппаратная (Мбайт/сек) 12 150 ÷170 170 Пропускн а я способ- ность программная (Мбайт/сек) 10 80 40 Технология Gigabit Ethernet позволяет довести пропускную способность сети до 60 ÷80 Мбайт/сек, однако латентность зачастую в полтора-два раза выше, чем у FastEthernet [5]. Если для повышения быстродействия Fast Ethernet-сети возможно применить технологию Channel Bonding (связы- вание каналов, фактически – их дублирование путем совместного использо- вания сетевых плат; в Linux начиная с ядер версии 2.4.x эта возможность яв- ляется стандартно включаемой, см. http://linux-cluster.org.ru/bonding.php.htm ), то снизить латентность реально лишь с помощью применения более дорого- стоящего сетевого оборудования. Одной из наиболее перспективных технологий считается InfiniBand ( http://www.infinibandta.org/home ), позволяющая достичь латентности 4 ÷5 мксек (в перспективе до 1 мксек) и пропускной способности от 800 ÷1000 - 55 - Мбайт/сек (однонаправленный обмен) до 2000 ÷2700 Мбайт/сек (двунаправ- ленные обмены). Величина латентности определяет класс задач, которые можно эффективно решать на данном многопроцессорном комплексе или необходимый уровень мастерства распараллеливания. Например, при латентности 100 мксек вели- чина зерна распараллеливания должна быть такой, чтобы соответствующая ему последовательность команд выполнялась в среднем за время не менее 1 ÷10 мсек (т.е. хотя бы на порядок больше времени латентности); это доста- точно крупнозернистый параллелизм, иначе время обмена сообщениями ‘съест’ все повышение производительности от распараллеливания. 2.4.4 Стандартные программные пакеты организации вычислительных кластеров В последние годы появилось программные комплексы, позволяющие ор- ганизовать вычислительные кластеры буквально в течение минут. Это, на- пример, дистрибутивы Parallel Knoppix ( http://pareto.uab.es/mcreel/ ParallelKnoppix), CLIC ( http://clic.mandrakesoft.com/index-en.htm ) компании Man- drake ( http://mandrake.com ), BCCD ( http://bccd.cs.uni.edu ) разработки Универси- тета Северной Айовы США ( http://cs.uni.edu ), Rocks Cluster Distribution (http://www.rocksclusters.org) и др. Особый интерес представляет первая из перечисленных разработок, осно- ванная на технологии openMosix и включающая технологию миграции зада- ний. Кластер openMosix (фактически Linux c 3% изменением исходного кода ядра ОС) представляет собой однообразную систему (Single System Image - SSI), при этом ресурсы входящих в кластер ЭВМ могут использоваться более эффективно вследствие возможности миграции (перемещения от одной ма- шины к другой) заданий. Особенностью openMosix является то, что пользо- ватель только запускает программу, а ОС кластера решает, где (на каких именно узлах) ее выполнить (если не предусмотрено противоположное); раз- работчики openMosix называют это свойство ‘разветвись-и-забудь’ (fork-and- forget). Подобные системы обладают высокой масштабируемостью и могут быть скомпонованы из машин с различными ресурсами (производительность процессора, размер памяти и др.). Несмотря на лежащие на поверхности явные достоинства подобных про- граммных пакетов, их применение при создании масштабных кластерных систем ограничено (обычная область их применения – демонстрационные и макетные системы и простейшие кластеры). Основная причина этого – серь- езные затруднения при оптимизации построенного с их использованием кла- стерного ПО (каждый масштабный кластер настраивается и оптимизируется строго индивидуально). - 56 - Интересной разработкой ПО кластерных систем является проект МВС-900, разработанный в испытательной лаборатория проекта МВС ИПМ им. М.В.Келдыша РАН [5], см. http://pilger.mgapi.edu/metods/1441/lacis.zip Технология МВС-900 использует (относительную) малозагруженность обо- рудования учебных Windows-классов, техническая реализация МВС-900 ос- нована на применении диспетчера виртуальных машин VMware (фирма VMware, Inc., http://www.vmware.com ), под которым работает Linux (рекомен- дуются дистрибутивы Dragon или Slackware, http://sourceforge.net/projects/ dragonlinux, http://www.slackware.com ); базовая операционная система – не ниже Windows’2000. При этом Windows и VMware-Linux на физической машине взаимодействуют минимально (переразмечать диски не требуется, исполь- зуются непересекающиеся адресные пространства, IP-адреса обслуживаю- щих сетей различны); в случае серьезной аварии восстановить работоспособ- ность МВС-900 ‘с нуля’ реально за полчаса-час. Т.о. виртуальный кластер работает совместно с Windows-машинами ком- пьютерного класса, разделяя их ресурсы. Отсутствие значимых накладных расходов при работе Linux под VMware обусловлено ее функционированием не в режиме полной программной эмуляции двоичного кода, а стандартного выполнения на правах обычного Windows-процесса; при этом непривилеги- рованные команды (арифметические, переходов и подобные) выполняются физическим процессором напрямую и только запрещенные к исполнению вне пределов базовой операционной системы привилегированные команды мо- делируются (эмулируя наличие соответствующего внешнего устройства). В конечном итоге центральным процессором выполняется поток команд (есте- ственно, перемежаемый предписаниями базовой ОС при сохранении и вос- становлении контекста), полностью идентичный таковому в настоящих ‘же- лезных’ Linux-кластерах; при этом потери быстродействия процессора на накладные расходы составляют около 7% (по данным разработчиков). Одна- ко формально такой кластер будет гетерогенным (производительность каж- дого узла зависит от загруженности Windows-программами и далеко непо- стоянна). Таким образом с помощью технологии МВС-900 реализуется классическая MPP-система коллективного пользования, практически полностью идентич- ная (по правилам администрирования, программирования и отладки) распо- ложенному в Межведомственном Суперкомпьютерном Центре (МСЦ) супер- кластеру МВС-1000М ( http://www.jscc.ru ). 2.5 Нетрадиционные архитектуры многопроцессорных вычислительных систем Поиски путей повышения производительности компьютеров вызвали раз- витие новых нетрадиционных архитектур вычислительных систем; наиболее - 57 - известными являются управляемые потоком данных вычислители, массивы систолических ячеек и многопроцессорные системы с программируемой ар- хитектурой. В наиболее общем виде процесс преобразования данных можно записать в виде триады (ср. с известным отношением ‘товар ⇒ деньги ⇒ товар’): входные данные ⇒ преобразование дан- ных (операторы) ⇒ выходные данные Какой объект (из перечисленных) должен управлять преобразованием? Из общих соображений именно тот, ради которого и ‘затеяна вся игра’ – данные (в этом смысле операторы суть всего лишь конкретизация технологии обра- ботки информации, малоинтересная конечному потребителю оной). Метод вычислений, при котором выполнение каждой операции произво- дится при готовности всех ее операндов, называется data flow (вычисления, управляемые потоком данных), при таком методе последовательность вы- полнения команд заранее не задается; используется также понятие Data Driven Computing (вычисления, управляемые данными). Впервые графиче- скую модель вычислений, управляемых потоком данных, предложил Дуайн Эдэмс (Стэнфордский университет, 1968). В системе data flow вместо импе- ративного указания выполнить некоторую команду используется разрешение ее выполнить; схема data flow противопоставляется традиционной схеме с управлением потоком (control flow). Сама природа метода управления потоком данных подразумевает глубокий параллелизм (в отличие от метода управления потоком команд, заданных че- ловеком). Метод управления потоком данных открывает широкие возможно- сти для организации параллельных вычислительных процессов, причем с ап- паратным распараллеливанием. Работы по созданию по созданию программно-аппаратных средств реали- зации принципа data flow велись в государственных и частных исследова- тельских центрах всего мира: напр., в Массачусетсом технологическом ин- ституте (процессор Tagget Token), лабораториях фирмы Texas Instruments (США), в Манчестерском университете (Англия), однако дальше экспери- ментальных машин дело не пошло. Наиболее известны data flow - системы Monsoon, Epsilon (США) и CSRO-2 (Австралия). В системах data flow последовательность выполнения операций зависит от готовности операндов (как только в памяти оказываются необходимые опе- ранды, необходимые и достаточные для выполнения того или иного опера- тора, исполнение последнего инициируется на одном из нескольких испол- нительных устройств - если есть свободные). При этом последовательность выполнения операций программы может отличаться от порядка их записи - - 58 - например, различные итерации цикла могут выполняться одновременно (бо- лее того, i+1-я итерация может выполняться ранее i-той – если для нее гото- вы данные). Data flow - системы включают много исполнительных устройств, работающих параллельно, на каждом из них возможно выполнение любого оператора системы команд машины. Таким образом удается преодолеть традиционно-узкое место современных скалярных процессоров, существенную часть времени тратящих не на об- работку данных, а на процедуры управления данными и спекулятивные вы- числения. В отличие от многомашинных комплексов с традиционной архи- тектурой распараллеливание вычислительных процессов в системах data flow осуществляется аппаратно. При этом работа по организации вычислитель- ного процесса возлагается на особое запоминающее устройство, в котором происходит накопление операндов и поиск готовых к выполнению операто- ров (аналог устройства управления в традиционных последовательных ЭВМ). Д ля описания потоковых программ используется язык акторных се- тей. Наиболее эффективная реализация этого механизма – использование ассо- циативной памяти, которая представляет собой сложное устройство, предна- значенное не только для хранения данных с определенными признаками – тэгами (tag, причем тэг указывает, в каком контексте используются данные и для выполнения какой команды они предназначены), но и для сравнения тэгов (п ри их совпадении происходит выборка данных и инициация выпол- нения соответствующей команды). Заметим, что этот механизм частично ис- пользуется в некоторых современных высокопроизводительных микропро- цессорах (напр., в 64-разрядном Itanium фирмы Intel). В терминологии data flow данные вместе с набором признаков (тэгами) именуются токенам (token – признак, метка, готовый для употребления). При data flow механизм управления данными сильно развит, соответственно име- ется большее число управляющих признаков у данных (выполняемая и сле- дующая за ней команды – та, кому необходим результат операции, номер итерации, тип операции - векторная/скалярная, одно/двухоперандная, число токенов результата операции, при этом совокупность признаков токена без кода операции именуется его ‘окраской’). На рис.15 приведена схема data flow – вычислителя согласно работы ( * ), исследования и создание новых архитектур ЭВМ проводились в рамках ‘Программы Основных направлений фундаментальных исследований и раз- работок по созданию оптической сверхвысокопроизводительной вычисли- тельной машины Академии наук’ (ОСВМ), позднее от реализации ассоциа- * Бурцев В.С. Выбор новой системы организации выполнения высокопараллельных вы- числительных процессов, примеры возможных архитектурных решений построения су- перЭВМ. // В кн.: Параллелизм вычислительных процессов и развитие архитектуры су- перЭВМ. – М.: ИВВС РАН, 1997. - 59 - тивной памяти на основе оптики от- казались в пользу появившихся на рынке высокопроизводительных полупроводниковых модулей тро- ичной ассоциативной памяти (Ternary Content Addressable Memory, TCAM) компаний Motorola, Music Semiconductors, Inc., M icron Tech., Inc. По этой схеме вычислительное устройство представляет собой кольцевую структуру. Токены фор- мируются на основе анализа струк- туры алгоритма, хранятся в ассо- циативной памяти (АП) и при усло- вии набора их комплекта, достаточ- ного для выполнения одного из опе- раторов, направляются в буфер ас- социативной памяти (БАП). В БАП’е накапливаются готовые па- кеты для передачи в исполнитель- ной устройство (ИУ); коммутатор K in распределяет пакеты готовых токенов между свободными ИУ. В ассоциативной памяти поиск нужной информации производится не по адресу ячейки, а по ее содержанию (ассоциативному признаку), при этом по- иск по ассоциативному признаку (или последовательно по отдельным его разрядам) происходит параллельно во времени для всех ячеек запоминающе- го массива. Данные в ассоциативной памяти интенсивно обрабатываются, поэтому для увеличения быстродействия она разбита на отдельные модули. Набор признаков токенов, полученных в результате обработки ИУ, аппаратно анализируется и коммутатором K out распределяется по модулям АП. Именно в таком направлении работают сотрудники отдела Института про- блем информатики РАН, ряд лет возглавляемые В.С.Бурцевым (при финан- совой поддержке американской корпорации Nodal Systems). Другой путь развития вычислительных систем связывают с отказом от коммутаторов (коммутационных сетей), ограниченное быстродействие кото- рых тормозит рост производительности МВС. Современные технологии по- зволяют создавать кристаллы с огромным количеством простых процессор- ных элементов (ПЭ), массивы ПЭ с непосредственными соединениями между близлежащими ПЭ называются систолическими. Такие массивы обладают Рисунок 15 — Архитектура вычислительного устройства, реализующего подход data flow. - 60 - очень высоким быстродействием, но каждый из них ориентирован на реше- ние очень узкого класса задач. В работе [7] описано использование систолических массивов (СМ) для ре- шения специальной задачи умножения и сложения матриц [D]=[C]+[A] × [B] (частный случай афинного преобразования), причем все матрицы — ленточ- ные порядка N; матрица [A] имеет одну диагональ выше и две диагонали ни- же главной; матрица [B] — одну диагональ ниже и две диагонали выше глав- ной; матрица [C] по три диагонали выше и ниже главной. Каждый входящий в систолический массив ПЭ выполняет скалярную операцию c+ab и одно- временно осуществляет передачу данных (имеет три входа a,b,c и три выхо- да a,b,c, причем (in) и выходные (out) данные связаны соотношениями a out =a in , b out =b in , c out =c in +a in × b in , точка в обозначении систолической ячей- ки определяет ее ориентация на плоскости, рис.16). Рисунок 16 — Систолический массив для реализации матричной операции [D]=[C]+[A] × [B] (слева – принятое обозначение систолической ячейки для выпол- нения скалярной операции c+a × b и передачи данных). Ячейки расположены в узлах регулярной косоугольной решетки, исходные данные поступают слева сверху, справа сверху и снизу (элементы матрицы [A], [B] и [C] соответственно), за каждый такт все данные перемещаются в соседние узлы по указанным стрелками направлениям. Рис.16 иллюстрирует состояние СМ в некоторый момент времени, при следующем такте все дан- ные переместятся на один узел и элементы a 11 , b 11 и c 11 окажутся в одном - 61 - ПЭ (помечен номером 1), находящемся на пересечении штриховых линий (т.е. будет вычислено выражение с 11 + a 11 × c 11 . В этот же такт данные a 12 и b 21 вплотную приблизятся в ПЭ, находящемся в вершине систолического массива (помечен символом 2), в следующий такт все данные снова перемес- тятся на один узел по направлению стрелок и в верхнем ПЭ окажутся a 12 и b 21 плюс результат предыдущего срабатывания ПЭ, находящегося снизу, т.е. с 11 +a 11 × b 11 Следовательно, будет вычислено выражение c 11 +a 11 × b 11 +a 12 × b 21 , а это и есть иск |