First implementation Rewrote it into nz_detect4 [a] = a nz_detect4 as = out where (as1,as2) = halveList as out1 = nz_detect4 as1 out2 = nz_detect4 as2 out = or2(out1,out2)

binTree op [a] = a binTree op as = out where (as1,as2) = halveList as out1 = binTree op as1 out2 = binTree op as2 out = op(out1,out2)

nz_detect4 = binTree or2

- Split up a monolithic solution into a reusable connection pattern and a simple solution
- Functional programming languages makes this easy!

First implementation | Rewrite it into |
---|---|

nz_detect3 [] = low nz_detect3 (a:as) = out where out = or2(a,out2) out2 = nz_detect3 as | chain op [a] = a chain op (a:as) = out where out = op(a,out2) out2 = chain op as nz_detect3 = chain or2 |

- We now have two similar connection patterns:
`binTree :: (`

**(a,a)->a**) -> (**[a]->a**)`chain :: (`

**(a,a)->a**) -> (**[a]->a**)

- Similarities and differences:
- Both turn a two-input operator into an n-input operator
- One builds a balanced tree, the other builds a linear chain

- But do
`chain`

and`op``binTree`

always compute the same result?`op`

- chain (*) [a,b,c,d,e,f,g,h] = a*(b*(c*(d*(e*(f*(g*h))))))
- binTree (*) [a,b,c,d,e,f,g,h] = ((a*b)*(c*d))*((e*f)*(g*h))
- a*(b*(c*(d*(e*(f*(g*h)))))) = ((a*b)*(c*d))*((e*f)*(g*h)) ?
- This holds if * is...
**associative**: (a*b)*c=a*(b*c)

- Take a look at the types of these connection patterns again:
`binTree :: ( (a,a)->a ) -> ( [a] -> a)`

`chain :: ( (a,a)->a ) -> ( [a] -> a)`

- They are
*generic*functions, so they work for arbitrary Haskell values

- An operator for measuring circuit depth:
`depth (a,b) = max a b + 1`

- We can now compare
`chain depth (replicate 16 0)`

= 15`binTree depth (replicate 16 0)`

= 4

- Here we compute with pure Haskell values

*Circuit generation*rather than*circuit description*.- Circuit generators can
*still look like*circuit descriptions. - Mary Sheeran:
*clever circuits*can control the choice of components, wiring and topology. - Designers can work with nice looking high level circuit descriptions, but still control low-level aspects of the design.

`row`

?
`chain`

can be seen as a special case!chain op (a:as) = out where (_,out) = row rowop (a,as) rowop (a,b) = ((),op(a,b))

- Alternatively,
`row`

can be seen as a generalization of`chain`

.

- Alternatively,

- Consider these two properties
- Structure: linear chain or balanced tree?
- Which outputs: only one final output or output from every op?

- Do we have all combinations?
Linear Tree Final output `chain`

`binTree`

Every op `row`

??? - What would we use the 4th operator for? ...
Linear Tree Final output `slowZeroDetect = chain or2`

`fastZeroDetect = binTree or2`

Every op `rippleCarryAdder = row fullAdder`

`fastAdder = ??? fullAdder`

- This requires some further thought...

- The carries ripple through in a linear chain.
- Hard to imagine how to rearrange full adders into a tree structure.
- Where is the associative operator?

- g = a ∧ b

p = a ⊕ b - c
_{out}= g ∨ (c_{in}∧ p) - Note: if c
_{in}=0, then c_{out}= g

g = g2 ∨ (g1 ∧ p2)

p = p1 ∧ p2- In Lava:
`dotOp ((g1,p1),(g2,p2)) = (g2 ∨ (p2 ∧ g1),p1 ∧ p2)`

- This operator is associative!
`chain dotOp = binTree dotOp`

- We can compute the c
_{out}from a`n`-bit adder with a circuit of depth log₂`n`.

- We can build a fast adder from these blocks:
map gp ... binTree? dotOp ... map sumBit ... - But we need the right tree pattern.
`binTree`

is not enough.

- Given
- Inputs x
_{1}, x_{2}, x_{3}, ..., x_{n} - an associative operator *

- Inputs x
- Compute
- x
_{1}, x_{1}*x_{2}, x_{1}*x_{2}*x_{3}, ..., x_{1}*x_{2}*x_{3}*...*x_{n}

- x

- Microprocessors cotain lots of parallel prefix circuits
- Addition (integer and floating point)
- Address calculation
- Priority encoding
- ...

- They need to be fast and have low power consumption

- We have
`chain, binTree :: (`

**(a,a)->a**) -> (**[a]->a**)

- We need
`ripple, sklansky :: (`

**(a,a)->a**) -> (**[a]->[a]**)

- Example (
*writing*):`abc`

instead of`a*b*c`

etc`chain (*) [a,b,c,d,e,f,g,h] =`

