ARM Neon：在一個8字節的向量通道中存儲非零字節的第n個位置

Question

我想將一個64位的Neon向量通道轉換爲第n個位置（s）非零（也就是0xFF）的8位值，然後用零填充向量的其餘部分。這裏有一些例子：

0 1 2 3 4 5 6 7 

d0: 00 FF 00 FF 00 00 00 FF 
d1: 1 3 7 0 0 0 0 0 

d0: 00 FF FF FF 00 00 FF 00 
d1: 1 2 3 6 0 0 0 0 

d0: FF FF FF FF FF FF FF FF 
d1: 0 1 2 3 4 5 6 7 

d0: FF 00 00 00 00 00 00 00 
d1: 0 0 0 0 0 0 0 0 

d0: 00 00 00 00 00 00 00 00 
d1: 0 0 0 0 0 0 0 0 

我覺得它可能是一個或兩個移位霓虹燈指令與另一個「好」的載體。我怎樣才能做到這一點？

Answer 1

事實證明，這並不簡單。

幼稚的高效方法首先得到索引（只需加載一個帶有位掩碼的0 1 2 3 4 5 6 7和vand的靜態向量）。但是，爲了在輸出矢量的一端收集它們 - 在它們表示的輸入通道的不同通道中 - 然後您需要一些任意的置換操作。只有一條指令可以任意排列矢量，vtbl（或vtbx，這本質上是相同的東西）。但是，vtbl會以目標順序採用一個源索引向量，這與您嘗試生成的內容完全相同。因此，爲了產生您的最終結果，您需要使用您的最終結果，因此，天真的有效解決方案是不可能的; QED。

最根本的問題是，你實際上在做什麼是排序一個向量，它本質上不是一個並行的SIMD操作。 NEON是爲媒體處理而設計的並行SIMD指令集，對於更一般的矢量處理的任何數據相關/水平/分散 - 聚集操作而言，並不是絕對的。

爲了證明這一點，我確實設法在純NEON中做到這一點，根本沒有任何標量代碼，它是可怕的;最好的「一個或兩個移位NEON指令」我能想出的是一些基於條件選擇的旋轉位掩碼累加技巧。如果它是不明確的，我建議在調試器或仿真步進通過遵循它做什麼（example）：

// d0 contains input vector 
vmov.u8 d1, #0 
vmov.u8 d2, #0 
vmvn.u8 d3, #0 
vdup.u8 d4, d0[0] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[1] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[2] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[3] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[4] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[5] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[6] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vsub.u8 d1, d1, d3 
vdup.u8 d4, d0[7] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
vbic.u8 d1, d1, d3 
// d1 contains output vector 

作弊和使用循環（這需要以相反的方向旋轉d0這樣我們就可以通過d0[0]訪問每個原車道），使得它更小，但不是真的任何少可怕：

vmov.u8 d1, #0 
vmov.u8 d2, #0 
vmvn.u8 d3, #0 
mov r0, #8 
1: 
vdup.u8 d4, d0[0] 
vext.u8 d5, d2, d3, #7 
vbit.u8 d3, d5, d4 
subs r0, r0, #1 
vext.u8 d0, d0, d0, #1 
vsub.u8 d1, d1, d3 
bne 1b 
vbic.u8 d1, d1, d3 

理想的情況下，如果它是在所有可能的返工算法的其他部分，以避免需要載體的非恆定的排列，做相反。

Answer 2

你可以通過排序向量來做到這一點。這是一個比你預期的這種手術更復雜的手術，但我還沒有提出任何更好的方案。

鑑於00/ff字節的列表中d0，並在d1常量0, 1, 2, ..., 7，您就可以使用vorn活躍列的排序列表。

vorn.u8 d0, d1, d0 

現在所有的d0不必要的車道已被替換0xff和其餘都換成了自己的車道指數。從那裏你可以對列表進行排序，最後將所有不需要的通道集中起來。

要做到這一點，你必須將名單擴大到16個字節：

vmov.u8 d1, #255 

，然後將它們分成奇/偶向量：

vuzp.u8 d0, d1 

排序操作由vmin/vmax那些載體，然後交錯操作之間，然後另一個vmin/vmax對到不同雙之間進行排序，以使得值可朝向氣泡ir適當的地方。像這樣：

vmin.u8 d2, d0, d1 
vmax.u8 d3, d0, d1 
vsri.u64 d2, d2, #8 ; stagger the even lanes (discards d0[0]) 
vmax.u8 d4, d2, d3 ; dst reg would be d0, but we want d0[0] back... 
vmin.u8 d1, d2, d3 
vsli.u64 d0, d4, #8 ; revert the stagger, and restore d0[0] 

這實現了全網絡的兩個階段，整個塊必須重複四次（八級），以使人們有可能的東西在d0[7]泡一路下跌到d0[0]在如果第一個字節是唯一的零輸入，則最後一個字節是唯一的非零輸入的極端情況，或者d0[0]轉到d0[7]。

一旦你完成對它們進行排序，縫合結果一起回來：

vzip.u8 d0, d1 

而且因爲你想在剩下的車道零：

vmov.u8 d1, #0 
vmax.s8 d0, d1 

現在d0應該包含的結果。

如果你看看維基百科的sorting network頁面，你會看到，八個車道的理論最小深度僅爲六個階段（6雙vmin/vmax），所以有可能找到一組排列的（代替我vsli和vsri操作），它實現了一個六階段排序網絡，而不是我實現的八階段插入/選擇/蒸餾類型。如果確實存在，並且與NEON的排列操作兼容，那麼它肯定值得找，但我沒有時間去看。

還要注意的是那種正在共有16個字節，這是比你更需要的，如果你使用Q寄你可以有它的32個字節的工作......所以這是最大的一個很長的路要走吞吐量。

哦，即使在這種配置中，我認爲你不需要排序的最後階段。爲讀者留下的練習。