1Combinational Circuits in BluespecBluespecArvind Computer Science & Artificial Intelligence LabFebruary 10, 2010 http://csg.csail.mit.edu/6.375 L03-1Massachusetts Institute of TechnologyBluespec: Two-Level CompilationBluespec(Objects TypeswLennart AugustssonRules and Actions(Term Rewriting System)(Objects, Types,Higher-order functions)Level 1 compilation• Type checking• Massive partial evaluationand static elaborationw@Sandburst 2000-2002Now we call this Guarded Atomic ActionsFebruary 10, 2010L03-2http://csg.csail.mit.edu/6.375Object code(Verilog/C)• Rule conflict analysis• Rule schedulingwJames Hoe & Arvindw@MIT 1997-2000Level 2 synthesisActions2Static 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:February 10, 2010L03-3http://csg.csail.mit.edu/6.375.exe design2 design3design1run1run1run2.1…run1run1run3.1…run1run1run1.1…run w/paramsrun w/paramsrun1run1…runCombinational IFFTin0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermuteFebruary 10, 2010L03-4http://csg.csail.mit.edu/6.375All numbers are complex and represented as two sixteen bit quantities. Fixed-point arithmetic is used to reduce area, power, ...****+--++--+*jt2t0t3t134-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 k3February 10, 2010L03-5http://csg.csail.mit.edu/6.375BSV 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 BSV 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 February 10, 2010L03-6http://csg.csail.mit.edu/6.375z[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);endfunction4Complex ArithmeticAddition zR= xR + yRRR yR zI= xI + yIMultiplication zR= xR * yR -xI *yI zR= xR * yI + xI *yRFebruary 10, 2010L03-7http://csg.csail.mit.edu/6.375The actual arithmetic for FFT is different because we use a non-standard fixed point representationsBSV 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;February 10, 2010L03-8http://csg.csail.mit.edu/6.375#( ) g y ;return(Complex{r:real, i:imag});endfunction5Combinational IFFTin0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermutestage_f functionFebruary 10, 2010L03-9http://csg.csail.mit.edu/6.375repeat 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);BSV 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]);February 10, 2010L03-10http://csg.csail.mit.edu/6.375The for-loop is unfolded and stage_fis inlined during static elaborationNote: no notion of loops or procedures during execution6BSV 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]);stage_data[1] = stage_f(0,stage_data[0]);stage_data[2] = stage_f(1,stage_data[1]);stage_data[3] = stage_f(2,stage_data[2]);February 10, 2010L03-11http://csg.csail.mit.edu/6.375Stage_f can be inlined now; it could have been inlined before loop unfolding also.Does the order matter?Bluespec 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];endFebruary 10, 2010L03-12http://csg.csail.mit.edu/6.375end//Permutationfor (Integer i = 0; i < 64; i = i + 1)stage_out[i] = stage_temp[permute[i]];endreturn(stage_out);twid’s are mathematically derivable constants7Higher-order functions:Stage functions f1, f2 and f3function f1(x); return (stage_f(1,x)); endfunctionfunction f2(x); return (stage_f(2,x)); endfunctionfunction f3(x); return(stage f(3,x));February 10, 2010L03-13http://csg.csail.mit.edu/6.375return(stage_f(3,x)); endfunctionWhat is the type of f1(x) ?Suppose we want to reuse some part of the circuit ...in0out0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4……out1out2out63out3out4PermutePermutePermuteFebruary 10, 2010L03-14http://csg.csail.mit.edu/6.375Reuse the same circuit three times to reduce areaBut why?8Architectural Exploration:AP f t d ff i Area-Performance tradeoff in 802.11a TransmitterFebruary 10, 2010 http://csg.csail.mit.edu/6.375 L03-15802.11a Transmitter OverviewheadersMust produce Controller Scrambler EncoderInterleaver Mapperdata24 Uncoded bitsMust produce one OFDM symbol every 4 μsecDepending upon the transmission rate, consumes 1, 2 or 4 tokens February 10, 2010L03-16http://csg.csail.mit.edu/6.375IFFTCyclicExtendIFFT Transforms 64 (frequency domain) complex numbers into 64 (time domain) complex numbersaccounts for 85% areaOne OFDM symbol (64 Complex Numbers)to produce one OFDM symbol9Preliminary results[MEMOCODE 2006] Dave, Gerding, Pellauer, ArvindDesign Lines of Block Code (BSV)RelativeAreaBlock Code (BSV)Controller 49 Scrambler 40 Conv. Encoder 113 Interleaver 76 Mapper112 Area0%0%0%1%11%February 10,
View Full Document
Unlocking...