1ArchitecturalArchitectural--Level SynthesisLevel SynthesisGiovanni De MicheliIntegrated Systems CentreEPF LausanneThis presentation can be used for non-commercial purposes as long as this note and the copyright footers are not removed© Giovanni De Micheli – All rights reserved(c) Giovanni De Micheli2Module1Objectives Motivation Compiling language models into abstract models Behavioral-level optimization and program-level transformations2(c) Giovanni De Micheli3Synthesis Transform behavioral into structural view Architectural-level synthesis: Architectural abstraction level Determine macroscopic structure Example: major building blocksLogic-level synthesis: Logic abstraction level Determine microscopic structure Example: logic gate interconnection(c) Giovanni De Micheli4Models and flowsLANGUAGE MODELSABSTRACT MODELSHDLHDLHDLcompilationcompilationtranslationOperations and dependencies (Data-flow & sequencing graphs)FSMs – Logic functions (State-diagrams & logic networks)Interconnected logic blocks (Logic networks)BEHAVIORAL VIEWSTRUCTURAL VIEWARCHITECTURAL LEVELLOGIC LEVELPhysical design(mask layout)VerilogVHDLSystemCEsterelStatechartsSchematicsGDS23(c) Giovanni De Micheli5Examplediffeq {read (x; y; u; dx; a);repeat {xl = x+dx;ul = u –(3 .x .u .dx) – (3 .y .dx)yl = y + u .dx ;c = x < a;X = xl; u = ul; y = yl;}until ( c )write (y) (c) Giovanni De Micheli6Example of structures*ALUSTEERING & MEMORYCONTROL UNIT*ALUSTEERING & MEMORYCONTROL UNIT*ALU4(c) Giovanni De Micheli7Example1234567851015781213(2,2)(2,1)(1,2)(1,1)AreaLatencyX(c) Giovanni De Micheli8Architectural-level synthesis motivation Raise input abstraction level Reduce specification of details Extend designer base Self-documenting design specifications Ease modifications and extensions Reduce design time Explore and optimize macroscopic structure: Series/parallel execution of operations5(c) Giovanni De Micheli9Architectural-level synthesis Translate HDL models into sequencing graphs Behavioral-level optimization: Optimize abstract models independently from the implementation parameters Architectural synthesis and optimization: Create macroscopic structure: Data-path and control-unit Consider area and delay information of the implementation(c) Giovanni De Micheli10Compilation and behavioral optimization Software compilation: Compile program into intermediate form Optimize intermediate form Generate target code for an architecture Hardware compilation: Compile HDL model into sequencing graph Optimize sequencing graph Generate gate-level interconnection for a cell library6(c) Giovanni De Micheli11Hardware and software compilationlex parse optimization codegenfront-end Intermediate form back-endlex parsebehavioral optimizationfront-end Intermediate form back-enda-synthesisl-synthesisl-binding(c) Giovanni De Micheli12Compilation Front-end: Lexical and syntax analysis Parse-tree generation Macro-expansion Expansion of meta-variables Semantic analysis: Data-flow and control-flow analysis Type checking Resolve arithmetic and relational operators7(c) Giovanni De Micheli13Parse tree examplea = p + q * rassignmentidentifierexpressionexpressionidentifieridentifier identifiera=+*pqr(c) Giovanni De Micheli14Behavioral-level optimizationSemantic-preserving transformations aiming at simplifying the modelApplied to parse-trees or during their generationTaxonomy: Data-flow based transformations Control-flow based transformations8(c) Giovanni De Micheli15Data-flow based transformationsTree-height reductionConstant and variable propagationCommon sub-expression eliminationDead-code eliminationOperator-strength reductionCode motion(c) Giovanni De Micheli16Tree-height reduction Applied to arithmetic expressions Goal: Split into two-operand expressions to exploit hardware parallelism at bestTechniques: Balance the expression tree Exploit commutativity, associativity and distributivity9(c) Giovanni De Micheli17Example of tree-height reduction using commutativity and associativity++**++aabbc cddx = a + b * c + d → x = (a + d) + b * c(c) Giovanni De Micheli18Example of tree-height reduction using distributivity*+**+* ** *aabbccddeeax = a * (b * c * d + e) → x = a * b * c * d + a * e;10(c) Giovanni De Micheli19Examples of propagationConstant propagationa = 0; b = a + 1; c = 2 * b;a = 0; b = 1; c = 2;Variable propagation:a = x; b = a + 1; c = 2 * x;a = x; b = x + 1; c = 2 * x; (c) Giovanni De Micheli20Sub-expression elimination Logic expressions: Performed by logic optimization Kernel-based methodsArithmetic expressions: Search isomorphic patterns in the parse trees Example:a = x + y; b = a +1; c = x + ya = x + y; b = a + 1; c = a;11(c) Giovanni De Micheli21Examples of other transformations Dead-code elimination:a = x; b = x + 1; c = 2 *x;a = x; can be removed if not referenced Operator-strength reduction:a = x2, b = 3 *x;a = x *x; t = x << 1; b = x + t; Code motion:for ( i = 1; i < a *b) { }t = a *b; for ( i = 1; i < t) { }(c) Giovanni De Micheli22Control-flow based transformationsModel expansionConditional expansionLoop expansionBlock-level transformations12(c) Giovanni De Micheli23Model expansion Expand subroutine Flatten hierarchy Expand scope of other optimization techniques Problematic when model is called more than once Example:x = a + b; y = a *b; z = foo (x , y);foo(p,q) { t=q - p; return (t); }By expanding foo:x = a + b; y = a*b; z = y – x;(c) Giovanni De Micheli24Conditional expansion Transform conditional into parallel execution with test at the end Useful when test depends on late signals May preclude hardware sharing Always useful for logic expressions Example:y = ab; if (a) {x = b + d; } else { x = bd; } Can be expanded to: x = a (b + d) + a’bd And simplified as: y = ab; x = y + d ( a + b )13(c) Giovanni De Micheli25Loop expansion Applicable to loops with data-independent exit conditions Useful to expand scope of other optimization techniques Problematic when loop has many iterations Example:x = 0; for ( I = 1; I < 3; I ++ ) { x = x + 1; } Expanded to:x = 0; x = x + 1; x = x + 2; x = x + 3(c) Giovanni De Micheli26Module2Objectives Architectural optimization Scheduling, resource