Параллельные и последовательные вычисления. Параллельные вычислительные системы

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

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

Способы синхронизации параллельного взаимодействия

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

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

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

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

Типичные задачи, допускающие параллельные вычисления

• map - выполнение одной и той же функции над каждым элементом массива входных данных, с получением равного по мощности массива результатов вычисления
• reduce - выполнение одной и той же функции для добавления вклада каждого элемента входных данных в одно итоговое значение

Программные инструменты параллелизма

• OpenMP - стандарт интерфейса приложений для параллельных систем с общей памятью.
• POSIX Threads - стандарт реализации потоков (нитей) выполнения.
• Windows API - многопоточные приложения для C++.
• PVM (Parallel Virtual Machine) позволяет объединить разнородный (но связанный сетью) набор компьютеров в общий вычислительный ресурс.
• MPI (Message Passing Interface) - стандарт систем передачи сообщений между параллельно исполняемыми процессами.

См. также

Напишите отзыв о статье "Параллельные вычисления"

Литература

• Словарь по кибернетике / Под редакцией академика В. С. Михалевича . - 2-е. - Киев: Главная редакция Украинской Советской Энциклопедии имени М. П. Бажана, 1989. - 751 с. - (С48). - 50 000 экз. - ISBN 5-88500-008-5 .
• . - IBM RedBook, 1999. - 238 с. (англ.)
• Воеводин В. В., Воеводин Вл. В. Параллельные вычисления. - СПб: БХВ-Петербург, 2002. - 608 с. - ISBN 5-94157-160-7 .
• Оленев Н. Н. . - М .: ВЦ РАН, 2005. - 80 с. - ISBN 5201098320 .

Примечания

Ссылки

• (англ.)
• (англ.)

Параллельные вычисления Общие положения Уровни параллелизма Поток выполнения Теория Элементы Взаимодействие Программирование Компьютерная техника API Проблемы

Отрывок, характеризующий Параллельные вычисления

Дух войска – есть множитель на массу, дающий произведение силы. Определить и выразить значение духа войска, этого неизвестного множителя, есть задача науки.
Задача эта возможна только тогда, когда мы перестанем произвольно подставлять вместо значения всего неизвестного Х те условия, при которых проявляется сила, как то: распоряжения полководца, вооружение и т. д., принимая их за значение множителя, а признаем это неизвестное во всей его цельности, то есть как большее или меньшее желание драться и подвергать себя опасности. Тогда только, выражая уравнениями известные исторические факты, из сравнения относительного значения этого неизвестного можно надеяться на определение самого неизвестного.
Десять человек, батальонов или дивизий, сражаясь с пятнадцатью человеками, батальонами или дивизиями, победили пятнадцать, то есть убили и забрали в плен всех без остатка и сами потеряли четыре; стало быть, уничтожились с одной стороны четыре, с другой стороны пятнадцать. Следовательно, четыре были равны пятнадцати, и, следовательно, 4а:=15у. Следовательно, ж: г/==15:4. Уравнение это не дает значения неизвестного, но оно дает отношение между двумя неизвестными. И из подведения под таковые уравнения исторических различно взятых единиц (сражений, кампаний, периодов войн) получатся ряды чисел, в которых должны существовать и могут быть открыты законы.
Тактическое правило о том, что надо действовать массами при наступлении и разрозненно при отступлении, бессознательно подтверждает только ту истину, что сила войска зависит от его духа. Для того чтобы вести людей под ядра, нужно больше дисциплины, достигаемой только движением в массах, чем для того, чтобы отбиваться от нападающих. Но правило это, при котором упускается из вида дух войска, беспрестанно оказывается неверным и в особенности поразительно противоречит действительности там, где является сильный подъем или упадок духа войска, – во всех народных войнах.
Французы, отступая в 1812 м году, хотя и должны бы защищаться отдельно, по тактике, жмутся в кучу, потому что дух войска упал так, что только масса сдерживает войско вместе. Русские, напротив, по тактике должны бы были нападать массой, на деле же раздробляются, потому что дух поднят так, что отдельные лица бьют без приказания французов и не нуждаются в принуждении для того, чтобы подвергать себя трудам и опасностям.

Так называемая партизанская война началась со вступления неприятеля в Смоленск.
Прежде чем партизанская война была официально принята нашим правительством, уже тысячи людей неприятельской армии – отсталые мародеры, фуражиры – были истреблены казаками и мужиками, побивавшими этих людей так же бессознательно, как бессознательно собаки загрызают забеглую бешеную собаку. Денис Давыдов своим русским чутьем первый понял значение той страшной дубины, которая, не спрашивая правил военного искусства, уничтожала французов, и ему принадлежит слава первого шага для узаконения этого приема войны.
24 го августа был учрежден первый партизанский отряд Давыдова, и вслед за его отрядом стали учреждаться другие. Чем дальше подвигалась кампания, тем более увеличивалось число этих отрядов.
Партизаны уничтожали Великую армию по частям. Они подбирали те отпадавшие листья, которые сами собою сыпались с иссохшего дерева – французского войска, и иногда трясли это дерево. В октябре, в то время как французы бежали к Смоленску, этих партий различных величин и характеров были сотни. Были партии, перенимавшие все приемы армии, с пехотой, артиллерией, штабами, с удобствами жизни; были одни казачьи, кавалерийские; были мелкие, сборные, пешие и конные, были мужицкие и помещичьи, никому не известные. Был дьячок начальником партии, взявший в месяц несколько сот пленных. Была старостиха Василиса, побившая сотни французов.
Последние числа октября было время самого разгара партизанской войны. Тот первый период этой войны, во время которого партизаны, сами удивляясь своей дерзости, боялись всякую минуту быть пойманными и окруженными французами и, не расседлывая и почти не слезая с лошадей, прятались по лесам, ожидая всякую минуту погони, – уже прошел. Теперь уже война эта определилась, всем стало ясно, что можно было предпринять с французами и чего нельзя было предпринимать. Теперь уже только те начальники отрядов, которые с штабами, по правилам ходили вдали от французов, считали еще многое невозможным. Мелкие же партизаны, давно уже начавшие свое дело и близко высматривавшие французов, считали возможным то, о чем не смели и думать начальники больших отрядов. Казаки же и мужики, лазившие между французами, считали, что теперь уже все было возможно.
22 го октября Денисов, бывший одним из партизанов, находился с своей партией в самом разгаре партизанской страсти. С утра он с своей партией был на ходу. Он целый день по лесам, примыкавшим к большой дороге, следил за большим французским транспортом кавалерийских вещей и русских пленных, отделившимся от других войск и под сильным прикрытием, как это было известно от лазутчиков и пленных, направлявшимся к Смоленску. Про этот транспорт было известно не только Денисову и Долохову (тоже партизану с небольшой партией), ходившему близко от Денисова, но и начальникам больших отрядов с штабами: все знали про этот транспорт и, как говорил Денисов, точили на него зубы. Двое из этих больших отрядных начальников – один поляк, другой немец – почти в одно и то же время прислали Денисову приглашение присоединиться каждый к своему отряду, с тем чтобы напасть на транспорт.
– Нет, бг"ат, я сам с усам, – сказал Денисов, прочтя эти бумаги, и написал немцу, что, несмотря на душевное желание, которое он имел служить под начальством столь доблестного и знаменитого генерала, он должен лишить себя этого счастья, потому что уже поступил под начальство генерала поляка. Генералу же поляку он написал то же самое, уведомляя его, что он уже поступил под начальство немца.
Распорядившись таким образом, Денисов намеревался, без донесения о том высшим начальникам, вместе с Долоховым атаковать и взять этот транспорт своими небольшими силами. Транспорт шел 22 октября от деревни Микулиной к деревне Шамшевой. С левой стороны дороги от Микулина к Шамшеву шли большие леса, местами подходившие к самой дороге, местами отдалявшиеся от дороги на версту и больше. По этим то лесам целый день, то углубляясь в середину их, то выезжая на опушку, ехал с партией Денисов, не выпуская из виду двигавшихся французов. С утра, недалеко от Микулина, там, где лес близко подходил к дороге, казаки из партии Денисова захватили две ставшие в грязи французские фуры с кавалерийскими седлами и увезли их в лес. С тех пор и до самого вечера партия, не нападая, следила за движением французов. Надо было, не испугав их, дать спокойно дойти до Шамшева и тогда, соединившись с Долоховым, который должен был к вечеру приехать на совещание к караулке в лесу (в версте от Шамшева), на рассвете пасть с двух сторон как снег на голову и побить и забрать всех разом.
Позади, в двух верстах от Микулина, там, где лес подходил к самой дороге, было оставлено шесть казаков, которые должны были донести сейчас же, как только покажутся новые колонны французов.
Впереди Шамшева точно так же Долохов должен был исследовать дорогу, чтобы знать, на каком расстоянии есть еще другие французские войска. При транспорте предполагалось тысяча пятьсот человек. У Денисова было двести человек, у Долохова могло быть столько же. Но превосходство числа не останавливало Денисова. Одно только, что еще нужно было знать ему, это то, какие именно были эти войска; и для этой цели Денисову нужно было взять языка (то есть человека из неприятельской колонны). В утреннее нападение на фуры дело сделалось с такою поспешностью, что бывших при фурах французов всех перебили и захватили живым только мальчишку барабанщика, который был отсталый и ничего не мог сказать положительно о том, какие были войска в колонне.
Нападать другой раз Денисов считал опасным, чтобы не встревожить всю колонну, и потому он послал вперед в Шамшево бывшего при его партии мужика Тихона Щербатого – захватить, ежели можно, хоть одного из бывших там французских передовых квартиргеров.

