1February 16, 2007 http://csg.csail.mit.edu/6.375/ L05-1Architectural Exploration:Area-Power tradeoff in 802.11a transmitter designArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 16, 2007L05-2http://csg.csail.mit.edu/6.375/This lecture has two purposesIllustrate how area-power tradeoff can be studied at a high-level for a realistic design Example: 802.11a transmitterIllustrate some features of BSV Static elaboration Combinational circuits Simple synchronous pipelines Valid bits as the Maybe type in BSVNo prior understanding of 802.11a is necessary to follow this lecture2February 16, 2007L05-3http://csg.csail.mit.edu/6.375/Object code(Verilog/C)Bluespec: Two-Level CompilationRules and Actions(Term Rewriting System)• Rule conflict analysis• Rule schedulingwJames Hoe & Arvindw@MIT 1997-2000Bluespec(Objects, Types,Higher-order functions)Level 1 compilation• Type checking• Massive partial evaluationand static elaborationLevel 2 synthesiswLennart Augustssonw@Sandburst 2000-2002Now we call this Guarded Atomic ActionsFebruary 16, 2007L05-4http://csg.csail.mit.edu/6.375/Static Elaboration.execompiledesign2 design3design1elaborate w/paramsrun1run1run2.1…run1run1run3.1…run1run1run1.1…run w/paramsrun w/paramsrun2run1 run1run1…run3At compile time Inline function calls and datatypes Instantiate modules with specific parameters Resolve polymorphism/overloadingsourceSoftwareToolflow:sourceHardwareToolflow:3February 16, 2007L05-5http://csg.csail.mit.edu/6.375/802.11a Transmitter OverviewController Scrambler EncoderInterleaver MapperIFFTCyclicExtendheadersdataIFFT Transforms 64 (frequency domain) complex numbers into 64 (time domain) complex numbersaccounts for 85% area24 UncodedbitsOne OFDM symbol (64 Complex Numbers)Must produce one OFDM symbol every 4 μsecDepending upon the transmission rate, consumes 1, 2 or 4 tokens to produce one OFDM symbolFebruary 16, 2007L05-6http://csg.csail.mit.edu/6.375/Preliminary results[MEMOCODE 2006] Dave, Gerding, Pellauer, ArvindDesign Lines of RelativeBlock Code (BSV) AreaController 49 0%Scrambler 40 0%Conv. Encoder 113 0%Interleaver 76 1%Mapper 112 11%IFFT 95 85%Cyc. Extender 23 3%Complex arithmetic libraries constitute another 200 lines of code4February 16, 2007L05-7http://csg.csail.mit.edu/6.375/Combinational IFFTin0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4…out0…out1out2out63out3out4Permute_1Permute_2Permute_3All numbers are complex and represented as two sixteen bit quantities. Fixed-point arithmetic is used to reduce area, power, ...****+--++--+*jt2t0t3t1February 16, 2007L05-8http://csg.csail.mit.edu/6.375/4-way Butterfly Nodefunction 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 ****+--++--+*it0t1 t2 t3k0k1 k2 k35February 16, 2007L05-9http://csg.csail.mit.edu/6.375/BSV code: 4-way Butterflyfunction Vector#(4,Complex) Bfly4(Vector#(4,Complex) t, Vector#(4,Complex) k);Vector#(4,Complex) m = newVector(),y = newVector(),z = newVector();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);endfunctionPolymorphic code: works on any type of numbers for which *, + and -have been defined****+--++--+*im yz Note: Vector does not mean storageFebruary 16, 2007L05-10http://csg.csail.mit.edu/6.375/Combinational IFFTin0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4…out0…out1out2out63out3out4Permute_1Permute_2Permute_3stage_f functionrepeat it three times6February 16, 2007L05-11http://csg.csail.mit.edu/6.375/BSV Code: Combinational IFFTfunction SVector#(64, Complex) ifft(SVector#(64, Complex) in_data);//Declare vectorsSVector#(4,SVector#(64, Complex)) stage_data = replicate(newSVector);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_fis inlined during static elaborationNote: no notion of loops or procedures during executionFebruary 16, 2007L05-12http://csg.csail.mit.edu/6.375/BSV Code: Combinational IFFT- Unfoldedfunction SVector#(64, Complex) ifft(SVector#(64, Complex) in_data);//Declare vectorsSVector#(4,SVector#(64, Complex)) stage_data = replicate(newSVector);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]);7February 16, 2007L05-13http://csg.csail.mit.edu/6.375/Bluespec Code for stage_ffunction SVector#(64, Complex) stage_f(Bit#(2) stage, SVector#(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];end//Permutationfor (Integer i = 0; i < 64; i = i + 1)stage_out[i] = stage_temp[permute[i]];endreturn(stage_out);February 16, 2007 http://csg.csail.mit.edu/6.375/ L05-14Architectural Exploration8February 16, 2007L05-15http://csg.csail.mit.edu/6.375/f gDesign AlternativesReuse a block over multiple cycleswe expect:Throughput toArea toffgFebruary 16, 2007L05-16http://csg.csail.mit.edu/6.375/Combinational IFFTOpportunity for reusein0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4…out0…out1out2out63out3out4Permute_1Permute_2Permute_3Reuse the same circuit three times9February 16, 2007L05-17http://csg.csail.mit.edu/6.375/Circular pipeline: Reusing the Pipeline Stagein0…in1in2in63in3in4out0…out1out2out63out3out4…Bfly4Bfly4Permute_1Permute_2Permute_3Stage Counter16 Bfly4s can be shared but not the three permutations. Hence the need for muxes64, 4-way MuxesFebruary 16, 2007L05-18http://csg.csail.mit.edu/6.375/Superfolded circular pipeline: Just one Bfly-4 node!in0…in1in2in63in3in4out0…out1out2out63out3out4Bfly4Permute_1Permute_2Permute_3Stage Counter 0 to 2Index Counter 0 to 1564, 4-way Muxes4, 16-way Muxes4, 16-way DeMuxes10February 16, 2007L05-19http://csg.csail.mit.edu/6.375/Algorithmic
View Full Document
Unlocking...