Параллельные вычисления
 Скачать 1.75 Mb.
|
|
МГУПИ ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ Кафедра ‘Персональные компьютеры и сети’ Баканов В.М. ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ Учебное пособие Москва, 2006 - 2 - УДК 681.3 Параллельные вычисления: Учебное пособие / В.М.Баканов; МГУПИ. Моск- ва, 2006. -124 с. Рекомендовано Ученым Советом МГУПИ в качестве учебного пособия для специальности ‘Вычислительные машины, комплексы, системы и сети’. Данное пособие предназначено для студентов III-V курсов, обучающихся по курсу ‘Параллельные вычисления’ или создающих программное обеспе- чение (ПО) указанного класса в среде различных операционных систем (ОС) и может быть применено в качестве конспекта лекций и для самостоятельной работы (содержит ссылки на дополнительные источники информации, в т.ч. сети InterNet). При изучении пособия необходимо знание основ алгоритмиза- ции и языков программирования высокого уровня (желательно С/Fortran). В пособии изложены требования науки и промышленности, приводящие к использованию суперкомпьютерных систем (подавляющее большинство ко- торых в настоящее время используют принцип параллельности вычислений), история вопроса и современное состояние проблемы, описаны основные подходы к организации многопроцессорных вычислительных систем, разра- ботке параллельных алгоритмов численного решения задач и технологий па- раллельного программирования. Taбл.6. Ил.30. Библиограф.:10 назв. Печатается по решению Редакционно-издательского совета Московского государственного университета приборостроения и информатики. Автор: профессор, д.т.н. Баканов В.М. Рецензент: профессор, д.т.н. Ульянов М.В. Научный редактор: профессор, д.т.н. Михайлов Б.М. Заведующий кафедрой ИТ-4 профессор, д.т.н. Б.М.Михайлов Баканов В.М., 2006 © - 3 - Содержание Стр. Введение ................................................................................................. 1 Общие вопросы решения ‘больших задач’………………………. 1.1 Современные задачи науки и техники, требующие для реше- ния суперкомпьютерных мощностей..…………………….…….… 1.2 Параллельная обработка данных………………………………... 1.2.1 Принципиальная возможность параллельной обработки…… 1.2.2 Абстрактные модели параллельных вычислений………….… 1.2.3 Способы параллельной обработки данных, погрешность вы- числений……………………………………………………….……… 1.3 Понятие параллельного процесса и гранулы распараллелива- ния………………………………………………………………….……... 1.4 Взаимодействие параллельных процессов, синхронизация процессов………………………………………………………………… 1.5 Возможное ускорение при параллельных вычислениях (закон Амдаля).………………………………………………………………….. 2 Принципы построения многопроцессорных вычислительных систем……………………………………………………………………. 2.1 Архитектура многопроцессорных вычислительных систем….. 2.2 Распределение вычислений и данных в многопроцессорных вычислительных системах с распределенной памятью………………. 2.3 Классификация параллельных вычислительных систем……… 2.4 Многопроцессорные вычислительные системы c распределен- ной памятью......................…………………………………………… 2.4.1 Массивно-параллельные суперкомпьютеры серии Cray T3… 2.4.2 Кластерные системы класса BEOWULF……………………… 2.4.3 Коммуникационные технологии, используемые при создании массово-параллельных суперкомпьютеров………………………. 2.4.3.1 Транспьютерные системы…………………………………… 2.4.3.2 Универсальные высокопроизводительные коммуникацион- ные сети: производительность, латентность и цена обмена ……… 2.4.4 Стандартные программные пакеты организации вычисли- тельных кластеров……………………………….………………………. 2.5 Нетрадиционные архитектуры многопроцессорных вычисли- тельных систем…………………………………………………………… 2.6. Метакомпьютинг и GRID-системы…………………………….. 3 Анализ алгоритмов с целью выявления параллелизма………….. 3.1 Представление алгоритма графовой структурой………………. 3.2 Потенциал распараллеливания циклов. Циклы ParDO………... - 4 - 3.3 Эквивалентные преобразования алгоритмов, избыточность вычислений и обменов данными ………………………………………. 4 Технологии параллельного программирования…………………. 4.1 Дополнения известных последовательных алгоритмических языков средствами параллельного программирования ……………… 4.2 Системы параллельного программирования на основе обмена сообщениями…………………………………………………………….. 4.3 Автоматизация распараллеливания алгоритмов………………... 4.3.1 Распараллеливающие компиляторы………………………….. 4.3.2 Автоматическое распараллеливание с помощью Т-системы.. 4.3.3 Непроцедурный декларативный язык НОРМА……………… 4.4 Стандартные предметно-ориентированные библиотеки парал- лельных вычислений………………………………………………… 4.5 Параллелизм в системах управления базами данных…………. Заключение.............................................................................................. Список использованной литературы.................................................... Приложения…………………………………………………………… - 5 - Введение Одной из явно прослеживаемых тенденций развития человечества является желание максимально строго моделировать процессы окружающей действи- тельности с целью как улучшения условий жизни в настоящем, так и макси- мально достоверного предсказания будущего (со сходной, впрочем, конечной целью). Математические методы и приемы цифрового моделирования во многих случаях позволяют разрешать подобные проблемы, однако с течени- ем времени имеет место серьезное усложнение (как качественное, так и коли- чественное) технологии решения задач. Во многих случаях ограничением яв- ляется недостаток вычислительных мощностей современных ЭВМ; значи- мость решаемых задач привлекли огромные финансовые ресурсы в область создания сверхсложных ЭВМ, стоимость разработок которых достигает со- тен миллионов долларов. Однако с некоторых пор повышение быстродействия компьютеров тради- ционной (именуемой ‘фон Неймановской’ и фактически обобщающей ре- зультаты исследований английских коллег-союзников и разработки нахо- дившегося тогда в США на положении консультанта-военнопленного Конра- да фон Цузе) архитектуры стало чрезмерно дорого вследствие технологиче- ских ограничений при производства процессоров, поэтому разработчики об- ратили внимание на иной путь повышения производительности – комплекси- рование ЭВМ в многопроцессорные вычислительные системы (МВС); при этом отдельные фрагменты программы параллельно (и одновременно) вы- полняются на различных процессорах, обмениваясь при этом информацией посредством внутренней компьютерной сети. Идея комплексирования ЭВМ с целью повышения как производительности так и надежности почти так же стара как компьютерный мир (документиро- ванные объединения ЭВМ известны с конца 50-х г.г.). Требования получить максимум производительности при минимальной стоимости привели к разработке многопроцессорных вычислительных ком- плексов (напр., в форме вычислительных кластеров на базе недорогих ком- понентов персональных ЭВМ); известны системы такого рода, объединяю- щие вычислительные мощности тысяч отдельных процессоров. Следующим этапом являются попытки объединить миллионы разнородных компьютеров планеты в единый вычислительный комплекс с огромной производительно- стью (технология распределенных вычислений, метакомпьютинга) посредст- вом сети InterNet. На сегодняшний день применение параллельных вычисли- тельных систем (ПВС) является стратегическим направлением развития вы- числительной техники. Развитие ‘железа’ с необходимостью подкрепляются совершенствованием алгоритмической и программной компонент - техноло- гий параллельного программирования (ТПП). - 6 - Хотя идея распараллеливания вычислений отнюдь не нова (принцип кон- вейера при обработке данных внутри конкретного процессора широкоизвес- тен), организация совместного функционирования множества независимых процессоров требует проведения серьезных теоретико-практических иссле- дований, без которых сложная и относительно дорогостоящая многопроцес- сорная установка часто не только не превосходит, а уступает по производи- тельности традиционному компьютеру. Потенциальная возможность распараллеливания неодинакова для вычис- лительных задач различного типа – она значительна для научных программ, содержащих много циклов и длительных вычислений и существенно меньше для инженерных задач, для которых характерен расчет по эмпирическим формулам. Выделенные курсивом текстовые последовательности фактически являются ключевыми словами для поиска их значений в InterNet, использование явно заданных InterNet-ссылок неминуемо приведет настойчивого читателя к пер- воисточнику информации. В сносках к конкретной странице приведена до- полнительная литература, полезная при изучении материала. - 7 - 1 Общие вопросы решения ‘больших задач’ Под термином ‘большие задачи’ обычно понимают проблемы, решение ко- торых требует не только построения сложных математических моделей, но и проведения огромного, на многие порядки превышающие характерные для ПЭВМ, количества вычислений (с соответствующими ресурсами ЭВМ – раз- мерами оперативной и внешней памяти, быстродействием линий передачи информации и др.). Заметим, что (практический) верхний предел количества вычислений для ‘больших задач’ определяется (при одинаковом алгоритме, эффективности и стойкости к потере точности которого при вычислениях) лишь производи- тельностью существующих на данный момент вычислительных систем. При ‘прогонке’ вычислительных задач в реальных условиях ставится не вопрос ‘решить задачу вообще’, а ‘решить за приемлемое время’ (десятки/сотни ча- сов). 1.1 Современные задачи науки и техники, требующие для решения суперкомпьютерных мощностей Нижеприведены некоторые области человеческой деятельности, где воз- никают задачи подобного рода, часто именуемые проблемами класса GRAND CHALLENGES (имеется в виду вызов окружающему миру) - фун- даментальные научные или инженерные задачи с широкой областью приме- нения, эффективное решение которых реально исключительно с использова- нием мощных (суперкомпьютерных, неизбежно использующих параллельные вычисления) вычислительных ресурсов [1]: • Предсказания погоды, климата и глобальных изменений в атмосфере • Науки о материалах • Построение полупроводниковых приборов • Сверхпроводимость • Структурная биология • Разработка фармацевтических препаратов • Генетика человека • Квантовая хромодинамика • Астрономия • Транспортные задачи большой размерности • Гидро- и газодинамика • Управляемый термоядерный синтез • Эффективность систем сгорания топлива • Разведка нефти и газа • Вычислительные задачи наук о мировом океане - 8 - • Раcпознавание и синтез речи, раcпознавание изображений Одна из серьезнейших задач – моделирование климатической системы и предсказание погоды. При этом совместно численно решаются уравнения динамики сплошной среды и уравнения равновесной термодинамики. Для моделирования развития атмосферных процессов на протяжении 100 лет и числе элементов дискретизации 2,6 × 10 6 (сетка с шагом 1 О по широте и дол- готе по всей поверхности Планеты при 20 слоях по высоте, состояние каждо- го элемента описывается 10 компонентами) в любой момент времени состоя- ние земной атмосферы описывается 2,6 × 10 7 числами. При шаге дискретиза- ции по времени 10 мин за моделируемый промежуток времени необходимо определить ≈ 5 × 10 4 ансамблей (т.е. 10 14 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получе- ния каждого промежуточного результата вычислительных операций в 10 2 ÷ 10 3 общее число необходимых для проведения численного эксперимен- та с глобальной моделью атмосферы вычислений с плавающей точкой дохо- дит до 10 16 ÷ 10 17 . Суперкомпьютер с производительностью 10 12 оп/сек при идеальном случае (полная загруженность и эффективная алгоритмизация) будет выполнять такой эксперимент в течение нескольких часов; для прове- дения полного процесса моделирования необходима многократная (десят- ки/сотни раз) прогонка программы [1]. Конкретным примером большой программы в этой области может служить программа ‘Ядерная зима’ для отечественной БЭСМ-6, в которой моделиро- вался климатический эффект ядерной войны (акад. Н.Н.Моисеев и В.А Алек- сандров, ВЦ Академии наук); проведенные с помощью этой программы ис- следования способствовали заключению соглашений об ограничении страте- гических вооружений ОСВ-1 (1972) и ОСВ-2 (1979). Известный Earth Simulator (Япония, см. ниже) интенсивно применяется при моделиро- вании поведения ‘озоновой дыры’ над Антарктидой (появление которой счи- талось следствием выброса в атмосферу хлорфторуглеродных соединений). При подготовке Киотского протокола (соглашение о снижении промышлен- ных выбросов парниковых газов в целях противодействию катастрофическо- го потепления климата Планеты) также широко использовалось моделирова- ние с помощью супер-ЭВМ. Огромные вычислительные ресурсы требуются при моделировании ядер- ных взрывов, оконтуривании месторождений, обтекания летательных и под- водных аппаратов, молекулярных и генетических исследованиях и др. Проблема супервычислений столь важна, что современной мировой тен- денцией является жесткое курирование работ в области суперкомпьютер- ных технологий государством: пример - объединяющая три крупнейшие на- циональные лаборатории (Лос-Аламос, Ливермор, Sandia) американская пра- - 9 - вительственная программа ‘Ускоренная стратегическая компьютерная ини- циатива’ (ASCI, Accelerated Strategic Computing Initiative, http://www.llnl.gov/asci ), программы NPACI (National Partnership for Advanced Computational Infrastructure, http://www.npaci.edu ), CASC (Coalition of Aca- demic Supercomputing Centers, http://www.osc.edu/casc.html ) и др. Государствен- ная поддержка прямо связана с тем, что независимость в области производст- ва и использования вычислительной техники отвечает интересам националь- ной безопасности, а научный потенциал страны непосредственно связан и в большой мере определяется уровнем развития вычислительной техники и ма- тематического обеспечения. Так, в рамках принятой в США еще в 1995 г. программы ASCI ставилась задача увеличения производительности супер-ЭВМ в 3 раза каждые 18 меся- цев и достижение уровня производительности в 100 триллионов (100 × 10 12 ) операций с плавающей точкой в секунду (100 Терафлопс) к 2004 г. (для срав- нения – наиболее мощные ‘персоналки’ имеют производительность не более 1 Гигафлопс). С целью объективности при сравнении производительность супер-ЭВМ рассчитывается на основе выполнения заранее известной тестовой задачи (‘бенчмарка’, от англ. benchmark); в качестве последней обычно используется тест LINPACK ( http://www.netlib.org/utk/people/JackDongarra/faq-linpack.html ), предполагающий решение плотнозаполненных систем линейных алгебраиче- ских уравнений (СЛАУ) большой размерности методом исключения Гаусса (другой метод не допускается) с числами с плавающей точкой двойной точ- ности (число выполняемых операций при этом априори известно и равно n n 2 3 2 3 / 2 × + × , где n – порядок матрицы, обычно n ≥ 1000; такой тест выбран вследствие того, что большое количество практических задач сводится имен- но к решению СЛАУ большой ( 10 0 1 6 4 ÷ ≈ n ) размерности. Для параллельных машин используется параллельная версия LINPACK – пакет HPL (High Performance Computing Linpack Benchmark, http://www.netlib.org/benchmark/hpl ). LINPACK-производительность вычисляется как t / n n R max 2 3 3 2 + × = , где t – время выполнения теста (время выполнения сложений и умножений прини- мается одинаковым). Пиковое (максимальное) быстродействие в общем слу- чае определяется в виде t γ p R i k i i i peak ∑ = = = 1 , где p — число процессоров или АЛУ; k — число различных команд в списке команд ЭВМ, γ i - удельный вес команд i-го типа в программе, t i — время выполнения команды типа i; веса команд определяются на основе сбора статистики по частотам команд в реальных программах (известны стандартные смеси команд Гибсона, Флин- на и др.), обычно R R peak max × = ÷0,95) (0,5 . Т.о. пиковая производительность - 10 - определяется максимальным числом операций, которое может быть выпол- нено за единичное время при отсутствии связей между функциональными устройствами, характеризует потенциальные возможности аппаратуры и (вообще говоря) не зависит от выполняемой программы. Именно на основе LINPACK-теста регулярно составляются мировой спи- сок наиболее быстродействующих вычислительных систем ‘Top-500’ ( http://www.top500.org ) в мире и внутри российский список ‘Top-50’ ( http://www.supercomputers.ru ). Более приближенным к реальным задачкам яв- ляется набор тестов NPB (NAS Parallel Benchmarks, http://www.nas.nasa.gov/NAS/NPB ). Недостатком метода оценки пиковой производительности как числа вы- полняемых компьютером команд в единицу времени (MIPS, Million Instruc- tion Per Second) дает только самое общее представление о быстродействии, т.к. не учитывает специфику конкретных программ (априори трудно предска- зуемо, в какое число и каких именно инструкций процессора отобразится пользовательская программа). Введенная в строй еще в 1999 г. в Sandia National Laboratories многопро- цессорная система ASCI Red (Intel Paragon, США) имеет предельную (п |