Параллельное программирование

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

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

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

Классификация компьютерных систем. Разнообразие способов организации параллельных вычислительных систем побудило научный мир к решению задачи классификации. Самая ранняя и наиболее известная классификация М. Флинна (M. Flynn) предложена в 1966 году. Ключевое понятие здесь — поток. На основе числа потоков команд и потоков данных Флинн делит все системы на четыре класса архитектур:

– SISD (Single Instruction stream/Single Data stream) — одиночный поток команд и одиночный поток данных. К этому классу относятся машины классического, фон-неймановского типа.

– SIMD (Single Instruction stream/Multiple Data stream) — одиночный поток команд и множественный поток данных. Здесь один поток команд манипулирует множественными (векторными) данными. В качестве известного примера можно привести технологию SSE компании Intel.

– MISD (Multiple Instruction stream/Single Data stream) — множественный поток команд и одиночный поток данных. К этому классу относят отказоустойчивые системы.

– MIMD (Multiple Instruction stream/Single Data stream) — множественный поток команд и множественный поток данных. К этому классу относятся мультипроцессорные системы.

На рисунке 1 показано схематическое представление рассмотренной классификации, взятое из работы [1]. Здесь приняты следующие условные обозначения: УУ — устройство управления, ПД — память данных, ПР — процессорные элементы. Данная классификация является самой распространенной. С её помощью можно определить базовые принципы работы компьютерной системы. Однако, она не является единственной. В работе [1] рассмотрено множество других классификаций.

Рис. 1. Классификация компьютерных архитектур М. Флинна

Связность параллельных компьютерных элементов исистем. По характеру интеграции компьютерные системы делятся на два больших класса: сильно связанные (tightly coupled) и слабо связанные (loosely coupled). Эти два класса плавно переходят в друг друга. Предельный случай сильно связанных систем — это внутрипроцессорный параллелизм. Предельный случай слабо связанных — распределенные вычислительные системы (grid computing). Рисунок 2 иллюстрирует связность систем на шкале связности [4]. Здесь под цифрами соответственно обозначены:

1. Внутрипроцессорный параллелизм. К этому классу относятся такие технологии: параллелизм на уровне команд процессора (суперскалярность), процессоры с сверхдлинным командным словом (VLIW, Very Long Instruction Word), внутрипроцессорная многопоточность (on-chip multithreading). Как правило программист не имеет доступ на этот уровень. Система работает автоматически.
2. Сопроцессоры. Представляют собой дополнительные процессоры, предназначенные для обработки специализированных данных: ввода-вывода, чисел с плавающей точкой, графических, сетевых, криптографических и др. Как и всякий процессор сопроцессор является программируемым. Пример реализации — технологии MMX,SSE.
3. Мультипроцессоры. К этому классу относятся системы, в которых процессоры используют общую физическую память. Самыми популярными технологиями параллельного программирования здесь являются: поточное программирование (потоки ОС), OpenMP (Open Multi-Processing), Intel TBB (Threading Building Blocks), Boost.
4. Мультикомпьютеры. Здесь процессоры используют собственную локальную память. Ввиду этого взаимодействие между ними организовано посредством коммуникационной сети. К мультикомпьютерам относятся такие известные системы как IBM BlueGene/L, Red Storm, кластер Google. Программирование систем этого класса осуществляется посредством таких технологий как MPI (Message-Passing Interface), PVM (Parallel Virtual Machine), Linda, Express, OpenCL (Open Computing Language), mpC, Fortran-DVM, C-DVM, MapReduce, Hadoop.
5. Распределенные вычислительные системы. Полноценных технологий программирования этого уровня пока не существует. Поэтому разработчики пользуются уже существующими технологиями уровня мультикомпьютинга, а для коммуникации применяют сетевые технологии. В настоящее время организацией Global Grid Forum создан стандарт OGSA (Open Grid Services Architecture), который определяет предоставляемые системами услуги и протоколы доступа к ним.

Рис. 2. Шкала связности параллельных компьютерных систем

Рассмотрим перечисленные выше технологии программирования в порядке связности систем.

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

Поддержка SSE реализована во многих современных компиляторах. На рисунке 3 показаны примеры использования SSE инструкций во встроенных ассемблерах Microsoft Visual Studio 2010 и Embarcadero Rad Studio XE8.

Рис. 3. SSE в ассемблерах самых популярных IDE

За время своего существования технология SSE эволюционировала до SSE4. Основные усовершенствования технологии: большая разрядность регистров, более широкий набор инструкций, инструкции для обработки специализированных данных [2].

Многопоточное программирование. Примитивы операционных систем. Во всех современных операционных системах реализована возможность распределения вычислительных мощностей процессора. Это достигается за счет многозадачности — свойства операционной системы обеспечивать параллельную (или псевдопараллельную) работу процессов (process). При запуске любой программы, операционная системы создает для неё процесс, который состоит из исполняемой программы (код и данные), виртуального адресного пространства (address space), ресурсов, выделяемых процессу и, как минимум, одного потока управления (thread of execution). В виртуальном адресном пространстве одного процесса может действовать несколько потоков. Если эти потоки являются взаимодействующими, то для организации их работы нужно решать задачу синхронизации [3]. Основные функции для работы с потоками показаны на рисунке 4.

Рис. 4. Основные функции для работы с потоками

Всего в библиотеке WinAPI определено 49 функций для работы с потоками.

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

– Критические секции (critical section)

–Функции ожидания (wait functions)

– События (event)

– Мьютекс (mutex)

Примитивы синхронизации, описанные разными стандартами и реализованные в разных операционных системах, имеют схожий интерфейс.

Многопоточное программирование мультипроцессоров. OpenMP. Стандарт OpenMP реализован в языках программирования C/С++ и Fortran и работает как в Unix, так и в Windows системах. Технология представляет собой набор особых директив компилятора, процедур и переменных окружения. Процесс программирования сводится (в упрощенной форме) к вставке директив в места где код может быть распараллелен [1]. Сказанное иллюстрируется рисунком 5.

Рис. 5. Применение технологии OpenMP

На этом рисунке код в параллельной секции создаст потоки ОС (количеством равным количеству ядер процессора), которые совместно выполнят все итерации этого цикла.

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

Литература:

1. Воеводин В. В., Воеводин Вл.В. Параллельные вычисления. — СПб.: БХВ-Петербург., 2002. — 600 с.
2. Качко Е. Г. Параллельное программирование: Учебное пособие. — Харьков: Форт, 2011. — 528 с.
3. Лупин С. А., Посыпкин М. А. Технологии параллельного программирования. — М.:ФОРУМ, 2011. — 208 с.
4. Таненбаум Э. Архитектура компьютера. — СПб.:Питер, 2009. -844 с.