Herb Sutter (
www.gotw.ca) архитектор ПО Microsoft и член комитета по стандартизации ISO C++.
Этой заметкой Herb начинает цикл статей, посвященных параллельному программированию, и демонстрирует необходимость построения целостной и полной модели, которая позволила бы разработчикам «думать и обсуждать» параллелизм на одном языке.
Если вы пробовали когда-нибудь подискутировать с вашими коллегами разработчиками на тему
параллельного программирования, то наверняка столкнулись с тем, что каждый из них говорит
об абсолютно разных моделях, языках, инструментах и понятиях, в конце концов. Поверьте,
такая ситуация не редкость. Смотрите — даже в языке мы имеем множество неоднозначных понятий,
так или иначе связанных с параллелизмом:
захват, параллельный, ассоциативный, атомарный, теневой, прерывание, целостность, управляемый
данными, равноправность, мелкозернистый, ветвление-соединение, иерархичный, интерактивный,
инвариантный, изоляция, сообщение, вложенный, оверхед, производительность, приоритет, протокол,
чтение, редукция, освобождение, структурированный, реентерабельный, отзывчивость,
масштабируемость, планировщик, сереализируемое обновление, побочный эффект, систолический,
таймаут, транзакция, пропускная способность, виртуальный, ожидание, запись,...
(acquire, and-parallel, associative, atomic, background, cancel, consistent, data-driven,
dialogue, dismiss, fairness, fine-grained, fork-join, hierarchical, interactive, invariant,
isolation, message, nested, overhead, performance, priority, protocol, read, reduction, release,
structured, repeatable, responsiveness, scalable, schedule, serializable update, side effect,
systolic, timeout, transaction, throughput, virtual, wait, write,...)
Некоторые из этих слов попросту многозначны, другие же не имеют полного значения без контекста.
Очевидно, что все это ведет к недопониманию среди разработчиков. Но каким образом мы можем
объединить разрозненную терминологию, когда опытные программисты, работающие с параллелизмом,
владеют сотнями различных технологий, множеством языков и под час трудятся в областях, где сами
задачи параллельной обработки понимаются по-разному?!
Сказ про слона и мудрецов очень похож на сегодняшнию ситуацию. Однако слон очень терпеливо вынес
все эти научные изыскания. Параллелизм же надает вам по рукам, будь здоров.
|
Раз шесть индийских мудрецов
(к несчастью слепых)
Пошли смотреть, что значит слон?
Как выгладят слоны?
И первый подошёл к слону,
Потрогал за бока
И удивлённо заявил:
"Слон — это же стена!"
Второй бивней лишь дотронув
Как тут же прокричал:
"Я знал всё это, да, я знал,
Что слон это кинжал!
А третий хобот в руку взял
"Послушайте, друзей,
Он длинён, мягок тягуч,
Слон — это же змея!"
Четвёртый руку протянул-
Опёрся на ногу,
"Я понял, — бормотал мудрец-
Подобен слон столбу".
А пятый ухо обнял вдруг,
Как он был поражён:
"На веер, — понял я, друзья —
Похож на веер слон".
Шестой вцепился сзади в хвост,
Был убеждён сто крат,
Что слон, он тонок и упруг,
Похож он на канат.
Шесть мудрецов вокруг слона
Горячий спор вели.
И каждый может, был и прав,
Ошиблись все они!
|
Мой коллега Дэвид Каллахан (David Callahan) возглавляет команду разработчиков, которая в рамках подразделения Visual Studio, работает над моделями параллельного программирования. Дэвид отмечает, что из множества фундаментальных задач и технологий параллельного программирования можно выделить три основных категории или столпа. Они представлены в таблице 1 [1]. Эти столпы позволяют нам построить каркас для систематизации всех аспектов параллелизма – от задач и компромиссных решений, которые имеют значение в рамках наших с вами проектов и шаблонов проектирования и технологий реализации, причин их применимости в тех или иных ситуация, возможности их объединения и дальнейшего развития инструментов и технологий.
Рассмотрим каждый столп в отдельности, отметим, как мы можем объединять технологии, принадлежащие выделенным категориям, и как мы можем использовать все это для систематизации знаний о параллелизме.
| Критерии\Категории (столпы) | 1. Реактивность и изолированность – асинхронные агенты | 2. Пиковая производительность и масштабируемость – параллельные коллекции | 3. Целостность – безопасно разделяемые ресурсы |
|---|
| "Одним словом" | Уменьшение связности\блокируемости | «Возвращение халявы» | Защита от повреждения разделяемых ресурсов |
| Резюме | Реактивность приложения сохраняется за счет независимости и асинхронности задач, взаимодействующих посредством сообщений | Ускорение пакетной обработки; параллельные алгоритмы и подходящие структуры данных | Синхронизация доступа к разделяемым ресурсам, в частности к изменяемым объектам в памяти |
| Примеры | GUI, Веб сервисы, фоновая печать, компиляция | Деревья, quicksort | Изменяемые объекты в памяти, таблицы в БД |
| Ключевые параметры | Реактивность (отзывчивость) | Пропускная способность, масштабируемость | Race-free, deadlock-free (отсутствие от гонок и тупиковых ситуаций) |
| Требования | Изолированность, независимость | Низкий оверхед | Компонуемость, сериализуемость |
| Распространенный сегодня инструментарий | Потоки, пулы потоков, очереди сообщений, фьючерсы(futures) | Потоки, пулы потоков, очереди сообщений, фьючерсы(futures), OpenMP | Мониторы\Семафоры, lock-free библиотеки, транзакции |
| Инструментарий завтрашнего дня | Активные объекты\сервисы, каналы, контракты | Chores, work stealing (1,2), параллельные STL и LINQ | Транзакционная память(STM), усовершенствованные механизмы блокировки |
| Лексика | Фоновый, теневой, прерывание, диалоговый, равноправность, ветвление-соединение, интерактивность, изоляция, сообщение, оверхед, производительность, приоритет, протокол, отзывчивость, реактивность, планирование, планировщик, тайм-аут | Ассоциативный, управляемый данными, мелкозернистый, иерархический, ветвление-соединение, вложенный, оверхед, производительность, редукция, повторяемость, масштабируемость, планирование, сериализуемость, побочный эффект, структурированность, систолический, пропускная способность | Блокировка, атомарность, целостность, равноправность, инвариантность, изолированность, вложенный, оверхед, производительность, приоритет, чтение\запись, сериализуемость, транзакционное обновление, виртуальность |
Взобравшись на этот «столб» мы с вами увидим параллельно исполняющиеся независимые друг от друга задачи (агенты), взаимодействие между которыми основано на асинхронном обмене сообщениями. Обычно мы стремимся избежать блокирования потоков, ответственных за взаимодействие с внешней по отношению к системе средой (примером таких потоков могут служить GUI-потоки). В этом случае мы выделяем тяжелые задачи в отдельные потоки и запускаем их параллельно. Независимость задач можно рассматривать как расширенную модульность – мы можем тестировать и размещать задачи независимо в разнообразных контекстах. Ораторы этого столпа обычно используют такие словечки как «интерактивность» и «отзывчивость», «реактивность» и «теневое, фоновое исполнение»; «сообщение» и «диалог»; «тайм-аут» и «принудительное завершение».
Как я уже сказал, типичным приемом этой категории является выделение тяжелых, продолжительных задач в отдельные потоки, что позволяет тем самым разгрузить поток, обрабатывающий сообщения от GUI. Нет ничего более плохого, чем подвисшая прорисовка интерфейса вашей программы (пользователь сворачивает окно программы, а, развернув его, получает белый, девственно чистый прямоугольник… кому ж это понравится?!). Но именно это происходит, когда вы вызываете какую-либо вычислительно нагруженную процедуру в GUI-потоке – GUI поток с радостью начинает проводить хитроумные расчеты, описанные в этой процедуре и полностью забывает о своей прямой обязанности – обработка сообщения WM_PAINT, а заодно и всех других сообщений, поступающих в очередь окна. На практике дело обстоит ещё хуже – увидев окно, заполненное белым, пользователь ожесточенно делает два-три щелчка мышкой, жмет Enter или Esc. Иногда приложения откликается на его действия, и процесс вычислений прерывается, но почти всегда это приводит к некорректному поведению программы. Никогда не допускайте такого поведения ваших приложений.
Какие виды задач подлежат депортации из GUI потока в отдельные потоки? Обычно это задачи, которым требуется длительное время для полного выполнения работы – печать, лингвистические проверки, рендеринг, компиляция и т.д. Кроме этого иногда некоторые функции вынуждены ожидать результатов работы других сервисов (сторонних по отношению к вашему приложению) – например, возвращения результатов запроса БД или Веб-сервиса. Некоторые из таких функций могут просто ожидать результата, тогда как другим для более быстрого выполнения своей работы может потребоваться помощь пользователя.
Наконец необходимо выяснить, как же должны взаимодействовать независимые задачи? Ключ к решению вопроса взаимодействия лежит в области асинхронного обмена сообщениями. Именно обмен сообщениями предпочтителен в данном вопросе, а не взаимодействие через общую память, изменяемые общедоступные объекты и т.п. (что по классификации Каллахана лежит в области третей категории). В случае с GUI-потоком, решение на основе асинхронных сообщений выглядит достаточно гармоничным, поскольку сам GUI основан на событиях и сообщениях.
Сегодня задачи, принадлежащие к обсуждаемой категории, решаются по средством фоновых потоков или пулов потоков. При этом в приложении обычно остается главный поток (нпр., GUI поток). Взаимодействие между фоновыми и главным потоками осуществляется либо посредством очередей сообщений, либо с помощью фьючерсов ({прим. перев. которые в некоторых языках являются частью языка (нпр., AliceML)}, а в Java и .NET выражены в форме Future и IAsyncResult соответственно). В будущем в данном разделе данной категории обязательно появятся новые инструменты и абстракции. Сегодня на эту роль могут претендовать активные объекты\сервисы (объекты, которые концептуально всегда обладают собственным потоком управления и взаимодействуют посредством асинхронных сообщений); каналы взаимодействия между задачами; и контракты, которые позволяют нам специфицировать ожидаемый порядок получения сообщений.
Отмечу, что задачи данной категории вообщем-то не стремятся нагрузить ядра наших процессоров по полной, это скорее задача для строителей второго столпа. Разработчики, опирающиеся на первый столп, стремятся сделать свои приложения более интерактивными, асинхронными и независимыми; впрочем, это вовсе не означает, что таким приложениям не требуется значительная вычислительная мощность. Раз мы можем выделить тяжеловесные вычислительные подзадачи нашего приложения в фоновые потоки, то очевидно, что лишнее ядрышко в процессоре нашему приложению не помешает.
В этой категории все направлено на оптимизацию вычислительного процесса, как можно более быстрое получение результата и максимальную загруженность ядер процессора. Одним словом эта область способствует возвращению старой-доброй халявы [2].
(прим.перев. Саттер намекает на то, что ранее, когда закон Мура ещё работал в полную мощь, программисты, не затрачивая почти никаких усилий, получали ускорение работы своих приложений вместе с удвоением тактовой частоты процессора почти каждые два года. Теперь же когда предел по наращиванию тактовой частоты почти достигнут, для ускорения работы приложение вынуждено использовать большее число ядер, что требует изыскания дополнительного параллелизма в приложении и, следовательно, является головной болью для программистов. Подробнее читайте [2]).
В частности мы хотим разрабатывать наши приложения в терминах обработки элементов той или иной коллекции (а это могут быть не только STL-контейнеры, но и «любая группа элементов») и параллелить уже сами коллекции (создавать параллельные алгоритмы обработки данных и структуры данных, подходящие для параллельной обработки). Спецы, воздвигающие столп #2, обычно употребляют такие слова как «масштабируемость», «пиковая производительность»; «управляемость данными», «мелкозернистость», «планировщик»; «побочный эффект» и «редукция».
Ключом к масштабируемости является не разделение вычислительно тяжелой задачи на некоторое жестко заданное число потоков, захардкоденных в коде приложения (а именно так обычно поступают в геймдейве, когда выделяют один поток под рендеринг, другой для обсчета физики, третий для ещё чего-нибудь и т.д.). Нет, такой путь не приведет нас к масштабируемости – при таком подходе приложение будет способно использовать лишь фиксированное число ядер К, когда же пользователь «поставит себе» К+1 ядро прироста производительности не будет. Конечно, программисту удобнее опираться на конкретную аппаратную конфигурацию (и иногда это возможно, например, конфигурация игровых консолей меняется лишь при переходе к следующему их поколению), однако приложения, разработанные таким образом, не являются масштабируемыми.
Путь к масштабированию лежит совсем в другой стороне. Необходимо таким образом создавать программу, чтобы она увеличивала степень своего параллелизма (например, число потоков) при росте объема входных данных. В общем случае мы можем добиться этого двумя способами.
Во-первых, мы можем использовать библиотеки, которые позволяют нам указывать, что мы хотим получить, не прописывая сам способ получения результата (т.е. работать в декларативном стиле). Сегодня, наверное, самым распространенным примером такого подхода является OpenMP, которая позволяет нам указать, что итерации данного цикла мы хотели бы выполнить параллельно, а система исполнения OpenMP уже сама решит, как нужно разбить цикл, чтобы оптимально загрузить имеющиеся аппаратные ресурсы. Инструментами следующего поколения, возможно, станут параллельные версии таких библиотек как STL и LINQ [5], что позволит нам просто прописать запрос – «выбери всех выпускников ВУЗа, отсортировав их по оценкам», — который будет параллельно выполнен над контейнером студентов, хранящихся в памяти компьютера, также просто, как если бы мы послали это запрос SQL серверу баз данных.
Во-вторых, мы можем явно прописывать действия, которые могут быть выполнены параллельно. Сегодня для этого мы можем воспользоваться пулом потоков (например, в Java и .NET это ThreadPoolExecutor и BackgroundWorker, соответственно). Однако необходимо помнить о наличии некоторого оверхеда, которые возникает при работе с пулом. Поэтому не следует использовать пул потоков для распараллеливания кратковременных операций. Например, мы можем захотеть реализовать рекурсивный алгоритм, такой как, например, QuickSort, параллельно выполняя сортировку левой и правой части списков, если размер этих частей достаточно большой и сортируя их последовательно при малом размере. Системы исполнения будущего, основанные на алгоритмах типа “work stealing”, смогут помочь нам в решении этой задачи – мы просто опишем «весь возможный параллелизм», а заботу о выборе параллельного или последовательного эффективного варианта исполнения возьмет на себя система. При этом, разумеется, такие системы учитывают и общую загруженность процессора в момент выполнения нашего приложения.
(прим.перев. Столп #3 часто становится столбом позора для разработчиков, не имеющих опыта параллельного программирования. Иногда он и вовсе предстает в образе пугала.)
В этой категории в основе всего лежит безопасный доступ к разделяемым ресурсам, в особенности к общим участкам памяти. Под безопасным доступом понимается доступ без нарушения целостности и без возникновения тупиковых ситуаций. Лексика этих столпотворцев в основном состоит из таких слов как «чтение и запись», блокировка, захват и освобождение блокировки, атомарность, целостность и транзакционность. Сейчас в основном я буду говорить о работе с изменяемыми объектами в общей памяти.
Сегодня статус-кво по части синхронизированного доступа к изменяемым общим ресурсам уверенно удерживают блокировки. Широко известно, что это не самый адекватный инструмент (подробнее см. [3] и [4]), но, тем не менее, на сегодня мы имел то, что имеем – из всех инструментов только блокировки хорошо подходят для решения неспециализированных задач.
Некоторые каркасы разработки снабжают программиста некоторыми lock-free структурами данных (нпр., хэш-таблицы), механизмы, синхронизации которых находятся в глубине каркаса и основаны на атомарных переменных, поэтому разработчик может использовать такие коллекции, не пользуясь блокировками. Это, безусловно, удобно, однако такие решения слишком специализированны – существует множество структур данных о наличии lock-free реализации которых ничего неизвестно.
В будущем нас ожидают усовершенствованные версии блокировок (которые, например, позволят удобно описывать вложенные захваты блокировок и указывать конкретно доступ к каким данным защищает та или иная блокировка) и возможно транзакционная память (основанная на автоматической версионности доступа к памяти, в частности см. STM системы). Однако пока мы вынуждены довольствоваться блокировками и головной болью при их использовании.
Поскольку три рассмотренных нами категории практически не пересекаются, то мы можем попробовать использовать подходы, разработанные в каждой из них, совместно. Собственно именно так дело обстоит в реальности – сегодняшние технологии и шаблоны разработки опираются на все три столпа.
Возьмем, к примеру, приложение в котором обход объемного дерева был вынесен в независимый от GUI-потока поток и запущен в фоновом режиме, что позволяет сделать интерфейс такого приложения отзывчивым (столп #1), использование деревянной структуры данных позволяет распараллелить саму задачу обхода дерева и, следовательно, получить необходимый результат быстрее (столп #2). Такое интерфейс такого приложения не будет подвисать на «медленной машине», хотя сам обход будет считаться довольно-таки неспешно, однако, сменив процессор на двух или четырехядерный, наш пользователь получит более быстрый обход – сработает масштабируемость из второй категории.
Предложенная классификация может использоваться и в обратном направлении – при изучении и декомпозиции уже имеющихся средств управления параллелизмом. Понимая, как соотносятся три столпа параллелизма, мы можем более четко выстраивать требования к нашему приложению и используемым инструментам – перенося центр тяжести с одного столпа на другой и используя их совместно.
Столпы параллелизма составляют основу общей модели сегодняшних параллельных вычислений и закладывают основу для её развития. При выделении категорий основными критериями выступали требования, компромиссы, шаблоны разработки и технологии. Выделяются три основные задачи параллельных вычислений – достижение реактивности\отзывчивости (за счет выполнения работы асинхронно), высокой производительности (за счет минимизации времени решения задачи) и целостности (за счет потокобезопасного доступа).
В будущем я постараюсь подробнее остановиться на каждой из трех выделенных категорий. В следующем месяце мы рассмотрим такой вопрос – «сколько параллелизма нужно вашему приложению» и обсудим различия между
O(1),
O(K) и
O(N) параллелизмом.
Столпы параллелизма Дэвида Каллахана, неопубликованная работа.
H. Sutter. "The Free Lunch Is Over: A Fundamental Turn Toward Concurrency Software".
H. Sutter. "The Trouble With Locks".
H. Sutter and J. Larus. "Software and the Concurrency Revolution" (ACM Queue, September 2005).
J. Duffy's blog. Hello PLINQ post
Если нам не помогут, то мы тоже никого не пощадим.
