С. П. Копысов, А. К. Новиков

ПРОМЕЖУТОЧНОЕ

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Ижевск

2012

Министерство образования и науки Российской Федерации

ФГБОУ ВПО Удмуртский государственный университет

Математический факультет

С. П. Копысов, А. К. Новиков

ПРОМЕЖУТОЧНОЕ

ПРОГРАММНОЕ ОБЕСПЕЧЕНИЕ

ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ

Учебное пособие Ижевск Удмуртский университет 2012 УДК 519.6, 004.4 ББК 32.973 K2 Печатается по решению учебно-методического совета УдГУ Рецензент: д. ф.-м.н., проф. М. В. Якобовский С. П. Копысов, А. К. Новиков К 2 Промежуточное программное обеспечение параллельных вычислений.

Ижевск: Изд-во Удмуртский университет. 2012. 140 с.

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

УДК 519.6, 004. ББК 32. c С. П. Копысов, А. К. Новиков, c Изд-во Удмуртский университет, Содержание Предисловие 1 Промежуточное программное обеспечение высокопроизводительных вычислений 1.1 Классификация.......................... 1.2 Реализуемые модели параллелизма............... 1.2.1 Модель обмен сообщениями............... 1.2.2 Модель общая память................. 1.2.3 Модель параллелизм данных............. 1.3 Предъявляемые требования................... 1.3.1 Инвариантность к языкам программирования.... 1.3.2 Платформонезависимость................ 1.3.3 Адаптация к различным архитектурам аппаратных средств........................... 1.3.4 Использование различных моделей распараллеливания 1.3.5 Объектно-ориентированный подход........... 1.3.6 Компонентный подход.................. 1.3.7 Инкапсуляция и интеграция существующих программных систем......................... 1.3.8 Система управления................... 1.3.9 Особенности программирования для многоядерных вычислительных систем................. 1.4 Пример распараллеливания матрично-векторного произведения............................ 1.4.1 Параллельное вычисление скалярных произведений. 1.4.2 Параллельное вычисление линейных комбинаций.. 1.4.3 Оценка времени параллельного выполнения..... 1.4.4 Произведение разреженной матрицы на вектор... 1.4.5 Объектно-ориентированное программирование в SpMV 1.4.6 Последовательная реализация SpMV на C++.... 2 Технология разработки масштабируемых 2.4 Оптимизация программ в модели 2.4.1 Привязка MPI-процессов к ресурсам вычислительной 4 Массивно-параллельные вычисления 5 Использование гибридных технологий 5.2.1 Возможности повышения производительности 5.2.2 Подходы к построению гибридной модели 5.2.3 Особенности привязки процессов/потоков 5.4.3 Построения интегрированной прикладной Предисловие Настоящее издание является частью учебно-методических разработок, проводимых на кафедре Вычислительная механика. Цель издания привести общие сведения о промежуточном программном обеспечении, на относительно простых примерах ознакомить студентов с парадигмами программирования для параллельных вычислительных систем, подготовить базу для выполнения практических заданий по курсам Промежуточное программное обеспечение, Программное обеспечение многопроцессорных вычислительных систем, Параллельные алгоритмы, Методы декомпозиции.

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

Для этого создается промежуточное программное обеспечение (ППО), которое реализует те или иные технологии распараллеливания. В книге представлен анализ некоторых из них, а также определен ряд требований к ППО.

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

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

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

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

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

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

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

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

Авторы глубоко признательны М.В. Якобовскому за конструктивные и доброжелательные дискуссии. Многие вопросы, затронутые в книге, активно обсуждались с В.Н. Рычковым, Л.Е. Тонковым и Н.С. Недожогиным.

Авторы приносят им свою искреннюю благодарность.

1 Промежуточное программное обеспечение высокопроизводительных вычислений Под параллельной вычислительной системой (ВС) будем понимать множество элементов аппаратного (hardware), промежуточного программного (middleware) и прикладного программного (software) обеспечения с набором связей между ними [1]. Все эти элементы объединены с целью проведения высокопроизводительных параллельных вычислений.

Взаимодействие элементов в ВС строится следующим образом: c элементами аппаратного обеспечения непосредственно взаимодействуют элементы промежуточного ПО, которые, учитывая все особенности архитектуры ЭВМ, предоставляют в совокупности программные средства управления ВС (программную модель ВС). Прикладные программы software через программную модель, обеспеченную middleware, реализуют те или иные алгоритмы для решения прикладной задачи, которая является целью данной ВС. Необходимо отметить, что промежуточное программное обеспечение (ППО) может быть многоуровневым, когда элементы объединяются в некоторые подсистемы, которые находятся в иерархической зависимости, например: операционная система – коммуникационная среда – система распределенных компонентов.

Термин промежуточное программное обеспечение является довольно устоявшимся, но в то же время его нередко используют для обозначения разных понятий. С самой общей точки зрения, ППО является типом программного обеспечения, предоставляющим API (Application Programming Interface интерфейс прикладного программирования) между приложением и ресурсами, необходимыми ему для нормального функционирования, и которое помогает справляться с неоднородностью и распределённостью.

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

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

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

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

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

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

Промежуточное ПО сглаживает различия аппаратно-программных платформ.

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

Промежуточное ПО, отнесенное по данной классификации ко второй группе (обеспечивающее взаимодействие между активными приложениями), может быть условно разбито на три основных типа [3]: ППО удаленного вызова процедур (RPC Remots Procedure Call) (см. также раздел 5.4), ППО передачи сообщений (MOM Message Orientet middleware) (раздел 2) и ППО брокеров объектных запросов (ORB Object Request Broker) (см.

раздел 5.4).

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

