Light-electric.com

IT Журнал
22 просмотров
Рейтинг статьи
1 звезда2 звезды3 звезды4 звезды5 звезд
Загрузка...

Параллельное программирование на c в действии

Используем параллельные алгоритмы C++17 для улучшения производительности

  • Переводы, 17 октября 2018 в 16:50
  • Никита Прияцелюк

Мы перевели пост из блога Microsoft, в котором разработчик рассказывает, как пользоваться параллельными алгоритмами, поддержка которых появилась в стандартной библиотеке C++17.

Как использовать параллельные алгоритмы

Чтобы использовать библиотеку параллельных алгоритмов, следуйте данным шагам:

  1. Найдите вызов алгоритма, который вы хотите оптимизировать с помощью распараллеливания. На эту роль хорошо подходят алгоритмы, которые делают больше чем O(n) работы, например, сортировка, и занимают значительное количество времени при профилировании приложения.
  2. Убедитесь, что код, используемый в алгоритме, безопасен для распараллеливания.
  3. Выберите политику параллельного исполнения (они будут описаны ниже).
  4. Если вы ещё этого не сделали, добавьте строку #include , чтобы сделать доступными политики параллельного исполнения.
  5. Добавьте одну из политик в качестве первого параметра вызова алгоритма для распараллеливания.
  6. Протестируйте результат, чтобы убедиться, что новая версия работает лучше. Распараллеливание не всегда работает быстрее, особенно когда используются итераторы непроизвольного доступа, когда набор входных данных мал или когда дополнительное распараллеливание создаёт конфликт внешних ресурсов вроде диска.

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

Параллельные алгоритмы зависят от доступного параллелизма оборудования, поэтому убедитесь, что вы проводите тесты на железе, производительность которого вам важна. Вам не нужно много ядер, чтобы показать прогресс, к тому же многие из алгоритмов построены по принципу «разделяй и властвуй», и поэтому не будут идеально ускоряться соответственно количеству потоков; но больше — всё равно лучше. В этом примере тестирование проводилось на системе с Intel 7980XE с 18 ядрами и 36 потоками. В этом тесте отладочная и релизная сборки программы показали следующий результат:

Теперь нам нужно убедиться, что вызов сортировки безопасен для распараллеливания. Алгоритмы безопасны для распараллеливания, если «функции доступа к элементу» — операции итерирования, предикаты и всё остальное, что вы можете попросить алгоритм сделать, — следуют обычному правилу для состояния гонки: «любое количество операций чтения или максимум одна операции записи». Более того, они не должны выбрасывать исключения (или выбрасывать достаточно редко, чтобы завершение программы не имело негативных последствий).

Политики исполнения

Теперь нужно выбрать политику исполнения. На данный момент стандарт включает в себя параллельную политику, обозначаемую как std::execution::par , и параллельную непоследовательную политику, обозначаемую как std::execution::par_unseq . В дополнение к требованиям первой, вторая требует, чтобы функции доступа к элементам допускали гарантии прогресса слабее параллельного выполнения. Это значит, что они не должны устанавливать блокировку или делать ещё что-то, что потребует от потоков конкурентного исполнения. Например, если алгоритм работает на графическом процессоре и пытается установить спинлок, поток, который держит этот спинлок, может помешать выполнению других потоков, и спинлок не будет снят. Больше о требованиях можно прочитать в разделах [algorithms.parallel.defns] и [algorithms.parallel.exec] стандарта C++. Если у вас есть сомнения, используйте параллельную политику. В этом примере мы используем оператор «меньше» для типа double , который не устанавливает никаких блокировок, и тип итератора, предоставленный стандартной библиотекой, поэтому мы можем использовать параллельную непоследовательную политику.

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

В пример сортировки чисел мы теперь можем добавить #include . Так как мы используем параллельную непоследовательную политику, мы добавляем std::execution::par_unseq в вызов алгоритма (при использовании параллельной политики нужно было бы использовать std::execution::par ). Теперь for -цикл в main() выглядит так:

Для этих входных данных программа сработала быстрее. Как вы будете тестировать программу зависит от выбранных вами критериев. Распараллеливание добавляет некоторую нагрузку и будет работать медленнее, чем последовательная версия, для малого числа N в зависимости от памяти и эффектов кеша, а также других факторов, специфичных для конкретной нагрузки. Если в этом примере установить значение N равным 1000, параллельная и последовательная версии будут работать примерно с одной скоростью, а если изменить значение на 100, то последовательная версия будет в 10 раз быстрее. Распараллеливание может оказать положительный эффект, но важно понимать, где его применять.

