- Тестирование №1 (ARM архитектура)
- Тестирование №2 (x86-64, 1226 x 2001)
- Тестирование №3 (x86-64, 1242 x 1227)
- Тестирование №4 (x86-64, sw - 1242 x 1227)
- Композиции фильтров
- Влияние значений в матрицах
Тестирование проводилось на изображениях размером 1226 × 2001 (image5.bmp) и 1242 x 1227 (image4.bmp), с использованием 4 потоков и 20 повторов для каждого замера. Точная конфигурация сборки указана в Makefile, а скрипт для запуска бенчмарков — в benchmark.sh.
В представленные графики не были включены результаты вычислений с по-пиксельным разбиением изображения (--block=1). Такой метод приводит к созданию чрезмерно большого количества элементарных задач (чанков), что ведёт к доминированию накладных расходов на создание, управление и синхронизацию потоков над временем полезных вычислений. В результате, измеренное время выполнения не отражает реальную эффективность алгоритма свертки. Кроме того, не проводились замеры для медианных фильтров, так как их алгоритм не является линейной сверткой.
Тестирование производилось на двух системах:
- Система на базе M2 MAX (ARM) - 8 высокопроизводительных ядер, 4 высокоэффективных ядра, 3.6 ГГц, ОЗУ 8+ ГБ, GCC 14.2.1
- Система на базе Intel Core i7 4790 (x86-64) - 8 ядер, 3.6 ГГц, ОЗУ 8+ ГБ, GCC 14.2.1
Каждая система подвергалась перезагрузке после каждого тестирования, сторонние эффекты были минимизированы + sudo cpupower frequency-set -g performance.
| FILTER NAME | SHORT NAME | SIZE |
|---|---|---|
| Big Gaussian Blur | gg | 15x15 |
| Box Blur | bo | 15x15 |
| Medium Gaussian Blur | mg | 9x9 |
| Motion Blur | mb | 9x9 |
| Basic Blur | bb | 5x5 |
| Gaussian Blur | gb | 5x5 |
| Emboss | em | 5x5 |
| None | co | 3x3 |
| Sharpen | sh | 3x3 |
При тестировании на ARM архитектуре исследовались режимы распределения вычислительной нагрузки между различными типами ядер (Performance и Efficiency). Было проведено сравнение стандартного режима работы планировщика macOS и режима с принудительным использованием только E-ядер.
Команда taskpolicy -c background в macOS назначает процессу самый низкий приоритет и предписывает использовать преимущественно энергоэффективные ядра (E-cores). Это позволяет изолированно оценить производительность на более медленных ядрах и понять потенциальное влияние неоднородности архитектуры.
| MODE | AVG TIME | MIN TIME | MAX TIME | 95th PERCENTILE | STD DEVIATION |
|---|---|---|---|---|---|
| P-Cores | 0.1351 | 0.1336 | 0.1412 | 0.1364 | 0.0013 |
| E-Cores | 0.6868 | 0.5174 | 0.8925 | 0.8627 | 0.1099 |
Результаты 40 запусков с каждым режимом распределения показали ожидаемое снижение производительности при выполнении исключительно* на E-ядрах, подчеркивая важность учета гетерогенности ядер при реализации под ARM-платформы.
Графики представлены в поддиректориях tests/plots/st-mt/.../arm/.
Подтверждена предсказуемая зависимость: время обработки изображения напрямую коррелирует с размером матрицы фильтра. Большие фильтры требуют больше вычислений и обращений к памяти на пиксель, увеличивая общее время.
fyi: количество чанков в тексте округлено, сомнительные тезисы отмечены * и рассмотрены далее.
При сравнении различных методов разбиения выявлены следующие тенденции:
-
В методе by_column при больших размерах блоков (> 128) наблюдается увеличение времени выполнения, превосходящее by_row и by_grid. Это указывает на то, что при такой ширине блока вычислительные затраты внутри одного потока начинают доминировать над экономией от сокращения числа чанков (и, следовательно, синхронизаций). Кроме того, горизонтальный рабочий набор данных (столбцы
x-rдоx+r, необходимые для вычисления свертки) становится слишком велик для эффективного размещения в быстрых кэшах L1/L2, что увеличивает задержку при доступе к памяти внутри потока и снижает общую производительность, даже если показатели L3 кэша остаются хорошими (см. таблицу ниже). -
В методе by_row, подобного резкого увеличения времени при росте блока (в исследованном диапазоне) не замечено. Интересно, что при малых размерах блока (например, 32), by_row (38 чанков 1226x32) оказался быстрее, чем by_column (62 чанка 32x2001). Это происходит несмотря на худшие показатели L3 кэша у
by_row(см. таблицу) и может объясняться несколькими факторами: 1) Более эффективным использованием L1/L2 кэша для горизонтальных обращений внутри короткого циклаy. 2) Потенциально меньшими суммарными накладными расходами на управление 38 широкими чанками по сравнению с 62 очень высокими и узкими. -
Из-за стандартного хранения массивов в C по строкам (row-major) и используемого порядка циклов
for (x = spec->start_column; x < spec->end_column; x++) { for (y = spec->start_row; y < spec->end_row; y++) {
переход к следующей строке (
image[y][x]->image[y+1][x]) означает скачок в памяти наwidth * sizeof(double)байт. Это расстояние практически гарантированно превышает размер кэш-линии (64 байта). Следовательно, каждая итерация поyпри фиксированномxс высокой вероятностью адресует новую кэш-линию, что может приводить к промахам в L1/L2 кэшах. Это фундаментальное свойство доступа к данным при данной организации цикла, не зависящее от метода разбиения. -
Анализ с помощью утилиты
perf(приblock=128) показывает значительное различие в эффективности использования L3 кэша:MODE L3 CACHE % MISSES BRANCH MISSES % by_column 4% 0.11% by_row 36% 0.11% Высокий процент L3 промахов в by_row обусловлен тем, что каждый поток обрабатывает широкую горизонтальную полосу. Внешний цикл
for xпроходит всю ширину изображения, постоянно запрашивая данные из новых столбцов. Из-за ограниченного размера L3, данные из "старых" столбцов вытесняются к моменту доступа к "новым", приводя к частым промахам. В by_column, поток работает с узкой вертикальной полосой, долго переиспользуя данные из небольшого числа столбцов, которые эффективно удерживаются в L3. Тем не менее, как отмечено выше, лучшие показатели L3 уby_columnне всегда транслируются в лучшее общее время выполнения.
Графики представлены в данной директории.
Для подтверждения наблюдений из Тестрования №2 было решено провести тестирование на изображении с примерно одинаковыми размерами по x и y.
-
Подтверждается ключевая проблема исходного порядка циклов: итерация по
yво внутреннем цикле (for x { for y { ... } }) приводит к неэффективному доступу к памяти. Переход отimage[y][x]кimage[y+1][x]— это скачок наwidth * sizeof(double)байт, что гарантированно адресует новую кэш-линию (размер которой 64 байта, вмещает ~8double), вызывая частые промахи L1/L2. -
Причина большего процента L3 cache miss в
by_row, наблюдавшаяся в Тесте №2, подтверждается и здесь. Как и ранее,by_rowвыполняет "широкое сканирование" по горизонтали, постоянно подгружая данные новых столбцов и вытесняя старые из L3.by_column, напротив, эффективно переиспользует данные в узкой вертикальной полосе в L3. Неэффективный порядок доступа к элементам внутри столбца (из-заfor y) влияет на L1/L2, но общая стратегия работы с данными на уровне L3 остается выгодной дляby_column. -
Вычисление с помощью метода by_grid показывает результаты производительности, схожие с by_row. Это указывает, что для данных размеров блоков, горизонтальный доступ к данным (как в
by_row) оказывает большее влияние на общую картину, чем вертикальный. -
Анализ
perfдля этого теста (квадратное изображение,for x { for y }) показывает:MODE (TEST NUM) L3 CACHE MISSES % BRANCH MISSES % L1 DCACHE LOAD MISSES % by_grid (2) 26% 0.11% 0.05% by_grid (3) 22% 0.11% 0.05% by_column (2) 3% 0.12% 0.24% by_column (3) 2% 0.12% 0.23% Вывод сравнения: Геометрия изображения оказывает незначительное влияние на процент промахов L1 и L3 для режимов by_grid и by_column при использовании неоптимального порядка циклов
for x { for y }. Основные характеристики (высокий L3 miss для by_grid, низкий L3 miss для by_column, высокий L1 miss для by_column, низкий L1 miss для by_grid) сохраняются. -
Уменьшение общего времени выполнения по сравнению с аналогичными тестами для изображения 1226x2001 ожидаемо из-за большего числа пикселей.
Графики представлены в данной директории.
Проверка влияния инвертированного порядка циклов (for y { for x { ... } }) на производительность и использование кэша.
// Новый, потенциально более эффективный порядок циклов
for (y = spec->start_row; y < spec->end_row; y++) {
for (x = spec->start_column; x < spec->end_column; x++) {
// ... вычисление свертки для pixel[y][x] ...
}
}-
Наблюдается заметное общее ускорение по сравнению с Тестирования №3 для всех методов разбиения. Это прямое следствие улучшения локальности доступа к памяти.
-
При анализе с помощью утилиты perf было замечена значительная разница между Тестирование №2 и №3. Для примера был взят
comp-mode=by_columnиblock=32. Несмотря на то, что время выполнения отличается не больше чем на 10%, другие метрики имеют сильное различие:
| MODE (TEST NUM) | AVG L3 CACHE MISSES % | L1 DCACHE MISSES % | BRANCH MISSES |
|---|---|---|---|
| by_grid (2) | 33 | 0.05 | 0.11 |
| by_grid (3) | 3 | 0.2 | 0.11 |
| by_column(2) | 33 | 0.05 | 0.11 |
| by_column(3) | 3 | 0.2 | 0.11 |
Графики представлены в данной директории.
При последовательном применении нескольких фильтров время выполнения не зависит от порядка их наложения. Это подтверждает предположение, что обработка каждого фильтра не зависит от предыдущих преображений. Следовательно накладные расходы не накапливаются в зависимости от последовательности.
Из-за того, что на графике графике значения выглядят искусственно равными - снизу представлены более детальные данные на 95% доверительном интервале с точностью до десятитысячных:
| ID | COMPOSITION | AVG TIME |
|---|---|---|
| 0 | gb-sh | 0.4647 |
| 1 | sh-gb | 0.4643 |
| 2 | gg-sh | 2.5818 |
| 3 | sh-gg | 2.5817 |
| 4 | mb-sh | 1.0844 |
| 5 | sh-mb | 1.0848 |
Для измерений значений была использована функция gettimeofday(), точность которой 10^(-6).
Вопрос о том, влияют ли конкретные числовые значения в матрице фильтра (при одинаковом размере) на время выполнения, требует дальнейшего отдельного исследования. Теоретически, базовая арифметика свертки не зависит от значений. Однако, нельзя исключать влияние низкоуровневых оптимизаций компилятора или процессора:
- Векторизация (SIMD): Эффективность может слегка зависеть от констант.
- Оптимизации (нули/единицы): Компилятор может упрощать вычисления (пропуск умножения на 0, замена умножения на 1).
Проведённый анализ многопоточной свертки изображений выявил следующие ключевые моменты:
- Попиксельное разбиение неэффективно из-за доминирования накладных расходов на управление потоками.
- Размер фильтра является основным фактором, определяющим вычислительную сложность и время выполнения.
- Порядок циклов итерации по пикселям критически важен для производительности кэша. Для стандартного хранения данных по строкам (row-major) порядок
for y { for x { ... } }значительно эффективнее (~10-30%и более) благодаря лучшему использованию пространственной локальности памяти (подтверждено Тестированием №4). - Выбор оптимального способа разделения (
by_row,by_column,by_grid) и размера блока зависит от архитектуры, геометрии изображения, размера фильтра и, что важно, от используемого порядка циклов. Оптимальный выбор является компромиссом между локальностью доступа, балансом нагрузки и накладными расходами. - Последовательность наложения фильтров не влияет на общее время выполнения (эффекты аддитивны).
- Анализ производительности должен учитывать характеристики кэш-памяти (L1, L2, L3), так как эффективность доступа к данным оказывает огромное влияние на реальное время выполнения, что наглядно продемонстрировано сравнением Тестирования №3 и №4.