Lava 2

Hardware Description and Verification

Thomas Hallgren

2010-05-03

Today

Examples covering these topics

• Functions
• Lists
• Connection patterns
• Sequential circuits

Last week

Look back for a quick reminder.

Functions in Haskell

Two ways to handle multiple arguments

• Pairing arguments

  • f1 (x,y) = nand2(x,y)
    g1 (x,y) = x+y
    

• One argument at a time

  • f2 x y = nand2(x,y)
    g2 x y = x+y
    

• The latter solution is common in the Haskell libraries. It makes it easier to use a function without giving all arguments at once.
  • map (g2 3) [4,5,6] = [7,8,9]

Function types in Haskell

The two ways to handle multiple arguments is reflected in the types

• f1 :: (Bit,Bit) -> Bit
  f1 (x,y) = nand2(x,y)
  
  g1 :: (Int,Int) -> Int
  g1 (x,y) = x+y
  
  f2 :: Bit -> (Bit -> Bit)
  f2 x y = nand2(x,y)
  
  g2 :: Int -> Int -> Int
  g2 x y = x+y
  

• g2 3 :: Int->Int
• map (g2 3) :: [Int]->[Int]

Higher order functions

• The previous examples illustrates higher order functions
  • Pass functions as arguments to other functions
  • Return functions as results from functions
  • Functions can be bart of data structures
• Lava represents circuits as functions
  • Functions form input signals to output signals, e.g. (Bit,Bit)->Bit
  • Higher order functions can be used to combine circuits into bigger circuits

Composition of circuits

Serial composition

Serial composition of circuits

• We could do this

  • serial ((circ1,circ2),inp) = out
      where
        mid = circ1 inp
        out = circ2 mid
    

• Or this

  • serial (circ1,circ2) inp = out
      where
        mid = circ1 inp
        out = circ2 mid
    

• From the Lava library

  • serial circ1 circ2 inp = out
      where
        mid = circ1 inp
        out = circ2 mid
    
    circ1 ->- circ2 = serial circ1 circ2
    

• Pipelines: c1 ->- c2 ->- c3 -> c4

Composition of circuits

Parallel composition

Parallel composition of circuits

From the Lava library

• par f g (inp1,inp2) = (out1,out2)
    where
      out1 = f inp1
      out2 = g inp2
  
  f -|- g = par f g
  

• What is the type?

Composition of circuits

We have also seen

• The map function
  • map f [x1,x2,...,xn] = [f x1,f x2,...,f xn]
• The row function

  

• More connection patterns later

Feedback and sequential circuits

First example

• bad inp = out
    where
      out = nand2(inp,out)
  

• This doesn't work, try it in Lava...
  • simulate bad low
  • simulate bad high *** Exception: combinational loop

Delay in VHDL

• Signal assignments have no delay by default:
  • out <= a nand b;
• Delay can be introduced explicitly:
  • out <= a nand b after 4ns;

Delay in Lava

• The logical gates in the Lava library are "ideal" and have zero delay.
• Delay has to be modelled explicitly:
  • delay init s
    • Delays the signal s by one time unit.
    • The output during the first time unit is init.
    • The Lava library does not care how long a time unit is.
      • It could be the gate delay, for analyzing the effect of delay in combinational circuits
      • But usually, it is one clock cycle in a synchronously clocked sequential circuit.

Feedback and sequential circuits

Second example

• nand2D = nand2 ->- delay low
  
  good a = out
    where
      out = nand2D(a,out)
  

• Works better, but...
  • simulate good high
• ...we need the to use the sequence simulator
  • simulateSeq good [high,high,high,high]

Creating longer sequences for simulations

Sequences are lists, so we can use any list function in Haskell

• low5 = replicate 5 low
  high5 = replicate 5 high
  

• Example:
  • simulateSeq good (high5++low5++high5)
• The operator ++ joins two lists

List functions

We have seen

• zipp :: ([a],[b]) -> [(a,b)]
• unzipp :: [(a,b)] -> ([a],[b])
• replicate :: Int -> a -> [a]
• ++ :: [a] -> [a] -> [a]
• map :: (a->b) -> ([a] -> [b])

List functions

But all lists are built from two basic operators on lists

• []: the empty list
• x : xs: adding one more element to the front of a list
  • Example: 3:[4,5,6] = [3,4,5,6]
• In fact [3,4,5,6] is just a shorthand for 3:4:5:6:[]

Creating lists from scratch

How does replicate 3 low work?

replicate 3 low = low : replicate 2 low
                = low : low : replicate 1 low
                = low : low : low : replicate 0 low
                = low : low : low : []
                = [low,low,low]

Creating lists from scratch

How is replicate defined?

replicate 0 x = []
replicate n x = x : replicate (n-1) x

Consuming lists

• How do functions with list arguments work?
  • Example 1: the function sum sums a list of numbers
    • sum :: [Int] -> Int
    • sum [] = 0
    • sum [7,5,3,6] = 7+5+3+6 = 21
• How does sum work?

  • sum [7,5,3,6] = 7 + sum [5,3,6]
                  = 7 + 5 + sum [3,6]
                  = 7 + 5 + 3 + sum [6]
                  = 7 + 5 + 3 + 6 + sum []
                  = 7 + 5 + 3 + 6 + 0
                  = 21
    

Consuming lists

How is sum defined?

sum [] = 0
sum (x : xs) = x + sum xs

Consuming lists 2

• Example 2: the function minimum finds the minimum number in a list
  • minimum [7,3,6] = 3
  • minimum [] = ?? we want to leave it undefined
  • minimum [7] = 7
• Assume we have min2 :: (Int,Int) -> Int
• How does minimum work?

  • minimum [7,3,6] = min2(7,minimum [3,6])
                    = min2(7,min2(3,minimum [6]))
                    = min2(7,min2(3,6))
                    = min2(7,3)
                    = 3
    

Consuming lists 2

How is minimum defined?

minimum [] = error "minimum of empty list"
minimum [x] = x
minimum (x:xs) = min2(x,minimum xs)

Exercise

Zero detection

• Define a generic circuit that
  • inputs a binary number (represented as bit vector), and
  • outputs high if the number is zero (all bits are zero).
• zero_detect :: [Bit] -> Bit
• Simple solution first
• Also think about circuit depth and delay