CPU矩阵矩阵乘法时间

Question

我正在尝试决定是应该同时处理还是顺序处理几个相似但独立的问题（可能在不同计算机上并行处理）。为了做出决定，我需要比较以下操作的 cpu 次：

time_1 是计算 X(with shape (n,p)) @ b (with shape (p,1)) 的时间。
time_k 是计算 X(with shape (n,p)) @ B (with shape (p,k)) 的时间。

其中 X、b 和 B 是随机矩阵。两个操作之间的区别是第二个矩阵的宽度。

天真地，我们期望 time_k = k x time_1。使用更快的矩阵乘法算法（Strassen 算法、Coppersmith–Winograd 算法），time_k 可能小于 k x time_1，但这些算法的复杂性仍然比我在实践中观察到的要大得多。因此我的问题是：如何解释这两个计算在 cpu 时间方面的巨大差异？

我使用的代码如下：

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

您不仅仅是在计时乘法运算。 time.time() 需要时间才能完成。

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

当乘以尝试次数 (10000) 时，实例数就变成了显着的开销，对于 n=100，您实际上是在比较对 time.time() 的 1.000.000 次调用与 100 个常规 numpy数组乘法。

为了快速基准测试，Python 提供了一个没有这个问题的专用模块：请参阅 timeit

Answer 2

这个细节原因很复杂。你知道当 PC 运行 X @ b 时，它会执行许多其他需要的指令，也许 load data from RAM to cache 等等。也就是说，成本时间包含两部分——Cost_A代表的CPU中的'real calculate instructions'和Cost_B代表的'other required instructions'。我有一个想法，只是我的猜测，它是 Cost_B 导致 time_k << k x time_1.

因为b的shape很小（比如1000 x 1），'other required instructions'相对耗时最多。因为 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

更多，我在linux中用pref做了一组实验。对于 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()

我已经将输出处理到 table A，如下所示。

我做一个简单的分析，我将邻居实验中的操作（点赞，缓存未命中）次数的误差除以 time elapsed(seconds) 的误差。然后，得到如下table B。从table可以发现，随着b的形状增加，形状与花费时间的线性关系更加明显。而导致time_k << k x time_1的主要原因可能是cache misses（将数据从RAM加载到缓存），因为它首先稳定。

CPU矩阵矩阵乘法时间

CPU Time for matrix matrix multiplication

python

time

numpy

matrix

multiplication