Skip to content

Latest commit

 

History

History
185 lines (133 loc) · 24.7 KB

QMT-mode-analysis.md

File metadata and controls

185 lines (133 loc) · 24.7 KB

Анализ производительности многопоточной свертки на основе очереди (Queue-based Convolution)

Содержание

  1. Введение
  2. Параметры и среда тестирования
  3. Этап 1: Анализ производительности реализации с фиксированной очередью
  4. Этап 2: Реализация с настраиваемой очередью
  5. Общие выводы и заключение
  6. Рекомендации по использованию

Введение

Анализ охватывает две опции реализации: с жестко заданным малым размером очереди и с настраиваемыми параметрами очереди. Используются данные из графиков времени выполнения/блокировок и детальные метрики производительности, собранные с помощью perf stat и perf report.

Архитектура Reader-Worker-Writer

  • Reader: Читает BMP-файлы, помещает во входную очередь (input_q).
  • Worker: Извлекает изображения из input_q, выполняет свертку, помещает результат в выходную очередь (output_q).
  • Writer: Извлекает результаты из output_q, записывает в файл.
  • Синхронизация: Потокобезопасные очереди (input_q, output_q), барьер для Reader'ов, атомарные счетчики для файлов.

Реализация очередей

  • Размер массива очереди (capacity) и лимит памяти (max_mem_usage_mb в МБ) задаются через аргументы командной строки (--queue-size, --queue-mem). Дефолтные значения - DEFAULT_QUEUE_CAP=20 и DEFAULT_QUEUE_MEM_LIMIT=500.
  • Логика queue_push: блокировка происходит, если (1) достигнута capacity ИЛИ (2) добавление нового элемента превысит max_mem_usage_mb (и очередь не пуста). Приоритет отдается лимиту памяти при принятии решения о блокировке, если capacity достаточно велико.
  • Расчет используемой памяти ведется в мегабайтах (estimate_image_memory_mb) с округлением вверх.

Параметры и среда тестирования

  • Изображения:
    • Этап 1 (Графики, ранний perf): image4.bmp (1242x1227).
    • Этап 2 (perf stat, perf report): image6.bmp (4480x6720).
  • Количество изображений: Варьировалось (6 для раннего perf, 17 для позднего perf, 20 для графиков).
  • Размер очереди: Варьировалось (2 для большого тестирования производительности с графиками - сделано для более детального отслеживания зависимостей и узких мест, 1-8 при тестировании с помощью perf)
  • Повторы: 25.
  • Фильтр: gg (15x15).
  • Параметры Worker'а: COMPUTE_MODE=by_row, BLOCK_SIZE=5.
  • Метрики: Графики Avg Thread Time/Avg Queue Ops Time, perf stat -d, perf report -g graph,0.5.
  • Среда: Intel Core i7 4790 (x86-64, 8 ядер, 3.6 ГГц), GCC 14.2.1, режим CPU performance.

Этап 1: Анализ производительности реализации с фиксированной очередью

Анализ соотношения потоков

Соотношение R-W-W является ключевым фактором, определяющим производительность и характер узких мест.

  • Mix с малым числом Worker'ов (e.g., 1-1-1, 2-1-1): Worker является узким местом. Один Worker не успевает обрабатывать данные с той скоростью, с которой их может поставлять Reader и потреблять Writer (особенно если их >1). Reader быстро заполняет input_q, а Writer часто простаивает, ожидая данные в output_q.

  • Mix с большим числом Worker'ов (e.g., 1-4-4, 1-6-6): Узкое место смещается на стадии ввода/вывода. Один Reader не успевает загружать данные для множества Worker'ов, или один Writer не успевает записывать результаты их работы. Worker'ы часто простаивают в ожидании данных (QPOP из input_q) или в ожидании освобождения места в выходной очереди (QPUSH в output_q).

  • Сбалансированные mix'ы (e.g., 2-2-2, 3-3-3, 5-5-5): При малом количестве потоков (2-2-2, 3-3-3) система может быть относительно сбалансирована, но ограничена абсолютной производительностью CPU и IO. При большом количестве потоков (5-5-5) узким местом становится сама инфраструктура очередей (конкуренция за мьютексы) или достижение пределов пропускной способности аппаратного обеспечения (дисковая подсистема, контроллер памяти, количество ядер). Малый размер очередей усугубляет эту проблему, вызывая частые блокировки даже при теоретически сбалансированных стадиях, обязывая потоки ожидать.

  • Потенциально несбалансированные mix'ы (e.g., 1-2-1, 1-1-2, 2-1-1, 1-2-2, 3-2-2, 2-3-3, 1-3-3): Например, 3-2-2 может быть выгоднее 2-2-2, если чтение медленнее обработки и записи (что и происходит в нашем случае). 2-3-3 может быть лучше, если обработка самая медленная. Графики показывают вариативность результатов для этих смесей.

Графики представлены в данной директории.

Анализ времени выполнения потоков (Reader, Worker, Writer)

