SupportLogic usage and decoding return results with cascaded multiplexers
About a week ago or so, I was working on a Wishbone cross-bar interconnect. It seemed like a fun project to toy around with. However, at one point in my design, things just weren’t working. Personally, I was convinced yosys was at fault, but I couldn’t figure out what the fault was.
So I set out about the task of creating a yosys issue.
The problem with creating a yosys issue is that most issues are ignored unless you can provide a minimal, complete, verifiable example of the error. For me, this is usually about 60-90 lines of code. However, usually when I turn in this 60-90 lines, Clifford tends to school me: either pointing out how the fault was my own, or otherwise he reduces my “minimal” example to 15 lines of code.
This time I was determined to create a better example of this bug myself first. Who knows, perhaps I might have even been able to find the bug?
So I set up all of the configurable parameters just the way I wanted, and ran yosys. At the prompt, I typed:
$ yosys -ql log.txt
yosys> read -sv wbxbar.v
yosys> dump
yosys> exitSure enough, if I squinted my eyes just right at the output in log.txt,
I felt like I could understand what was going on.
For example, I found things like:
attribute \src "../../rtl/wbxbar.v:227"
cell $mux $ternary$../../rtl/wbxbar.v:227$1146
parameter \WIDTH 1
connect \Y $ternary$../../rtl/wbxbar.v:227$1146_Y
connect \S \r_stb [0]
connect \B \r_we [0]
connect \A \i_mwe [0]
endThis appeared to describe a
multiplexer, where the output,
\Y, would be set to \A is \S was false, and to \B otherwise.
always @(*)
if (S)
Y = B;
else
Y = A;If I looked at line 227 within my source file, sure
enough, I could recognize some of the variables within my design: r_stb[0],
r_we[0], and even i_mwe[0]. The $ternary$../../rtl/wbxbar.v:227$1146_Y
value really didn’t make much sense to me, but if I searched on this string
within the log.txt file, I could often find where that was an input to
another block, meaning that it was an intermediate piece of logic.
Then, as I started trying to back out what was going on in this giant file of logic, I found a chain of several muxes all in a row. Sure, I had to do some scratching through the output to try to put it back together. No, it wasn’t easy, but I was convinced I was going to do this! If you adjust the output format to make it easier to read, you can then see (roughly) what I found:
cell $mux ...
connect \Y $one$
connect \S av
connect \B bdata
connect \A adata
end
cell $mux ...
connect \Y $two$
connect \S cv
connect \B cdata
connect \A $one$
end
cell $mux ...
connect \Y myoutput
connect \S dv
connect \B ddata
connect \A $two$
endThis is really simplified, but what I found was certainly a long chain of these multiplexers, perhaps as many as sixteen in a row.
This new knowledge left me wondering, was I writing my logic properly?
What’s wrong with cascaded if’s
Okay, I’ll admit that I use cascaded if’s in my code all the time. A classic example of when I might use such a cascaded if is when decoding a Wishbone return within an interconnect.
The basic logic is something like,
always @(posedge i_clk)
begin
o_ack = 0;
o_data = 0;
for(i=0; i<num_slaves; i=i+1)
begin
if (slave_ack[i])
begin
o_ack = 1;
o_data = slave_data[i];
end
end
endWhile I don’t normally use a for loop for this logic, like I did in my crossbar code, the result would roughly be the same.
Now, consider what this would look like once it was turned into logic. It would become something similar to,
always @(*)
begin
tmp_ack[0] = 1;
tmp_data[0] = 0;
if (slave_ack[0])
begin
tmp_ack[0] = 1;
tmp_data[0] = slave_data[0];
end
end
always @(*)
begin
if (slave_ack[1])
begin
tmp_ack[1] = 1;
tmp_data[1] = slave_data[1];
end else begin
tmp_ack[1] = tmp_ack[0];
tmp_data[1] = tmp_data[0];
end
end
always @(*)
begin
if (slave_ack[2])
begin
tmp_ack[2] = 1;
tmp_data[2] = slave_data[2];
end else begin
tmp_ack[2] = tmp_ack[1];
tmp_data[2] = tmp_data[1];
end
endAnd so on …. as this would continue through processing eight separate slaves.
Immediately I was concerned: long chains of logic like this will impact the clock rate this logic can run at! In general, as part of design, you want to minimize your longest path in order to achieve high speed. This logic, however was anything but minimum!
But could it be improved?
 |
Looking over this logic tree, it was very much a one-sided tree, much like the one shown in Fig. 1 at the right.
In this figure, the inputs are at the bottom left, and the intersections within the tree represent the multiplexers yosys placed into my design. At the top, then is the result of this logic.
What if I could balance the tree?
 |