Текущие ограничения MSVC-реализации параллельных алгоритмов

Мы написали параллельную версию reverse() , и она оказалась в 1.6 раза медленнее последовательной версии на тестовом оборудовании даже при больших значениях N. Также мы протестировали другую реализацию, HPX, и получили схожие результаты. Это не значит, что добавление параллельных алгоритмов в STL было ошибкой со стороны комитета по стандартизации C++. Это просто значит, что оборудование, на которое нацелена наша реализация, не заметило улучшений. В результате мы предоставляем сигнатуры для алгоритмов, которые просто переставляют, копируют или размещают элементы в последовательном порядке, но не распараллеливаем их. Если нам покажут пример, в котором параллелизм будет работать быстрее, мы посмотрим, что можно сделать. Затронутые алгоритмы:

Реализация некоторых алгоритмов будет закончена в будущем релизе. В Visual Studio 2017 15.8 мы распараллелим:

  • adjacent_difference()
  • adjacent_find()
  • all_of()
  • any_of()
  • count()
  • count_if()
  • equal()
  • exclusive_scan()
  • find()
  • find_end()
  • find_first_of()
  • find_if()
  • for_each()
  • for_each_n()
  • inclusive_scan()
  • mismatch()
  • none_of()
  • reduce()
  • remove()
  • remove_if()
  • search()
  • search_n()
  • sort()
  • stable_sort()
  • transform()
  • transform_exclusive_scan()
  • transform_inclusive_scan()
  • transform_reduce()

Цели разработки MSVC-реализации параллельных алгоритмов

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

Сочетание с платформенными механизмами блокировки

Ранее Microsoft поставляла фреймворк для распараллеливания, ConcRT, который использовался в некоторых местах стандартной библиотеки. ConcRT позволяет разнородным нагрузкам прозрачно использовать доступное оборудование и позволяет потокам доделывать работу друг друга, что может увеличить общую производительность. В сущности, когда поток с рабочей нагрузкой ConcRT уходит в спящий режим, он приостанавливает выполнение текущей задачи и запускает другие готовые задачи. Такое неблокирующее поведение уменьшает переключение контекста и может обеспечить большую производительность, чем пул потоков Windows, используемый в нашей реализации параллельных алгоритмов. Тем не менее, это также означает, что нагрузка ConcRT не сочетается с примитивами синхронизации операционной системы вроде SRWLOCK, NT-событий, семафоров, оконных процедур и т. д. Мы считаем, что это неприемлемый компромисс для реализации «по умолчанию», используемой в стандартной библиотеке.

LATOKEN, Москва, от 3500 до 5000 $

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

Производительность в отладочных сборках

Мы заботимся об эффективности отладки. Решения, которым нужен включённый оптимизатор для нормальной работы, не подходят для использования в стандартной библиотеке. Если добавить вызов Concurrency::parallel_sort в предыдущий пример, то мы увидим, что параллельная сортировка ConcRT немного быстрее в релизе, но при этом почти в 100 раз медленней во время отладки:

Сочетание с другими системными программами и библиотеками параллелизма

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

Для получения дополнительной информации о том, какие оптимизации делает пул потоков, посмотрите доклад Педро Тейшеры, а также официальную документацию для функций CreateThreadpoolWork() , SubmitThreadpoolWork() , WaitForThreadpoolWorkCallbacks() и CloseThreadpoolWork() .

Прежде всего, параллелизм — это оптимизация

Если в ходе тестов параллельный алгоритм не даёт преимуществ для разумных значений N, то мы его не распараллеливаем. Мы считаем, что в два раза большая скорость для N = 1,000,000 и на три порядка меньшая для N = 100 является неприемлемым компромиссом. Если вам нужен «параллелизм любой ценой», существует множество других реализаций, которые работают с MSVC, включая HPX и Threading Building Blocks.

Аналогично, стандарт C++ позволяет параллельным алгоритмам выделять память и выбрасывать std::bad_alloc , когда они не могут получить к ней доступ. В нашей реализации мы возвращаемся к последовательной версии алгоритма, если нельзя получить дополнительные ресурсы.

Параллельное программирование на c в действии

Параллельное программирование на С++ в действии

Практика разработки многопоточных программ