График "Comparison of Avg Thread Execution Times" показывает среднее время, затраченное потоком одного типа на выполнение одной итерации своей основной задачи (чтение файла, обработка изображения, запись файла). Важно: Это время включает саму работу (I/O, вычисления) и возможные внутренние ожидания, но не включает время явной блокировки на queue_push/queue_pop, которое измеряется отдельно.

  • Worker Time: Зависит от сложности фильтра (gg 15x15 - ресурсоемкий), размера изображения и эффективности compute_mode. Среднее время одного Worker'а закономерно уменьшается при увеличении их общего числа (работа распределяется), как видно при переходе от 1-1-1 к 1-6-6. Однако, это не означает пропорционального ускорения всей системы, если другие стадии отстают.
  • Reader Time: В основном определяется скоростью чтения фала и накладными расходами на парсинг BMP. Если Reader один (1-X-X), его время выполнения становится потенциальным пределом скорости для всего конвейера.
  • Writer Time: Зависит от скорости записи в файл и формирования BMP. Аналогично Reader'у, если Writer один (X-X-1), его производительность ограничивает общую пропускную способность.

Графики представлены в данной директории.

Анализ Времени Блокировок на Операциях с Очередью (QPOP, QPUSH Block Time)

График "Comparison of Avg Queue Ops Times" – ключевой для понимания дисбаланса конвейера. Он показывает среднее время, которое потоки проводили в состоянии ожидания (pthread_cond_wait или pthread_cond_timedwait) при попытке доступа к очереди.

  • QPUSH Block Time (Светло-голубой): Очередь полна.

    • Reader блокируется на QPUSH в input_q: Worker'ы не успевают забирать изображения. Это происходит, когда Worker'ов мало или они медленные (2-1-1, 1-1-1).
    • Worker блокируется на QPUSH в output_q: Writer'ы не успевают записывать результаты. Это происходит, когда Writer'ов мало или они медленные (1-6-1 - гипотетически, 1-1-1 если запись медленная).

  • QPOP Block Time (Темно-синий): Очередь пуста.

    • Worker блокируется на QPOP из input_q: Reader'ы не успевают читать файлы. Характерно для смесей с малым числом Reader'ов и быстрыми Worker'ами (1-6-6, 1-4-4).
    • Writer блокируется на QPOP из output_q: Worker'ы не успевают обрабатывать изображения. Характерно для смесей с малым числом Worker'ов (2-1-1, 1-1-1).

Вывод по очередям: Экстремально малый размер очереди (DEFAULT_QUEUE_CAP=2) является основной причиной высоких времен блокировок и низкой утилизации потоков во многих конфигурациях. Время QPOP в целом ниже QPUSH, но все же заметно во многих конфигурациях (1-6-6, 1-1-1, 2-1-1), подтверждая, что потребители часто ожидают данные. Также графиках видны очень высокие значения QPUSH во многих mix'ах (2-1-1, 2-2-2, 2-2-3, 3-2-2, 5-5-5). Даже небольшой временный дисбаланс приводит к заполнению очереди и блокировке производителя. Система работает в режиме "тугой связи", где производительность сильно ограничена необходимостью частой синхронизации.

Графики представлены в данной директории.

Выводы этапа 1

Исходная реализация страдала от серьезного ограничения производительности из-за DEFAULT_QUEUE_CAP=2. Это приводило к частым блокировкам, низкой утилизации CPU и маскировало влияние других факторов, таких как compute_mode. Требовалось увеличить гибкость управления очередью.

Этап 2: Реализация с настраиваемой очередью

Описание изменений

Введены параметры --queue-size (физическая емкость массива) и --queue-mem (лимит памяти в МБ). Очередь блокируется при достижении capacity ИЛИ превышении лимита памяти (если не пуста). Расчет памяти ведется в МБ с округлением вверх в функции estimate_image_memory.

Введение

Тесты проводились на image6.bmp и image4.bmp. --queue-mem=500, чтобы не быть основным лимитом в тестах с queue-size 1-8.

Влияние queue-size при 6 Worker потоках

(На основе данных perf stat для image6.bmp)

