A parallel prefix network solves the following equations given some binary associative operator (denoted by $\oplus$ in the equations and +: in the code blow).
Given $x_{0},x_{1},...$ we compute $y_{0},y_{1},...$
The obvious solution is basically a fold that tracks each step of the computation (aka scan).
In [1]:
let serial (+:) l =
let h,t = List.hd l, List.tl l in
let o = List.fold_left (fun a b -> (b +: (List.hd a)) :: a) [h] t in
List.rev o
Out[1]:
val serial : ('a -> 'a -> 'a) -> 'a list -> 'a list = <fun>
Of the following solutions serial is probably the best suited to software as it performs the minimum amount of computation. By allowing more computations, but arranging them in parallel, we can optimise for other metrics such as critical path delay (or parallelism).
The following implementations of three parallel prefix algorithms are designed to arrange the given (+:) operator with the appropriate inputs.
They have the following properties:
In [2]:
let split_pow2 l =
let open HardCaml in
let w = List.length l in
if w = 0 then [],[]
else if w = 1 then l,[]
else
let x = 1 lsl ((Utils.clog2 w)-1) in
Utils.lselect l 0 (x-1), Utils.lselect l x (w-1)
let rec sklansky (+:) l =
match l with
| [] -> failwith "sklansky"
| [a] -> [a]
| _ ->
let s,t = split_pow2 l in
let s = sklansky (+:) s in
let t = sklansky (+:) t in
let s' = List.hd (List.rev s) in
let t = List.map (fun t -> t +: s') t in
s @ t
Out[2]:
val split_pow2 : 'a list -> 'a list * 'a list = <fun>
Out[2]:
val sklansky : ('a -> 'a -> 'a) -> 'a list -> 'a list = <fun>
In [3]:
let rec brent_kung (+:) l =
match l with
| [] -> failwith "brent_kung"
| [a] -> [a]
| _ ->
let p = HardCaml.Utils.pairs l in
let l = List.map (fun (a,b) -> b +: a) p in
let l = brent_kung (+:) l in
let p = List.map fst p in
let ph,pt = List.hd p, List.tl p in
let lt,lh =
let l = List.rev l in
List.rev (List.tl l), List.hd l
in
let o = List.flatten (List.map2 (fun a b -> [a; b +: a]) lt pt) in
ph :: (o @ [lh])
Out[3]:
val brent_kung : ('a -> 'a -> 'a) -> 'a list -> 'a list = <fun>
In [4]:
let kogge_stone (+:) l =
let open HardCaml.Utils in
let l' = List.length l in (* must be power of two *)
let rec b n l =
if n=0 then l
else
let l = b (n/2) l in
let l0,l1,l2 =
lselect l 0 (n-1), lselect l n (l'-1),
lselect l 0 (l'-n-1)
in
l0 @ (List.map2 (+:) l1 l2)
in
b (l' / 2) l
Out[4]:
val kogge_stone : ('a -> 'a -> 'a) -> 'a list -> 'a list = <fun>
Starting with an obvious test $x=[1;1;1;1]$ should give $y=[1;2;3;4]$ if the operator is addition.
In [5]:
let x = [1;1;1;1]
Out[5]:
val x : int list = [1; 1; 1; 1]
In [6]:
let y = serial (+) x
Out[6]:
val y : int list = [1; 2; 3; 4]
In [7]:
let y = sklansky (+) x
Out[7]:
val y : int list = [1; 2; 3; 4]
In [8]:
let y = brent_kung (+) x
Out[8]:
val y : int list = [1; 2; 3; 4]
In [9]:
let y = kogge_stone (+) x
Out[9]:
val y : int list = [1; 2; 3; 4]
Now lets assume the serial implementation is correct and use it to test the other networks.
The kogge_stone implementation requires inputs to be a power of two in length
In [10]:
let test l =
let y = serial (+) l in
assert (y = sklansky (+) l);
assert (y = brent_kung (+) l);
assert (y = kogge_stone (+) l);
y
Out[10]:
val test : int list -> int list = <fun>
In [11]:
test [7;2]
Out[11]:
- : int list = [7; 9]
In [12]:
test [4;1;3;7]
Out[12]:
- : int list = [4; 5; 8; 15]
In [13]:
test [4;1;3;7;12;9;87;111]
Out[13]:
- : int list = [4; 5; 8; 15; 27; 36; 123; 234]
The most basic adder is the carry ripple adder.
$$s_{i}=a_{i} \oplus b_{i} \oplus c_{i}$$$$c_{i+1}=(a_{i}.b_{i}) \oplus (a_{i}.c_{i}) \oplus (b_{i}.c_{i})$$$$c_{0}=c_{in}$$Implemented in hardware the most significant bit of the adder has a delay proportional to number of bits in the operands. A parallel prefix network can optimise the critical path at the cost of hardware size and routability.
To do so the carry computation needs to be reformulated. In the formulae above the $c_{i}$ depends on $c_{i-1}$. The trick is to make $c_{i}$ depend on only $c_{0}$. First, for each input bit
$$x_{i} = (p_{i},g_{i}) = (a_i \oplus b_i,a_i.b_i)$$
In [14]:
open HardCaml.Signal.Comb
let preprocess a b =
List.map2 (fun x y -> x &: y, x ^: y) (List.rev (bits a)) (List.rev (bits b))
Out[14]:
val preprocess : t -> t -> (t * t) list = <fun>
The carry computation can now be carried out in terms of the propogate and generate bits using
$$y_{i} = (P_{i},G_{i}) = (p_{i},g_{i}) \circ (P_{i-1},G_{i-1}) = x_{i} \circ y_{i-1}$$$$(p_{x},g_{x}) \circ (p_{y},g_{y}) = (g_{x} \oplus p_{x}.g_{y},p_{x}.p_{y})$$
In [15]:
let prefix_op (gx,px) (gy,py) = (gx |: (px &: gy), px &: py)
Out[15]:
val prefix_op : t * t -> t * t -> t * t = <fun>
The final sums are calculated with
$$s_{i}=p_{i}.c_{i}$$$$c_{i}=G_{i-1} \oplus (P_{i-1}.c_{in})$$$$c_{0}=c_{in}$$
In [16]:
let postprocess cin i o =
let c = List.map (fun (g,p) -> g |: (p &: cin)) o in
let s = List.map2 (fun (_,p) c -> p ^: c) (i@[gnd,gnd]) (cin::c) in
concat (List.rev s)
Out[16]:
val postprocess : t -> (t * t) list -> (t * t) list -> t = <fun>
Putting it all together
In [17]:
let prefix_adder network a b cin =
let i = preprocess a b in
let o = network prefix_op i in
postprocess cin i o
Out[17]:
val prefix_adder :
((t * t -> t * t -> t * t) -> (t * t) list -> (t * t) list) ->
t -> t -> t -> t = <fun>
In [18]:
prefix_adder serial (consti 4 3) (consti 4 5) gnd
Out[18]:
- : t =
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 77L; s_names = []; s_width = 5;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 76L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 2L; s_names = ["gnd"]; s_width = 1;
s_deps = []},
"0");
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 71L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 63L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 54L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 46L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 38L;
s_names = []; s_width = 4; s_deps = []},
"0011")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 42L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 37L;
s_names = []; s_width = 4; s_deps = []},
"0101")]},
3, 3)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 62L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 53L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 46L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 38L;
s_names = []; s_width = 4; s_deps = []},
"0011")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 42L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 37L;
s_names = []; s_width = 4; s_deps = []},
"0101")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 60L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 52L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 45L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 38L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 41L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 37L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
2, 2)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 59L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 51L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 45L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id =
38L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 41L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id =
37L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
2, 2)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 57L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 50L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id =
44L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id
= 38L;
s_names = [];
s_width = 4;
s_deps = []},
"0011")]},
1, 1);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id =
40L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id
= 37L;
s_names = [];
s_width = 4;
s_deps = []},
"0101")]},
1, 1)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 56L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id =
49L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id
= 44L;
s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id
= 38L;
s_names = [];
s_width = 4;
s_deps = []},
"0011")]},
1, 1);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id
= 40L;
s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id
= 37L;
s_names = [];
s_width = 4;
s_deps = []},
"0101")]},
1, 1)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id =
48L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id
= 43L;
s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id
= 38L;
s_names = ...;
s_width = ...;
s_deps = ...},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...)
In [19]:
prefix_adder sklansky (consti 4 3) (consti 4 5) vdd
Out[19]:
- : t =
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 121L; s_names = []; s_width = 5;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 120L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 2L; s_names = ["gnd"]; s_width = 1;
s_deps = []},
"0");
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 115L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 107L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 101L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 95L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 87L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 79L;
s_names = []; s_width = 4; s_deps = []},
"0011")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 83L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 78L;
s_names = []; s_width = 4; s_deps = []},
"0101")]},
3, 3)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 100L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 94L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 87L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 79L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 83L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 78L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 93L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 86L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 79L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 82L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 78L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
2, 2)]},
HardCaml.Signal.Types.Signal_and)]},
HardCaml.Signal.Types.Signal_and)]},
HardCaml.Signal.Types.Signal_or);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 106L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 99L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 94L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 87L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 79L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 83L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 78L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 92L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 86L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 79L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 82L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 78L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
2, 2)]},
HardCaml.Signal.Types.Signal_xor)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 98L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 91L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 85L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 79L;
s_names = []; s_width = 4;
s_deps = []},
"0011")]},
1, 1);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 81L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 78L;
s_names = []; s_width = 4;
s_deps = []},
"0101")]},
1, 1)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 97L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 90L;
s_names = []; s_width = 1;
s_deps = [...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...)
In [20]:
prefix_adder kogge_stone (consti 4 2) (consti 4 6) vdd
Out[20]:
- : t =
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 168L; s_names = []; s_width = 5;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 167L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 2L; s_names = ["gnd"]; s_width = 1;
s_deps = []},
"0");
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 162L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 154L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 148L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 139L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 131L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 123L;
s_names = []; s_width = 4; s_deps = []},
"0010")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 127L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 122L;
s_names = []; s_width = 4; s_deps = []},
"0110")]},
3, 3)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 147L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 138L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 131L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 123L;
s_names = []; s_width = 4;
s_deps = []},
"0010")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 127L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 122L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 137L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 130L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 123L;
s_names = []; s_width = 4;
s_deps = []},
"0010")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 126L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 122L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
2, 2)]},
HardCaml.Signal.Types.Signal_and)]},
HardCaml.Signal.Types.Signal_and)]},
HardCaml.Signal.Types.Signal_or);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 153L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 146L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 138L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 131L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 123L;
s_names = []; s_width = 4;
s_deps = []},
"0010")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 127L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 122L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 136L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 130L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 123L;
s_names = []; s_width = 4;
s_deps = []},
"0010")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 126L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 122L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
2, 2)]},
HardCaml.Signal.Types.Signal_xor)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 142L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 135L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 129L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 123L;
s_names = []; s_width = 4;
s_deps = []},
"0010")]},
1, 1);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 125L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 122L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
1, 1)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 141L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 134L;
s_names = []; s_width = 1;
s_deps = [...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...)
In [21]:
prefix_adder kogge_stone (consti 4 6) (consti 4 7) gnd
Out[21]:
- : t =
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 215L; s_names = []; s_width = 5;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 214L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 2L; s_names = ["gnd"]; s_width = 1;
s_deps = []},
"0");
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 209L; s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 201L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 195L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 186L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 178L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 170L;
s_names = []; s_width = 4; s_deps = []},
"0110")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 174L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 169L;
s_names = []; s_width = 4; s_deps = []},
"0111")]},
3, 3)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 194L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 185L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 178L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 170L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 174L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 169L;
s_names = []; s_width = 4;
s_deps = []},
"0111")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 184L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 177L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 170L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 173L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 169L;
s_names = []; s_width = 4;
s_deps = []},
"0111")]},
2, 2)]},
HardCaml.Signal.Types.Signal_and)]},
HardCaml.Signal.Types.Signal_and)]},
HardCaml.Signal.Types.Signal_or);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 200L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 193L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 185L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 178L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 170L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
3, 3);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 174L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 169L;
s_names = []; s_width = 4;
s_deps = []},
"0111")]},
3, 3)]},
HardCaml.Signal.Types.Signal_xor);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 183L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 177L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 170L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
2, 2);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 173L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 169L;
s_names = []; s_width = 4;
s_deps = []},
"0111")]},
2, 2)]},
HardCaml.Signal.Types.Signal_xor)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 189L; s_names = [];
s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 182L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 176L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 170L;
s_names = []; s_width = 4;
s_deps = []},
"0110")]},
1, 1);
HardCaml.Signal.Types.Signal_select
({HardCaml.Signal.Types.s_id = 172L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_const
({HardCaml.Signal.Types.s_id = 169L;
s_names = []; s_width = 4;
s_deps = []},
"0111")]},
1, 1)]},
HardCaml.Signal.Types.Signal_and);
HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 188L;
s_names = []; s_width = 1;
s_deps =
[HardCaml.Signal.Types.Signal_op
({HardCaml.Signal.Types.s_id = 181L;
s_names = []; s_width = 1;
s_deps = [...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...);
...]},
...)
Content source: ujamjar/hardcaml
Similar notebooks: