Время процессора для умножения матричной матрицы

Question

Я пытаюсь решить, стоит ли решать несколько похожих, но независимых проблем одновременно или последовательно (возможно, параллельно на разных компьютерах). Чтобы принять решение, мне нужно сравнить время процессора следующих операций:

• time_1 - время для вычисления X (с формой (n, p)) @ b (с формой (p, 1)).

• time_k - это время для вычисления X (с формой (n, p)) @ B (с формой (p, k)).

где X, b и B - случайные матрицы. Разница между этими двумя операциями заключается в ширине второй матрицы.

Наивно, мы ожидаем, что time_k = k x time_1. При использовании более быстрых алгоритмов умножения матриц (алгоритм Штрассена, алгоритм Копперсмита – Винограда) time_k может быть меньше, чем k x time_1, но сложность этих алгоритмов остается намного больше, чем я наблюдал на практике. Поэтому мой вопрос: Как объяснить большую разницу с точки зрения времени процессора для этих двух вычислений?

Код, который я использовал, следующий:

import time
import numpy as np
import matplotlib.pyplot as plt

p     = 100
width = np.concatenate([np.arange(1, 20), np.arange(20, 100, 10), np.arange(100, 4000, 100)]).astype(int)

mean_time = []
for nk, kk in enumerate(width):
    timings = []
    nb_tests = 10000 if kk <= 300 else 100
    for ni, ii in enumerate(range(nb_tests)):
        print('\r[', nk, '/', len(width), ', ',  ni, '/', nb_tests, ']', end = '')
        x     = np.random.randn(p).reshape((1, -1))
        coef  = np.random.randn(p, kk)
        d     = np.zeros((1, kk))
        start = time.time()
        d[:]  = x @ coef
        end   = time.time()
        timings.append(end - start)

    mean_time.append(np.mean(timings))

mean_time = np.array(mean_time)


fig, ax = plt.subplots(figsize =(14,8))
plt.plot(width, mean_time, label =  'mean(time\_k)')
plt.plot(width, width*mean_time[0], label = 'k*mean(time\_1)')
plt.legend()
plt.xlabel('k')
plt.ylabel('time (sec)')
plt.show()

Answer 1

Эта деталь причины очень сложна. Вы знаете, что когда ПК запускает X @ b, он выполняет много других необходимых инструкций, возможно, load data from RAM to cache и так далее. Другими словами, время затрат состоит из двух частей - «реальные инструкции вычисления» в ЦП, представленные Cost_A, и «другие обязательные инструкции», представленные Cost_B. У меня есть идея, только мое предположение, что это Cost_B ведет к time_k << k x time_1.

Поскольку форма b мала (например, 1000 x 1), «другие необходимые инструкции» стоят относительно больше времени. Поскольку форма b огромна (например, 1000 x 10000), она относительно мала. Следующая группа экспериментов может дать менее строгое доказательство. Мы можем видеть, что когда форма b увеличивается от (1000 x 1) до (1000 x), время затрат увеличивается очень медленно.

import numpy as np
import time

X = np.random.random((1000, 1000))

b = np.random.random((1000, 1))
b3 = np.random.random((1000, 3))
b5 = np.random.random((1000, 5))
b7 = np.random.random((1000, 7))
b9 = np.random.random((1000, 9))
b10 = np.random.random((1000, 10))
b30 = np.random.random((1000, 30))
b60 = np.random.random((1000, 60))
b100 = np.random.random((1000, 100))
b1000 = np.random.random((1000, 1000))

def test_cost(X, b):
    begin = time.time()
    for i in range(100):
        _ = X @ b
    end = time.time()
    print((end-begin)/100.)

test_cost(X, b)
test_cost(X, b3)
test_cost(X, b5)
test_cost(X, b7)
test_cost(X, b9)
test_cost(X, b10)
test_cost(X, b30)
test_cost(X, b60) 
test_cost(X, b100)
test_cost(X, b1000)

output:
0.0003210139274597168
0.00040063619613647463
0.0002452659606933594
0.00026523590087890625
0.0002449488639831543
0.00024344682693481446
0.00040068864822387693
0.000691361427307129
0.0011700797080993653
0.009680757522583008

Более подробно я провожу серию экспериментов с pref в linux. Для pref, Cost_B может быть более большим. У меня есть 8 файлов Python, первый из которых выглядит следующим образом.

import numpy as np
import time
def broken2():
    mtx = np.random.random((1, 1000))
    c = None
    c = mtx ** 2

broken2()

Я обработал вывод в таблицу A следующим образом.

Я делаю простой анализ, который делю ошибку числа операций (лайков, пропусков кэша) в соседних экспериментах на ошибку time elapsed(seconds). Затем я получаю следующую таблицу B. Из таблицы мы можем найти, что по мере увеличения формы b линейная зависимость между формой и временем затрат становится более очевидной. И, может быть, главная причина, по которой time_k << k x time_1 - это cache misses (загрузка данных из ОЗУ в кэш), для него сначала стабилизируется .

Answer 2

Вы не только операция умножения времени.time.time() требуется время для завершения.

>>> print(time.time() - time.time())
-9.53674316406e-07

При умножении на количество попыток (10000) количество экземпляров становится значительным, поскольку при n = 100 вы фактически сравниваете то, что составляет 1000.000 обращений к time.time() до 100 умножений обычных числовых массивов.

Для быстрого бенчмаркинга, Python предоставляет специальный модуль, у которого нет этой проблемы: см. timeit