[C.CC USERS] Modeling computer bits

Martin Ellis ellism88 at gmail.com
Fri Dec 31 23:51:47 GMT 2010


I don't know if its relavent but I belive peter wrote a paper on modeling
electonics in occam at some point. I don't think he covered ram though.

I think you may be able to model ram access using shared channel bundles.
Not sure if this fits the model though.

Martin

On 31 Dec 2010 19:30, "Matt Jadud" <matt at jadud.com> wrote:

Hi all,

I was poking around this morning, and came upon a design question that
I'm stuck on. My design question comes at the end, and everything else
is preamble. You might be able to read this message from the bottom up
for all I know...

I'm playing with "The Elements of Computer Systems" by Nisan and
Schocken. (I passed this book around the group at one point in the
past... where they build up from logic gates through to programming
languages.) The book has students implement computer bits in HDL, but
that's practically occam (or visa versa) within some epsilon, so I
thought I'd implement some of the bits.

Things like "and" were easy:

PROC and (CHAN BOOL a?, b?, o!)
 WHILE TRUE
   BOOL v.a, v.b:
   SEQ
     PAR
       a ? v.a
       b ? v.b
     o ! (v.a AND v.b)
:

Adders were straight forward as well. I then got into the stateful
components. For example, a data flip-flop, which becomes the core of a
"bit" (their abstraction for a state-holding 1-bit wide cell) looks
like this:

PROC mux (CHAN BOOL a?, b?, sel?, o!)
 WHILE TRUE
   BOOL v.a, v.b, v.sel:
   SEQ
     a ? v.a
     b ? v.b
     sel ? v.sel
     IF
       v.sel
         o ! v.a
       TRUE
         o ! v.b
:

PROC dff (CHAN BOOL in?, out!, BARRIER tick)
 INITIAL BOOL prev IS FALSE:
 WHILE TRUE
   BOOL state:
   SEQ
     SYNC tick
     PAR
       out ! prev
       in ? state
     prev := state
:

PROC bit (CHAN BOOL in?, load?, out!, BARRIER tick)
 WHILE TRUE
   CHAN BOOL dff.in, dff.out, loopback:
   PAR
     delta.bool (dff.out?, loopback!, out!)
     mux (in?, loopback?, load?, dff.in!)
     dff (dff.in?, dff.out!, tick)
:

I've used a BARRIER to simulate a clock tick; components like mux()
are continuous/parallel, while components like the bit (and therefore
registers built from bit()s) are clocked. I have, for the moment, used
a BARRIER to simulate the synchronization of a clock tick. (Other
suggestions welcome, but I wasn't sure how to get the effect of a
broadcast channel without lots and lots of plumbing.)

Now, registers are a bunch of bits:

PROC register.N ([WIDTH]CHAN BOOL in?, out!, CHAN BOOL load?, BARRIER tick)
 PROC delta.N (CHAN BOOL in?, [WIDTH]CHAN BOOL o!)
   WHILE TRUE
     BOOL v:
     SEQ
       in ? v
       PAR i = 0 FOR WIDTH
         o[i] ! v
 :
 [WIDTH]CHAN BOOL reg.load:
 PAR
   delta.N (load?, reg.load!)
   PAR i = 0 FOR WIDTH BARRIER tick
     bit (in[i]?, reg.load[i]?, out[i]!, tick)
:

Note how the "load" signal needs to be propagated to all of the
individual bits in the register... if there's a better design to be
used there, I'd welcome it.

Where I got stuck was RAM. RAM is modeled in their text as an array of
registers. My initial thought looked like this:

PROC ram ([WIDTH]CHAN BOOL in?, CHAN INT addr?, [WIDTH]CHAN BOOL out!,
BARRIER tick)
 [ADDR.SPACE]CHAN BOOL load.lines:
 PAR
   WHILE TRUE
     INT address:
     SEQ
       addr ? address
       load.lines[address] ! TRUE
   PAR i = 0 FOR ADDR.SPACE BARRIER tick
     PAR
       register.16(in?, out!, load.lines[i]?, tick)
:

(Assume ADDR.SPACE is 3 and WIDTH is 16.)

This, of course, yields parallel reads/writes on in? and out!. Do I
need to build a big ugly routing network that multiplexes and
demultiplexes these channel bundles? That is one way to solve the
problem, but it feels ugly.

Cheers,
Matt

PS. I could (obviously) model this using actual state in the
language... that is, by simply making RAM an array. I'd rather build
this up from components.

_______________________________________________
users mailing list
users at concurrency.cc
http://unhosting.org/mailman/listinfo/users
-------------- next part --------------
An HTML attachment was scrubbed...
URL: <http://www.concurrency.cc/pipermail/users/attachments/20101231/4bd85641/attachment.htm>


More information about the users mailing list