Четыре причины, почему параллельные программы должны иметь последовательную семантику

Создать новую статью

23.11.2009 12:00


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

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

Последовательную семантику (Serial semantics) не надо путать с последовательной консистентностью (sequential consistency), которая является концепцией, изобретённой Лесли Лампором (Leslie Lamport), и которая широко обсуждалась в литературе по параллельным вычислениям. Параллельная вычислительная система с последовательно консистентной памятью гарантирует, по словам Лампора, «что результат любого выполнения будет таким же, как если бы операции всех процессоров выполнялись в некотором последовательном порядке и операции каждого индивидуального процессора появляются в этой последовательности в порядке, определяемом программой».

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

Последовательная семантика Cilk++

Для начала посмотрим, как в Cilk++ реализована последовательная семантика.

В Cilk++ присутствуют три ключевых слова: cilk_spawn, cilk_for, и cilk_sync. Каждое из них имеет интуитивно понятную последовательную интерпретацию.

Ключевое слово

Параллельное значение

Последовательное значение

cilk_spawn

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

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

cilk_sync

Ожидание завершения параллельной работы

Ничего не делает (нет никакой параллельной активности)

cilk_for

Позволяет циклу выполнять итерации параллельно

Исполняет стандартный цикл for, в котором итерации выполняются по одной за раз

Как видно, программа на Cilk++ может легко становиться последовательной: просто нужно поменять cilk_for  на for и удалить операторы cilk_spawn и cilk_sync. В системе разработки Cilk++ есть опция компилятора, позволяющая строить последовательную программу. При использовании Cilk++ для Linux для «отрубания» функций Cilk++ используется опция [-fcilk-stub]. При использовании Cilk++  для Windows запускайте  cilkpp с опцией [/cilkp cpp].

Вы можете сказать: «Ладно, твоя умная параллельная программа может стать последовательной. Ну и что? Если бы мне нужна была последовательная программа, то я бы просто использовал C++!». Хорошо, что вы подняли этот вопрос! Параллельная модель с последовательной семантикой имеет четыре больших преимущества перед программными моделями без последовательной семантики.

  1. Эквивалентная последовательная программа на C++ может легко отлаживаться и анализироваться с помощью существующих средств разработки. Это идеальный способ отладки параллельной программы, без необходимости беспокоиться о параллельном взаимодействии, и без необходимости учитывать множество стеков и счётчиков программ. Так же, как и в старом добром C++, все символы и отладочная информация доступны для стандартных системных и сторонних средств. Ведь средства, которые легко применить к последовательным программам, могут потребовать специальных версий для работы с параллельными программами. К таким средствам относятся профайлеры производительности, средства анализа кода и безопасности, контроля утечки памяти и любые другие, которые могут работать с программами на C++.
  2. Последовательная семантика программ на Cilk++ позволяет Cilk Arts создавать лучшие средства анализа производительности и корректности программ Cilk++. Эти средства дают твёрдую гарантию правильной работы программы. Например, наш детектор состояния гонки Cilkscreen прогоняет тестовую программу в последовательном режиме на одном процессоре. Используя информацию о параллельной структуре программы (то есть о местах, в которых происходит распараллеливание и синхронизация), Cilkscreen имеет возможность анализировать все возможные режимы работы программы, при любом количестве процессоров. Другими словами, Cilkscreen замечает потенциальное состояние гонки в любом из всех возможных режимов работы программы. Последовательная семантика Cilk++ позволяет Cilkscreen анализировать параллельную программу, когда она работает на одном «работнике» (worker, так в Cilk++ называется выполняющий поток) на одном процессоре.
  3. Последовательная семантика Cilk++ даёт реальное преимущество при тестировании и анализе качества программ. Cilk++ разрабатывался с таким расчётом, чтобы параллельные программы, написанные на нём, могли быть детерминированными и надёжно воспроизводили результаты, аналогичные последовательной версии. Эта гарантия позволяет использовать традиционные средства тестирования, которые предполагают, что при наличии одних и тех же входных данных во множественных запусках программа всегда возвращает один и тот же результат. Последовательная семантика Cilk++ устраняет необходимость учитывать нюансы тайминга и планирования при оценке корректности программ и позволяет легко проводить сравнение вывода программы при множественных запусках. Повторяемость – одно из основных свойств, которое делает программы на Cilk++ надежными и легкими в тестировании.

     

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

