ФЕДЕРАЛЬНОЕ АГЕНТСТВО ПО ОБРАЗОВАНИЮ

ГОСУДАРСТВЕННОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ

ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ

«САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ

УНИВЕРСИТЕТ имени академика С.П.КОРОЛЕВА»

В.П. Гергель, В.А. Фурсов

ЛЕКЦИИ ПО ПАРАЛЛЕЛЬНЫМ ВЫЧИСЛЕНИЯМ

Утверждено Редакционно-издательским советом университета в качестве учебного пособия

САМАРА

Издательство СГАУ 2009 УДК СГАУ: 519.6(075) ББК 22.19 Г 375 Рецензенты: д-р техн. наук, проф. Ю. Я. Б о л д ы р е в канд. техн. наук, доц. С.Б. П о п о в Гергель В.П.

Г 375 Лекции по параллельным вычислениям: учеб. пособие / В.П. Гергель, В.А.Фурсов. – Самара: Изд-во Самар. гос. аэрокосм. ун-та, 2009. – 164 с.

ISBN 0-00000-000-X ISBN 978-5-7883-0739- Излагаются основы построения параллельных алгоритмов, ориентированных для реализации на многопроцессорных вычислительных системах. Приводятся примеры распараллеливания алгоритмов для решения простейших задач.

Для большинства примеров приводятся оценки достижимого ускорения и показателей эффективности (загрузки процессоров). Примеры завершаются построением временной диаграммы параллельного алгоритма, которая, по существу, является расписанием реализации параллельного алгоритма и исходной моделью для составления соответствующей программы.

Учебное пособие ориентировано в основном на начальную подготовку, например, студентов в рамках программ подготовки бакалавров, слушателей ФПКП и других категорий учащихся, приступающих к освоению технологий параллельных вычислений.

Учебное пособие может быть полезно также при проведении прикладных научных исследований, выполнении курсовых и дипломных проектов по физико-математическим и техническим направлениям подготовки.

УДК СГАУ: 519.6(075) ББК 22. Самарский государственный ISBN 978-5-7883-0739- аэрокосмический университет,

ВВЕДЕНИЕ

В последние годы усиливается внимание к использованию высокопроизводительной вычислительной техники в научных исследованиях и образовании.

Связано это с тем, что во многих областях знаний фундаментальные научные исследования связаны с необходимостью проведения масштабных численных экспериментов. Общая тенденция состоит в том, что происходит концентрация вычислительных ресурсов в центрах коллективного пользования и развитие инфраструктуры удаленного доступа с использованием средств телекоммуникаций. Это требует, чтобы большое число специалистов в разных областях владели современными технологиями работы как на многопроцессорных системах удаленных суперкомпьютерных центров, так и на персональных миникластерах.

В последние годы появились замечательные книги [2,3], которые позволили в какой-то степени снять проблему недостатка в учебных пособиях. Вместе с тем массовая подготовка специалистов, в особенности переход на двухступенчатую подготовку бакалавр-магистр (с крайне малым числом часов аудиторных занятий), потребовала издания более компактного и вместе с тем достаточно доступного для самостоятельной подготовки пособия. Другая важная отличительная черта настоящего учебного пособия состоит в следующем.

Подготовка задачи к решению на параллельном компьютере заключается в составлении плана вычислений и составлении кода. Для составления эффективного плана вычислений обычно требуется глубокое понимание существа задачи, а для написания соответствующего некоторому плану вычислений эффективного кода требуется глубокое знание особенностей построения вычислительной системы. В частности, требуется знание топологии связей, типа процессора, относительных объемов памяти кэшей различных уровней и др. К сожалению, специалистов, одинаково глубоко владеющих как предметом исследований в «своей» области знаний, так и знаниями в области высокопроизводительных вычислительных систем, не так много.

В последние годы предпринимаются усилия по расширению подготовки специалистов в области решения задач на многопроцессорных системах в рамках бакалавриата. Представляется, что решение этой проблемы более эффективно путем полной «развязки» параллельных вычислений и параллельного программирования. Настоящее учебное пособие является такой попыткой. В нем подчеркнуто не используются термины «программа» и «программирование», а анализ параллельных алгоритмов завершается составлением временной диаграммы его выполнения. Для того чтобы сделать диаграммы полностью понятными программисту, который не владеет существом прикладной задачи, авторы «модернизировали» обычно используемые диаграммы [1]. В частности, в них в явном виде введены нумерация процессоров и связи между процессами в виде номеров входных, выполняемых и выходных операторов.

Указанная особенность построения учебного пособия, кроме прочего, позволяет начать изучение вопросов организации параллельных вычислений до того, как изучен какой-либо алгоритмический язык. Это создает дополнительные удобства в реализации учебного плана. Такой подход может представлять интерес и для научных работников. Процесс создания параллельных приложений может быть более эффективным, если организовать своеобразный конвейер: математическая постановка задачи (1), структурный анализ алгоритма и построение плана вычислений (2), написание кода (3), отладка программы (4). Ясно, что методики, обеспечивающие возможность реализовывать каждый из указанных этапов независимо, обеспечат более быстрое и притом более качественное решение задачи.

