1EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 1High Level Synthesis• Data Flow Graphs• FSM with Data Path• Allocation• Scheduling• Implementation• Directions in Architectural SynthesisEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 2High Level Synthesis (HLS)• Convert a high-level description of a design to a RTL netlist– Input:• High-level languages (e.g., C)• Behavioral hardware description languages (e.g., VHDL)• State diagrams / logic networks–Tools:•Parser• Library of modules– Constraints:• Area constraints (e.g., # modules of a certain type)• Delay constraints (e.g., set of operations should finish in clock cycles)– Output:• Operation scheduling (time) and binding (resource)• Control generation and detailed interconnections2EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 3High Level SynthesisCDFGParsingTransformationSynthesisStructuralRTLBehavioralDescriptionEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 4Structural BehavioralPhysicalTransGateRTLBlockBooleanFSMAlgorithmGDSIIPlacementFloorplanLayoutSynthesisSource: D. Gajski, Y.-L. Lin3EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 5Structural BehavioralPhysicalTrans.GateRTLBlockBooleanFSMAlgorithmGDSIIPlacementFloorplanLogicSynthesisSource: D. Gajski, Y.-L. LinEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 6Structural BehavioralPhysicalTrans.GateRTLBlockBooleanFSMAlgorithmGDSIIPlacementFloorplanHigh-LevelSynthesisSource: D. Gajski, Y.-L. Lin4EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 7Essential Issues• Behavioral Specification Languages• Target Architectures• Intermediate Representation• Operation Scheduling• Allocation/Binding• Control GenerationEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 8Behavioral Specification Languages• Add hardware-specific constructs to existing languages– SystemC• Popular HDL– Verilog, VHDL• Synthesis-oriented HDL–UDL/I5EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 9Target Architectures• Bus-based• Multiplexer-based• Register file• Pipelined• RISC, VLIW• Interface ProtocolEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 10Design Space ExplorationArch IArch IIArch IIIDelayArea6EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 11FSM with Data Path (FSMD)FSMDataPathFSMDataPathFSMDataPathCommunicating FSMDsEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 12Intermediate Representation (CDFG)* *+Control Flow GraphData Flow Graph7EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 13Allocation/BindingFunctional UnitsOperationsStorageVariablesSignalsBus/Wire/MuxData TransfersEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 14RFFUFURFVariables/SignalsData TransferOperations8EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 15Controller Specification GenerationScheduledCDFGAllocatedDatapathMicro-OperationsforEvery Control StepEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 16Quality Measures for High-Level Synthesis• Performance• Area Cost• Power Consumption• Testability• Reusability9EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 17Hardware Variations• Functional Units– Pipelined, Multi-Cycle, Chained, Multi-Function• Storage– Register, RF, Multi-Ported, RAM, ROM, FIFO, Distributed• Interconnect– Bus, Segmented Bus, Mux, Protocol-BasedEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 18Functional Unit Variations+****-+Step 1Step 2Step 3Step 4+++10EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 19Storage/Interconnect VariationsRFFUFURFSegmentedBusesDistributedFIFOMuxChainingMulti-PortEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 20Architectural PipeliningFSMDataPath11EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 21High-Level Synthesis Compilation FlowLexParseCompilationfront-endBehavioralOptimizationIntermediateformArch synthLogic synthLib BindingHLS backendx = a + b  c + d++ab cd++ ad bcSource: R. GuptaEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 22Data flow graph• Data flow graph (DFG) models data dependencies• Does not require that operations be performed in a particular order• Models operations in a basic block of a functional model—no conditionals• Requires single-assignment form12EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 23Data flow graph constructionoriginal code:x <= a + b;y <= a * c;z <= x + d;x <= y - d;x <= x + c;single-assignment form:x1 <= a + b;y <= a * c;z <= x1 + d;x2 <= y - d;x3 <= x2 + c;EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 24Data flow graph construction, cont’dData flow forms directed acyclic graph (DAG):13EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 25Goals of scheduling and allocation• Preserve behavior—at end of execution, should have received all outputs, be in proper state (ignoring exact times of events)• Utilize hardware efficiently• Obtain acceptable performanceEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 26Data flow to data path-controllerOne feasible schedule for last DFG:14EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 27Binding values to registersregisters fall onclock cycleboundariesEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 28Choosing function unitsmuxes allowfunction unitsto be sharedfor severaloperations15EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 29Building the sequencerSequencer requires three states,even with no conditionalsEE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 30Behavioral Optimization• Techniques used in software compilation– Expression tree height reduction– Constant and variable propagation– Common sub-expression elimination– Dead-code elimination– Operator strength reduction • Typical Hardware transformations– Conditional expansion• If (c) then x=A else x=B compute A and B in parallel, x=(C)?A:B– Loop expansion• Instead of three iterations of a loop, replicate the loop body three timesABxcSource: R. Gupta16EE 382V: SoC Design, Fall 2009J. A. AbrahamHLS 31Architectural Synthesis• Deals with “computational” behavioral descriptions– Behavior as sequencing graph(called dependency graph, or data flow graph DFG)– Hardware resources as library elements• Pipelined or non-pipelined• Resource performance in terms of execution delay – Constraints on operation timing– Constraints on hardware resource availability– Storage as registers, data transfer using wires • Objective– Generate a synchronous, single-phase clock circuit– Might have multiple feasible solutions (explore tradeoff)– Satisfy constraints, minimize objective:• Maximize performance subject to area