В чём соль?

Возможно, всё это звучит слишком хорошо, чтобы быть правдой, и, возможно, теперь вы подумаете: «Ну ладно, а в чём соль?». Вот несколько вещей, которые я не упомянул. Во-первых, поскольку имеются некоторые виды параллелизма, которые не имеют последовательной семантики, на Cilk++ нельзя написать программу, использующую такие стратегии параллелизации. Например, Cilk++ не поддерживает моделей производитель/потребитель, программный пайплайнинг или передачу сообщений. Тем не менее, хотя мы и вынуждены кое от чего отказываться ради последовательной семантики, опыт показывает, что лучше меньше, да лучше. Четыре преимущества, описанных выше, вполне восполняют наши потери.

Есть ещё один момент. В третьем пункте я сказал, что программы на Cilk++ могут быть детерминированными, а не что они такими являются. Почему? Результат работы программы с гонкой (смотреть «Are Determinacy Races Lurking in Your Multicore Application") зависят от того, как программа «разложилась» на несколько процессоров. Состояние гонки, приводящее к такому недетерминированному поведению, обычно является результатом ошибки. В большинстве случаев вы обычно застреваете в этом месте, пытаясь обнаружить ошибку гонки, тщательно проверяя код. Преимущество Cilk++ в том, что существует инструмент, который  помогает находить и устранять гонки – Cilkscreen.  Cilkscreen возвращает программе детерминированность, и делает это весбма эффективно именно благодаря последовательной семантике. «Соль» с том, что Cilkscreen использует последовательный режим как тест правильности параллельного выполнения.

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

На практике мы обнаружили, что большинство программ на Cilk++ требуют очень мало блокировок. В частности, параллельные конструкции  Cilk++ устраняют необходимость в блокировках, которые требуют другие параллельные модели для коммуникаций между потоками и синхронизации. Более того, во многих обычных ситуациях, в которых блокировка кажется необходимой для устранения гонки, Cilk++ предлагает использовать гиперобъекты – новые структуры данных, которые могут разрешать состояние гонки на глобальных переменных, не жертвуя при этом производительностью или детерминизмом. Избегая блокировок и используя гиперобъекты, Cilk++ обходит стороной многие тонкие места производительности, вызываемые блокировками, такие как соревнование блокировок (lock contention), которое может существенно замедлить выполнение параллельных программ, или дедлоки, которые могут подвесить программу посередине работы.

Последнее слово

Подводя итоги, можно сказать, что последовательная семантика Cilk++ обеспечивает три ключевых преимущества: производительность, надёжность и продуктивность.

  • Масштабируемая производительность, обеспеченная моделью проектирования,  которая не подразумевает предварительного  знания программистом количества имеющихся процессоров. Разработчик может использовать традиционные последовательные средства настройки производительности для нахождения горячих мест и повышения как последовательной, так и параллельной производительности.
  • Надёжность, основанная на принципах повторяемости результатов и  детерминизма и возможности построить эффективный и гарантированно правильный детектор состояний гонки, базирующийся на однозначном соответствии параллельной и последовательной семантик.
  • Наконец, программисты могут работать более продуктивно, используя знакомые им парадигмы в новых разработках, и, естественно, старый последовательный код может быть легко преобразован в Cilk++: его не надо переписывать, как в случае с концептуально отличными программными моделями, такими,  как модель параллельных данных или с модель обмена сообщениями.

Дополнительные ресурсы по Cilk++

Данная статья является переводом блога Steve Lewin-Berlin.
Оригинал доступен по адресу http://www.cilk.com/multicore-blog/.