Учебное пособие ориентировано в основном на начальную подготовку студентов в рамках программ подготовки бакалавров, слушателей ФПКП и других категорий учащихся, приступающих к освоению технологий параллельных вычислений, но может быть полезным также при выполнении курсовых и дипломных проектов, а также при проведении прикладных научных исследований, связанных с подготовкой параллельных приложений.

Лекция История и значение вычислений 1.1. Предыстория ЭВМ и связанные с ней выводы В последние годы усиливается внимание к использованию высокопроизводительной вычислительной техники. Возникает естественный вопрос: является ли это объективной потребностью общества или это лишь модное движение.

Как долго продлится эта затянувшаяся гонка производительностей? Не является ли эта гонка своего рода соревнованием престижности, которое лишь истощает ресурсы общества. Для того чтобы ответить на эти вопросы, полезно «заглянуть» в историю вычислений.

Кратко перечислим некоторые наиболее известные, типы инструментов и машин, использовавшихся до эпохи ЭВМ и основанных на механических и электромеханических принципах [4].

Механические вычислители:

Абак и счеты, логарифмическая линейка (1617).

Вычислительная машина Паскаля (1642).

Разностная и аналитическая машина Бэбиджа (1834).

Арифмометр Лейбница (1673).

Арифмометр Однера (1876) («Феликс»).

Электромеханические вычислители:

Табулятор Холлерита(1887).

Машинно-счетные станции.

Проекты Конрада Цузе (Германия, 1938-1945).

Проект MARK-1 (Эйкен, IBM, 1939-1944).

Проекты Джорджа Стибица (Bell Laboratories, 1939-1947).

Что же двигало создателями этих машин и инструментов? Известно, что поистине революционный шаг: создание первой вычислительной машины, юный Блез Паскаль совершил, движимый желанием облегчить арифметические вычисления отца – сборщика налогов. Конечно, для этого он должен был обладать необходимыми материальными ресурсами. Надо полагать, что семья сборщика налогов, по тем временам, была сравнительно обеспеченной, чтобы позволить сыну строить вычислительную машину.

Дальнейшие весьма важные усовершенствования вычислительной машины Паскаля были выполнены Лейбницем и Однером. Они также были продиктованы потребностями практики, в частности необходимостью совершенствования учета при сборе налогов. Значение, которое сыграли эти усовершенствования для ускорения вычислений, трудно переоценить. В СССР даже в 1969 году арифмометров «Феликс» было произведено 300000 шт.

Тем не менее, арифмометры не смогли обеспечить решение всех задач такой, например, актуальной задачи того времени – переписи населения. Например, итоги переписи 1880 года, когда население США составляло около 50 млн.

человек, были получены только через 7,5 лет. В ответ на эти новые вызовы появляется «машина для переписи населения» – табулятор Холлерита. В табуляторе на каждый объект переписи заводилась 80-колоночная перфокарта, в которой с помощью перфоратора в определенных позициях делались отверстия, отвечающие определенным значениям признаков. Применение табуляторов в 1890 году позволило сократить сроки обработки результатов переписи до двух лет. После этого спрос на машины для переписи не только в США, но и в других странах резко возрос, что обеспечило успех становления компании IBM.

Следующим важным практическим шагом в развитии вычислений было создание электромеханической машины MARK-1. При создании этой машины Говард Эйкен опирался на идеи неосуществленного проекта Бэббиджа. Это служит лишним подтверждением того факта, что новые идеи в развитии вычислительной техники находят практическое воплощение при появлении спроса на высокопроизводительные вычисления. Действительно, одной из основных причин успеха проекта MARK-1 была его востребованность: машина создавалась в интересах Военно-морского флота и использовалась для расчета артиллерийских таблиц. Таким образом, потребность плюс ресурсы (в создание машины MARK-1 компания IBM вложила 500000 долларов, проект также поддерживался правительством США и командованием Военно-морского флота) оказались решающими факторами в развитии высокопроизводительных, по тому времени, вычислений.

В настоящее время во многих областях знаний также возникает необходимость проведения масштабных вычислений, реализация которых возможна только на суперкомпьютерах. Если внимательно посмотреть на состояние современных наук, опирающихся на математику, нетрудно заметить следующую тенденцию. Ограничиваются возможности получения результатов только при помощи теоретического исследования. Связано это со сложностью аналитических моделей реальных процессов и явлений. При этом сравнимая, а чаще более высокая точность, может быть достигнута с использованием учитывающих большее число факторов, численных моделей. По-видимому, «развитие математики в определенный период времени отражает природу вычислительных средств, доступных в этот момент, в значительно большей степени, чем можно было бы предположить» [8, с.152].

Указанные тенденции вовсе не являются изобретением собственно математиков. Напротив, математики в данном случае пытаются найти рациональный ответ тем вызовам, которые возникли в современном обществе. Эти вызовы объективно существуют на нескольких уровнях.

1. Глобальные проблемы развития и сохранения цивилизаций (межгосударственный уровень). Примерами задач этого уровня являются моделирование климата, экологических процессов, прогнозирование космических явлений и др. Эти проблемы вполне осознаются сообществами ученых разных стран, а исследования поддерживаются развитыми странами и международными фондами.

2. Задачи поддержания высокого уровня национальной безопасности (государственный уровень). В данном случае высокопроизводительные вычислительные системы являются основой инфраструктуры, обеспечивающей военно-экономическое преимущество и оперативное реагирование на возможные угрозы.

