Стремительное развитие наук, как фундаментальных, так и прикладных, использующих сложные реалистические (многомерные, многопараметрические) математические модели или требующих сложной, но быстрой обработки информации, а также быстрый технологический прогресс, привели к тому, что значительно возросла потребность в применении мощных вычислительных средств.
Мы являемся свидетелями быстрого прогресса вычислительной техники. Производительность современных компьютеров на много порядков превосходит производительность первых ЭВМ и продолжает возрастать заметными темпами. Увеличиваются и другие ресурсы, такие как объем и быстродействие оперативной и постоянной памяти, скорость передачи данных между компонентами компьютера и т.д. Совершенствуется архитектура ЭВМ.
Вместе с тем следует заметить, что уже сейчас прогресс в области микроэлектронных компонент сталкивается с ограничениями, связанными с фундаментальными законами природы. Вряд ли можно надеяться на то, что в ближайшее время основной прогресс в быстродействии электронно-вычислительных машин будет достигнут лишь за счет совершенствования их элементной базы. Переход на качественно новый уровень производительности потребовал от разработчиков ЭВМ и новых архитектурных решений.
Традиционная архитектура ЭВМ была последовательной. Это означало, что в любой момент времени выполнялась только одна операция и только над одним операндом. Совокупность приемов программирования, структур данных, отвечающих последовательной архитектуре компьютера, называется моделью последовательного программирования. Ее основными чертами являются применение стандартных языков программирования (как правило, это ФОРТРАН-77, ФОРТРАН-90, С/С++), достаточно простая переносимость программ с одного компьютера на другой и невысокая производительность.
Появление в середине шестидесятых первого компьютера класса суперЭВМ, разработанного в фирме CDC знаменитым Сеймуром Крэем, ознаменовало рождение новой – векторной архитектуры. Основная идея, положенная в основу новой архитектуры, заключалась в распараллеливании процесса обработки данных, когда одна и та же операция применяется одновременно к массиву (вектору) значений. В этом случае можно надеяться на определенный выигрыш в скорости вычислений. Идея параллелизма оказалась плодотворной и нашла воплощение на разных уровнях функционирования компьютера.
В основе параллельного компьютера лежит идея использования для решения одной задачи нескольких процессоров, работающих сообща. Расчет делается на то, что если одному процессору для выполнения задачи требуется время t, то p процессоров смогут решить эту задачу, разбитую на подзадачи, за время t/р. Однако это идеальное ускорение удается получить лишь в очень специальных ситуациях, когда подзадачи полностью независимы. На практике же целью программиста является построение алгоритмов, способных извлечь из наличия нескольких процессоров максимальную выгоду для данной задачи.
Первые промышленные образцы мультипроцессорных систем на базе векторно-конвейерных компьютеров появились в середине 80-х годов. Они были чрезвычайно дороги и, как альтернатива, была предложена идея создавать эквивалентные по мощности многопроцессорные системы из большого числа серийно выпускаемых дешевых микропроцессоров. Однако такая архитектура обладает весьма ограниченными возможностями по наращиванию числа процессоров в системе из-за конфликтов при обращении к общей шине памяти. В связи с этим оправданной представлялась идея снабдить каждый процессор собственной оперативной памятью, превращая компьютер в объединение независимых вычислительных узлов. Такой подход значительно увеличил степень масштабируемости многопроцессорных систем, однако потребовал создания специального механизма обмена данными между вычислительными узлами. В настоящее время две последних архитектуры являются доминирующими в развитии суперкомпьютерных технологий.
В 70-80-х годах в России велись интенсивные исследования, направленные на создание параллельных вычислительных систем. Примерами могут служить системы PHOENIX [1], ПС-2000 [19]. К реально действующим суперЭВМ того времени можно отнести машину БЭСМ-6 [15] с быстродействием около 1 млн. одноадресных операций в секунду, многопроцессорные вычислительные комплексы Эльбрус [11] (Эльбрус-1 около 10 млн. оп./c., Эльбрус-2 около 100 млн. оп./c.), "Электроника ССБИС" [15] и др.
Принципы, заложенные в основу структурной организации упомянутых машин, не потеряли своего значения до сих пор. Машины БЭСМ-6 и вычислительные комплексы, созданные на их основе, интенсивно использовались в научно-исследовательских институтах, центрах обработки информации, решающих наиболее важные для народного хозяйства, науки и обороны задачи. За время использования этой машины накоплено огромное по составу, чрезвычайно важное по значимости математическое обеспечение, сконцентрировавшее в себя лучшие достижения советских ученых в области вычислительной математики, программирования, решения задач проектирования сложнейших объектов, в области решения задач, связанных с освоением космического пространства.
Одновременно с проектированием параллельных вычислительных систем ведущими учеными велись работы по распараллеливанию алгоритмов решения сложных задач, например, [7, 14] посвящены общим вопросам распараллеливания алгоритмов, [22] – распараллеливанию численных методов линейной алгебры, [10, 26] – уравнений в частных производных и т.д.
В настоящее время в России создан ряд суперкомпьютерных ресурсов, перечень которых можно найти на WWW-странице НИВЦ МГУ [15].
Важнейшей составной частью создания и внедрения высокопроизводительных технологий является существенное расширение компьютерного образования и подготовка квалифицированных специалистов в этой области. Многие вузы начали подготовку специалистов по данному направлению [9, 13].
В 2000 году в КемГУ создана кафедра ЮНЕСКО по новым информационным технологиям, которая приступила к чтению спецкурсов по высокопроизводительным вычислениям в рамках специальности “прикладная математика”. Программирование на суперкомпьютере или кластере ПК - это далеко не всегда простая задача, и простой перенос программы на многопроцессорную вычислительную систему может не дать ожидаемого выигрыша в производительности программы. Может случиться и так, что в результате такого переноса программа будет работать медленнее, чем на компьютере с традиционной архитектурой. Таким образом, изучение методов распараллеливания последовательных программ, анализ свойств параллельных алгоритмов является актуальной задачей.
Цель пособия – познакомить читателя с основными направлениями в развитии суперкомпьютерных вычислительных технологий, дать обзор средств параллельного программирования, детально изложить идеи параллельного программирования с помощью интерфейса передачи сообщений.
Пособие по своему логическому содержанию разбито на шесть глав. В первой главе обсуждаются основные направления развития высокопроизводительных вычислительных компьютеров, приводятся классификации архитектур суперкомпьютеров.
Во второй главе приведен обзор средств параллельного программирования, отдельное внимание уделяется отечественной разработке DVM.
В третьей главе пособия детально рассмотрены вопросы создания вычислительного кластера на основе сети персональных компьютеров. В качестве инструментария для проведения параллельных вычислений был выбран MPI (интерфейс передачи сообщений), базой для создания кластера – компьютерный класс кафедры Юнеско по НИТ КемГУ. Приведенные в данной главе тесты показали привлекательность такого подхода для создания вычислительных комплексов.
Четвертая глава знакомит читателя с набором функций MPI, необходимых для создания параллельных приложений. При написании главы были использованы следующие материалы: MPI Complete Reference [27], учебное пособие по параллельному программированию [9]. Описание почти всех функций MPI сопровождается примерами их использования.
В пятой главе вводятся основные понятия параллелизма алгоритмов, дается рекомендация по исследованию свойств параллельного алгоритма.
В шестой главе приводится описание простейших параллельных алгоритмов для более глубокого понимания идей параллельного программирования.
При написании учебного пособия незаменимым источником информации были материалы информационно-аналитического центра НИВЦ МГУ [15].
Предлагаемое учебное пособие является частью плановой работы, которая была определена департаментом информационных технологий Организации Объединенных Наций по вопросам образования, науки и культуры (UNESCO), при создании в Кемеровском государственном университете кафедры Юнеско по новым информационным технологиям в образовании и науке.