Software & Systems

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

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

Параллелизм по данным

В модели c параллелизмом по данным (называется также параллелизм данных, data parallel) используется «естественный параллелизм», возникающий при обработке по одним и тем же формулам регулярных структур данных, в первую очередь массивов. Так, цикл обработки массивов можно записать одной векторной операцией: A(1:N)=B(1:N) * C(1:N)+D(1:N).

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

Из-за простоты программирования модель получила широкое распространение. Элементы модели параллелизма по данным были введены даже в последовательном языке Фортран-95, в частности, в конструкциях FORALL – для организации параллельных циклов и WHERE – для задания условий при операциях над массивами. В качестве примеров параллельных языков, построенных на основе данной модели, назовем CM FORTRAN, C*, HIGH PERFORMANCE FORTRAN (HPF2).

Модель параллелизма по данным использовалась при создании вычислителей класса SIMD, таких как векторные. Существует два основных подхода к реализации операций над массивами: создание векторных процессоров и реализация векторных ускорителей.

Системы, построенные на векторных процессорах, поддерживают векторные операции память-память, что обеспечивает непосредственное отображение модели программирования на реальное выполнение операций и высокую эффективность. В настоящее время выпускаются векторные системы NEC SX-8 и Cray X1E. Для программирования векторных ЦП используются векторные расширения языков программирования. Принцип конвейерной обработки, пришедший из векторных систем, используется во всех процессорах.

Векторные ускорители реализовывали подход разделения вычислительной и управляющей частей программы. В настоящее время ускорители встраиваются внутрь кристалла, например, Intel SSE, IBM VMX. В микропроцессоре IBM Cell реализовано сразу восемь ускорителей.

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

vector float a,b,c;

c=vec_add(a,b);

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

Модель параллелизма по данным не ограничивается выполнением на системах класса SIMD. Для выполнения на системах с множественным потоком команд в языках, в частности HPF, используется отображение данных на множество реальных процессоров. Специалисты предложили ввести особый тип данных – распределение индексного пространства по процессорам. Объекты данного типа используются для выравнивания распределенных массивов и циклов. Такой тип данных, в частности, реализован в языке системы распараллеливания RATIO и в языке HPF (ключевое слово TEMPLATE). В языке DVM используются дополнительные к HPF директивы для явного указания динамического размещения данных.

В следующем примере на языке RATIO вводится переменная типа распределение (DIST), по ней выравниваются массивы A и B, а также пространство итераций цикла.

  real a(16), b(22)

C$RATIO DISTRIBUTION DIST /( N_PROC) (1:10)/

C$RATIO SPLIT A(DIST)

C$RATIO SPLIT B(DIST+1)

   ...

   do i = 1, 10

C$RATIO placed pardo with (DIST)

      a(i)=b(i+1)

   enddo

Общая память

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

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

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

Одним из механизмов выполнения параллельных процессов стало многонитевое программирование «легковесных процессов», для которых не создаются полноценные процессы с отдельным адресным пространством, но которые все же могут распределяться по процессорам. Появился стандарт создания нитей POSIX Pthread, поддерживаемый всеми ведущими производителями. В настоящее время широко используется OpenMP – расширение языков С/С++ и Фортран, представляющее директивы компилятору. OpenMP представляет концепцию нитей и часто ими же реализуется. Программа на языке OpenMP является последовательно-параллельной. Последовательные участки выполняются корневым процессом. Для выполнения параллельных участков образуются нити.

Основные конструкции организации параллельных нитей в языке OpenMP:

!$OMP PARALLEL     < параллельный код >

!$OMP END PARALLEL

и

!$OMP PARALLEL DO       < код распределенного цикла >

!$OMP END PARALLEL DO

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

При создании SMP-систем возникают физические ограничения на количество процессоров, которые могут эффективно работать над одними модулями памяти. С увеличением количества процессоров становится необходимым создавать системы с распределенной памятью. Однако накопленный опыт и относительная простота параллельного программирования с общей памятью делают желательным использование этого механизма при максимально возможном количестве процессоров. Для решения этой задачи был разработан механизм создания общего адресного пространства из набора локальных памятей, который получил название NUMA (Non uniform memory access). Для идентичной функциональности требовалось решить проблему когерентности кэш-памятей процессоров. В таком варианте механизм стал называться CC-NUMA (от cache coherent).

В качестве примера системы, использующей CC-NUMA, является SGI Altix. Эта система позволяет использовать общее адресное пространство 512 процессорам.

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

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

Отдельно стоят функциональные языки и языки однократного присваивания: n-parallel PRO­LOG, Норма и потоковые архитектуры.

Распределенная память

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

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

При программировании таких систем чаще всего используется коммуникационные библиотеки PVM и MPI, обеспечивающие передачи сообщений между процессорами. MPI фактически стал международным стандартом программирования модели с передачей сообщений. Реализации MPI существуют практически для всех многопроцессорных вычислительных систем. MPI включает большой набор средств, ключевыми являются подпрограммы передачи данных от одного процесса к другом (другим). MPI реализован для языков С и Фортран и поддерживает все типы данных, имеющиеся в этих языках. В следующем примере приведены два вызова подпрограмм MPI – передачи и приема вещественной переменной A от процессора номер 0 к процессору номер 1 соответственно.

call MPI_SEND(A, 1, MPI_REAL, 1, TAG,& MPI_COMM_WORLD, ierr);call MPI_RECV(A, 1, MPI_REAL, 0, TAG, & MPI_COMM_WORLD, status, ierr);

Среди других языков, реализующих механизм передачи сообщений, отметим Occam и Linda, которые явно помещают данные в канал или кортеж. Языки mpC и co-array Fortran (рекомендован как часть нового стандарта Фортрана) не содержат явных передач данных, однако позволяют адресовать локальные копии элементов данных. Операция над локальными копиями данных, принадлежащим разным процессорам, подразумевает передачу данных.

Например, в языке mpC следующая конструкция [row0]neighbour[]=[row1]me[]; заключается в параллельной пересылке содержимого соответствующей проекции массива me от каждого j-го виртуального процессора строки row1 каждому j-му виртуальному процессору строки row0 с последующим его присваиванием соответствующей проекции массива neighbour.

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

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

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

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

Из других топологий отметим дерево и идеальное тасование.

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

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

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

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

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

В следующем примере внешний цикл как наиболее крупноблочный реализуется на разных узлах кластера, параллелизм записан в синтаксисе HPF. Средний цикл реализуется нитями на SMP-узле кластера и записан в синтаксисе OpenMP. Внутренний цикл записан как команда для скалярного произведения в языке Фортран.

!$HPF INDEPENDENT

DO I = 1, N

!$OMP PARALLEL DO 

DO J = 1, N

A(I,J)=DOTPRODUCT(B(I,1:N),C(1:N,J))

ENDDO

!$OMP END PARALLEL DO

ENDDO

При уменьшении частоты и объема взаимодействия параллельных процессов (то есть при уменьшении связности параллельной программы) снижаются требования к коммуникационной сети – латентности и пропускной способности. Слабо связные приложения возможно выполнять на метакомпьютере или вычислительной GRID-системе. С другой стороны, удаленная обработка экспериментальных данных также требует распределенных GRID-систем. Модели программирования метакомпьютеров принципиально не отличаются от программирования систем с распределенной памятью. В частности, реализованы версии MPI для GRID, такие как PACX-MPI и MPICH-G2.