3. Задачи расширения рынка и повышения конкурентоспособности товаров и услуг (производственный уровень). Известно, для того чтобы захватить рынок, надо опередить конкурентов. Наряду с совершенствованием организации производства, в данном случае основной резерв – это сокращение сроков проектирования и отработки новых образцов за счет моделирования на высокопроизводительных ЭВМ.

Таким образом, гонка производительностей ЭВМ является одним из необходимых факторов успешного развития постиндустриального общества.

1.2 История ЭВМ 1.2.1. Некоторые зарубежные решения Юридический приоритет создания первой ЭВМ принадлежит Джону Атанасову (Atanasoff, John; 1903-1995). В 1939 г. он с аспирантом Клиффордом Берри (Berry, Clifford Edward; 1918-1963) приступил к постройке машины, предназначенной для решения системы алгебраических уравнений с 30 неизвестными (ABC — Atanasoff-Berry Calculator). Проект не был завершен (в этом разделе используются сведения, приведенные в [4]).

Первая работающая ЭВМ ENIAC (Electronic Numerical Integrator And Calculator) была создана в 1945 г. в Пенсильванском университете. Длина 26 м, высота 6 м, масса 30 т. 18 000 ламп, 1500 реле, потребляемая мощность 150 кВт.

В годы Второй мировой войны под руководством выдающегося математика Алана Тьюринга была также построена специализированная электронная вычислительная машина Colossus. Она насчитывала 2000 радиоламп и обрабатывала 25000 симв./с В 1953 г. к производству ЭВМ общего назначения подключилась фирма IBM, выпустив серийную IBM-701. Быстродействие около 10000 оп./с, ОЗУ 2К 36-разрядных слов. Следующим, поистине революционным, шагом было создание вычислительной системы (mainframes) IBM-360 (апрель, 1964). Важнейшие особенности IBM System/360 следующие:

микросхемная элементная база;

микропрограммное управление;

внешняя память на магнитных дисках;

дисплейные терминалы;

открытая масштабируемая архитектура.

Важной отличительной чертой системы IBM-360 являлась возможность создавать комплексы «под заказ» в широком диапазоне производительностей.

Таким образом, отпала необходимость создавать майнфреймы. Это побудило производителей ЭВМ искать новые ниши как в направлении миниатюризации (мини-ЭВМ), так и в области создания супер-ЭВМ.

Первая супер-ЭВМ CDC-6600 была разработана Сеймуром Креем (Cray, Seimour; 1925-1996) и построена в фирме Control Data Corporation (1963 г.) Разрядность 64 бита, быстродействие 3 млн. оп./с.

Значительный скачок произошел также и в создании рынка мини-ЭВМ.

Наиболее известные решения в этом направлении: мини-ЭВМ PDP:

-5 (1963), первые модели ПК компаний MITS и Apple (Altair-1975, Apple-II, 1977); IBM-совместимые ПК (IBM PC XT - 1983, PC AT – 1984); Apple: Macintosh (1984).

Появление на рынке сравнительно дешевых и достаточно высокопроизводительных персональных компьютеров, с одной стороны, и развитие высокопроизводительных сетевых технологий, с другой стороны, обусловило появление высокопроизводительных вычислительных систем – кластеров. Круг замкнулся.

Основа этих достижений, вне всякого сомнения, была создана успехами в развитии элементной базы. Ниже приводится наглядная иллюстрация закона Мура, согласно которому количество элементов на одном кристалле удваивается каждые полтора года. Несмотря на то, что многими исследователями ощущается предел, обусловленный физическими законами, этот закон пока выполняется.

1.2.2 Развитие отечественных ЭВМ В развитии отечественной вычислительной техники можно выделить следующие важнейшие этапы: зарождение (1948 - 1952 годы); расцвет (1950-е – 1960-е годы); подражание (1970-е – 1980-е годы); кризис (1990-е годы).

Этап зарождения интересен и поучителен для нынешнего времени. Началось с того, что в 1950 году академик М.А. Лаврентьев написал письмо И.В. Сталину, в котором обратил внимание на важность вычислительных машин для обороны страны. В результате в удивительно короткие сроки были подготовлены соответствующие постановления правительства и началась разработка ЭВМ одновременно в Академии наук СССР и Министерстве машиностроения и приборостроения.

В результате уже в 1951 году появилась первая отечественная ЭВМ МЭСМ (1951 г., Киев), гл. конструктор С.А. Лебедев. Она имела следующие характеристики: 6000 электронных ламп, быстродействие 50 оп./с, ОЗУ 16-разрядных слов, потребляемая мощность 15 кВт, занимаемая площадь – 60 кв.м.

Первая полномасштабная отечественная ЭВМ БЭСМ (1952 г., Москва, ИТМ и ВТ), гл. конструктор С.А. Лебедев. Характеристики: 5000 ламп, быстродействие 8000 оп./с, ОЗУ 1К 39-разрядных слов, ПЗУ 1К слов, потребляемая мощность 30 кВт, занимаемая площадь 100 кв. м.

Первая отечественная серийная ЭВМ «Стрела» (1953 г.), гл. конструктор Ю.Я. Базилевский, зам. гл. конструктора Б.И. Рамеев. Характеристики: ламп, 60000 полупроводниковых диодов. Быстродействие 2000 оп./с, ОЗУ на потенциалоскопах (43-разрядные слова), потребляемая мощность 150 кВт, занимаемая площадь 300 кв. м. С 1953 до 1956 г. выпущено 7 экземпляров этих машин.