С идеей многопоточного программирования я столкнулся на своей первой работе после окончания колледжа. Мы занимались приложением, которое должно было помещать входные записи в базу данных. Данных было много, но все они были независимы и требовали значительной предварительной обработки. Чтобы задействовать всю мощь нашего десятипроцессорного компьютера UltraSPARC, мы организовали несколько потоков, каждый из которых обрабатывал свою порцию входных данных. Код был написан на языке С++, с использованием потоков POSIX. Ошибок мы наделали кучу — многопоточность для всех была внове — но до конца все-таки добрались. Именно во время работы над этим проектом я впервые услыхал о комитете по стандартизации С++ и о недавно опубликованном стандарте языка С++.

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

Тем временем интерес к С++ свел меня с членами Ассоциации пользователей С и С++ (ACCU), а затем с членами комиссии по стандартизации С++ при Институте стандартов Великобритании (BSI) и разработчиками библиотек Boost. Я с интересом наблюдал за началом разработки библиотеки многопоточности Boost, а когда автор забросил проект, я воспользовался шансом перехватить инициативу. С тех пор разработка и сопровождение библиотеки Boost Thread Library лежит в основном на мне.

По мере того как в работе комитета по стандартизации С++ наметился сдвиг от исправления дефектов в существующем стандарте в сторону выработки предложений для нового стандарта (получившего условное название С++0х в надежде, что его удастся завершить до 2009 года, и официально названного С++11, так как он наконец был опубликован в 2011 году), я стал принимать более активное участие в деятельности BSI и даже вносить собственные предложения. Когда стало ясно, что многопоточность стоит на повестке дня, я по-настоящему встрепенулся — многие вошедшие в стандарт предложения по многопоточности и параллелизму написаны как мной самим, так и в соавторстве с коллегами. Я считаю большой удачей, что таким образом удалось совместить две основных сферы моих интересов в области программирования — язык С++ и многопоточность.

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

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

Далее я хочу поблагодарить коллектив издательства Manning, благодаря которому эта книга появилась на свет: Марджана Баджи (Marjan Васе), главного редактора; Майкла Стивенса (Michael Stephens), его заместителя; Синтию Кейн (Cynthia Kane), моего редактора-консультанта; Карен Тегтмейер (Karen Tegtmeyer), выпускающего редактора; Линду Ректенвальд (Linda Recktenwald), редактора; Кати Теннант (корректора) и Мэри Пирджис, начальника производства. Без их стараний вы не читали бы сейчас эту книгу. Я хочу также поблагодарить других членов комитета по стандартизации С++, которые подавали на рассмотрение материалы, относящиеся к многопоточности: Андрея Александреску (Andrei Alexandrescu), Пита Беккера (Pete Becker), Боба Блэйнера (Bob Blainer), Ханса Бема (Hans Boehm), Бимана Доуса (Beman Dawes), Лоуренса Кроула (Lawrence Crowl), Петера Димова (Peter Dimov), Джеффа Гарланда (Jeff Garland), Кевлина Хэнни (Kevlin Henney), Ховарда Хиннанта (Howard Hinnant), Бена Хатчингса (Ben Hutchings), Йана Кристоферсона (Jan Kristofferson), Дуга Ли (Doug Lea), Пола Маккинни (Paul МсKenney), Ника Макларена (Nick McLaren), Кларка Нельсона (Clark Nelson), Билла Пью (Bill Pugh), Рауля Силвера (Raul Silvera), Герба Саттера (Herb Sutter), Детлефа Вольмана (Detlef Vollmann) и Майкла Вонга (Michael Wong), а также всех тех, кто рецензировал материалы, принимал участие в их обсуждении на заседаниях комитета и иными способами содействовал оформлению поддержки многопоточности и параллелизма в С++11.

Наконец, хочу выразить благодарность людям, чьи предложения позволили заметно улучшить книгу: д-ру Джейми Оллсопу (Jamie Allsop), Петеру Димову, Ховарду Хиннанту, Рику Моллою (Rick Molloy), Джонатану Уэйкли (Jonathan Wakely) и д-ру Расселу Уиндеру (Russel Winder). Отдельное спасибо Расселу за подробные рецензии и Джонатану, который в качестве технического редактора, тщательно проверил окончательный текст на предмет наличия вопиющих ошибок. (Все оставшиеся ошибки — целиком моя вина.) И напоследок выражаю признательность группе рецензентов: Райану Стивенсу (Ryan Stephens), Нилу Хорлоку (Neil Horlock), Джону Тейлору младшему (John Taylor Jr.), Эзре Дживану (Ezra Jivan), Джошуа Хейеру (Joshua Heyer), Киту С. Киму (Keith S. Kim), Мишель Галли (Michele Galli) Майку Тянь-Чжань Чжану (Mike Tian-Jian Jiang), Дэвиду Стронгу (David Strong), Роджеру Орру (Roger Orr), Вагнеру Рику (Wagner Rick), Майку Буксасу (Mike Buksas) и Бас Воде (Bas Vodde). Также спасибо всем читателям предварительного издания, которые нашли время указать на ошибки и отметить места, нуждающиеся в уточнении.

