Reference Hardware Implementations of Bit Extract/Deposit Instructions
The BEXT (bit extract, aka parallel extract, PEXT) instruction takes as arguments a value and a bit mask. The bits in the mask indicate which bits in the value should be extracted. All extracted bits are then packed into the LSB end of the result:
uint32_t bext32(uint32_t v, uint32_t mask)
{
uint32_t c = 0, m = 1;
while (mask) {
uint32_t b = mask & -mask;
if (v & b)
c |= m;
mask -= b;
m <<= 1;
}
return c;
}
The BDEP (bit deposit, aka parallel deposit, PDEP) instruction performs the inverse operation. It takes the LSB bits of the value and places them in the positions marked in the mask argument:
uint32_t bdep32(uint32_t v, uint32_t mask)
{
uint32_t c = 0, m = 1;
while (mask) {
uint32_t b = mask & -mask;
if (v & m)
c |= b;
mask -= b;
m <<= 1;
}
return c;
}
Simple 16-bit example:
value 0011_0110_0000_0101
mask 0011_1100_0000_0000
bext 0000_0000_0000_1101
bdep 0001_0100_0000_0000
This instructions may be valuable features in bit-manipulation ISA extensions. However, they are not trivial to implement in an efficient manner. This repository contains permissively licensed Verilog reference implementations for 32-bit and 64-bit implementations of those instructions using different architectures:
- Pipelined prallel extract/deposit
- Single-stage parallel extract/deposit
- Sequential in chunks with fixed cycle count
- Sequential with one cycle per set mask bit
Additionally, some of the cores do also implement the generalised bit reversal (GREV) instruction, since the GREV instruction can in some cases share resources with BEXT/BDEP. GREV can be used to reverse the bit order in a word, or swap the two halfs of a word, or any in-between operation (like endianess convertion), or combinations of them:
uint32_t grev32(uint32_t x, int k)
{
if (k & 1) x = ((x & 0x55555555) << 1) | ((x & 0xAAAAAAAA) >> 1);
if (k & 2) x = ((x & 0x33333333) << 2) | ((x & 0xCCCCCCCC) >> 2);
if (k & 4) x = ((x & 0x0F0F0F0F) << 4) | ((x & 0xF0F0F0F0) >> 4);
if (k & 8) x = ((x & 0x00FF00FF) << 8) | ((x & 0xFF00FF00) >> 8);
if (k & 16) x = ((x & 0x0000FFFF) << 16) | ((x & 0xFFFF0000) >> 16);
return x;
}
The Verilog code for the cores can be found in bextdep.v
. The Verilog file
bextdep_pps.v
is also needed. It is generated by ppsmaker.py
(make bextdep_pps.v
) and contains prefix-sum cores that are used by most of the
cores in bextdep.v
.
Evaluation
This are the 64 bit Verilog cores:
Name | Gates | Rel | Rel+G | Delay | Description |
---|---|---|---|---|---|
bextdep64g3 |
9672 | 2.00 | 2.00 | 22 | 3-stage pipeline with GREV |
bextdep64p3 |
8846 | 1.83 | 2.17 | 22 | 3-stage pipeline |
bextdep64g2 |
8075 | 1.67 | 1.67 | 40 | 2-stage pipeline with GREV |
bextdep64p2 |
7140 | 1.48 | 1.82 | 40 | 2-stage pipeline |
bextdep64g1 |
6406 | 1.33 | 1.33 | 49 | single-stage with GREV support |
bextdep64p1 |
5515 | 1.14 | 1.48 | 51 | single-stage implementation |
bextdep64sh |
4324 | 0.90 | 1.24 | 33 | 4-cycles sequential implementation |
bextdep64sb |
3589 | 0.74 | 1.08 | 24 | 8-cycles sequential implementation |
bextdep64sn |
3192 | 0.66 | 1.00 | 17 | 16-cycles sequential implementation |
bextdep64sx |
3123 | 0.65 | 0.99 | 71 | up-to-64-cycles sequential implementation |
bextdep64go |
1641 | 0.34 | 0.34 | 15 | single-stage GREV-only core |
vscalealu64 |
4825 | 1.00 | 1.34 | 131 | ALU from V-Scale CPU (for comparison) |
And this are the 32 bit Verilog cores:
Name | Gates | Rel | Rel+G | Delay | Description |
---|---|---|---|---|---|
bextdep32g3 |
4214 | 1.91 | 1.91 | 16 | 3-stage pipeline with GREV |
bextdep32p3 |
3859 | 1.75 | 2.08 | 16 | 3-stage pipeline |
bextdep32g2 |
3451 | 1.57 | 1.57 | 28 | 2-stage pipeline with GREV |
bextdep32p2 |
3062 | 1.39 | 1.72 | 27 | 2-stage pipeline |
bextdep32g1 |
2616 | 1.19 | 1.19 | 38 | single-stage with GREV support |
bextdep32p1 |
2198 | 1.00 | 1.33 | 36 | single-stage implementation |
bextdep32sb |
1976 | 0.90 | 1.22 | 24 | 4-cycles sequential implementation |
bextdep32sn |
1670 | 0.76 | 1.09 | 17 | 8-cycles sequential implementation |
bextdep32sx |
1543 | 0.70 | 1.03 | 39 | up-to-32-cycles sequential implementation |
bextdep32go |
721 | 0.33 | 0.33 | 13 | single-stage GREV-only core |
vscalealu32 |
2203 | 1.00 | 1.33 | 68 | ALU from V-Scale CPU (for comparison) |
The gate counts in the tables above are for the cores mapped to NAND, NOR, and
NOT gates, and DFFs, with NOT counting as 0.5 gates and DFFs counting as 4
gates. (See Makefile
for synthesis scripts.)
The "Rel" column lists the size relative to the the ALU of a V-Scale RISC-V
processor. (The 64-bit version is just the 32 bit ALU with extended bit-width,
it does not support the RV64 *W
opcodes. See vscalealu.v
.) The "Rel+G"
column lists the relative size when the size of a GREV core is added to the
cores that don't implement GREV.
The "Delay" column lists the number of date delays in the longest path from a primary input or FF output to a primary output or FF input.
The sequential cores require an additional cycle for initialization. So the
initiation interval (II) of the bextdep32sb
core is 5 and the II of the
bextdep64sx
core is up to 65 (when all mask bits in the input are set).
Here are the sizes and timings for the cores when mapped to a Xilinx UltraScale Kintex device (speed grade -3) with Vivado 2017.3. This evaluation also includes the Rocket "TinyConfig" core for size comparison:
Name | LUTs | Rel | Rel+G | Max Freq. |
---|---|---|---|---|
bextdep64g3 |
774 | 0.80 | 0.80 | 451 MHz |
bextdep64p3 |
675 | 0.70 | 0.90 | 462 MHz |
bextdep64g2 |
762 | 0.79 | 0.79 | 430 MHz |
bextdep64p2 |
678 | 0.70 | 0.91 | 406 MHz |
bextdep64g1 |
854 | 0.89 | 0.89 | 277 MHz |
bextdep64p1 |
733 | 0.76 | 0.96 | 285 MHz |
bextdep64sh |
553 | 0.57 | 0.78 | 351 MHz |
bextdep64sb |
437 | 0.45 | 0.66 | 543 MHz |
bextdep64sn |
314 | 0.33 | 0.53 | 668 MHz |
bextdep64sx |
309 | 0.32 | 0.52 | 421 MHz |
bextdep64go |
195 | 0.20 | 0.20 | 1189 MHz |
vscalealu64 |
964 | 1.00 | 1.00 | 713 MHz |
Name | LUTs | Rel | Rel+G | Max Freq. |
---|---|---|---|---|
bextdep32g3 |
322 | 0.75 | 0.75 | 521 MHz |
bextdep32p3 |
279 | 0.65 | 0.84 | 537 MHz |
bextdep32g2 |
318 | 0.74 | 0.74 | 497 MHz |
bextdep32p2 |
276 | 0.64 | 0.83 | 497 MHz |
bextdep32g1 |
370 | 0.86 | 0.86 | 350 MHz |
bextdep32p1 |
283 | 0.66 | 0.85 | 352 MHz |
bextdep32sb |
263 | 0.61 | 0.80 | 545 MHz |
bextdep32sn |
168 | 0.39 | 0.58 | 686 MHz |
bextdep32sx |
158 | 0.37 | 0.56 | 427 MHz |
bextdep32go |
83 | 0.19 | 0.19 | 1116 MHz |
vscalealu32 |
431 | 1.00 | 1.00 | 819 MHz |
tinyrocket |
4280 | 9.93 | ----- | 211 MHz |
Interfaces
All cores implement the same interface (XLEN=32 or XLEN=64):
input clock, reset;
input din_valid;
output din_ready;
input [ 1:0] din_mode;
input [XLEN-1:0] din_value;
input [XLEN-1:0] din_mask;
output dout_valid;
input dout_ready;
output [XLEN-1:0] dout_result;
The din*
signals are a valid/ready-style input stream. Data is transferred
in to the core in cycles where valid and ready are high. The core will raise
ready when it is ready to receive data without waiting for an external valid
signal, and ready is guaranteed to stay high until a transfer happens (or the
core is reset).
The dout*
signals are a valid/ready-style output stream. Data is transferred
out of the core in cycles where valid and ready are high. The core will raise
valid when it is ready to transmit data without waiting for an external ready
signal, and valid is guaranteed to stay high until a transfer happens (or the
core is reset).
The assigned values for din_mode
are (GREV mode is only valid for cores with
GREV support):
Mode | Description |
---|---|
2'b00 | BEXT |
2'b01 | BDEP |
2'b10 | GREV |
2'b11 | reserved |
All cores have FFs near the dout_result
output, but may borrow from the
timing path of the incomming din_mode
, din_value
, and din_mask
signals.
Why do you call those instructions BEXT/BDEP and not PEXT/PDEP like everyone else?
Because the P in PEXT/PDEP stands for parallel and thus implies a certain implementation. That's just bad ISA naming. Imo an instruction name should describe what the instruction is doing, but leave it to the implementation to decide how to do it.
Limitations, Todos and Future Work
- The 3-stage pipelined cores don't have very well balanced pipeline stages in Vivado synthesis. This might be worth looking into.
References
- https://en.wikipedia.org/wiki/Bit_Manipulation_Instruction_Sets#Parallel_bit_deposit_and_extract
- http://nbviewer.jupyter.org/url/svn.clifford.at/handicraft/2017/permsyn/data.ipynb
- http://palms.ee.princeton.edu/PALMSopen/hilewitz04comparing_with_cit.pdf
- http://palms.ee.princeton.edu/PALMSopen/hilewitz06FastBitCompression.pdf
- http://svn.clifford.at/handicraft/2017/pdep_pext
- http://programming.sirrida.de/bit_perm.html#bmi2
- http://www.felixcloutier.com/x86/PEXT.html
- http://www.felixcloutier.com/x86/PDEP.html