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

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

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

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

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

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

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

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

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

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

1.1. Архитектура фон Неймана.

Первые же попытки автоматизировать процесс вычислений в конце 40-х годов прошлого века показали, что быстродействие определяется не только и не столько тем, как быстро машина выполняет арифметические операции, сколько тем, как именно организован процесс «объяснения» машине, что именно вычислять.

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

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

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

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

На этом этапе:

- программист почти не задумывался о том, для суперкомпьютера или для «обычного» компьютера он пишет программу;

- разработчик оборудования суперкомпьютера разрабатывал «супер-процессор»;

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

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

Примерно в конце 80-х годов разработчики СБИС смогли разместить на одном кристалле кремния миллион транзисторов (это – примерно технологический уровень процессора Intel 80486 [67]). Имея в своем распоряжении такое количество «деталей», разработчики процессоров получили возможность ускорить практически все, что можно было ускорить в принципе. Конечно, попытки «добыть» дополнительное быстродействие на микроуровне продолжаются и сейчас – на кристалле микропроцессора Itanium-2, например, транзисторов уже миллиард [7,67]. Но уже тогда, на миллионном уровне, стало очевидно, что многократного (в десятки и сотни раз) ускорения работы, выполняемой в среднем за один такт, не получить. Эпоха «супер-процессоров» кончилась – отныне каждый процессор является одновременно и «обычным», и «супер», существенной разницы нет.

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

На этом этапе:

- программист, чтобы получить суперкомпьютерный уровень быстродействия, был поставлен перед необходимостью писать специальные – параллельные – программы;

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

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

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

На этом этапе:

- для программиста, по сравнению с предшествующим этапом, ничего принципиально не изменилось, кроме того, что таких программистов стало многократно больше, как и самих суперкомпьютеров;

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

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

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

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

Технология кластеров выделенных рабочих станций господствует в суперкомпьютерной отрасли, фактически, определяя ее облик, уже почти 10 лет. На подходе третья суперкомпьютерная революция. Правильнее было бы сказать даже, что она уже началась. Масштаб изменений, которые внесет ее завершение в мир технологий параллельной обработки данных, будет беспрецедентным. Именно это мешает нам охарактеризовать ее суть «в двух словах», как мы сделали это в случае первой и второй суперкомпьютерных революций. Оставим этот увлекательный рассказ до второй части книги, а пока остановимся на этой точке: сегодня (вчера?) весь мир считает, в основном, на кластерах.

1.3. Способы объединения многих процессоров в единую систему.

Многопроцессорные вычислительные комплексы принято делить на мультипроцессоры, то есть системы с общей, или разделяемой (между процессорами) памятью, и мультикомпьютеры, то есть системы из самостоятельных компьютеров, каждый – со своей, локальной, памятью, объединенных коммуникационной сетью. Мультикомпьютеры чаще называют системами с распределенной (между процессорами) памятью, или MPP-системами (Massively Parallel Processing, массово – параллельная обработка), или просто системами без общей памяти. На сегодняшний день такая классификация не может быть признана достаточной. Как класс мультипроцессоров, так и класс мультикомпьютеров подразделяются на подклассы, качественно различающиеся по способам интеграции процессоров. В итоге способы интеграции процессоров в единую вычислительную систему образуют не только иерархию, но и непрерывный спектр, от способов с наиболее сильными взаимосвязями между процессорами из класса мультипроцессоров до способов с наиболее слабыми взаимосвязями из класса мультикомпьютеров. Схематически эту классификацию можно представить себе так:

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

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

На самом «сильном» краю спектра в верхней части рисунка находятся SMP-системы (Symmetric Multi Processing). В этих мультипроцессорах вся имеющаяся в системе оперативная память общая, и вся она равно доступна всем процессорам.

Самый «слабый» край спектра в нижней части рисунка представлен MPP-системами на базе сетей двустороннего обмена данными. В этих системах для передачи данных из памяти одного процессора в память другого необходимы специальные, явно записанные в программе действия на обоих концах канала. Тот, кому требуются «чужие» данные, должен выполнить запрос на прием данных, а тот, у кого эти данные хранятся – запрос на их передачу. Только при таком совместном желании обоих участников обмена данные могут быть переданы от одного процессора к другому (отсюда название: «сети двусторонних обменов»).

Теперь остановимся на промежуточных по «силе» решениях.

