1.2 循環交換

數組在內存中是以行主序（row-major order）存儲的，即數組每一行的元素是連續存儲的，而列之間存在跨越?；谶@個特點，在保證矩陣乘法運算結果正確的前提下，可以考慮交換循環順序來提高訪存的空間局部性，從而提高緩存命中率，減少對內存的訪問，最終提升程序性能。

圖1.1展示了三個調換C語言實現的循環順序后數組訪存的模式。其中，圖1.1a對應代碼1.3中采用的i， j， k的循環順序。這里展示的是當完成一次最內層循環的時候，每個矩陣的訪存模式情況。通過圖中所示的訪存模式可以看出，使用k， i， j的循環順序是有利于內存訪問空間局部性的一種實現。代碼1.4是這種循環順序對應的源代碼，它與代碼1.3的主要區別就是交換了循環順序。

圖1.1 矩陣乘法中不同循環順序對內存訪問空間局部性的影響

代碼1.4 交換了循環順序后的矩陣乘法實現

針對不同的循環順序，我們分別實現并進行了性能測量。同時，采用cachegrind工具對程序的訪存行為進行了模擬測量。cachegrind是Valgrind套件中的一個工具，模擬了一個帶有多級緩存的計算機系統，會跟蹤程序的每次內存訪問，并記錄緩存的命中和未命中情況。它還提供了一系列對程序進行性能分析的基本功能，使用該工具進行性能測量和分析的基本命令如下：

從表1.3所示的性能數據可以看出，具有良好訪存模式的k， i， j和i， k， j都取得了較好的性能，同時，由cachegrind仿真測得的最后一級高速緩存（Last Level Cache，LLC）未命中率也較低，說明這兩種模式下對內存的訪問較少。接下來，我們采用結果最好的k， i， j循環順序的實現（即代碼1.4）繼續進行優化。

表1.3 不同循環順序對運行時間和LLC未命中率的影響