Транскрипт

1 Часть 3. Методы параллельных вычислений 6. Принципы разработки параллельных методов 6. Принципы разработки параллельных методов Моделирование параллельных программ Этапы разработки параллельных алгоритмов Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование набора подзадач Распределение подзадач между процессорами Параллельное решение гравитационной задачи N тел Разделение вычислений на независимые части Выделение информационных зависимостей Масштабирование и распределение подзадач по процессорам Анализ эффективности параллельных вычислений Краткий обзор раздела Обзор литературы Контрольные вопросы Задачи и упражнения Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную проблему. Для снижения сложности рассматриваемой темы оставим в стороне математические аспекты разработки и доказательства сходимости алгоритмов эти вопросы в той или иной степени изучаются в ряде "классических" математических учебных курсов. Здесь же мы будем полагать, что вычислительные схемы решения задач, рассматриваемых далее в качестве примеров, уже известны 1). С учетом высказанных предположений последующие действия для определения эффективных способов организации параллельных вычислений могут состоять в следующем: Выполнить анализ имеющихся вычислительных схем и осуществить их разделение (декомпозицию) на части (подзадачи), которые могут быть реализованы в значительной степени независимо друг от друга, Выделить для сформированного набора подзадач информационные взаимодействия, которые должны осуществляться в ходе решения исходной поставленной задачи, Определить необходимую (или доступную) для решения задачи вычислительную систему и выполнить распределение имеющего набора подзадач между процессорами системы. При самом общем рассмотрении понятно, что объем вычислений для каждого используемого процессора должен быть примерно одинаков это позволит обеспечить равномерную вычислительную загрузку (балансировку) процессоров. Кроме того, также понятно, что распределение подзадач между процессорами должно быть выполнено таким образом, чтобы наличие информационных связей (коммуникационных взаимодействий) между подзадачами было минимальным. 1) Несмотря на то, что для многих научно-технических задач на самом деле известны не только последовательные, но и параллельные методы решения, данное предположение является, конечно, очень сильным, поскольку для новых возникающих задач, требующих для своего решения большого объема вычислений, процесс разработки алгоритмов составляет существенную часть всех выполняемых работ.

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

3 передачи сообщений. В дополнение, на этой модели может быть показано распределение процессов по процессорам вычислительной системы, если количество подзадач превышает число процессоров см. рис процесс - канал - операции приема (передачи) - входные (выходные) каналы для взаимодействия процессов Рис Модель параллельной программы в виде графа "процессы-каналы" Использование двух моделей параллельных вычислений 2) позволяет лучше разделить проблемы, которые проявляются при разработке параллельных методов. Первая модель граф "подзадачи - сообщения" позволяет сосредоточиться на вопросах выделения подзадач одинаковой вычислительной сложности, обеспечивая при этом низкий уровень информационной зависимости между подзадачами. Вторая модель граф "процессы каналы" концентрирует внимание на вопросах распределения подзадач по процессорам, обеспечивая еще одну возможность снижения трудоемкости информационных взаимодействий между подзадачами за счет размещения на одних и тех же процессорах интенсивно взаимодействующих процессов. Кроме того, эта модель позволяет лучше анализировать эффективность разработанного параллельного метода и обеспечивает возможность более адекватного описания процесса выполнения параллельных вычислений. Дадим дополнительные пояснения для используемых понятий в модели "процессы-каналы": Под процессом в рамках данного учебного материала будем понимать выполняемую на процессоре программу, которая использует для свой работы часть локальной памяти процессора и которая содержит ряд операций приема/передачи данных для организации информационного взаимодействия между выполняемыми процессами параллельной программы, Канал передачи данных с логической точки зрения может рассматриваться как очередь сообщений, в которую один или несколько процессов могут отправлять пересылаемые данные и из которой процесс-адресат может извлекать сообщения, отправляемые другими процессами. В общем случае, можно считать, что каналы возникают динамически в момент выполнения первой операции приема/передачи с каналом. По степени общности, канал может соответствовать одной или нескольким командам приема данных процесса-получателя; аналогично при передаче сообщений канал может использоваться одной или несколькими командами передачи данных одного или нескольких процессов. Для снижения сложности моделирования и анализа параллельных методов будем предполагать, что емкость каналов является неограниченной и, как результат, операции передачи данных выполняются практически без задержек простым копированием сообщений в канал. С другой стороны, операции приема сообщений могут приводить к задержкам (блокировкам), если запрашиваемые из канала данные еще не были отправлены процессами-источниками сообщений. Следует отметить важное достоинство рассмотренной модели "процессы-каналы" в этой модели проводится четкое разделение локальных (выполняемых на отдельном процессоре) вычислений и 2) В Foster (1995) рассматривается только одна модель модель "задача-канал" для описания параллельных вычислений, которая занимает некоторое промежуточное положение по сравнению с изложенными здесь моделями. Так, в модели "задачаканал" не учитывается возможность использования одного процессора для решения нескольких подзадач одновременно. 3

4 действий по организации информационного взаимодействия одновременно выполняемых процессов. Такой подход значительно снижает сложность анализа эффективности параллельных методов и существенно упрощает проблемы разработки параллельных программ Этапы разработки параллельных алгоритмов Рассмотрим более подробно изложенную выше методику разработки параллельных алгоритмов. В значительной степени данная методика опирается на подход, впервые рассмотренный в Foster (1995), и, как отмечалось ранее, включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы (см. рис. 6.1). Для демонстрации приводимых рекомендаций далее будет использоваться учебная задача поиска максимального значения среди элементов матрицы A (такая задача возникает, например, при численном решении систем линейных уравнений для определения ведущего элемента метода Гаусса): y = max a. 1 i, j N i j Такая задача носит полностью иллюстративный характер, и после рассмотрения этапов разработки в оставшейся части раздела будет приведен более полный пример использования данной методики для разработки параллельных алгоритмов. Кроме того, данная схема разработки будет применена и при изложении всех далее рассматриваемых методов параллельных вычислений Разделение вычислений на независимые части Выбор способа разделения вычислений на независимые части основывается на анализе вычислительной схемы решения исходной задачи. Требования, которым должен удовлетворять выбираемый подход, обычно состоят в обеспечении равного объема вычислений в выделяемых подзадачах и минимума информационных зависимостей между этими подзадачами (при прочих равных условиях нужно отдавать предпочтение редким операциям передачи большего размера сообщений по сравнению с частыми пересылками данных небольшого объема). В общем случае, проведение анализа и выделение задач представляет собой достаточно сложную проблему ситуацию помогает разрешить существование двух часто встречающихся типов вычислительных схем: а) б) Рис Разделение данных для матрицы A: а) ленточная схема, б) блочная схема Для большого класса задач вычисления сводятся к выполнению однотипной обработки элемент элементов большого набора данных к такому виду задач относятся, например, матричные вычисления, численные методы решения уравнений в частных производных и др. В этом случае говорят, что существует параллелизм по данным, и выделение подзадач сводится к разделению имеющихся данных. Так, например, для нашей учебной задачи поиска максимального значения при формировании подзадач исходная матрица A может быть разделена на отдельные строки (или последовательные группы строк) ленточная схема разделения данных (см. рис. 6.3) или на прямоугольные наборы элементов блочная схема разделения данных. Для большого количества решаемых задач разделение вычислений по данным приводит к порождению одно-, двух- и трех- мерных наборов подзадач, для которых информационные связи существуют только между ближайшими соседями (такие схемы обычно именуются сетками или решетками), 4

