x86 SIMD下13位存储8个三值trit的位掩码高效提取方案咨询
13位直映三进制trit编码的SIMD掩码提取实现方案
核心约束与已实现能力
- 存储规格:共8个取值为0/1/2的trit元素,因x86 SIMD通道位宽预算严格限制,将直映三进制编码的8trit值压缩至13位存储空间存储;容量验证显示213=8192,大于38=6561的全三进制枚举状态数,可完全覆盖所有合法取值。
- 编码规则:trit序列按三进制权值直接映射为整数值存储,例如序列
0t12211012按权值计算对应整数值4244,二进制表示为0b1000010010100。 - 已落地操作:支持单trit值修改,通过预存3的幂次值、借助
pshufw指令查表快速定位目标trit位置完成修改。
待解决核心需求
快速提取所有trit位置的取值位掩码:针对给定的13位编码值,输出3个8位掩码,分别标记所有trit位置上取值为0、1、2的位向量。仍以上述编码序列为例,需输出的掩码分别为:
- 0值位置掩码:
0b00000100 - 1值位置掩码:
0b10011010 - 2值位置掩码:
0b01100001
当前尚未找到适配x86 SIMD的低指令数实现路径。
已排查的低效方案
逐位拆分trit的循环实现为当前验证的低效率路径,示例代码如下:
uint32_t trits = <something>; uint8_t mask0 = 0, mask1 = 0, mask2 = 0; for (uint8_t shift = 0; shift < 8; ++shift) { const uint32_t remainder = trits % 3; mask0 |= (!remainder) << shift; mask1 |= (remainder == 1) << shift; mask2 |= (remainder == 2) << shift; trits /= 3; }
即使通过乘移位技巧优化常量除法的SIMD执行效率,整体指令数仍随trit数量线性增长,单轮循环指令数较多,无法满足性能要求。此前也尝试探索可复用的trit级相等判断原语(即通过短位运算实现两个编码值的trit级位置匹配,输出相等位置的位掩码),但尚未找到适配位宽约束的实现方法。
适配x86 SIMD的低指令数实现思路
- 全量小表查法:利用13位编码的小枚举空间优势,预先在只读常量段构建全量映射表,每个条目存储对应编码值的3个8位掩码,整体表大小仅约20KB(覆盖6561个合法编码状态),完全适配x86 L1缓存的容量边界。实现时直接将13位编码值拆分为高5位和低8位偏移,通过两次连续的
pshufw/vpshufb查表操作,即可一次性读出全部3个掩码,无循环开销。 - 定点对齐分解法:通过预计算的定点缩放常量,将13位编码值中的8个trit值一次性对齐到独立的位通道。具体为基于三进制编码的线性叠加特性,通过乘法移位操作将不同权值的trit余数映射到独立的4位通道,再通过通道值与0/1/2的固定比较,通过
pmovmskb指令直接生成全位置的取值掩码,全程仅需固定数目的乘、移位、比较指令,指令数不随trit数量变化。 - trit级相等原语搭建:基于上述对齐的独立trit通道,两个输入编码值的对应trit可直接做逐通道比较,通过SIMD比较指令的掩码输出直接生成trit级相等的位向量,无需逐位拆分操作。
内容的提问来源于stack exchange,提问作者Octavianus
相关产品推荐
相关产品推荐

