WWW.DISSERS.RU

БЕСПЛАТНАЯ ЭЛЕКТРОННАЯ БИБЛИОТЕКА

   Добро пожаловать!


Pages:     || 2 | 3 | 4 | 5 |   ...   | 17 |
ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ МГУПИ МОСКОВСКИЙ ГОСУДАРСТВЕННЫЙ УНИВЕРСИТЕТ ПРИБОРОСТРОЕНИЯ И ИНФОРМАТИКИ Кафедра ‘Персональные компьютеры и сети’ Баканов В.М.

ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛЕНИЯ Учебное пособие Москва, 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,6106 (сетка с шагом 1О по широте и долготе по всей поверхности Планеты при 20 слоях по высоте, состояние каждого элемента описывается 10 компонентами) в любой момент времени состояние земной атмосферы описывается 2,6107 числами. При шаге дискретизации по времени 10 мин за моделируемый промежуток времени необходимо определить 5104 ансамблей (т.е. 1014 необходимых числовых значений промежуточных вычислений). При оценке числа необходимых для получения каждого промежуточного результата вычислительных операций в 102 103 общее число необходимых для проведения численного эксперимента с глобальной моделью атмосферы вычислений с плавающей точкой доходит до 1016 1017. Суперкомпьютер с производительностью 1012 оп/сек при идеальном случае (полная загруженность и эффективная алгоритмизация) будет выполнять такой эксперимент в течение нескольких часов; для проведения полного процесса моделирования необходима многократная (десятки/сотни раз) прогонка программы [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 Academic Supercomputing Centers, http://www.osc.edu/casc.html) и др. Государственная поддержка прямо связана с тем, что независимость в области производства и использования вычислительной техники отвечает интересам национальной безопасности, а научный потенциал страны непосредственно связан и в большой мере определяется уровнем развития вычислительной техники и математического обеспечения.

Так, в рамках принятой в США еще в 1995 г. программы ASCI ставилась задача увеличения производительности супер-ЭВМ в 3 раза каждые 18 месяцев и достижение уровня производительности в 100 триллионов (1001012) операций с плавающей точкой в секунду (100 Терафлопс) к 2004 г. (для сравнения – наиболее мощные ‘персоналки’ имеют производительность не более 1 Гигафлопс).

С целью объективности при сравнении производительность супер-ЭВМ рассчитывается на основе выполнения заранее известной тестовой задачи (‘бенчмарка’, от англ. benchmark); в качестве последней обычно используется тест LINPACK (http://www.netlib.org/utk/people/JackDongarra/faq-linpack.html), предполагающий решение плотнозаполненных систем линейных алгебраических уравнений (СЛАУ) большой размерности методом исключения Гаусса (другой метод не допускается) с числами с плавающей точкой двойной точности (число выполняемых операций при этом априори известно и равно 2 / 3 + 2, где n – порядок матрицы, обычно n 1000; такой тест выбран n3 nвследствие того, что большое количество практических задач сводится именно к решению СЛАУ большой ( n ) размерности. Для параллельных 104 машин используется параллельная версия LINPACK – пакет HPL (High Performance Computing Linpack Benchmark, http://www.netlib.org/benchmark/hpl).

n3 n2, где t – / 3 + LINPACK-производительность вычисляется как = Rmax t время выполнения теста (время выполнения сложений и умножений принимается одинаковым). Пиковое (максимальное) быстродействие в общем слуi=k чае определяется в виде = p R i ti, где p — число процессоров или peak i=i АЛУ; k — число различных команд в списке команд ЭВМ, - удельный вес команд i-го типа в программе, ti — время выполнения команды типа i;

веса команд определяются на основе сбора статистики по частотам команд в реальных программах (известны стандартные смеси команд Гибсона, ФлинRmax на и др.), обычно = (0,50,95) R. Т.о. пиковая производительность peak - 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).

Pages:     || 2 | 3 | 4 | 5 |   ...   | 17 |










© 2011 www.dissers.ru - «Бесплатная электронная библиотека»

Материалы этого сайта размещены для ознакомления, все права принадлежат их авторам.
Если Вы не согласны с тем, что Ваш материал размещён на этом сайте, пожалуйста, напишите нам, мы в течении 1-2 рабочих дней удалим его.