Параллельные вычисления
 Скачать 1.75 Mb.
|
|
омый элемент d 11 матрицы [D]. На соот- ветствующих верхней границе СМ выходах ПЭ, периодически через три так- та выдаются очередные элементы матрицы [D], на каждом выходе появля- ются элементы одной и той же диагонали. Примерно через 3 × n тактов будет закончено вычисление всей матрицы [D], при этом загруженность каждой систолической ячейки асимптотически приближается к 1/3. Систолические массивы обладают чертами как процессорных матриц (со- вокупность связанных ПЭ, выполняющих единую команду), так и явные при- знаки конвейерного вычислителя (что выражается в потактном получении результата). Систолические массивы являются специализированными вычис- лительными системами и могут выполнять только регулярные алгоритмы; математические модели систолических массивов, пригодные для целей по- строения СМ c заданными свойствами, обсуждаются в работе [1]. Главное отличие многопроцессорных систем с программируемой архи- тектурой является возможность программно устанавливать как связи меж- ду процессорными элементами, так и функции, выполняемые данными ПЭ. Важнейшей составной частью такой системы является универсальная комму- тационная среда (УКС) ( * ), которая состоит из однотипных, соединенных друг с другом регулярным образом автоматических коммутационных ячеек, для которых характерно коллективное поведение . Структура многопроцессорной системы, использующей универсальную коммутацию, приведена на рис.17. Настройка системы на выполнение кон- кретной задачи производится в два этапа: • На первом этапе производится распределении крупных (макро-) операций (интегрирование, дифференцирование, матричные операции, быстрое пре- образование Фурье и т.п.) между ПЭ и настройка имеющихся ПЭ на вы- полнение этих операций. • Второй этап заключается в настройке необходимых каналов связи между ПЭ в УКС. * Каляев А.В. Многопроцессорные системы с программируемой архитектурой. -М.: Радио и связь, 1984. -283 с. - 62 - После этого возможен автоматиче- ский режим работы многопроцессор- ной системы, при котором на вход по- дается входная информация, а с выхода снимаются результаты. Простейший коммутационный эле- мент (КЭ), необходимый для построе- ния плоской УКС (возможны и много- мерные УКС), содержит два входа и два выхода и связан с четырьмя сосед- ними КЭ. В таком элементе возможны девять вариантов внутренней коммута- ции (рис.18), что и обеспечивает возможность установления произвольных связей между ПЭ (в т.ч. и изображенных на рис.17). При настройке плоской УКС наме- чается непрерывная цепочка свобод- ных КЭ, соединяющих входы и выходы нуж- ных ПЭ. При этом цепочка должна обходить неисправные КЭ и элементы, уже вошедшие в другие каналы связи. После выбора канала связи во все выбранные КЭ вводится код на- стройки, далее канал связи функционирует по- добно сдвиговому регистру, в котором инфор- мация по тактам передается от одного КЭ к другому. Настройка КЭ может производиться вручную или автоматически. Для автоматического образования одного канала связи между двумя ПЭ хорошо подхо- дит известный волновой принцип: o В УКС указываются входной и выходной КЭ. o Входной элемент соединяется со всеми исправными и незанятыми сосед- ними элементами (при этом образуется волна подсоединенных КЭ; если в ней не оказалось нужного выходного элемента, то каждый элемент волны соединяется с соседними КЭ, образуя новый фронт волны). o Продвижение волны продолжается до тех пор, пока ее фронт не достигнет нужного выходного КЭ, после чего в элементы, составляющие кратчай- ший путь между двумя ПЭ, заносятся коды настройки, а остальные уста- новленные связи разрываются. Рисунок 17 — Структура многопроцессор- ной системы с программируемой архитектурой Рисунок 18 — Варианты внутрен- ней коммутации простейшего КЭ - 63 - o Процесс повторяется для всего набора входных и выходных КЭ; таким образом последовательно устанавливаются все связи, необходимые для решения конкретной задачи. Эффективность систем с программируемой архитектурой зависит от вели- чины коэффициента K = t з / t н , где t з — время решения задачи, t н — время на- стройки системы (естественно стремиться к увеличению K). Время t н для систем с программируемой архитектурой относительно велико, поэтому по- высить K можно только увеличением t з Для увеличения t з следует эксплуатировать многопроцессорную систему с программируемой архитектурой длительное время для решения одной и той же задачи; при этом в каждый такт на вход системы поступает новый набор исходных данных, а с выхода системы в каждый такт снимаются новые ре- зультаты – именно этим объясняется очень высокое быстродействие при ре- шении крупных задач. Т.о. наиболее выгодным для систем с программируе- мой архитектурой является режим конвейерной обработки, в то же время эти системы принадлежат к многопроцессорным системам типа MIMD в класси- фикации М.Флинна (см. подраздел 2.2 данной работы). Интересно, что еще в конце 80-х г.г. была создана экспериментальная ‘из Ряда вон выход я щая’ многопроцессорная (24 вычислительных модуля, 12 коммутационных процессоров и 6 процессоров ввода-вывода) вычислительная система ЕС-2704 (В.А.Торгашев, В.У.Плюснин, Научно-исследовательский центр электронной вычисли- тельной техники - НИЦЭВТ), представляющая собой мультипроцессор с динамической архитектурой (МДА) и массовым параллелизмом; осн о вой необычной архитектуры составляла адаптивная (подстраивающаяся под логическую структуру конкретной за- дачи) сеть вычислительных модулей с полностью децентрализованным управлением. Для ЕС-2704 характерно представление задачи не в виде традиционного алгоритма, а в виде сети, каждый элемент которой способен изменять свои связи с другими элемента- ми сети, порождать новые элементы или самоуничтожаться. Аппаратно поддержанная распредел е нная ОС обеспечивала динамическое управление ресурсами при решения задач, подготовленных для выполнения в сети процессоров, высокую степень распа- раллеливания и надежность. Дальнейшие разработки привели к появлению нового типа компонента вычислительной системы - процессора с динамической архитектурой (ПДА), который может быть как элементом (модулем) МДА, так и самостоятельным устройством, которое может быть использовано для самых различных приложений; реализации процессоров с динамической архитектурой (DAP-31, DAP-311, DAP-317) применяются в системах обработки радиолокационной информации и телекоммуника- ций. 2.6 Метакомпьютинг и GRID-системы Несмотря на огромную производительность суперкомпьютеров, вполне ре- ально существует огромный резерв вычислительных мощностей, который - 64 - представляют объединенные сетью InterNet миллионы компьютеров. Их суммарная производительность и объем памяти на порядки превышают соот- ветствующие величины любого мыслимого суперкомпьютера. Эти миллионы ЭВМ образуют сообщество вычислительных мощностей (метакомпьютер), поэтому использующая эти мощности технология полу- чила название метакомпьютинг. Для связи ЭВМ при метакомпьютинге обычно используется InterNet (протокол TCP/IP) как общедоступная и охва- тывающая всю Планету сеть, хотя для некоторых специальных проектов мо- гут создаваться специализированные компьютерные сети. Метакомпьютер существенно отличается от иных вычислительных систем – он является рас- пределенным по своей природе, динамически меняет свою конфигурацию (специальная программная система отслеживает включение и отключение отдельных ЭВМ таким образом, чтобы пользователь этого не замечал), мета- компьютер неоднороден (используются компьютеры самых различных мощ- ностей и конфигураций с несовпадающими системами инструкций процес- соров, операционными системами и т.д.). Не всякие задачи могут эффективно решаться с помощью метакомпью- тинга – вследствие существенно большего (секунды/минуты) времени обмена данными для обработки пригодны задачи, не требующие тесного (частого и интенсивного) взаимодействия параллельных процессов. Одним из наиболее известных метакомпьютерных проектов является SETI@home (Search for Extra Terrestrial Intelligence) – обработка принятых радиотелескопом Аресибо (Пуэрто-Рико) данных (просматривается полоса 2,5 MHz вокруг частоты 1420 MHz, в день записывается около 35 Гбайт ин- формации) с целью выявления признаков сигналов искусственного происхо- ждения (цель – поиск внеземной разумной жизни). Принять участие в про- грамме может любой пользователь Windows, UNIX, Mac или OS/2, загрузив клиентскую часть программы с адреса http://setiathome.ssl.berkely.edu (русскоя- зычное зеркало http://setiathome.spb.ru ). Серверная часть ПО загружает на клиентские машины блоки данных размером 0,34 Мбайт и после обработки принимает результаты анализа, расчеты возможны в период простоя ПЭВМ (работа в режиме ‘хранителя экрана’) или постоянно в фоновом режиме; еще к 2002 г. число клиентов приблизилось к 4 млн., при этом суммарная произ- водительность их ЭВМ намного превосходит производительность всех вклю- ченных в ‘Top-500’ суперкомпьютеров. Проект Einstein@Home ( http://einstein.phys.uwm.edu ) имеет цель проверки одного из следствий общей теории относительности А.Эйнштейна - сущест- вование гравитационных волн. Данные поступают с LIGO (Laser Interferome- ter Gravitational wave Oservatore, две установки в США – Ливингстон и Хан- форд, штаты Луизиана и Вашингтон соответственно) и установки GEO 600 (Ганновер, Германия); метод замера – сравнение времени запаздывания луча лазера в интерферометрах со сверхдлинным плечом 0,6 ÷ 4 км при анализе - 65 - гравитационного воздействия от пульсаров или нейтронных звезд. Проект запущен в начале 2005 г., размер клиентского блока данных составляет 12 ÷ 14 Мбайт и рассчитан на недельную обработку, приращение участников проекта – 1’000 в день. Проект Condor ( http://www.cs.wisc.edu.condor ) распределяет задачи в корпо- ративной сети, используя неиспользуемые ресурсы ПЭВМ в режиме их про- стоя (нерабочие дни, ночь и т.п.); программное обеспечение распространяет- ся свободно для платформ Windows NT, Linux, Solaris и др. В рамках проекта Globus ( http://globus.org ) разрабатывается глобальная ин- формационно-вычислительная среда; созданные в рамках проекта программ- ные средства распространяются свободно (в т.ч. с исходными текстами) в ви- де пакета Globus Toolkit; это программное обеспечение является основой многих иных проектов в области метакомпьютинга и GRID. Некоторые из других известных проектов распределенных вычислений: • Climate Prediction - проект по моделированию влияния выбросов углеки- слого газа на климат Земли (‘парниковый эффект’). • Legion (A Worldwide Virtual Computer, http://legion.virginia.edu ) - разработка объектно-ориентированного программного обеспечения для построения виртуальных метакомпьютеров на основе миллионов индивидуальных ЭВМ и высокоскоростных сетей, при этом работающий на ПЭВМ поль- зователь имеет полностью прозрачный доступ ко всем ресурсам мета- компьютера. • Dictributed.Net ( http://distributed.net) - перебор ключей с целью взлома шифров. • TERRA ONE ( http://cerentis.com ) – коммерческий проект фирмы Cerentis по созданию метакомпьютера для анализа различной информации (пре- доставившие для вычислений свои ПЭВМ пользователи получают кре- диты TerraPoints для закупок в InterNet-магазинах). • Find-a-Drug ( http://www.find-a-drug.org ) - проект по поиску лекарств от раз- личных болезней путем расчета процесса синтеза белков с запланиро- ванной молекулярной структурой. • Folding@Home - проект по расчету свертывания белков (суммарная вы- числительная мощность 200 Тфлопс). • GIMPS (Great Internet Mersenne Prime Search) - поиск простых чисел Мерсенна ( http://mersenne.org ). Фонд Electronic Frontier Foundation ( http://www.eff.org ) предлагает приз в 100 тыс. $US за нахождение числа Мерсенна (простого числа вида 2 P -1) с числом цифр 10 млн. • SeventeenOrBust ( http://www.seventeenorbust.com ) - проект, занимающийся решением задачи Серпински (нахождении величины n, при котором зна- чение выражения 1 2 + × n k является простым; в начале проекта это было доказано для всех значений k, кроме семнадцати – отсюда название про- - 66 - екта SeventeenOrBust). • ZetaGrid ( http://www.zetagrid.net ) - проверка гипотезы Римана (одна из проблем теории чисел, 1859). Несмотря на задействованные при метакомпьютинге огромные вычисли- тельные мощности, некоторые задачи не могут быть за приемлемое время ре- шены даже этим способом. Под GRID (по аналогии с ‘power grid’ – электрическая сеть) понимают рас- пределенную программно-аппаратную компьютерную среду, призванную пу- тем интегрирования географически удаленных компьютерных ресурсов обес- печить всеобщий доступ к вычислительным мощностям для решения крупных научно-технических задач. Для создания надежной системы GRID особенно важно создание специализированного программного обеспечения промежу- точного (middleware) уровня для управления заданиями, обеспечения безо- пасного доступа к данным, перемещения/тиражирования данных огромного объема в пределах континентов. Показательным примером использования технологии GRID является орга- низация обработки данных экспериментов предполагающегося ко вводу в строй в 2006 ÷ 2007 г.г. Большого Адронного Коллайдера (LHC, Large Hadron Collider) в Европейском Центре Ядерных исследований (CERN). На четырех крупных физических установках в течение 15 ÷ 20 лет будет собираться по несколько Петабайт данных ежегодно. Во время проведения эксперимента данные записываются со скоростью 0,1 ÷ 1 Гбайт/сек и сохраняются как в ар- хивах CERN, так и многих сотен участников – исследовательских институтов и университетов всех стран мира; для хранения и обработки данных создана пятиуровневая иерархическая структура вычислительных центров. Поддержку LHC осуществляет система EU Data GRID (EDG, http://eu- datagrid.org ), основан Европейским Сообществом с целью создания сетевой компьютерной инфраструктуры нового поколения для обработки распреде- ленных тера- и петабайтных баз данных, полученных в результате научных исследований. EDC предполагает хранение и обработку данных физики высо- ких энергий, биоинформатики и системы наблюдений за Планетой (особен- ность проекта – разделение информации по различным базам данных, распо- ложенных на различных континентах, цель – кардинальное улучшение эффек- тивности и скорости анализа данных методом распределения мощностей про- цессоров и систем распределенного хранения с динамически распределением и репликацией). Основой проекта является набор программных средств Globus. В России действует компонент DataGrid, услугами которого пользу- ются ведущие научные институты - НИИЯФ МГУ, ОИЯИ, ИТЭФ, ИФВЭ. В НИВЦ МГУ разработана GRID-система X-Com, предназначенная для ор- ганизации распределенных вычислений с использованием неоднородных вы- числительных ресурсов. Для функционирования X-Com не требуется спе- - 67 - циализированных компьютеров, высокоскоростных сетей, сложной на- стройки задействованных вычислительных ресурсов и необходимости ис- пользования определенного языка программирования. Контрольные вопросы 1. В чем заключается основное отличие многопроцессорных систем с общей и распределенной памятью? Каковы достоинства и недостатки систем каж- дого из этих классов? Что такое масштабируем ость многопроцессорных вычислительных систем? В чем преимущества и недостатки компьютеров с NUMA-архитектурой? 2. Допустим, имеются системы параллельного программирования с возмож- ностью преимущественного распределения по вычислительным узлам: a) только вычислений, б) только данных, в) и данных и вычислений. С по- мощью каких из этих систем проще (удобнее, быстрее) разрабатывать эф- фективные параллельные программы для многопроцессорных вычисли- тельных комплексов архитектуры: a) SMP, б) NUMA, в) MPP? 3. В чем суть использования матричных переключателей и принципа каска- дирования при объединении модулей многопроцессорных ЭВМ? Каковы достоинства и недостатки этих технологий? 4. Что такое величина средней длины пути, соединяющего произвольные вы- числительные узлы многопроцессорных систем? Для каких топологий эта величина больше и для каких она минимальна суть? 5. В чем различие топологий ‘двумерная решетка’ и ‘двумерный тор’ (соот- ветственно ‘трехмерная решетка’ и ‘трехмерный тор’)? 6. На каких характеристиках основываются известные классификации парал- лельных вычислительных систем? 7. Постарайтесь расширить топологию МВС-100 и МВС-100/200 для транс- пьютеров с 6-ю линками (представить возможные схемы топологии). 8. Каков физический смысл понятий латентности и цены обмена? Предло- жите иную систему (количественных) характеристик для рассматриваемо- го явления. 9. Назвать распространенные сетевые технологии для связывания вычисли- тельных узлов многопроцессорных систем и дать количественные характе- ристики основных параметров оных (латентности, пропускной способно- сти и др.). - 68 - 3 Анализ алгоритмов с целью выявления параллелизма Кардинальным отличием выполнения программы на вычислительной сис- теме параллельной архитектуры от такового последовательного компьютера является возможность одновременного выполнения целой группы опера- ций, друг от друга не зависящих (на последовательной машине в каждый мо- мент времени выполняется только одна операция, другие могут находиться только на стадии подготовки). На различных параллельных машинах эти группы и последовательность их выполнения скорее всего будут разными. Однако существует (естественное) требование повторяемости результатов (алгоритм, приводящий к различным конечным результатам даже при оди- наковых входных данных, вряд ли кому нужен – моделирование статистиче- ских процессов не рассматриваем). В общем случае этап разработки параллельной программы должен предва- ряться процессом выявления блоков (последовательностей исполняемых предписаний), м |