Является ли алгоритмический анализ путем подсчета флопов устаревшим?

На моих курсах по численному анализу я научился анализировать эффективность алгоритмов, подсчитывая количество операций с плавающей запятой (флоп), которые им требуются, в зависимости от размера проблемы. Например, в тексте Trefethen & Bau о числовой линейной алгебре есть даже трехмерные изображения подсчетов флопа.

Сейчас модно говорить, что «флопы свободны», потому что задержка памяти для извлечения чего-либо, не находящегося в кеше, намного превышает стоимость флопа. Но мы все еще учим студентов считать флопы, по крайней мере, на курсах численного анализа. Должны ли мы учить их считать доступ к памяти? Нужно ли нам писать новые учебники? Или доступ к памяти слишком специфичен для конкретной машины, чтобы тратить на нее время? Какова будет долгосрочная тенденция с точки зрения того, являются ли провалы или доступ к памяти узким местом?

Примечание: некоторые из приведенных ниже ответов, похоже, отвечают на другой вопрос, такой как «Должен ли я одержимо переписать свою реализацию, чтобы сохранить несколько провалов или улучшить производительность кэша?» Но то, что я спрашиваю, больше похоже на « Полезно ли оценивать алгоритмическую сложность с точки зрения арифметических операций или обращений к памяти ?»

Я думаю, что (первый порядок) правильно сделать, это посмотреть на соотношение флопов и байтов, необходимое в алгоритме, который я называю . Пусть - максимальная частота флопа процессора, а - максимальная полоса пропускания. Если , то алгоритм будет ограничен по пропускной способности. Если , алгоритм ограничен на флопе.$\beta$$F_{\mathrm{max}}$$B_{\mathrm{max}}$$\frac{F_{\mathrm{max}}}{\beta} > B_{\mathrm{max}}$$B_{\mathrm{max}}\beta > F_{\mathrm{max}}$

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

• Сколько локальной памяти требуется

• Сколько возможного параллелизма у нас

Затем вы можете начать анализировать алгоритмы для современного оборудования.

