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

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

$F_{op} \;::\;$входные размеры$\rightarrow$время выполнения

для таких операций, как матричное умножение, поэлементное сложение, треугольное решение и т. д.

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

Вопросов:

1. Это предположение реалистично? Является ли функция времени выполнения почти детерминированной?
2. Можно ли предположить, что эта функция будет полиномиальной по размерам входов? (т.е. я ожидаю, что умножение плотной матрицы будет выглядеть примерно так:$\alpha n\times k\times m$ за $A_{nk}\times B_{km}$ а также $\alpha$ некоторый скалярный коэффициент)
3. Есть ли где-то уже существующая работа по этому вопросу?
4. Мой текущий план состоит в том, чтобы сделать регрессию наименьших квадратов с $L_1$регуляризатором. Любые другие предложения?

Изменить: Чтобы было ясно, я ищу среды выполнения, а не FLOP или какие-либо другие общие показатели производительности. Я хочу ограничиться одной конкретной архитектурой.

Я недавно работал именно над этой темой. Возможно, вы захотите взглянуть на нашу статью: http://arxiv.org/abs/1209.2364 .

Почему вы заинтересованы в прогнозировании линейной алгебры во время выполнения? Вы собираетесь использовать модель для определенной цели?

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

Например, поиск «производительности DGEMM» приводит к следующему: http://math-atlas.sourceforge.net/timing/3_5_10/index.html .

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

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