Второй по «силе» способ интеграции процессоров – NUMA-системы (Non-Uniform Memory Access). Это системы, в которых память общая, но не обязательно вся, а главное – не все области памяти доступны всем процессорам на равных правах. Общая память в такой системе поделена (обычно – на блоки). Каждый из таких блоков принадлежит конкретному процессору, то есть обращения к нему из этого процессора происходят быстро. Все остальные, кроме «своего», блоки общей памяти также доступны процессору для прямой адресации обычными командами обращения к памяти, но выполняются эти команды гораздо медленнее, чем при доступе в «свой» блок. В зависимости от конкретной реализации, слово «гораздо» в предыдущей фразе может означать «вдвое медленнее», а может – и «в 300 раз медленнее».

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

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

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

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

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

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

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

Отметим, что все популярные в последнее время многоядерные процессоры являются, с логической точки зрения, SMP-системами.

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

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

Довольно часто узлом MPP-системы бывает не единичный однопроцессорный компьютер, а SMP-система сравнительно небольшого размера.

Еще совсем недавно средние позиции выстроенного нами спектра были заполнены плохо. Среди мультипроцессоров было мало NUMA-систем, и стоимость их зачастую мало отличалась от стоимости SMP-систем. Единственным преимуществом (кстати, очень важным) была значительно более высокая масштабируемость. С другой стороны, подавляющее большинство MPP-систем были системами на базе сетей двустороннего обмена данными. За годы, прошедшие после второй суперкомпьютерной революции, именно в этих промежуточных позициях спектра наблюдался устойчивый и значительный прогресс. NUMA-системы росли в размерах и дешевели, оставаясь, тем не менее, суперкомпьютерами на оригинальной схемотехнической базе (то есть не кластерами). При этом в классе сетевого оборудования для кластеров выделенных рабочих станций стало появляться все больше решений, поддерживающих на аппаратном уровне односторонние обмены данными. Третья суперкомпьютерная революция, о которой мы будем говорить во второй части книги, скорее всего, приведет к слиянию этих двух промежуточных классов. В самом деле, NUMA-систему можно рассматривать как «усовершенствованную» сеть односторонних обменов, в которой односторонний обмен запускается автоматически, на аппаратном уровне, при выполнении команды, адресующей «медленную», то есть «чужую», память. Очевидно, существование этих двух родственных, но не равноценных промежуточных классов – NUMA-систем и сетей одностороннего обмена данными – возможно лишь в случае, если системы «менее удобного» класса гораздо дешевле и доступнее. До совсем недавнего времени это так и было. NUMA-системы можно было строить исключительно на основе оригинальной схемотехники уровня плат и шкафов, причем с применением дорогостоящих заказных СБИС, в то время как сети односторонних обменов были кластерами на базе серийно выпускаемого оборудования. Изменения в архитектуре и технологии выпускаемых крупными сериями материнских плат, речь о которых пойдет во второй части книги, привели, фактически, к стиранию этой грани. NUMA-кластеры уже появляются, и коммуникационного оборудования в них не больше, а меньше, чем в «обычных» кластерах, а значит – буквально завтра они станут дешевыми и доступными. Скорее всего, это приведет не только к слиянию двух промежуточных классов нашего спектра, но и к частичному поглощению вновь образовавшимся классом «обычных» кластеров на базе сетей двустороннего обмена.

1.4. Альтернативные архитектуры. Классификация Флинна.

До сих пор мы молчаливо полагали, что параллельная вычислительная система, в любом случае, строится из универсальных (фоннеймановских) процессоров. Это далеко не всегда так. Например, векторный процессор – это тоже параллельная не фоннеймановская архитектура, но полученная не объединением в одну систему многих фоннеймановских процессоров, а другим способом – добавлением к универсальному процессору команд работы с векторами [3,4]. Мы не будем сейчас специально обсуждать вопросы векторных вычислений. Однако отметим, что узел как SMP-, так и MPP-системы может быть и векторным процессором. Также, как мы уже отмечали выше, узел MPP-системы может быть SMP- или NUMA-системой, размер которой заметно меньше размера установки в целом.

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

1). Один поток команд, один поток данных – SISD (Single Instruction, Single Data). Это – фоннеймановский компьютер.

2). Один поток команд, много потоком данных – SIMD (Single Instruction, Multiple Data). Это – векторный компьютер, процессор которого может, например, одной командой сложить покомпонентно два массива чисел.

3). Много потоков команд, много потоков данных – MIMD (Multiple Instruction, Multiple Data). В этот класс попадают все упомянутые нами выше многопроцессорные вычислители на базе фоннеймановских процессоров, независимо от способа объединения этих процессоров между собой – SMP, NUMA, MPP.

