加速大量數組相關的計算，visual studio

Question

我想知道什麼最好的辦法可能是加速大量的數組計算。可以說我有這樣的場景：

int template_t[] = {1, 2, 3, 4, 5, 6, ...., 125}; 
int image[3200][5600]; 
int template_image[3200][5600]; 

for(int i = 0; i < 3200; i++) { 
    for(int j = 0; j < 5600; j++) { 

     // iterate over template to find template value per pixel 
     for(int h = 0; h < template_length; h++) 
      template_image[i][j] += template_t[h] * image[i][j]; 

    } 
} 

當然我的情況要複雜得多，但同樣的想法適用。我有一個大的數組代表圖像中的像素，我需要將一些模板數組應用到每個像素來計算要放置在模板圖像中的值。

我已經考慮過幾種方法可以加快這：

• SIMD指令？然而，我似乎無法找到任何資源在Visual Studio中編寫SIMD特定代碼。
• 並行化 - 儘管我已經完全執行了整個執行過程，所以程序會運行基於X核心的X實例。該程序的輸入是大量的圖像文件，所以這些X實例都將處理單獨的文件。

什麼會給我最大的壓力？感謝您的任何建議！

Answer 1

一個簡單的優化，不應編譯器已經爲你做的，應該是：

int p = template_image[i][j], p2= image[i][j]; 
    // iterate over template to find template value per pixel 
    for(int h = 0; h < template_length; h++) 
     p += template_t[h] * p2; 

    template[i][j]= p; 

在此尋找進一步與您的模板爲1，2，3，...... 125的定義，然後p2乘以1 * 2 * 3 * 4 .. * 125，其是恆定的（我們稱之爲CT）等：

for (h.. 
    template_image[i][j] += template_t[h] * image[i][j]; 

相當於

template_image[i][j] += CT * image[i][j]; 

所以算法變成：

#define CT 1*2*3*4*5*6*7...*125 // must stil lbe completed 
int image[3200][5600]; 
int template_image[3200][5600]; 

for(int i = 0; i < 3200; i++) { 
    for(int j = 0; j < 5600; j++) { 
     template_image[i][j] += CT * image[i][j]; 
    } 
} 

這可以在j被parallellized。

Answer 2

首先，爲類型使用_t名稱，而不是數組。我們來調用數組template_multipliers[]。

如果template_multipliers是const，變量是unsigned，編譯器可以在編譯時對它進行求和，並完全優化內部循環。

對於gcc，我們也得到了更好的代碼，將template_t的總和從循環中提出。在這種情況下，它甚至可以在編譯時加上int，而不是unsigned int。

簽名溢出是未定義的行爲，這可能是爲什麼gcc有時會錯誤地知道在它正在優化的目標機器上會發生什麼。 （例如，在x86上，它不是你需要避免的東西，即使有些命令在臨時結果中產生了符號溢出，而有些命令卻沒有產生，一系列增加的最終結果並不取決於操作的順序，gcc doesn'在簽署的情況下，總是要利用加法的相關性）。

這純粹是gcc的限制。您的代碼必須避免源代碼級操作順序中的符號溢出，但是如果編譯器知道您可以通過做更快的其他操作獲得相同的結果，則它可以並且應該。

---

// aligning the arrays makes gcc's asm output *MUCH* shorter: no fully-unrolled prologue/epilogue for handling unaligned elements 
#define DIM1 320 
#define DIM2 1000 
alignas(32) unsigned int image[DIM1][DIM2]; 
alignas(32) unsigned int template_image[DIM1][DIM2]; 

// with const, gcc can sum them at compile time. 
const 
static unsigned int template_multipliers[] = {1, 2, 3, 4, 5, 6, 7, 8, 8, 10, 11, 12, 13, 125}; 
const static int template_length = sizeof(template_multipliers)/sizeof(template_multipliers[0]); 


void loop_hoisted(void) { 
    for(int i = 0; i < DIM1; i++) { 
    for(int j = 0; j < DIM2; j++) { 
     // iterate over template to find template value per pixel 
     unsigned int tmp = 0; 
     for(int h = 0; h < template_length; h++) 
      tmp += template_multipliers[h]; 
     template_image[i][j] += tmp * image[i][j]; 

    } 
    } 
} 

GCC 5.3 -O3 -fverbose-asm -march=haswellauto-vectorizes this與內環：

# gcc inner loop: ymm1 = set1(215) = sum of template_multipliers 
.L2: 
    vpmulld ymm0, ymm1, YMMWORD PTR [rcx+rax] # vect__16.10, tmp115, MEM[base: vectp_image.8_4, index: ivtmp.18_90, offset: 0B] 
    vpaddd ymm0, ymm0, YMMWORD PTR [rdx+rax] # vect__17.12, vect__16.10, MEM[base: vectp_template_image.5_84, index: ivtmp.18_90, offset: 0B] 
    vmovdqa YMMWORD PTR [rdx+rax], ymm0  # MEM[base: vectp_template_image.5_84, index: ivtmp.18_90, offset: 0B], vect__17.12 
    add  rax, 32 # ivtmp.18, 
    cmp  rax, 4000 # ivtmp.18, 
    jne  .L2  #, 

這是英特爾的Haswell內環9稠域的uop，由於pmulld是上的Haswell 2個微指令和後來（即使使用單寄存器尋址模式也不能微熔絲）。這意味着循環每3個時鐘只能運行一次。 gcc可以通過爲目的地使用指針增量來保存2個uops（因此它將以每2個時鐘一次迭代的方式運行），以及src的2寄存器尋址模式（因爲它無論如何都不能微熔絲） 。

請參閱godbolt Compiler Explorer link瞭解OP代碼的修改版本的完整源代碼，該代碼不提升template_multipliers的總和。它使怪異ASM：

unsigned int tmp = template_image[i][j]; 
    for(int h = 0; h < template_length; h++) 
     tmp += template_multipliers[h] * image[i][j]; 
    template_image[i][j] = tmp; 

.L8: # ymm4 is a vector of set1(198) 
    vmovdqa ymm2, YMMWORD PTR [rcx+rax]  # vect__22.42, MEM[base: vectp_image.41_73, index: ivtmp.56_108, offset: 0B] 
    vpaddd ymm1, ymm2, YMMWORD PTR [rdx+rax] # vect__1.47, vect__22.42, MEM[base: vectp_template_image.38_94, index: ivtmp.56_108, offset: 0B] 
    vpmulld ymm0, ymm2, ymm4 # vect__114.43, vect__22.42, tmp110 
    vpslld ymm3, ymm2, 3  # vect__72.45, vect__22.42, 
    vpaddd ymm0, ymm1, ymm0 # vect__2.48, vect__1.47, vect__114.43 
    vpaddd ymm0, ymm0, ymm3 # vect__29.49, vect__2.48, vect__72.45 
    vpaddd ymm0, ymm0, ymm3 # vect_tmp_115.50, vect__29.49, vect__72.45 
    vmovdqa YMMWORD PTR [rdx+rax], ymm0  # MEM[base: vectp_template_image.38_94, index: ivtmp.56_108, offset: 0B], vect_tmp_115.50 
    add  rax, 32 # ivtmp.56, 
    cmp  rax, 4000 # ivtmp.56, 
    jne  .L8  #, 

它做通過循環每次一些template_multipliers求和的。循環中的相加數根據數組中的值而改變（而不僅僅是數值）。

---

大多數這些優化應適用於MSVC，除非整個程序的鏈接時優化允許它這樣做的總和那麼即使template_multipliers是非常量。