Параллельная обработка данных на эвм. Последовательная и параллельная обработка информации

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

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

2. Обеспечение высокой надежности ВС за счет дублирования вычислительной аппаратуры.

Рис. 5.1. Уровни параллелизма

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

Параллельная обработка информации может производиться на нескольких уровнях (рис. 5.1).

Очевидно, что чем ниже уровень, тем мельче дробление программных процессов, тем мельче, как принято говорить, «зерно параллелизма ». В общем случае возможно реализовать параллелизм как на отдельном уровне, так и на нескольких одновременно. Независимая однопроцессорная обработка реализует параллелизм на уровне 1. Векторная обработка заключается в параллельном выполнении циклов на уровне 2 и может производиться как на одном, так и нескольких процессорах. Уровни 3 и 4 соответствуют многопроцессорным ВС. Параллелизм уровня 5 характерен для многомашинных вычислительных комплексов.

Существует два основных способа организации параллельной обработки:

· совмещение во времени этапов решения разных задач;

· одновременное решение различных задач или частей одной задачи;

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

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

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

1. Естественный параллелизм независимых задач.

2. Параллелизм объектов или данных.

3. Параллелизм ветвей задачи или программы.

Рассмотрим эти типы параллелизма.

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

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

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

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

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

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

· ни одна из выходных вели­чин этих ветвей задачи не является входной величиной для другой такой ветви (отсутствие функциональных связей);

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

Хорошее представление о параллелизме ветвей дает ярусно-параллельная форма(ЯПФ) програм­мы, пример которой приведен на рис. 5.2.

Программа представлена в виде совокупности ветвей, расположенных на нескольких уровнях - ярусах. Кружками с цифрами внут­ри обозначены ветви. Длина ветви представляется цифрой, стоящей около кружка и говорящей, сколько временных единиц выполняется данная ветвь. Стрелками показаны входные данные и результаты обработки. Входные данные обозначаются символом X, выходные данные - символом Y. Символы Х имеют нижние цифровые индексы, обозначающие номера входных величин; символы Y имеют цифровые индек­сы и внизу, и вверху; цифра вверху соответствует номеру ветви, при выполнении которой получен данный результат, а цифра внизу означает порядковый номер результата, по­лученного при реализации данной ветви программы. На одном ярусе размещаются независимые ветви задачи, не связанные друг с другом, т.е. результаты решения ка­кой-либо ветви данного яруса не являются входными дан­ными для другой ветви этого же яруса.

Рис. 5.2. Пример ярусно-параллельной формы программы

Изображенная на рис. 5.2 программа содержит 9 вет­вей, расположенных на 3 ярусах. На примере этой, в общем, достаточно простой прог­раммы, можно выявить преимущества вычислительной систе­мы, включающей несколько обрабатывающих устройств, и проблемы, которые при этом возникают.

Примем, что длина i -й ветви представляется числом временных единиц t i , которые требуются для ее исполнения. Тогда нетрудно подсчитать, что для исполнения всей программы на 1 процессоре потребуется время T 1 :

T 1 =S (10+20+15+30+55+10+15+25+15)=195

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

Рассмотрим, например, такой вариант выполнения программы, представленной на рис. 5.2. Пусть процессор 1 выполняет ветви 1-3-4-6-7-9, а процессор 2 выпол­няет ветви 2-5-8. На рис. 5.3 представлены временные диаграммы выполнения процессорами ветвей программы.

Рис. 5.3. Разложение ветвей программы по 2 процессорам

Нетрудно подсчитать, что процессор 1 затрачивает 105, а процессор 2 - 100 единиц времени. При этом имеется два промежутка времени, когда один из процессоров вынужденно простаивает – П1 длительностью 10 единиц и П2 длительностью 5 единиц времени. Промежуток П1, во время которого работает только процессор 2, образовался из-за того, что ветвь 7 зависит от ветви 5 (к моменту завершения ветви 6 еще не готовы данные Y 5 1). Промежуток П1, во время которого работает только процессор 1, образовался по причине окончания счета процессором 2.

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