5 Рис Регулярные одно-, двух- и трех- мерные структуры базовых подзадач после декомпозиции данных Для другой части задач вычисления могут состоять в выполнении разных операций над одним и тем же набором данных в этом случае говорят о существовании функционального параллелизма (в качестве примеров можно привести задачи обработки последовательности запросов к информационным базам данных, вычисления с одновременным применением разных алгоритмов расчета и т.п.). Очень часто функциональная декомпозиция может быть использована для организации конвейерной обработки данных (так, например, при выполнении каких-либо преобразований данных вычисления могут быть сведены к функциональной последовательности ввода, обработки и сохранения данных). Важный вопрос при выделении подзадач состоит в выборе нужного уровня декомпозиции вычислений. Формирование максимально возможного количества подзадач обеспечивает использование предельно достижимого уровня параллелизма решаемой задачи, однако затрудняет анализ параллельных вычислений. Использование при декомпозиции вычислений только достаточно "крупных" подзадач приводит к ясной схеме параллельных вычислений, однако может затруднить эффективное использование достаточно большого количества процессоров. Возможное разумное сочетание этих двух подходов может состоять в использовании в качестве конструктивных элементов декомпозиции только тех подзадач, для которых методы параллельных вычислений являются известными. Так, например, при анализе задачи матричного умножения в качестве подзадач можно использовать методы скалярного произведения векторов или алгоритмы матрично-векторного произведения. Подобный промежуточный способ декомпозиции вычислений позволит обеспечить и простоту представления вычислительных схем, и эффективность параллельных расчетов. Выбираемые подзадачи при таком подходе будем именовать далее базовыми, которые могут быть элементарными (неделимыми), если не допускают дальнейшего разделения, или составными в противном случае. Для рассматриваемой учебной задачи достаточный уровень декомпозиции может состоять, например, в разделении матрицы A на множество отдельных строк и получении на этой основе набора подзадач поиска максимальных значений в отдельных строках; порождаемая при этом структура информационных связей соответствует линейному графу см. рис Для оценки корректности этапа разделения вычислений на независимые части можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Выполненная декомпозиция не увеличивает объем вычислений и необходимый объем памяти? Возможна ли при выбранном способе декомпозиции равномерная загрузка всех имеющихся процессоров? Достаточно ли выделенных частей процесса вычислений для эффективной загрузки имеющихся процессоров (с учетом возможности увеличения их количества)? Выделение информационных зависимостей При наличии вычислительной схемы решения задачи после выделения базовых подзадач определение информационных зависимостей между подзадачами обычно не вызывает больших затруднений. При этом, однако, следует отметить, что на самом деле этапы выделения подзадач и информационных зависимостей достаточно сложно поддаются разделению. Выделение подзадач должно происходить с учетом возникающих информационных связей; после анализа объема и частоты необходимых информационных обменов между подзадачами может потребоваться повторение этапа разделения вычислений. При проведении анализа информационных зависимостей между подзадачами следует различать (предпочтительные формы информационного взаимодействия выделены подчеркиванием): Локальные и глобальные схемы передачи данных для локальных схем передачи данных в каждый момент времени выполняются только между небольшим числом подзадач (располагаемых, как 5

6 правило, на соседних процессорах), для глобальных операций передачи данных в процессе коммуникации принимают участие все подзадачи, Структурные и произвольные способы взаимодействия для структурных способов организация взаимодействий приводит к формированию некоторых стандартных схем коммуникации (например, в виде кольца, прямоугольной решетки и т.д.), для произвольных структур взаимодействия схема выполняемых операций передач данных не носит характер однородности, Статические или динамические схемы передачи данных для статических схем моменты и участники информационного взаимодействия фиксируются на этапах проектирования и разработки параллельных программ, для динамического варианта взаимодействия структура операции передачи данных определяется в ходе выполняемых вычислений, Синхронные и асинхронные способы взаимодействия для синхронных способов операции передачи данных выполняются только при готовности всех участников взаимодействия и завершаются только после полного окончания всех коммуникационных действий, при асинхронном выполнении операций участники взаимодействия могут не дожидаться полного завершения действий по передаче данных. Для представленных способов взаимодействия достаточно сложно выделить предпочтительные формы организации передачи данных: синхронный вариант, как правило, более прост для использования, в то время как асинхронный способ часто позволяет существенно снизить временные задержки, вызванные операциями информационного взаимодействия. Как уже отмечалось в предыдущем пункте, для учебной задачи поиска максимального значения при использовании в качестве базовых элементов подзадач поиска максимальных значений в отдельных строках исходной матрицы A структура информационных связей имеет вид, представленный на рис Рис Структура информационных связей учебной задачи Как и ранее, для оценки правильности этапа выделения информационных зависимостей можно воспользоваться контрольным списком вопросов, предложенных в Foster (1995): Соответствует ли вычислительная сложность подзадач интенсивности их информационных взаимодействий? Является ли одинаковой интенсивность информационных взаимодействий для разных подзадач? Является ли схема информационного взаимодействия локальной? Не препятствует ли выявленная информационная зависимость параллельному решению подзадач? Масштабирование набора подзадач Масштабирование разработанной вычислительной схемы параллельных вычислений проводится в случае, если количество имеющихся подзадач отличается от числа планируемых к использованию процессоров. Для сокращения количества подзадач необходимо выполнить укрупнение (агрегацию) вычислений. Применяемые здесь правила совпадают с рекомендациями начального этапа выделения подзадач определяемые подзадачи, как и ранее, должны иметь одинаковую вычислительную сложность, а объем и интенсивность информационных взаимодействий между подзадачами должны оставаться на минимально-возможном уровне. Как результат, первыми претендентами на объединение являются подзадачи с высокой степенью информационной взаимозависимости. При недостаточном количестве имеющегося набора подзадач для загрузки всех доступных к использованию процессоров необходимо выполнить детализацию (декомпозицию) вычислений. Как 6

7 правило, проведение подобной декомпозиции не вызывает каких-либо затруднений, если для базовых задач методы параллельных вычислений являются известными. Выполнение этапа масштабирования вычислений должно свестись, в конечном итоге, к разработке правил агрегации и декомпозиции подзадач, которые должны параметрически зависеть от числа процессоров, применяемых для вычислений. Для рассматриваемой учебной задачи поиска максимального значения агрегация вычислений может состоять в объединении отдельных строк в группы (ленточная схема разделения матрицы см. рис. 6.3а), при декомпозиции подзадач строки исходной матрицы A могут разбиваться на несколько частей (блоков). Список контрольных вопросов, предложенный в Foster (1995) для оценки правильности этапа масштабирования, выглядит следующим образом: Не ухудшится ли локальность вычислений после масштабирования имеющегося набора подзадач? Имеют ли подзадачи после масштабирования одинаковую вычислительную и коммуникационную сложность? Соответствует ли количество задач числу имеющихся процессоров? Зависят ли параметрически правила масштабирования от количества процессоров? Распределение подзадач между процессорами Распределение подзадач между процессорами является завершающим этапом разработки параллельного метода. Надо отметить, что управление распределением нагрузки для процессоров возможно только для вычислительных систем с распределенной памятью, для мультипроцессоров (систем с общей памятью) распределение нагрузки обычно выполняется операционной системой автоматически. Кроме того, данный этап распределения подзадач между процессорами является избыточным, если количество подзадач совпадает с числом имеющихся процессоров, а топология сети передачи данных вычислительной системы представляет собой полный граф (т.е., все процессоры связаны между собой прямыми линиями связи). Основной показатель успешности выполнения данного этапа эффективность использования процессоров, определяемая как относительная доля времени, в течение которого процессоры использовались для вычислений, связанных с решением исходной задачи. Пути достижения хороших результатов в этом направлении остаются прежними как и ранее, необходимо обеспечить равномерное распределение вычислительной нагрузки между процессорами и минимизировать количество сообщений, передаваемых между процессорами. Точно так же, как и на предшествующих этапах проектирования, оптимальное решение проблемы распределения подзадач между процессорами основывается на анализе информационной связности графа "подзадачи - сообщения". Так, в частности, подзадачи, между которыми имеются информационные взаимодействия, целесообразно размещать на процессорах, между которыми существуют прямые линии передачи данных. Следует отметить, что требование минимизации информационных обменов между процессорами может противоречить условию равномерной загрузки процессов. Так, мы можем разместить все подзадачи на одном процессоре и полностью устранить межпроцессорную передачу сообщений, однако, понятно, загрузка большинства процессоров в этом случае будет минимальной. Для нашей учебной задачи поиска максимального значения распределение подзадач между процессорами не вызывает каких-либо затруднений достаточно лишь обеспечить размещение подзадач, между которыми имеются информационные связи, на процессорах, для которых существуют прямые каналы передачи данных. Поскольку структура информационной связей учебной задачи имеет вид линейного графа, выполнение данного требования может быть обеспечено практически при любой топологии сети вычислительной системы. Решение вопросов балансировки вычислительной нагрузки значительно усложняется, если схема вычислений может изменяться в ходе решения задачи. Причиной этого могут быть, например, неоднородные сетки при решении уравнений в частных производных, разреженность матриц и т.п. 3). Кроме того, используемые на этапах проектирования оценки вычислительной сложности решения подзадач могут иметь приближенный характер и, наконец, количество подзадач может изменяться в ходе вычислений. В таких ситуациях может потребоваться перераспределение базовых подзадач между 3) Можно отметить, что даже для нашей простой учебной задачи может наблюдаться различная вычислительная сложность сформированных базовых задач. Так, например, количество операций при поиске максимального значения для строки, в которой максимальное значение имеет первый элемент, и строки, в которой значения являются упорядоченными по возрастанию, будет различаться в два раза. 7

