Здравствуйте, мои дорогие хикке и хиккочки,
В этот холодный вечер мы с вами поговорим о параллельных вычислениях и даже
проведём некоторые численные эксперименты. Для этого нам потребуются:
1. Какой-нибудь всем известный алгоритм, которых легко распараллеливается
2. Компилятор с поддержкой openmp, например gcc или msvs
3. Компьютер с более чем одним физическим ядром
4. Немного свободного времени
В качестве алгоритма возьмём сортировку слияниями. На каждой итерации
увеличения размера сливаемого окна мы имеем цикл, который сливает два
отсортированных массива в один большой сортированный. Особенностью данного
цикла является то, что все итерации данного цикла изолированны друг от друга и
пишут в разные области памяти. Вокруг этого цикла мы и напишем заклинание:
#pragma omp parallel for
Самые ленивые могут найти полный пример по ссылке: http://ideone.com/yawZnl
В нём вы увидите, полную реализацию сортировки массива int'ов размером в пол
миллиарда элеметов¹.
Теперь подумаем, чего же нам ожидать от openmp? Какого прироста
производительности? Я запускал тесты на четырёхядерном процессоре, значит ли
это, что я должен был получить четырёхкратное ускорение по сравнению с
однопоточным запуском?
Обратим внимание, что в случае с четырёхядерным процессором в последней и
предпоследней итерациях увеличения сливаемого окна смогут пронять участие не
все ядра процессора, а только одно и два соответственно. Поэтому из двадцати
девяти итераций (log₂500000000), эффективно ядра будут использованы лишь 27
раз, плюс ещё полраза, плюс ещё четвертинка:
27.75/29 ≈ 95.69%
Итак, мы с вами посчитали теоретическую оценку эффективности параллельного
алгоритма по сравнению с последовательным. Обратите внимание, что при
увеличении количества ядер или уменьшении количества элементов в массиве,
эффективность параллельного алгоритма будет падать.
Таким образом, ускорения более чем в 0.9569 * 4 ≈ 3.83 добиться никак нельзя².
Давайте запустим тест и сравним теоретические ожидания с практическими. Сначала
скомпилируем и трижды запустим тест без openmp, а затем скомпилируем и запустим
его же с openmp и сравним времена выполнения:
g++ -march=native -O3 -ansi -pedantic -Wall -Wextra main.c;./a.out;./a.out;./a.out;g++ -march=native -O3 -ansi -pedantic -Wall -Wextra -fopenmp main.c;./a.out;./a.out;./a.out
main.c:53:0: warning: ignoring #pragma omp parallel [-Wunknown-pragmas]
Array prepared
Time taken: 109.250078s
Array prepared
Time taken: 109.242994s
Array prepared
Time taken: 109.150572s
Array prepared
Time taken: 30.908248s
Threads: 4
Array prepared
Time taken: 30.860521s
Threads: 4
Array prepared
Time taken: 30.904798s
Threads: 4
Возьмём сумму времён выполнения последовательного алгоритма поделим её на сумму
времён выполнения параллельного алгоритма:
(109.250078+109.242994+109.150572)/(30.908248+30.860521+30.904798) ≈ 3.53
Меньше чем максимально возможно, но тем не менее, нельзя не отметить, что это
составляет 3.53 / 3.83 ≈ 92% от теоретической скорости.
Таким образом, OpenMP³ на управление потоками и синхронизацию данных между ними
тратит всего 8% полезного времени. Любите и почитайте его, как панацею и
продолжателя дела Закона Мура.
--
¹ Если быть точным, то 2²⁹ элементов. На большее у меня не хватило оперативной
памяти в компьютере
² Возможно некоторое ускорение за счёт более удачного попадания элементов в
кеш-процессора, но поскольку данный алгоритм использует последновательный
проход по массиву, то попадание элементов в кеш не окажет влияния. Любопытный
читатель может самостоятельно распараллелить какой-нибудь алгоритм перемножения
матриц, на которых теоретический предел ускорения можно значительно превысить
как раз за счёт многократного использования элементов находящихся в текущем
окне кэша.
³ С такими результатами название этой библиотеки можно написать с большой буквы
42 comments
recommend
bookmark
subscribe
форматировать текст по ширине в 80 символов в 2012 году — пиздец
высказывать мнение о котором не спрашивали — пиздец
Поставили дедфуда на место.
его оттуда и не снимали
Нихуя себе! Как ты сделал сноски с upper символами?
Compose
А, понял, спасибо.
Срыв покровов просто %)
ага. ZOG скрывает, но на самом деле лучший инструмент для выполнения любых задач — мозг
почему? у меня если на две части разделить экран то как раз где-то по 100 символов влазит (стандартное 1280x разрешение, шрифт невелик).
ах да, сбоку никаких панелей нету, может с ними как раз по не больше 80 символов влезет
потому в 2012 году почти все ПО уже умеет самостоятельно разбивать строки
не понял, покажи пример.
вот моё ПО (vim) и разбивает по мере набора
на самом деле нет // лолка
> всем известный алгоритм, которых легко распараллеливается
/0 дальше не читал, гляну коменты ещё
> лучший инструмент для выполнения любых задач — мозг
проиграл
короче, ты не прав, поддерживаю гисти
короче, ты не прав, твоего мнения не спрашивали
notepad.exe, "перенос по словам"
да кто вы такие, что СПРАШИВАТЬ мое мнение?
я же не в рашке живу — могу высказывать что, где и когда захочу. Зрозуміло?
підгоріло?
разбивать надо на выходе (браузер читателя), а не на входе (браузер писателя)
пiдмакака
я вот не понимаю, как можно автоматически разбивать читабельно, я иногда затрудняюсь в ручном режиме, а тут вообще страшно представить что получится
писателю виднее как лучше представлять читателю его произведение
я по этому и прошу пример такого "умного" редактора
читателю виднее, в каком виде ему удобнее читать произведение
Homo sapiens
НУ ХОТЬ КТО-НИБУДЬ gets the «і» right // гуглом переводил, да?
ссылку на ебилд или не было
абсолютно справедливое возражение.
я просто на четверть нечеловек^W хохол. ну и да, гуглом переводил
нет ебилда. приходится искать тян и вместе с ней из исходников собирать
стало быть картины вам подавай в виде набора красок, а вы сами уж их на холсте разместите?
короче, палю: http://www.ietf.org/rfc/rfc2646.txt секция 3.2
тебя это должно убедить. Готов закрыть тред? // как давно ты признавал свою неправоту? а?
мой блог — мои rfc
ну ты сравнил. картины и какой-то технический высер.
если бы твое обилие импровизированных <br /> несло хоть какую-нибудь смысловую нагрузку (как у меня в #tiioes, например) — аналогия с красками подошла бы. Но по факту ты просто размечал большие параграфы, не самым удобным образом.
и да, если бы ты присылал мне посты по почте на бумаге, тогда можно было бы проводить аналогию с картинами и говорить про представление произведения. а
#tiitss
#tiitss/1