Использование RPC накладывает определенные ограничения на тип связи между приложениями. Дело в том, что в RPC применяется синхронный механизм взаимодействия: запрашивающее приложение выдает запрос и ждет ответа. На время ожидания приложение оказывается заблокированным Распространение Java вызвало к жизни аналог RPC для Java-приложений RMI (Remote Method Invocation).

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

Технология ORB выполняет функции интеллектуального посредника, т. е. принимает запросы от клиента (клиентского приложения), осуществляет поиск и активизацию удаленных объектов, которые принципиально могут ответить на запрос, и передает ответ объектам запрашивающего приложения. ППО ORB, RPC и MOM, скрывает от пользователя процесс доступа к удаленным объектам. Запрашивающий объект должен знать имя активизируемого объекта и передать ему некоторые параметры (как правило, это информация об интерфейсе вызываемого объекта – своего рода API для ORB). Интерес к ORB связан с тем, что это ППО поддерживает объектную модель, ставшую де-факто стандартом при разработке больших программных систем. В настоящее время существуют стандарт CORBA http://citforum.ru/database/articles/corba.shtml и технология.NET Remoting корпорации Microsoft.

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

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

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

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

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

1.2 Реализуемые модели параллелизма Параллельное программирование представляет дополнительные сложности необходимо явно управлять работой тысяч процессоров, координировать миллионы межпроцессорных взаимодействий. Для того решить задачу на параллельной ВС, необходимо распределить вычисления между процессорами системы так, чтобы каждый процессор был занят решением части задачи. Кроме того, желательно, чтобы как можно меньший объем данных пересылался между процессорами, поскольку коммуникации намного более медленные операции, чем вычисления. Часто, возникают конфликты между степенью распараллеливания и объемом коммуникаций, то есть, чем между большим числом процессоров распределена задача, тем больший объем данных необходимо пересылать между ними. Среда параллельного программирования должна обеспечивать адекватное управление распределением и коммуникациями данных.

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

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

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

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

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

Упрощенная классификация схем функционирования модели архитектуры была предложена M. Флинном (M.J. Flynn) [4]. Согласно этой классификации различаются схемы:

• SIMD (Single-Instruction/Multiple-Data архитектура с одним потоком команд и многими потоками данных). В архитектурах подобного рода сохраняется один поток команд, включающий векторные команды.

• MIMD (Multiple-Instruction/ Multiple-Data архитектура со множеством потоков команд и множеством потоков данных). Этот класс предполагает, что в ВС есть несколько устройств обработки команд, объединенных в единый комплекс и работающих каждое со своим потоком команд и данных.

• SISD (Single Instruction/Single Data) одиночный поток команд и одиночный поток данных. К этому классу относятся, прежде всего, классические последовательные машины.

• MISD (Multiple Instruction/Single Data) множественный поток команд и одиночный поток данных. Определение подразумевает наличие в архитектуре многих процессоров, обрабатывающих один и тот же поток данных.

Позже эти схемы были расширены до SPMD (Single-Program/ MultipleData одна программа, несколько потоков данных) и MPMD (MultiplePrograms/Multiple-Data множество программ, множество потоков данных) соответственно. Схема SPMD (из класса SIMD) позволяет нескольким процессорам выполнять одну и ту же инструкцию или программу при условии, что каждый процессор получает доступ к различным данным. SPMD имеет более высокий уровень абстракции и является уже моделью параллельных вычислений, которая предполагает наличие нескольких взаимодействующих процессов выполнения программы. Также можно говорить, что SPMD является и моделью параллельного программирования.

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

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

Параллельная модель программирования определяет представление программиста о параллельной ВС, определяя, тем самым возможности каким образом разработчик может запрограммировать алгоритм. При этом существуют много различных параллельных моделей программирования для одной и той же архитектуры. Например, для одной из наиболее распространенных MIMD-архитектур может быть реализована модель вычислений как SPMD, так и MPMD c помощью моделей программирования передачи сообщений (MPI), а в рамках одного вычислительного узла и с помощью OpenMP.

Существует несколько критериев, по которым можно разделить модели параллельного программирования:

• уровень параллелизма, который используется при параллельном выполнении (уровень инструкций, уровень команд, уровень функций, уровень объектов, уровень компонентов или параллельных циклов);

• неявная или явная, определённая пользователем спецификация параллелизма;

• каким образом определены параллельные части программы;

• способ выполнения параллельных подзадач (SPMD, синхронный или асинхронный);

• способы коммуникации между вычислительными подзадачами для обмена информацией (явная коммуникация или разделяемые переменные);

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

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

• последовательностью инструкций, выполняющих арифметические или логические операции;

• последовательность операторов, где каждый оператор может включать несколько инструкций;

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

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

На этом этапе необходимо определить наиболее подходящую модель программной реализации параллельных вычислений (задачи и каналы, пересылка сообщений с использованием стандартных библиотечных утилит, разделяемая память с использованием блокировок и семафоров и др.). В модели разделяемой памяти с использованием блокировок и семафоров задачи используют общее адресное пространство, в котором они читают и записывают данные асинхронно. Механизм блокировок и семафоров используется для контроля доступа к общей памяти. Другие примеры моделей параллельного программирования включают в себя: алгоритмические скелетоны; компоненты; распределённые объекты; потоковая обработка;

удаленный вызов процедур; рабочие процессы (workows) и др.

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