Серийная ЭВМ общего назначения М-20 (1958 г.), гл. конструктор С.А.Лебедев, имела следующие характеристики: 2600 ламп, ОЗУ 4К 45-разрядных слов, быстродействие 20 000 оп./с (в то время самое большое в Европе).

Серийная ЭВМ малого класса Урал -1 (1957 г., НИИММ, г. Пенза): электронных ламп, ОЗУ на магнитном барабане (1024 36-разрядных слов), быстродействие 100 оп./с. Семейство полупроводниковых ЭВМ среднего класса Урал -11,- 14, -16 (1964-1969 годы), гл. конструктор Б.И. Рамеев, имело унифицированную архитектуру, быстродействие от 45 до 100 тыс. оп./с.

ЭВМ БЭСМ-6 (1968 г.) наиболее мощная из отечественных машин 2-го поколения, гл. конструктор С.А. Лебедев. Характеристики: 60 тыс. транзисторов, 180 тыс. диодов, быстродействие 1 млн оп./с, ОЗУ от 32К до128К 48-разрядных слов. Производилась до 1987 г, всего выпущено 355 экз.

Машина инженерных расчетов МИР-1 (1966 г., ИК АН УССР, г. Киев), гл.

конструктор В.М.Глушков. Машина имела оригинальное многоступенчатое программное управление. Куплена фирмой IBM (1967 г.).

Полупроводниковая ЭВМ «Минск-32» (1968 г.) – последняя из семейства машин «Минск». Гл. конструктор В.В. Пржиялковский, характеристики: 30- тыс. оп./с, ОЗУ 64К 38-разрядных слов. До 1975 г. выпущено 2889 экземпляров.

Для сопоставления темпов развития вычислительной техники в России и за рубежом ниже приводится таблица, в которую включены некоторые наиболее успешные решения, которые оказали большое влияние на последующие этапы развития.

Таблица 1.1 Сопоставление отечественных и зарубежных ЭВМ 1952 БЭСМ 5000 ламп, 8000 оп./с, ОЗУ 1К IBM-701. 10000 оп./с, ОЗУ 2К 36разрядных слов, ПЗУ 1К слов разрядных слов (1952) 1953 «Стрела» 6200 ламп, 60000 п/п диоIBM- 1958 М-20 2600 ламп, ОЗУ 4К 45-разрядных IBM-7030 Stretch (1959 г.), 500 тыс.

1964 Урал -11,- 14, -16 45 до 100 тыс. оп./с. IBM System/360 (1964). Можно собрать 1968 БЭСМ-6 60 тыс. транзисторов, 180 тыс.

диодов,1 млн оп./с, ОЗУ от 32К до128К Таблица 1.1. показывает, что до начала этапа копирования, хотя и имело место отставание, оно не было катастрофическим и носило характер динамической системы. Заметим, что успехи в развитии вычислительной техники нельзя рассматривать изолированно. Они напрямую связаны с потребностями развития экономики СССР послевоенного периода, а достижения в других областях были и причиной и следствием.

Напомним некоторые из этих достижений:

август 1949 г. - успешное испытание в СССР атомной бомбы;

4 ноября 1957 г. – в СССР запущен первый искусственный спутник Земли;

12 сентября 1959 г. - запуск космического аппарата «Луна-2», достигшего поверхности Луны;

12 апреля 1961 г. - Юрий Гагарин на космическом корабле «Восток» совершил первый в мире полёт в космос;

31 января 1966 г - космический аппарат «Луна-9» впервые в мире осуществил мягкую посадку на Луну;

12 июня 1967 г. – космический аппарат «Венера-4» впервые осуществил плавный спуск в атмосфере Венеры.

Нетрудно заметить, что период успехов в развитии вычислительной техники (50-е годы) удивительным образом совпадает со впечатляющими успехами СССР в других областях: космических исследованиях, развитии атомной энергетики и др.

1.2.3 Этап создания единой системы (ЕС) ЭВМ В конце 1960-х годов советское руководство приняло решение о прекращении производства оригинальных отечественных ЭВМ и развертывании работ по созданию Единой системы ЭВМ (ЕС ЭВМ) социалистических стран на базе архитектуры IBM System/360, а также Системы малых машин (СМ ЭВМ) на базе архитектуры Hewlett Packard и PDP-11. Всего за период с 1970 по 1990 год было произведено более 15000 вычислительных машин разной производительности ряда ЕС ЭВМ.

Этот этап имел как некоторые положительные, так и отрицательные последствия. В качестве положительных результатов следует отметить следующие: удалось несколько сократить технологическое отставание; пользователи могли использовать уже существовавшие к тому времени довольно значительные библиотеки для ЭВМ. Кроме того, наличие переводной литературы позволило в короткие сроки организовать выпуск специалистов.

Вместе с тем это имело также значительные отрицательные последствия.

Несмотря на большую затратность проекта, скачка так и не произошло, поскольку технологическая база оставалась слабой, но самое главное были разрушены сложившиеся научные школы. Некоторые отрицательные последствия, например, зависимость от заимствованного программного обеспечения остро ощущается до сих пор. Это существенно сдерживает создание и реализацию сложных систем во многих областях.