8 процессорами уже непосредственно в процессе выполнения параллельной программы (или, как обычно говорят, придется выполнить динамическую балансировку вычислительной нагрузки). Данные вопросы являются одними из наиболее сложных (и наиболее интересных) в области параллельных вычислений к сожалению, рассмотрение данных вопросов выходит за рамки данного учебного материала (дополнительная информация может быть получена, например, в Buyya (1999) и Wilkinson and Allen (1999)). В качестве примера дадим краткую характеристику широко используемого способа динамического управления распределением вычислительной нагрузки, обычно именуемого схемой "менеджер - исполнитель" (manager-worker scheme). При использовании данного подхода предполагается, что подзадачи могут возникать и завершаться в ходе вычислений, при этом информационные взаимодействия между подзадачами либо полностью отсутствует, либо минимальны. В соответствии с рассматриваемой схемой для управления распределением нагрузки в системе выделяется отдельный процессор-менеджер, которому доступна информация обо всех имеющихся подзадачах. Остальные процессоры системы являются исполнителями, которые для получения вычислительной нагрузки обращаются к процессору-менеджеру. Порождаемые в ходе вычислений новые подзадачи передаются обратно процессору-менеджеру и могут быть получены для решения при последующих обращениях процессоров-исполнителей. Завершение вычислений происходит в момент, когда процессорыисполнители завершили решение всех переданных им подзадач, а процессор-менеджер не имеет какихлибо вычислительных работ для выполнения. Предложенный в Foster (1995) перечень контрольных вопросов для проверки этапа распределения подзадач состоит в следующем: Не приводит ли распределение нескольких задач на один процессор к росту дополнительных вычислительных затрат? Существует ли необходимость динамической балансировки вычислений? Не является ли процессор-менеджер "узким" местом при использовании схемы "менеджерисполнитель"? 6.3. Параллельное решение гравитационной задачи N тел Многие вычислительные задачи в области физики сводятся к операциям обработки данных для каждой пары объектов имеющейся физической системы. Такой задачей является, в частности, проблема, широко известная в литературе как гравитационная задача N тел (или просто задача N тел) см., например, Andrews (2000) В самом общем виде, задача может быть описана следующим образом. Пусть дано большое количество тел (планет, звезд и т.д.), для каждого из которых известна масса, начальное положение и скорость. Под действием гравитации положение тел меняется, и требуемое решение задачи состоит в моделировании динамики изменения системы N тел на протяжении некоторого задаваемого интервала времени. Для проведения такого моделирования заданный интервал времени обычно разбивается на временные отрезки небольшой длительности и далее на каждом шаге моделирования вычисляются силы, действующие на каждое тело, а затем обновляются скорости и положения тел. Очевидный алгоритм решения задачи N тел состоит в рассмотрении на каждом шаге моделирования всех пар объектов физической системы и выполнении для каждой получаемой пары всех необходимых расчетов. Как результат, при таком подходе время выполнения одной итерации моделирования будет составлять 4) T = τ N(N 1) / 2, 1 где τ есть время перевычисления параметров одной пары тел. Как следует из приведенного описания, вычислительная схема рассмотренного алгоритма является сравнительно простой, что позволяет использовать задачу N тел в качестве еще одной наглядной демонстрации применения методики разработки параллельных алгоритмов. 4) Следует отметить, что для решения задачи N тел существует и более эффективные последовательные алгоритмы, однако их изучение может потребовать достаточно больших усилий. С учетом данного обстоятельства для дальнейшего рассмотрения выбирается именно данный "очевидный" (но не самый быстрый) метод, хотя, в общем случае, безусловно, для распараллеливания следует выбирать наилучшие схемы выполнения расчетов. 8

9 Разделение вычислений на независимые части Выбор способа разделения вычислений не вызывает каких-либо затруднений - очевидный подход состоит в выборе в качестве базовой подзадачи всего набора вычислений, связанных с обработкой данных одного какого-либо тела физической системы Выделение информационных зависимостей Выполнение вычислений, связанных с каждой подзадачей, становится возможным только в случае, когда в подзадачах имеются данные (положение и скорости передвижения) обо всех телах имеющейся физической системы. Как результат, перед началом каждой итерации моделирования каждая подзадача должна получить все необходимые сведения от всех других подзадач системы. Такая процедура передачи данных, как отмечалось в разделе 3, именуется операцией сбора данных (single-node gather). В рассматриваемом алгоритме данная операция должна быть выполнена для каждой подзадачи такой вариант передачи данных обычно именуется как операция обобщенного сбора данных (multi-node gather or all gather). Определение требований к необходимым результатам информационного обмена не приводит к однозначному установлению нужного информационного обмена между подзадачами достижение требуемых результатов может быть обеспечено при помощи разных алгоритмов выполнения операции обобщенного сбора данных. Наиболее простой способ выполнения необходимого информационного обмена состоит в реализации последовательности шагов, на каждом из которых все имеющиеся подзадачи разбиваются попарно и обмен данными осуществляется между подзадачами образовавшихся пар. При надлежащей организации попарного разделения подзадач (N-1)-кратное повторение описанных действий приведет к полной реализации требуемой операции сбора данных. Рассмотренный выше метод организации информационного обмена является достаточно трудоемким для сбора всех необходимых данных требуется (N-1) итераций, на каждой из которых выполняется одновременно (N/2) операций передачи данных. Для сокращения требуемого количества итераций можно обратить внимание на факт, что после выполнения первого шага операции сбора данных подзадачи будут уже содержать не только свои данные, но и данные подзадач, с которыми они образовывали пары. Как результат, на второй итерации сбора данных можно будет образовывать пары подзадач для обмена данными сразу о двух телах физической системы тем самым, после завершения второй итерации каждая подзадача будет содержать сведения о четырех телах системы и т.д. Как можно заметить, данный способ реализации обменов позволяет завершить необходимую процедуру за log 2 N итераций. Следует отметить, что при этом объем пересылаемых данных в каждой операции обмена удваивается от итерации к итерации на первой итерации между подзадачами пересылаются данные об одном теле системы, на второй итерации о двух телах и т.д. Использование рассмотренного способа реализации операции обобщенного сбора данных приводит к определению структуры информационных связей между подзадачами в виде N-мерного гиперкуба Масштабирование и распределение подзадач по процессорам Как правило, число тел физической системы N значительно превышает количество процессоров p. Как результат, рассмотренные ранее подзадачи следует укрупнить, объединив в рамках одной подзадачи вычисления для группы (N/p) тел. После проведения подобной агрегации число подзадач и количество процессоров будет совпадать, и при распределении подзадач между процессорами останется лишь обеспечить наличие прямых коммуникационных линий между процессорами с подзадачами, между которыми имеются информационные обмены при выполнении операции сбора данных Анализ эффективности параллельных вычислений Оценим эффективность разработанных способов параллельных вычислений для решения задачи N тел. Поскольку предложенные варианты отличаются только методами выполнения информационных обменов, для сравнения подходов достаточно определить длительность операции обобщенного сбора данных. Используем для оценки времени передачи сообщений модель, предложенную Хокни (см. раздел 3), тогда длительность выполнения операции сбора данных для первого варианта параллельных вычислений может быть выражена как 1 T p (comm) = (p 1)(α + m (N / p) / β), где α, β есть параметры модели Хокни (латентность и пропускная способность сети передачи данных), а m задает объем пересылаемых данных для одного тела физической системы. 9

10 Для второго способа информационного обмена, как уже отмечалось ранее, объем пересылаемых данных на разных итерациях операции сбора данных различается. На первой итерации объем пересылаемых сообщений составляет (mn/p), на второй итерации этот объем увеличивается вдвое и оказывается равным 2(mN/p) и т.д. В общем случае, для итерации с номером i объем сообщений оценивается как 2 i-1 (mn/p). Как результат, длительность выполнения операции сбора данных в этом случае может быть определена при помощи следующего выражения T 2 p log p i= 1 i 1 (comm) = (α + 2 m(N / p) / β) = α log p + m (N / p)(p 1) / β. Сравнение полученных выражений показывает, что второй разработанный способ параллельных вычислений имеет существенно более высокую эффективность, несет меньшие коммуникационные затраты и допускает лучшую масштабируемость при увеличении количества используемых процессоров Краткий обзор раздела В разделе была рассмотрена методика разработки параллельных алгоритмов, предложенная в Foster (1995). Данная методика включает этапы выделения подзадач, определения информационных зависимостей, масштабирования и распределения подзадач по процессорам вычислительной системы. При применении методики предполагается, что вычислительная схема решения рассматриваемой задачи уже является известной. Основные требования, которые должны быть обеспечены при разработке параллельных алгоритмов, состоят в обеспечении равномерной загрузки процессоров при низком информационном взаимодействии сформированного множества подзадач. Для описания получаемых в ходе разработки вычислительных параллельных схем рассмотрены две модели. Первая из них модель "подзадачи-сообщения" может быть использована на стадии проектирования параллельных алгоритмов, вторая модель "процессы-каналы" может быть применена на стадии реализации методов в виде параллельных программ. В завершение раздела показывается применение рассмотренной методики разработки параллельных алгоритмов на примере решения гравитационной задачи N тел Обзор литературы Рассмотренная в разделе методика разработки параллельных алгоритмов впервые была предложена в Foster (1995). В этой работе изложение методики проводится более детально; кроме того, в работе содержится несколько примеров использования методики для разработки параллельных методов для решения ряда вычислительных задач. Полезной при рассмотрении вопросов проектирования и разработки параллельных алгоритмов может оказаться также работа Quinn (2004). Гравитационная задача N тел более подробно рассматривается в Andrews (2000) Контрольные вопросы 1. В чем состоят исходные предположения для возможности применения рассмотренной в разделе методики разработки параллельных алгоритмов? 2. Каковы основные этапы проектирования и разработки методов параллельных вычислений? 3. Как определяется модель "подзадачи-сообщения"? 4. Как определяется модель "процессы-каналы"? 5. Какие основные требования должны быть обеспечены при разработке параллельных алгоритмов? 6. В чем состоят основные действия на этапе выделения подзадач? 7. Каковы основные действия на этапе определения информационных зависимостей? 8. В чем состоят основные действия на этапе масштабирования имеющегося набора подзадач? 9. В чем состоят основные действия на этапе распределения подзадач по процессорам вычислительной системы? 10. Как происходит динамическое управление распределением вычислительной нагрузки при помощи схемы "менеджер - исполнитель"? 11. Какой метод параллельных вычислений был разработан для решения гравитационной задачи N тел? 10

