Can Google XLS be used to pipeline integer operations such as multiplication?

[oharboe]

@tspyrou @ollef @QuantamHD FYI

I was wondering if integer multiplication could be pipelined using Google XLS, but either we're doing something wrong or our expectations are wrong w.r.t. the Google XLS use-case.

fn mul(a: u64, b: u64) -> uN[128] {
  for (i, acc) in range(u32:0, u32:64) {
    if a[i +: u1] == u1:1 { acc + ((b as uN[128]) << i) } else { acc }
  }(uN[128]:0)
}

Alas:

% ./codegen_main --pipeline_stages=3 --delay_model=asap7 --clock_period_ps=1000 mul.opt.ir > mul.v
Error: INVALID_ARGUMENT: __mul__mul: cannot achieve the specified pipeline length. Try `--pipeline_stages=63`; Running pass #54: Pipeline Scheduling [short: pipesched]; Running pass #54: Top level scheduling pass pipeline [short: scheduling]

Initially I wanted to use Yosys+abc retiming to do this, but yosys+abc retiming runs up against limitations in how much pipelining it is able to take advantage of.

https://github.com/The-OpenROAD-Project/RegFileStudy/tree/main/multiplier

[ericastor]

Perhaps things aren't quite working as you expect?

Having tested this myself, it seems XLS's opt_main is successfully narrowing each of the adders you're invoking to a 65-bit adder, which is great. According to delay_info_main, the critical path of the result looks like:

# Critical path:
  37369ps (+  0ps): concat.99144: bits[128] = concat(add.3407: bits[65], bit_slice.87857: bits[1], sel.87609: bits[1], sel.85592: bits[1], sel.83578: bits[1], sel.81568: bits[1], sel.79563: bits[1], sel.77564: bits[1], sel.75572: bits[1], sel.73588: bits[1], sel.71613: bits[1], sel.69648: bits[1], sel.67694: bits[1], sel.65752: bits[1], sel.63823: bits[1], sel.61908: bits[1], sel.60008: bits[1], sel.58124: bits[1], sel.56257: bits[1], sel.54408: bits[1], sel.52578: bits[1], sel.50768: bits[1], sel.48979: bits[1], sel.47212: bits[1], sel.45468: bits[1], sel.43748: bits[1], sel.42053: bits[1], sel.40384: bits[1], sel.38742: bits[1], sel.37128: bits[1], sel.35543: bits[1], sel.33988: bits[1], sel.32464: bits[1], sel.30972: bits[1], sel.29513: bits[1], sel.28088: bits[1], sel.26698: bits[1], sel.25344: bits[1], sel.24027: bits[1], sel.22748: bits[1], sel.21508: bits[1], sel.20308: bits[1], sel.19149: bits[1], sel.18032: bits[1], sel.16958: bits[1], sel.15928: bits[1], sel.14943: bits[1], sel.14004: bits[1], sel.13112: bits[1], sel.12268: bits[1], sel.11473: bits[1], sel.10728: bits[1], sel.10034: bits[1], sel.9392: bits[1], sel.8803: bits[1], sel.8268: bits[1], sel.7788: bits[1], sel.7364: bits[1], sel.6997: bits[1], sel.6688: bits[1], sel.6438: bits[1], sel.6248: bits[1], sel.6119: bits[1], bit_slice.5733: bits[1], id=99144)
  37369ps (+439ps): add.3407: bits[65] = add(concat.99206: bits[65], and.6109: bits[65], id=3407)
  36930ps (+  0ps): concat.99206: bits[65] = concat(literal.1539: bits[1], bit_slice.87854: bits[64], id=99206)
  36930ps (+  0ps): bit_slice.87854: bits[64] = bit_slice(sel.99514: bits[65], start=1, width=64, id=87854)
  36930ps (+156ps): sel.99514: bits[65] = sel(bit_slice.1034, cases=[concat.99205, add.3402], id=99514, pos=[(0,2,4)])
  36774ps (+439ps): add.3402: bits[65] = add(concat.99205: bits[65], concat.5798: bits[65], id=3402, pos=[(0,2,28)])
