Суров закон параллелизма, или «что за #@%&^ этот ваш параллелизм?»

Всем привет!

То, что Intel поглотил прикупил приобрел Cilk Arts общеизвестно. Подбирая подходящий глагол, я заглянул на сайт авторов Cilk++. И как бы вы думали они сами назвали происшедшее? Cilk++ has moved to Intel Corporation! (Cilk++ переехал в Intel!). Хорошее чувство юмора никогда не помешает, и мы решили перевести несколько постов о Cilk++ на русский. Читайте о законах параллелизма, последовательной семантике, параллельных менеджерах памяти, числах Фибоначчи и N ферзях:

Законы параллелизма, или «что за #@%&^ этот ваш параллелизм?»

Наши постоянные авторы уже неоднократно касались теоретических аспектов параллельного программирования, да и мы сами по мере сил публиковали переводы интересных материалов. Логично предположить, что люди, взявшиеся за параллельное расширение C++, кое-что в этом смыслят. Чарльз Лейзерсон рассказывает на пальцах о теории параллелизма и дорабатывает напильником закон Амдаля. Не, даже не так: критикует закон Амдаля и называет свою теорию законом. Заинтригованы? Читайте перевод блога «What the $#@! is Parallelism, Anyhow?».

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

Продолжая теоретические изыски Чарльза, Стив Левин-Берлин рассуждает о плюсах и минусах последовательной семантики Cilk++. Точнее о плюсах, т.к. минусов в статье я не нашел. Это напомнило мне жанр социалистического реализма, но, положа руку на сердце – у Штирлица ведь тоже не было недостатков, но это нисколько не мешает нам его любить. Итак, основная мысль Стива: если семантика последовательна, то для понимания или выполнения программы НЕ нужна концептуальная параллельная модель. Последовательная семантика позволяет легко построить эквивалентную последовательную программу, гарантировать правильность выполнения, облегчить разработку аналитических инструментов и соответственно – сам анализ производительности и QA. Читаем и ждем комментариев нашего эксперта по моделям Вячеслава Любченко ;).

Параллельные механизмы выделения памяти.

Есть модель, нет модели - проблемы с памятью будут. Даже если ее много, потому что жизнь такая. Но не даром говорят, что проинформирован – значит вооружен! Опять же на пальцах основные проблемы тяжелого наследия NUMA и коротенько как с этим всем бороться в статье Чарльза Multicore Storage Allocation.

Miser – динамически загружаемый аллокатор памяти для многопоточных приложений.

Из всех карточных игр я знаю только «дурака», «21», и чуть-чуть покер. А вот те, кто играет в преферанс, оценят юмор силкартовцев, которые вдохновились известным менеджером памяти «Hoard» и назвали свой менеджер «Miser». Кстати, эта библиотечка вполне самодостаточна – если у вас проблемы с памятью, можете ее использовать без Cilk++. Ссылка на короткое, но емкое описание архитектуры Miser.

Визуализация «параллельного ускорения» с помощью Cilkview.

Если бы Фибоначчи мог предположить о популярности своей фамилии в среде программистов, он бы наверняка назвал эти числа как-то иначе. Очередной раз возвращаемся к параллельному расчету чисел Фибоначчи (ой), теперь – с целью продемонстрировать вкусности Cilkview. Это инструментальное средство позволяет на основании встроенных в код «меток» сделать прогноз о параллелизме заданного участка, а затем выполнить проверочные запуски для сравнения теоретического прогноза с реальными данными. Вы спросите: зачем все это? Да потому что графики – это круто! Шутка. Когда теоретический прогноз говорит о линейном параллелизме алгоритма, а на практике получается беда, - значит нужно копать куда-то в сторону, например, ограничений по памяти. Если даже теория ничего хорошего не говорит – меняем алгоритм.

Решение задачи N ферзей на Cilk++

Еще раз обо всем вышеизложенном в виде одного практического примера. До боли знакомая задачка N ферзей разобрана по косточкам с помощью Cilk++, Miser и Cilkview: Multicore-enabling the N-Queens Problem Using Cilk++.

Надеюсь, я не потратил время зря, а вам будет интересно почитать обо всем об этом на родном языке. От себя добавлю, что переводить блог ребят из Cilk Arts было весьма интересно (в отличие от большинства сухих и скучных технических материалов). Что, впрочем, не исключает возможных ошибок в терминологии, а возможно и смысловых ошибок. Поэтому критика и пожелания приветствуется. Сегодня - как никогда! :)

Всем удачи! Читайте о хорошем.
Pour de plus amples informations sur les optimisations de compilation, consultez notre Avertissement concernant les optimisations.