Slide 1Bluespec: Two-Level CompilationStatic ElaborationCombinational IFFT4-way Butterfly NodeBSV code: 4-way ButterflySlide 7BSV Code: Combinational IFFTBSV Code: Combinational IFFT- UnfoldedBluespec Code for stage_fSuppose we want to reuse some part of the circuit ...Slide 12802.11a Transmitter OverviewPreliminary results [MEMOCODE 2006] Dave, Gerding, Pellauer, ArvindSlide 15Design AlternativesCircular pipeline: Reusing the Pipeline StageSuperfolded circular pipeline: Just one Bfly-4 node!Pipelining a blockSynchronous pipelineStage functions f1, f2 and f3Problem: What about pipeline bubbles?The Maybe type data in the pipelineFolded pipeline802.11a Transmitter Synthesis results (Only the IFFT block is changing)Why are the areas so similarLanguage notesPattern-matching: A convenient way to extract datastructure componentsSyntax: Vector of RegistersMaking guards explicitImplicit guards (conditions)Guards vs If’sFebruary 20, 2008 http://csg.csail.mit.edu/6.375 L06-1Combinational Circuits and Simple Synchronous PipelinesArvind Computer Science & Artificial Intelligence LabMassachusetts Institute of TechnologyFebruary 20, 2008L06-2http://csg.csail.mit.edu/6.375Object code(Verilog/C)Bluespec: Two-Level CompilationRules and Actions(Term Rewriting System)• Rule conflict analysis• Rule schedulingJames Hoe & Arvind@MIT 1997-2000Bluespec(Objects, Types,Higher-order functions)Level 1 compilation• Type checking• Massive partial evaluation and static elaborationLevel 2 synthesisLennart Augustsson@Sandburst 2000-2002Now we call this Guarded Atomic ActionsFebruary 20, 2008L06-3http://csg.csail.mit.edu/6.375Static Elaboration.execompiledesign2 design3design1elaborate w/paramsrun1run1run2.1…run1run1run3.1…run1run1run1.1…run w/paramsrun w/paramsrun1run1…runAt compile timeInline function calls and unroll loopsInstantiate modules with specific parametersResolve polymorphism/overloading, perform most data structure operationssourceSoftwareToolflow:sourceHardwareToolflow:February 20, 2008L06-4http://csg.csail.mit.edu/6.375Combinational IFFTin0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4…out0…out1out2out63out3out4PermutePermutePermuteAll numbers are complex and represented as two sixteen bit quantities. Fixed-point arithmetic is used to reduce area, power, ...****+--++--+*jt2t0t3t1February 20, 2008L06-5http://csg.csail.mit.edu/6.3754-way Butterfly Nodefunction Vector#(4,Complex) bfly4 (Vector#(4,Complex) t, Vector#(4,Complex) k);BSV has a very strong notion of typesEvery expression has a type. Either it is declared by the user or automatically deduced by the compilerThe compiler verifies that the type declarations are compatible ****+--++--+*it0t1 t2 t3k0k1 k2 k3February 20, 2008L06-6http://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]); 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 20, 2008L06-7http://csg.csail.mit.edu/6.375Combinational IFFTin0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4…out0…out1out2out63out3out4PermutePermutePermutestage_f functionrepeat it three timesFebruary 20, 2008L06-8http://csg.csail.mit.edu/6.375BSV Code: Combinational IFFTfunction 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 elaborationNote: no notion of loops or procedures during executionFebruary 20, 2008L06-9http://csg.csail.mit.edu/6.375BSV Code: Combinational IFFT- Unfoldedfunction 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]);Stage_f can be inlined now; it could have been inlined before loop unfolding also.Does the order matter?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 20, 2008L06-10http://csg.csail.mit.edu/6.375Bluespec Code for stage_ffunction 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]]; endreturn(stage_out);twid’s are mathematically derivable constantsFebruary 20, 2008L06-11http://csg.csail.mit.edu/6.375Suppose we want to reuse some part of the circuit ...in0…in1in2in63in3in4Bfly4Bfly4Bfly4x16Bfly4Bfly4Bfly4…Bfly4Bfly4Bfly4…out0…out1out2out63out3out4PermutePermutePermuteReuse the same circuit three times to reduce areaBut why?February 20, 2008 http://csg.csail.mit.edu/6.375 L06-12Architectural Exploration:Area-Performance tradeoff in 802.11a TransmitterFebruary 20, 2008L06-13http://csg.csail.mit.edu/6.375802.11a Transmitter OverviewController Scrambler EncoderInterleaver MapperIFFTCyclicExtendheadersdataIFFT Transforms 64 (frequency domain) complex numbers into 64 (time domain) complex numbersaccounts for 85% area24 Uncoded bitsOne 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 20, 2008L06-14http://csg.csail.mit.edu/6.375Preliminary 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
View Full Document
Unlocking...