...
    635ps (+  0ps): concat.99145: bits[65] = concat(literal.1539: bits[1], sel.99520: bits[64], id=99145, pos=[(0,2,28)])
    635ps (+156ps): sel.99520: bits[64] = sel(bit_slice.729, cases=[bit_slice.99761, bit_slice.99519], id=99520, pos=[(0,2,4)])
    479ps (+  0ps): bit_slice.99519: bits[64] = bit_slice(add.2975: bits[65], start=1, width=64, id=99519, pos=[(0,2,4)])
    479ps (+439ps): add.2975: bits[65] = add(bit_slice.5797: bits[65], concat.5798: bits[65], id=2975, pos=[(0,2,28)])
     40ps (+  0ps): bit_slice.5797: bits[65] = bit_slice(and.2291: bits[128], start=1, width=65, id=5797, pos=[(0,2,28)])
     40ps (+ 23ps): and.2291: bits[128] = and(concat.155: bits[128], sign_ext.2290: bits[128], id=2291, pos=[(0,2,4)])
     17ps (+ 17ps): sign_ext.2290: bits[128] = sign_ext(bit_slice.728: bits[1], new_bit_count=128, id=2290, pos=[(0,2,4)])
      0ps (+  0ps): bit_slice.728: bits[1] = bit_slice(a: bits[64], start=0, width=1, id=728, pos=[(0,2,8)])
      0ps (+  0ps): a: bits[64] = param(name=a, id=1)

It seems XLS's asap7 delay model thinks that a 65-bit adder has 439ps of delay, and a 65-bit-wide binary select has 156ps of delay. Since you're requiring a 1 GHz clock (clock period = 1000ps), this means that XLS can only fit ~one stage of your multiplier in each pipeline stage.

This could be a sign that the delay model is falling short! But - if it's accurate, then I think you'll need to relax your target clock period, or find a better multiplier architecture for XLS to pipeline. For instance, you could try some number of steps of reductions from (a1<<32 + a0) * (b1<<32 + b0), either classical:

(a1*b1)<<64 + (a1*b0 + a0*b1)<<32 + (a0*b0)

or Karatsuba:

let z0 = a0*b0;
let z2 = a1*b1;
let z3 = (a0 + a1)*(b0 + b1);
(z2)<<64 + (z3 - z0 - z2)<<32 + (z0)

EDIT: For reference, your decomposition is estimated under the ASAP7 delay model to have a critical path of ~37 ns. Two steps of classical reduction gets you down to something that schedules in 4 pipeline stages with 1000ps target clock period, with an unscheduled critical path of ~3.5 ns. (Karatsuba is cool, but you end up needing 3 steps of reduction to get to your target clock... and even so, you end up with a ~6.2 ns critical path and requiring 8 pipeline stages.)

Alternatively, it would be possible for XLS to add a feature to pipeline large multipliers. This gets a little tricky, since it's (in general) unclear which architecture or cut-points would be best... but we could at least try to decompose a multiplication to smaller operations that each fit within the target clock period. If you'd like this, I'm sure we'd welcome a PR for it - or you could file a feature request!

[oharboe]

I wanted to start simple, with an integer multiply. To my surprise integer multiply is atomic, whereas floating point multiply appears to be "molecylic", i.e. it consists of multiple "atoms" and can be pipelined.

My use-case for Google XLS, would be "architectural retiming" that compliments yosys+abc automatic retiming.

Examples where I'm looking for automatic retiming is multiply, bit counting and floating point operations. I want to express the logic combinationally, because it is easier to get right and to test, and then have the pipelining be automatic (through Google XLS and/or yosys+abc).

[oharboe]

vlsiffra implements a 64x64 bit 128bit multiplier in asap7

A 2 cycle 64 bit multiply-adder (64bit * 64bit + 128bit -> 128bit) built with the OpenROAD RTL to GDSII flow and the ASAP7 7nm academic PDK makes timing at 1.85 GHz 1. It takes up 3600um of area:

[ericastor]

XLS is currently written to create Verilog that trusts the logic synthesis engine to do a good job with its atomic operations. When it comes to breaking up large operations where it's known that logic synthesis engines aren't optimal, or where the size of the operation obstructs optimal pipelining, that would be a reasonable feature request for XLS; however, any implementation would also need to avoid penalizing us when the operation doesn't need to be split.

Doing this is probably possible, but likely requires large & expensive architectural changes to XLS's delay models and/or scheduler. We'd be glad to discuss designs for these new features, if provided!

[oharboe]

I'm trying to correct my expecations w.r.t. the Google XLS intended use-case: Google XLS is for large scale optimization whereas register retiming/duplication in synthesis is for small scale optimizations?

It is unclear to me what operations in Google XLS that are atomic that non-yosys synthesis tools is able to retime/optimize and where Google XLS is working fine and yosys needs to become more competitive.

We had a go at trying to use Google XLS to improve floating point performance with OpenROAD and Yosys, but we got similar results(in terms of asymptotic clock period towards 500ps with increasing pipeling) to Berkely Floating point and yosys+abc retiming:

 bazelisk build //multiplier:xls_fp_mul_plot