ГЛАВА 9. Основы параллельных вычислений

 

В основе архитектуры большинства современных ВМ лежит представление алго­ритма решения задачи в виде программы последовательных вычислений. Базовые архитектурные идеи ВМ, ориентированной на последовательное исполнение ко­манд программы, были сформулированы Джоном фон Нейманом. В условиях по­стоянно возрастающих требований к производительности вычислительной техники все очевидней становятся ограничения классической фон-неймановской архитек­туры, обусловленные исчерпанием всех основных идей ускорения последователь­ного счета. Дальнейшее развитие вычислительной техники связано с переходом к параллельным вычислениям как в рамках одной ВМ, так и путем создания мно­гопроцессорных систем и сетей, объединяющих большое количество отдельных процессоров или отдельных вычислительных машин. Для такого подхода вместо термина «вычислительная машина» более подходит термин «вычислительная си­стема» (ВС). Отличительной особенностью вычислительных систем является на­личие в них средств, реализующих параллельную обработку, за счет построения параллельных ветвей в вычислениях, что не предусматривалось классической структурой ВМ. Идея параллелизма как средства увеличения быстродействия ЭВМ возникла очень давно — еще в XIX веке.

Уровни параллелизма

 

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

· Уровень заданий. Несколько независимых заданий одновременно выполня­ются на разных процессорах, практически не взаимодействуя друг с другом. Этот уровень реализуется на ВС с множеством процессоров в многозадачном режиме.

· Уровень программ. Части одной задачи выполняются на множестве процессо­ров. Данный уровень достигается на параллельных ВС.

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

· Уровень битов (арифметический уровень). Биты слова обрабатываются один за другим, это называется бит-последовательной операцией. Если биты слова обрабатываются одновременно, говорят о бит-параллельной операции. Данный уровень реализуется в обычных и суперскалярных процессорах.

К понятию уровня параллелизма тесно примыкает понятие гранулярности. Это мера отношения объема вычислений, выполненных в параллельной задаче, к объему коммуникаций (для обмена сообщениями). Степень гранулярности варьируется от мелкозернистой до крупнозернистой. Определим понятия крупнозернистого (coarse grained), среднезернистого (medium grained) и мелкозернистого (fine grai­ned) параллелизма.

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

Среднезернистый параллелизм: единицами распараллеливания являются вызы­ваемые процедуры, включающие в себя сотни команд. Обычно организуется как программистом, так и компилятором.

Мелкозернистый параллелизм: каждое параллельное вычисление достаточно мало и элементарно, составляется из десятков команд. Обычно распараллеливае­мыми единицами являются элементы выражения или отдельные итерации цикла, имеющие небольшие зависимости по данным. Сам термин «мелкозернистый па­раллелизм» говорит о простоте и быстроте любого вычислительного действия. Характерная особенность мелкозернистого параллелизма заключается в прибли­зительном равенстве интенсивности вычислений и обмена данными. Этот уровень параллелизма часто используется распараллеливающим (векторизирующим) ком­пилятором.

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

9.1.1. Параллелизм уровня задания

 

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

В качестве примера рассмотрим вычислительную систему с четырьмя процес­сорами. ВС обрабатывает задания, классифицируемые как малое (S), среднее (М) и большое (L). Для выполнения малых заданий требуется один, средних — два, а больших заданий — четыре процессора. Обработка каждого задания занимает одну условную единицу времени. Первоначально существует такая очередь заданий: S M L S S M L L S M M (таблица 6).

 

Таблица 6
Время	Выполняемые задания	% использования ВС
	S, M
	L
	S, S, М
	L
	L
	S, М
	М

 

При этом средний уровень использования ресурсов вычислительной системы равен 83,3%; на выполнение всех заданий требуется 7 единиц времени.

Для получения большей степени утилизации ресурсов ВС разрешим заданиям «выплывать» в начало очереди. Тогда можно получить следующую последователь­ность выполнения заданий: S M S L S M S L L M M (таблица 7).

 

Таблица 7
Время	Выполняемые задания	% использования ВС
	S, M, S
	L
	S, М, S
	L
	L
	М, М

 

При этом средний процент использования ресурсов ВС составляет 100%; на выполнение всех заданий требуется 6 единиц времени.

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

Пусть выполняется задание и оно для своего продолжения нуждается в выпол­нении ввода/вывода. По сравнению с вычислениями он обычно более длителен, поэтому текущее задание приостанавливается и запускается другое задание. Ис­ходное задание активизируется после завершения ввода/вывода. Все это требует специального оборудования: каналов В/ВЫВ или специальных процессоров В/ ВЫВ. За то, как различные задания упорядочиваются и расходуют общие ресур­сы, отвечает операционная система.

Параллелизм уровня программ

 

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

 

Таблица 8
Задача	Зрение	Манипуляция	Движение
Поиск розетки	X		X
Движение к розетке	X		X
Подключение к розетке	X	X

 

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

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

 

For I:=l to N do A(I):=B(I) + C(I)

 

Все суммы независимы, то есть вычисление В_i + С_i не зависит от B_j + C_j для любо­го j < i. Это означает, что вычисления могут производиться в любой последова­тельности и в вычислительной системе с N процессорами все суммы могут быть вычислены одновременно.

Общая форма параллелизма на уровне программ проистекает из разбиения про­граммируемых данных на подмножества. Это разделение называют декомпозицией области (domain decomposition), а параллелизм, возникающий при этом, носит название параллелизма данных. Подмножества данных назначаются разным вы­числительным процессам, и называется этот процесс распределением данных (data distribution). Процессоры выделяются определенным процессам либо по инициа­тиве программы, либо в процессе работы операционной системой. На каждом про­цессоре может выполняться более чем один процесс.

Параллелизм уровня команд

 

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

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