Modules with Guarded Interfaces

This resource discusses the implementation of constructive computer architecture modules with guarded interfaces, making programming tasks easier by including checks within method definitions. It explores the concept of guarded interfaces, where methods have guards that determine the validity of their returns, along with enable signals for invoking actions. The content also covers the implementation of a one-element FIFO with guards and rules with guards. Streaming a function using a FIFO with guarded interfaces and implicit guards are also discussed.

• Computer Architecture
• Guarded Interfaces
• Programming
• FIFO
• Rules

mar_bec Follow

Uploaded on Feb 24, 2025 | 0 Views

Download Presentation

Please find below an Image/Link to download the presentation.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.If you encounter any issues during the download, it is possible that the publisher has removed the file from their server.

You are allowed to download the files provided on this website for personal or commercial use, subject to the condition that they are used lawfully. All files are the property of their respective owners.

The content on the website is provided AS IS for your information and personal use only. It may not be sold, licensed, or shared on other websites without obtaining consent from the author.

Presentation Transcript

1. Constructive Computer Architecture Modules with Guarded Interfaces Arvind Computer Science & Artificial Intelligence Lab. Massachusetts Institute of Technology September 15, 2017 http://csg.csail.mit.edu/6.175 L05-1

2. Guarded interfaces Make the life of the programmers easier: Include some checks (readyness, fullness, ...) in the method definition itself, so that the user does not have to test the applicability of the method from outside Guarded Interface: Every method has a guard (rdy wire) The value returned by a method is meaningful only if its guard is true Every action method has an enable signal (en wire) and it can be invoked (en can be set to true) only if its guard is true n enq en not full rdy en deq FIFO not empty rdy n first not empty rdy interface Fifo#(numeric type size, type t); method Action enq(t x); method Action deq; method t first; endinterface http://csg.csail.mit.edu/6.175 notice, en and rdy wires are implicit L05-2 September 15, 2017