11 12. Какой способ выполнения операции обобщенного сбора данных является более эффективным? 6.7. Задачи и упражнения 1. Выполните реализацию каскадной схемы вычисления суммы последовательности числовых значений (см. раздел 2) и сравните время выполнения выполненной реализации и функции MPI_Bcast библиотеки MPI. 2. Выполните реализацию рассмотренных способов выполнения обобщенной операции сбора данных и сравните время их выполнения. Сопоставьте получаемые временные характеристики с имеющими теоретическими оценками. Выполните сравнение со временем выполнения функции MPI_Allgather библиотеки MPI. 3. Разработайте схему параллельных вычислений, используя рассмотренную в разделе методику проектирования и разработки параллельных методов: для задачи поиска максимального значения среди минимальных элементов строк матрицы (такая задача имеет место для решения матричных игр) y = max min a, 1 i N 1 j N ij (обратите особое внимание на ситуацию, когда число процессоров превышает порядок матрицы, т.е. p>n), для задачи вычисления определенного интеграла с использованием метода прямоугольников b N 1 y = f (x) dx h fi, a i= 0 f i = f (x), x = i h, h = (b a) / N. i i (описание методов интегрирования дано, например, в Kahaner, Moler and Nash (1988)) 4. Выполните реализацию разработанных параллельных методов для задач п Разработайте схему параллельных вычислений для задачи умножения матрицы на вектор, используя рассмотренную в разделе методику проектирования и разработки параллельных методов. Литература Andrews, G. R. (2000). Foundations of Multithreaded, Parallel, and Distributed Programming.. Reading, MA: Addison-Wesley (русский перевод Эндрюс Г.Р. Основы многопоточного, параллельного и распределенного программирования. М.: Издательский дом "Вильямс", 2003) Bertsekas, D.P., Tsitsiklis, J.N. (1989) Parallel and distributed Computation. Numerical Methods. - Prentice Hall, Englewood Cliffs, New Jersey. Buyya, R. (Ed.) (1999). High Performance Cluster Computing. Volume1: Architectures and Systems. Volume 2: Programming and Applications. - Prentice Hall PTR, Prentice-Hall Inc. Kahaner, D., Moler, C., Nash, S. (1988). Numerical Methods and Software. Prentice Hall (русский перевод Каханер Д., Моулер Л., Нэш С. Численные методы и программное обеспечение. М.: Мир, 2001) Foster, I. (1995). Designing and Building Parallel Programs: Concepts and Tools for Software Engineering. Reading, MA: Addison-Wesley. Quinn, M. J. (2004). Parallel Programming in C with MPI and OpenMP. New York, NY: McGraw-Hill. Wilkinson, B., Allen, M. (1999). Parallel programming. Prenrice Hall. 11

ГЛАВА 3 ПРИНЦИПЫ РАЗРАБОТКИ ПАРАЛЛЕЛЬНЫХ МЕТОДОВ Разработка алгоритмов (а в особенности методов параллельных вычислений) для решения сложных научно-технических задач часто представляет собой значительную

Методы и алгоритмы параллельных вычислений Проектирование параллельных алгоритмов Кулаков Кирилл Александрович 2016 Петрозаводск Цели проектирования Балансировка нагрузки Масштабируемость Эффективность

Высокопроизводительные вычисления Лекция 2. Оценка максимально возможного параллелизма Обеспечение наилучших наилучшего ускорения S T = эффективности E = 1 возможно не для всех вычислительно T трудоемких

Лекции Лекция 1. Принципы построения параллельных вычислительных систем.............................. 23 Лекция 2. Моделирование и анализ параллельных вычислений...... 49 Лекция 3. Оценка коммуникационной

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 9. Параллельные

Проект комиссии Президента по модернизации и технологическому развитию экономики России «Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного

Тема: Распараллеливание выражений на примере арифметических Основные характеристики сложности и параллельности Что подлежит распараллеливанию? Задача (декомпозиция на подзадачи меньшей размерности) 2Метод

ВОПРОСЫ К ТЕСТУ ПО КУРСУ «ПАРАЛЛЕЛЬНЫЕ ВЫЧИСЛИТЕЛЬНЫЕ СИСТЕМЫ» 1. Принципы построения параллельных вычислительных систем (15) 1. Схемы многопроцессорных систем с однородным и неоднородным доступом. 2.

Проектирование параллельных алгоритмов Лекция 3.1 29.03.2012 Т.Ю.Лымарь 1 3.1 Методология проектирования Разделение Установление связей Агрегирование Привязка к конкретной ЭВМ 29.03.2012 Т.Ю.Лымарь 2 3.1.1

Московский государственный университет им. М.В. Ломоносова История и методология параллельного программирования 9. Проектирование параллельных алгоритмов Разработчики: Л.Б. Соколинский, д.ф.-м.н., профессор

Федеральное агентство по образованию Нижегородский государственный университет им. Н.И. Лобачевского Национальный проект «Образование» Инновационная образовательная программа ННГУ. Образовательно-научный

Нижегородский государственный университет им. Н.И.Лобачевского Факультет вычислительной математики и кибернетики Кафедра математического обеспечения ЭВМ Лаборатория «Информационные технологии» ItLab Практический

Нижегородский государственный университет им. Н.И. Лобачевского - Национальный исследовательский университет - Лекция. Моделирование параллельных вычислений Гергель В.П., декан ВМК ННГУ Суперкомпьютерные

Алгоритмы для параллельных вычислительных систем 1. Типы параллелизма и методы синтеза параллельных алгоритмов. 2. Оценка эффективности параллельных алгоритмов. 1. Типы параллелизма и методы синтеза параллельных

СУПЕРКОМПЬЮТЕРНЫЙ КОНСОРЦИУМ УНИВЕРСИТЕТОВ РОССИИ Проект Создание системы подготовки высококвалифицированных кадров в области суперкомпьютерных технологий и специализированного программного обеспечения

Оценка эффективности параллельных алгоритмов Лекция 4. 29.03.2012 Т.Ю. Лымарь 1 Введение Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма:

Оценка эффективности параллельных алгоритмов Лекция 7 Т.Ю. Лымарь Принципиальный момент при разработке параллельных алгоритмов - анализ эффективности использования параллелизма: Оценка максимально возможного

ОСНОВНЫЕ ПОНЯТИЯ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ Параллельные вычисления (параллельная обработка) это использование нескольких или многих вычислительных устройств для одновременного выполнения разных частей одной

Математические модели и методы эффективного использования распределенных Цифровая вычислительных 3D-медицина систем Заголовок Результаты Подзаголовок в области компьютерной презентации графики и геометрического

УДК 681.5 ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ ЧИСЛЕННОГО РЕШЕНИЯ ЗАДАЧИ КОШИ ДЛЯ СОДУ Назарова И.А. Донецкий национальный технический университет Запропоновано паралельні чисельні алгоритми однокрокових методів для

ГЛАВА МОДЕЛИРОВАНИЕ И АНАЛИЗ ПАРАЛЛЕЛЬНЫХ ВЫЧИСЛЕНИЙ При разработке параллельных алгоритмов решения сложных научнотехнических задач принципиальным моментом является анализ эффективности использования параллелизма,

1. Цели и задачи дисциплины: Суперкомпьютерные технологии и высокопроизводительные вычисления с использованием многопроцессорных вычислительных систем (МВС) становятся важным фактором научно-технического

Построение статистических моделей эффективности параллельных программ В.Н.Белецкий, С.А.Резникова, А.А.Чемерис Институт проблем моделирования в энергетике им. Г.Е.Пухова НАН Украины В статье рассмотрен