1.3 Новая стратегическая инициатива США и перспективы развития суперкомпьютерной отрасли в России Успехи США в разработке ЭВМ и программного обеспечения, конечно, не были случайными. Они явились следствием микропроцессорной революции, которая произошла в результате беспрецедентных по масштабу инвестиций правительства США в электронное машиностроение. Следствием этого является то, что до сих пор ведущие производители вычислительной техники (IBM, HP, Intel) сосредоточены в США. Тем не менее именно США выступили с новой стратегической инициативой в области вычислительной техники.

В мае 2005 года Консультативный комитет по информационным технологиям при Президенте США представил Джорджу Бушу аналитический доклад под названием: «Вычислительная наука: обеспечение конкурентоспособности Америки» [11]. В этом докладе содержатся результаты анализа потенциальных возможностей развития науки, промышленности и экономики, их связи с достижениями в области информатики (Computational Science). По мнению авторов, это одна из наиболее важных областей, которая является существенным фактором инновационного развития общества в XXI веке. Авторы доклада подчеркивают, что именно эта область в настоящее время является важнейшим фактором для обеспечения научного лидерства, конкурентоспособности и национальной безопасности США.

Под Computational Science (вычислительными науками) авторы доклада понимают:

1. Модели, вычислительные алгоритмы и моделирующие программы для решения научных (биология, физика, социальные исследования и др.), технических и гуманитарных проблем.

2. Оптимизация и развитие аппаратных, программных и сетевых средств обработки данных, обеспечивающих решение указанных выше вычислительных задач.

3. Компьютерная инфраструктура для поддержки научных исследований и решения технических задач.

В докладе показано, что развитие «вычислительной науки» создает уникальные возможности для проведения научных исследований, в т.ч. для исследования процессов и явлений в реальном масштабе времени с использованием высокопроизводительных суперкомпьютеров. Предполагается, что именно вычислительная наука, наряду с теоретическими исследованиями и физическим экспериментом, будет являться главной основой всей научной методологии XXI века (рис. 1.2).

Физические, экономические, социальные, технические и гуманитарные науки.

Прогноз погоды, Политические исследования, Национальная безопасность, Нанотехнологии.

Энергия, Биомедицинские науки, Промышленность, Климат Вычислительные науки (Computational Science) Алгоритмы и модели, моделирующие программы.

Науки о компьютерах и информатике.

Компьютерная инфраструктура (метакомпьютинг).

Рис. 1.2. Иллюстрация интегрирующей роли вычислительных наук Основные меры, направленные на поддержание национальной безопасности, которые были сформулированы в документе:

1. Выработка перспективных направлений и поддержание высокого уровня исследований в области вычислительных наук.

2. Создание инфраструктуры для поисковых исследований.

3. Создание национального репозитария данных и программных продуктов.

4. Создание и поддержка национальных высокопроизводительных вычислительных центров.

Новая американская стратегическая компьютерная инициатива содержит серьезный анализ новых вызовов XXI века мировому сообществу. Эти вызовы затронут все без исключения страны мира и повлекут за собой новый этап конкурентной борьбы в области науки, образования и информационных технологий. По-видимому, вычислительные науки, понимаемые в широком смысле этого слова, т.е. включающие как собственно теорию и методы алгоритмизации вычислительных процессов, так и вопросы создания аппаратно-программного обеспечения, будут играть ведущую интегрирующую роль в этом процессе.

К сожалению, Россия отстает от основных лидеров – стран, где установлены самые мощные суперкомпьютеры. Поэтому весьма своевременной представляется задача, поставленная президентом Дмитрием Медведевым на заседании комиссии по модернизации и технологическому развитию российской экономики в г. Сарове Нижегородской области: «для технологического и инновационного развития Россия должна сократить отставание от лидеров в сфере вычислительных технологий. Прежде всего это касается создания суперкомпьютеров и так называемых grid-технологий» (Российская газета - Федеральный выпуск №4962 (138) от 29 июля 2009 г.). В частности, в этом городе во Всероссийском НИИ экспериментальной физики в 2011 году должен появиться первый отечественный суперкомпьютер, способный выполнять одновременно квадриллион операций.

Дмитрий Медведев очертил круг основных направлений работы в сфере суперкомпьютеров:

«Есть пять задач, которые надо поставить и решить.

Первая – определить приоритетное направление использования суперкомпьютерных и grid-технологий в области обеспечения национальной безопасности и социально-экономического развития страны.

Вторая задача заключается в подъеме уровня отечественной электронной компонентной базы до потребностей производства суперкомпьютеров.

Третье очевидное условие – сформировать нормативно-правовую базу применения суперкомпьютеров.

Четвертое – создать условия для построения grid-сетей прежде всего в научно-образовательной сфере.

Пятое – организовать специальную систему подготовки специалистов ведущих вузов страны»

Президент России подчеркнул, что «применение суперкомпьютеров во всем мире осуществляется при решающей финансовой и организационной поддержке государства, и Россия готова идти по общепринятому пути». При этом важно также одновременно развивать технологическую культуру разработки новых образцов техники с использованием современной суперкомпьютерной техники. «Мы должны всячески стимулировать ее востребованность не потому, что это модная тема, а просто потому, что по-другому не создать конкурентоспособную продукцию» – считает глава государства.