Коэффициент распараллеливанияизменяется от 0 до 1 (от 0 до 100%) и отражает эффективность использования вычислительных ресурсов. В нашем примере нетрудно посчитать, что ускорение S = 195/105 = 1,86, а коэффициент распараллеливания K п = 0,93. Как видим, по причине простоев одного из процессоров ускорение счета значительно меньше 2, т.е. количества используемых процессоров. Заметим, что в нашем примере не учитывались временные задержки, связанные с переключением контекстов программы (смены ветвей) и передачи данных от одной ветви к другой. Тем не менее, в силу алгоритмических особенностей программы, часть вычислений в промежутки П1 и П2 производится только одним процессором, т.е. фактически последовательно.

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

Данное соотношение носит название закона Амдала . На примере программы рис. 5.2 мы можем видеть, что доля последовательных вычислений составляет f = 15/195. Подставляя эту величину в формулу закона Амдала, получаем для системы из двух процессоров максимальное ускорение 1,86 раза, что соответствует ранее рассчитанному значению.

Для иллюстрации действия закона Амдала приведем следующий пример. Пусть доля последовательных вычислений в некоторой программе составляет 10%. Тогда максимальное ускорение счета на 100 процессорах не превысит 9,2. Коэффициент распараллеливания составит всего лишь 9,2%. На 10 процессорах ускорение составит 5,3, а коэффициент распараллеливания ‑ 53%. Нетрудно видеть, что даже такая небольшая доля последовательных вычислений уже на теоретическом уровне, без учета неизбежных задержек в реальной ВС, серьезно ограничивает возможности масштабирования программы.

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

Соотношение (5.6) определяет очень важное следствие из закона Амдала. Для того, чтобы ускорить программу в q раз, необходимо ускорить не менее, чем в q раз не менее, чем () -ю часть программы . Например, чтобы получить ускорение в 100 раз, необходимо распараллелить 99,99% всей программы.

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

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

1.2 Параллельная обработка данных

1.2.1 Принципиальная возможность параллельной обработки

Практически все разработанные к настоящему времени алгоритмы являются последовательными. Например, при вычислении выражения a + b × c , сначала необходимо выполнить умножение и только потом выполнить сложение. Если в электронно-вычислительных машин присутствуют узлы сложения и умножения, которые могут работать одновременно, то в данном случае узел сложения будет простаивать в ожидании завершения работы узла умножения. Можно доказать утверждение, состоящее в том, что возможно построить машину, которая заданный алгоритм будет обрабатывать параллельно.

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

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

1.2.2 Абстрактные модели параллельных вычислений

Модель параллельных вычислений обеспечивает высокоуровневый подход к определению характеристик и сравнению времени выполнения различных программ, при этом абстрагируются от аппаратного обеспечения и деталей выполнения. Первой важной моделью параллельных вычислений явилась машина с параллельным случайным доступом (PRAM – Parallel Random Access Machine), которая обеспечивает абстракцию машины с разделяемой памятью (PRAM является расширением модели последовательной машины с произвольным доступом RAM – Random Access Machine). Модель BSP (Bulk Synchronous Parallel, массовая синхронная параллельная) объединяет абстракции как разделенной, так и распределенной памяти. Считается, что все процессоры выполняют команды синхронно; в случае выполнения одной и той же команды PRAM является абстрактной SIMD-машиной, (SIMD – Single Instruction stream/Multiple Data stream – одиночный поток команд наряду со множественным потоком данных), однако процессоры могут выполнять и различные команды. Основными командами являются считывание из памяти, запись в память и обычные логические и арифметические операции.

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

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

