1Combinational Circuits in BluespecBluespecArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 9, 2011 L03-1http://csg.csail.mit.edu/6.375Bluespec: Two-Level CompilationBluespec(Objects TypesLennart AugustssonRules and Actions(Term Rewriting System)(Objects, Types,Higher-order functions)Level 1 compilation• Type checking• Massive partial evaluationand static elaboration@Sandburst 2000-2002Now we call this Guarded Atomic ActionsObject code(Verilog/C)• Rule conflict analysis• Rule schedulingJames Hoe & Arvind@MIT 1997-2000Level 2 synthesisActionsFebruary 9, 2011L03-2http://csg.csail.mit.edu/6.3752Static ElaborationAt compile time Inline function calls and unroll loopscompileelaborate w/params Instantiate modules with specific parameters Resolve polymorphism/overloading, perform most data structure operationssourceSoftwareToolflow:sourceHardwareToolflow:.exe design2 design3design1run1run1run2.1…run1run1run3.1…run1run1run1.1…run w/paramsrun w/paramsrun1run1…runFebruary 9, 2011L03-3http://csg.csail.mit.edu/6.375Combinational IFFTin0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermuteAll numbers are complex and represented as two sixteen bit quantities. Fixed-point arithmetic is used to reduce area, power, ...****+--++--+*jt2t0t3t1February 9, 2011L03-4http://csg.csail.mit.edu/6.37534-way Butterfly Node**+-+-t0t1 k0function Vector#(4,Complex) bfly4(Vector#(4,Complex) t, Vector#(4,Complex) k);BSV has a very strong notion of types**-+-+*it1 t2 t3k1 k2 k3BSV 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 9, 2011L03-5http://csg.csail.mit.edu/6.375BSV code: 4-way Butterflyfunction 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]);****+--++--+*im yz 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);endfunctionPolymorphic code: works on any type of numbers for which *, + and -have been definedNote: Vector does not mean storageFebruary 9, 2011L03-6http://csg.csail.mit.edu/6.3754Complex ArithmeticAddition zR= xR+ yRRRyR zI= xI+ yIMultiplication zR= xR* yR-xI*yI zI= xR* yI+ xI*yRThe actual arithmetic for FFT is different because we use a non-standard fixed point representationFebruary 9, 2011L03-7http://csg.csail.mit.edu/6.375BSV code for Additiontypedef struct{#( )Int#(t) r;Int#(t) i;} Complex#(numeric type t) deriving (Eq,Bits);function Complex#(t) \+(Complex#(t) x, Complex#(t) y);Int#(t) real = x.r + y.r; Int#(t) imag = x.i + y.i;#( ) g y ;return(Complex{r:real, i:imag});endfunctionWhat is the type of this + ?February 9, 2011L03-8http://csg.csail.mit.edu/6.3755Combinational IFFTin0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermutestage_f functionrepeat stage_fthree timesfunction Vector#(64, Complex) stage_f (Bit#(2) stage, Vector#(64, Complex) stage_in);function Vector#(64, Complex) ifft(Vector#(64, Complex) in_data);February 9, 2011L03-9http://csg.csail.mit.edu/6.375BSV Code: Combinational IFFTfunction Vector#(64, Complex) ifft (Vector#(64, Complex) in_data);//Declare vectors//Declare vectorsVector#(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 elaborationNote: no notion of loops or procedures during executionFebruary 9, 2011L03-10http://csg.csail.mit.edu/6.3756BSV Code: Combinational IFFT- Unfoldedfunction Vector#(64, Complex) ifft (Vector#(64, Complex) in_data);//Declare vectors//Declare vectorsVector#(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 9, 2011L03-11http://csg.csail.mit.edu/6.375Bluespec Code for stage_ffunction Vector#(64, Complex) stage_f(Bit#(2) stage, Vector#(64, Complex) stage_in);beginfor (Integer i = 0; i < 16; i = i + 1)beginInteger 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];endend//Permutationfor (Integer i = 0; i < 64; i = i + 1)stage_out[i] = stage_temp[permute[i]];endreturn(stage_out);February 9, 2011L03-12http://csg.csail.mit.edu/6.3757Higher-order functions:Stage functions f1, f2 and f3function f0(x); return (stage_f(0,x)); endfunctionfunction f1(x); return (stage_f(1,x)); endfunctionfunction f2(x); return(stage f(2,x));return(stage_f(2,x)); endfunctionWhat is the type of f0(x) ?February 9, 2011L03-13http://csg.csail.mit.edu/6.375Suppose we want to reuse some part of the circuit ...in0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermuteReuse the same circuit three times to reduce areaBut why?February 9, 2011L03-14http://csg.csail.mit.edu/6.3758Architectural Exploration:AP f t d ff i Area-Performance tradeoff in 802.11a TransmitterFebruary 9, 2011 L03-15http://csg.csail.mit.edu/6.375802.11a Transmitter OverviewheadersMust produce Controller Scrambler EncoderInterleaver Mapperdata24 Uncoded bitsMust produce one OFDM symbol every 4 secIFFTCyclicExtendIFFT Transforms 64 (frequency domain) complex numbers into 64 (time domain) complex numbersFebruary 9, 2011L03-16http://csg.csail.mit.edu/6.3759Preliminary results[MEMOCODE 2006] Dave, Gerding, Pellauer, ArvindDesign Lines of Block Code (BSV)RelativeAreaBlock Code (BSV)Controller 49 Scrambler 40 Conv. Encoder 113 Interleaver 76 Mapper 112 AreaMapper 112 IFFT 95 Cyc. Extender 23 Complex arithmetic libraries constitute another 200 lines of codeFebruary 9, 2011L03-17http://csg.csail.mit.edu/6.375Combinational IFFTin0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermuteReuse the same circuit three times to reduce
View Full Document
Unlocking...