Combinational Circuits and Simple Synchronous Pipelines Arvind Computer Science Artificial Intelligence Lab Massachusetts Institute of Technology February 13 2009 http csg csail mit edu 6 375 L05 1 Bluespec Two Level Compilation Bluespec Objects Types Higher order functions wLennart Augustsson w Sandburst 2000 2002 Type checking Massive partial evaluation and static elaboration Level 1 compilation Rules and Actions Term Rewriting System Rule conflict analysis Rule scheduling Level 2 synthesis Object code Verilog C February 13 2009 Now we call this Guarded Atomic Actions wJames Hoe Arvind w MIT 1997 2000 http csg csail mit edu 6 375 L05 2 1 Static Elaboration At compile time Inline function calls and unroll loops Instantiate modules with specific parameters Resolve polymorphism overloading perform most data structure operations Software Toolflow source elaborate w params Hardware source Toolflow compile exe run w params run1 run run1 February 13 2009 run w params design1 design2 design3 run1 1 run1 run1 run2 1 run1 run1 run3 1 run1 run1 L05 3 http csg csail mit edu 6 375 Combinational IFFT in0 out0 in1 Bfly4 Bfly4 x16 in4 Bfly4 Bfly4 Bfly4 t0 t1 t2 t3 February 13 2009 j out2 out3 out4 Bfly4 in63 Bfly4 out1 Permute Bfly4 in3 Bfly4 Permute Permute in2 out63 All numbers are complex and represented as two sixteen bit quantities Fixed point arithmetic is used to reduce area power http csg csail mit edu 6 375 L05 4 2 4 way Butterfly Node t0 t1 t2 t3 k0 k1 k2 k3 i function Vector 4 Complex bfly4 Vector 4 Complex t Vector 4 Complex k BSV has a very strong notion of types Every expression has a type Either it is declared by the user or automatically deduced by the compiler The compiler verifies that the type declarations are compatible February 13 2009 L05 5 http csg csail mit edu 6 375 A1 BSV code 4 way Butterfly function Vector 4 Complex bfly4 Vector 4 Complex t Vector 4 Complex k Vector 4 Complex m y z m 0 k 0 t 0 m 1 k 1 t 1 m 2 k 2 t 2 m 3 k 3 t 3 y 0 m 0 m 2 y 1 m 0 m 2 y 2 m 1 m 3 y 3 i m 1 m 3 z 0 y 0 y 2 z 1 y 1 y 3 z 2 y 0 y 2 z 3 y 1 y 3 return z endfunction Note Vector does not mean storage February 13 2009 http csg csail mit edu 6 375 m i y z Polymorphic code works on any type of numbers for which and have been defined L05 6 3 Slide 6 A1 Add a slide on arithmetic compile time costants Arvind 4 28 2007 Combinational IFFT in0 in1 x16 Bfly4 Bfly4 Bfly4 Bfly4 out1 Permute in4 Bfly4 Bfly4 Permute in3 Bfly4 Permute in2 out0 Bfly4 Bfly4 in63 out2 out3 out4 out63 stage f function repeat it three times February 13 2009 http csg csail mit edu 6 375 L05 7 BSV Code Combinational IFFT function Vector 64 Complex ifft Vector 64 Complex in data Declare vectors Vector 4 Vector 64 Complex stage data stage data 0 in data for Integer stage 0 stage 3 stage stage 1 stage data stage 1 stage f stage stage data stage return stage data 3 The for loop is unfolded and stage f is inlined during static elaboration Note no notion of loops or procedures during execution February 13 2009 http csg csail mit edu 6 375 L05 8 4 BSV Code Combinational IFFT Unfolded function Vector 64 Complex ifft Vector 64 Complex in data Declare vectors Vector 4 Vector 64 Complex stage data stage data 0 in data for Integer stage 0 stage 3 stage stage 1 stage data stage 1 stage f stage stage data stage return stage data 3 February 13 2009 L05 9 http csg csail mit edu 6 375 Bluespec Code for stage f function Vector 64 Complex stage f Bit 2 stage Vector 64 Complex stage in begin for Integer i 0 i 16 i i 1 begin Integer idx i 4 let twid getTwiddle stage fromInteger i let y bfly4 twid stage in idx idx 3 stage temp idx y 0 stage temp idx 1 y 1 stage temp idx 2 y 2 stage temp idx 3 y 3 end Permutation for Integer i 0 i 64 i i 1 stage out i stage temp permute i end return stage out February 13 2009 http csg csail mit edu 6 375 L05 10 5 Suppose we want to reuse some part of the circuit in0 in1 x16 Bfly4 Bfly4 Bfly4 Bfly4 out1 Permute in4 Bfly4 Bfly4 Permute in3 Bfly4 Permute in2 out0 Bfly4 Bfly4 in63 out2 out3 out4 out63 Reuse the same circuit three times to reduce area February 13 2009 http csg csail mit edu 6 375 L05 11 Architectural Exploration Area Performance tradeoff in 802 11a Transmitter February 13 2009 http csg csail mit edu 6 375 L05 12 6 802 11a Transmitter Overview headers 24 Uncoded bits Controller data Scrambler Interleaver Encoder Cyclic Extend IFFT Transforms 64 frequency domain complex numbers into 64 time domain complex numbers February 13 2009 Depending upon the transmission rate consumes 1 2 or 4 tokens to produce one OFDM symbol Mapper IFFT Must produce one OFDM symbol every 4 sec One OFDM symbol 64 Complex Numbers L05 13 http csg csail mit edu 6 375 Preliminary results MEMOCODE 2006 Dave Gerding Pellauer Arvind Design Block Controller Scrambler Conv Encoder Interleaver Mapper IFFT Cyc Extender Lines of Code BSV 49 40 113 76 112 95 23 Relative Area 0 0 0 1 11 85 3 Complex arithmetic libraries constitute another 200 lines of code February 13 2009 http csg csail mit edu 6 375 L05 14 7 Combinational IFFT in0 in1 x16 Bfly4 Bfly4 Bfly4 Bfly4 Bfly4 in63 out1 Permute in4 Bfly4 Bfly4 Permute in3 Bfly4 Permute in2 out0 Bfly4 out2 out3 out4 out63 Reuse the same circuit three times to reduce area February 13 2009 L05 15 http csg csail mit edu 6 375 Design Alternatives Reuse a block over multiple cycles f f g f g we expect Throughput to Area to February 13 2009 http csg csail mit edu 6 375 L05 16 8 Circular pipeline Reusing the Pipeline Stage in0 out0 in2 in3 Bfly4 out1 Permute Bfly4 in1 out2 out3 in4 out4 Stage Counter in63 out63 L05 17 http csg csail mit edu 6 375 February 13 2009 Superfolded circular pipeline Just one Bfly 4 node in0 out0 in1 in3 Stage 0 to 2 in4 Index 0 to 15 4 16 way DeMuxes in63 4 16 way Muxes out1 64 2 way Muxes Permute Bfly4 in2 out2 out3 out4 out63 Index 15 February 13 2009 http csg csail mit edu 6 375 L05 18 9 Pipelining a block f1 C f2 Combinational f3 inQ P outQ f1 f2 Pipeline f3 inQ outQ f FP inQ outQ Clock Area Throughput L05 19 http csg csail mit edu 6 375 February 13 2009 Folded Pipeline Synchronous pipeline f2 f1 f3 x inQ sReg1 sReg2 rule sync pipeline True inQ …
View Full Document
Unlocking...