Опираясь на опыт передовых стран, в России предполагается создание иерархических вычислительных комплексов – так называемых grid-систем. В основе grid-систем должно находиться большое количество относительно небольших компьютеров с очень широкой географией, связанных в высокопроизводительные сети. А вершиной пирамиды станет мощная ЭВМ для проведения наиболее сложных фундаментальных исследований. Для того чтобы ликвидировать отставание, предполагается развитие сотрудничества с США и другими странами по вопросам развития высокопроизводительных вычислений. Использование имеющегося опыта, в том числе зарубежных стран, в деле создания своей суперкомпьютерной отрасли имеет большое значение для реализации стратегии национальной безопасности и развития концепции долгосрочного социально-экономического развития России.

1.4 Проблемы высокопроизводительных вычислений и задачи курса В последние годы во всем мире усиливается внимание к использованию высокопроизводительной вычислительной техники. С одной стороны, растет число пользователей персональных миникластеров, с другой стороны, происходит концентрация мощных вычислительных ресурсов в центрах коллективного пользования и развитие инфраструктуры удаленного доступа с использованием средств телекоммуникаций.

С другой стороны, в настоящее время всеми осознается факт, что дальнейшее повышение производительности компьютеров только за счет улучшения характеристик элементов электроники достигло предела, определяемого физическими законами. Дальнейшее повышение производительности возможно лишь за счет распараллеливания процессов обработки информации. Однако оказалось, что построение параллельных вычислительных процессов, обеспечивающих достижение максимальной производительности, является важной самостоятельной проблемой.

Сокращение времени выполнения большого объема работ путем разбиения на отдельные работы, которые могут выполняться независимо и одновременно, используется во многих отраслях. В области вычислительной техники это достигается путем увеличения числа одновременно работающих процессоров.

Вместе с тем известно, что перенос обычной программы на многопроцессорную вычислительную систему может не дать ожидаемого выигрыша в производительности. Более того, в результате такого переноса программа может работать медленнее.

Опыт показывает, что написать эффективную параллельную программу или приспособить уже имеющуюся последовательную программу для параллельных вычислений чрезвычайно трудно. Связано это с тем, что переход к использованию многопроцессорных систем характеризуется принципиально новым содержанием. В данном случае важнейшим оказывается структурный анализ алгоритма, выявление его внутреннего параллелизма. Этот анализ требует глубокого понимания существа задачи. Часто же проблема заключается в том, что программист не вполне ясно понимает алгоритм решения задачи, а математик не может поправить программу, т.к. не обладает достаточной квалификацией в области программирования.

Эта трудность может быть преодолена, если использовать модель представления алгоритма, которая понятна как математику, так и программисту.

При этом математик и программист могут работать в значительной степени независимо, взаимодействуя лишь в рамках используемой модели.

Представляется, что такое «разделение труда» позволит существенно сократить сроки решения сложных задач. Это освобождает прикладного математика высокой квалификации от необходимости написания кодов для решения своих задач. Математик может выполнить структурный анализ алгоритма, выявить имеющийся в нем параллелизм и представить в виде модели, понятной программисту. С другой стороны, программист, не вникая в существо задачи, используя лишь модель параллельных вычислений, может написать весьма эффективный код.

Именно поэтому центральная идея настоящего пособия состоит в том, чтобы изучать вопросы построения параллельных алгоритмов и вопросы программирования независимо. В частности, цель настоящего курса лекций дать основные сведения в области параллельных вычислений, касающиеся вопросов анализа эффективности параллельной структуры алгоритма. При этом основное внимание будет уделено построению моделей и схем параллельных вычислений, а также анализу достижимых ускорения и эффективности для различных прикладных вычислительных задач. Изучение этих вопросов, следуя изложенной выше точке зрения, будет доводиться до описания параллельного алгоритма в виде блок-схем, графов и диаграмм, которые понятны программисту и могут использоваться им для написания параллельной программы.

Архитектура параллельных вычислительных систем 2.1 Введение Представьте себе на минуту, что вы музыкант и ваша задача подготовить некоторое музыкальное произведение для исполнения оркестром (на музыкальном языке это называется написать партитуру для оркестра). Что для этого надо знать? По-видимому, надо знать, какие группы инструментов существуют (духовые, струнные, ударные и др.). Затем надо знать, какие особенности звучания имеют отдельные виды инструментов внутри каждой группы и, наконец, как они называются (ведь каждая партия должна быть адресована конкретному инструменту). Композитор, пишущий партитуру для оркестра, может впоследствии и не дирижировать оркестром. Вполне вероятно, это будут делать другие музыканты, притом с различными стилями дирижирования, всякий раз придающими произведению своеобразную окраску.

Этот музыкальный пример мы привели для того, чтобы еще раз подчеркнуть основную идею настоящего учебного пособия: рассмотреть проблемы параллельных вычислений, не затрагивая вопросы программирования. Мы рассматриваем процесс подготовки параллельного решения задачи на многопроцессорной системе как отдельный этап подготовки описания (партитуры) параллельного алгоритма не некотором языке блок-схем и/или графов. Написание параллельной программы рассматривается как завершающий этап (дирижирование оркестром), обеспечивающий эффективную реализацию задуманного алгоритма (произведения), возможно, с учетом его конкретных особенностей (состава, квалификации музыкантов и др.).

