The acronym RWT stands for Ricker Wavelet Trans(form/warp), which means that this is an example of how to do competitive wavelet transforms through task-based parallelism provided by the Transwarp library (by Christian Blume).
- transform_uniprocessor: 1499
- transform_omp: 245
- transform_transwarp: 203
(DELL Inspiron 3593, 8 cores, signal frequency 95 kHz, search rate (f) 15 Hz)
Current state requires some Boost, GCC compiler 7.2+ with extensions (to compare with an introduced openmp version).
mkdir build
cd build
cmake -DCMAKE_BUILD_TYPE=Release ..
make -j 2
./test_app
./sample 2
In Russian:
Статистика применения вейвлет-преобразования на основе двух типов распараллеливания: Transwarp и OpenMP (GCC 8.3) на машине Orange Pi X (4 ядра).
На нескольких примерах приведены входные данные и усредненные времена обработки, полученные через многократные тестовые замеры (исключая однопоточный вариант: ввиду перерасхода времени он запускался единожды в начале каждой серии тестов и, таким образом, отрабатывал на еще "не разогретом кэше", его показатели могли быть существенно лучше, но только в начальных тестах с облегченными входными данными). Значение времен обработки всегда указаны в миллисекундах. Тестовый объем генерированных данных размера int32_t - 1 секунда. Вейвлет-преобразование работает с полным типом данных с плавающей запятой, double. Также, выражается надежда, что отвод тепла был обеспечен в минимальной, но достаточной мере (в абсолютном большинстве тестов) для честности цифр и актуальности их соотношений в данной статье.
Общий вид алгоритма сводится к подобному коду:
std::transform(signal_iter, signal_iter + total_iterations, dest, [&](auto & elem)
{
return std::inner_product(std::begin(filter), std::end(filter), std::addressof(elem), 0.0) / filter_size;
});
В сущности, есть внешний и внутренний цикл. Для каждой точки внешнего цикла рассчитывается
(во внутреннем цикле) скалярное произведение последующих точек, объемом длины построенного заранее
вейвлет-фильтра, на, собственно, сам фильтр, с последующей нормализацией.
В Transwarp-варианте распараллеливается внешний цикл на максимальное - аппаратно-обоснованное - количество
подзадач, каждой из которых ничего не остается как исполняться последовательно с дальнейшим объединением
результатов.
В случае применения GCC-OpenMP алгоритмов мы своевольно расставляем API-параллелизм
__gnu_parallel::transform() и __gnu_parallel::inner_product()
в тех местах, в которых посчитаем нужным: только во внутреннем цикле (omp), во внешнем и внутреннем циклах
(honest_omp), и только во внешнем цикле (не проверено), полагая, что система каждый раз нужным
образом поучаствует.
rate/frequency - частота дискретизации АЦП
f - искомая частота (или "частота для анализа")
uni/однопоточный - время обработки в однопоточном варианте
tw - время обработки с помощью библиотеки для конкурентных вычислений на основе задач (Transwarp)
honest_omp - время обработки посредством "честного" варианта вычислений на основе технологии OpenMP
omp - время обработки посредством альтернативного варианта вычислений на основе технологии OpenMP
| rate 16kHz, f 20Hz | Результаты |
|---|---|
| uni: 231 | |
| tw: 43 | |
| honest_omp: 60 |
| rate 16kHz, f 10Hz | Результаты |
|---|---|
| uni: 432 | |
| tw: 82 | |
| honest_omp: 112 |
Здесь достаточен даже однопоточный вариант, поскольку мала сама частота дискретизации АЦП.
| rate 32kHz, f 10Hz | Результаты |
|---|---|
| uni: 1295 | |
| tw: 314 | |
| honest_omp: 423 |
Здесь для runtime обработки уже недостаточно однопоточного варианта.
| rate 50kHz, f 10Hz | Результаты |
|---|---|
| uni: 2960 | |
| tw: 781 | |
| honest_omp: 1150 |
Очевидно, это первый пример, когда применение технологии OpenMP невозможно в runtime, то есть, когда обработка сигнала должна выполняться своевременно. Здесь начинается буферирование обработки, поскольку приход сигнала опережает его обработку. Однако, наш метод (tw) по-прежнему укладывается в срок.
Что можно сказать на данный момент: во всех вышеприведенных случаях выигрыш от распараллеливания постепенно падает от 4 (и даже более) раз (что соответствует количеству ядер) до [3..4) и ниже и, как будет показано, этот выигрыш будет продолжать снижаться. Почему - возможно разберемся по ходу. Держа в голове этот факт, зададимся еще одним вопросом: а до каких пор naive-реализация, написанная с помощью библиотеки, предполагающей разнородные (а не однотипные) задачи, будет эффективней OpenMP/GCC алгоритмов?
| rate 60kHz, f 10Hz | Результаты |
|---|---|
| uni: 4150 | |
| tw: 1598 | |
| honest_omp: 1600 |
Уже идут вровень?!
| rate 80kHz, f 10Hz | Результаты |
|---|---|
| uni: 7335 | |
| tw: 4400 | |
| honest_omp: 2710 |
Хмм... Мы уже дико отстаем от OpenMP? Что же тогда будет, если привлекать для вычислений не все ядра?
| rate 80kHz, f 10Hz | Результат |
|---|---|
| 3 ядра | tw: 3232 |
| rate 80kHz, f 10Hz | Результат |
|---|---|
| 2 ядра | tw: 3790 |
Но что это?
4 ядра производят итоговое вычисление медленнее, чем 3 ядра... И даже медленнее, чем 2 ядра?
"Это вообще что? Это вообще... - как?"
Пришло время как-то усовершенствовать нашу реализацию. Первое, что приходит в голову, это что пробегание по диапазонам приводит к какой-то недружественности к кэшу/кэшам, когда процессору для вычислений приходится часто подтягивать увеличивающиеся в размерах диапазоны данных сигнала и вейвлет-фильтра из основной памяти в ограниченные по размеру кэши. Перед вычислениями каждой подзадачей своего поддиапазона мы скопировали в автоматическую память (стек) каждой подзадачи причитающуюся ей часть сигнала и вейвлет-фильтр. Если с частями сигнала ничего поделать нельзя, то фильтр - для всех один, и его, единожды заполнив одной из задач, можно использовать совместно всеми. Для этого, выражение параметризации подзадачи должно выглядеть следующим образом:
template <class FILTER_LOCATION_STRATEGY = use_static_filter_strategy>
После повторных сборки приложения и тестирования результаты для уже знакомых нам входных данных таковы:
| rate 60kHz, f 10Hz | Результаты |
|---|---|
| uni: 4150 | |
| tw: 1140 | |
| honest_omp: 1600 |
| rate 80kHz, f 10Hz | Результат |
|---|---|
| 2 ядра | tw: 3693 |
| rate 80kHz, f 10Hz | Результат |
|---|---|
| 3 ядра | tw: 2671 |
| rate 80kHz, f 10Hz | Результаты |
|---|---|
| uni: 7335 | |
| 4 ядра | tw: 2098 |
| honest_omp: 2710 |
Статус-кво восстановлен. Мы по-прежнему опережаем алгоритм honest_omp (даже в большей мере, чем раньше). И зависимость скорости расчета от количества участвующих ядер, как и положено, соответствует закону прямой пропорциональности. Однако, видна и неприятная закономерность о том, что привлечение к расчетам каждого последующего ядра приводит к не столь впечатляющему выигрышу, как предыдущего. Все это не исключает наличия неизвестных нам (кроме промахов кэша) особенностей системы. Поскольку операция объединения результатов подзадач ничтожна по времени в сравнении с временем работы подзадач.
Не забывая про основной интерес, не забываем и про сравнение OpenMP-вариаций между собой. Вот как менялось соотношение между omp и honest_omp.
| rate 30kHz, f 10Hz | Результат |
|---|---|
| omp: 461 | |
| honest_omp: 380 |
| rate 90kHz, f 10Hz | Результат |
|---|---|
| omp: 4072 | |
| honest_omp: 3888 |
| rate 150kHz, f 10Hz | Результат |
|---|---|
| omp: 10615 | |
| honest_omp: 13017 |
Производительность omp постепенно настигала производительность honest_omp, и, в конечном итоге, оказалась выше. Что же касается нашего типа распараллеливания, он, постоянно выигрывая (до rate 150kHz, f 10Hz) у omp, начинает проигрывать примерно с ширины вейвлет-фильтра в 35551 точку, что отражено далее:
| rate 160kHz, f 10Hz | Результат |
|---|---|
| uni: 30392 | |
| tw: 12980 | |
| omp: 12650 |
Окончательный тестовый вариант:
| rate 200kHz, f 10Hz | Результат |
|---|---|
| uni: 50450 | |
| tw: 24810 | |
| omp: 19782 |
- Решение на базе Transwarp относительно легковесно, оно и быстрее во многих практических ситуациях (например, когда частота для анализа будет задана не столь жестко, а размер вейвлет-фильтра не будет превосходить пары десятков тысяч значений).
- Решение на базе Transwarp не зависит от реализации в стандартных библиотеках компиляторов поддержки алгоритмов параллельности.
- Решив однажды проблему дружественности алгоритма кэшированию данных, нельзя решить ее раз и навсегда для всех предстоящих случаев и объемов данных.
- При кажущейся простоте параллельных алгоритмов
__gnu_parallel::transform и __gnu_parallel::inner_productих сочетание и совместное использование на больших объемах данных, определенно, задействует скрытую мощь технологии OpenMP, которая инкапсулирует в себе многое о системе и аппаратуре. То есть, ответ на вопрос: "За счет чего эти алгоритмы выиграли в конечном итоге" требует самого серьезного осмысления. Конечно, остались и простые предположения на этот счет, но их доказательство или опровержение ждет своих экспериментов как на данной машине, так и вообще. - За счет чего решение на базе Transwarp, в остальном, быстрее? Думается, за счет низкой цены за абстракцию. Пул потоков и хорошее проектирование библиотеки Transwarp (функциональный подход) оказались ниже цены за тяжелую, хотя и продуманную, абстракцию от OpenMP.
- Проводите замеры быстродействия вашего кода - справедливость этого широко известного правила как никогда наглядна.
Предположим, нужно решить следующую задачу: при температуре окружающей среды 24-26 °C и гарантиях обработки 1 секунды входящего оцифрованного сигнала за среднее время в ~300 мс рассмотреть возможность функционирования компьютера без радиатора, оставляя за низкой теплопроводностью воздуха всю работу по рассеиванию тепла. Было написано 2 теста:
- Первый тест в цикле обрабатывает новые данные после того, как за ~300 мс закончил обработку предыдущих.
- Второй тест в цикле обрабатывает данные за время ~300 мс, а оставшееся до конца секунды время берет паузу, спит (ведь "порция данных появится" не ранее, чем через это время).
Цель первого теста - выяснение того, насколько постоянная обработка ухудшает характеристики
вычислений с течением времени, является ли это ухудшение лавинообразным (принцип домино), но речь об
отсутствии радиаторной системы не идет.
Цель второго теста - попытка выяснить, как периодическое остывание процессора во время вычислительной
паузы скажется на общей работе: возможен ли безрадиаторный вариант.
Мы редко оказываемся правы в своих первичных предположениях, потому что невозможно учесть то, о чем невозможно помыслить. Первый тест, несмотря на отсутствие вычислительной паузы, продолжает работать постоянно, хотя из-за нагрева (недостаточного отвода тепла через маленький радиатор) времена расчета медленно сдвигаются в сторону увеличения. Второй же тест, в случайные периоды времени приводит к перезагрузке операционной системы! После того как было выяснено, что программное обеспечение не имеет ни малейшего undefined behaviour, стало очевидным: приводит к перезагрузке перегрев процессора, что, по-логике, невероятно.
Дело вот в чем. По умолчанию в Armbian включена политика масштабирования тактовой частоты центрального процессора (и симметричных процессорных ядер) под названием ondemand (по требованию). Программа масштабирующего регулятора (scaling_governor) управляет сменой тактирования в зависимости от текущей вычислительной нагрузки, выбирая наиболее подходящую тактовую частоту из дискретного диапазона тактовых частот scaling_available_frequencies (по умолчанию, от 480000 до 1800000 Гц). Если в первом тесте тактовая частота почти неизменно остается на уровне 1488000 редко повышаясь до 1608000 Гц, то во втором тесте, в моменты возобновления вычислений может прыгать до 1800000 Гц. А эта частота - максимально возможная (а значит, критическая), согласно спецификации и системному файлу cpuinfo_max_freq.
Таким образом, во втором тесте, операционная система пытается осуществить компенсационное действие - после
долгого простоя приложения с последующей стремительной его вычислительной нагрузкой - привлекает все
вычислительные ресурсы. При резком снижении тактовой частоты до минимума и резком увеличении до максимума
так же резко скачет и температура, до показателей, очевидно, критических для работы.
Решение: установить максимальную частоту в 1488000 Гц в системном файле scaling_max_freq, проконтролировать,
что среднее время в ~300 если и возросло, то не более чем до допустимого уровня.