Page 1

Lava 4

Hardware Description and Verification

Thomas Hallgren

2010-05-10

Page 2

Topics

Parallel prefix circuits and fast adders in Lava

Sklansky, the most well-know way of computing parallel prefix

Page 3

Back to our example

From the zero detection circuit example

Page 4
Back to our example

Apply the same trick to the linear solution

First implementationRewrite 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

Page 5

Comparing the two connection patterns

Page 6

Comparing two connection patterns

Page 7

Measuring combinatorial circuit depth

Page 8
Measuring combinatorial circuit depth
Page 9
Measuring combinatorial circuit depth

We can also write functions that involve both circuit components and arbitrary Haskell values

This hints at very powerful techniques for constructing circuits!

Page 10

Linear chains

Remember row?

Page 11

Classifying connection patterns

Page 12

Ripple carry adder revisited

Page 13

Carry Generate and Propagate

Page 14

Combining generate and propagate signals

When would the combination of two full adders generate/propagate carry?

Page 15

Fast adder components

Page 16

The Parallel Prefix Problem

Page 17
The Parallel Prefix Problem

Uses for parallel prefix circuits

Page 18

The Parallel Prefix Problem in Lava

Page 19

Serial prefix solution

Circuit diagram for ripple

Page 20
Serial prefix solution

How does 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]

Page 21
Serial prefix solution

Lava code

Page 22

Tree shaped prefix solution

Circuit diagram

Originally idea published by Sklansky in 1960

Page 23
Tree shaped prefix solution

How do we implement sklansky in Lava?

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

Page 24
Tree shaped prefix solution

Lava Code

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

Page 25

Measuring circuit depth

Page 26

Assembling an adder

Page 27

Clever circuits

A simple example: leaving some inputs disconnected

Page 28

Formal verification

Page 29

Other parallel prefix solutions

Page 30

Brent Kung

Page 31

Ladner Fischer


Sklansky:

Page 32

Next?