Другими словами, при описании параллельных алгоритмов не обязательно знать конкретный язык программирования, на котором будет реализована программа. Однако надо хорошо знать особенности вычислительной системы, на которой будет реализован алгоритм (типы используемых вычислительных узлов, производительность и др.). Если у разработчика есть выбор, можно поставить задачу построения наиболее эффективного параллельного алгоритма, подобрав типы вычислителей, наиболее полно реализующие его особенности. Для этого необходимо ясно представлять потенциальные возможности различных архитектур.

Таким образом, изучение возможных типов архитектур, характеристик и способов организации вычислительной системы, на которой предполагается реализация разрабатываемого параллельного алгоритма, является необходимым этапом. Настоящая лекция содержит краткий обзор наиболее популярных архитектур в том минимальном объеме, который может потребоваться при разработке параллельного алгоритма.

2.2 Классификация компьютерных систем Существуют различные классификации, преследующие разные цели. При разработке параллельного алгоритма наиболее важно знать тип оперативной памяти, т.к. она определяет способ взаимодействия между частями параллельной программы. В зависимости от организации подсистем оперативной памяти параллельные компьютеры можно разделить на следующие два класса.

Системы с разделяемой памятью (мультипроцессоры), у которых имеется одна виртуальная память, а все процессоры имеют одинаковый доступ к данным и командам, хранящимся в этой памяти (uniform memory access или UMA).

По этому принципу строятся векторные параллельные процессоры (parallel vector processor или PVP) и симметричные мультипроцессоры (symmetric multiprocessor или SMP).

Системы с распределенной памятью (мультикомпьютеры), у которых каждый процессор имеет свою локальную оперативную память, а у других процессоров доступ к этой памяти отсутствует.

При работе на компьютере с распределенной памятью необходимо создавать копии исходных данных на каждом процессоре. В случае системы с разделяемой памятью достаточно один раз задать соответствующую структуру данных и разместить ее в оперативной памяти.

Указанные два типа организации памяти могут быть реализованы в различных архитектурах. Рассмотрим различные классификации параллельных компьютеров, указывая там, где это имеет значение, способ организации оперативной памяти.

Исторически наиболее ранней является классификация М. Флинна (1966).

Классификация основана на понятии потока, под которым понимается последовательность команд или данных, обрабатываемых процессором. На основе числа потоков команд и потоков данных выделяют четыре класса архитектур:

SISD (Single Instruction stream/Single Data stream) – один поток команд и один поток данных;

SIMD (Single Instruction stream/Multiple Data stream) – один поток команд и множество потоков данных;

MISD (Multiple Instruction stream/Single Data stream) – множество потоков команд и один поток данных;

MIMD (Multiple Instruction stream/Multiple Data stream) – множество потоков команд и множество потоков данных.

В настоящее время подавляющее число «серьезных» компьютеров реализуется в классе MIMD-архитектур. При этом рассматривают следующие основные подклассы.

Векторно-конвейерные компьютеры, в которых используется набор векторных команд, обеспечивающих выполнение операций с массивами независимых данных за один такт. Типичным представителем данного направления является линия «классических» векторно-конвейерных компьютеров CRAY.

Массово-параллельные (чаще называемые также массивно-параллельные) компьютеры с распределенной памятью. В данном случае микропроцессоры, имеющие каждый свою локальную память, соединяются посредством некоторой коммуникационной среды. Достоинство этой архитектуры – возможность наращивать производительности путем добавления процессоров. Недостаток – большие накладные расходы на межпроцессорное взаимодействие.

Симметричные мультипроцессоры (SMP) состоят из совокупности процессоров, имеющих разделяемую общую память с единым адресным пространством и функционирующих под управлением одной операционной системы.

Недостаток – число процессоров, имеющих доступ к общей памяти, нельзя сделать большим. Существует предел наращивания числа процессоров, превышение которого ведет к быстрому росту потерь на межпроцессорный обмен данными.

Кластеры образуются из вычислительных модулей любого из рассмотренных выше типов, объединенных системой связи или посредством разделяемой внешней памяти. Могут использоваться как специализированные, так и универсальные сетевые технологии. Это направление, по существу, является комбинацией предыдущих трех.

Еще раз подчеркнем, что наиболее важным при разработке параллельного алгоритма является деление на компьютеры с общей и распределенной памятью. Для компьютеров с общей памятью пользователю не нужно заботиться о распределении данных, достаточно предусмотреть лишь затраты на выбор необходимых данных из этой памяти. При реализации параллельного алгоритма на компьютерах с распределенной памятью необходимо продумать рациональную, с точки зрения потерь на обмен данными, схему их размещения. Далее дадим более подробную характеристику каждого из указанных выше подклассов компьютеров.

2.3 Детализация архитектур по достижимой степени параллелизма Выше мы рассмотрели основные классы параллельных компьютеров, отличия между которыми следует учитывать в первую очередь при построении параллельных алгоритмов. Поскольку подавляющее число архитектур реализуется в классе MIMD, требуется более детальная классификация, которая, кроме прочего, позволяла бы также давать оценку достижимой степени параллелизма.

Одна из таких систематизаций MIMD-компьютеров дана Р. Хокни [2]. Основная идея классификации состоит в том, что множественный поток команд может быть обработан либо по конвейерной схеме в режиме разделения времени, либо каждый поток обрабатывается своим устройством.