Информатика, управление, экономика ТРУДЫ МФТИ 2 Том 2, (5) УДК 59687+475 АС Хританков Московский физико-технический институт (государственный университет) Математическая модель характеристик производительности

АЛГОРИТМЫ БАЛАНСИРОВКИ ЗАГРУЗКИ ПРОЦЕССОРОВ ПАРАЛЛЕЛЬНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ Бельков Д.В. Донецкий национальный технический университет, г. Донецк кафедра вычислительной математики и программирования

Вычислительные машины и программное обеспечение УДК 681.3.06 П.А. Павлов ЭФФЕКТИВНОСТЬ РАСПРЕДЁЛЕННЫХ ВЫЧИСЛЕНИЙ В МАСШТАБИРУЕМЫХ СИСТЕМАХ Масштабируемость (scalability) является одним из важнейших требований

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

ДИАГОНАЛЬНЫЙ МЕТОД УМНОЖЕНИЯ ПЛОТНЫХ МАТРИЦ Князькова Т.В., к.т.н., доцент, ВятГУ, г. Киров Сегодня с ростом мощностей вычислительных систем и современных суперкомпьютеров в широком спектре отраслей экономики

Введение 1 Глава 1 Задания 1.1 Разминка Первое задание на написание программы, использующей библиотеку MPI, одно на всех. 1.1.1 Вычисление числа π Вычислить число π по следующей формуле: 1 1 dx 4 1 + x

Лабораторная работа 4 Параллельная реализация метода Якоби в трехмерной области Цель работы: практическое освоение методов распараллеливания численных алгоритмов на регулярных сетках на примере реализации

Р. И. Идрисов ВРЕМЕННАЯ РАЗВЁРТКА ВНУТРЕННЕГО ПРЕДСТАВЛЕНИЯ IR2 ЯЗЫКА SISAL 3.1 * На сегодняшний день увеличение вычислительных мощностей связано уже не с ускорением отдельного, а с добавлением дополнительных

Стратегия оптимизационного исследования и методы решения задач статической и динамической оптимизации технологических объектов Задачи статической оптимизации технологических объектов традиционно формулируются

ОРГАНИЗАЦИЯ ПАРАЛЛЕЛЬНЫХ ЗЕРНИСТЫХ ВЫЧИСЛИТЕЛЬНЫХ ПРОЦЕССОВ (Получение параллельных последовательностей зернистых вычислений) Приведем примеры получения параллельных алгоритмов, множества операций которых

ПАРАЛЛЕЛЬНЫЕ СВОЙСТВА АЛГОРИТМА Параллельные компьютеры (суперкомпьютеры) предназначены для быстрого решения больших задач. Чем мощнее компьютер, тем потенциально быстрее можно решить на нем задачу. Помимо

Каляев А.В. ПРОГРАММИРОВАНИЕ ВИРТУАЛЬНЫХ АРХИТЕКТУР И ОРГАНИЗАЦИЯ СТРУКТУРНО- ПРОЦЕДУРНЫХ ВЫЧИСЛЕНИЙ В МНОГОПРОЦЕССОРНЫХ СИСТЕМАХ С МАССОВЫМ ПАРАЛЛЕЛИЗМОМ 1 Аннотация НИИ многопроцессорных вычислительных

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

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

РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ И СИСТЕМ НЕЛИНЕЙНЫХ УРАВНЕНИЙ.. РЕШЕНИЕ НЕЛИНЕЙНЫХ УРАВНЕНИЙ вида Численное решение нелинейных алгебраических или трансцендентных уравнений. заключается в нахождении значений

«Алгебра и геометрия» 13. Системы линейных алгебраических уравнений (СЛАУ). Теорема Кронекера-Капелли. Общее и частное решения СЛАУ. 14. Кривые второго порядка: эллипс, гипербола, парабола, и их свойства.

УДК 681.32 ПОВЫШЕНИЕ ПРОИЗВОДИТЕЛЬНОСТИ КЛАСТЕРОВ РАБОЧИХ СТАНЦИЙ С ИСПОЛЬЗОВАНИЕМ ВЕЕРНОГО РАСПРЕДЕЛЕНИЯ ДОПОЛНИТЕЛЬНЫХ ЗАДАНИЙ НА ПРОСТАИВАЮЩЕЕ ОБОРУДОВАНИЕ 2012 В. М. Довгаль 1, С. Г. Спирин 2 1 профессор

Граф алгоритма и параллельные вычисления. Внутренний параллелизм программ. Лекция 3 12.04.2012 (С) Л.Б.Соколинский 1 3.1 Внутренний параллелизм Программа содержит параллелизм, если некоторые ее части (операторы)

МИНОБРНАУКИ РОССИИ ФЕДЕРАЛЬНОЕ ГОСУДАРСТВЕННОЕ БЮДЖЕТНОЕ ОБРАЗОВАТЕЛЬНОЕ УЧРЕЖДЕНИЕ ВЫСШЕГО ПРОФЕССИОНАЛЬНОГО ОБРАЗОВАНИЯ «САМАРСКИЙ ГОСУДАРСТВЕННЫЙ АЭРОКОСМИЧЕСКИЙ УНИВЕРСИТЕТ ИМЕНИ АКАДЕМИКА С.П.КОРОЛЕВА

Лекция 5 5 Теорема существования и единственности решения задачи Коши для нормальной системы ОДУ Постановка задачи Задача Коши для нормальной системы ОДУ x = f (, x), () состоит в отыскании решения x =

Нижегородский государственный университет им. Н.И.Лобачевского Факультет Вычислительной математики и кибернетики Образовательный комплекс Введение в методы параллельного программирования Раздел 2. Моделирование

Глава 5. МЕТОДЫ НЕЯВНОГО ПЕРЕБОРА Рассмотрим общую постановку задачи дискретной оптимизации mi f (x), (5.) x D в которой -мерный искомый вектор x принадлежит конечному множеству допустимых решений D.

ОГЛАВЛЕНИЕ Введение.... 12 Ч а с т ь I. Основы распараллеливания Лекция 1. О постановке задачи распараллеливания... 17 1.1. Введение.... 17 1.2. О некоторых вычислительных задачах.... 19 1.3. Численный

УДК 68.3.06 ОПРЕДЕЛЕНИЕ ЧИСЛА И ТОПОЛОГИИ РАЗМЕЩЕНИЯ СТАНЦИЙ МНОГОПРОЦЕССОРНОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ А.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected] Рассмотрены задачи

ЭКСТРАПОЛЯЦИОННЫЕ БЛОЧНЫЕ ОДНОШАГОВЫЕ МЕТОДЫ ЧИСЛЕННОГО ВЫСОКОТОЧНОГО РЕШЕНИЯ ЗАДАЧИ КОШИ Кулаков В.В. Назарова И. А.Фельдман Л.П. Донецкий национальный технический университет Рассматриваются параллельные

Труды ИСА РАН, 2008. Т. 32 О понятии производительности в распределенных вычислительных системах М. А. Посыпкин, А. С. Хританков Институт системного анализа Российской академии наук (ИСА РАН) В данной

2007 НАУЧНЫЙ ВЕСТНИК МГТУ ГА 26 серия Радиофизика и радиотехника УДК 6236:6239 ОЦЕНКА ЦЕЛЕСООБРАЗНОСТИ РАСПАРАЛЛЕЛИВАНИЯ ИНФОРМАЦИОННО-ЗАВИСИМЫХ ЗАДАЧ В ВЫЧИСЛИТЕЛЬНЫХ СИСТЕМАХ РН АКИНШИН Статья представлена

Максимальное распараллеливание алгоритмов на основе концепции Q-детерминанта Валентина Николаевна Алеева Южно-Уральский государственный университет (НИУ) Новосибирcк, 2015 ВВЕДЕНИЕ В докладе рассматривается

Министерство образования и науки Российской Федерации Нижегородский государственный университет им. Н.И. Лобачевского В.П. Гергель ВЫСОКОПРОИЗВОДИТЕЛЬНЫЕ ВЫЧИСЛЕНИЯ ДЛЯ МНОГОПРОЦЕССОР- НЫХ МНОГОЯДЕРНЫХ

ЛК 1. Моделирование. 1. Основные понятия. 2 Принципы моделирования. 3 Свойства моделей 4 Классификация методов моделирования. 5. Математическое моделирование 1. ОСНОВНЫЕ ПОНЯТИЯ. Моделирование замещение

Федеральное агентство по образованию Государственное образовательное учреждение высшего профессионального образования «Новосибирский государственный университет» (НГУ) Факультет информационных технологий

Нижегородский государственный университет им. Н.И. Лобачевского Научно исследовательский университет Создание учебной библиотеки параллельных методов Parlib Выполнили: Козинов Е.А. Кутлаев М.В. Осокин

УДК 681.3.06 ПРОЕКТИРОВАНИЕ СТРУКТУРЫ ЛОКАЛЬНОЙ СЕТИ ДЛЯ РАСПРЕДЕЛЕННОЙ ВЫЧИСЛИТЕЛЬНОЙ СИСТЕМЫ РЕАЛЬНОГО ВРЕМЕНИ А.В. Погребной, Д.В. Погребной Институт «Кибернетический центр» ТПУ E-mail: [email protected]