Моделировать схемы из функциональных элементов с помощью параллельных машин с произвольным доступом (PRAM) позволяет теорема Брента. В качестве функциональных элементов могут выступать как 4 основных (осуществляющих логические операции NOT, AND, OR, XOR – отрицание, логическое И, логическое ИЛИ и исключающее ИЛИ соответственно), более сложные NAND и NOR (И-НЕ и ИЛИ-НЕ), так и любой сложности.

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

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

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

На рисунке 1 приведен результат моделирования схемы размером (общее количество процессоров) n=15 при глубине схемы (максимальное число элементов на каждом из уровней глубины) d=5 с числом процессоров p=2 (одновременно моделируемые элементы объединены в группы прямоугольными областями, причем для каждой группы указан шаг, на котором моделируются ее элементы; моделирование происходит последовательно сверху вниз в порядке возрастания глубины, на каждой глубине по р штук за раз). Согласно теоремы Брента моделирование такой схемы займет не более ceil(15/2+1)=9 шагов.

«Параллелизм как способ параллельной обработки данных»

Котовск2010

Введение

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

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

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

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

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

1. Параллельные вычислительные системы

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

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

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

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

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

2. Типы параллелизма

2.1 Параллелизм на уровне битов

Эта форма параллелизма основана на увеличении размера машинного слова. Увеличение размера машинного слова уменьшает количество операций, необходимых процессору для выполнения действий над переменными, чей размер превышает размер машинного слова. К примеру: на 8-битном процессоре нужно сложить два 16-битных целых числа. Для этого вначале нужно сложить нижние 8 бит чисел, затем сложить верхние 8 бит и к результату их сложения прибавить значение флага переноса. Итого 3 инструкции. С 16-битным процессором можно выполнить эту операцию одной инструкцией.

Исторически 4-битные микропроцессоры были заменены 8-битными, затем появились 16-битные и 32-битные. 32-битные процессоры долгое время были стандартом в повседневных вычислениях. С появлением технологии x86–64 для этих целей стали использовать 64-битные процессоры.

2.2 Параллелизм на уровне инструкций

Компьютерная программа – это, по существу, поток инструкций, выполняемых процессором. Но можно изменить порядок этих инструкций, распределить их по группам, которые будут выполняться параллельно, без изменения результата работы всей программы. Данный приём известен как параллелизм на уровне инструкций. Продвижения в развитии параллелизма на уровне инструкций в архитектуре компьютеров происходили с середины 1980-х до середины 1990-х.

Современные процессоры имеют многоступенчатый конвейер команд. Каждой ступени конвейера соответствует определённое действие, выполняемое процессором в этой инструкции на этом этапе. Процессор с N ступенями конвейера может иметь одновременно до N различных инструкций на разном уровне законченности. Классический пример процессора с конвейером – это RISC-процессор с 5-ю ступенями: выборка инструкции из памяти (IF), декодирование инструкции (ID), выполнение инструкции (EX), доступ к памяти (MEM), запись результата в регистры (WB). Процессор Pentium 4 имеет 35-тиступенчатый конвейер.

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

2.3 Параллелизм данных

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

2.4 Параллелизм задач (многопоточность)

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

2.5 Распределенные операционные системы

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

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

лекции (34 часа), зачет

Кафедра, отвечающая за курс : АСВК

Составитель программы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.,

Лекторы : чл.-кор. РАН, доктор физ.-мат. наук Воеводин Вл.В.

Аннотация

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

Программа

2. Основные классы современных параллельных вычислительных систем. Компьютеры с общей памятью, примеры, причины снижения производительности на реальных программах. Архитектуры SMP, NUMA, ccNUMA. Коммутация процессоров и модулей памяти, шина, матричный коммутатор, омега-сеть. Векторно-конвейерные вычислительные системы, примеры, причины снижения производительности. Компьютеры с распределенной памятью, примеры, причины снижения производительности. Топология связи между процессорами: звезда, решетка, трехмерный тор, двоичный гиперкуб, их свойства. Вычислительные кластеры, примеры, латентность и пропускная способность различных коммуникационных технологий. Архитектуры с параллелизмом на уровне машинных команд, VLIW, суперскалярность.

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

