Elastic Pipelines and Basics of Multi rule Systems Arvind Computer Science Artificial Intelligence Lab Massachusetts Institute of Technology February 17 2010 http csg csail mit edu 6 375 L05 1 Inelastic Pipeline f1 f2 f3 x inQ sReg1 sReg2 outQ rule sync pipeline True if inQ notEmpty begin sReg1 Valid f1 inQ first inQ deq end else sReg1 Invalid case sReg1 matches tagged Valid sx1 sReg2 Valid f2 sx1 tagged Invalid sReg2 Invalid case sReg2 matches tagged Valid sx2 outQ enq f3 sx2 endrule February 17 2010 http csg csail mit edu 6 375 L05 2 Elastic pipeline Use FIFOs instead of pipeline registers f1 f2 f3 x inQ fifo1 fifo2 rule stage1 True fifo1 enq f1 inQ first inQ deq endrule rule stage2 True fifo2 enq f2 fifo1 first fifo1 deq endrule rule stage3 True outQ enq f3 fifo2 first fifo2 deq endrule February 17 2010 http csg csail mit edu 6 375 outQ Firing conditions Can tokens be left inside the pipeline No Maybe types Easier to write Can all three rules fire concurrently L05 3 Inelastic vs Elastic Pipelines In an Inelastic pipeline typically only one rule the designer controls precisely which activities go on in parallel downside The rule can get too complicated easy to make a mistake difficult to make changes In an Elastic pipeline February 17 2010 several smaller rules each easy to write easier to make changes downside sometimes rules do not fire concurrently when they should http csg csail mit edu 6 375 L05 4 What behavior do we want f1 f2 f3 x inQ fifo1 fifo2 outQ If inQ fifo1 and fifo2 are not empty and fifo1 fifo2 and outQ are not full then we want all the three rules to fire If inQ is empty fifo1 and fifo2 are not empty and fifo2 and outQ are not full then we want rules stage2 and stage3 to fire Maximize concurrency Fire maximum number of rules February 17 2010 http csg csail mit edu 6 375 L05 5 The tension If multiple rules never fire in the same cycle then the machine can hardly be called a pipelined machine If all rules fire in parallel every cycle when they are enabled then in general wrong results can be produced February 17 2010 http csg csail mit edu 6 375 L05 6 Concurrency analysis and rule scheduling February 17 2010 http csg csail mit edu 6 375 L05 7 Guarded Atomic Actions GAA Execution model Repeatedly Select a rule to execute Compute the state updates Make the state updates Highly nondeterministic User annotations can help in rule selection Implementation concern Schedule multiple rules concurrently without violating one rule at a time semantics February 17 2010 http csg csail mit edu 6 375 L05 8 some insight into Concurrent rule firing Rules Ri Rj Rk rule steps Rj HW Rk Ri clocks There are more intermediate states in the rule semantics a state after each rule step In the HW states change only at clock edges February 17 2010 http csg csail mit edu 6 375 L05 9 Parallel execution reorders reads and writes Rules reads reads rule writes reads writes reads writes reads writes reads writes writes reads writes steps clocks HW In the rule semantics each rule sees reads the effects writes of previous rules In the HW rules only see the effects from previous clocks and only affect subsequent clocks February 17 2010 http csg csail mit edu 6 375 L05 10 Correctness Rules Ri Rj Rk rule steps Rj HW Rk Ri clocks Rules are allowed to fire in parallel only if the net state change is equivalent to sequential rule execution Consequence the HW can never reach a state unexpected in the rule semantics February 17 2010 http csg csail mit edu 6 375 L05 11 A compiler can determine if two rules can be executed in parallel without violating the one rule ata time semantics James Hoe Ph D 2000 February 17 2010 http csg csail mit edu 6 375 L05 12 Rule As a State Transformer A rule may be decomposed into two parts s and s such that snext if s then s else s s is the condition predicate of the rule a k a the CAN FIRE signal of the rule is a conjunction of explicit and implicit conditions s is the state transformation function i e computes the next state values from the current state values February 17 2010 http csg csail mit edu 6 375 L05 13 Executing Multiple Rules Per Cycle Conflict free rules rule ra z 10 x x 1 endrule rule rb z 20 y y 2 endrule Parallel execution behaves like ra rb or equivalently rb ra Rulea and Ruleb are conflict free if s a s b s 1 a b s b a s 2 a b s b a s Parallel Execution can also be understood in terms of a composite rule February 17 2010 rule ra rb if z 10 then x x 1 if z 20 then y y 2 endrule http csg csail mit edu 6 375 L05 14 Mutually Exclusive Rules Rulea and Ruleb are mutually exclusive if they can never be enabled simultaneously s a s b s Mutually exclusive rules are Conflict free by definition February 17 2010 http csg csail mit edu 6 375 L05 15 Executing Multiple Rules Per Cycle Sequentially Composable rules rule ra z 10 x y 1 endrule rule rb z 20 y y 2 endrule Parallel execution behaves like ra rb R rb is the range of rule rb Prjst is the projection selecting st from the total state Rulea and Ruleb are sequentially composable if s a s b s 1 b a s 2 PrjR rb b s PrjR rb b a s Parallel Execution can also be understood in terms of a composite rule February 17 2010 rule ra rb if z 10 then x y 1 if z 20 then y y 2 endrule http csg csail mit edu 6 375 L05 16 Compiler determines if two rules can be executed in parallel Rulea and Ruleb are conflict free if s a s b s 1 a b s b a s 2 a b s b a s D Ra R Rb D Rb R Ra R Ra R Rb Rulea and Ruleb are sequentially composable if s a s b s 1 b a s D Rb R Ra 2 PrjR Rb b s PrjR Rb b a s These conditions are sufficient but not necessary These properties can be determined by examining the domains and ranges of the rules in a pairwise manner Parallel execution of CF and SC rules does not increase the critical path delay February 17 2010 http csg csail mit edu 6 375 L05 17 Conflicting rules rule ra True x y 1 endrule Assume x and y are initially zero rule rb True y x 2 endrule Concurrent execution of these can produce x 1 and y 2 but these values cannot be produced by any sequential execution February 17 2010 http csg csail mit edu 6 375 L05 18 The …
View Full Document
Unlocking...