Параллельное программирование на С++ в действии. Практика разработки многопоточных программ

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

Книга «Параллельное программирование на С++ в действии» не предполагает предварительных знаний в этой области. Вдумчиво читая ее, вы научитесь писать надежные и элегантные многопоточные программы на С++11. Вы узнаете о том, что такое потоковая модель памяти, и о том, какие средства поддержки многопоточности, в том числе запуска и синхронизации потоков, имеются в стандартной библиотеке. Попутно вы познакомитесь с различными нетривиальными проблемами программирования в условиях параллелизма.

С идеей многопоточного программирования я столкнулся на своей первой работе после окончания колледжа. Мы занимались приложением, которое должно было помещать входные записи в базу данных. Данных было много, но все они были независимы и требовали значительной предварительной обработки. Чтобы задействовать всю мощь нашего десятипроцессорного компьютера UltraSPARC, мы организовали несколько потоков, каждый из которых обрабатывал свою порцию входных данных. Код был написан на языке С++, с использованием потоков POSIX. Ошибок мы наделали кучу — многопоточность для всех была внове — но до конца все-таки добрались. Именно во время работы над этим проектом я впервые услыхал о комитете по стандартизации С++ и о недавно опубликованном стандарте языка С++.

Параллельное программирование на С++ в действии. Практика разработки многопоточных программ скачать pdf бесплатно

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

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

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

Читать онлайн «Параллельное программирование на С++ в действии. Практика разработки многопоточных программ» автора Уильямс Энтони — RuLit — Страница 10

Разумеется, производители компиляторов вправе добавлять в язык любые расширения, а наличие различных API для поддержки многопоточности в языке С, например, в стандарте POSIX С Standard и в Microsoft Windows API, заставило многих производителей компиляторов С++ поддержать многопоточность с помощью платформенных расширений. Как правило, эта поддержка ограничивается разрешением использовать соответствующий платформе С API с гарантией, что библиотека времени исполнения С++ (в частности, механизм обработки исключений) будет корректно работать при наличии нескольких потоков. Хотя лишь очень немногие производители компиляторов предложили формальную модель памяти с поддержкой многопоточности, практическое поведение компиляторов и процессоров оказалось достаточно приемлемым для создания большого числа многопоточных программ на С++.

Не удовлетворившись использованием платформенно-зависимых С API для работы с многопоточностью, программисты на С++ пожелали, чтобы в используемых ими библиотеках классов были реализованы объектно-ориентированные средства для написания многопоточных программ. В различные программные каркасы типа MFC и в универсальные библиотеки на С++ типа Boost и АСЕ были включены наборы классов С++, которые обертывали платформенно-зависимые API и предоставляли высокоуровневые средства для работы с многопоточностью, призванные упростить программирование. Детали реализации в этих библиотеках существенно различаются, особенно в части запуска новых потоков, но общая структура классов очень похожа. В частности, во многих библиотеках классов С++ применяется крайне полезная идиома захват ресурса есть инициализация (RAII), которая материализуется в виде блокировок, гарантирующих освобождение мьютекса при выходе из соответствующей области видимости.

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

1.3.2. Поддержка параллелизма в новом стандарте

Все изменилось с выходом стандарта С++11. Мало того что в нем определена совершенно новая модель памяти с поддержкой многопоточности, так еще и в стандартную библиотеку С++ включены классы для управления потоками (глава 2), защиты разделяемых данных (глава 3), синхронизации операций между потоками (глава 4) и низкоуровневых атомарных операций (глава 5).

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

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

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

Библиотека OpenMP. Параллельный цикл

Статья ориентирована на тех, кто не знаком с библиотекой OpenMP, но хотел бы познакомиться.

OpenMP — не просто библиотека параллельного программирования, но и стандарт, официально поддерживаемый для языков Си, C++ и Fortran (а неофициально и для других языков, Free Pascal, например [1]). Работает OpenMP только на архитектурах с общей памятью.