4. Производительность параллельных вычислительных систем. Универсальность и специализация компьютеров, производительность спецпроцессоров. Закон Мура. Методы оценки производительности. Введение единого числового параметра, Mflops, MIPS. Пиковая и реальная производительность компьютеров. Тест Linpack и его варианты. Наборы взаимодополняющих тестовых программ, STREAM и NPB.

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

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

Литература

2. Королев Л.Н. Архитектура процессоров электронных вычислительных машин. – М.: Изд. факультета ВМК МГУ, 2003.

3. В.В.Корнеев. Параллельные вычислительные системы. – М.: Изд-во "Нолидж", 1999. – 320с.

4. Материалы информационно-аналитического центра по параллельным вычислениям Parallel.ru.

Дополнительная литература

MPI: Учебное пособие. – М.: Изд-во МГУ, 2004. - 71 с.

Увеличение производительности ЭВМ, за счет чего?

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

Попробуем разобраться, какой из этих факторов оказывается решающим для достижения рекордной производительности. Обратимся к известным историческим фактам. На одном из первых компьютеров мира - EDSAC, появившемся в 1949 году в Кембридже и имевшем время такта 2 микросекунды (2*10-6 секунды), можно было выполнить 2*n арифметических операций за 18*n миллисекунд, то есть в среднем 100 арифметических операций в секунду. Сравним с одним вычислительным узлом современного суперкомпьютера Hewlett-Packard V2600: время такта приблизительно 1.8 наносекунды (1.8*10-9 секунд), а пиковая производительность около 77 миллиардов арифметических операций в секунду.

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

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

Параллельная обработка . Если некое устройство выполняет одну операцию за единицу времени, то тысячу операций оно выполнит за тысячу единиц. Если предположить, что есть пять таких же независимых устройств, способных работать одновременно, то ту же тысячу операций система из пяти устройств может выполнить уже не за тысячу, а за двести единиц времени. Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут - принцип параллельности в действии!

Кстати, пионером в параллельной обработке потоков данных был академик А.А.Самарский, выполнявший в начале 50-х годов расчеты, необходимые для моделирования ядерных взрывов. Самарский решил эту задачу, посадив несколько десятков барышень с арифмометрами за столы. Барышни передавали данные друг другу просто на словах и откладывали необходимые цифры на арифмометрах. Таким образом, в частности, была расчитана эволюция взрывной волны. Работы было много, барышни уставали, а Александр Андреевич ходил между ними и подбадривал. Это, можно сказать, и была первая параллельная система. Хотя расчеты водородной бомбы были мастерски проведены, точность их была очень низкая, потому что узлов в используемой сетке было мало, а время счета получалось слишком большим.

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

Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получаем очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Казалось бы конвейерную обработку можно с успехом заменить обычным параллелизмом, для чего продублировать основное устройство столько раз, сколько ступеней конвейера предполагается выделить. В самом деле, пять устройств предыдущего примера обработают 100 пар аргументов за 100 единиц времени, что быстрее времени работы конвейерного устройства! В чем же дело? Ответ прост, увеличив в пять раз число устройств, мы значительно увеличиваем как объем аппаратуры, так и ее стоимость. Представьте себе, что на автозаводе решили убрать конвейер, сохранив темпы выпуска автомобилей. Если раньше на конвейере одновременно находилась тысяча автомобилей, то действуя по аналогии с предыдущим примером надо набрать тысячу бригад, каждая из которых (1) в состоянии полностью собрать автомобиль от начала до конца, выполнив сотни разного рода операций, и (2) сделать это за то же время, что машина прежде находилась на конвейере. Представили себестоимость такого автомобиля? Нет? Согласен, трудно, разве что Ламборгини приходит на ум, но потому и возникла конвейерная обработка...