4). Много потоков команд, один поток данных – MISD (Multiple Instruction, Single Data). Некоторые исследователи компьютерных архитектур считают, что отдельные, экспериментальные вычислительные установки, известные им, могли бы претендовать на включение в этот класс. Большинство авторов полагает, что этот класс пуст, и вряд ли будет заполнен в обозримом будущем. Иногда практикуемое отнесение к этому классу систолических массивов [3] и даже векторно-конвейерных структур, на взгляд автора, имеет характер некоторой «терминологической натяжки».

1.5. Простейшая модельная программа.

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

1.5.1. Решение двумерной краевой задачи для уравнения теплопроводности методом Якоби.

Физика задачи: рассмотрим однородный прямоугольный параллелепипед («кирпич»), к боковым граням которого плотно прислонены «утюги» бесконечной массы и заданной температуры. По мере прогрева «кирпича» в нем установится некоторое распределение температуры, которое нам и требуется найти. Будем рассматривать двумерное приближение задачи. Это значит, что кирпич предполагается очень высоким, и нас будет интересовать распределение температуры в его горизонтальном срезе, достаточно удаленном как от верхней, так и от нижней грани. Для краткости будем далее называть эту задачу «задачей о прогреве кирпича». Подчеркнем, что ни физическая, ни вычислительно – математическая сторона этой прекрасно изученной задачи нас не интересует – мы рассматриваем ее как пример заданной и не обсуждаемой вычислительной процедуры, для которой надо построить параллельную реализацию [2].

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

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

- для каждой ячейки вычисляем новое значение как среднее арифметическое значений четырех ее соседей,

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

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

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

include <stdio.h>

/***/

#define MX 640

#define MY 480

#define NITER 10000

#define STEPITER 100

static float f[MX][MY];

static float df[MX][MY];

/***/

int main( int argc, char **argv )

{

int i, j, n, m;

FILE *fp;

/***/

printf( "Solving heat conduction task on %d by %d grid\n",

MX, MY );

fflush( stdout );

/* Initial conditions: */

for ( i = 0; i < MX; i++ )

{

for ( j = 0; j < MY; j++ )

{

f[i][j] = df[i][j] = 0.0;

if ( (i == 0)

|| (j == 0) ) f[i][j] = 1.0;

else if ( (i == (MX-1))

|| (j == (MY-1)) ) f[i][j] = 0.5;

}

}

/* Iteration loop: */

for ( n = 0; n < NITER; n++ )

{

if ( !(n%STEPITER) ) printf( "Iteration %d\n", n );

/* Step of calculation starts here: */

for ( i = 1; i < (MX-1); i++ )

{

for ( j = 1; j < (MY-1); j++ )

{

df[i][j] = ( f[i][j+1] + f[i][j-1] + f[i-1][j] + f[i+1][j] )

* 0.25 - f[i][j];

}

}

for ( i = 1; i < (MX-1); i++ )

{

for ( j = 1; j < (MY-1); j++ )

{

f[i][j] += df[i][j];

}

}

}

/* Calculation is done, F array is a result: */

fp = fopen( "progrev.dat", "w" );

for ( i = 1; i < (MX-1); i++ )

fwrite( f[i]+1, MY-2, sizeof(f[0][0]), fp );

fclose( fp );

return 0;

}

1.5.2. Параллельная реализация «на бумаге».

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

Рис. 1.2. Массив F из 14 строк, поделенный между 3 процессорами.

Строки 0 и 13 – граничные условия.

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

Если наша машина – SMP-система, то параллельную реализацию мы построили. Если это – NUMA-система, то мы ее построили, при условии, что нам удастся расположить каждую полосу массивов F и DF в памяти, «своей» для обрабатывающего эти полосы процессора. В обоих этих случаях весь массив F, изображенный на рисунке, располагается в общей памяти, доступной всем процессорам. При этом каждый процессор, зная собственный номер, выполняет цикл обхода строк не всего массива, а только своей полосы: нулевой процессор модифицирует строки с 1-й по 4-ю, первый – с 5-й по 8-ю, и т. д. Пределы изменения переменной цикла по строкам у каждого процессора свои. Нулевая и 13-я строки массива содержат граничные условия и не обрабатываются. Обработка 12 строк поделена между процессорами поровну, каждому досталось по 4 строки.

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

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

Рис. 1.3. Локальная порция массива F на первом процессоре.

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

Теперь параллельную реализацию «на бумаге» можно считать построенной и для случая кластера. Далее будем, если явно не оговорено противное, говорить только о кластерах (точнее, об MPP-системах).

1.5.3. Что потребуется для параллельной реализации на практике.

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

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

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

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

Написанная нами программа для обобщенного узла номер i называется ветвью параллельной про<