Pure combinational circuit without registers possible?

[ju-sh]

Hi.

Is it possible to have a circuit that doesn't use any registers in bsv?

Like a 2 bit adder?

Or would all circuits end up having registers?

[rsnikhil]

Certainly, you can express arbitrary combinational circuits in BSV.

Broadly speaking, any BSV expression with a "value type" (not involving Action or ActionValue types) represents a combinational circuit. For example, given two 1-bit signals 'a' and 'b', the expression

{(a & b, a ^ b}

represents a half-adder with the sum and carry bits. Any expression can be encapsulated into a function, e.g.,

function Bit #(2) half_adder (Bit #(1) a, Bit #(1) b);
   Bit #(1) s = a ^ b;
   Bit #(1) c = a & b;
   return { c, s };
endfunction

The following is a full adder, which also takes an carry-in bit argument:

function Bit #(2) fa (Bit #(1) a, Bit #(1) b, Bit #(1) c_in);
   Bit #(2) ab    = ha (a, b);
   Bit #(2) abc   = ha (ab[0], c_in); 
   Bit #(1) s     = abc[0];
   Bit #(1) c_out = (ab[1] | abc[1]);
   return {c_out, s}; 
endfunction 

With function composition and loops around such expressions, you can build this up into a full N-bit ripple-carry adder.

With recursive functions around such expressions, you can write more efficient adders like Wallace Tree Adders (look for 'Wallace.bs' in the bsc libraries).

And they can be polymporphic in N, the bit-widths of the inputs and outputs. See 'polymorpic types' in the manuals and tutorials.

And, finally, methods of modules can be purely combinational, so combinational circuits can be encapsulated in modules.

For standard arithmetic/logic operations, we typically don't build circuits up from scratch with AND/OR/NOT gates (unless one wants a specialist circuit like a Wallace adder); BSV provides a variety of arithmetic-logic operators addition, multiplication, AND, OR, XOR, arithmetic and logical shifts etc. and we leave it to Verilog/Synthesis tool to synthesize the details of those.

Conditional expressions represent multiplexers, and can be written in several ways (here 'a' and 'b' can be arbitrary expression but must have the same type):

((s == 0) ? a : b)

if (s == 0) then
   result = a;
else
   result = b;

case (s)
   0: result = a;
   1: result = b;
endcase

[ju-sh]

Thanks for the detailed reply with examples. Was very helpful.

I made this as an attempt at a 4b ripple carry adder:

package rca;

// Full adder
function Bit#(2) fa (Bit#(1) a, Bit#(1) b, Bit#(1) cin);
  Bit#(1) s = a ^ b ^ cin;
  Bit#(1) cout = (a & b) | (b & cin) | (a & cin);
  return {cout, s};
endfunction

// Ripple carry adder
function Bit#(TAdd#(w, 1)) rca (Bit#(w) a, Bit#(w) b, Bit#(1) cin);
  // Carry bits
  Bit#(TAdd#(w, 1)) cs;
  cs[0] = cin;

  // Sum bits
  Bit#(w) s;

  let wval = valueOf(w);

  for (Integer i=0; i<wval; i=i+1) begin
    let res = fa(a[i], b[i], cs[i]);
    s[i] = res[0];
    cs[i+1] = res[1];
  end

  return {cs[wval], s};
endfunction

endpackage

How can we write a test bench for it? I got to first have module here, right?
Would a register variable be needed there?

I tried:

module mkRca();
  Reg#(Bit#(4)) res <- mkReg(0);
  method Action start(Bit#(4) a, Bit#(4) b, Bit#(1) cin);
    res <= rca(a, b, cin);
  endmethod
endmodule

I had a glimpse at tutorial, but still wasn't sure.

A register won't be needed in the code for the adder itself, right? Only in the test bench?

[rsnikhil]

I have attached a tar file with some discussion and examples: tmp.tar.gz

The following text repeats the README in the tar file, for convenience.

// ================================================================

I made this as an attempt at a 4b ripple carry adder:

Actually (congratulations!) your solution is more general, it's a
'w'-bit ripple-carry adder, for any 'w'.

// ================================================================
(1) Re. rca

Your code in rca.bsv is functionally correct, although when we compile
it with 'bsc' we encounter a false-negative error message:

 Error: "src_BSV/rca.bsv", line 13, column 21: (G0028)
     `cs[4]' uses uninitialized value (the position shown is the object's
 declaration). If this error is unexpected, please consult KPNS #32.
 During elaboration of the body of rule `rl1' at "src_BSV/Top.bsv", line 8,
 column 9.
 During elaboration of `mkTop' at "src_BSV/Top.bsv", line 6, column 8.

It takes some analysis to realise that, no, you're not using any
unitialized bits; you're assigning each bit outside the loop or in a
loop iteration, before using it in the next loop iteration.
Unfortunately that analysis is beyond 'bsc's ability; hence it
conservatively produces that error message.

The solution is simple: appease 'bsc' by intializing 'cs'. Change:

Bit#(TAdd#(w, 1)) cs;

to

Bit#(TAdd#(w, 1)) cs = 0;

and then it will compile without complaint.

This small modification is in file 'rca1.bsv'.

// ================================================================
(2) Re. rca

Although perhaps overkill for this small example, file 'rca2.bsv'
shows 'rca' in a more "functional programming" style, using
higher-order functions map, zipWith and sscanl.

// ================================================================
(3) Re. testbench

A register won't be needed in the code for the adder itself, right?

No, the adder is fine, as is.

Only in the test bench?

Depends on what you want to do.

The file 'Top1.bsv' shows a simple testbench with no registers; its
one rule invokes 'rca' three times and prints results, and exits
simulation.

Since a pure function like 'rca' can be invoked any number of times in
a rule, see 'Top2.bsv' which does the full complement of 16x16 tests
in one rule, using a statically elaborated loop. They will all be
done "simultaneously" in one cycle.

The file 'Top3.bsv' uses a register to generate the 16x16 input
combinations. They will be done sequentially in 256 cycles.

The BSV libraries also contain pseudo-random-number generator modules
which you can import and instantiate to generate random inputs.

// ================================================================
(4) Running the examples:

In 'src_BSV',

• Copy or make a symbolic link from {rca1.bsv,rca2.bsv} to 'rca.bsv'.
• Copy or make a symbolic link from {Top1.bsv,Top2.bsv,Top3.bsv} to Top.bsv'.

In the top-level dir,
'$ make' for a list of available make-targets
'$ make b_all' for Bluesim compile/link/simulate
'$ make v_all' for IVerilog compile/link/simulate

See 'transcript_make_b_all_Top2_rca1.txt' for an example transcript.

// ================================================================

[ju-sh]

Thanks very much for taking the time to make the examples!
(Sorry for the very late response.. 😬)

The comments in the source files helped a lot.

Like this one in Top2.bsv:

Note: there'd be a problem with the following:
for (Bit #(8) ab = 0; ab <= 'h_FF; ab=ab+1) begin
because the loop condition is always true
(+1 wraps around to 0 on 8-bit value at 'h_FF)

I would've missed it otherwise.

---

The solution is simple: appease 'bsc' by intializing 'cs'. Change:

Earlier, I had been trying to figure out a way to make w'b0 where the value of w would be filled in. Hadn't realized that a simple 0 would've sufficed.. 🥴

file 'rca2.bsv' shows 'rca' in a more "functional programming" style, using higher-order functions map, zipWith and sscanl.

That certainly feels better.

Had an initial trouble understanding what sscanl was about, but then got hold if it. As the reference guide says, it's like fold with the intermediate values saved and first value skipped.

(The type looks more readable in haskell.)

---

The file 'Top1.bsv' shows a simple testbench with no registers; its
one rule invokes 'rca' three times and prints results, and exits
simulation.

Since a pure function like 'rca' can be invoked any number of times in
a rule, see 'Top2.bsv' which does the full complement of 16x16 tests
in one rule, using a statically elaborated loop. They will all be
done "simultaneously" in one cycle.

The file 'Top3.bsv' uses a register to generate the 16x16 input
combinations. They will be done sequentially in 256 cycles.

So, it would be like:

| Filename | Adder count | Cycle count |
|----------+-------------+-------------|
| Top1.bsv |           3 |           1 |
| Top2.bsv |         256 |           1 |
| Top3.bsv |           1 |         256 |

Is it?

---

Regarding using Tuple2 as return type of fa in function Tuple2 #(Bit#(1), Bit #(1)) fa (Bit#(1) a, Bit#(1) b, Bit#(1) cin); instead of plain Bit#(2), is that considered better? Ease of separating out the values, maybe?

---

Would using vectors instead of loops still result in the same circuit? They are merely containers?

I couldn't make it spit out verilog files. Probably because rca.bsv don't have any modules.

---

And thanks for the Makefile. It looks as if I can pull bits and pieces from it to make one of my own. 🙂