Ordre de parcours et tuilage de boucles

Deux boucles imbriquées qui visitent les mêmes cellules d'une matrice peuvent différer d'un facteur sept en défauts de cache, simplement selon la boucle placée à l'intérieur. Ce cours compare la lecture ligne par ligne et colonne par colonne, puis découpe une transposition en tuiles pour qu'un bloc reste dans le cache pendant qu'on l'utilise, et mesure les deux sur une matrice construite à partir de clôtures de SPY.

Une matrice de n lignes et n colonnes est rangée en ordre par lignes. Une boucle qui avance le long d'une ligne, en changeant j, lit des valeurs voisines. Une boucle qui descend une colonne, en changeant i, saute une ligne entière à chaque pas. Les deux boucles ci-dessous visitent les mêmes cellules, l'une avec j à l'intérieur, l'autre avec i. Nous affichons les six premières adresses d'une matrice 4 sur 4 de valeurs float64.

def row_major_trace(n):    return [(i * n + j) * 8 for i in range(n) for j in range(n)]def col_major_trace(n):    return [(i * n + j) * 8 for j in range(n) for i in range(n)]1print("row:", row_major_trace(4)[:6])print("col:", col_major_trace(4)[:6])

row: [0, 8, 16, 24, 32, 40]
col: [0, 32, 64, 96, 8, 40]

1. 1Avec i à l'intérieur, la lecture suivante est une ligne entière plus loin (ici 4 valeurs = 32 octets).

Ligne par ligne, les adresses augmentent de 8 octets, le pas du premier sujet, et une ligne de cache sert huit lectures. Colonne par colonne, elles sautent de 32 octets ici, et de la longueur d'une ligne entière dans une matrice plus grande. Nous comptons maintenant les défauts des deux ordres, dans un petit cache de 4 Ko, pour des matrices de 16 sur 16 à 73 sur 73.

for n in (16, 32, 48, 73):    print(n, "x", n, "row:", count_misses(row_major_trace(n)), "col:", count_misses(col_major_trace(n)))

16 x 16 row: 32 col: 32
32 x 32 row: 128 col: 1024
48 x 48 row: 288 col: 2304
73 x 73 row: 667 col: 4573

Une matrice 16 sur 16 fait 2 Ko et tient dans le cache : après chargement, les deux ordres coûtent 32 défauts, c'est pareil. À partir de 32 sur 32, la matrice ne tient plus, et l'ordre par colonnes échoue à chaque lecture : 1 024 défauts contre 128, un facteur huit, soit les huit valeurs d'une ligne. À 73 sur 73, le facteur est presque sept. La forme des boucles n'a pas changé ; c'est la taille des données qui a changé.

Parfois aucun ordre de boucles n'aide. La transposition B[j][i] = A[i][j] lit A et écrit B, et si les boucles suivent les lignes de A elles descendent les colonnes de B. Quelle que soit la boucle placée à l'intérieur, l'une des deux matrices est parcourue avec un grand pas. Le remède est le tuilage de boucles : traiter la matrice en petites tuiles carrées, pour que les quelques lignes que touche une tuile soient utilisées de nombreuses fois avant d'être évincées.

1. 1
   Choisir une taille de tuile tAssez petite pour qu'une tuile de A et une de B tiennent dans le cache.
2. 2
   Parcourir les tuilesDeux boucles extérieures de pas t : ii et jj donnent le coin d'une tuile.
3. 3
   Travailler dans la tuileLes deux boucles intérieures ne visitent que les t sur t cellules de cette tuile, comme avant.
4. 4
   Passer à la tuile suivanteC'est seulement maintenant que le programme abandonne les lignes de l'ancienne tuile.

Le code ci-dessous liste seulement l'ordre de visite des cellules, pour une matrice 4 sur 4, sans et avec des tuiles de 2. Avec les tuiles, le programme termine le bloc 2 sur 2 en haut à gauche avant de toucher une autre cellule.

def visit_order(n, tile=None):    step = n if tile is None else tile    order = []    for ii in range(0, n, step):1        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    order.append((i, j))    return orderprint("plain:", visit_order(4)[:8])print("tile 2:", visit_order(4, 2)[:8])

plain: [(0, 0), (0, 1), (0, 2), (0, 3), (1, 0), (1, 1), (1, 2), (1, 3)]
tile 2: [(0, 0), (0, 1), (1, 0), (1, 1), (0, 2), (0, 3), (1, 2), (1, 3)]

1. 1Les deux boucles extérieures parcourent les tuiles ; les deux boucles intérieures parcourent l'intérieur d'une tuile.

Passons à la vraie transposition. Nous écrivons la trace des lectures de A et des écritures de B, B étant rangée juste après A, et comptons les défauts pour une matrice 73 sur 73 sans tuile et avec des tuiles de 4, 8, 16 et 32.

def transpose_trace(n, tile=None):    base_b = n * n * 8    step = n if tile is None else tile    trace = []    for ii in range(0, n, step):        for jj in range(0, n, step):            for i in range(ii, min(ii + step, n)):                for j in range(jj, min(jj + step, n)):                    trace.append((i * n + j) * 8)                    trace.append(base_b + (j * n + i) * 8)    return tracefor tile in (None, 4, 8, 16, 32):    print("tile", tile, "misses:", count_misses(transpose_trace(73, tile)))

tile None misses: 5996
tile 4 misses: 2603
tile 8 misses: 2036
tile 16 misses: 1960
tile 32 misses: 1714

Sans tuilage, la transposition échoue 5 996 fois. Avec des tuiles de 4 on tombe déjà à 2 603, et avec des tuiles de 8 à 32 on reste entre 2 036 et 1 714, environ trois fois moins. Une tuile trop petite gaspille les bords des lignes qu'elle charge : le gain croît donc avec la tuile jusqu'à ce qu'elle cesse de tenir.

Le labo suit le cours : les deux ordres de lecture, la trace de la transposition avec une tuile facultative, le décompte des défauts par ordre et par tuile, le choix de la meilleure tuile et l'étude sur la matrice SPY.

• Fonction · questionS'appuie sur
• row_major_trace(n)Quelles adresses une lecture ligne par ligne touche-t-elle ?De l'arithmétique simple
• col_major_trace(n)Et une lecture colonne par colonne ?De l'arithmétique simple
• transpose_trace(n, tile=None)Quelles adresses une transposition touche-t-elle, avec ou sans tuiles ?Quatre boucles imbriquées
• compare_orders(n)De combien l'ordre par colonnes est-il pire ?row_major_tracecol_major_trace
• misses_by_tile(n, tiles)Comment les tuiles changent-elles les défauts de la transposition ?transpose_trace
• best_tile(n, tiles)Quelle tuile est la meilleure ?misses_by_tile
• study(bars)Que gagne le tuilage sur une matrice de clôtures de SPY ?compare_ordersbest_tile

Sujet suivant : le tuilage masque le coût d'un défaut en réutilisant des lignes ; le préchargement le masque en demandant une ligne avant qu'elle soit nécessaire. Dans Préchargement, vous ajoutez un détecteur de pas au cache et voyez quels motifs d'accès il sait prédire, et lesquels, comme une marche aléatoire dans une table, lui échappent.