Правильный способ сравнения стоимости алгоритма

Question

Каков правильный способ сравнить вычислительные ресурсы, требуемые алгоритмами обработки сигналов?

Я говорю о алгоритмах обработки сигналов, которые имеют пределы ошибок против ресурсов по сравнению с задержкой ответа компромисс.

После достижения ошибки и задержки ответа с реализацией алгоритма, я пытаюсь сравнить его эффективность.

В настоящее время я бенчмаркинг различных алгоритмов, кормя их с тем же сигналом и с помощью perf получить ТАСК-часы/MSEG используется на amd64, но это не архитектура агностика.

Промышленность использует MFLOPS/Hz для сравнения процессоров, но как я могу использовать служебные данные памяти (и, возможно, потоки) для конкретной реализации?

Что такое правильный академический измерения, чтобы иметь возможность сказать:

Алгоритм X является N раз лучше, чем Y для достижения P с Q границ.

---

EDIT: Для контекста, алгоритмы обработки сигналов я, занимающихся, являются итерационные те, у которых шаг функции могут быть связаны O (1). Так что BigO кажется бесполезным здесь.

Answer 1

Точные показатели эффективности не являются архитектурными или реализующими агностиками. Различные платформы вычислений DSP будут не только иметь разные абсолютные показатели производительности (МГц/ГГц), но и разные отношения латентности MAC или флопа для распределения коэффициентов и латентности памяти в отношении полосы пропускания, а также многих других опасностей, связанных с производительностью (политика кэширования и потоковой передачи и т. д.) и эффективности (SMP или векторная отправка и т. д.)

В древние времена (VAX, FP-системы, 56000 или более ранние) сырые размножения или подсчеты MAC преобладали над всеми другими ограничениями производительности, так что это стало deacto стоимость метрика. Это уже не всегда является доминирующим фактором для современных конвейерных коротко-векторных многопроцессорных процессоров FPU, которые теперь являются обычными внутри даже игрушек.

Одна из возможностей заключается в том, чтобы угадать платформу (-ы), что ваш алгоритм, скорее всего, будет нацелен, и измерить на этом (скорее всего, похожий на мобильный телефон на основе ARM или систему Raspberry Pi, чем на компьютер AMD IMHO или, возможно, даже OpenCL GPU).

Другая возможность - запустить на академическом симуляторе процессора (RISC V?), Где вы можете включить подробные счетчики производительности (операционные системы каждого отправленного типа, трафик памяти, риск повторного использования реестра и т. Д.). Это будет намного больше точнее, чем любой рабочий стол AMD, где переключение задач ОС, пропуски TLB/MMU и изменения в инициализации и трафике кэша могут вызывать все виды неизвестных изменений при любых измерениях производительности.

Answer 2

Существует несколько правильных ответов на этот вопрос. Вы должны рассмотреть, по крайней мере эти два:

• Компьютерная наука использует O notation - Обычно для измерения требований к обработке, но это просто математика и может быть применен к памяти, а также.
• Бенчмаркинг, как вы это сделали, является правильным способом проверки реализации. Но вы хотите сделать многомерный анализ (например, проверить его на разных форматах, размерах ввода и т. Д.).

В принципе, платформа должна быть постоянным фактором. Но в практике постоянные факторы могут иметь значение.