Студенты, аспиранты, молодые ученые, использующие базу знаний в своей учебе и работе, будут вам очень благодарны.
Размещено на http://www.allbest.ru/
Размещено на http://www.allbest.ru/
Большое количество параллельных вычислений связано с трёхмерными играми. Параллельные векторные вычисления на универсальных устройствах с многоядерными процессорами используются в 3D-графике, достигая высокой пиковой производительности. Универсальным процессорам это не под силу. Максимальная скорость достигается только в ряде удобных задач, имея некоторые ограничения. Но всё равно такие устройства широко применяются в сферах, где изначально не предназначались. Например, процессор Cell, разработки альянса Sony-Toshiba-IBM в игровой приставке Sony PlayStation 3, или, современные видеокарты от компаний NVIDIA и AMD.
Ещё несколько лет назад начали появляться технологии неграфических расчётов общего назначения GPGPU для 3D видеоускорителей. Современные видеочипы имеют сотни математических исполнительных блоков, такая мощь может помочь для значительного ускорения множества вычислительно интенсивных приложений. Нынешние поколения GPU имеют гибкую архитектуру, которая вместе с программно-аппаратными архитектурами и высокоуровневыми языками даёт возможность делать их намного более доступными.
Появление достаточно быстрых и гибких шейдерных программ заинтересовало разработчиков создать GPGPU, которые способны выполнять современные видеочипы. Разработчики захотели на GPU рассчитывать не только изображения в игровых и 3D приложениях, но и применять в других областях параллельных вычислений. Для этого использовали API графических библиотек OpenGL и Direct3D. Данные в видеочип передавались в качестве текстур, расчётные программы помещались в виде шейдеров. Главным недостатком такого способа является значительная сложность программирования, низкий обмен данными между GPU и CPU, и некоторые другие ограничения.
Ведущие производители видеочипов NVIDIA и AMD представили платформы для параллельных вычислений - CUDA и CTM, соответственно. В видеокартах появилась аппаратная поддержка прямого доступа к вычислительным ресурсам. CUDA является расширением языка программирования С. CTM более похож на виртуальную машину, которая выполняет только ассемблерный код. Обе платформы убрали ограничениz предыдущих версий GPGPU, которые использовали традиционный графический конвейер, ну и конечно графические библиотеки Direct3D и Open GL.
OpenGL является более портируемой, а также универсальной из-за своей открытости кода. Но она не позволят использовать тот же код на чипах разных производителе. У таких методов много недостатков, они не удобные, и обладают малой гибкостью. А также они не позволяют использовать специфические возможности некоторых видеокарт, например, быстрая общая память.
Именно это постигнуло компанию NVIDIA выпустить платформу CUDA -- C-подобный язык программирования, наделённый своим компилятором, а также имеющий в наборе библиотеками для вычислений на GPU. Написание хорошего кода для видеочипов очень не простое занятие, но CUDA даёт больше контроля над аппаратными средствами видеокарты. CUDA появилась с видеокарт серии 8. Появилась CUDA версии 2.0, которая поддерживает расчёты с двойной точность в 32- и 64- битных ОС Windows, Linux, MacOS X.
Специальные векторные возможности (инструкции SSE) для 4-х компонентных (одинарная точность с плавающей точкой) и 2-х компонентных (двойная точность) векторов появились в универсальных процессорах из-за возникновения высоких требований приложений, работающие с графикой. Поэтому применение GPU является более выгодным, т.к. они заточены изначально под такие задачи.
Основные различия между архитектурами (GPU и CPU): ядра CPU исполняют один поток последовательных инструкций с максимальной производительностью, GPU исполняет большое число параллельно выполняемых потоков инструкций. Универсальные процессоры нацелены на достижение высокой производительности одного потока команд, обрабатывающие числа с плавающей точкой и без. Доступ к памяти случайный.
Другое отличие CPU от GPU: принцип доступа к памяти. В GPU Он связный и предсказуемы, т.к. если считались текстуры, значит через некоторое время придёт очередь соседних текстур. Поэтому организация памяти у видеокарты и центрального процессора разные. И видеочипу по этой причине не надо кэш-память большого размера, а для текстур требуются лишь около 128-256 кБ.
В CPU большое кол-во транзисторов уходит на буферы команд, аппаратное предсказание ветвления, огромные объёмы кэш-памяти. Все эти блоки нужны для ускорения немногочисленных потоков команд. В GPU транзисторы идут на массивы исполнительных блоков, разделяемую память малого объёма, управляющие потоками блоки, контроллеры памяти. Всё это не ускоряет выполнение отдельных потоков, но позволяет обрабатывать их в огромном количестве одновременно.
Кэширование. CPU использует кэш для уменьшения задержек доступа к памяти, следствие чего, происходит увеличение производительности. GPU использует кэш для увеличения пропускной способности. CPU снижает задержки доступа к памяти за счёт большого кэша и предсказания ветвлений кода. Эти аппаратные части являются большими ни чипе, следовательно, они потребляют много энергии. GPU решают проблему задержки доступа к памяти другим способом: исполнение тысяч потоков одновременно. Когда один поток ожидает данные, другой поток выполняет вычисления без ожидания и задержек.
BrookGPU. Известный компилятор языка программирования Brook. Является потоковым. Был специально разработан для вычислений на GPU. Разработчики использовали API: Direct3D или OpenGL. Это существенной ограничивало применения GPU, т.к. шейдеры и текстуры применялись в 3D графике, а специалисты по параллельному программированию ничего знать не обязаны. Они используют тока потоки и ядра. Brook смог немного помочь в этой задачи. Расширения к языку С помогли скрыть от программистов трёхмерный API, и предоставить видеочип в качестве параллельного сопроцессора. Компилятор компилировал код и привязывал к библиотеке DirectX, OpenGL или x86.
· Флуоресцентная микроскопия - в 12 раз;
· Молекулярная динамика - в 8-16 раз;
· Электростатика (прямое и многоуровневое суммирование Кулона) - в 40-120 раз и 7 раз.
ядро процессор графический
Заключение
В реферате удалось рассмотреть параллельные вычисления на многоядерных процессорах, а также технологиях CUDA и CTM. Были рассмотрены разница между CPU и GPU, какие были сложности применения видеокарт в параллельных вычислениях без технологии CUDA, рассмотрены области применения.
В реферате не было рассмотрело применение параллельных вычислений в центральных процессорах с интегрированным видеоядром. Это процессоры фирмы AMD серии А (AMD A10, AMD A8, AMD A6, AMD A4) и процессоры фирмы Intel серии i3/i5/i7 со встроенным видеоядром HD Graphics.
Список использованной литературы
1. Сайт ixbt.com, владелец Byrds Research and Publishing, Ltd
2. Сайт wikipedia.org, владелец Фонд Викимедиа
3. Сайт nvidia.ru, владелец NVIDIA corporation
Размещено на Allbest.ru
...Пакетный метод как основной способ выполнения коммуникационных операций, его содержание и предъявляемые требования. Оценка трудоемкости операции передачи данных между двумя узлами кластера. Этапы разработки параллельных алгоритмов (распараллеливания).
презентация , добавлен 10.02.2014
Знакомство с историей развития многопроцессорных комплексов и параллельных вычислений. Персональные компьютеры как распространенные однопроцессорные системы на платформе Intel или AMD, работающие под управлением однопользовательских операционных систем.
презентация , добавлен 22.02.2016
Классификация параллельных вычислительных систем. Существенные понятия и компоненты параллельных компьютеров, их компоненты. Особенности классификаций Хендера, Хокни, Флинна, Шора. Системы с разделяемой и локальной памятью. Способы разделения памяти.
курсовая работа , добавлен 18.07.2012
Математическая основа параллельных вычислений. Свойства Parallel Computing Toolbox. Разработка параллельных приложений в Matlab. Примеры программирования параллельных задач. Вычисление определенного интеграла. Последовательное и параллельное перемножение.
курсовая работа , добавлен 15.12.2010
Развитие концепций и возможностей ОС. Параллельные компьютерные системы и особенности их ОС. Симметричные и асимметричные мультипроцессорные системы. Виды серверов в клиент-серверных системах. ОС для облачных вычислений. Кластерные вычислительные системы.
лекция , добавлен 24.01.2014
Технология разработки параллельных программ для многопроцессорных вычислительных систем с общей памятью. Синтаксис, семантика и структура модели OpenMP: директивы, процедуры и переменные окружения. Распараллеливание по данным и операциям, синхронизация.
презентация , добавлен 10.02.2014
Параллельные вычислительные системы, их общая характеристика и функциональные особенности, оценка возможностей, внутренняя структура и взаимосвязь элементов, типы: одно- и многопроцессорные. Параллельная форма алгоритма, его представление и реализация.
контрольная работа , добавлен 02.06.2014
Достоинства многопроцессорных систем. Создание программы, реализующей работу мультипроцессорной системы с общей памятью по обработке различного количества заявок, а также различного количества процессоров. Модели вычислений на векторных и матричных ЭВМ.
курсовая работа , добавлен 21.06.2013
Абстрактные модели и способы параллельной обработки данных, допустимая погрешность вычислений. Понятие параллельного процесса, их синхронизация и гранулы распараллеливания, определение закона Амдаля. Архитектура многопроцессорных вычислительных систем.
дипломная работа , добавлен 09.09.2010
Однопроцессорные вычислительные системы не справляются с решением военно-прикладных задач в реальном времени, поэтому для повышения производительности вычислительных систем военного назначения используются многопроцессорные вычислительные системы (МВС).
Существуют различные способы реализации параллельных вычислений. Например, каждый вычислительный процесс может быть реализован в виде процесса операционной системы , либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса ОС. Параллельные программы могут физически исполняться либо последовательно на единственном процессоре - перемежая по очереди шаги выполнения каждого вычислительного процесса, либо параллельно - выделяя каждому вычислительному процессу один или несколько процессоров (находящихся рядом или распределённых в компьютерную сеть).
Основная сложность при проектировании параллельных программ - обеспечить правильную последовательность взаимодействий между различными вычислительными процессами, а также координацию ресурсов, разделяемых между процессами.
В некоторых параллельных системах программирования передача данных между компонентами скрыта от программиста (например, с помощью механизма обещаний), тогда как в других она должна указываться явно. Явные взаимодействия могут быть разделены на два типа:
Параллельные системы, основанные на обмене сообщениями, зачастую более просты для понимания, чем системы с разделяемой памятью, и обычно рассматриваются как более совершенный метод параллельного программирования. Существует большой выбор математических теорий для изучения и анализа систем с передачей сообщений, включая модель акторов и различные виды исчислений процессов . Обмен сообщениями может быть эффективно реализован на симметричных мультипроцессорах как с разделяемой когерентной памятью, так и без неё.
У параллелизма с распределенной памятью и с передачей сообщений разные характеристики производительности. Обычно (но не всегда), накладные расходы памяти на процесс и времени на переключение задач у систем с передачей сообщений ниже, однако передача самих сообщений более накладна, чем вызовы процедур. Эти различия часто перекрываются другими факторами, влияющими на производительность.
Разумеется в такой системе можно также использовать и исключительно метод передачи сообщений, то есть запустить на каждом процессоре каждого узла отдельный процесс. В этом случае количество процессов (и потоков) будет равно количеству процессоров на всех узлах. Этот способ проще (в параллельной программе надо только увеличить количество процессов), но является менее эффективным, так как процессоры одного и того же узла будут обмениваться друг с другом сообщениями, словно они находятся на разных машинах .
|
||||||||||||||||||||||||||||||||||||||||||
Так называемая партизанская война началась со вступления неприятеля в Смоленск.
Прежде чем партизанская война была официально принята нашим правительством, уже тысячи людей неприятельской армии – отсталые мародеры, фуражиры – были истреблены казаками и мужиками, побивавшими этих людей так же бессознательно, как бессознательно собаки загрызают забеглую бешеную собаку. Денис Давыдов своим русским чутьем первый понял значение той страшной дубины, которая, не спрашивая правил военного искусства, уничтожала французов, и ему принадлежит слава первого шага для узаконения этого приема войны.
24 го августа был учрежден первый партизанский отряд Давыдова, и вслед за его отрядом стали учреждаться другие. Чем дальше подвигалась кампания, тем более увеличивалось число этих отрядов.
Партизаны уничтожали Великую армию по частям. Они подбирали те отпадавшие листья, которые сами собою сыпались с иссохшего дерева – французского войска, и иногда трясли это дерево. В октябре, в то время как французы бежали к Смоленску, этих партий различных величин и характеров были сотни. Были партии, перенимавшие все приемы армии, с пехотой, артиллерией, штабами, с удобствами жизни; были одни казачьи, кавалерийские; были мелкие, сборные, пешие и конные, были мужицкие и помещичьи, никому не известные. Был дьячок начальником партии, взявший в месяц несколько сот пленных. Была старостиха Василиса, побившая сотни французов.
Последние числа октября было время самого разгара партизанской войны. Тот первый период этой войны, во время которого партизаны, сами удивляясь своей дерзости, боялись всякую минуту быть пойманными и окруженными французами и, не расседлывая и почти не слезая с лошадей, прятались по лесам, ожидая всякую минуту погони, – уже прошел. Теперь уже война эта определилась, всем стало ясно, что можно было предпринять с французами и чего нельзя было предпринимать. Теперь уже только те начальники отрядов, которые с штабами, по правилам ходили вдали от французов, считали еще многое невозможным. Мелкие же партизаны, давно уже начавшие свое дело и близко высматривавшие французов, считали возможным то, о чем не смели и думать начальники больших отрядов. Казаки же и мужики, лазившие между французами, считали, что теперь уже все было возможно.
22 го октября Денисов, бывший одним из партизанов, находился с своей партией в самом разгаре партизанской страсти. С утра он с своей партией был на ходу. Он целый день по лесам, примыкавшим к большой дороге, следил за большим французским транспортом кавалерийских вещей и русских пленных, отделившимся от других войск и под сильным прикрытием, как это было известно от лазутчиков и пленных, направлявшимся к Смоленску. Про этот транспорт было известно не только Денисову и Долохову (тоже партизану с небольшой партией), ходившему близко от Денисова, но и начальникам больших отрядов с штабами: все знали про этот транспорт и, как говорил Денисов, точили на него зубы. Двое из этих больших отрядных начальников – один поляк, другой немец – почти в одно и то же время прислали Денисову приглашение присоединиться каждый к своему отряду, с тем чтобы напасть на транспорт.
– Нет, бг"ат, я сам с усам, – сказал Денисов, прочтя эти бумаги, и написал немцу, что, несмотря на душевное желание, которое он имел служить под начальством столь доблестного и знаменитого генерала, он должен лишить себя этого счастья, потому что уже поступил под начальство генерала поляка. Генералу же поляку он написал то же самое, уведомляя его, что он уже поступил под начальство немца.
Распорядившись таким образом, Денисов намеревался, без донесения о том высшим начальникам, вместе с Долоховым атаковать и взять этот транспорт своими небольшими силами. Транспорт шел 22 октября от деревни Микулиной к деревне Шамшевой. С левой стороны дороги от Микулина к Шамшеву шли большие леса, местами подходившие к самой дороге, местами отдалявшиеся от дороги на версту и больше. По этим то лесам целый день, то углубляясь в середину их, то выезжая на опушку, ехал с партией Денисов, не выпуская из виду двигавшихся французов. С утра, недалеко от Микулина, там, где лес близко подходил к дороге, казаки из партии Денисова захватили две ставшие в грязи французские фуры с кавалерийскими седлами и увезли их в лес. С тех пор и до самого вечера партия, не нападая, следила за движением французов. Надо было, не испугав их, дать спокойно дойти до Шамшева и тогда, соединившись с Долоховым, который должен был к вечеру приехать на совещание к караулке в лесу (в версте от Шамшева), на рассвете пасть с двух сторон как снег на голову и побить и забрать всех разом.
Позади, в двух верстах от Микулина, там, где лес подходил к самой дороге, было оставлено шесть казаков, которые должны были донести сейчас же, как только покажутся новые колонны французов.
Впереди Шамшева точно так же Долохов должен был исследовать дорогу, чтобы знать, на каком расстоянии есть еще другие французские войска. При транспорте предполагалось тысяча пятьсот человек. У Денисова было двести человек, у Долохова могло быть столько же. Но превосходство числа не останавливало Денисова. Одно только, что еще нужно было знать ему, это то, какие именно были эти войска; и для этой цели Денисову нужно было взять языка (то есть человека из неприятельской колонны). В утреннее нападение на фуры дело сделалось с такою поспешностью, что бывших при фурах французов всех перебили и захватили живым только мальчишку барабанщика, который был отсталый и ничего не мог сказать положительно о том, какие были войска в колонне.
Нападать другой раз Денисов считал опасным, чтобы не встревожить всю колонну, и потому он послал вперед в Шамшево бывшего при его партии мужика Тихона Щербатого – захватить, ежели можно, хоть одного из бывших там французских передовых квартиргеров.
Параллельные вычисления - способ организации компьютерных вычислений, при котором программы разрабатываются как набор взаимодействующих вычислительных процессов, работающих одновременно.
Существуют различные способы реализации параллельных вычислений: каждый вычислительный процесс может быть реализован в виде процесса операционной системы, либо же вычислительные процессы могут представлять собой набор потоков выполнения внутри одного процесса. Поток (или правильнее поток выполнения) – наименьшая единица обработки, исполнение которой может быть назначено ядром операционной системы. Несколько потоков выполнения могут существовать в рамках одного и того же процесса и совместно использовать ресурсы, такие как память, тогда как процессы не разделяют этих ресурсов. Параллельные программы могут физически исполняться либо последовательно на единственном процессоре - перемежая по очереди шаги выполнения каждого вычислительного процесса, либо параллельно - выделяя каждому вычислительному процессу один или несколько процессоров (находящихся рядом или распределённых в компьютерную сеть).
Основная сложность при проектировании параллельных программ - обеспечить правильную последовательность взаимодействий между различными вычислительными процессами, а также разделение таких ресурсов, как оперативная память или периферийные устройства.
В некоторых параллельных системах программирования передача данных между компонентами скрыта от программиста, тогда как в других она должна указываться явно. Явные взаимодействия могут быть разделены на два типа:
1. Взаимодействие через разделяемую память (например, в Java или C#). Данный вид параллельного программирования обычно требует какой-то формы захвата управления для координации потоков между собой.
2. Взаимодействие с помощью передачи сообщений. Обмен сообщениями может происходить асинхронно, либо с использованием метода «рандеву», при котором отправитель блокирован до тех пор, пока его сообщение не будет доставлено. Асинхронная передача сообщений может быть надёжной (с гарантией доставки) либо ненадёжной. Параллельные системы, основанные на обмене сообщениями, зачастую более просты для понимания, чем системы с разделяемой памятью, и обычно рассматриваются как более совершенный метод параллельного программирования. Обмен сообщениями может быть эффективно реализован на симметричных мультипроцессорах как с разделяемой когерентной памятью, так и без неё.
Существует довольно много разных технологий параллельного программирования. Причем эти технологии отличаются не столько языками программирования, сколько архитектурными подходами к построению параллельных систем. Например, какие-то технологии предполагают построение параллельных решений на основе нескольких компьютеров (как одного, так и разных типов), другие же предполагают именно работу на одной машине с несколькими процессорными ядрами. В настоящее время основными программные инструменты создания параллельных программ являются:
1. OpenMP используется в параллельных системах с общей памятью (например, современные компьютеры с многоядерными процессорами);
2. MPI (Message Passing Interface) является стандартом систем передачи сообщений между параллельно исполняемыми процессами, используется при разработке программ для суперкомпьютеров;
3. POSIX Threads является стандартом реализации потоков выполнения;
4. Операционная система Windows имеет встроенную поддержку многопоточных приложений для C++ на уровне API;
5. PVM (Parallel Virtual Machine) позволяет объединять разнородные связанные сетью компьютеры в общий вычислительный ресурс.
Системы на базе нескольких компьютеров относят к классу систем для распределенных вычислений. Подобные решения используются довольно давно. Наиболее яркий пример технологии распределенных вычислений - MPI (Message Passing Interface - интерфейс передачи сообщений). MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для огромнейшего числа компьютерных платформ. MPI предоставляет программисту единый механизм взаимодействия ветвей внутри параллельного приложения независимо от машинной архитектуры (однопроцессорные/многопроцессорные с общей/раздельной памятью), взаимного расположения ветвей (на одном процессоре или на разных).
Так как MPI предназначен в первую очередь для систем с раздельной памятью, то использование его для организации параллельного процесса в системе с общей памятью является крайне сложным нецелесообразным. Тем не менее, ничего не мешает делать MPI-решения для одной машины.
А вот системы параллельного программирования для работы на одной машине, начали развиваться относительно недавно. Конечно, это не принципиально новые идеи, но именно с приходом многоядерных систем на рынок персональных компьютеров, мобильных устройств, такие технологии как OpenMP получили значительное развитие.
Очень важно, чтобы технология параллельного программирования поддерживала возможность делать программу параллельной постепенно. Разумеется идеальную параллельную программу следует сразу писать параллельной, возможно на каком-нибудь функциональном языке, где вопрос распараллеливания вообще не стоит. Но на практике приходится, постепенно распараллеливать написанную последовательную с целью повышения быстродействия. В этом случае технология OpenMP будет очень удачным выбором. Она позволяет, выбрав в приложении наиболее нуждающиеся в параллелизации места, в первую очередь сделать параллельными именно их. Процесс разработки параллельной версии можно прерывать, выпускать промежуточные версии программы, возвращаться к нему по мере необходимости. Именно поэтому в частности технология OpenMP стала довольно популярной.
OpenMP (Open Multi-Processing) - это набор директив компилятора, библиотечных процедур и переменных окружения, которые предназначены для программирования многопоточных приложений на многопроцессорных системах с общей памятью.
Разработку спецификации OpenMP ведут несколько крупных производителей вычислительной техники и программного обеспечения, чья работа регулируется некоммерческой организацией, называемой OpenMP Architecture Review Board (ARB).
Первая версия появилась в 1997 году, предназначалась для языка Fortran. Для С/С++ версия разработана в 1998 году. В 2008 году вышла версия OpenMP 3.0. Интерфейс OpenMP стал одной из наиболее популярных технологий параллельного программирования. OpenMP успешно используется как при программировании суперкомпьютерных систем с большим количеством процессоров, так и в настольных пользовательских системах или, например, в Xbox 360.
OpenMP реализует параллельные вычисления с помощью многопоточности, в которой «главный» (master) поток создает набор подчиненных (slave) потоков и задача распределяется между ними. Предполагается, что потоки выполняются параллельно на машине с несколькими процессорами (количество процессоров не обязательно должно быть больше или равно количеству потоков).
Задачи, выполняемые потоками параллельно, также как и данные, требуемые для выполнения этих задач, описываются с помощью специальных директив препроцессора соответствующего языка - прагм. Например, участок кода на языке Fortran, который должен исполняться несколькими потоками, каждый из которых имеет свою копию переменной N, предваряется следующей директивой: !$OMP PARALLEL PRIVATE(N)
Количество создаваемых потоков может регулироваться как самой программой при помощи вызова библиотечных процедур, так и извне, при помощи переменных окружения.
Ключевыми элементами OpenMP являются
1. конструкции для создания потоков (директива parallel);
2. конструкции распределения работы между потоками (директивы DO/for и section);
3. конструкции для управления работой с данными (выражения shared и private для определения класса памяти переменных);
4. конструкции для синхронизации потоков (директивы critical, atomic и barrier);
5. процедуры библиотеки поддержки времени выполнения (например, omp_get_thread_num);
6. переменные окружения (например, OMP_NUM_THREADS).
В OpenMP используется модель параллельного выполнения «ветвление-слияние». Программа OpenMP начинается как единственный поток выполнения, называемый начальным потоком. Когда поток встречает параллельную конструкцию, он создает новую группу потоков, состоящую из себя и некоторого числа дополнительных потоков, и становится главным в новой группе. Все члены новой группы (включая главный) выполняют код внутри параллельной конструкции. В конце параллельной конструкции имеется неявный барьер. После параллельной конструкции выполнение пользовательского кода продолжает только главный поток. В параллельный регион могут быть вложены другие параллельные регионы, в которых каждый поток первоначального региона становится основным для своей группы потоков. Вложенные регионы могут в свою очередь включать регионы более глубокого уровня вложенности.
Число потоков в группе, выполняющихся параллельно, можно контролировать несколькими способами. Один из них - использование переменной окружения OMP_NUM_THREADS. Другой способ - вызов процедуры omp_set_num_threads(). Еще один способ - использование выражения num_threads в сочетании с директивой parallel.
В этой программе два массива (a и b) складываются параллельно десятью потоками.
#include
#include
int main(int argc, char *argv)
float a[N], b[N], c[N];
omp_set_dynamic(0); // запретить библиотеке openmp менять число потоков во время исполнения
omp_set_num_threads(10); // установить число потоков в 10
// инициализируем массивы
for (I = 0; I < N; i++)
// вычисляем сумму массивов
#pragma omp parallel shared(a, b, c) private(i)
for (I = 0; I < N; i++)
c[i] = a[i] + b[i];
printf (“%f\n”, c);
Эту программу можно скомпилировать, используя gcc-4.4 и более новые с флагом –fopenmp. Очевидно, если убрать подключение заголовочного файла omp.h, а также вызовы функции настроки OpenMP, программу возможно скомпилировать на любом компиляторе С как обычную последовательную программу.
OpenMP поддерживается многими современными компиляторами:
1. Компиляторы Sun Studio поддерживают официальную спецификацию - OpenMP 2.5 - с улучшенной производительностью под ОС Solaris; поддержка Linux запланирована на следующий релиз.
2. Visual C++ 2005 и выше поддерживает OpenMP в редакциях Professional и Team System.
3. GCC 4.2 поддерживает OpenMP, а некоторые дистрибутивы (такие как Fedora Core 5 gcc) включили поддержку в свои версии GCC 4.1.
4. Intel C++ Compiler, включая версию Intel Cluster OpenMP для программирования в системах с распределённой памятью.
Message Passing Interface (MPI, интерфейс передачи сообщений) - программный интерфейс (API) для передачи информации, который позволяет обмениваться сообщениями между процессами, выполняющими одну задачу. Разработан Уильямом Гроуппом, Эвином Ласком (англ.) и другими.
MPI является наиболее распространённым стандартом интерфейса обмена данными в параллельном программировании, существуют его реализации для большого числа компьютерных платформ. Используется при разработке программ для кластеров и суперкомпьютеров. Основным средством коммуникации между процессами в MPI является передача сообщений друг другу. Стандартизацией MPI занимается MPI Forum. В стандарте MPI описан интерфейс передачи сообщений, который должен поддерживаться как на платформе, так и в приложениях пользователя. В настоящее время существует большое количество бесплатных и коммерческих реализаций MPI. Существуют реализации для языков Фортран 77/90, Си и Си++.
В первую очередь MPI ориентирован на системы с распределенной памятью, то есть когда затраты на передачу данных велики, в то время как OpenMP ориентирован на системы с общей памятью (многоядерные с общим ЭШем). Обе технологии могут использоваться совместно, дабы оптимально использовать в кластере многоядерные системы.
Первая версия MPI разрабатывалась в 1993-1994 году, и MPI 1 вышла в 1994.
Большинство современных реализаций MPI поддерживают версию 1.1. Стандарт MPI версии 2.0 поддерживается большинством современных реализаций, однако некоторые функции могут быть реализованы не до конца.
передача и получение сообщений между отдельными процессами;
коллективные взаимодействия процессов;
взаимодействия в группах процессов;
реализация топологий процессов;
динамическое порождение процессов и управление процессами;
односторонние коммуникации (Get/Put);
параллельный ввод и вывод;
расширенные коллективные операции (процессы могут выполнять коллективные операции не только внутри одного коммуникатора, но и в рамках нескольких коммуникаторов).
Версия MPI 2.1 вышла в начале сентября 2008 года.
Базовым механизмом связи между MPI процессами является передача и приём сообщений. Сообщение несёт в себе передаваемые данные и информацию, позволяющую принимающей стороне осуществлять их выборочный приём:
1. отправитель - ранг (номер в группе) отправителя сообщения;
2. получатель - ранг получателя;
3. признак - может использоваться для разделения различных видов сообщений;
4. коммуникатор - код группы процессов.
Операции приёма и передачи могут быть блокирующимися и не блокирующимися. Для не блокирующихся операций определены функции проверки готовности и ожидания выполнения операции.
Другим способом связи является удалённый доступ к памяти (RMA), позволяющий читать и изменять область памяти удалённого процесса. Локальный процесс может переносить область памяти удалённого процесса (внутри указанного процессами окна) в свою память и обратно, а также комбинировать данные, передаваемые в удалённый процесс с имеющимися в его памяти данными (например, путём суммирования). Все операции удалённого доступа к памяти не блокирующиеся, однако, до и после их выполнения необходимо вызывать блокирующиеся функции синхронизации.
Ниже приведён пример программы вычисления числа π на языке C с использованием MPI:
// Подключение необходимых заголовков
#include
#include
// Подключение заголовочного файла MPI
#include «mpi.h»
// Функция для промежуточных вычислений
double f(double a)
return (4.0 / (1.0+ a*a));
// Главная функция программы
int main(int argc, char **argv)
// Объявление переменных
int done = 0, n, myid, numprocs, I;
double PI25DT = 3.141592653589793238462643;
double mypi, pi, h, sum, x;
double startwtime = 0.0, endwtime;
char processor_name;
// Инициализация подсистемы MPI
MPI_Init(&argc, &argv);
// Получить размер коммуникатора MPI_COMM_WORLD
// (общее число процессов в рамках задачи)
MPI_Comm_size(MPI_COMM_WORLD,&numprocs);
// Получить номер текущего процесса в рамках
// коммуникатора MPI_COMM_WORLD
MPI_Comm_rank(MPI_COMM_WORLD,&myid);
MPI_Get_processor_name(processor_name,&namelen);
// Вывод номера потока в общем пуле
fprintf(stdout, “Process %d of %d is on %s\n”, myid,numprocs,processor_name);
// количество интервалов
fprintf(stdout, “Enter the number of intervals: (0 quits) “);
if(scanf(“%d”,&n) != 1)
fprintf(stdout, “No number entered; quitting\n”);
MPI_Bcast(&n, 1, MPI_INT, 0, MPI_COMM_WORLD);
h = 1.0 / (double) n;
// Обсчитывание точки, закрепленной за процессом
for(I = myid + 1 ; (I <= n) ; I += numprocs)
x = h * ((double)I – 0.5);
// Сброс результатов со всех процессов и сложение
MPI_Reduce(&mypi, &pi, 1, MPI_DOUBLE, MPI_SUM, 0, MPI_COMM_WORLD);
// Если это главный процесс, вывод полученного результата
printf(“PI is approximately %.16f, Error is %.16f\n”, pi, fabs(pi – PI25DT));
endwtime = MPI_Wtime();
printf(“wall clock time = %f\n”, endwtime-startwtime);
// Освобождение подсистемы MPI
Наиболее распространенными реализациями MPI на сегодняшний день являются:
MPICH - самая распространённая бесплатная реализация, работает на UNIX-системах и Windows NT
LAM/MPI - ещё одна бесплатная реализация MPI. Поддерживает гетерогенные конфигурации, LAM (http://www.lam-mpi.org) поддерживает гетерогенные конфигурации, пакет Globus и удовлетворяет IMPI (Interoperable MPI).
Поддерживаются различные коммуникационные системы (в том числе Myrinet).
WMPI - реализация MPI для Windows
MPI/PRO for Windows NT - коммерческая реализация для Windows NT
Intel MPI - коммерческая реализация для Windows / Linux
Microsoft MPI входит в состав Compute Cluster Pack SDK. Основан на MPICH2, но включает дополнительные средства управления заданиями. Поддерживается спецификация MPI-2.
HP-MPI - коммерческая реализация от HP
SGI MPT - платная библиотека MPI от SGI
Mvapich - бесплатная реализация MPI для Infiniband
Open MPI - бесплатная реализация MPI, наследник LAM/MPI
Oracle HPC ClusterTools - бесплатная реализация для Solaris SPARC/x86 и Linux на основе Open MPI
MPJ - MPI for Java
POSIX Threads - стандарт POSIX реализации потоков выполнения, определяющий API для создания и управления ими.
Библиотеки, реализующие этот стандарт (и функции этого стандарта), обычно называются Pthreads (функции имеют приставку «pthread_»). Хотя наиболее известны варианты для Unix-подобных операционных систем, таких как Linux или Solaris, но существует и реализация для Microsoft Windows (Pthreads-w32)
Pthreads определяет набор типов и функций на языке программирования Си. Заголовочный файл - pthread.h.
Типы данных:
1. pthread_t – дескриптор потока;
2. pthread_attr_t – перечень атрибутов потока.
Функции управления потоками:
1. pthread_create() – создание потока;
2. pthread_exit() – завершение потока (должна вызываться функцией потока при завершении);
3. pthread_cancel() – отмена потока;
4. pthread_join() – заблокировать выполнение потока до прекращения другого потока, указанного в вызове функции;
5. pthread_detach() – освободить ресурсы занимаемые потоком (если поток выполняется, то освобождение ресурсов произойдёт после его завершения);
6. pthread_attr_init() – инициализировать структуру атрибутов потока;
7. pthread_attr_setdetachstate() – указать системе, что после завершения потока она может автоматически освободить ресурсы, занимаемые потоком;
8. pthread_attr_destroy() – освободить память от структуры атрибутов потока (уничтожить дескриптор).
Функции синхронизации потоков:
2. pthread_mutex_init(), pthread_mutex_destroy(), pthread_mutex_lock(), pthread_mutex_trylock(), pthread_mutex_unlock();
3. pthread_cond_init(), pthread_cond_signal(), pthread_cond_wait().
Пример использования потоков на языке C:
#include
#include
#include
#include
static void wait_thread(void)
time_t start_time = time(NULL);
while (time(NULL) == start_time)
/* do nothing except chew CPU slices for up to one second. */
static void *thread_func(void *vptr_args)
for (I = 0; I < 20; i++)
fputs(“ b\n”, stderr);
pthread_t thread;
if (pthread_create(&thread, NULL, thread_func, NULL) != 0)
return EXIT_FAILURE;
for (I = 0; I < 20; i++)
if (pthread_join(thread, NULL) != 0)
return EXIT_FAILURE;
return EXIT_SUCCESS;
Представленная программа используют два потока, печатающих в консоль сообщения, один, печатающий "a", второй - "b". Вывод сообщений смешивается в результате переключения выполнения между потоками или одновременном выполнении на мультипроцессорных системах.
Программа на C создает один новый поток для печати "b", а основной поток печатает "a". Основной поток (после печати "aaaaa….") ждёт завершения дочернего потока.
Контрольные вопросы
Многопроцессорность и многоядерность уже давно стали обыденностью среди пользователей, что не мешает программистам не в полной мере, а то и просто неправильно использовать заложенные в них возможности. Не обещаем, что после прочтения этой статьи ты станешь гуру параллельных вычислений в среде Win, но в некоторых вещах точно разберешься.
Близился закат эры 32-битных камней, и было очевидно, что надо повышать не только мощность, но и разрядность. Разработчики процессоров столкнулись с рядом проблем в увеличении тактовой частоты: невозможно рассеивать выделяемую кристаллом теплоту, нельзя дальше уменьшать размер транзисторов, однако главной проблемой стало то, что при увеличении тактовой частоты быстродействие программ не повышалось. Причиной этому явилась параллельная работа современных компьютерных систем, а один процессор, каким бы мощным бы он ни был, в каждый момент времени может выполнять только одну задачу. Для примера, у меня в системе Windows 7 в момент написания статьи выполняется 119 процессов. Хотя они далеко не все находятся в бэкграунде, им не всем нужна высокая мощность. На одном камне выполнение нескольких процессов/потоков может быть только конкурентным. То есть их работа чередуется: после того как определенный поток отработает свой квант времени, в течение которого он выполнил полезную нагрузку, его текущее состояние сохранится в памяти, а он будет выгружен из процессора и заменен следующим находящимся в очереди на выполнение потоком - произойдет переключение контекста, на что тратится драгоценное время. А пока идет обмен данными между процессором и оперативной памятью, из-за ограниченной пропускной способности системной шины микропроцессор нервно курит бамбук, в сторонке ожидая данные. На помощь могут прийти аппаратный и программный (например, из операционной системы) планировщики, чтобы подгружать данные в кеш. Однако кеш очень ограничен по объему, поэтому такое решение не может служить панацеей. Выходом стала параллельная обработка, при которой в реальном времени одновременно выполняются несколько процессов. А чтобы ее реализовать, потребовалось фундаментально перепроектировать и перестроить камень - совместить в одном корпусе два исполняющих кристалла и более.
При разработке параллельной программы стадия проектирования становится еще более важной, чем при разработке однопоточных приложений. И поскольку на самом деле параллельное программирование в узком кругу задач используется уже десятилетиями, были выявлены некоторые зарекомендовавшие себя концепции. Самое важное - посмотреть на разработку иначе, не последовательно, выделить единицу выполняемой работы, провести декомпозицию задачи. Имеется три способа: декомпозиция по заданиям, декомпозиция по данным, декомпозиция по информационным потокам. Первый способ декомпозиции самый простой: мы просто привязываем отдельную функцию к определенному потоку и запускаем его на выполнение. Параллельная обработка готова. Однако могут быть проблемы - конкуренция, если в исполняемой единице используются общие глобальные данные. Но об этом мы поговорим позже. Второй способ тоже достаточно понятный метод распараллеливания: например, большой массив данных обрабатывается несколькими потоками, каждый из которых работает над частью, ограниченной определенными пределами. Декомпозиция по информационным потокам служит для задач, когда работа одного потока зависит от результата выполнения другого. Например, во время чтения из файла поток - обработчик считанных данных не может начать работу, пока поток-читатель не считает определенный объем данных.
Прежде чем перейти к многоядерности, разработчики процессоров выяснили, что при выполнении одного потока процессорное ядро загружается не полностью (думаю, для этого не надо быть провидцем). И поскольку для выполнения второго программного потока используются не все ресурсы микропроцессора (так как аппаратное состояние - исполнительные устройства, кеш - может храниться в одном экземпляре), то в дублировании нуждается только область состояния программной архитектуры (логика прерываний). Эта технология получила название гиперпоточности (Hyper-Threading). Гиперпоточность - аппаратный механизм, в котором несколько независимых аппаратных потоков выполняются в одном такте на единственном суперскалярном процессорном ядре. С ее помощью один физический процессор представляется как два логических, то есть так его видит операционная система, потому что планирование и выполнение, по сути, осуществляется с расчетом на два ядра. Это происходит благодаря непрерывному потоку команд, выполняющихся на совместном оборудовании. Эта технология была добавлена к архитектуре NetBurst, реализованной в процессорах Pentium 4. Поэтому гиперпоточность была реализована еще в последних версиях Pentium 4, но мне в то время как-то не удалось ее застать. Зато сейчас я могу наблюдать ее в процессоре Atom, установленном в нетбуке. В этом камне, помимо гиперпоточности, реализована многоядерность (в количестве двух штук), поэтому в операционной системе я наблюдаю четыре камня. Но, например, в Core 2 Duo гиперпоточность отсутствует, равно как и в Core i5. С помощью гиперпоточности скорость исполнения оптимизированных для многопоточности программ удалось повысить на 30%. Подчеркну, что прирост производительности будет иметь место только в специально подготовленных приложениях.
Одновременно с гиперпоточностью вдобавок к суперскалярной архитектуре была создана новая архитектура EPIC, реализованная в процессорах Itanium, но эта тема уже не поместится в сегодняшней статье.
Затем были изобретены многоядерные процессоры, которые ныне используются повсеместно. Многоядерные процессоры поддерживают мультипроцессорную обработку на кристалле. В этой архитектуре два ядра или более реализуются в одном процессоре, устанавливаемом в один сокет. В зависимости от конструкции эти ядра могут совместно использовать большой кеш на том же кристалле. Многоядерные процессоры также требуют совместимого чипсета. Так как каждое ядро представляет собой самостоятельный исполняющий модуль, то многоядерные процессоры обеспечивают истинный параллелизм - выполнение каждого потока в обособленной среде. В случае присутствия нескольких исполняющих ядер должен быть способ обмена информацией между ними, без чего попросту невозможно создать параллельную систему, причем нужен специальный ресурс. Для этого был изобретен усовершенствованный программируемый контроллер прерываний (APIC). Он выполняет обмен информации между процессорами/ядрами, используя механизм межпроцессорного прерывания (Interprocessor Interrupt). Последний, в свою очередь, используется операционной системой для планирования/выполнения потоков.
Также на первый план выходит энергопотребление. И это касается не только различных мобильных платформ, питающихся от аккумуляторов, но также и серверных систем и десктопов. Первые x86-процессоры потребляли доли ватт, в то время как современные высокопроизводительные модели могут потреблять 130 и более ватт. Между тем многоядерные процессоры позволяют экономить энергию, так как рост производительности достигается за счет параллелизма, а не за счет увеличения тактовой частоты.
В параллельном выполнении кода огромную роль играют программные решения. На сцену выходят как системные программные продукты (операционные системы, компиляторы), так и приложения пользовательского уровня. С точки зрения прикладного программиста мы можем воспользоваться только вторым подмножеством. На самом деле этого вполне достаточно, если операционная система надежна. Дальнейшее повествование в большинстве своем относится к Windows NT 6.1, если не оговорено иное. Как тебе известно, Windows NT использует модель вытесняющей многопоточности. Когда запускается приложение, стартует процесс, в нем могут выполнять свою работу один или несколько потоков, все они разделяют общую память и общее адресное пространство. Поток же, в свою очередь, - это обособленная последовательность команд, выполняемая независимо. Существует три вида потоков:
Создание потока протекает в три этапа. Сначала происходит его описание с помощью поточного API, затем на стадии выполнения этот вызов обрабатывается как вызов ядра, в результате создается поток, потом он выполняется внутри своего процесса. Но в связи с тем, что в программе одновременно выполняется несколько действий, может возникнуть куча проблем. Их удобно классифицировать под четыре типа. Проблема синхронизации возникает, когда один поток ждет выполнения другого, который по каким-то причинам не может завершить выполнение. При проблеме взаимодействия один поток не может вовремя передать информацию другому, например из-за задержек. Когда один поток напрягается, а другой прохлаждается, возникает проблема балансировки. Если в момент переноса программы на более мощный компьютер ее быстродействие не повышается, то говорят о проблеме масштабируемости. Для решения всех этих проблем предназначены примитивы для работы в многопоточной среде. Давай кинем на них поверхностный взгляд.
Участки кода, которые могут быть одновременно использованы несколькими потоками и содержат общие переменные, называются критическими секциями. В них чтение-запись значений под действием двух и более потоков могут произойти асинхронно. Это состояние называется состоянием гонок. Поэтому в каждый временной промежуток внутри критической секции должен выполняться только один поток. Для обеспечения этого используются примитивы синхронизации - блокировки. Семафор - исторически самый первый механизм для синхронизации, разработанный Дейкстрой в 1968 году. Позволяет войти в критическую секцию определенному количеству потоков, при входе в нее потока уменьшает свое значение и увеличивает в момент его выхода. Обязательным условием является атомарное выполнение операций проверки значения семафора + увеличения значения, а так же проверки значения + уменьшения значения. Развитием семафора служит мьютекс, который является попросту двоичным семафором и поэтому в критической секции допускает выполнение только одного потока. Блокировки чтения-записи позволяют нескольким потокам читать значение общей переменной, находящейся в критической секции, но записывать только одному. Во время ожидания спин-блокировка не блокируется, а продолжает активный опрос заблокированного ресурса. Спин-блокировка - плохое решение проблемы синхронизации для одноядерного процессора, поскольку занимает все вычислительные ресурсы.
Похож на семафоры механизм условных переменных, тем не менее они, в отличие от семафоров (и мьютексов), не содержат реальных значений. Они следят за выполнением внешних условий.
В современных языках программирования присутствуют высокоуровневые механизмы, позволяющие упростить использование блокировок и условных переменных («мониторы»). Вместо того чтобы явно писать операции блокировки и разблокировки участка кода, разработчику достаточно объявить критическую секцию как синхронизируемую.
Для обмена информацией между процессами/потоками используются сообщения, подразделяемые на три группы: внутрипроцессные (для передачи информации между потоками одного процесса), межпроцессные (для передачи инфы между процессами - с зависимостью от потоков) и процесс - процесс (поточно независимая передача инфы между процессами).
В то же время при использовании блокировок для избегания гонок могут наступить мертвые (dead lock) и живые (live lock) блокировки. Мертвая блокировка имеет место, когда один поток заблокирован на ожидании определенного ресурса от другого потока, но тот не может дать его (например, ожидает результат от первого). Мертвая блокировка может произойти при выполнении четырех хорошо определенных условий (мы не будем разбирать эти условия в данной статье). Поэтому при написании многопоточного кода у программиста есть возможность избежать дидлока, но на практике это выглядит гораздо сложнее. Живая блокировка хуже мертвой тем, что в первом случае потоки заблокированы, а во втором они постоянно конфликтуют.
Существует насколько несовместимых между собой прикладных поточных программных интерфейсов. Все они в основном используют одинаковые примитивы, отличия лишь в зависимости от операционной системы. В следующих разделах мы рассмотрим способы работы в многопоточной среде и решения проблем параллельного кода с использованием этих интерфейсов.
После появления первой версии Windows NT многопоточное программирование в ней улучшалось от версии к версии, одновременно улучшался связанный с потоками API. Итак, когда стартует процесс посредством функции CreateProcess, он имеет один поток для выполнения команд. Поток состоит из двух объектов: объект ядра (через него система управляет потоком) и стек, в котором хранятся параметры, функции и переменные потока. Чтобы создать дополнительный поток, надо вызвать функцию CreateThread. В результате создается объект ядра - компактная структура данных, используемая системой для управления потоком. Этот объект, по сути, не является потоком. Также из адресного пространства родительского процесса для потока выделяется память. И поскольку все потоки одного процесса будут выполняться в его адресном пространстве, то они будут разделять его глобальные данные. Вернемся к функции CreateThread и рассмотрим ее параметры. Первый параметр - указатель на структуру PSECURITYATTRIBUTES, которая определяет атрибуты защиты и свойства наследования, для установки значений по умолчанию достаточно передать NULL. Второй параметр типа DW0RD определяет, какую часть адресного пространства поток может использовать под свой стек. Третий параметр PTHREAD START_ROUTIME pfnStartAddr - указатель на функцию, которую необходимо привязать к потоку и которую он будет выполнять. Эта функция должна иметь вид DWORD WINAPI ThreadFunc(PVOID pvParam), она может выполнять любые операции; когда она завершится, то возвратит управление, а счетчик пользователей объекта ядра потока будет уменьшен на 1, в случае, когда этот счетчик будет равен 0, данный объект будет уничтожен. Четвертый параметр функции CreateThread - указатель на структуру PVOID, содержащую параметр для инициализации выполняемой в потоке функции (см. описание третьего параметра). Пятый параметр (DWORD) определяет флаг, указывающий на активность потока после его создания. Последний, шестой параметр (PDWORD) - адрес переменной, куда будет помещен идентификатор потока, если передать NULL, тем самым мы сообщим, что он нам не нужен. В случае успеха функция возвращает дескриптор потока, с его помощью можно манипулировать потоком; при фейле функция возвращает 0.
Существуют четыре пути завершения потока, три из которых нежелательные: это завершение потока через вызов функции ExitThread, через вызов TerminateThread, при завершении родительского процесса без предварительного завершения потока. Лишь 1 путь – самозавершение потока, которое происходит при выполнении назначенных ему действий, является благоприятным. Потому что только в этом случае гарантируется освобождение всех ресурсов операционной системы, уничтожение всех объектов C/C++ с помощью их деструкторов.
Еще пара слов о создании потока. Функция CreateThread находится в Win32 API, при этом в библиотеке Visual C++ имеется ее эквивалент _beginthreadex, у которой почти тот же список параметров. Рекомендуется создавать потоки именно с ее помощью, поскольку она не только использует CreateThread, но и выполняет дополнительные операции. Кроме того, если поток был создан с помощью последней, то при уничтожении вызывается _endthreadex, которая очищает блок данных, занимаемый структурой, описывающей поток.
Потоки планируются на выполнение с учетом приоритета. Если бы все потоки имели равные приоритеты, то для выполнения каждого (в WinNT) выделялось бы по 20 мс. Но это не так. В WinNT имеется 31 (от нуля) поточный приоритет. При этом 31 - самый высокий, на нем могут выполняться только самые критичные приложения - драйверы устройств; 0, самый низкий, зарезервирован для выполнения потока обнуления страниц. Тем не менее разработчик не может явно указать номер приоритета для выполнения своего потока. Зато в Windows есть таблица приоритетов, где указаны символьные обозначения сгруппированных номеров приоритетов. При этом конечный номер формируется не только на основе этой таблицы, но и на значениях приоритета родительского процесса. Значения скрыты за символьными константами по той причине, что Microsoft оставляет за собой право их изменить и пользуется им от версии к версии своей операционки. При создании поток получает обычный (normal) уровень приоритета. Его можно изменить функцией SetThreadPriority, принимающей два параметра: HANDLE hThread - дескриптор изменяемого потока, int nPriority - уровень приоритета (из таблицы). С помощью функции GetThreadPriority можно получить текущий приоритет, передав в нее дескриптор нужного потока. Перед изменением приоритета потока его надо приостановить, это делается функцией SuspendThread. После изменения приоритета поток надо снова отдать планировщику для планирования выполнения функцией ResumeThread. Обе функции получают дескриптор потока, с которым работают. Все описанные операции кроме приостановки и возобновления применимы и к процессам. Они не могут быть приостановлены/возобновлены, поскольку не затрачивают процессорное время, поэтому не планируются.
В многопоточных приложениях надо везде по возможности использовать атомарные - неделимые операции, в выполнение которых не может встрять другой поток. Такие функции в Win32 API имеют префикс Interlocked, например, для инкремента переменной вместо i++ использовать InterlockedExchangeAdd(&i, 1). Помимо операций увеличения/уменьшения, еще есть операции для атомарного сравнения, но мы их оставим в качестве твоего домашнего задания.
Атомарные функции, однако, позволяют решить очень узкий круг задач. На помощь приходят критические секции. В Win32 есть функции для явной отметки такого куска кода, который будет выполняться атомарно. Сначала надо создать экземпляр структуры критической секции, затем в выполняемой в потоке функции написать операторы для входа и выхода в критическую секцию:
CRITICAL_SECTION g_cs; DWORD WINAPI ThreadRun(PVOID pvParam) { EnterCriticalSection(&g_cs); // Что-то вычисляем LeaveCriticalSection(&g_cs); return 0; }
Критические секции в Win32 не просто код, который может выполняться несколькими потоками, это целый механизм синхронизации данных. Критические секции должны быть как можно меньше, то есть включать как можно меньше вычислений.
Чтобы позволить читать значение переменной нескольким потокам, а изменять одному, можно применить структуру «тонкой блокировки» SRWLock. Первым делом надо инициализировать структуру вызовом InitializeSRWLock с передачей указателя на нее. Затем во время записи ограничиваем ресурс эксклюзивным доступом:
AcquireSRWLockExclusive(PSRWLOCK SRWLock); // Записываем значение ReleaseSRWLockExclusive(PSRWLOCK SRWLock);
С другой стороны, во время чтения осуществляем расшаренный доступ:
AcquireSRWLockShared(PSRWLOCK SRWLock); // Читаем значение ReleaseSRWLockShared(PSRWLOCK SRWLock);
Обрати внимание: все функции принимают проинициализированную структуру SRWLock в качестве параметра.
С помощью условных переменных удобно организовать зависимость «поставщик - потребитель» (см. декомпозицию по информационным потокам), то есть следующее событие должно произойти в зависимости от предыдущего. В этом механизме используются функции SleepConditionVariableCS и SleepConditionVariableSRW, служащие для блокировки критической секции или структуры «тонкой блокировки». Они принимают три и четыре параметра соответственно: указатель на условную переменную, ожидаемую потоком, указатель на критическую секцию либо SRWLock, применимую для синхронизации доступа. Следующий параметр - время (в миллисекундах) для ожидания потоком выполнения условия, если условие не будет выполнено, функция вернет False; последний параметр второй функции - вид блокировки. Чтобы пробудить заблокированные потоки, надо из другого потока вызвать функцию WakeConditionVariable или WakeAllConditionVariable. Если выполненная в результате вызова этих функций проверка подтвердит выполнение условия, передаваемого в качестве параметра данным функциям, поток будет пробужден.
В приведенном описании мы познакомились с общими определениями механизмов семафор и мьютекс. Сейчас посмотрим, как они реализованы в Win32. Создать семафор можно с помощью функции CreateSemaphore. Ей передаются такие параметры: указатель на структуру PSECURITY_ATTRIBUTES, содержащую параметры безопасности; максимальное число ресурсов, обрабатываемых приложением; количество этих ресурсов, доступных изначально; указатель на строку, определяющую имя семафора. Когда ожидающий семафора поток хочет получить доступ к ресурсу, охраняемому семафором, то wait-функция потока опрашивает состояние семафора. Если его значение больше 0, значит, семафор свободен и его значение уменьшается на 1, а поток планируется на выполнение. Если же при опросе семафор занят, его значение равно 0, тогда вызывающий поток переходит в состояние ожидания. В момент, когда поток покидает семафор, вызывается функция ReleaseSemaphore, в которой значение семафора увеличивается на 1. Мьютексы, как и семафоры, - объекты ядра. Функционирование мьютексов похоже на критические секции Win32, с разницей в том, что последние выполняются в пользовательском режиме. В каждый момент времени мьютекс разрешает выполняться только одному потоку и предоставляет доступ только к одному ресурсу. При этом он позволяет синхронизировать несколько потоков, храня идентификатор потока, который захватил ресурс и счетчик количества захватов. Чтобы создать мьютекс, можно воспользоваться функцией CreateMutex, ее параметры аналогичны рассмотренным выше. Когда ожидание мьютекса потоком успешно завершается, последний получает монопольный доступ к защищенному ресурсу. Все остальные потоки, пытающиеся обратиться к этому ресурсу, переходят в состояние ожидания. Когда поток, занимающий ресурс, заканчивает с ним работать, он должен освободить мьютекс вызовом функции ReleaseMutex. Эта функция уменьшает счетчик рекурсии в мьютексе на 1. Выбор используемого механизма синхронизации во многом зависит от времени его исполнения и кода, в котором он используется.
Кроме всего прочего, в Windows NT, начиная с четвертой версии, имеется еще один поточный уровень детализации - волокна (или нити). На уровне пользователя объект ядра поток может быть разделен на несколько нитей. И в таком случае операционная система ничего о них не знает, вся работа по планированию и управлению нитями ложится на плечи разработчика прикладного приложения.
Создание современного ПО требует использования параллелизма, а в будущем производители процессоров грозятся только увеличивать количество ядер на одном процессоре. Однако у многопоточного программирования есть ряд сложных моментов: организовать синхронное выполнение команд, избежать гонок и при этом оптимально нагрузить железо, чтобы добиться повышения производительности за счет параллелизма.
В этой статье сначала мы разобрались с примитивами параллельного кодинга - общими понятиями, затем разобрались, как они исполнены в конкретном API - Win 32 threads. Рамки статьи не позволили нам рассмотреть другие API для многопоточного кодинга. Будем надеяться, что у нас еще будет возможность когда-нибудь продолжить обсуждение этой нужной темы.
Желаю удачи, до встречи!
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 Решение задачи Пуассона методом Якоби в трехмерной области Цель - практическое освоение методов распараллеливание алгоритмов задач, решаемых сеточными методами на примере решения