binTree (*) [a,b,c,d,e,f,g,h] = abcdefgh`ripple (*) [a,b,c,d,e,f,g,h] =`

sklansky (*) [a,b,c,d,e,f,g,h] = [a,ab,abc,abcd,abcde,abcdef,abcdefg,abcdefgh]

`ripple`

- The circuit depth grows linearly with the number of input bits

`ripple`

work?
ripple (*) [a,b,c,d,e,f,g,h] = a: ripple (*) [ab,c,d,e,f,g,h] = a: ab: ripple (*) [abc,d,e,f,g,h] = a: ab: abc: ripple (*) [abcd,e,f,g,h] = a: ab: abc: abcd: ripple (*) [abcde,f,g,h] = a: ab: abc: abcd: abcde: ripple (*) [abcdef,g,h] = a: ab: abc: abcd: abcde: abcdef: ripple (*) [abcdefg,h] = a: ab: abc: abcd: abcde: abcdef: abcdefg: ripple (*) [abcdefgh] = a: ab: abc: abcd: abcde: abcdef: abcdefg: [abcdefgh] = [a, ab, abc, abcd, abcde, abcdef, abcdefg, abcdefgh]

ripple

**::**((a,a)**->**a)**->**[a]**->**[a] ripple op [a]**=**[a] ripple op (a**:**b**:**cs)**=**a**:**rs**where**rs**=**ripple op (ab**:**cs) ab**=**op(a,b)- Similar to
`row`

, but the single output from`op`

is both part of the result and propagated to the next`op`

.

`sklansky`

in Lava?
`sklansky (*) [a,b,c,d,e,f,g,h]`

= ?
- Use
`halveList`

:- halveList [a,b,c,d,e,f,g,h] = ([a,b,c,d],[e,f,g,h])

- Compute the results for the halves:
- sklansky (*) [a,b,c,d] = [a, ab, abc, abcd]
- sklansky (*) [e,f,g,h] = [e, ef, efg, efgh]

- Combine the results:
- [a, abc, abcd] ++ [abcd*e, abcd*ef, abcd*efg, abcd*efgh] =

[a, ab, abc, abcd, abcde, abcdef, abcdefg, abcdefgh]

- [a, abc, abcd] ++ [abcd*e, abcd*ef, abcd*efg, abcd*efgh] =

sklansky op [a]=[a] sklansky op as=bs++rswhere(as1,as2)=halveList as bs=sklansky op as1 cs=sklansky op as2 bn=last bs rs=[op(bn,c)|c<-cs]

`ripple depth (replicate 16 0)`

= [0,1,2,3,4,5,6,7,8,9,10,11,12,13,14,15]`sklansky depth (replicate 16 0)`

= [0,1,2,2,3,3,3,3,4,4,4,4,4,4,4,4]

sklanskyAdder (as,bs)

**=**sum**where**abs**=**zipp (as,bs) gps**=**map gp abs gps'**=**sklansky dotOp gps cs**=**map fst gps' sum**=**map sumBit (zipp (low**:**cs,abs++[(low,low)]))- Room for improving the circuits for the first and last bit in the sum
- Rewrite the code, or
- use
*clever circuits*!

nc

**=****Nothing**-- not connected c**=****Just**-- connected cleverSumBit (**Nothing**,**Nothing**)**=**low cleverSumBit (**Just**c_in,**Nothing**)**=**c_in cleverSumBit (**Nothing**,**Just**(a,b))**=**a ⊕ b cleverSumBit (Just c_in,Just (a,b)) = c_in ⊕ a ⊕ bcleverSklanskyAdder (as,bs)

**=**sum**where**abs**=**zipp (as,bs) gps**=**map gp abs gps'**=**sklansky dotOp gps cs**=**map fst gps' sum**=**map cleverSumBit (zipp (nc**:**map c cs,map c abs++[nc]))- Same as
`sklanskyAdder`

, except the last line

propAdder' myAdder n

**=**forAll (list n) $**\**as**->**forAll (list n) $**\**bs**->**prop_Equivalent binAdder myAdder (as,bs) fvAdder' adder**=****do**rs**<-**sequence [smv (propAdder' adder n)**|**n**<-**[1**..**32]] return (all (==**Valid**) rs) fvSklanskyAdder**=**fvAdder' sklanskyAdder fvCleverSklanskyAdder**=**fvAdder' cleverSklanskyAdder- Verifies that the new adders are equivalent to binAdder from the Lava library, for all sizes [1..32].

- Brent Kung (fewer ops, deeper, fanout only 2)
- Ladner Fischer
- Clever circuits: dynamic programming to search for optimal solutions

Sklansky:

- This week
- Lava lab deadline on Friday

- Next week
- Monday: Guest lecture by Kasyab P. Subramaniyan
- Tuesday: discussion and exam preparation
- Lava take home exam