ПАРАЛЛЕЛЬНЫЕ АЛГОРИТМЫ МЕТОДА ЦИКЛИЧЕСКОЙ ПРОГОНКИ Головашкин Д.Л., Филатов М. В. Институт систем обработки изображений РАН Самарский государственный аэрокосмический университет Аннотация Работа посвящена

УДК 519.856; 519.854; 519.85 СТАТИСТИЧЕСКИЙ ПОИСК СТРУКТУР ИНФОРМАЦИОННО- ВЫЧИСЛИТЕЛЬНОЙ СЕТИ В.В. Малыгин Исследованы свойства сходимости функции оценки структуры информационно вычислительной сети. На

Построение рекурсивно-параллельных алгоритмов решения задач вычислительной геометрии на основе стратегии «распределяй и властвуй» В.Н. Терещенко В работе рассматривается один из подходов построения эффективных

12.1. Ввод-вывод по опросу готовности устройства Готовность или неготовность внешнего устройства к вводу-выводу проверяется в регистре состояния внешнего устройства Для программно-управляемого ввода/вывода

ТАКСОНОМИЯ ФЛИННА Кириллова Юлия 6057/2 22.11.11 Таксономия Флинна общая классификация архитектур ЭВМ по признакам наличия параллелизма в потоках команд и данных. предложена в 1972 г. Майклом Флинном.

Лабораторная работа 4 Решение задачи Пуассона методом Якоби в трехмерной области Цель - практическое освоение методов распараллеливание алгоритмов задач, решаемых сеточными методами на примере решения

Понятие параллельных вычислений

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

Лекция №6

Под параллельными вычислениями (parallel or concurrent computations) можно понимать процессы решения задач, в которых в один и тот же момент времени могут выполняться одновременно несколько вычислительных операций

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

· Параллельная обработка

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

Аналогично система из N устройств ту же работу выполнит за 1000/N единиц времени. Подобные аналогии можно найти и в жизни: если один солдат вскопает огород за 10 часов, то рота солдат из пятидесяти человек с такими же способностями, работая одновременно, справятся с той же работой за 12 минут - принцип параллельности в действии!

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

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

· Конвейерная обработка

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

Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят - ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5+99=104 единицы времени - ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

Модели параллельных компьютеров (классификация Флинна)

· «Один поток команд - один поток данных» (SISD - "Single Instruction Single Data")

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

· «Один поток команд - много потоков данных» (SIMD - "Single Instruction - Multiplе Data")

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

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

· «Много потоков команд - один поток данных» (MISD - "Multiple Instruction - Single Data")

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

Массивы ПЭ с непосредственными соединениями между близлежащими ПЭ называются систолическими . Такие массивы исключительно эффективны, но каждый из них ориентирован на решение весьма узкого класса задач. Рассмотрим, как можно построить систолический массив для решения некоторой задачи. Пусть, например, требуется создать устройство для вычисления матрицы D=C+AB , где

Здесь все матрицы - ленточные, порядка n . Матрица A имеет одну диагональ выше и две диагонали ниже главной; матрица B - одну диагональ ниже и две диагонали выше главной; матрица C по три диагонали выше и ниже главной. Пусть каждый ПЭ может выполнять скалярную операцию c+ab и одновременно осуществлять передачу данных. Каждый ПЭ, следовательно, должен иметь три входа: a, b, c и три выхода: a, b, c . Входные (in ) и выходные (out ) данные связаны соотношениями

a out = a in , b out = b in , c out = c in + a in *b in ;

Если в момент выполнения операции какие-то данные не поступили, то будем считать, что они доопределяются нулями. Предположим далее, что все ПЭ расположены на плоскости и каждый из них соединен с шестью соседними. Если расположить данные, как показано на рисунке, то схема будет вычислять матрицу D .

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

На рисунке показано состояние систолического массива в некоторый момент времени. В следующий такт все данные переместятся на один узел и элементы a11, b11, c11 окажутся в одном ПЭ, находящемся на пересечении штриховых линий. Следовательно, будет вычислено выражение c11+a11b11 .В этот же такт данные a12 и b21 вплотную приблизятся в ПЭ, находящемся в вершине систолического массива.

В следующий такт все данные снова переместятся на один узел в направлении стрелок и в верхнем ПЭ окажутся a12 и b21 и результат предыдущего срабатывания ПЭ, находящегося снизу, т.е. c11+a11b11 . Следовательно, будет вычислено выражение c11+a11b11+a12b21 . Это есть элемент d11 матрицы D .

Продолжая потактное рассмотрение процесса, можно убедиться, что на выходах ПЭ, соответствующих верхней границе систолического массива, периодически через три такта выдаются элементы матрицы D , при этом на каждом выходе появляются элементы одной и той же диагонали. Примерно через 3n тактов будет закончено вычисление всей матрицы D . При этом загруженность каждой систолической ячейки асимптотически равна 1/3 .

· «Много потоков команд - много потоков данных» (MIMD - "Multiple Instruction - Multiple Data")

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

Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования. Начнем с самых простых вещей. У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

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

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

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

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

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

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

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

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

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

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

Мультипрограммирование - параллельное выполнение нескольких программ. Мультипрограммирование позволяет уменьшить общее время их выполнения.

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

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

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

Для аппаратуры характерен экспоненциальный рост, что нашло отражение в известном эмпирическом законе Мура, - экспоненциально росли все важнейшие характеристики - объем памяти на всех уровнях, уменьшение времени доступа к памяти, быстродействие процессоров. Согласно закону Мура (Гордон Мур - один из основателей фирмы Intel) каждые полтора года значения характеристик увеличивались вдвое. Росло и число процессоров, включаемых в состав компьютера. Изменялась и архитектура компьютера . Эти изменения во многом были шагами в сторону распараллеливания вычислений. Вот лишь некоторые изменения в архитектуре процессоров, связанные непосредственно с процессом распараллеливания:

• Конвейерная обработка команд. Процесс выполнения потока команд процессором уже не рассматривался как последовательное выполнение команды за командой. Обработка потока команд выполнялась на конвейере, так что сразу несколько команд готовились к выполнению. При конвейерной обработке команды, не связанные между собой по данным, могли выполняться одновременно, что является уже настоящим параллелизмом.
• "Длинные команды". Архитектура некоторых компьютеров включала несколько процессоров, позволяющих выполнять логические и арифметические операции над целыми числами, несколько процессоров, выполняющих операции над числами с плавающей точкой. Длинная команда позволяла указать в одной команде действия, которые должен выполнить каждый из существующих процессоров. Опять таки, это позволяло реализовать параллелизм на аппаратном уровне.
• Векторные и матричные процессоры. В набор команд таких процессоров включаются базисные операции над векторами и матрицами. Одной командой, например, можно сложить две матрицы. Такая команда фактически реализует параллельные вычисления. Приложения, где эти операции составляют основу обработки данных, широко распространены. Реализуемая аппаратно параллельная обработка данных позволяет существенно повысить эффективность работы приложений этого класса.
• Графические процессоры. Еще одним важным видом приложений, где на аппаратном уровне происходит параллельное выполнение, являются приложения, интенсивно работающие с графическими изображениями. Эту обработку осуществляют графические процессоры. Графическое изображение можно рассматривать как набор точек. Обработка изображения зачастую сводится к выполнению одной и той же операции над всеми точками. Распараллеливание по данным легко реализуется в такой ситуации. Поэтому графические процессоры давно уже стали многоядерными, что позволяет распараллелить обработку и эффективно обрабатывать изображение.
• Суперкомпьютеры. К суперкомпьютерам относят компьютеры с максимальными характеристиками производительности на данный момент. В их состав входят сотни тысяч процессоров. Эффективное использование суперкомпьютеров предполагает самое широкое распараллеливание вычислений.

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

Классификация компьютеров

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

• SISD (Single Instruction stream - Single Data stream) - одиночный поток команд - одиночный поток данных. К этому классу относятся обычные "последовательные" компьютеры с фон-Неймановской архитектурой, когда команды программы выполняются последовательно, обрабатывая очередной элемент данных.
• SIMD (Single Instruction stream - Multiple Data stream) - одиночный поток команд - множественный поток данных. К этому типу относятся компьютеры с векторными и матричными процессорами.
• MISD (Multiple Instruction stream - Single Data stream) - множественный поток команд - одиночный поток данных. К этому типу можно отнести компьютеры с конвейерным типом обработки данных. Однако, многие полагают, что такие компьютеры следует относить к первому типу, а компьютеры класса MISD пока не созданы.
• MIMD (Multiple Instruction stream - Multiple Data stream) - множественный поток команд - множественный поток данных. Класс MIMD чрезвычайно широк и в настоящее время в него попадают многие компьютеры достаточно разной архитектуры. Поэтому предлагаются другие классификации, позволяющие более точно классифицировать компьютеры, входящие в класс MIMD.

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

