Основы параллельного программирования вычислительных систем с распределенной и разделяемой памятью

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

Федеральное агентство по образованию

 

Государственное образовательное  учреждение высшего профессионального  образования

«Московский государственный технический  университет имени Н.Э. Баумана»

(МГТУ им. Н.Э. Баумана)

 

Факультет «Информатика и системы  управления»

 

Кафедра «Компьютерные системы  и сети»

 

 

 

 

 

 

 

 

Основы параллельного программирования вычислительных систем с распределенной и разделяемой памятью 

 

 

 

 

 

 

          В.С. Буренков

 Ю.Ю. Митрушенков 

 Ю.М. Руденко

 

 

 

 

 

Москва 2010

Оглавление

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

Введение

 Параллельное программирование  – важная часть высокопроизводительных  вычислений – до недавнего  времени`  

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

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

Многоядерные архитектуры в  форме многоядерных процессоров, систем из нескольких многоядерных процессоров с разделенной памятью или кластеров, состоящих из многоядерных процессоров, соединенных между собой, окажут большое влияние на развитие программного обеспечения. В 2009 году применение двухъядерных и четырехъядерных процессоров в настольных компьютерах – обычное явление; в 2010 году были выпущены восьмиядерные процессоры. Используя закон Мура, можно предсказать, что количество ядер в процессоре будет удваиваться каждые 18-24 месяца. Согласно сообщению фирмы Intel, в 2015 году типичный процессор будет состоять из десятков, вплоть до сотен, ядер, причем каждая часть ядер будет посвящена определенным целям, таким как сетевое управление, шифрование, дешифрование, графика; большинство ядер будет доступно для прикладных программ, обеспечивая огромный производительный потенциал.

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

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

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

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

 

1 Общие представления  о параллельном программировании

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

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

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

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

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

 

 

2 Архитектура параллельных компьютеров

2.1 Развитие архитектуры компьютера

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

1.  Параллелизм на разрядном уровне: к 1986 году размер машинных слов увеличился с 4 до 32 разрядов. Эта тенденция к увеличению замедлилась и прекратилась с появлением 64-разрядных слов в начале 1990-х гг. Увеличение разрядности слов было продиктовано требованиями к увеличению точности выполнения операций с плавающей точкой и большим адресным пространством. Длина слова в 64 бита обеспечивает достаточную точность и адресное пространство в 2⁶⁴ байта.

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

а) выбор команды из памяти для выполнения;

б) дешифрация команды, выбранной  на шаге а;

в) загрузка определенных операндов  и выполнение команды;

г) запись результата в регистр  назначения.

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

Количество ступеней конвейера, используемых на практике, зависит  от конкретной команды и возможностей по ее разделению на ступени. Типичное количество ступеней конвейера лежит  в пределах от 2 до 26. Процессоры, использующие конвейеризацию для выполнения команд, называются ILP-процессорами (Instruction-Level Parallelism, параллелизм на уровне команд).

3.  Параллелизм на уровне функциональных блоков. Многие процессоры используют несколько независимых функциональных узлов, таких как ALU (Arithmetic Logic Unit, арифметико-логическое устройство, АЛУ), FPU (Floating Point Unit, блок арифметики с плавающей точкой) и др. Эти узлы могут работать параллельно, т.е. различные независимые команды могут выполняться одновременно на различных функциональных узлах. Процессоры, работающие по такому принципу, различаются на суперскалярные процессоры и VLIW-процессоры (Very Long Instruction Word, командное слово очень большой длины).

4.  Параллелизм на уровне процессов или потоков.

Классификация параллельных архитектур по Флинну

Таксономия Флинна – это классификация архитектуры компьютеров по соотношению между потоками данных и команд. Различают 4 класса архитектур.

1. SISD (Single-Instruction, Single-Data, один поток команд, один поток данных). Имеется один процессорный элемент, имеющий доступ к единственной программе и единственному устройству хранения данных. На каждом шаге процессорный элемент загружает команду и соответствующие данные и выполняет эту команду. Результат записывается обратно в устройство хранения данных. Таким образом, в соответствии с моделью фон Неймана,  SISD-архитектура – это обычная последовательная архитектура.

2. MISD (Multiple-Instruction, Single-Data, много потоков команд, один поток данных). Имеется несколько процессорных элементов, каждый из которых имеет собственную память программ, но все они обращаются к единственной памяти данных. На каждом шаге все процессорные элементы выбирают одни и те же данные из памяти данных и загружают команду из своей собственной памяти программ. Эти, вероятно, разные команды затем выполняются параллельно. Такая модель может предоставить сильно ограниченные возможности, и промышленно не было выпущено ни одного параллельного компьютера с таким типом архитектуры.

3. SIMD (Single-Instruction, Multiple-Data, один поток команд, много потоков данных). Имеется несколько процессорных элементов, каждый из которых имеет доступ к (разделяемой или распределенной) памяти данных. Но память программ только одна, из которой специальный управляющий процессор извлекает команды. На каждом шаге все процессорные элементы получают от управляющего процессора одну и ту же команду и загружают свой элемент данных, над которым команда будет выполняться. Таким образом, команда параллельно применяется всеми процессорными элементами к разным элементам данных.

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

4. MIMD (Multiple-Instruction, Multiple-Data, много потоков команд, много потоков данных). Имеется несколько процессорных элементов, каждый из которых имеет собственный доступ к (разделяемой или распределенной) памяти программ и памяти данных. На каждом шаге каждый процессорный элемент загружает свою команду и свой элемент данных, выполняет команду над этим элементом данных и записывает результат в устройство хранения данных. Процессорные элементы работают асинхронно по отношению друг к другу. Многоядерные процессоры, кластерные системы – примеры MIMD-модели.

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