Я не понимаю, почему нужно быть «победителем»; это не игра с нулевой суммой, где количество флопов и доступ к памяти должны заглушить другого. Вы можете научить их обоих, и я думаю, что они оба используют. В конце концов, трудно сказать, что ваш алгоритм с обращениями к памяти обязательно будет быстрее, чем ваш алгоритм с доступами. Все зависит от относительной стоимости различных частей (этот надоедливый фактор, который мы всегда игнорируем в этих анализах!).O ( N $O(N^4)$$O(N)$$O(N \log N)$$O(N^2)$

В более широком плане, я думаю, что анализ алгоритмической производительности должен быть «всеобъемлющим». Если мы учим людей быть настоящими разработчиками и пользователями высокопроизводительных вычислений, им необходимо понять, какова стоимость программирования в реальном мире. Модели абстрактного анализа, которые мы имеем, не учитывают время программиста. Мы должны думать с точки зрения «общего времени до решения», а не просто подсчета флопов и алгоритмической эффективности. Нет смысла тратить три или четыре дня программиста на переписывание подпрограммы, которая сэкономит одну секунду компьютерного времени на задание, если вы не планируете выполнить несколько миллионов вычислений. Точно так же инвестиции в несколько дней, чтобы сэкономить час или два вычислительного времени, быстро окупаются. Этот новый алгоритм может быть удивительным,

Как уже отмечали другие, ответ, конечно, зависит от того, является ли узкое место ЦП или пропускная способность памяти. Для многих алгоритмов, которые работают с некоторым набором данных произвольного размера, узким местом обычно является пропускная способность памяти, поскольку набор данных не помещается в кэш ЦП.

Более того, Кнут упоминает, что анализ доступа к памяти с большей вероятностью выдержит испытание временем, предположительно потому, что он относительно прост (даже с учетом удобства кэширования) по сравнению со сложностями современных конвейеров ЦП и прогнозированием ветвлений.

Кнут использует термин gigamems в томе 4A TAOCP при анализе BDD. Я не уверен, использует ли он это в предыдущих томах. Он сделал вышеупомянутый комментарий о том, как выдержать испытание временем в своей ежегодной рождественской лекции в 2010 году.

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

То, как вы определяете стоимость алгоритма, зависит от того, на каком «уровне» научных вычислений вы работаете, и какой (узкий или широкий) класс проблем вы рассматриваете.

Если вы подумаете об оптимизации кэша, это, безусловно, больше относится, например, к реализации пакетов числовой линейной алгебры, таких как BLAS, и аналогичных библиотек. Так что это относится к низкоуровневой оптимизации, и это хорошо, если у вас есть фиксированный алгоритм для конкретной задачи и с достаточными ограничениями на входе. Например, оптимизация кэша может иметь значение для быстрой реализации итерации сопряженного градиента, если обещано, что матрица будет достаточно разреженной.

С другой стороны, чем шире класс задач, тем меньше вы можете предсказать фактические вычисления (например, вы не знаете, насколько разреженными будут входные матрицы вашей реализации CG). Чем шире класс машин, на которых должна работать ваша программа, тем меньше вы можете предсказать архитектуру Cache.

Кроме того, на более высоком уровне научных вычислений может оказаться более актуальным изменение структуры проблемы. Например, если вы тратите время на поиск хорошего предобусловливателя для линейной системы уравнений, этот вид оптимизации обычно превосходит любую низкоуровневую оптимизацию, поскольку количество итераций резко сокращается.

В conclusio оптимизация кэша полезна только в том случае, если нечего оптимизировать за счет параллелизма и уменьшения асимптотического числа FLOP.

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

Я всегда отказывался даже думать о подсчете флопов, обращений к памяти или о том, что у вас есть. Это концепция 1960-х годов, когда то, что вы делали, было в значительной степени дано, и только то, как вы это делали, зависело от алгоритмической оптимизации. Подумайте о решении проблемы конечных элементов на равномерной сетке XYZ, используя либо гауссовское исключение итерации Якоби.

Теперь вы можете оптимизировать это до чертиков и сэкономить несколько флопов, получая 10% времени выполнения. Или вы можете подумать о реализации многосеточного метода и оптимальной предварительной обработки блоков с коэффициентом 10 во время выполнения. Это то, чему мы должны обучать наших учеников - подумать о том, какие сложные внешние алгоритмы могут помочь вам при поиске лучшего внутреннего алгоритма. У вашего босса (Киз) есть эти слайды о прогрессе в вычислениях MHD, которые делают эту точку зрения довольно очевидной.

Да, устарел. Алгоритмический анализ с помощью флопов или любого другого метода полезен только в качестве абстрактной модели машины при рассмотрении масштаба рассматриваемой проблемы. Фактическая производительность зависит как от реализации, так и от аппаратного обеспечения, и применимость любой абстрактной модели для последней к реальности со временем уменьшается. Например, когда вы продолжаете распараллеливать реализацию сложного алгоритма, такого как молекулярная динамика, разные аспекты становятся ограничивающими скорость на разных аппаратных средствах, а алгоритмический анализ не имеет ничего общего с наблюдениями. В одном смысле единственной важной вещью является измерение производительности реализации алгоритма (ов) для рассматриваемого аппаратного типа (типов).

Полезны ли такие абстракции в качестве инструмента обучения? Да, как и многие модели, используемые для обучения, они полезны, если они размещены вместе с пониманием ограничений модели. Классическая механика хороша до тех пор, пока вы понимаете, что она не будет работать на масштабах малого расстояния или большой скорости ...

На самом деле не отвечаю на ваш вопрос, но добавлю еще одну переменную, которую нужно учесть: особенности языка программирования. Например, Python sortиспользует алгоритм Timsort , который разработан (среди других приятных свойств), чтобы минимизировать количество сравнений, которые могут быть потенциально медленными для объектов Python. С другой стороны, сравнивать два числа с плавающей точкой в ​​C ++ очень быстро, но их замена обходится дороже, поэтому они используют другие алгоритмы.

Другими примерами являются динамическое распределение памяти (тривиально в списке Python, быстрое как во время выполнения, так и во время разработки, просто .append()), против FORTRAN или C, где, хотя это возможно и быстрее при правильной реализации, это требует значительно больше времени на программирование и мозг. Смотрите Python быстрее, чем Фортран.