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

Страны, научные организации и университеты соревнуются за попадание в верхние строки рейтингов производительности. Наиболее мощными в мире сейчас считаются японский вычислительный комплекс RIKEN – 8.776 PFlop, суперкомпьютер в Тайваньском суперкомпьютерном центре – 4.701 PFlop и вычислительный комплекс Oak Ridge National Laboratory (США) – 2.331 PFlop. (В одном петафлопсе 1000 терафлопс). В США объявлено о начале разработки экса-флопного компьютера, один эксафлопс равен миллиону терафлопс.

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

Задачи, конечно, есть. Рассмотрим прогноз погоды в масштабах всей планеты. Для расчета атмосферных явлений будем использовать ячейки размером 1 кубическая миля до высоты в 10 миль. Тогда при шаге по времени в 1 минуту при решении уравнений математической модели с целью получения прогноза погоды на 10 дней нам потребуется 1015 операций с плавающей точкой. Это как раз и составит 10 дней работы персонального компьютера производительностью 1.5 Gflop. Для проверки правильности результатов останется лишь выглянуть в окно. Понятно, что решение такой задачи требует использования более мощной техники.

Еще более впечатляющими по требуемому времени выполнения являются задачи астрофизики и биофизики. Для моделирования развития галактики из 1011 звезд на один шаг интегрирования уравнений математической модели требуется примерно 1 год времени работы современного персонального компьютера. Таких шагов для получения сколь-нибудь адекватных результатов требуется несколько миллиардов. А для моделирования образования белка методами молекулярной динамики у вас уйдет 1025 машинных команд, что займет на одноядерном персональном компьютере с тактовой частотой 3.2 Ghz 106 веков. Понятно, что при таких сроках расчетов ни один исследователь результатов не дождется.

Есть задачи, и есть техника для их решения. Что же мешает эффективному использованию высокопроизводительных вычислительных комплексов? Для ответа на этот вопрос проще всего привести цитату из лекции Дейкстры, прочитанной им при получении Тьюринговской премии: «To put it quite bluntly: as long as there were no machines, programming was no problem at all; when we had a few weak computers, programming became a mild problem, and now we have gigantic computers, programming has become an equally gigantic problem.»

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

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

NGC_4414_(NASA-med)

Три кризиса программного обеспечения

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

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

Первый кризис программного обеспечения можно датировать концом 1950-х – началом 1970-х годов, когда программирование на языках низкого уровня вошло в противоречие с возможностями компьютеров. Тогда назрела необходимость перехода на более высокий уровень абстракции и переносимости программ. Решением появившейся проблемы стало развитие языков высокого уровня (ALGOL, FORTRAN, C и так далее) для машин неймановской архитектуры.

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

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

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

В 1965 году Гордон Мур, один из основателей Intel, сформулировал эмпирический закон, который обычно принято записывать так: количество полупроводниковых элементов на кристалле и производительность процессоров будут удваиваться в среднем каждые полтора–два года. Однако в реальности закон Мура носил экономический характер и первоначально утверждал, что стоимость производства одного транзистора будет вдвое снижаться каждые полтора года. Закон Мура в экономической форме, по мнению сотрудников Intel, будет действовать вплоть до 2015 года.

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

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

Последовательная и параллельная парадигмы программирования

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

При решении задачи на последовательной вычислительной системе (один процессор и одно ядро) принято считать, что эта совокупность состоит из пяти этапов.

Первый этап.

Постановка задачи.

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

Второй этап.

Создание математической модели.

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

Третий этап.

Разработка алгоритма решения в рамках созданной математической модели.

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

Четвертый этап.

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

Модель программирования определяет основные идеи и стиль программной реализации, абстрагируясь от алгоритмического языка и, частично, от hardware. Например, модель функционального программирования, модель объектно-ориентированного программирования, модель продукционного программирования и так далее.

Пятый этап.

Работа программы как набора процессов и/или нитей исполнения на вычислительной системе и получение результатов.

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

При решении задачи на параллельной вычислительной системе (несколько процессоров и/или несколько ядер) в этой совокупности появляются дополнительные этапы. Теперь этапов  становится восемь:

Первый этап. Постановка задачи.

Второй этап. Создание математической модели.

Третий этап. Разработка алгоритма.

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

Четвертый этап.

Декомпозиция алгоритма (decomposition).

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

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

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

Пятый этап.

Назначение работ (assignment).

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

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

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

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

По времени способы назначения разделяются на две категории:

• статические – распределение выполняется на этапе написания, компиляции или старта программы (до реального начала вычислений);

• динамические – распределение осуществляется в процессе исполнения.

Шестой этап.

Аранжировка.

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

Роль дирижера тоже определяется на этапе аранжировки.

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

Остановимся подробнее на программных моделях для работы на параллельных вычислительных системах.

?????????????_?????????????

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

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

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

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

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

Модель разделенных данных предполагает, что приложение состоит из наборов процессов или thread’ов, каждый из которых работает со своим набором данных, обмена информацией при работе нет.  Такая модель применима лишь для ограниченного класса задач.

Седьмой этап.

Написание программы, реализующей алгоритм, в выбранной модели программирования и на выбранном алгоритмическом языке. Модель программирования определяет основные идеи и стиль программной реализации, абстрагируясь от алгоритмического языка и, частично, от hardware. Например, модель функционального программирования, модель объектно-ориентированного программирования, модель продукционного программирования и так далее.

Восьмой этап.

Отображение

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

В зависимости от выбранной модели программирования это может делать как человек, проводящий вычислительный эксперимент, так и операционная система. Заметим в заключение, что проблема кризиса программного обеспечения и производства супервычислений очень остра. Как правило, на таких системах решаются большие уникальные задачи – от прогноза погоды до моделирования ядерных испытаний и проектирования новых лекарственных препаратов. Уже известны случаи, когда архитектура «железа» продумывается под одну единственную задачу, которая на данном суперкомпьютере будет выполняться. И с этой точки зрения самым ценным суперкомпьютерным ресурсом остается человек, специалист по супервычислениям, который может правильно поставить задачу и определиться с путем ее решения. Для подготовки таких специалистов в России сформировано несколько НОЦ – научно-учебных центров. Один из таких центов по суперкомпьютерным технологиям организован в МФТИ. 

Владимир Карпов,

Алексей Лобанов

 

При написании статьи использованы материалы лекционных курсов авторов в рамках НОЦ СКТ МФТИ.

Список литературы

1. Шагин И. Архитектура высокопроизводительных компьютеров и вычислительных систем. – 17.12.2001.

2. Российский список Top50 самых мощных суперкомпьютеров http://supercomputers.ru/top50/?page=rating

3. http://www.top500.org/lists/2011/09

4. Терехов И. К созданию эксафлопного суперкомпьютера подключилась Intel. – 18.08.2010. http://www.3dnews.ru/news/

5. Wilkinson B., Allen M. Parallel programming techniques and applications using networked workstations and parallel computers. – Pearson Education, 2005. – p. 468.

6. Карпов В. Е., Коньков К. А. Основы операционных систем. – М.: Интуит.ру, 2005. –  657с.

7. Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. – Спб.: БХВ-Петербург, 2002. –  601 с.

8. http://ru.wikipedia.org/wiki/Парадигма_программирования

9. Столяров Л.Н., Абрамов В.М. Начала информатики. От задачи к программе. – М.: Изд-во МАКЕТ, 2007. –  120 с.

10. А.А. Самарский, А.С. Михайлов Математическое моделирование: Идеи. Методы. Примеры. – 2 изд., М. – Физматлит, 2002 – 320 с.


Выпуск №12 журнал - ноябрь 2011