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

Этой статьей мы начинаем цикл публикаций «Параллельное программирование для самых маленьких». Ожидаемая аудитория проекта: школьники, а также студенты, начинающие изучать параллельное программирование. Преимущество многопоточного приложения перед последовательным заключается в том, что несколько потоков делают тот же самый объем работы в несколько раз быстрее. Единицей работы в частном случае может служить одна итерация цикла. Студенты допускают типичную ошибку при параллельном программировании: создают несколько потоков, каждый из которых делает тот же объем работы, что и последовательная программа. Это не приводит к желаемому ускорению, а даже иногда замедляет работу приложения. Здесь работает очень простое правило: каждый поток в параллельном приложении должен делать в 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.