Were I able to balance the tree, I might then use fewer multiplexers, the decoding logic would get far simpler, and the longest path far shorter, perhaps as short as Fig 2 on the left.
Was it doable?
In this example, I was issuing requests to one of several slaves, never to more than one slave at a time, then listening for the requests in return. So I got to thinking, what if I also created an index to describe the one slave that would respond? In that fashion, the above code could be simplified to something closer to:
always @(posedge i_clk)
begin
o_ack = slave_ack[slave_index];
o_data = slave_data[slave_index];
endAlternatively, I could’ve written this output in a case statement–had I known how many slaves. An example of such a case statement for four slaves might look something like,
always @(posedge i_clk)
case(slave_index)
2'b00: { o_ack, o_data } <= { slave_ack[0], slave_dat[0] };
2'b01: { o_ack, o_data } <= { slave_ack[1], slave_dat[1] };
2'b10: { o_ack, o_data } <= { slave_ack[2], slave_dat[2] };
2'b11: { o_ack, o_data } <= { slave_ack[3], slave_dat[3] };
endcaseSurely that would be better, right?
It was time to run some tests.
The basic logic test
Some time ago, I had the wonderful opportunity to meet Jan Gray. While you may know me for advertising a resource constrained 32-bit CPU that I call the ZipCPU, Jan has been known for stuffing many, many CPUs within an FPGA.
Much as I hate to admit it, his CPUs are often much smaller than mine. So, I asked him, how do you get your CPUs that small? I found his answer very enlightening.
He said, and I’m paraphrasing here, to start with the clock rate you want to achieve. Then start piecing small bits of logic together here and there, and just run these tiny pieces of logic through the synthesizer–never the whole design. Look at what the synthesizer does with these tiny pieces, the number of LUTs they create, their timing performance, and then optimize these small pieces at the low level. In this way, you can gradually work your way up to the whole.
No, that’s not a direct quote. About a year and a half has passed since that conversation, but his point remains: optimize your design piecemeal at the very low level, and learn optimization there. It will then be easier to create a larger design from the lessons you’ve learned.
So, let’s do that here!
Imagine if you will that we have four sources of data, a through d. Each
of these sources has a select line, asel through dsel, telling us when
their respective data words, adata through ddata are valid. Our goal
will be to set our own output, odata, to contain the data from the one valid
input data word.
The code for this would look something like the one below.
module testa(asel, adata, bsel, bdata, csel, cdata, dsel, ddata, odata);
input wire asel, bsel, csel, dsel;
input wire [31:0] adata, bdata, cdata, ddata;
output reg [31:0] odata;
always @(*)
if (asel)
odata = adata;
else if (bsel)
odata = bdata;
else if (csel)
odata = cdata;
else
odata = ddata;
endmoduleLet’s run this through yosys and see what we can learn.
% yosys
yosys> read -sv test.v
# ... lots of stuff
yosys> synth_ice40 -top testa
# ... skipping even more stuff, then ...
#
2.42. Printing statistics.
=== testa ===
Number of wires: 73
Number of wire bits: 228
Number of public wires: 9
Number of public wire bits: 164
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 96
SB_LUT4 96
2.43. Executing CHECK pass (checking for obvious problems).
checking module testa..
found and reported 0 problems.
yosys>So we now know that this code would cost us 96 LUTs–essentially 3 LUTs for every outgoing data bit.
Can we do better?
Suppose we instead had an index, which could indicate for us which of the
four inputs we wanted to set our output to. Such an example might look like
this one:
module testb(index, adata, bdata, cdata, ddata, odata);
input wire [1:0] index;
input wire [31:0] adata, bdata, cdata, ddata;
output reg [31:0] odata;
always @(*)
case(index)
2'b00: odata = adata;
2'b01: odata = bdata;
2'b00: odata = cdata;
2'b01: odata = ddata;
endcase
endmoduleThis time, yosys tells us that we could calculate our outgoing data using only two LUTs per output bit.
2.42. Printing statistics.
=== testb ===
Number of wires: 38
Number of wire bits: 194
Number of public wires: 6
Number of public wire bits: 162
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 64
SB_LUT4 64If you find yourself like me, scrounging for every LUT you can in order to maintain your reputation as a log-logic designer, 32 LUTs is a big difference. It might get even bigger if this sort of savings could be replicated across the design.
Moving to the CPU
 |
