Logic Restructuring for Timing OptimizationTiming OptimizationProblem StatementCurrent Design ProcessTechnology mapping for delayOverview of Solutions for delayCircuit re-structuringRe-structuring methodsRe-structuring for delay: tree-height reductionRestructuring for delay: path reductionGeneralized bypass transform (GBX)GBX and KMS transformKMS (Keutzer, Malik, Saldanha ‘90)End of lecture 20Generalized select transform (GST)GST vs GBXGST vs GBXTechnology independent delay reductionsClustering/partial-collapseSlide 20Lawler’s clustering algorithmClustering algorithm - overviewExample of clusteringChoosing kArea recoveryRelabeling procedure:Relabeling examplePost-collapse area recoveryConclusions1Logic Restructuring for Logic Restructuring for Timing OptimizationTiming OptimizationOutline:Outline:•Definitions and problem statementDefinitions and problem statement•Overview of techniques Overview of techniques (motivated by (motivated by adders)adders)–Tree height reduction (THR)Tree height reduction (THR)–Generalized bypass transform (GBX)Generalized bypass transform (GBX)–Generalized select transform (GST)Generalized select transform (GST)–Partial collapsing (?)Partial collapsing (?)2Timing OptimizationTiming OptimizationFactors determining Factors determining delaydelay of circuit: of circuit:•Underlying Underlying circuitcircuit technology technology–Circuit type Circuit type (e.g. domino, static CMOS, etc.)(e.g. domino, static CMOS, etc.)–Gate typeGate type–Gate sizeGate size•Logical Logical structurestructure of circuit of circuit–Length of computation pathsLength of computation paths–False pathsFalse paths–BufferingBuffering•ParasiticsParasitics–Wire loadsWire loads–Layout Layout3Problem StatementProblem StatementGiven:Given:•Initial circuit function descriptionInitial circuit function description•Library of primitive functionsLibrary of primitive functions•Performance constraints Performance constraints (arrival/required (arrival/required times)times)Generate:Generate:an implementation of the circuit using the an implementation of the circuit using the primitive functions, such that:primitive functions, such that:1.1. performanceperformance constraints are met constraints are met2.2. circuit circuit areaarea is minimized is minimized4Current Design ProcessCurrent Design ProcessBehaviorBehaviorOptiizationOptiization(scheduling)(scheduling)PartitioningPartitioning(retiming)(retiming)Logic synthesisLogic synthesis•Technology independentTechnology independent•Technology mappingTechnology mappingTiming drivenTiming drivenplace and routeplace and routeBehavioral descriptionBehavioral descriptionLogic and latchesLogic and latchesLogic equationsLogic equationsGate netlistGate netlistLayout Layout •Gate libraryGate library•Perf. ConstraintsPerf. Constraints•Delay modelsDelay models5Technology mapping for Technology mapping for delaydelayFunctionFunctiontreetreeBufferBuffertreetree6Overview of Solutions for Overview of Solutions for delaydelay1.1.Circuit Circuit re-structuringre-structuring–Rescheduling operations to reduce time of computationRescheduling operations to reduce time of computation2.2.Implementation of Implementation of functionfunction trees trees (technology mapping)(technology mapping)–Selection of gates from librarySelection of gates from library•Minimum delay Minimum delay (load independent model - Kukimoto)(load independent model - Kukimoto)•Minimize delay and area Minimize delay and area (Jongeneel, DAC’00)(Jongeneel, DAC’00)(combines Lehman-Watanabe and Kukimoto)(combines Lehman-Watanabe and Kukimoto)3.3.Implementation of Implementation of bufferbuffer trees trees–Touati Touati (LT-trees)(LT-trees)–SinghSingh4.4.ResizingResizingFocus Focus herehere on circuit on circuit re-structuringre-structuring7Circuit re-structuringCircuit re-structuringApproaches:Approaches:Local:Local: •Mimic optimization techniques in Mimic optimization techniques in addersadders–Carry lookahead (Carry lookahead (THRTHR tree height reduction) tree height reduction)–Conditional sum (Conditional sum (GSTGST transformation) transformation)–Carry bypass (Carry bypass (GBXGBX transformation) transformation)Global:Global:•Reduce depth of entire circuitReduce depth of entire circuit–Partial collapsingPartial collapsing–Boolean simplificationBoolean simplification8Re-structuring methodsRe-structuring methodsPerformance measured by Performance measured by 1.1.levels, levels, 2.2.sensitizable paths, sensitizable paths, 3.3.technology dependent delaystechnology dependent delays•LevelLevel based optimizations: based optimizations:–Tree height reduction (Singh ‘88)Tree height reduction (Singh ‘88)–Partial collapsing and simplification (Touati ‘91)Partial collapsing and simplification (Touati ‘91)–Generalized select transform (Berman ‘90)Generalized select transform (Berman ‘90)•SensitizableSensitizable paths paths–Generalized bypass transform (Mcgeer ‘91)Generalized bypass transform (Mcgeer ‘91)9Re-structuring for delay: Re-structuring for delay: tree-height reductiontree-height reductionnnllmmiijjhhkk3366555511441100000000220000aabbccddeeffggii110000aabbmmjjhhkk3344110000220000ccddeeffggn’n’DuplicatedDuplicatedlogiclogic1122000055CriticalCriticalregionregionCollapsedCollapsedCritical regionCritical region10Restructuring for delay: Restructuring for delay: path reductionpath reductionii110000aabbmmjjhhkk3344110000220000ccddeeffggn’n’DuplicatedDuplicatedlogiclogic1122000055ii110000aabbmmjjhhkk3344110000220000ccddeeffgg1122003355n’n’22110044Singh ‘88Singh ‘88CollapsedCollapsedCritical regionCritical regionNew delay = 5New delay = 511Generalized bypass Generalized bypass transform (GBX)transform (GBX)•Make critical path Make critical path falsefalse–Speed up the circuitSpeed up the circuit•BypassBypass logic of critical path(s) logic of critical path(s)McGeer ‘91McGeer ‘91ffmm=f=fffm+1m+1ffnn=g=g……ffm m =f=fffm+1m+1ffnn=g=g……0011g’g’dgdg____dfdfBooleanBooleandifferencedifferences-a-0 redundants-a-0 redundant12GBX and KMS transformGBX and KMS transformGBX gives little area increase, GBX gives little area increase, BUT BUT have now created an have now created an untestableuntestable fault fault (on control input to multiplexor)(on control input to multiplexor)KMS transform:KMS transform: (remove false paths without increasing delay)(remove false