Параллельные вычисления
 Скачать 1.75 Mb.
|
|
ико- вую) производительность 3,2 триллионов операций в секунду (3,2 Тераф- лопс), включает 9’632 микропроцессора Pentium Pro, общий объем оператив- ной памяти 500 Гбайт и оценивается в сумму около 50 млн. $US. Список ‘Top-500’ некоторое время возглавлял созданный для моделирования клима- тических изменений на основе полученных со спутников данных многопро- цессорный комплекс Earth Simulator (NEC Vector, Япония), состоящий из 640 узлов (каждый узел включает 8 микропроцессоров SX-6 производительно- стью 8 Гфлопс каждый), общий объем оперативной памяти 8 Тбайт, суммар- ная пиковая производительностью 40 Тфлоп/сек (занимает площадь размера- ми 65 ×50 м в специально построенном двухъярусном здании с системами антисейсмики, кондиционирования воздуха и защиты от электромагнитных излучений). 70-ти терафлопный Blue Gene/L заказан Минэнергетики США и установлен в специализирующейся на ядерных проблемах Ливерморской ла- боратории. Отечественная система МВС-15000ВМ (установлена в МСЦ - Межведомственном суперкомпьютерном центре РАН, http://www.jscc.ru ) пред- ставляет собой кластер из 462 серверов IBM, каждый из которых включает два процессора PowerPC 970 с частотой 2,2 ГГц и 4 Гб оперативной памяти, производительность МВС-15000ВМ в тесте LINPACK равна 5,4 Тфлопс при пиковой производительноcти в 8,1 Тфлопс на 56 месте в ‘Top-500’ (июнь 2005 г.). Китай планирует в течение 11-й китайской пятилетки (2006 ÷ 2010 г.г.) вве- сти в строй суперкомпьютер производительностью не менее 1 Петафлопс (1 Пфлопс=10 15 ‘плавающих’ операций в секунду), однако Япония приблизи- тельно к этому сроку планирует построить суперкомпьютер на 10 Пфлопс - 11 - (японцев легко понять – в условиях повышенной сейсмической активности крайне важно уметь предсказывать как сами землетрясения, так и их послед- ствия – напр., цунами). Вычислительные мощности отечественных супер-ЭВМ (список ‘Top-50’) c 2002 г. возглавлял комплекс МВС-1000М МСЦ (768 процессоров Alpha 21264A 667 MHz, пиковая производительность 1 Tфлопс); в середине 2005 г. он на четвертом месте. На третьем - кластер ANT (НИВЦ МГУ, http://parallel.ru/cluster/ant-config.html ), на втором – кластерная система СКИФ К- 1000 Объединенного института информационных проблем, Беларусь ( http://www.skif.bas-net.by ), на первом – система МВС-15000 МСЦ РАН (про- изводительность по LINPACK равна 3,1 Тфлопс, пиковая 4,9 Тфлопс). Все возглавляющие списки ‘Top-500’ и ‘Top-50’ вычислительные системы реализуют принцип параллельных вычислений, вследствие чего именно это принцип создания суперпроизводительных компьютеров в настоящее время считается наиболее перcпективным. Для очистки совести необходимо отметить, что существуют аргументы против широкого практического применения параллельных вычислений [3,4]: • Параллельные вычислительные системы чрезмерно д о роги. По подтверждаемому практикой закону Гроша (Herb Grosch, 60-е г.г.), производительность компьютера растет пропорционально квадрату его стоимости; в результате гораздо выгоднее по- лучить требуемую вычислительную мощность приобретением одного производи- тельного процессора, чем использование нескольких менее быстродействующих процессоров. Контраргумент. Рост быстродействия последовательных ЭВМ не может продол- жаться бесконечно (потолок в настоящее время почти достигнут), компьютеры под- вержены быстрому моральному старению и необходимы частые финансовые затра- ты на покупку новых моделей. Практика создания параллельных вычислительных систем класса Beowulf ( http://www.beowulf.org ) ясно показала экономичность имен- но этого пути. • При организации параллелизма излишне быстро растут потери производительности. По гипотезе Минского (Marvin Minsky) достигаемое при использовании параллель- ной системы ускорение вычислений пропорционально двоичному логарифму от чис- ла процессоров (при 1000 процессорах возможное ускорение оказывается равным всего 10). Контраргумент. Привед е нная оценка ускорения верн а для распараллеливания определенных алгоритмов. Однако существует большое количество задач, при па- раллельном решении которых достигается близкое к 100% использованию всех имеющихся процессоров параллельной вычислительной системы. • Последовательные компьютеры постоянно совершенствуются. По широко известно- му (и подтверждаемому практикой) закону Мура (Gordon Moore, 1965) сложность (тесно связанная с быстродействием) последовательных микропроцессоров возрас- тает вдвое каждые 18 месяцев (исторически быстродействие ЭВМ увеличивалось на порядок каждое 5-летие), поэтому необходимая производительность может быть достигнута и на ‘обычных’ последовательных компьютерах. - 12 - Контраргумент. Аналогичное развитие свойственно и параллельным системам. Однако применение параллелизма позволяет получать необходимое ускорение вы- числений без ожидания разработки новых более быстродействующих процессоров. • Эффективности параллелизма сильно зависит характерных свойств параллельных систем. Все современные последовательные ЭВМ работают в соответствие с класси- ческой схемой фон-Неймана; параллельные системы отличаются существенным раз- нообразием архитектуры и максимальный эффект от использования параллелизма может быть получен при полном использовании всех особенностей аппаратуры (следствие - перен о с параллельных алгоритмов и программ между разными типами систем затруднителен, а иногда и невозможен). Контраргумент. При реально имеющемся разнообразии архитектур параллельных систем существуют и определенные ‘устоявшиеся’ способы обеспечения паралле- лизма (конвейерные вычисления, многопроцессорные системы и т.п.). Инвариант- ность создаваемого программного обеспечения обеспечивается при помощи исполь- зования стандартных программных средств поддержки параллельных вычислений (программные библиотеки PVM, MPI, DVM и др.). • За десятилетия эксплуатации последовательных ЭВМ накоплено огромное про- граммное обеспечение, ориентировано на последовательные ЭВМ; переработка его для параллельных компьютеров практически нереальна. Контраргумент. Если эти программы обеспечивают решение поставленных задач, то их переработка вообще не нужн а . Однако если последовательные программы не позволяют получать решение задач за приемлемое время или же возникает необхо- димость решения новых задач, то необходима разработка нового программного обеспечения и оно изначально может реализовываться в параллельном исполнении. • Существует ограничение на ускорение вычисление при параллельной реализации алгоритма по сравнению с последовательной (закон Амдаля, связывающий величину этого ускорения с долей вычислений, которые невозможно распараллелить; подроб- нее о законе Амдаля см. ниже, подраздел 1.3) Контраргумент. В самом деле, алгоритмов вообще без (определенной) доли по- следовательных вычислений не существует. Однако это суть свойство алгоритма и не имеет отношения к возможности параллельного решения задачи вообще. Необхо- димо научиться применять новые алгоритмы, более подходящие для решения задач на параллельных системах. Т.о. на каждое критическое соображение против использования параллель- ных вычислительных технологий находится более или менее существенный контраргумент. Наиболее серьезным препятствием к применению технологий параллельных вычислений является все же (изначальная) нацеленность мышления современных алгоритмистов и программистов на строгую после- довательность выполнения вычислений; этому не препятствует даже осозна- ваемая (на разумном, но отнюдь не на подсознательном уровне) реальность широкого применения параллелизма в выполнении микрокоманд современ- ных процессоров даже в ПЭВМ. Очевидно, единственно реальным средством ‘перестройки мышления’ создателей программного обеспечения является практика параллельного программирования; при этом теоретические разра- ботки более чем полезны при совершенствовании технологий параллельного программирования. - 13 - 1.2 Параллельная обработка данных 1.2.1 Принципиальная возможность параллельной обработки Практически все разработанные к настоящему времени алгоритмы явля- ются последовательными. Например, при вычислении выражения c b a × + , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в ЭВМ присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет про- стаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину (разумеется, гипотетическую), которая заданный алгоритм будет обрабатывать парал- лельно ( * ). В самом деле, формула c b a × + фактически задает преобразование чи- сел a,b,c в некоторое другое число c b a r + + = (причем без конкретизации действий этого преобразования!). Без ограничений общности считаем, что числа a,b,c заданы в двоичной формуле; тогда речь идет о преобразовании некоторого набора нулей и единиц (битов), представляющих собой после- довательность чисел a,b,c в некоторый другой набор битов последовательно- сти r (результат вычисления). Возможно построить такое логическое уст- ройство, на вход которого поступает любая допустимая комбинация a,b,c, а на выходе сразу должна появиться комбинация, соответствующая результа- ту r. Согласно алгебре логики для любой функции можно построить дизъ- юнктивную нормальную формулу, тогда i-й двоичный разряд (i=1...n) резуль- тата r будет рассматриваться как логическая функция ) , , , , , ( 2 1 2 1 2 1 c c c b b b a a a r r n n n i i = , где c j b j a j , , являются двоичными разрядами, представляющими воз- можные значения a,b,c. Учитывая, что любая функция r i (любой i-тый разряд двоичного r, i=1...m,где m - число разрядов результата) может быть представлена дизъюнктивной нормальной формулой с участием логи- ческих операций ‘И’, ‘ИЛИ’, ‘НЕ’, можно построить m процессоров (m ло- гических схем, по одной для каждого бита числа r), которые при одновре- * Королев Л.Н. Структуры ЭВМ и их математическое обеспечение. –M.: Наука, 1978, -352 c. - 14 - менной работе выдают нужный результат за один-единственный такт ра- боты вычислителя. Такие ‘многопроцессорные’ машины теоретически можно построить для каждого конкретного алгоритма и, казалось бы, ‘обойти’ последо- вательный характер алгоритмов. Однако не все так просто - конкретных алгоритмов бесконечно много, поэтому развитые выше абстрактные рассу- ждения имеют не столь прямое отношение к практической значимости. Их развитие убедило в самой возможности распараллеливания, явилось основой концепции неограниченного параллелизма, дало возможность рассматривать с общих позиций реализацию т.н. вычислительных сред - многопроцессор- ных систем, динамически настраиваемых под конкретный алгоритм. 1.2.2 Абстрактные модели параллельных вычислений Модель параллельных вычислений обеспечивает высокоуровневый подход к определению характеристик и сравнению времени выполнения различных программ, при этом абстрагируются от аппаратного обеспечения и деталей выполнения. Первой важной моделью параллельных вычислений явилась машина с параллельным случайным доступом (PRAM, Parallel Random Ac- cess Machine), которая обеспечивает абстракцию машины с разделяемой па- мятью (PRAM является расширением модели последовательной машины с произвольным доступом RAM - Random Access Machine). Модель BSP (Bulk Synchronous Parallel, массовая синхронная параллельная) объединяет абст- ракции как разделенной, так и распределенной памяти. В LogP моделируются машины с распределенной памятью и некоторым способом оценивается стоимость сетей и взаимодействия. Модель работы и глубины NESL основа- на на структуре программы и не связана с аппаратным обеспечением, на ко- тором выполняется программа. PRAM (Fortune, Wyllie, 1978) является идеализированной моделью син- хронной машины с разделяемой памятью. Постулируется, что все процессо- ры выполняют команды синхронно; в случае выполнения одной и той же ко- манды PRAM является абстрактной SIMD-машиной, однако процессоры мо- гут выполнять и различные команды. Основными командами являются счи- тывание из памяти, запись в память и обычные логические и арифметиче- ские операции. Модель PRAM идеализирована в том смысле, что каждый процессор в лю- бой момент времени может иметь доступ к любой ячейке памяти (идеоло- гема ‘Операции записи, выполняемые одним процессором, видны всем ос- тальным процессорам в том порядке, в каком они выполнялись, но операции записи, выполняемые разными процессорами, могут быть видны в произ- вольном порядке’). Например, каждый процессор в PRAM может считывать данные из ячейки памяти илизаписывать данные в эту же ячейку. На ре- - 15 - альных параллельных машинах такого, конечно, не бывает, поскольку моду- ли памяти на физическом уровне упорядочивают доступ к одной и той же ячейке памяти. Более того, время доступа к памяти на реальных машинах не- одинаково из-за наличия кэшей и возможной иерархической организации модулей памяти. Базовая модель PRAM поддерживает конкуррентные (в данном контексте - параллельные) считывание и запись (CRCW, Concurrent Read, Concurrent Write). Известны подмодели PRAM, учитывающие правила, позволяющие избежать конфликтных ситуаций при одновременном обращении нескольких процессоров к общей памяти: • Параллельное считывание при параллельной записи(CRCW, Concurrent Read, Concurrent Write) – данные каждой ячейки памяти в любой момент времени могут считываться и записываться параллельно любыми про- цессорами. • Параллельное считывание при исключительной записи(CREW, Concur- rent Read, Exclusive Write) - из каждой ячейки памяти в любой момент времени данные могут считываться параллельно любыми процессорами, но записываться только одним процессором. • Параллельное считывание при исключительной записи(ERCW, Exclusive Read, Concurrent Write) - из каждой ячейки памяти в любой момент вре- мени данные могут считываться только одним процессором, однако запи- сываться параллельно несколькими. • Исключительное считывание при исключительной же записи(EREW, Exclusive Read, Exclusive Write) - каждая ячейка памяти в любой момент времени доступна только одному процессору. Эти модели более ограничены (и, само собой, более реалистичны), однако и их трудно реализовать на практике. Даже же при этом модель PRAM и ее подмодели полезны для анализа и сравнения параллельных алгоритмов. Вер- сией модели PRAM с обменом сообщениями является BPRAM. В модели массового синхронного параллелизма BSP (Valiant, 1990) син- хронизация отделена от взаимодействия и учтены влияния иерархии памяти и обмена сообщениями. Модель BSP включает три компонента: • Процессоры, имеющие локальную память и работающие с одинаковой скоростью. • Коммуникационная сеть, позволяющая процессорам взаимодействовать друг с другом. • Механизм синхронизациивсех процессоров через регулярные отрезки времени. - 16 - Параметрами модели являются число процессоров и их скорость, стои- мость взаимодействия и период синхронизации. Вычисление в BSP состоит из последовательности сверхшагов. На каждом отдельном сверхшаге процес- сор выполняет вычисления, которые обращаются к локальной памяти и отправляет сообщения другим процессорам. Сообщения являются запросами на получение копии (операция чтения) или на обновление (запись) удален- ных данных. В конце сверхшага процессоры выполняют барьерную синхронизацию и только затемобрабатывают запросы, полученные в течение данного сверхшага; далее процессоры переходят к выполнению следующего сверхшага. Первоначально предложенная в качестве интересной абстрактной модели, BSP позднее стала моделью программирования. Напр., в Оксфордском уни- верситете ( http://www.osc.ox.ac.uk ) реализована библиотека взаимодействия и набор протоколирующих инструментов, основанные на модели BSP. Эта библиотека содержит около 20 функций, в которых поддерживается постули- руемый BSP-стиль обмена сообщениями и удаленный доступ к памяти. Под- модель E-BSP является расширением BSP, учитывающая несбалансирован- ность схем взаимодействия. Более современной является модель LogP (David Culler, 1996), т.к. она учитывает характеристики машин с распределенной памятью и содержит больше деталей, связанных со свойствами выполнения в коммуникационных сетях, нежели модель BSP. Процессы в LogP рассматриваются как асинхрон- ные, а не синхронные. Компонентами модели являются процессоры, локаль- ная память и соединительная сеть; свое название модель получила от про- писных букв своих параметров: • L-верхняя граница задержки (Latency) при передаче от одного процессо- ра к другому сообщения, состоящего из одного слова. • о- накладные расходы (overhead), которые несет процессор при передаче сообщения (в течение этого промежутка времени процессор не может вы- полнять иные операции). • g-минимальный временн |