So I took a look within the ZipCPU. As you may recall, the ZipCPU has a couple of functional units. There’s the ALU, which can perform basic arithmetic, the memory unit, which can load values from memory and stores them back again, and the divide unit. Not shown in Fig. 3, is the fact that the external debugging port can also write values to the registers within the CPU. I’ve also dreamed of creating a floating point unit, so let’s include that in our discussion as well.
Now, each of these three units can return a valid signal, indicating that it
has an item to write to the register file, a data signal, containing the
data to be written, and similarly, many of the units can return an error signal.
The logic, then, to determine when to write a value to a register looks something like the following:
assign wr_reg_ce = (dbgv)||(mem_valid)
||((!clear_pipeline)&&(!alu_illegal)
&&(((alu_wR)&&(alu_valid))
||((div_valid)&&(!div_error))
||((fpu_valid)&&(!fpu_error))));Does this look at all like the logic cascade we were dealing with above?
How about the logic to determine which of the various values needs to be written to the register file? That looks like another logic cascade:
assign wr_gpreg_vl = ((mem_valid) ? mem_result
:((div_valid|fpu_valid))
? ((div_valid) ? div_result:fpu_result)
:((dbgv) ? dbg_val : alu_result));Well, actually, it’s worse. If you look at the code I referenced above,
you’ll notice that I calculated the value twice, once for wr_gpreg_vl and
another time for wr_spreg_vl. I had to do this just to keep any updates to
the program counter
and the status register
off of the critical path.
This logic doesn’t need to be so complex!
The ZipCPU is very much an in order processor. Sure, it is pipelined, but by the time you get to this stage in the pipeline, you already know what component will be producing a value. Hence, I could’ve used an index instead.
So let’s instead create a simple test, just to estimate what the impact of this change will be. Let’s say that this is our current logic.
module testcpu(dbgv, clear, wb, aluv, memv, divv, fpuv,
dbgerr, aluerr, memerr, diverr, fpuerr,
dbgdata, aludata, memdata, divdata, fpudata,
ov, odata);
input wire dbgv, clear, wb, aluv, memv, divv, fpuv;
input wire dbgerr, aluerr, memerr, diverr, fpuerr;
input wire [31:0] dbgdata, aludata, memdata, divdata, fpudata;
output reg ov;
output reg [31:0] odata;
always @(*)
ov = (dbgv | memv) || (!clear && wb) &&
((aluv && !aluerr) || (memv && !memerr)
||(divv && !diverr) || (fpuv && !fpuerr));
always @(*)
if (memv)
odata = memdata;
else if (divv | fpuv)
odata = (divv ? divdata : fpudata);
else if (dbgv)
odata = dbgdata;
else // if (aluv)
odata = aludata;
endmoduleIf you compare this to the actual logic above, you should see some strong similarities.
So let’s ask, how much logic does this use? A quick run through yosys yields the following result:
2.42. Printing statistics.
=== testcpu ===
Number of wires: 117
Number of wire bits: 303
Number of public wires: 19
Number of public wire bits: 205
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 131
SB_LUT4 131Can we do better?
Sure we can! Let’s add in just a little bit of precursor logic. In this
case, imagine we know we will have to write to the
ALU
on the clock after prealu is true, and likewise for the other values.
This means we’ll need to create an index first from these pre* values,
and so change our test case to:
module testcpui(i_clk, pred, prealu, premem, prediv, prefpu,
dbgv, clear, wb, aluv, memv, divv, fpuv,
dbgerr, aluerr, memerr, diverr, fpuerr,
dbgdata, aludata, memdata, divdata, fpudata,
ov, odata);
input wire i_clk;
input wire pred, prealu, premem, prediv, prefpu;
input wire dbgv, clear, wb, aluv, memv, divv, fpuv;
input wire dbgerr, aluerr, memerr, diverr, fpuerr;
input wire [31:0] dbgdata, aludata, memdata, divdata, fpudata;
output reg ov;
output reg [31:0] odata;
reg [2:0] index;
initial index = 0;
always @(posedge i_clk)
if (pred)
index <= 3'h0;
else if (prealu)
index <= 3'h1;
else if (premem)
index <= 3'h2;
else if (prediv)
index <= 3'h3;
else // if (fpuv)
index <= 3'h4;Once we have this three bit index, we can now create logic based around a case
statement to decode our results. As before ov will tell us when our output is
valid and hence when we need to write to the register file,
always @(*)
case(index)
3'h0: ov = (dbgv);
3'h1: ov = (clear && !wb) && (aluv && !aluerr);
3'h2: ov = (memv);
3'h3: ov = (clear && !wb) && (divv && !diverr);
3'h4: ov = (clear && !wb) && (fpuv && !fpuerr);
default: ov = 0;
endcasewhereas odata will be the value we write to the register file.
always @(*)
case(index)
3'h0: odata = dbgdata;
3'h1: odata = aludata;
3'h2: odata = memdata;
3'h3: odata = divdata;
default: odata = fpudata;
endcase
endmoduleWhat kind of logic usage might this garner?
Any guesses?
=== testcpui ===
Number of wires: 103
Number of wire bits: 291
Number of public wires: 26
Number of public wire bits: 214
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 113
SB_DFFSR 3
SB_LUT4 110110 LUTs! That’s a savings of nearly 20%!
What about that SB_DFFSR line? That’s new. Those three SB_DFFSRs
are the
flip-flops
holding the three bits of our index. In most all of my designs, I’ve been
LUT
starved, not
flip-flops
starved, so I’m not really worried about these.
Resource measurement is not just for iCE40s
Did you know you could measure resource usage for Xilinx chips, Intel chips, as well as ASIC gates using this approach with yosys?
If you wanted to do this for a Xilinx design, for example, all you’d need to change is the synth_ice40 line to a synth_xilinx line. Indeed, in my experience, you’ll also get a much faster result using yosys than using any of the Vendor tools–Vivado, ISE, or even Quartus. Feel free to check me out on this.
$ yosys
yosys> read -sv test.v
yosys> synth_xilinx -top testcpu
# ...
=== testcpu ===
Number of wires: 116
Number of wire bits: 302
Number of public wires: 19
Number of public wire bits: 205
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 130
LUT3 32
LUT5 1
LUT6 65
MUXF7 32So our basic design would require 65 6-input LUTs, one 5-input LUT, and 32 3-input LUTs. The 32 MUXF7s are needed to combine 64 of those 6-input LUTs together in order to make 32 7-input LUTs.
If you now swap design approaches to use the index, the LUT usage drops dramatically:
=== testcpui ===
Number of wires: 67
Number of wire bits: 257
Number of public wires: 26
Number of public wire bits: 214
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 79
FDRE 3
LUT2 5
LUT3 1
LUT4 1
LUT5 16
LUT6 52
MUXF7 1If you figure that the MUXF7s are really there for free, then we dropped our logic needs from 98 6-input LUTs down to 78–again this is about a 20% improvement or so.
Ever had to try to answer the question, “how complex is your design?” and the questioner wants your answer in gates? We can do that too! In this case, just run synth, a generic synthesis routine, followed by abc -g cmos2, to map your design to traditional CMOS gates, and then stat to report the results.
$ yosys
yosys> read -sv test.v
yosys> synth
yosys> abc -g cmos2
yosys> stat
=== testcpu ===
Number of wires: 729
Number of wire bits: 915
Number of public wires: 19
Number of public wire bits: 205
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 433
$_NAND_ 293
$_NOR_ 70
$_NOT_ 70That is, our pre-optimized design will require 293 NAND gates, 70 NOR gates, and another 70 NOT gates.
Similarly, after our optimization, you’d get:
=== testcpui ===
Number of wires: 856
Number of wire bits: 1046
Number of public wires: 26
Number of public wire bits: 214
Number of memories: 0
Number of memory bits: 0
Number of processes: 0
Number of cells: 396
$_DFF_P_ 3
$_NAND_ 238
$_NOR_ 80
$_NOT_ 75If we don’t count the flip-flops, then you can see that we’ve dropped from 433 gates down to 393. This time the savings isn’t nearly as much, but 10% fewer gates translates to area in the ASIC business, and lower area translates to lower cost.
Conclusion
Perhaps you’ve picked up on a couple of points from this discussion. First, if you are concerned about minimum area and minimum logic, then it’s important to know a bit about what’s happening under the hood. Second, that yosys dump command was what tipped me off to what was going on under the hood. Yosys also supports a show command for those who would rather view this information graphically. Third, you can compare various design techniques in seconds when using yosys. It’s really quite a valuable lesson.
I’ve just rewritten how AutoFPGA handles its address decoding as a result. While I’m still working through some of the pains of that rewrite, it turns out that it wasn’t all that hard to do.
Adjusting how the ZipCPU determines whether or not to write back, and which value to write back to the register file is likely to be next. Perhaps you might want to consider at this point, what formal properties could be used in a switch like this, and how easy (or hard) would it be to convince yourself that the updated code still worked as before?
I should also mention, there is another competing theory out there espoused by the major vendors. This theory is that you should build your design, count up the gates you need, and buy your chip. If your algorithm doesn’t fit in the chip, then you need to buy a bigger chip and possibly even build a bigger board. This also applies to much of the vendor supplied IP. The major vendors have no incentive to build low-logic designs, if their low logic designs would keep you from buying more of their product.
Think about it.
Oh, one more thing, remember that bug that sent me looking into the yosys dump in the first place? Yeah, that one. It was my own fault. The problem was just obscured by the for loop I was using, and the fact that for loops in Verilog don’t work like they do in C++.
It is naught, it is naught, saith the buyer: but when he is gone his way, then he boasteth. (Prov 20:14)