Hardware Languages of Mary Sheeran

Presented by Jeff Palm
Scribed by Peter Douglass

MuFP is an extension of FP a functional programming language. MuFP provides a succinct clear means of describing systolic regular arrays. The purpose of muFP is not to reason about existing circuits, but to derive new circuits.

Combinatorial circuits combine elements by arbitrary arcs. Systolic circuits are distinguished by using latches in all inner arcs.  That is, all inner arcs are clocked. Systollic circuits are a significant subclass of meaningful or useful circuits.  (Latches are denoted by a dot or circle on the arc.)

A question was raised in the audience whether the clocks for latches in systolic circuit may be driven at different clock rates.  The answer is that there is a single global clock.  Multiple latches may be used to implement delays representing integral multiples of a clock cycle.

The transition from FP to muFP

FP maps values to values.  MuFP maps streams of values to streams of values.  A stream of values is denoted with angled brackets thusly:

      <a0, a1, a2,...>

Some primitive functions in muFP are defined.

zip :

 <<a, b, c> <e, f, g>>          => <<a e> <b f> <c g>>

composition: 

    F * G

A law using composition and zip:     zip-1 * zip = id

(Discussion of whether zip * zip-1 ? id.  This is not well defined.)

construction

 is written |_F,G_| and is a function

map

   map F

Discussion:  FP originated with Backus.  Ethan' talk had the slogan FL = FP + something

Visual interpretation

A key component of muFP is that the primitive functions have a visual counterpart.

graphics omitted

Promotion of FP functions to muFP functions

[| F * G |] = [| F |] * [| G |]

[| [F,G] |] = zip * [ [| F |] , [| G |] ]

[| map F |] = zip * map [| F |] * zip

Example:  A Tally Circuit

(graphics omitted)

The tally circuit has output r high if r inputs are high.  If given a simple 3 input 1 output tally circuit as a base component, how would one construct a general tally circuit recursively?

(graphics omitted). 

Tal(n) = map R * zip * [ apndl * [ 0,Tal(n-1)*mst], [n,n,...,n], apndr * [Tal(n-1)*mst,0]

where

apndl appends an input to the left, apndr appends an input to the right and

mst F <a b c d> = <Fa Fb Fc d>

Note:  There is ambiguity in how mst (and many muFP) operators work regarding the number of inputs.  mst takes any number of inputs and  applies F to all but the last.

This is ugly.

Question:  What is Tal(0)?  What is the base case?  Position put forward that Tal(1) is the identity.  Counter position that T(1) has two outputs.  Tal(0) has 0 inputs and 1 output which is always high.

Comparison of FP with other languages

FP is a combinator language, with no lambda, let, no lifting of variables, common subexpression elimination

More Operators

reduce

/F

graphics omitted.  similar to fold, but with graphic interpretation

right array operator

R\

graphics omitted

left array operator

L\

triangle operator

>

Examples

R > F applies more and more F's to input.  Can anyone think of an circuit that might use the triangle op?  Multiplication with shifters.

Plumbing disambiguates the meanings of operators.

Creating a sort circuit from comparison circuits

    comp = [smaller, larger]

    insert = L \ comp * apl

    sort = / ins * last [id]

Q from audience.  A stream is infinite.  What does it mean to take last of an infinite stream?  Streams are _potentially_ infinite.

Q why not take 1st instead of last?

graphics omitted

Systolic Circuits

The goal was to describe systolic circuits, but so far we have only created combinatorial.  How to make circuit systolic?  The base component in the example is comp.  Insert is not systolic.  To make it so we use the transformation

   sys(Q) => L \ (s D Q)

where D is a latch or D-flip-flop and s is second

we derive

S > D ins = R > D L (S D comp) * appl

eventually we get

        = S ins s R > D

so

sort * < > D = systolicSort * m L > D

Punchline:  by sprinkling internal latches into non-systolic sort, we have to wait n cycles for output, but get all output lines available at once.

Question.  This is combinator programming.  What is the relationship to reactive programming?  What is relationship to point-free programming?  Combinator programming is different from reactive.