Библиотека OpenMP задумана так, что программист сначала может написать последовательную программу, отладить ее (ведь отлаживать параллельную программу очень тяжело), а затем, постепенно распараллеливать, дополняя директивами OpenMP.

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

В статье рассмотрены:

Все примеры статьи написаны на С++, использовался компилятор gcc (но можно использовать и другие, отличаться будут только ключи, передаваемые компилятору). Для поддержки OpenMP, gcc должен принять ключ -fopenmp.

1 Вычисление суммы элементов массива

Как отмечалось выше, OpenMP позволяет распараллеливать нашу программу постепенно, а сначала можно написать последовательную программу и отладить, что мы и сделали:

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

OpenMP нам, также, позволяет распределять работу вручную, но чаще всего это не нужно, ведь есть более удобные средства.

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

Поток может использовать как локальные переменные, так и разделяемые. Разделяемые переменные (shared) являются общими для всех потоков, очевидно, с ними надо очень осторожно работать (если хоть один поток изменяет значение такой переменной — все остальные должны ждать — это можно организовать средствами OMP). Все константы являются разделяемыми — в нашем примере, разделяемыми являются переменные «a» и «n».

Поток может содержать набор локальных переменных (опции private и firstprivate), для которых порождаются копии в каждом потоке. Для переменных, объявленных в списке private начальное значение не определено, для firstprivate — берется из главного потока. Все переменные, объявленные внутри параллельной области являются локальными (переменная «i» в нашем примере).

Опция reduction, также, задает локальную переменную (sum), а также, операцию, которая будет выполнена над локальными переменными при выходе из параллельной области («+»). Начальное значение локальных переменных, в этом случае, определяется типом операции (для аддитивных операций — ноль, для мультипликативных — единица).

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

Директива for имеет множество опций, подробнее про которые можно прочитать в толстых учебниках. Внутри цикла можно задать опции private и firstprivate, но кроме того, ряд новых. Например schedule определяет способ распределения итераций между потоками, а nowait — убирает неявную барьерную синхронизацию, которая по умолчанию стоит в конце цикла.

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

рис. 1 распараллеливание OMP

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

2 Вычисление интеграла методом прямоугольников

2.1 Задано количество прямоугольников

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

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

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

В качестве аргумента программа на рис. 2 принимает количество прямоугольников, интегрируется функция x * x на интервале [-1, 1], точное значение интеграла 2/3. Чем больше прямоугольников на ограниченном интервале — тем меньше каждый прямоугольник, следовательно, прямоугольники «плотнее прилегают к графику» и точность должна расти. Точность действительно повышается, мы видим это при увеличении количества прямоугольников с 10 до 100, однако, при очень большом их количестве точность резко падает. OpenMP тут оказывается и не причем (обратите внимание, при компиляции не использовался ключ -fopenmp).

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

OpenMP тут вроде бы и не причем, но оказывается так, что на точность может влиять количество работающих потоков и порядок вычисления. Читатель может убедиться в этом, например последовательно вычислив сумму ряда 1/(x * x) сначала при изменении x от 1 до 100000000, а затем, в обратном порядке. Результаты вычислений будут отличаться, и вычисление в обратном порядке дает более точный результат (если не понятно почему и очень интересно — сообщите, я напишу статью по этой теме). OpenMP не гарантирует определенный порядок вычислений, поэтому и может появляться неожиданная погрешность, на это многократно указывается в некоторых источниках [2].

2.2 Задана точность интегрирования

Так или иначе, в предыдущем примере у нас получилось без особого труда распараллелить последовательную программу (как и задумывалось разработчиками OpenMP). Может показаться, что так будет всегда, но это не так. Чуть-чуть изменим условие предыдущей задачи — теперь нам задана точность, которой надо достичь, а не количество прямоугольников.

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

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

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

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

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

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

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

В OpenMP имеется множество других полезных инструментов распараллеливания, таких как задачи (tasks), параллельные секции (sections), различные средства синхронизации. Все это не затронуто в статье (но может быть восполнено [2, 3, 4, 5]), т.к. ее целью ставилось показать читателю хоть какой-то пример того, как можно распараллелить свою программу средствами OpenMP. В следующих статьях, возможно, я опишу какие-нибудь другие части этой полезной библиотеки (не забудьте подписаться на рассылку).

Читать еще:  Язык программирования в эксель
Ссылка на основную публикацию
ВсеИнструменты
Adblock
detector
×
×