基本上,我有8个数据,每个2位(4个状态),存储在32位整数的16个LSB中。我想颠倒数据片的顺序来做一些模式匹配。
我给了一个参考整数和8个候选,我需要匹配其中一个候选参考。然而,匹配候选者可以以某种可预测的方式变换。
如果参考数据的格式为[0,1,2,3,5,5,7],那么可能的匹配可以是以下8种形式之一:
[0,1,2,3,4,5,6,7], [0,7,6,5,4,3,2,1]
[6,7,0,1,2,3,4,5], [2,1,0,7,6,5,4,3]
[4,5,6,7,0,1,2,3], [4,3,2,1,0,7,6,5]
[2,3,4,5,6,7,0,1], [6,5,4,3,2,1,0,7]
模式是数据始终按顺序排列,但可以反转和旋转。
我在C和MIPS中实现这一点。我有两个工作,但他们看起来很笨重。我目前的方法是将每个部分与原始部分进行屏蔽,将其移至新位置,并将其与新变量(初始化为0)进行对比。
我在C中做了更多的硬编码:
int ref = 4941; // reference value, original order [1,3,0,1,3,0,1,0], (encoded as 0b0001001101001101)
int rev = 0;
rev |= ((ref & 0x0003) << 14) | ((ref & 0x000C) << 10) | ((ref & 0x0030) << 6) | ((ref & 0x00C0) << 2); // move bottom 8 bits to top
rev |= ((ref & 0xC000) >> 14) | ((ref & 0x3000) >> 10) | ((ref & 0x0C00) >> 6) | ((ref & 0x0300) >> 2); // move top 8 bits to bottom
// rev = 29124 reversed order [0,1,0,3,1,0,3,1], (0b0111000111000100)
我在MIPS中实现了一个循环来尝试减少静态指令:
lw $01, Reference($00) # load reference value
addi $04, $00, 4 # initialize $04 as Loop counter
addi $05, $00, 14 # initialize $05 to hold shift value
addi $06, $00, 3 # initialize $06 to hold mask (one piece of data)
# Reverse the order of data in Reference and store it in $02
Loop: addi $04, $04, -1 # decrement Loop counter
and $03, $01, $06 # mask out one piece ($03 = Reference & $06)
sllv $03, $03, $05 # shift piece to new position ($03 <<= $05)
or $02, $02, $03 # put piece into $02 ($02 |= $03)
sllv $06, $06, $05 # shift mask for next piece
and $03, $01, $06 # mask out next piece (#03 = Reference & $06)
srlv $03, $03, $05 # shift piece to new position ($03 >>= $05)
or $02, $02, $03 # put new piece into $02 ($02 |= $03)
srlv $06, $06, $05 # shift mask back
addi $05, $05, -4 # decrease shift amount by 4
sll $06, $06, 2 # shift mask for next loop
bne $04, $00, Loop # keep looping while $04 != 0
有没有办法实现这个更简单或至少更少的指令?
要反转您的位,您可以使用以下代码。
static int rev(int v){
// swap adjacent pairs of bits
v = ((v >> 2) & 0x3333) | ((v & 0x3333) << 2);
// swap nibbles
v = ((v >> 4) & 0x0f0f) | ((v & 0x0f0f) << 4);
// swap bytes
v = ((v >> 8) & 0x00ff) | ((v & 0x00ff) << 8);
return v;
}
MIPS实现是15条指令。
rev: # value to reverse in $01
# uses $02 reg
srli $02, $01, 2
andi $02, $02, 0x3333
andi $01, $01, 0x3333
slli $01, $01, 2
or $01, $01, $02
srli $02, $01, 4
andi $02, $02, 0x0f0f
andi $01, $01, 0x0f0f
slli $01, $01, 4
or $01, $01, $02
srli $02, $01, 8
andi $02, $02, 0xff
andi $01, $01, 0xff
slli $01, $01, 8
or $01, $01, $02
# result in $01
请注意,您可以通过将常数加倍(甚至64位机器上的4)来同时反转2x16bits。但我不确定它对你的情况有用。
注意:谨慎使用手写优化组件,如果您真的在紧密循环中使用编译器生成,那么确实存在特定于处理器的优化。
你可以改进pipeline,(如果你用C代码编译器为你编写代码)并使用bne
指令的延迟槽。这将改善你的instruction level parallelism。
假设您有类似Mips处理器的东西,具有1个延迟槽和5级流水线(指令获取,解码,执行,存储器,写回)。
这条管道引入Read After Write危害数据依赖大多数是在$3
登记。
RaW hasard导致您的管道停转。
# Reverse the order of data in Reference and store it in $02
Loop: and $03, $01, $06 # mask out one piece ($03 = Reference & $06)
addi $04, $04, -1 # decrement Loop counter (RaW on $3)
sllv $03, $03, $05 # shift piece to new position ($03 <<= $05)
sllv $06, $06, $05 # shift mask for next piece
or $02, $02, $03 # put piece into $02 ($02 |= $03)
and $03, $01, $06 # mask out next piece (#03 = Reference & $06)
srlv $06, $06, $05 # shift mask back
srlv $03, $03, $05 # shift piece to new position ($03 >>= $05)
addi $05, $05, -4 # decrease shift amount by 4
or $02, $02, $03 # put new piece into $02 ($02 |= $03)
bne $04, $00, Loop # keep looping while $04 != 0
sll $06, $06, 2 # shift mask for next loop
如果您有超标量处理器,则解决方案需要进行一些更改。
对于一种非常简单有效的方法,使用256字节的查找表并执行2次查找:
extern unsigned char const xtable[256];
unsigned int ref = 4149;
unsigned int rev = (xtable[ref & 0xFF] << 8) | xtable[ref >> 8];
xtable
数组可以通过一组宏静态初始化:
#define S(x) ((((x) & 0x0003) << 14) | (((x) & 0x000C) << 10) | \
(((x) & 0x0030) << 6) | (((x) & 0x00C0) << 2) | \
(((x) & 0xC000) >> 14) | (((x) & 0x3000) >> 10) | \
(((x) & 0x0C00) >> 6) | (((x) & 0x0300) >> 2))
#define X8(m,n) m((n)+0), m((n)+1), m((n)+2), m((n)+3), \
m((n)+4), m((n)+5), m((n)+6), m((n)+7)
#define X32(m,n) X8(m,(n)), X8(m,(n)+8), X8(m,(n)+16), X8(m,(n)+24)
unsigned char const xtable[256] = {
X32(S, 0), X32(S, 32), X32(S, 64), X32(S, 96),
X32(S, 128), X32(S, 160), X32(S, 192), X32(S, 224),
};
#undef S
#undef X8
#undef X32
如果空间不贵,您可以使用单个查找到128K字节的表,您可以在启动时计算或使用脚本生成并包含在编译时,但它有点浪费,而且不缓存。