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

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

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

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

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

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

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

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

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

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

Теперь допустим, что есть два точно таких же устройства, которые могут работать одновременно и независимо друг от друга. Для простоты будем рассматривать идеальную ситуацию, когда нет никаких дополнительных накладных расходов, связанных с получением устройствами входных данных и сохранением результатов. Постоянно загружая каждое устройство элементами входных массивов, можно получить исходную сумму уже за 250 тактов. В случае десяти подобных устройств, время получения результата составит всего 50 тактов, а в общем случае система из N устройств затратит на суммирование время около 500/N.

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

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

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

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

В общем случае конвейерное устройство содержит M ступеней, а каждая ступень срабатывает за одну единицу времени, то время обработки N независимых операций этим устройством составит M+N-1 единиц. Если это же устройство используется как последовательное, то время обработки будет равно M*N. В результате для больших значений N получили ускорение почти в M раз за счет использования конвейерной обработки данных. Причем, чем больше длина входных данных, тем производительней конвейерное устройство.

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

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

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

• Второй класс – это компьютеры с распределенной памятью (рис. 1.2). По сути дела, каждый вычислительный узел является полноценным компьютером со своим процессором, памятью, подсистемой ввода/вывода, операционной системой. Каждый процессор имеет свою память и работает в своем адресном пространстве.

Рис. 1.1

Рис. 1.2

Рассмотрим простейшие примеры сетевой топологии – связи между прцессорами (рис. 1.3а). Обьединение N вычислительных узлов в одну линейку требует N-1 соединение. Средняя длина пути между двумя узлами равна N/3. простым преобразованием линейки в кольцо (рис. 1.3б) можно уменьшить длину пути до N/6. При этом, за счет того, что передача между двумя любыми узлами может идти по двум независимым направлениям, увеличилась отказоустойчивость системы. Пока все связи работоспособны, будет идти передача данных по кратчайшему пути. Но если нарушилась какая-либо одна связь, то возможна передача в противоположном направлении.

Рис. 1.3

а

б

в

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

Хочется упомянуть такие типичные топологии коммуникации процессоров, как полный граф, решетка, гиперкуб и трехмерный тор. Полный граф – топология, в которой между любой парой процессоров существует линия связи. В результате, данный способ соединения процессоров обеспечивает минимальные затраты при передаче данных, но из-за технических сложностей он используется только при небольшом числе процессоров. Решетка – топология, в которой линии связи образуют двумерную или трехмерную прямоугольную сетку. Гиперкуб – многомерная прямоугольная сетка линий связи, в которой по каждой размерности имеется только два процессора (гиперкуб содержит процессоров при размерности N); Трехмерный тор – система типа трехмерной решетки, у которой каждая линия в любом из направлений замкнута в кольцо.

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

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

Рассмотрим известный пример сложения восьми чисел. Однопроцессорный алгоритм сложения этих чисел показан на рис. 1.4а. Он эффективно реализуется с помощью оператора цикла и требует семь операций сложения. Лучшего здесь ничего не придумаешь. Но, имея восемь процессоров и размещая каждое число на одном из процессоров, мы можем сложить эти числа за три операции, как показано на рис. 1.4б. Легко видеть, что реализовать этот алгоритм на однопроцессорной машине более сложно, чем первый алгоритм, и очевидно, что он не будет более быстрым. Этот пример наглядно показывает разницу между последовательным и параллельным алгоритмом. В этом же примере можно увидеть и некоторые проблемы, которые возникают при распараллеливании алгоритмов. Первое – это то, что возникают обмены данными между процессорами. И очевидно, что скорость передачи данных играет большую роль в оценке эффективности распараллеливания. Понятно, что чем больше происходит вычислений на процессоре, и чем меньше обменов данными между процессорами, тем параллельный алгоритм эффективнее. Второй вывод, который можно сделать на этом примере, заключается в том, что хотя мы имеем восемь процессоров, мы не можем сложить восемь чисел за одну операцию. В данном случае легко подсчитать, что для сложения N чисел необходимо порядка log(N) операций.

Рис. 1.4

а

б

б

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

Физико-математическая декомпозиция задачи является одним из глобальных видов структурирования высокого уровня и связана с расщеплением исследуемого физического процесса по составляющим его подпроцессам и, соответственно, с сегментацией общего математического алгоритма решения полной задачи на ряд алгоритмов решения составляющих подзадач. Например, при решении задачи о движении летательного аппарата в газовых средах с учетом широкого спектра физических явлений могут быть промоделированы раздельно (параллелизованы) подзадачи «механика», «физико-химическая кинетика», «термодинамика», «турбулентность» с их соответствующим интерфейсом. Специфическим видом физической декомпозиции может быть названа «траекторная» задача, когда требуется провести цикл расчетов при изменении одного или нескольких глобальных входных параметров, в частности, определенного набора значений скорости V и высоты H полета. Такая задача хорошо коррелирует с архитектурой многопроцессорной системы с распределенной памятью: «единые инструкции – множественные данные» (весь полный пакет программ в комплексе моделирующих механику и физику явления – заданный набор значений V и/или H).

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

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

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

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

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

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

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

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

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

Для оценки ускорения q, которое возможно получить на компьютере из p процессоров, можно воспользоваться законом Амдала

где f - доля операций, необходимо выполняемых последовательно. Интервал изменения f[0,1], крайние случаи в значениях f соответствуют полностью параллельным (f=0) и полностью последовательным (f=1) программам. Заметим, что даже при p рост ускорения ограничен пределом q1/f, и если в некоторых подпрограммах, составляющих код, значение f велико, то следует заняться «расшивкой этих узких мест». Множитель k в законе Амдала есть коэффициент, корректирующий (уменьшающий, k[0,1]) возможное ускорение вычислительного процесса из-за задержек, связанных с маршрутизацией, обменом и подкачкой данных, в том числе режимов ожидания с возможностью «зависания» некоторых процессоров и возникновением тупиковых ситуаций. Этот коэффициент весьма эмпиричен, и его более или менее точное значение может быть определено лишь в вычислительном эксперименте. Поэтому закон Амдала достаточно точно дает значение q лишь в «идеальном» (k=1) смысле, без учета замедления вычислительного процесса из-за обменов данными.

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