Constructive Computer Architecture: Bluespec execution model and concurrency semantics Arvind

Publish in

Documents

21 views

Please download to get full document.

View again

of 28
All materials on our website are shared by users. If you have any questions about copyright issues, please report us to resolve them. We are always happy to assist you.
Share
Description
Constructive Computer Architecture: Bluespec execution model and concurrency semantics Arvind Computer Science & Artificial Intelligence Lab. Massachusetts Institute of Technology. Contributors to the course material. Arvind, Rishiyur S. Nikhil, Joel Emer, Muralidaran Vijayaraghavan
Transcript
Constructive Computer Architecture: Bluespec execution model and concurrency semantics Arvind Computer Science & Artificial Intelligence Lab. Massachusetts Institute of Technology http://csg.csail.mit.edu/6.s195 Contributors to the course material
  • Arvind, Rishiyur S. Nikhil, Joel Emer, MuralidaranVijayaraghavan
  • Staff and students in 6.375 (Spring 2013), 6.S195 (Fall 2012), 6.S078 (Spring 2012)
  • Asif Khan, Richard Ruhler, Sang Woo Jun, Abhinav Agarwal, Myron King, Kermin Fleming, Ming Liu, Li-Shiuan Peh
  • External
  • Prof AmeyKarkare& students at IIT Kanpur
  • Prof Jihong Kim & students at Seoul Nation University
  • Prof Derek Chiou, University of Texas at Austin
  • Prof YoavEtsion & students at Technion
  • http://csg.csail.mit.edu/6.s195 Finite State Machines (Sequential Ckts) Typical description: State Transition Table or Diagram Easily translated into circuits http://www.ee.usyd.edu.au/tutorials/digital_tutorial/part3/t-diag.htm http://csg.csail.mit.edu/6.s195 Finite State Machines (Sequential Ckts)
  • A computer (if fact all digital hardware) is an FSM
  • Neither State tables nor diagrams is suitable for describing very large digital designs
  • large circuits must be described in a modular fashion -- as a collection of cooperating FSMs
  • Bluespec is a modern programming language to describe cooperating FSMs
  • This lecture is about understanding the semantics of Bluespec
  • http://csg.csail.mit.edu/6.s195 In this lecture we will use pseudo syntax, and assume that type checking has been performed (programs are type correct) http://csg.csail.mit.edu/6.s195 KBS0: A simple language for describing Sequential type checking has been performed (programs are type correct)ckts -1
  • A program consists of a collection of registers (x,y, ...) and rules
  • Registers hold the state from one clock cycle to the next
  • A rule specifies how the state is to be modified each clock cycle
  • All registers are read at the beginning of the clock cycle and updated at the end of the clock cycle
  • http://csg.csail.mit.edu/6.s195 KBS0: A simple language for describing Sequential type checking has been performed (programs are type correct)ckts - 2 A rule is simply an action <a> described below. Expression <e> is a way of describing combinational ckts <a> ::= x:= <e> register assignment | <a> ; <a> parallel actions | if (<e>) <a> conditional action | let t = <e> in <a> binding <e> ::= c constants | t value of a binding | x.rregister read | op(<e>,<e>) operators like And, Or, Not, +, ... | let t = <e> in <e> binding We will assume that the names in the bindings (t …) can be defined only once (single assignment restriction) http://csg.csail.mit.edu/6.s195 Evaluating expressions and actions type checking has been performed (programs are type correct) x y z ... x’ y’ z’ ...
  • The state of the system s is defined as the value of all its registers
  • An expression is evaluated by computing its value on the current state
  • An action defines the next value of some of the state elements based on the current value of the state
  • A rule is evaluated by evaluating the corresponding action and simultaneously updating all the affected state elements
  • rule    http://csg.csail.mit.edu/6.s195 Highly type checking has been performed (programs are type correct)non-deterministic; User annotations can be used in rule selection Bluespec Execution Model Repeatedly:
  • Select a rule to execute
  • Compute the state updates
  • Make the state updates
  • One-rule-at-a-time-semantics: Any legal behavior of a Bluespec program can be explained by observing the state updates obtained by applying only one rule at a time Need a evaluator to define how a rule transforms the state http://csg.csail.mit.edu/6.s195 KBS0 Evaluator type checking has been performed (programs are type correct)
  • We will write the evaluator as a software program using case-by-case analysis of syntax
  • evalE :: (Bindings, State, e) -> Value evalA:: (Bindings, State, a) -> (Bindings, StateUpdates) Bindings is a set of (variable name,value) pairs State is a set of (register name, value) pairs. s.xgives the value of register x in the current state Syntax is represented as [[…]] http://csg.csail.mit.edu/6.s195 KBS0: Expression evaluator type checking has been performed (programs are type correct) evalE :: (Bindings, State, exp) -> Value evalE (bs, s, [[c]]) = c evalE (bs, s, [[t]]) = bs[t] evalE (bs, s, [[x.r]]) = s[x] evalE (bs, s, [[op(e1,e2)]]) = op(evalE(bs, s, [[e1]]), evalE(bs, s, [[e2]])) evalE (bs, s, [[(let t = e in e1)]]) = {v = evalE(bs, s, [[e]]); returnevalE(bs+(t,v), s, [[e1]])} lookup t; if t does not exist in bs then the rule is illegal add a new binding to bs. The operation is illegal if t is already present in bs Bindings bs is empty initially http://csg.csail.mit.edu/6.s195 KBS0: Action evaluator type checking has been performed (programs are type correct) evalA :: (Bindings, State, a) -> StateUpdates evalA (bs, s, [[x.w(e)]]) = (x, evalE(bs, s, [[e]])) evalA (bs, s, [[a1 ; a2]]) = { u1 = evalA(bs, s, [[a1]]); u2 = evalA(bs’, s, [[a2]]) return u1 + u2 } evalA (bs, s, [[if (e) a]]) = if evalE(bs, s, [[e]]) then evalA(bs, s, [[a]]) else {} evalA (bs, s, [[(let t = e in a)]]) = { v = evalE(bs, s, [[e]]) return evalA(bs+(t,v), s, [[a]]) } merges two sets of updates; the rule is illegal if there are multiple updates for the same register extends the bindings by including one for t initially bs is empty and s contains old register values http://csg.csail.mit.edu/6.s195 Rule evaluator type checking has been performed (programs are type correct)
  • To apply a rule, we compute the state updates using EvalA and then simultaneously update all the state variables that need to be updated
  • http://csg.csail.mit.edu/6.s195 Evaluation in the presence of modules type checking has been performed (programs are type correct)
  • It is easy to extend the evaluator we have shown to include non-primitive method calls
  • An action method, just like a register write, can be called at most once from a rule
  • The only additional complication is that a value method with parameters can also be called at most once from an action
  • It these conditions are violated then it is an illegal rule/action/expression
  • http://csg.csail.mit.edu/6.s195 Evaluation in the presence of guards type checking has been performed (programs are type correct)
  • In the presence of guards the expression evaluator has to return a special value – NR (for “not ready”). This ultimately affects whether an action can affect the state or not.
  • Instead of complicating the evaluator we will give a procedure to lift when’s to the top of a rule. At the top level a guard behaves just like an “if”
  • http://csg.csail.mit.edu/6.s195 Guard Elimination type checking has been performed (programs are type correct) http://csg.csail.mit.edu/6.s195 Guards vs If’s type checking has been performed (programs are type correct)
  • A guard on one action of a parallel group of actions affects every action within the group (a1 when p1); a2 ==> (a1; a2) when p1
  • A condition of a Conditional action only affects the actions within the scope of the conditional action (if(p1) a1); a2 p1 has no effect on a2 ...
  • Mixing ifs and whens (if(p) (a1 when q)) ; a2  ((if(p) a1); a2) when ((p && q) | !p)  ((if(p) a1); a2) when(q | !p)
  • http://csg.csail.mit.edu/6.s195 Method calls have implicit guards type checking has been performed (programs are type correct)
  • Every method call, except the primitive method calls, i.e., x,r, x.w, has an implicit guard associated with it
  • m.enq(x), the guard indicated whether one can enqueue into fifo m or not
  • Make the guards explicit in every method call by naming the guard and separating it from the unguarded body of the method call, i.e., syntactically replace m.g(e) by m.gB(e) whenm.gG
  • Notice m.gGhas no parameter because the guard value should not depend upon the input
  • http://csg.csail.mit.edu/6.s195 Make implicit guards explicit type checking has been performed (programs are type correct) <a> ::= x.w(<e>) | <a> ; <a> | if (<e>) <a> | m.g(<e>) | let t = <e> in <a> | <a> when <e> m.gB(<e>) whenm.gG <a> ::= <a> ; <a> | if (<e>) <a> | m.g(<e>) | let t = <e> in <a> | <a> when <e> The new kernel language methods without guards http://csg.csail.mit.edu/6.s195 Lifting implicit guards type checking has been performed (programs are type correct) rulefoo if (True); (if(p) fifo.enq(8)); x.w(7) rule foo if (fifo.enqG | !p); if (p) fifo.enqB(8); x.w(7) All implicit guards are made explicit, and lifted and conjoined to the rule guard http://csg.csail.mit.edu/6.s195 Guard Lifting Axioms type checking has been performed (programs are type correct)without Let-blocks
  • All the guards can be “lifted” to the top of a rule
  • (a1 whenp) ; a2 
  • a1 ; (a2 whenp)
  • if(p whenq) a 
  • if(p) (a whenq)
  • (a whenp1) whenp2 
  • m.gB(e whenp) similarly for expressions ...
  • Ruler (a whenp)
  • (a1 ; a2) when p
  • (a1 ; a2) whenp
  • (if(p) a) when q
  • (if(p) a) when (q | !p)
  • a when (p1 & p2)
  • m.gB(e) when p
  • Rule r (if(p) a)
  • We will call this guard lifting transformation WIF, for when-to-if A complete guard lifting procedure also requires rules for let-blocks http://csg.csail.mit.edu/6.s195 Optional: A complete procedure for guard lifting type checking has been performed (programs are type correct) http://csg.csail.mit.edu/6.s195 Let-blocks: Variable names and guards type checking has been performed (programs are type correct)
  • let t = e in f(t)
  • Since e can have a guard, a variable name, t, can also have an implicit guard
  • Essentially every expression has two parts: unguarded and guarded and consequently t has two parts tB and tG
  • Each use of the variable name has to be replaced by (tBwhentG)
  • http://csg.csail.mit.edu/6.s195 Lift procedure type checking has been performed (programs are type correct) LWE :: (Bindings, Exp) -> (Bindings, ExpB, ExpG) LW :: (Bindings, Exp) -> (Bindings, ActionB, ExpG) Returned exp, actions and bindings are all free of when’s
  • Bindings is a collection of (t,e) pairs where e is restricted to be c | x.r | t | op(t,t) | m.h(t) | {body: t, guard: t}
  • The bindings of the type (t, {body:tx, guard:ty}) are not needed after When Lifting because all such t’s would have been eliminated from the returned expressions
  • http://csg.csail.mit.edu/6.s195 Bindings type checking has been performed (programs are type correct)
  • The bindings that LW and LWE return are simply a collection of (t,e) pairs where e is restricted to be c | x.r | x.r0| x.r1 | t | op(t,t) | m.h(t) | {body: t, guard: t}
  • The bindings of the type (t, {body:tx, guard:ty}) are not needed after When Lifting because all such t’s would have been eliminated from the returned expressions
  • http://csg.csail.mit.edu/6.s195 LWE: procedure for lifting when’s in expressions type checking has been performed (programs are type correct) LWE :: (Bindings, Exp) -> (Bindings, ExpB, ExpG) LWE (bs, [[c]]) = (bs, c, T) ; LWE (bs, [[x.r]]) = (bs, x.r, T) LWE (bs, [[x.r0]]) = (bs, x.r0, T); LWE (bs, [[x.r1]]) = (bs, x.r1, T) LWE (bs, [[t]]) = (bs, bs[t].body, bs[t].guard) LWE (bs, [[Op(e1,e2)]]) = {bs1, t1B, t1G= LWE(bs, [[e1]]); bs2, t2B, t2G= LWE(bs1, [[e2]]); return bs2, Op(t1B, t2B), (t1G&t2G)} LWE(bs, [[m.h(e)]]) = {bs1, tB, tG= LWE(bs, [[e]]); return bs1, m.hB(tB), (tG&m.hG)} LWE (bs, [[e1 whene2]]) = {bs1, t1B, t1G = LWE(bs, [[e1]]); bs2, t2B, t2G= LWE(bs1, [[e2]]); bs3 = bs2+(tx, t2B&t2G) return bs3, t1B, (tx&t1G)} LWE(bs, [[lett=e1 ine2]]) = {bs1, tB, tG= LWE(bs, [[e1]]); bs2 = bs1+(tx,tB)+(ty,tG) +(t,{body:tx,guard:ty}) return LWE(bs2, [[e2]]} tx, ty are new variable http://csg.csail.mit.edu/6.s195 LW: procedure for lifting when’s in actions type checking has been performed (programs are type correct) LW :: (Bindings, Exp) -> (Bindings, ActionB, ExpG) LW (bs, [[x.w(e)]]) = {bs1, tB , tG = LWE(bs, [[e]]); return bs1, x.w(tB), tG} LW (bs, [[m.g(e)]]) = {bs1, tB, tG= LWE(bs, [[e]]); return bs1, m.gB(tB), (tG&m.gG)} LW (bs, [[a1;a2]]) = {bs1, a1B, g1 = LW(bs, [[a1]]); bs2, a2B, g2 = LW(bs1, [[a2]]); return bs2, (a1B; a2B), (g1&g2)} LW (bs, [[if (e) a]]) = {bs1, tB, tG= LWE(bs, [[e]]); bs2, aB, g= LW(bs1, [[a]]); bs3 = bs2+(tx,tB)+(ty,tG) return bs3, aB, (g | !tx) & ty)} LW (bs, [[a whene]]) = {bs1, tB, tG= LWE(bs, [[e]]); bs2, aB , g = LW(bs1, [[a]]); return bs2+(tx, tB&tG), aB, (tx&g)} LW(bs, [[let t=e in a]]) = {bs1, tB, tG= LWE(bs, [[e]]); bs2 = bs1+(tx,tB)+(ty,tG) +(t,{body:tx,guard:ty}) return LW(bs2, [[a]]} tx, ty are new variable http://csg.csail.mit.edu/6.s195 WIF: when-to-if transformation type checking has been performed (programs are type correct)
  • Given rulera a, WIF(ra) returns rulera(letbsin (if(g) aB)) assuming LW({}, a) returns (bs, aB, g)
  • Notice,
  • WIF(ra) has no when’s
  • WIF(a1;a2) ≠ (WIF(a1);WIF(a2))
  • http://csg.csail.mit.edu/6.s195
    Related Search

    Previous Document

    Westview Wolverines

    Next Document

    The Aadhaar Project

    We Need Your Support
    Thank you for visiting our website and your interest in our free products and services. We are nonprofit website to share and download documents. To the running of this website, we need your help to support us.

    Thanks to everyone for your continued support.

    No, Thanks