RWW Mix queue-size Время (с) CPU Util IPC Анализ
6,6,1 1 129.5 5.120 2.10 База для q=1
6,6,1 2 130.8 5.097 2.10 Нет изменений
6,6,1 4 124.2 5.387 2.09 Небольшое улучшение (выброс или оптимум?)
6,6,1 8 127.6 5.252 2.10 Нет значимых изменений
6,6,6 1 126.0 5.241 2.10 Сравнение с 6,6,1 - Writer'ы не влияют
6,6,6 8 128.8 5.178 2.09 queue-size 1 vs 8 - нет разницы
4,6,4 1 128.4 5.197 2.10 Сравнение с 6,6,6 - Reader'ы не влияют (при 6W)
4,6,4 8 129.1 5.168 2.08 queue-size 1 vs 8 - нет разницы
2,6,4 1 134.1 4.979 2.07 Чуть медленнее (2 Reader'а - предел?)
2,6,4 8 130.5 5.125 2.08 queue-size 1 vs 8 - нет разницы

Вывод: Для большого изображения и 6 Worker'ов, queue-size (1-8) почти не влияет. Производительность стабильна ~125-130с, утилизация CPU ~5.1-5.4. Число Reader/Writer'ов (при >=2R, >=1W) также слабо влияет. Узкое место не в размере очереди и не в I/O (в этих пределах).

Worker-bound сценарий (6,1,1 mix, большое изображение)

queue-size Время (с) CPU Util IPC Анализ
1 465.6 1.002 2.82 База
2 465.4 1.002 2.82 Нет изменений
4 465.7 1.003 2.82 Нет изменений
8 465.7 1.003 2.82 Нет изменений

Вывод: Подтверждает, что при 1 Worker'е размер очереди не имеет значения.

Анализ perf report (большое изображение, настраиваемая очередь)

Сравнение профилей perf report для RWW 2,4,2 ("Оптимум"), 6,6,6 ("Плато") и 1,8,1 ("Перегрузка").

Сценарий "Оптимальный" (2,4,2)

  • apply_filter: ~53% CPU времени.
  • intel_idle : ~45.6%, система все еще много простаивает.
  • Нет явных пиков на pthread_mutex_lock.
  • Вывод: Производительность ограничена не только вычислениями, но и простоями (ожидание в очередях или I/O).

Сценарий "Плато" (6,6,6)

  • apply_filter: ~71% CPU времени (больше ядер занято вычислениями).
  • intel_idle: Снизился до ~27%.
  • Общее время выполнения не улучшилось. IPC упал (~2.1).
  • Нет явных пиков на pthread_mutex_lock.
  • Вывод: Эффективность снизилась. Больше ядер работают, но медленнее (на цикл). Узкое место - пропускная способность памяти или скрытая конкуренция за мьютексы.

Сценарий "Перегрузка Worker'ами?" (1,8,1)

  • apply_filter: ~95% CPU времени!
  • intel_idle: Минимальный (~3.3%).
  • Общее время не лучше, чем у 6,6,6. IPC самый низкий (~1.55).
  • Вывод: Пропускная способность памяти является явным ограничителем. 8 Worker'ов перегружают подсистему памяти. I/O (1R/1W) также может быть узким местом.

Выводы этапа 2

Анализ данных perf stat и perf report для реализации с настраиваемой очередью, особенно на большом изображении (image6.bmp), позволяет сделать следующие ключевые выводы:

  1. Новая реализация с параметрами --queue-size и --queue-mem позволила преодолеть ограничение MAX_QUEUE_SIZE=2 и дала системе возможность масштабироваться по числу Worker'ов, выявив при этом другие узкие места.
  2. Увеличение числа Worker'ов эффективно до ~4-6 на тестовой системе (8 ядер). Дальнейшее увеличение (до 8) не дает прироста скорости и приводит к значительному падению IPC (с ~2.7 до ~1.55), указывая на достижение предела масштабируемости.
  3. Плато производительности и падение IPC при 6+ Worker'ах, несмотря на рост утилизации CPU и отсутствие явных долгих блокировок мьютексов в perf report, сильно указывают на достижение предела пропускной способности подсистемы памяти или на высокую конкуренцию за разделяемые ресурсы (частые, но короткие конфликты за мьютексы очередей, борьба за кэш-линии).
  4. При достижении плато производительности (6+ Worker'ов), изменение queue-size (>=2) и числа Reader'ов/Writer'ов (в пределах 2-6 R/W) практически не влияет на результат. Это подтверждает, что узкое место уже не в размере буфера очереди или дисковом I/O.

Общие выводы и заключение

Проведенный анализ двух этапов реализации многопоточной свертки на основе очередей показал:

  1. Критичность Размера Буфера: Исходная реализация с MAX_QUEUE_SIZE=2 была неэффективна из-за постоянных блокировок. Переход к настраиваемой очереди с лимитом по памяти (--queue-mem) и достаточной емкостью (--queue-size) является обязательным для производительности.
  2. Оптимальное Распределение Потоков: Существует оптимальное число Worker'ов (~4-6 для данной системы/задачи), превышение которого ведет к падению эффективности из-за системных ограничений.
  3. Лимит Пропускной Способности Памяти/Конкуренции: При оптимальном/высоком числе Worker'ов главным ограничителем становится доступ к памяти и/или конкуренция за мьютексы очередей, а не I/O или размер буфера очереди (если он достаточен).
  4. Необходимость Оптимизации Worker'а: Несмотря на хороший IPC "в моменте", общее время выполнения и простои CPU указывают на необходимость дальнейшей оптимизации, особенно в части локальности данных для снижения нагрузки на память (см. Рекомендации).

Рекомендации по использованию

  1. Использовать Оптимальное Число Worker'ов: Настроить R-W-W Mix так, чтобы число Worker'ов было в районе 4-6 для данной системы.
  2. Настроить Лимит Памяти (--queue-mem): Установить значение, достаточное для буферизации нескольких больших изображений (например, 4 * <размер_image6_в_МБ>), чтобы избежать блокировок по памяти, но не исчерпать RAM.
  3. Установить достаточный queue-size: Значение >= Число Worker'ов (например, 8 или 16) будет достаточным, позволяя лимиту памяти управлять буфером.