分支的向量化

If轉(zhuǎn)換是向量化控制依賴最常用的方法，可以將控制依賴轉(zhuǎn)換為數(shù)據(jù)依賴，其需要借助于向量條件選擇指令完成向量指令生成。向量選擇指令select的格式如圖所示：

dst = select (src1，src2， mask)，指令有三個參數(shù)，其中mask為掩碼，src1和src2是兩個源操作數(shù)。當(dāng)掩碼位置的值為1時，取src2的值賦給dst，否則將src1的值賦給dst。

當(dāng)程序的指令執(zhí)行順序和分支結(jié)果相關(guān)時會形成控制依賴，其存在會影響向量化的開展，是向量化時需要重點考慮的依賴形式之一，本節(jié)將介紹向量化時存在分支所導(dǎo)致的控制依賴的處理方法。

原始代碼：

經(jīng)過if轉(zhuǎn)換后的代碼：

向量化是根據(jù)條件表達式進行改寫的，對于滿足條件的進行與操作，對于不滿足條件的取反。如果程序中有多層條件嵌套，則按此規(guī)則逐級向外層遞推。

原始代碼：

向量化后代碼：

當(dāng)基本塊內(nèi)同構(gòu)語句條數(shù)足夠多時，基于if轉(zhuǎn)換的控制流向量化生成的代碼并不高效，因為這些語句對應(yīng)的控制條件相同，不需要再生成條件語句指令，可以直接進行向量化，此種向量化方法稱為直接SIMD向量化控制流方法。

原始代碼：

向量化后代碼：

進一步精簡：

歸約的向量化

歸約操作是指將多個元素歸并為單個元素的過程，該操作把向量中的多個元素歸約為一個元素，常見的歸約操作包括歸約加、歸約乘等。

原始代碼：

向量化后：

以上面的代碼段為例，將向量寄存器槽位中的4個數(shù)據(jù)相加，利用提取指令實現(xiàn)的上述歸約需要進行三次提取，然后進行三次加法。

此外還可以利用向量移位指令實現(xiàn)歸約加法，實現(xiàn)原理如圖所示。此種方法通過兩次移位、兩次相加獲得最終結(jié)果。由于幾乎所有平臺的移位指令節(jié)拍數(shù)和提取指令節(jié)拍數(shù)相同，而向量加和標量加的節(jié)拍數(shù)也相同，因此利用向量寄存器移位指令實現(xiàn)的歸約加減少了一次加法和提取操作，代價小于利用提取指令實現(xiàn)的歸約加。

當(dāng)前大多數(shù)向量寄存器在使用時為一個不可拆分的整體，即向量寄存器中的每個數(shù)據(jù)都是有效的。但語句中的數(shù)據(jù)并行性不足時，需要向量寄存器的部分使用，即向量寄存器中的某些槽位為有效數(shù)據(jù)，其它槽位為無效數(shù)據(jù)。向量寄存器有四種使用方式，分別為滿載使用、一端無效的部分使用、兩端無效的部分使用、不連續(xù)的部分使用。其中寄存器滿載使用的情況也可稱為程序充分向量化，而部分使用的情況可稱為程序不充分向量化。

合適的向量長度

但不是所有程序都適合使用不充分向量化方法改寫，適合使用不充分向量化方法程序可以分為兩種情況。

（1）一是當(dāng)平臺沒有向量重組指令或者向量重組指令的功能較弱時，如果強制將不連續(xù)的訪存數(shù)據(jù)組成向量可能導(dǎo)致向量化沒有收益，而不充分向量化不需考慮平臺是否支持向量重組指令，同樣可以生成向量程序。

（2）二是向量重組指令的代價過大而導(dǎo)致向量化沒有效果，即使用充分向量化效果不如使用不充分向量化效果。