• Мультипроцессорные вычислительные комплексы - это компьютеры, обладающие множеством процессоров, работающих на общей памяти. В этот класс входит большинство продаваемых сегодня на рынке многоядерных компьютеров.
• Мультикомпьютерные вычислительные комплексы - представляют множество компьютеров, соединенных высокоскоростными линиями связи. Каждый компьютер обладает собственной памятью и обменивается сообщениями с другими компьютерами системы для передачи данных. В этот класс входят кластеры. Под кластером понимается вычислительный комплекс, рассматриваемый как единое целое, с некоторым выделенным компьютером, играющим роль сервера. Поскольку компьютеры, входящие в состав кластера, могут быть обычными компьютерами, то кластеры относительно недороги. Большинство входящих в Top 500 суперкомпьютеров являются кластерами.
• Гибридные вычислительные комплексы - состоят из множества узлов, каждый из которых может быть мультикомпьютером, мультипроцессором, графическим или векторным процессором. Такие комплексы, как правило, являются суперкомпьютерами.

Параллельные вычислительные процессы и системы (Лекция 13)

Виды параллелизма

Параллельная обработка данных имеет две разновидности: конвейерность и собственно параллельность.

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

Конвейерная обработка. Что необходимо для сложения двух вещественных чисел, представленных в форме с плавающей запятой? Целое множество мелких операций таких, как сравнение порядков, выравнивание порядков, сложение мантисс, нормализация и т.п. Процессоры первых компьютеров выполняли все эти "микрооперации" для каждой пары аргументов последовательно одна за одной до тех пор, пока не доходили до окончательного результата, и лишь после этого переходили к обработке следующей пары слагаемых. Идея конвейерной обработки заключается в выделении отдельных этапов выполнения общей операции, причем каждый этап, выполнив свою работу, передавал бы результат следующему, одновременно принимая новую порцию входных данных. Получается очевидный выигрыш в скорости обработки за счет совмещения прежде разнесенных во времени операций. Предположим, что в операции можно выделить пять микроопераций, каждая из которых выполняется за одну единицу времени. Если есть одно неделимое последовательное устройство, то 100 пар аргументов оно обработает за 500 единиц. Если каждую микрооперацию выделить в отдельный этап (или иначе говорят– ступень) конвейерного устройства, то на пятой единице времени на разной стадии обработки такого устройства будут находится первые пять пар аргументов, а весь набор из ста пар будет обработан за 5 + 99 = 104 единицы времени – ускорение по сравнению с последовательным устройством почти в пять раз (по числу ступеней конвейера).

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

Реализация параллельных систем

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

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

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

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

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

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

Другие модели машин. Рассмотрим важнейшие компьютерные архитектуры. Мультикомпьютер очень похож на то, что часто называют компьютером с распределенной памятью MIMD (Multiple Instruction Multiple Data ). MIMD означает, что каждый процессор может обрабатывать отдельный поток инструкций над его собственными локальными данными. Распределенная память означает, что память распределена между процессорами. Принципиальным отличием MIMD компьютера от мультикомпьютера – это то, что стоимость доставки сообщения между двумя узлами не зависит от местоположения узла и сетевого трафика. Основные представители этого класса: IBM SP, Intel Paragon , Thinking Machines CM 5, Cray T 3D , Meiko CS -2, и CUBE .

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

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

Более специализированный класс параллельных компьютеров – это SIMD (Single Instruction Miltiple Data) компьютеры. В SIMD машинах все процессоры оперируют с одним и тем же потоком инструкций над различными порциями данных. Этот подход может уменьшить сложность программного и аппаратного обеспечения, но это имеет смысл только для специализированных проблем, характеризуемых высокой степенью закономерности, например обработка изображений и определенные виды цифрового моделирования. Алгоритмы, применимые на мультикомпьютерах, не могут в общих чертах эффективно выполняться в SIMD компьютерах.

Нейровычислительные системы.

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

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

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

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

· аппаратная реализация нейронных сетей.

Несмотря на то, что наибольшего эффекта при реализации нейросетевых алгоритмов удается добиться лишь с использованием нейрокомпьютеров третьего направления, их широкое применение ограничивается высокой. Например, нейрокомпьютер Synaps1 – один из представителей нейрокомпьютеров третьего направления, имеет мультипроцессорную архитектуру, оригинальное построение подсистемы памяти, а для выполнения вычислительных операций использует сигнальные процессоры и специальные сигнальные матричные процессоры МА16. За счет этого производительность нейрокомпьютера составила порядка несколько миллиардов умножений и сложений в секунду. Программное обеспечение данной системы включает в себя ОС Synaps1 с библиотекой нейроалгоритмов, а также ППО: базовую библиотеку НС, компилятор языка программирования нейроалгоритмов (nAPL) (набор библиотечных функций для С++) и т.п. Прикладные исследования показали, что использование нейрокомпьютеров третьего направления позволяет повысить производительность обычных вычислительных систем как минимум на три порядка и моделировать НС с миллионами соединений. Так, например, Synaps1 позволяет моделировать нейросеть с 64 миллионами синапсов с использованием различных активационных функций.

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

Сложности использования параллельных систем

Гигантская производительность параллельных компьютеров и супер-ЭВМ с лихвой компенсируется сложностями их использования.

У вас есть программа и доступ, скажем, к 256-процессорному компьютеру. Что вы ожидаете? Да ясно что: вы вполне законно ожидаете, что программа будет выполняться в 256 раз быстрее, чем на одном процессоре. А вот как раз этого, скорее всего, и не будет.

Закон Амдала. Предположим, что в программе доля операций, которые нужно выполнять последовательно, равна f, где 0<=f <=1 (при этом доля понимается не по статическому числу строк кода, а по числу операций в процессе выполнения). Крайние случаи в значениях f соответствуют полностью параллельным (f = 0) и полностью последовательным (f = 1) программам. Тогда для того, чтобы оценить, какое ускорение S может быть получено на компьютере из "p" процессоров при данном значении f, можно воспользоваться законом Амдала: если 9/10 программы исполняется параллельно, а 1/10 по-прежнему последовательно, то ускорения более, чем в 10 раз получить в принципе невозможно вне зависимости от качества реализации параллельной части кода и числа используемых процессоров (10 получается только в том случае, когда время исполнения параллельной части равно 0).

Следствие закона Амдала. Для того, чтобы ускорить выполнение программы в q раз, необходимо ускорить не менее, чем в q раз не менее, чем (1-1/q ) -ю часть программы. Следовательно, если есть желание ускорить программу в 100 раз по сравнению с ее последовательным вариантом, то необходимо получить не меньшее ускорение не менее, чем для 99.99% кода!

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

Программирование параллельных систем

Модель машины фон Неймана предполагает, что процессор выполняет последовательность инструкций. Инструкции могут определять в дополнение к различным арифметическим операциям адреса данных, которые надо прочитать/записать в памяти, и/или адрес следующей инструкции, которую надо выполнить. Пока возможно только программировать компьютер с точки зрения этой основной модели, этот метод для большинства целей недопустимо сложен из-за того, что мы должны следить за миллионами позиций памяти и организовать выполнение тысяч машинных инструкций. Следовательно, прикладывается модульная техника разработки, посредством которой сложные программы создаются из простых компонент, и компоненты структуры с точки зрения абстракций более высокого уровня (такие, как структуры данных, итерационные циклы и процедуры). Абстракции (например, процедуры) делают эксплуатацию модульности легче, допуская объекты, которыми должны управлять без беспокойства для их внутренней структуры. Так сделаны высокоуровневые языки, как, например, Fortran, C, Ada и Java , которые допускают разработку, выраженную с точки зрения этих абстракций, которые переводятся автоматически в выполняемый код. Параллельное программирование вводит дополнительные источники сложности: если мы должны запрограммировать на самом низком уровне, нам нужно не только увеличить количество выполняемых инструкций, но также управлять выполнением тысяч процессоров и координированием миллионов межпроцессорных взаимодействий. Следовательно, абстракция и модульность по крайней мере так же важны, как и в последовательном программировании. Фактически, мы выделим модульность как четвертое фундаментальное требование для параллельного программного обеспечения, дополнительно к параллелизму, масштабируемости, и локальности.

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

1.Параллельное вычисление состоит из одной или более задач. Задачи выполняются параллельно. Количество задач может меняться во время выполнения программы.

2.Задача изолирует последовательную программу и локальную память. Вдобавок набор вводов и выводов определяет свой интерфейс в своей среде.

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

4.Операция отправления сообщения – асинхронная, она завершается немедленно. Операция получения – синхронная, она вызывает выполнение задачи, блокируя процесс, пока сообщение не будет получено.

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

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

Абстракция задач требует свойство локальности: данные, содержащиеся в локальной памяти задачи – «закрытые»; другие данные – «удаленные». Канальная абстракция обеспечивает механизм для указания, вычисление каких данных из одной задачи требуется для начала работы другой задачи. (Это охарактеризовано зависимостью данных). Модель задач и каналов обладает и некоторыми другими свойствами:

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

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

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

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