Конкурс Интела по параллельному программированию

С апреля месяца проводится очередной конкурс Интела по параллельному программированию. В этом году участникам предлагается решить 12 задач в два этапа. Первый этап начался 6 апреля и закончится 3 июля, а второй этап начнется 17 августа и закончится 13 ноября. Каждая решенная задача оценивается отдельно следующим образом:

• 0—100 баллов за решенную задачу (учитывается корректность и скорость выполнения)
• 0—50 баллов за пояснительную записку (до 10 баллов за описание последовательного алгоритма, до 30 баллов за описание параллельного алгоритма и использованных технологий, до 10 баллов за производительность)
• 5 баллов за каждое сообщение на форуме, посвященному решению конкретной задачи (но не больше 25 баллов)

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

Простое статическое распределение работы в многопоточной программе

Этой статьей мы начинаем цикл публикаций «Параллельное программирование для самых маленьких». Ожидаемая аудитория проекта: школьники, а также студенты, начинающие изучать параллельное программирование. Преимущество многопоточного приложения перед последовательным заключается в том, что несколько потоков делают тот же самый объем работы в несколько раз быстрее. Единицей работы в частном случае может служить одна итерация цикла. Студенты допускают типичную ошибку при параллельном программировании: создают несколько потоков, каждый из которых делает тот же объем работы, что и последовательная программа. Это не приводит к желаемому ускорению, а даже иногда замедляет работу приложения. Здесь работает очень простое правило: каждый поток в параллельном приложении должен делать в N раз меньше работы, чем последовательная программа, где N — количество запущенных потоков. Рассмотрим простой способ статического разделения итераций одномерного цикла между несколькими потоками. На рисунке показан простой цикл, состоящий из 10 итераций. Пространство итераций описывается интервалом [0; 10). В последовательной программе начальное значение счетчика итераций равно нулю, инкремент цикла равен единице, т. е. тело цикла выполняется для каждой итерации. Как было сказано выше, ошибочным является запуск двух и более потоков, которые бы выполняли тот же самый код, показанный на рисунке. В этом случае объем работы для одного потока останется таким же, а для целой программы вырастет в несколько раз. Необходимо разделить работу — итерации цикла — между потоками. На рисунке ниже схематически показано статическое поочередное распределение для двух потоков. Нетрудно заметить, что поток номер 0 начинает свою работу с нулевой итерации и выполняет только четные итерации (инкремент равен 2): 0, 2, 4, 6, 8, а поток номер 1 начинает с итерации 1 и делает нечетные: 1, 3, 5, 7, 9. Таким образом, каждый поток делает в два раза меньше работы, чем последовательная программа. Теоретическое ускорение равно двум. Рассмотрим вариант разделения работы на три потока (см. рис. ниже). Здесь поток номер 0 также начинает с нулевой итерации, но обрабатывает каждую третью итерацию: 0, 3, 6, 9. Поток номер 1 начинает с итерации 1, а поток номер два начинает с итерации 2. У всех потоков инкремент счетчика цикла равен трём. Теоретическое ускорение равно 3. В конкретном случае баланс загрузки нарушен и фактическое ускорение равно 10/4 = 2,5. Следует отметить, что с ростом количества итераций дисбаланс будет нивелироваться, и будет приближаться к теоретическому ускорению. Можно проследить закономерность, что каждый поток начинает выполнять итерацию, номер которой совпадает с номером потока, а инкремент равен количеству потоков. Таким образом, можно записать общий случай для произвольного количества потоков (см. рис. ниже). Достоинства статического поочередного распределения итераций заключаются в: а) простоте программной реализации; б) отсутствии накладных расходов на планирование итераций; в) хорошем балансе загрузки при большом количестве итераций и одинаковом времени выполнения тела цикла для разных итераций. Недостаток подхода заключается в отсутствии возможности балансировать нагрузку, если для различных итераций тело цикла выполняется различное время. Этот недостаток был исправлен в библиотеке OpenMP. Для статического поочередного разделения итераций цикла может быть использована директива, показанная на рисунке ниже. Для плохо сбалансированных объемов работы, когда тело цикла выполняется различное время для разных итераций, может быть использован динамический алгоритм балансирования нагрузкой. К недостаткам OpenMP можно отнести ограничение на тип переменной итерации цикла. Библиотека OpenMP версии 2.5 поддерживает только signed int.

Смешные ситуации

Первого апреля начал читать курс "Введение в оптимизацию производительности ПО" для третьего курса СКС. Для вводной лекции решил не использовать слайды и проектор, а просто распечатал себе небольшой конспект лекции. На занятии поинтересовался у студентов: удобнее ли им с проектором или без. Обсудили достоинства и недостатки обоих способов, но решили проводить лекции со слайдами. На следующее занятия я принес ноутбук, проектор и удлиннитель. А в ауд. 314и нет розеток. И в коридоре рядом с аудиторией розеток нет тоже. Сейчас вспоминаю, что со мной случаются разные забавные ситуации. Приведу несколько примеров. Зимой 2008 года с друзьями поехали в Карпаты кататься на лыжах. Я всем хвастался тем, как я компактно всё сложил в один рюкзачок, а вот другие едут с большими сумками. Когда приехали на место, оказалось, что я забыл положить в мой компактный рюкзачок лыжный костюм. В первый же съезд с горы, после нескольких падений, мои джинсы были очень сильно разорваны. Договорился о покупке бэушных лыжных брюк с хозяином домика, в котором мы жили. Брюки оказались на один размер меньше, чем было нужно. К концу отдыха они тоже порвались. Перед поездкой в горы заказал себе две новые пластиковые карточки: одну для зарплаты, другую — Master Card — для оплаты в интернет-магазинах. Вскрыл конверты с секретными пин-кодами и подумал: "О! Какие хорошие пин-коды, так легко запоминаются"! Затем скомкал конверты и выбросил. После возвращения из Карпат я даже примерно не смог вспомнить, какие цифры входили в комбинации. Интервал между заказом и перезаказом двух карт составил всего лишь две недели.