循環交換與循環平鋪

Question

哪種優化更好，哪種情況下更好？爲什麼？

憑直覺，我越來越覺得循環平鋪將一般 是一個更好的優化。

怎麼樣了下面的例子？ 假設一個緩存在任何時候只能存儲大約20個元素。

Original Loop: 
for(int i = 0; i < 10; i++) 
{ 
    for(int j = 0; j < 1000; j++) 
    { 
     a[i] += a[i]*b[j]; 
    } 
} 

Loop Interchange: 
for(int i = 0; i < 1000; i++) 
{ 
    for(int j = 0; j < 10; j++) 
    { 
     a[j] += a[j]*b[i]; 
    } 
} 

Loop Tiling: 
for(int k = 0; k < 1000; k += 20) 
{ 
    for(int i = 0; i < 10; i++) 
    { 
     for(int j = k; j < min(1000, k+20); j++) 
     { 
      a[i] += a[i]*b[j]; 
     } 
    } 
} 

Answer 1

你在問題中暴露的前兩種情況大致相同。事情會在以下兩種情況下真正改變：

案例1：

for(int i = 0; i < 10; i++) 
{ 
    for(int j = 0; j < 1000; j++) 
    { 
     b[i] += a[i]*a[j]; 
    } 
} 

在這裏，您正在訪問矩陣 「一」 如下：a [0] * A [0]，A [0] *一個1，一個[0] * A [2]，....在大多數結構中，矩陣結構被存儲在存儲器等：A [0] *一個[0]，一個1 *一個[0]，A [ 2] * a [0]（第一行的第一列後跟第一個原始的第二列，....）。設想你的緩存只能存儲5個元素，而你的矩陣是6x6。將存儲在緩存中的元素的第一個「pack」將是[0] * a [0]到a [4] * a [0]。你的第一次訪問不會導致緩存未命中，所以[0] [0]被存儲在緩存中，但第二個是！一個0不存儲在緩存中！然後操作系統將緩存元素包0到4。然後你做第三次訪問：一個[0] * a [2]將再次超出緩存。另一個緩存錯過！

你可以colcude，案例1不是問題的一個很好的解決方案。它會導致大量的高速緩存未命中使我們能夠避免改變代碼如下：

案例2：

for(int i = 0; i < 10; i++) 
    { 
     for(int j = 0; j < 1000; j++) 
     { 
      b[i] += a[i]*a[j]; 
     } 
    } 

在這裏，你可以看到，我們正在訪問矩陣，因爲它是存儲在內存中。因此它比情況要好得多（快）1.

關於你張貼了關於循環平鋪，環瓷磚也循環展開第三代碼，在大多數情況下，編譯器優化automaticaly。 Here's a very interesting post in stackoverflow explaining these two techniques;

希望它能幫助！ （我的英語很抱歉，我不是一個母語）