24 апр. 2009 г.

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

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

Комментариев нет:

Отправить комментарий

Темы

2012 (2) амазон (1) анпакинг (1) артемий лебедев (4) атн (1) аудио (1) аэропорт (1) безопасность (3) бизнес (1) билайн (1) блог (2) будущее (2) видео (11) википедия (5) вымысел (16) гагарин (1) герман (1) гитхаб (1) гугл (3) дед мороз (1) декабрь (1) демотиватор (2) дети (2) дизайн (13) диссертация (2) документация (1) друзья (5) евпатория (1) евро-2012 (1) жадность (1) заяц (1) идея (1) имейл (1) инстаграм (1) интервью (5) интересное (20) интерфейс (13) история (7) как_выжить (4) календарь (1) капитализм (1) картина (1) кмб (6) книга (6) коллекция (4) компилятор (2) конкурс (5) космос (1) лаборатория (1) либералы (1) лингво (1) лузер (6) макаренко (2) макдональдс (2) математика (1) медиапорт (1) ментор (1) металлика (1) металлист (2) метро (7) микрософт (6) миргород (1) москва (2) музыка (3) наркомания (1) новости (17) образование (3) оптимизация (5) основы (14) открытки (3) ошибка (11) памятник (1) патриотизм (3) плагиат (1) плата (1) погода (3) поиск (1) политика (2) полтава (2) праздник (1) программирование (15) прошлое (2) путешествия (8) рейтинг (1) рендер (1) рисунок (2) русские (1) русский язык (1) сайт (4) санкт-петербург (1) сапр (7) сеть (1) си++ (1) синтез (1) системси (1) скриншот (40) социализм (1) соцопрос (3) спектрум (2) спорт (2) срач (2) статистика (1) такси (1) тбб (3) твитер (9) тимошенко (1) украина (5) униан (1) фан (30) фокус (1) фото (39) фотошоп (1) фурсенко (1) футбол (2) хабр (1) харьков (21) хнурэ (19) хобби (4) цитата (2) чехия (1) школа (1) эпл (1) эхостар (1) юмор (1) яндекс (1) clang (2) doxygen (1) english (3) ios (1) llvm (1) msdn (1) outlook (1) PHP (1) stackoverflow (1)

Поиск

Читатели