3. One-Element FIFO Implementation with guards module mkFifo (Fifo#(1, t)); Reg#(t) d <- mkRegU; Reg#(Bool) v <- mkReg(False); method Action enq(t x) v <= True; d <= x; endmethod method Action deq v <= False; endmethod method t first return d; endmethod endmodule n enq en if (!v); not full rdy en deq FIFO not empty rdy n if (v); first not empty rdy Notice, no semicolon turns the if into a guard if (v); L05-3 http://csg.csail.mit.edu/6.175 September 15, 2017

4. Rules with guards Like a method, a rule can also have a guard rule foo(p); begin x1 <= e1; x2 <= e2 end endrule guard A rule can execute only if it s guard is true, i.e., if the guard is false the rule has no effect True guards can be omitted L05-4 http://csg.csail.mit.edu/6.175 September 15, 2017

5. Streaming a function using a FIFO with guarded interfaces f inQ outQ rule stream; if(inQ.notEmpty && outQ.notFull) begin outQ.enq(f(inQ.first)); inQ.deq; end endrule rule stream (True); outQ.enq(f(inQ.first)); inQ.deq; endrule L05-5 http://csg.csail.mit.edu/6.175 September 15, 2017

6. Implicit Guards L05-6 http://csg.csail.mit.edu/6.175 September 15, 2017

7. Switch using FIFOs with guarded interfaces inQ redQ switch greenQ rule switch; if (inQ.notEmpty) if (inQ.first.color == Red) begin1 if (redQ.notFull) begin2 redQ.enq(inQ.first.value); inQ.deq; end2 end1 else begin3 if (greenQ.notFull) begin4 greenQ.enq(inQ.first.value); inQ.deq; end4 end3 endrule September 15, 2017 All the red stuff can be deleted L05-7 http://csg.csail.mit.edu/6.175

8. Switch using FIFOs with guarded interfaces inQ redQ switch greenQ rule switch(True); if (inQ.first.color == Red) begin redQ.enq (inQ.first.value); inQ.deq; end else begin greenQ.enq(inQ.first.value); inQ.deq; end endrule Implicit guard? L05-8 http://csg.csail.mit.edu/6.175 September 15, 2017

9. GCD with and without guards getResult start getResult en en start GCD en en GCD ready busy ready busy Interface without guards Interface with guards interface GCD; method Action start (Bit#(32) a, Bit#(32) b); method ActionValue#(Bit#(32)) getResult; method Bool busy; method Bool ready; endinterface L05-9 http://csg.csail.mit.edu/6.175 September 15, 2017

10. Using GCD module with guarded interfaces getResult get result invoke GCD start GCD inQ outQ rule invokeGCD; gcd.start(inQ.first); inQ.deq; endrule; rule getResult; let x <- gcd.getResult; outQ.enq(x); endrule; A rule can be executed only if guards of all of its actions are true L05-10 http://csg.csail.mit.edu/6.175 September 15, 2017

11. GCD with guarded interfaces implementation interface GCD; method Action start (Bit#(32) a,Bit#(32) b); method ActionValue(Bit#(32)) getResult; endinterface module mkGCD (GCD); Reg#(Bit#(32)) x <- mkReg(0); Reg#(Bit#(32)) y <- mkReg(0); Reg#(Bool) busy <- mkReg(False); rule gcd; if (x >= y) begin x <= x y; end //subtract else if (x != 0) begin x <= y; y <= x; end //swap endrule method Action start(Bit#(32) a, Bit#(32) b) x <= a; y <= b; busy <= True; endmethod methodActionValue (Bit#(32)) getResult busy <= False; return y; endmethod endmodule if (!busy); if (x==0); Assume b /= 0 L05-11 http://csg.csail.mit.edu/6.175 September 15, 2017

12. Guards vs Ifs guard is !v; enq can be applied only if v is false method Action enq(t x) if (!v); v <= True; d <= x; endmethod versus guard is True, i.e., the method is always applicable. method Action enq(t x); if (!v) begin v <= True; d <= x; end endmethod if v is true then x would get lost; bad L05-12 http://csg.csail.mit.edu/6.175 September 15, 2017

13. Pipelining combinational circuits September 15, 2017 http://csg.csail.mit.edu/6.175 L05-13

14. Pipelining Combinational Functions xi+1 xi xi-1 3 different datasets in the pipeline f0 f1 f2 Lot of area and long combinational delay Folded or multi-cycle version can save area and reduce the combinational delay but throughput per clock cycle gets worse Pipelining: a method to increase the circuit throughput by evaluating multiple inputs L05-14 http://csg.csail.mit.edu/6.175 September 15, 2017

15. Inelastic vs Elastic pipeline f0 f1 f2 x inQ sReg1 sReg2 outQ Inelastic: all pipeline stages move synchronously f0 f1 f2 x inQ fifo1 fifo2 outQ Elastic: A pipeline stage can process data if its input FIFO is not empty and output FIFO is not Full Most complex processor pipelines are a combination of the two styles http://csg.csail.mit.edu/6.175 L05-15 September 15, 2017

16. Elastic pipeline Use FIFOs instead of pipeline registers no need for valid bits f1 f2 f3 x inQ fifo1 fifo2 outQ When can stage1 rule fire? - inQ has an element - fifo1 has space rule stage1; fifo1.enq(f1(inQ.first)); inQ.deq(); rule stage2; fifo2.enq(f2(fifo1.first)); fifo1.deq; rule stage3; outQ.enq(f3(fifo2.first)); fifo2.deq; endrule Can tokens be left in the pipeline? endrule No Can these rules execute concurrently? endrule L05-16 http://csg.csail.mit.edu/6.175 September 15, 2017

17. Elastic pipeline f1 f2 f3 x inQ fifo1 fifo2 outQ If these rules cannot execute concurrently, it is hardly a pipelined system When can rules execute concurrently? What hardware is synthesized to execute rules concurrently? rule stage1; fifo1.enq(f1(inQ.first)); inQ.deq(); rule stage2; fifo2.enq(f2(fifo1.first)); fifo1.deq; rule stage3; outQ.enq(f3(fifo2.first)); fifo2.deq; endrule endrule endrule L05-17 http://csg.csail.mit.edu/6.175 September 15, 2017

18. Multi-rule Systems Repeatedly: Select a rule to execute Compute the state updates Make the state updates Non-deterministic choice; User annotations can be used in rule selection 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 However, for performance we execute multiple rules concurrently whenever possible stay tuned L05-18 http://csg.csail.mit.edu/6.175 September 15, 2017

19. L05-19 http://csg.csail.mit.edu/6.175 September 15, 2017

20. Inelastic pipeline f0 f1 f2 x inQ sReg1 sReg2 outQ rule sync_pipeline; inQ.deq; sReg1 <= f0(inQ.first); sReg2 <= f1(sReg1); outQ.enq(f2(sReg2)) endrule When can this rule execute? L05-20 http://csg.csail.mit.edu/6.175 September 15, 2017

21. Pipeline bubbles Some issues f0 f1 f2 x inQ sReg1 sReg2 outQ rule sync_pipeline; inQ.deq; sReg1 <= f0(inQ.first); sReg2 <= f1(sReg1); outQ.enq(f2(sReg2)) endrule - Red and Green tokens must move even if there is nothing in inQ! - Also if there is no token in sReg2 then nothing should be enqueued in the outQ Modify the rule to deal with these conditions Introduce a valid bit L05-21 http://csg.csail.mit.edu/6.175 September 15, 2017

22. Explicit encoding of data presence valid bit f0 f1 f2 x inQ outQ sReg1 sReg2 rule sync_pipeline; if(outQ.notFull || sReg2v != true) if (inQ.notEmpty) begin sReg1 <= f0(inQ.first); inQ.deq; sReg1v <= true end else sReg1v <= false; sReg2 <= f1(sReg1); sReg2v <= sReg1v; if (sReg2v == true) outQ.enq(f2(sReg2))) endrule L05-22 http://csg.csail.mit.edu/6.175 September 15, 2017