Slide 1GAA Execution modelRule: As a State TransformerCompiling a RuleCombining State Updates: strawmanCombining State UpdatesOne-rule-at-a-time SchedulerExecuting Multiple Rules Per Cycle: Conflict-free rulesExecuting Multiple Rules Per Cycle: Sequentially Composable rulesSequentially Composable rules ...Compiler determines if two rules can be executed in parallelMutually Exclusive RulesMultiple-Rules-per-Cycle SchedulerMuxing structureScheduling and control logicsome insight PictoriallyParallel execution reorders reads and writesCorrectnessSynthesis SummaryTwo-stage PipelineTwo-stage Pipeline AnalysisScheduling expectations: execute < fetch scheduleOne Element FIFO AnalysisThe good news ...Register InterfacesEphemeral History Register (EHR)Transformation for PerformanceOne Element FIFO using EHRsAfter RenamingExperiments in scheduling Dan Rosenband, ICCAD 2005February 28, 2007 http://csg.csail.mit.edu/6.375/ L10-1Bluespec-7: Scheduling & Rule CompositionArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 28, 2007 L10-2http://csg.csail.mit.edu/6.375/GAA Execution modelRepeatedly:Select a rule to execute Compute the state updates Make the state updatesHighly non-deterministicImplementation concern: Schedule multiple rules concurrently without violating one-rule-at-a-time semanticsUser annotations can help in rule selectionFebruary 28, 2007 L10-3http://csg.csail.mit.edu/6.375/Rule: As a State TransformerA rule may be decomposed into two parts (s) and (s) such thatsnext = if (s) then (s) else s(s) is the condition (predicate) of the rule,a.k.a. the “CAN_FIRE” signal of the rule. (conjunction of explicit and implicit conditions)(s) is the “state transformation” function, i.e., computes the next-state value in terms of the current state values.February 28, 2007 L10-4http://csg.csail.mit.edu/6.375/Compiling a Rulefxcurrentstatenextstate valuesenablefxrule r (f.first() > 0) ; x <= x + 1 ; f.deq ();endrule = enabling condition = action signals & valuesrdy signalsread methodsenable signalsaction parametersFebruary 28, 2007 L10-5http://csg.csail.mit.edu/6.375/Combining State Updates: strawmannext statevaluelatch enableR OR1n1,Rn,R OR’s from the rulesthat update R’s from the rulesthat update RFebruary 28, 2007 L10-6http://csg.csail.mit.edu/6.375/Combining State Updatesnext statevaluelatch enableRScheduler:PriorityEncoder OR1n1n1,Rn,R OR’s from the rulesthat update RScheduler ensures that at most one i is true ’s from all the rulesFebruary 28, 2007 L10-7http://csg.csail.mit.edu/6.375/One-rule-at-a-time SchedulerScheduler:PriorityEncoder12n12n1i i21 2 .... n 1 2 .... n 3. One rewrite at a time i.e. at most one i is true Very conservative way of guaranteeing correctnessFebruary 28, 2007 L10-8http://csg.csail.mit.edu/6.375/Executing Multiple Rules Per Cycle: Conflict-free rulesParallel execution behaves like ra < rb = rb < rarule ra (z > 10); x <= x + 1; endrulerule rb (z > 20); y <= y + 2; endrulerule ra_rb((z>10)&&(z>20)); x <= x+1; y <= y+2; endruleParallel Execution can also be understood in terms of a composite ruleRulea and Ruleb are conflict-free ifs . a(s) b(s) 1. a(b(s)) b(a(s)) 2. a(b(s)) == b(a(s))February 28, 2007 L10-9http://csg.csail.mit.edu/6.375/Executing Multiple Rules Per Cycle: Sequentially Composable rulesrule ra (z > 10); x <= y + 1; endrulerule rb (z > 20); y <= y + 2; endruleParallel execution behaves like ra < rbrule ra_rb((z>10)&&(z>20)); x <= y+1; y <= y+2; endruleParallel Execution can also be understood in terms of a composite ruleRulea and Ruleb are sequentially composable ifs . a(s) b(s) b(a(s))February 28, 2007 L10-10http://csg.csail.mit.edu/6.375/Sequentially Composable rules ...Parallel execution can behave either like ra < rb or rb < ra but the two behaviors are not the sameComposite rulesrule ra (z > 10); x <= 1; endrulerule rb (z > 20); x <= 2; endrulerule ra_rb(z>10 && z>20); x <= 2; endruleBehavior ra < rbrule rb_ra(z>10 && z>20); x <= 1; endruleBehavior rb < raFebruary 28, 2007 L10-11http://csg.csail.mit.edu/6.375/Compiler determines if two rules can be executed in parallelRulea and Ruleb are sequentially composable ifs . a(s) b(s) b(a(s))Rulea and Ruleb are conflict-free ifs . a(s) b(s) 1. a(b(s)) b(a(s))2. a(b(s)) == b(a(s)) These properties can be determined by examining the domains and ranges of the rules in a pairwise manner.These conditions are sufficient but not necessary.Parallel execution of CF and SC rules does not increase the critical path delay D(Ra) R(Rb) = D(Rb) R(Ra) = R(Ra) R(Rb) = D(b) R(Ra) = February 28, 2007 L10-12http://csg.csail.mit.edu/6.375/Mutually Exclusive RulesRulea and Ruleb are mutually exclusive if they can never be enabled simultaneouslys . a(s) ~ b(s) Mutually-exclusive rules are Conflict-free even if they write the same stateMutual-exclusive analysis brings down the cost of conflict-free analysisFebruary 28, 2007 L10-13http://csg.csail.mit.edu/6.375/Multiple-Rules-per-Cycle Scheduler1.i i 2.1 2 .... n 1 2 .... n3.Multiple operations such thati j Ri and Rj are conflict-free or sequentially composableScheduler12n12nSchedulerSchedulerDivide the rules into smallest conflicting groups; provide a scheduler for each groupFebruary 28, 2007 L10-14http://csg.csail.mit.edu/6.375/Muxing structureMuxing logic requires determining for each register (action method) the rules that update it and under what conditions1 ~2Conflict Free (Mutually exclusive)andand or1122Sequentially composableandand or11 and ~222CF rules either do not update the same element or are MEFebruary 28, 2007 L10-15http://csg.csail.mit.edu/6.375/Scheduling and control logicModules(Current state)Rules11Scheduler1n1nMuxing1nnnModules(Next state)condaction“CAN_FIRE” “WILL_FIRE”February 28, 2007 L10-16http://csg.csail.mit.edu/6.375/some insightPictoriallyRulesHWRi Rj RkclocksrulestepsRiRjRk•There are more intermediate states in the rule semantics (a state after each
View Full Document
Unlocking...