常用的不充分向量化方法分為三類，分別為掩碼內(nèi)存讀寫方法、插入/提取方法以及加寬向量訪存方法。首先介紹掩碼內(nèi)存讀寫方法，以下圖所示的語句S1:c[2i]=a[2i] + b[2i]為例，load指令從內(nèi)存中連續(xù)地加載數(shù)據(jù)到向量寄存器Va和Vb中，其中的偶數(shù)位是有效槽位，奇數(shù)位是無效的槽位 。

不充分向量化方法的代碼生成需要從三個方面進行考慮，首先在讀內(nèi)存時需要標記出有效槽位和無效槽位，然后在運算時需要將參與運算的向量寄存器槽位相對應(yīng)，最后再將結(jié)果寫入內(nèi)存時需要避免將無效槽位的值寫入內(nèi)存。在申威平臺以下面的基本塊代碼為例說明如何生成不充分向量化代碼。 申威平臺支持256位的向量寄存器，其向量寄存器也是標量寄存器，根據(jù)操作指令決定寄存器類型。然而這個結(jié)果是不正確的。

源代碼為：

匯編代碼為：

因為讀寫內(nèi)存操作會訪問到原程序沒有涉及到的值w[col+1][0]和A[Anext][1][0]，如下圖所示，這可能導(dǎo)致程序結(jié)果不正確和內(nèi)存溢出，并且在對無效槽位進行乘法運算時可能引發(fā)異常，此時可以采用插入/提取的方法對程序進行向量化。

利用插入指令實現(xiàn)時首先通過多條標量內(nèi)存讀操作將數(shù)據(jù)存放到標量寄存器中，然后將數(shù)據(jù)分別插入到向量寄存器中，如下圖所示。一些平臺支持向量插入指令，如Intel的SSE指令集可利用一條插入讀指令“__mm_set_ps(f[k][0],f[k][1], f[k][2],0)”，就可以將f[k][0]、f[k][1] 和f[k][2]的值加載到向量寄存器中。

同樣可以利用加寬向量訪存方法實現(xiàn)向量化，如圖所示，如果需要的值在內(nèi)存中是連續(xù)的，那么一條加寬的向量讀指令就可以將其加載到向量寄存器中實現(xiàn)部分向量讀操作。

代碼中的向量寫操作可以使用提取指令實現(xiàn)，如圖所示。利用提取指令將數(shù)據(jù)從向量寄存器中提取出來，然后利用標量內(nèi)存寫指令實現(xiàn)。AVX2指令集中提供有掩碼內(nèi)存寫指令，一條掩碼內(nèi)存寫指令“vmaskmovpd ymm3，mask，x[k][0]”就可以將x[k][0]， x[k][1]和x[k][2]的值寫入內(nèi)存。

與加寬向量讀指令相似，加寬向量寫指令可以用于部分向量寫內(nèi)存操作，然而該操作不僅需要避免訪存溢出，同時還要避免對內(nèi)存造成誤寫，可以在尾部添加一些內(nèi)存空間避免內(nèi)存訪問溢出。

示例中需要避免w[col+1][0]的值在部分內(nèi)存寫時被改變，使用備份和恢復(fù)機制可以更正被改變的值，首先將w[col+1][0]的值讀到標量寄存器$f4中，然后利用一個加寬的向量存操作將結(jié)果寫入內(nèi)存，最后再利用一個標量存操作恢復(fù)w[col+1][0]的值。

在原程序中，無效槽位的數(shù)據(jù)不需要任何計算。因此需要將無效槽位填充一些數(shù)據(jù)以避免無效槽位引入算術(shù)異常。利用插入指令或者混洗指令，將任意一個有效槽位中的數(shù)據(jù)填充到無效槽位，來避免無效槽位引入的算術(shù)異常。

利用加寬向量訪存生成的不充分向量化匯編代碼如下所示：

與前面直接向量化的錯誤代碼相比，添加了一條插入指令以保證部分向量運算時不會引起算術(shù)異常，然后添加了一條標量讀和標量寫指令實現(xiàn)部分向量操作。