Рассмотрим только основные модели параллельного программирования [4]:

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

• Параллелизм задач (Task Parallel). Модель программирования, которая подразумевает, что вычислительная задача разбивается на несколько относительно самостоятельных подзадач и каждый процессор загружается своей собственной подзадачей. Тем самым увеличивается общая эффективность программы, основанной на параллелизме • Параллелизм данных (Data Parallel). В этой модели единственная программа задает распределение данных между всеми процессорами компьютера и операции над ними. Распределяемыми данными обычно являются массивы. Как правило, языки программирования, поддерживающие данную модель, допускают операции над массивами, позволяют использовать в выражениях целые массивы, вырезки из массивов. Распараллеливание операций над массивами, циклов обработки массивов позволяет увеличить производительность программы. Компилятор отвечает за генерацию кода, осуществляющего распределение элементов массивов и вычислений между процессорами.

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

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

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

1.2.1 Модель обмен сообщениями На сегодняшний день модель обмен сообщениями (message passing) является наиболее широко используемой моделью параллельного программирования. Программы этой модели создают множество процессов, с каждым из которых ассоциированы локальные данные. Каждый процесс идентифицируется уникальным именем. Процессы взаимодействуют, посылая и получая сообщения. В этом отношение модель обмен сообщениями является разновидностью модели процесс/канал и отличается только механизмом, используемым при передаче данных.

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

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

Фактически стандартизованный механизм для построения параллельных программ в модели обмена сообщениями реализован в MPI (раздел 2).

1.2.2 Модель общая память В модели программирования с общей памяти все процессы совместно используют общее адресное пространство, к которому они асинхронно обращаются с запросами на чтение и запись. В таких моделях для управления доступом к общей памяти используются всевозможные механизмы синхронизации типа семафоров и блокировок процессов. Преимущество этой модели, с точки зрения программирования, состоит в том, что понятие собственности данных (монопольного владения данными) отсутствует, следовательно, не нужно явно задавать обмен данными между производителями и потребителями. Эта модель, с одной стороны, упрощает разработку программы, но, с другой стороны, затрудняет понимание и управление локальностью данных, написание детерминированных программ. В основном, эта модель используется при программировании для архитектур с общедоступной памятью. Модель общая память поддерживает SPMD и MPMD модели программирования. Cтандарт для программирования в модели общей памяти система OpenMP (см. раздел 3 ).

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

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

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

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

По определению, данная модель параллелизма предполагает SPMD модель программирования. Параллеизм данных основная модель определяющая дизайн CUDA (см. раздел 4), OpenCL (см. раздел 5.1).

Для распараллеливания может быть использовано несколько программных моделей (см. разделы 5.2,5.3,5.4.2), каждая из которых соответствует определенному подмножеству требований. Заранее может быть трудно определить, какая именно модель лучше подходит. Еще больше сложностей возникает в связи с потребностью комбинировать различные модели.

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

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

1. Реализация интерфейса системы на различных языках программирования. Такой подход применяется, например, в технологии MPI.

