J'essaie de décider si plusieurs problèmes similaires mais indépendants doivent être traités simultanément ou séquentiellement (éventuellement en parallèle sur différents ordinateurs). Pour me décider, j'ai besoin de comparer les temps cpu des opérations suivantes :

  • time_1 est le temps de calcul de X(avec forme (n,p)) @ b (avec forme (p,1)).

  • time_k est le temps de calcul de X(avec forme (n,p)) @ B (avec forme (p,k)).

Où X, b et B sont des matrices aléatoires. La différence entre les deux opérations est la largeur de la deuxième matrice.

Naïvement, nous nous attendons à ce que time_k = k x time_1. Avec des algorithmes de multiplication matricielle plus rapides (algorithme de Strassen, algorithme de Coppersmith-Winograd), time_k pourrait être plus petit que k x time_1 mais la complexité de ces algorithmes reste bien plus grande que ce que j'ai observé en pratique. Ma question est donc : Comment expliquer la grande différence en termes de temps cpu pour ces deux calculs ?

Comparison of the CPU times in terms of the width k

Le code que j'ai utilisé est le suivant :

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()
2
Kokli 19 mars 2019 à 12:59

2 réponses

Meilleure réponse

Ce détail de la raison est très complexe. Vous savez que lorsque le PC exécute le X @ b, il exécutera de nombreuses autres instructions requises, peut-être load data from RAM to cache et ainsi de suite. En d'autres termes, le temps de coût contient deux parties : les « instructions de calcul réelles » dans le processeur représentées par Cost_A et les « autres instructions requises » représentées par Cost_B. J'ai une idée, juste ma conjecture, que c'est le Cost_B plomb à time_k << k x time_1.

Comme la forme de b est petite (par exemple 1000 x 1), les « autres instructions requises » coûtent relativement le plus de temps. Car la forme de b est énorme (par exemple 1000 x 10000), elle est relativement petite. Le groupe d'expériences suivant pourrait donner une preuve moins rigoureuse. Nous pouvons voir que lorsque la forme de b augmente de (1000 x 1) à (1000 x ) le temps de coût augmente très lentement.

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

Pour en savoir plus, je fais une série d'expériences avec pref sous Linux. Pour le pref, le Cost_B peut-être plus gros. J'ai 8 fichiers python, le premier est le suivant.

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

broken2()

J'ai traité la sortie vers le tableau A, comme suit. entrez la description de l'image ici

Je fais une analyse simple que je divise l'erreur du nombre d'opérations (j'aime, cache-miss) dans les expériences voisines par l'erreur de time elapsed(seconds) . Ensuite, j'obtiens le tableau B suivant. À partir du tableau, nous pouvons constater que lorsque la forme de b augmente, la relation linéaire entre la forme et le coût du temps est plus évidente. Et peut-être que la principale raison qui a conduit à time_k << k x time_1 est cache misses (charge les données de la RAM vers le cache), car il s'est d'abord stabilisé.

enter image description here

1
Happy Boy 26 mars 2019 à 01:40

Vous n'êtes pas seulement en train de chronométrer l'opération de multiplication. time.time() prend du temps.

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

Lorsqu'il est multiplié par le nombre d'essais (10000), le nombre d'instances devient un surcoût important, pour n = 100, vous comparez en fait ce qui est 1.000.000 appels à time.time() à 100 multiplications de tableau numpy régulières.

Pour un benchmark rapide, Python fournit un module dédié qui n'a pas ce problème : voir timeit< /a>

1
Arthur Hv 19 mars 2019 à 13:02