В соответствии с этим различают следующие MIMD – компьютеры:

- конвейерные;

- переключаемые (с обей памятью и распределенной памятью);

- сети, реализованные в виде: регулярной решетки, гиперкуба, иерархической структуры и изменяемой конфигурации.

Следующая классификация [2] Т. Фенга позволяет также строить оценки достижимой степени параллелизма. Она основана на двух характеристиках:

- число n бит в машинном слове, обрабатываемых параллельно;

- число слов m, обрабатываемых одновременно вычислительной системой.

Произведение P=mn, определяющее интегральную характеристику параллельности архитектуры, называют максимальной степенью параллелизма вычислительной системы. Введение этой единой числовой метрики для всех типов компьютеров позволяет сравнивать любые два компьютера между собой. Однако в данном случае не делается акцент на том, за счет чего компьютер может одновременно обрабатывать более одного слова.

С точки зрения указанной классификации возможны следующие варианты построения компьютера:

- разрядно-последовательные, пословно-последовательные (n=1, m=1);

- разрядно-параллельные, пословно-последовательные (n>1, m=1);

- разрядно-последовательные, пословно-параллельные (n=1, m>1);

- разрядно-параллельные, пословно-параллельные (n>1, m>1).

Подавляющее большинство вычислительных систем принадлежит к этому, последнему, классу.

Классификация В. Хендлера [2]. В основе этой классификации явное описание параллельной и конвейерной обработки. При этом различают три уровня обработки данных:

- уровень выполнения программы;

- уровень выполнения команд;

- уровень битовой обработки.

На каждом уровне допускается возможность конвейерной обработки. Таким образом, в общем случае каждый компьютер может быть охарактеризован следующими шестью числами:

k - число процессоров;

k’ - глубина макроконвейера;

d - число АЛУ в каждом процессоре;

d’ - глубина конвейера из функциональных устройств АЛУ;

w - число разрядов в слове, обрабатываемых в АЛУ параллельно;

w’ - число ступеней в конвейере функциональных устройств каждого АЛУ.

Имеет место связь классификации Хендлера с классификацией Фенга: для получения максимальной степени параллелизма в смысле Фенга необходимо вычислить произведение указанных выше шести величин.

В классификации Д. Скилликорна [2] архитектуру любого компьютера предлагается рассматривать как абстрактную структуру, состоящую из четырех компонентов:

- процессор команд (IP – Instruction Procesor) – интерпретатор команд;

- процессор данных (DP – Data Procesor) – устройство обработки данных;

- устройство памяти (IM – Instruction Memory, DM – Data Memory);

- переключатель – абстрактное устройство, обеспечивающее связь между процессорами и памятью.

Рассматривается четыре типа переключателей:

- 1–1 – связывает пару функциональных устройств;

- n–n – реализует попарную связь каждого устройства из одного множества с соответствующим ему устройством из другого множества;

- 1–n – соединяет одно выделенное устройство со всеми функциональными устройствами из некоторого набора;

- nn – каждое функциональное устройство одного множества может быть связано с любым устройством из некоторого набора.

Заметим, что приведенные в настоящем разделе типы классификаций претендуют на более высокий уровень формализации количественных оценок параллелизма и поэтому могут быть полезными при проведении исследований, связанных с применением моделей вычислительных систем достаточно высокого уровня абстрактности.

2.4 Векторно-конвейерные компьютеры Появление термина суперкомпьютер связано с созданием в середине шестидесятых годов фирмой CDC (Сеймуром Крэем) высокопроизводительного компьютера с новой векторной архитектурой. Основная идея, положенная в основу этой архитектуры, заключалась в распараллеливании процесса обработки данных, когда одна и та же операция применяется одновременно к массиву (вектору) значений. Эта идея оказалась плодотворной и нашла воплощение на разных уровнях функционирования компьютера.

Классическим представителем мира суперкомпьютеров является первый векторно-конвейерный компьютер Cray-1 (1976). Основные особенности архитектуры этого класса компьютеров следующие.

Конвейеризация выполнения команд.

Независимость функциональных устройств, т.е. несколько операций могут выполняться одновременно.

Векторная обработка (набор данных обрабатывается одной командой).

Зацепление функциональных устройств (выполнение нескольких векторных операций в режиме «макроконвейера»).

Многопроцессорная обработка (наличие независимых процессоров позволяет выполнять несколько независимых программ).

Эффективность векторно-конвейерных компьютеров существенным образом зависит от наличия одинаковых и независимых операций. В качестве примера рассмотрим несколько фрагментов вычислений в виде блок-схем, показанных на рисунке 2.1, а, б, в.

Поскольку в системе команд векторно-конвейерных компьютеров обычно есть векторные команды, в которых аргументы могут быть как скалярами, так и векторами, векторизация фрагментов, показанных на рис. 2.1, а и б, не вызовет проблем. В то же время фрагмент, показанный на рис. 2.1, в, невозможно векторизовать, поскольку вычисление i-го элемента массива A не может начаться, пока не будет вычислен предыдущий элемент. В данном примере имеет место зависимость между операциями, которая будет препятствовать векторизации.

Это надо иметь в виду при выполнении программы на компьютере векторноконвейерной архитектуры.