Интерфейс MPI реализовывается только на языках C, Fortran. Недостаток такого подхода: несовершенный интерфейс. В связи с развитием языков программирования, в частности, с появлением объектноориентированных языков, возникла необходимость записать интерфейс MPI совершенно иным способом. Поэтому сначала появляются интерфейсы MPI++, OOMPI, в которых сама промежуточная среда представляется в виде объектов, затем создаются описания параллельных объектов TPO++ (см. раздел 2, интерфейсы для работы с компонентами [5].

2. Введение специальных высокоуровневых описаний. Так, в технологии CORBA [6] центральное место занимает язык описания интерфейсов IDL, который эволюционирует вместе с самой системой. Для того чтобы расширить языковую поддержку CORBA, необходимо реализовать транслятор, переводящий IDL-описания в текст на целевом языке. IDL-описания используются не только для получения исходного кода программы, Разные типы ППО обслуживают приложения с разными требованиями к межмодульным коммуникациям. Объектная ориентированность прикладных разработок и построение приложений из готовых компонентов стимулирует развитие объектных решений промежуточного слоя. Кроме этого, выделение языка как части системы позволяет CORBA не отставать от развития языков программирования.

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

1. Переносимость на уровне исходного кода: в данном случае все прикладные программы переносимы, но для этого требуется их перекомпиляция на новой платформе. Взаимодействовать друг с другом компоненты разных платформ не могут. Перенос обеспечивается единым интерфейсом на общем языке программирования. Процесс усложняется или вообще невозможен, если используются библиотеки, связанные с той или иной платформой. MPI (Message Passing Interface) http://www.mpi-forum.org/ пример системы ППО, платформонезависимой на уровне исходного кода.

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

3. Переносимость на уровне бинарного кода: переносимы откомпилированные прикладные программы. Промежуточная система, реализующая такой подход, включает в себя некую виртуальную машину для выполнения программ. Такого рода перенос возможен между различными версиями OC Windows посредством языконезависимой технологии COM и между ОС, оснащенными Java-системой. В данном случае узким местом является виртуальная машина: необходимо, чтобы она была реализована для широкого класса OС, была достаточно производительной и использовала наработанное ПО для данной ОС.

Наиболее приемлемыми являются системы, платформонезависимые во втором смысле, такие как CORBA, OpenCL. Их преимущество эффективное взаимодействие с платформой, т.к. доступ к ней осуществляется без посредников. Платформа понимается широко: операционная система, созданное на ее основе программное обеспечение, аппаратные средства. В данном случае может оказаться полезной некоторая зависимость от платформы. С другой стороны, очевидной становится проблема управления программными компонентами в гетерогенной аппаратно-программной среде. Чтобы решить эту проблему, можно расширить функциональность CORBA Application Server путем внедрения компиляторов, интерпретаторов и библиотек к ним, что позволит управлять исходным кодом компонентов.

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

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

ППО OpenCL (см. раздел 5.1) для написания программ, связанных с параллельными вычислениями на различных графических (GPU) и центральных процессорах (CPU). В OpenCL входят язык программирования, который базируется на стандарте C99, и интерфейс программирования приложений (API).

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

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

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

Эволюция параллельных и распределенных систем, несмотря на то, что они использовались для решения определенных классов задач, показывает, что сегодня высокопроизводительная технология должна описывать и SIMD, и MISD, и MIMD модели. Сегодня наметилась тенденция на расширение описательных возможностей существующих стандартов (для MPI разрабатываются технологии распределенных объектов, для CORBA дополнительные модули параллельной обработки). Такие системы должны строиться на основе компонентного подхода с широким использованием различных методов взаимодействия между процессами (обмены) и доступа к объектам (клиент-сервер).

1.3.5 Объектно-ориентированный подход Объектно-ориентированный стиль моделирования и программирования систем в настоящее время является наиболее удобным и эффективным для реализации программных систем [7]. Объектно-ориентированный подход (ООП) основан на систематическом использовании моделей для языково-независимой разработки программной системы.

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

1. уменьшение сложности программного обеспечения;

2. повышение надежности программного обеспечения;

3. модификация отдельных компонентов программного обеспечения без изменения остальных его компонентов;

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

В соответствии с объектно-ориентированной технологии разработка приложений происходит в три фазы: анализ, проектирование и реализация.

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

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

Аспекты, включаемые в функциональную модель, связаны с передачей сообщений и параллельным выполнением (см. разделы 2.6, 3.4, 4.2, 5.1).

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

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

1.3.6 Компонентный подход На основе ООП развивается компонентный подход, в котором этапы проектирования и программирования четко разграничены. Компонентом называют объект, в котором разделены интерфейс и реализация. Это позволяет реализовать ее одновременно на разных платформах. Прикладное обеспечение, созданное на основе такой системы, может функционировать на многих платформах. Как компонентная технология с самого начала проектировалась CORBA. Показательно, что для системы MPI в ходе эволюции были определены объектная структура, интерфейс работы с объектами, компонентная модель. Компонентный подход дает много преимуществ по разработке программ, которые могут быть автоматизированы, поэтому важно создать соответствующие средства разработки. В настоящее время наметилась тенденция к созданию интегрированных сред разработки, направленных не только на создание программ на каком-либо языке программирования, но и поддерживающих различные технологии программирования. Можно выделить ряд необходимых свойств среды разработки:

1. наличие инструментов объектного моделирования (например, Rational 2. поддержка компонентной технологии (например: CORBA [6], ICE [8]);

3. тесная интеграция всех инструментов для повышения эффективности программирования семантики компонентов;

4. возможность групповой работы над проектами, для чего создаются CVS-системы (Control Version System система контроля версий);

5. ведение библиотек компонентов для их повторного использования (например репозитории CORBA);

6. наличие хранилища шаблонов и мастеров для автоматизации создания компонентов, 7. открытость, т.е. возможность включения в среду разработки новых компонентов (компиляторов, скриптов, редакторов и др.).

Среду разработки, удовлетворяющую данным требованиям имеет смысл создавать на основе существующих инструментов, таких как некоторые компоненты CORBA (IDL-компилятор, репозитории объектов, сервис поддержки жизненного цикла и др.), языков управления сценариями Python, Perl, Tcl.

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

1. Инкапсуляция это включение в состав многокомпонентной системы набора компонентов некоторой ВС. Это позволяет повторно использовать программные компоненты. В тех случаях, когда ВС, которую необходимо инкапсулировать, основана на другой технологии, создаются специальные механизмы, например, программы каркасы между компонентными системами COM-CORBA, Java-COM, CORBA-RMI.

Инкапсуляцию существующих ВС может осуществить прикладной программист.

2. Интеграцией называется инкапсуляция с одновременным изменением архитектуры исходной системы. Интеграцией MPI в CORBA можно назвать проект Cobra [5], когда модифицируются важные составляющие CORBA. Это относится к области системного программирования. Перед тем как браться за интеграцию, необходимо оценить преимущества и недостатки видоизменения базовой ВС.

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

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

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

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

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

1. Определяется интерфейс компонента, включающий наиболее основные и общие свойства.

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

3. Сервис реализуется и включается в компонентную систему. Создается средство интерактивного взаимодействия с сервисом.

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

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

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

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

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

2. Блокировки возникают из-за невозможности одновременного доступа приложений на разных ядрах к таким ресурсам, как жёсткий диск, некоторые устройства ввода/вывода, прикладным данным в определённых ситуациях (например, в момент сборки мусора ).

3. Очень часто параллельные процессы, выполняемые на разных ядрах, должны синхронизироваться в определённые моменты времени.

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

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

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

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

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

Сложность состоит в распределении потоков и процессов между ядрами таким образом, чтобы оптимально задействовать возможности системной топологии и архитектуры. В большинстве случаев планировщики в операционных системах (ОС) общего назначения назначают потоки ядрам с наименьшей загрузкой, чтобы обеспечить сбалансированную нагрузку, либо ядрам с уже подготовленными данными в кэше (cache-warm), используя преимущества привязки к кэшу (cache anity).

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

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

Операционная система рассматривает ядра процессоров, как процессоры (processor на рисунках 1 и 2). По аналогии с логическими жесткими дисками назовем ядра процессоров логическими CPU. Данное понятие отличается от понятия виртуальные процессоры, число которых полагается равным числу аппаратно поддерживаемых потоков (как правило, два потока на каждое ядро процессора). Например, в процессорах Intel Core i3 и Core i7 используется технология гиперпоточности (Hyper-Threading Technology), в этом случае каждое физическое ядро процессора определяется операционной системой как два логических (виртуальных).

Нумерация ядер в ОС изменяется для разных систем и ее нельзя наследовать для достижения оптимальных результатов на всех вычислительных системах. Например, для двух систем, на которых проводилось тестироваРис. 1. Вычислительный узел Рис. 2. Вычислительный узел клаМВС-100К стера X ние МВС-100К МСЦ РАН (каждый ВУ два четырехядерных процессора Xeon 5365, 3GHz) и кластер X4 ИМ УрО РАН (каждый ВУ два четырехядерных процессора Xeon 5420, 2.66GHz) приведены данные на рисунках 1 и 2. Строка processor содержит номера логических CPU, core id идентификаторы ядра в физических (реальных) процессоров ( physical id ).

Соответствие логических CPU ядрам вычислительных узлов для них показано на рисунках 3, 4. Представленные вычислительные узлы идентичны по числу и архитектуре процессоров, но на уровне операционной системы имеют разные номера ядер. В данном случае, процессы/потоки, выполняемые нулевым и первым логическими CPU на узле кластера X4 будут Рис. 3. Соответствие логических Рис. 4. Соответствие логических CPU ядрам вычислительных узлов CPU ядрам вычислительных узлов выполнятся одним физическим процессором, конкурируя за один канал оперативной памяти, а на МВС-100К двумя процессорами без конкуренции. Пары процессов/потоков, выполняемые на логических CPU с номерами 0 и 4, 1 и 5, 2 и 6, 3 и 7 на обеих вычислительных системах будут конкурировать за кэш-память второго уровня.

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

Рисунки 1 – 4 построены на основе информации из файла cpuinfo, размещаемого в каталоге proc корневого каталога Linux. Графические изображения аппаратной архитектуры вычислительного узла также могут быть построены при помощи утилиты lstopo.

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

Высокоуровневые системные вызовы привязки Как было отмечено ранее, операционная система определяет нумерацию ядер для вычислительных узлов (ВУ) с многоядерными процессорами. В операционной системе Linux пользователь может привязать процесс к логическому CPU, используя вызов функций sched_setaffinity(), sched_getaffinity() с соответствующим параметром affinity_mask из текущего процесса (своей программы). Эти функции могут отличаться типом параметров в зависимости от производителей Linux и версий библиотеки Glibc. Реализованы функции в библиотеке PLPA (The Portable Linux Processor Anity http://www.open-mpi.org/projects/plpa).

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

Готовая к выполнению задача (приложение) также может быть привязан к логическим СPU в Linux, при помощи команды taskset.

Отметим также, что для привязки процессов в других операционных системах также имеются системные вызовы: в операционной системе Windows SetThreadAffinityMask(); в Solaris pbind().

Другие способы привязки параллельных процессов и потоков рассматриваются более подробно в разделах 2.4.1, 3.5.

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

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

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

1.4 Пример распараллеливания матрично-векторного произведения Матрицы и матричные операции широко используются при математическом моделировании разнообразных процессов, явлений и систем. Матричные вычисления составляют основу многих научных и инженерных расчётов среди областей приложений могут быть указаны вычислительная математика и механика и др. Одним из примеров применения матричных вычислений является решение систем линейных алгебраических уравнений (СЛАУ), которые, в свою очередь, занимают одну из основных ролей при использовании численных методов и математического моделирования [10].

Другие интересные задачи и примеры распараллеливания можно найти в [11].

Построение эффективных алгоритмов умножения разряженной матрицы на вектор (Sparse Matrix-Vector Multiplication SpMV) затруднено тем, что для представления разряженных матриц используется сложная структура данных, и шаблон доступа к памяти не предсказуем. Способ вычисления произведения на любой архитектуре ВС зависит от формата представления разреженной матрицы, который, в свою очередь, связан со спецификой рассматриваемой задачи.

Вычислим произведение матрицы A RN M и вектора b RM. (Здесь и далее жирным шрифтом будем выделять матрицы и вектора, в остальных случаях скалярные величины.) Последовательный алгоритм матрично-векторного произведения имеет где c = (c1, c2,..., cN ) RN, A = ((aij )i=1,...,N,j=1,...,M ), b = (b1, b2,..., bM ) и может быть реализован двумя различными способами в зависимости от переменной цикла.

В первом случае, умножение вычисляется как N скалярных произведений строк (a1, a2,..., aN ) матрицы A и вектора b:

Соответствующий алгоритм на языке С можно представить как Матрица A RN M представляется как двумерный массив, а соответствующие вектора как одномерные массивы. Для каждого внутреннего цикла i = 0, 1,..., N 1 имеется вложенный цикл содержащий одно скалярное произведение.

Во втором случае, произведение матрицы на вектор может быть записано как линейная комбинация столбцов a1, a2,..., aM матрицы A с коэффициентами b1, b2,..., bM Соответствующий программный код имеет вид:

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

• при строчно-ориентированном представлении матрицы A, вычисляются N скалярных произведений (ai, b), i = 1, 2,..., N строк матрицы A с вектором b параллельно. Каждый процессор из числа доступных процессоров ВС np обрабатывает N/np скалярных произведений;

• при столбцово-ориентированном представлении матрицы A, вычисления линейных комбинаций M bj aj происходят на каждом проj= цессоре над частью линейных комбинаций M/np векторов.

Рассмотри эти алгоритмы более подробно.

1.4.1 Параллельное вычисление скалярных произведений Для реализации параллельного произведения на ВС с распределённой памятью необходимо распределить матрицу A и вектор b, так чтобы вычисления скалярных произведений (ai, b), i = 1, 2,..., N выполнялись над данными в памяти данного процессора, т.е. соответствующие строки ai и вектора b хранились в памяти процессора вычисляющего процессора. Т.к.

вектор b необходим для всех скалярных произведений, поэтому b просто дублируется.

При строчно-ориентированном распределении матрицы A, процессор Pk, k = 1, 2,..., np, хранит строки матрицы ai, i = N/np · (k 1), N/np · (k 1) + 1,..., N/np · k, в локальной памяти и вычисляет скалярные произведения (ai, b). Для вычисления (ai, b) нет необходимости в пересылке и приёме данных с других процессоров. Результат произведения вектор c = (c1, c2,..., cN ) будет распределён по блокам.

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

1.4.2 Параллельное вычисление линейных комбинаций Для параллельных вычислений матрично-векторного умножения на ВС с распределённой памятью в форме линейных комбинаций, используется распределение матрицы A по столбцам. Каждый процессор вычисляет часть линейных комбинаций для соответствующих столбцов ai (i 1, 2,..., M ). Каждому процессору Pk распределяется часть столбцов ai (i = M/np · (k 1) + 1, M/np · (k 1) + 2,..., k · M/np ) и вычисляется вектор размерности N как:

где k = 1, 2,..., np. Отметим, что на каждом процессоре хранится только часть вектора b. По окончанию параллельных вычислений вектора dk, хранимые в локальной памяти каждого процессора, должны быть просумnp мированы в результирующий вектор c = k=1 dk.

1.4.3 Оценка времени параллельного выполнения Время необходимое для параллельного выполнения программы зависит:

• от размера входных данных и параметров алгоритма. Например, границы циклов или число итераций;

• числа используемых процессоров np ;

• коммуникационных характеристик и, прежде всего, вида коммуникаций в ВС и ППО обеспечивающего коммуникации.

Рассмотрим простейшую параметрическую оценку модели производительности алгоритма матрично-векторного произведения, применительно к квадратной, заполненной матрице A. Выражение для времени работы и параллельного ускорения через параметры задачи (N ) и характеристики архитектуры (np число процессоров, время выполнения характерной арифметической операции, время инициализации пересылки, характерное время пересылки одного слова данных). В данном случае оценка характерна для модели вычислений SPMD и модели программирования MPI.

Определим время выполнения параллельных вычислений t(np, N ), как функцию, зависящую от размерности задачи N и числа используемых процессоров np. Будем полагать, что размерность задачи N пропорциональна числу процессоров r = N/np, и, что время выполнения характерной арифметической операции определяется через.

В случае использования строчно-ориентированных блоков, каждый процессор хранит r строк ai матрицы A таких, что r · (k 1) + 1 i r · k и вычисляет Для каждого блока размера r необходимо вычислить N перемножений и N 1 операций сложения, что приближенно можно оценить как вычислительные затраты, равные 2N r. Напомним, что вектор b дублируется на каждом процессоре. В случае если результирующий вектор c также должен быть на каждом процессоре, необходимо выполнить операцию сбора для каждого процессора Pk, k = 1, 2,..., np приняв r = N/np элементов.

При использовании столбцово-ориентированной схемы каждый процессор Pk хранит r столбцов aj матрицы A таких, что r · (k 1) + 1 j r · k, а также соответствующие элементы вектора b. Процессор Pk также вычисляет часть суммы Для вычисления dkj необходимо r перемножений и r 1 сложений. Таким образом, для вычисления всех N величин требуются вычислительные затраты равные 2N r. Для получения окончательного результата произведения каждый процессор суммирует величины d1j, d2j,..., dnj, здесь делим функцию затрат на коммуникации. Будем полагать, что пересылка r чисел с плавающей точкой на соседний процессор по коммуникационной сети требует затрат + r ·, где время инициализации пересылки;

сылки одного слова данных.

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

В случае, если процессоры соединены как линейный массив, то операция суммирования выполняется за np шагов на каждом из которых посылается сообщение размерности r = N/np и затраты на коммуникацию составят np ( + r · ). Для операций передачи данных от одного ВУ к остальным и операций передачи данных от всех ВУ ко всем узлам можно использовать и более сложные модели, отражающие специфику маршрутизации в используемой модели вычислений и программирования. Для рассматриваемого случая оценку времени выполнения можно записать как Отметим, что согласно этому выражению время вычислений сокращается с ростом числа процессоров np, а время коммуникаций увеличивается линейно с увеличением np. Таким образом, при заданном размере задачи N увеличение ускорения параллельного матрично-векторного произведения возможно при ограничении числа процессоров np n. Определим оптимальное число процессоров np для заданного N из условия минимума функции времени Значение np, соответствующее минимуму t(N, np ) это оптимальное число процессоров n = N · 2/, которое линейно зависит от размерности задачи N. Полученная оценка потребует уточнения в случае разреженной матрицы, хранящейся в сжатом формате.

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

Матрица, число ненулевых элементов которой гораздо меньше числа нулевых элементов, называется разряженной. При работе с такими матрицами имеет смысл хранить только ненулевые элементы, или ненулевые элементы и малое число нулей [12].

Пусть матрица A произвольная разреженная матрица, размерности N N, и которая содержит N nz ненулевых элементов.

Рассмотрим форматы представления разреженных матриц [12], т.е. матриц имеющих большое число нулевых элементов на примере матрицы A, имеющей следующий вид Отметим, что матрица A квадратная, размерности 44 и имеет N nz = ненулевых элементов.

Формат CSR CSR (Compressed Sparse Row Storage Format) построчный формат хранения разряженных матриц. При использовании этого формата создаются три массива:

массив значений ненулевых элементов матрица A. Значения элементов записываются упорядоченно, по строкам.

i-ый элемент этого массива номер столбца, в котором наAN C ходится i-ый элемент массива AV в матрицы A.

• AN L i-ый элемент этого массива номер элемента из массива AV, с которого начинается i-ая строка в матрице A. Последний элемент всегда число ненулевых элементов.

Массивы AV и AN C имеют размерность N nz, а массив AN L размерность (N + 1).

На примере матрицы A представление её в формате CSR имеет вид:

Последовательный алгоритм умножения матрицы A в формате CSR на вектор b размерности N может быть записан как Алгоритм 1 Последовательный алгоритм матрично-векторного произведения в формате CSR res[i] := res[i] + AV [j] · b[AN C[j]];

5: end for Результат Алгоритма 1 помещается в вектор res размерности N.

Рассмотрим параллельный вариант SpMV также в формате CSR. Пусть на процессоре Pk хранятся k-ые части массивов AV, AN C, AN L и заданного вектора. Массив AN L разбивается на части, размером N/np, а AV и AN C на части, размером (AN L[(k + 1) · np ] AN L[k · np ]), где k номер процессора Pk. Тогда параллельный алгоритм умножения матрицы A в формате CSR, на вектор b будет выглядеть следующим образом:

Алгоритм 2 Параллельный алгоритм матрично-векторного произведения в формате CSR resk [i] := resk [i] + AVk [j] · b[AN Ck [j]], где k = 0, 1,..., (np 1);

i = k·N, k·N +1,..., (k+1)·N 1; j = AN Lk [i], AN Lk [i]+1,..., AN Lk [i+1];

На первом шаге Алгоритма 2 обнуляем i-ые компоненты вектора res на каждом процессоре, на втором умножаем части матрицы и вектора, а на третьем пересылаем вектора результатов на нулевой процессор, и на последнем шаге складываем локальные векторы в вектор res.

Формат COO COO (Coordinate Storage Format) координатный формат хранения.

При использовании этого формата создаются три массива:

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

i-ый элемент этого массива является номером столбца, в коAN C тором находится i-ый элемент массива AV в матрицы A.

i-ый элемент этого массива является номером строки, в коAN R торой находится i-ый элемент массива AV в матрицы A.

Все массивы имеют размерность N nz. Вернёмся к примеру матрицы A:

Последовательный и параллельный алгоритмы умножения матрицы A в формате COO, на вектор b размерности N представлены в Алгоритме Алгоритм 3 Последовательный алгоритм матрично-векторного произведения в формате COO res[AN R[i]] := res[AN R[i]] + AV [i] · b[AN C[i]];

3: end for и Алгоритме 4 соответственно. Результаты записываются в вектор res размерности N.

Пусть на k-ом процессоре хранятся части массивов AV, AN C, AN R, размерности N nz/np и вектор правых частей. Тогда параллельный алгоритм умножения матрицы A в формате COO, на вектор b будет выглядеть следующим образом:

Алгоритм 4 Параллельный алгоритм матрично-векторного произведения в формате COO 2: resk [AN Rk [i]] := resk [AN Rk [i]] + AVk [i] · b[AN Ck [i]], 3: Pk (resk ) P0 (resk ), k = 1, 2,..., (np 1) 4: res[i] := res[i] + resk [i] на P0, i = 0, 1,..., (N 1); k = 0, 1,..., (np 1).

При доступе к компонентам вектора res, на втором шаге Алгоритма применяется косвенная индексация, в которой индекс i локальный.

Формат ELL ELL (ELLPack Storage Format) строчный формат хранения. Исходная матрица преобразуется следующим образом: все ненулевые элементы записываются в строках по очереди слева направо. Находим строку, в которой расположено наибольшее число ненулевых элементов LN nz. Остальные строки дополняются нулями до размера этой строки.

Представление разряженной матрицы включает два массива AV e и AN Ce размерности N · LN nz:

массив значений элементов (включая нули);

• AN Ce массив номеров столбцов элементов. Если на i-ом месте массива AV e находится 0, то AN Ce[i] = 1.

На примере матрицы A:

соответственно вектора имеют вид Последовательный алгоритм умножения матрицы A, хранящейся в формате ELL на вектор b размерности N. Результат Алгоритма 5 записывается в вектор res размерности N :

Алгоритм 5 Последовательный алгоритм матрично-векторного произведения в формате ELL res[i/LN nz] := res[i/LN nz] + AV e[i] · b[AN Ce[i]];

5: end for Пусть на k-ом процессоре хранятся части массивов AV e, AN Ce, размерности (N · LN nz)/np и вектор. Тогда параллельный алгоритм умножения матрицы A в формате ELL на вектор b выглядит следующим образом:

Алгоритм 6 Параллельный алгоритм матрично-векторного произведения в формате ELL 2: resk [i/LN nz + k · LN nz] := resk [i/LN nz + k · LN nz]+ 3: Pk (resk ) P0 (resk ), k = 1, 2,..., (np 1);

4: res[i] := res[i] + resk [i] на P0, i = 0, 1,..., (N 1); k = 0, 1,..., (np 1).

Отметим, что на втором шаге Алгоритма 6 используется локальная нумерация при доступе к компонентам вектора res.

Формат BCSR BCSR (Block-Based Compressed Row Storage Format) [12] блочный формат хранения по строкам. Матрица A разбивается на блоки заранее известного размера. Рассмотрим разбиение матрицы на блоки размера 2 2.

При этом создаются три массива AV B, AN CB, AN LB, элементы которых:

• AV B содержат значения элементов матрицы A. Значения записываются упорядоченно, по блокам. При этом встречаются не только ненулевые элементы.

являются номерами столбцов левого верхнего элемента являются номерами элементов из массива AN CB, с котоAN LB рых начинаются новые строки блоков.

Массив AV B имеет размерность N nzb N nz, массив AN CB размерность N b равную количеству блоков, массив AN LB размерность, равную N/2+1.

Тогда матрица A будет иметь следующий вид:

и её представление как:

Последовательный алгоритм умножения матрицы A в формате BCSR, на вектор b размерности N имеет вид:

Алгоритм 7 Последовательный алгоритм матрично-векторного произведения в формате BCSR Результат Алгоритма 7 записывается в вектор res размерности N.

Пусть на k-ом процессоре Pk хранятся части массивов AV B, AN CB, AN LB Алгоритм 8 Параллельный алгоритм матрично-векторного произведения в формате BCSR resk [2 · i] := resk [2 · i] + AV Bk [j] · b[AN CBk [j]] + и вектор правых частей. Массив AN LB разбивается на части, размером 2·np, массив AN CB на части размером (AN LB[(k + 1) · np ] AN LB[k · np ]), а массив AV B на части в четыре раза большие, чем AN CB.

Тогда параллельный алгоритм умножения матрицы A в формате BCSR на вектор b будет иметь вид Алгоритма 8. В отличие от предыдущих параллельных алгоритмов, на втором шаге вычисляются две компоненты вектора resk, поэтому диапазон индекса i изменяется в два раза.

Введенное ранее, оптимальное число процессоров n для сжатых форp матов хранения зависит от числа ненулевых элементов матрицы, и например для CSR формата составит n = (2 · N nz · )/.

1.4.5 Объектно-ориентированное программирование в SpMV Большинство далее рассматриваемых программных кодов будут использовать язык С++. Это связано прежде всего с тем, что на С++ имеется возможность использования различных парадигм программирования, а с другой стороны можно не использовать определённые языковые средства в соответствии с предпочтениями разработчика. Например, не использовать макросы, шаблоны и т.д. Хорошим введением в тему данного раздела может послужить работа С.С. Гайсаряна [7].

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

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

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

Язык С++ поддерживает несколько парадигм в подходе к разработке библиотек программ, которые делают средства параллельного программирования легко доступными. Помимо библиотек системного уровня, для поддержки параллелизма в С++ могут применяться промежуточное программное обеспечение, как MPI, OpenMP и CORBA, которое будет подробно рассмотрено в следующих разделах.

1.4.6 Последовательная реализация SpMV на C++ Программная реализация SpMV в рамках объектно-ориентированного подхода С++ может строиться на основе как пользовательских классов (или шаблонов классов) для матрицы A и векторов b и c, так и с использованием контейнеров из библиотеки стандартных шаблонов (Standard Templates Library (STL)) http://www.sgi.com/tech/stl/. Контейнеры это объекты, хранящие в себе другие объекты. Для хранения матрицы в CSR формате могут использоваться последовательные контейнеры vector или ассоциативный контейнер map. Произведение матрицы на вектор может быть реализовано несколькими способами: переопределением оператора *, в виде функции члена класса матрица, реализуемой в виде отдельной функции.

При выборе реализации необходимо учитывать, что наследование приводит к дополнительным зависимостям по данным, которые ограничивают возможности распараллеливания программного кода. Ограничимся рассмотрением варианта, в котором для хранения матриц в формате CSR используется класс SpM (см. Листинг 1), а произведение матрицы на вектор реализуется в виде метода (функции члена класса) SpMV данного класса.

Для хранения матрицы в классе SpM применяются контейнеры vector.

i nt Nnz ; // Число ненулевых элементов матрицы v e c t o r AV; // Значения элементов матрицы v e c t o r ANC; //Столбцовые индексы элементов матрицы / Произведение матрицы на вектор / При объявлении объекта класса SpM в пользовательской программе конструктор SpM::SpM (Листинг 2) создаст структуру данных для хранения матрицы размерности f N f N с f N N Z ненулевыми элементами. Определение метода SpMV показано в Листинге 3.

Границы внешнего цикла ib и ie позволят в дальнейшем (см. раздел 3.6 ) применить метод SpM::SpMV к строчному блоку матрицы A, при создании параллельных версий программы. Введенные дополнительно переменные jb, je и sum уменьшают частоту обращений к контейнерам ANL и c.

Листинг 3. Произведение матрицы, хранящейся в CSR формате на вектор