high-throughput asynchronous pipelines for fine-grain dynamic 细粒度的动态高吞吐量的异步管道

High-ThroughputAsynchronous Pipelines forFine-Grain Dynamic Datapaths,Montek Singh and Steven NowickColumbia UniversityNew York, USAmontek,/montek,Intl. Symp. Adv. Res. Asynchronous Circ. Syst. (ASYNC), April 2-6, 2000, Eilat, Israel.,2,Outline,IntroductionBackground: Williams PS0 pipelinesNew Pipeline DesignsDual-Rail: LP3/1, LP2/2 and LP2/1Single-Rail: LPSR2/1Practical Issue: Handling slow environmentsResults and Conclusions,3,Why Dynamic Logic?,Potentially:Higher speedSmaller area“Latch-free” pipelines:Logic gate itself provides an implicit latchlower latencyshorter cycle timesmaller area very important in gate-level pipelining!Our Focus: Dynamic logic pipelines,4,How Do We Achieve High Throughput?,Introduce novel pipeline protocols:specifically target dynamic logicreduce impact of handshaking delaysshorter cycle timesPipeline at very fine granularity:“gate-level:” each stage is a single-gate deephighest throughputs possiblelatch-free datapaths especially desirabledynamic logic is a natural match,5,Prior Work: Asynchronous Pipelines,Sutherland (1989), Yun/Beerel/Arceo (1996)very elegant 2-phase control expensive transition latchesDay/Woods (1995), Furber/Liu (1996)4-phase control simpler latches, but complex controllersKol/Ginosar (1997)double latches greater concurrency, but area-expensiveMolnar et al. (1997-99)Two designs: asp* and micropipeline both very fast, but:asp*: complex timing, cannot handle latch-free dynamic datapathsmicropipeline: area-expensive, cannot do logic processing at all!Williams (1991), Martin (1997)dynamic stages no explicit latches! low latencythroughput still limited,6,Background,IntroductionBackground: Williams PS0 pipelinesNew Pipeline DesignsDual-Rail: LP3/1, LP2/2 and LP2/1Single-Rail: LPSR2/1Practical Issue: Handling slow environmentsResults and Conclusions,7,PS0 Pipelines (Williams 1986-91),Basic Architecture:,8,PS0 Function Block,Each output is produced using a dynamic gate:,9,Dual-Rail Completion Detector,OR together two rails of each bitCombine results using C-element,10,Precharge Evaluate: another 3 events,Complete cycle: 6 events,N+1 indicates “done”,PRECHARGE N: when N+1 completes evaluationEVALUATE N: when N+1 completes precharging,PS0 Protocol,N evaluates,N+1 evaluates,N+2 evaluates,N+2 indicates “done”,N+1 precharges,Evaluate Precharge: 3 events,N,N+1,N+2,11,PS0 Performance,Cycle Time =,12,New Pipeline Designs,IntroductionBackground: Williams PS0 pipelinesNew Pipeline DesignsDual-Rail: LP3/1, LP2/2 and LP2/1Single-Rail: LPSR2/1Practical Issue: Handling slow environmentsResults and Conclusions,13,Overview of Approach,Our Goal: Shorter cycle time, without degrading latencyOur Approach: Use “Lookahead Protocols” (LP):main idea: anticipate critical events based on richer observationTwo new protocol optimizations:“Early evaluation:”give stage head-start on evaluation by observing events further down the pipeline(actually, a similar idea proposed by Williams in PA0,but our designs exploit it much better)“Early done:”stage signals “done” when it is about to precharge/evaluate,14,Uses “early evaluation:”each stage now has two control inputsthe new input comes from two stages aheadevaluate N as soon as N+1 starts precharging,Dual-Rail Design #1: LP3/1,15,LP3/1 Protocol,PRECHARGE N: when N+1 completes evaluationEVALUATE N: when N+2 completes evaluation,N evaluates,N+1 evaluates,N+2 indicates “done”,N+2 evaluates,N,N+1,N+2,16,PS0,LP3/1,LP3/1: Comparison with PS0,Only 4 events in cycle!,6 events in cycle,N,N+1,N+2,N,N+1,N+2,17,LP3/1 Performance,Cycle Time =,saved path,Savings over PS0: 1 Precharge + 1 Completion Detection,18,Inside a Stage: Merging Two Controls,Precharge when PC=1(and Eval=0)Evaluate “early” when Eval=1(or PC=0),A NAND gate combinesthe two control inputs:,Problem: “early” Eval=1 is non-persistent!it may get de-asserted before the stage has completed evaluation!,19,LP3/1 Timing Constraints: Example,Observation: PC=0 soon after Eval=1, and is persistent use PC as safe “takeover” for Eval!Solution: no change!Timing Constraint: PC=0 arrives before Eval=1 is de-assertedsimple one-sided timing requirementother constraints as well all easily satisfied in practice,Problem: “early” Eval=1 is non-persistent!,20,Dual-Rail Design #2: LP2/2,Uses “early done:”completion detector now before functional blockstage indicates “done” when about to precharge/evaluate,21,LP2/2 Completion Detector,Modified completion detectors needed:Done=1 when stage starts evaluating, and inputs validDone=0 when stage starts prechargingasymmetric C-element,22,LP2/2 Protocol,Completion detection occurs in parallel with evaluation/precharge:,N evaluates,N+1 evaluates,N,N+1,N+2,23,LP2/2 Performance,1,2,4,Cycle Time =,LP2/2 savings over PS0: 1 Evaluation + 1 Precharge,24,Dual-Rail Design #3: LP2/1,Hybrid of LP3/1 and LP2/2. Combines:early evaluation of LP3/1early done of LP2/2,Cycle Time =,25,New Pipeline Designs,IntroductionBackground: Williams PS0 pipelinesNew Pipeline DesignsDual-Rail: LP3/1, LP2/2 and LP2/1Single-Rail: LPSR2/1Practical Issue: Handling slow environmentsResults and Conclusions,26,Single-Rail Design: LPSR2/1,Derivative of LP2/1, adapted to single-rail:bundled-data: matched delays instead of completion detectors,27,Inside an LPSR2/1 Stage,28,LPSR2/1 Protocol,Cycle Time =,N evaluates,N,N+1,N+2,29,Practical Issue: Handling Slow Environments,We inherit a timing assumption from Williams PS0:Input (left) environment must precharge reasonably fastProblem:If environment is stuck in precharge,all pipelines (incl. PS0) will malfunction!Our Solution:Add a special robust controller for 1st stagesimply synchronizes input environment and pipelinedelay critical events until environment has finished prechargeModular solution overcomes shortcoming of Williams PS0No serious throughput overheadreal bottleneck is the slow environment!,30,Results and Conclusions,IntroductionBackground: Williams PS0 pipelinesNew Pipeline DesignsDual-Rail: LP3/1, LP2/2 and LP2/1Single-Rail: LPSR2/1Practical Issue: Handling slow environmentsResults and Conclusions,31,Results,Designed/simulated FIFOs for each pipeline style Experimental Setup:design: 4-bit wide, 10-stage FIFOtechnology: 0.6 HP CMOSoperating conditions: 3.3 V and 300K,32,dual-rail,single-rail,Comparison with Williams PS0,LP2/1: 2X faster than Williams PS0LPSR2/1: 1.2 Giga items/sec,33,Comparison: LPSR2/1 vs. Molnar FIFOs,LPSR2/1 FIFO: 1.2 Giga items/secAdding logic processing to FIFO:simply fold logic into dynamic gate little overheadComparison with Molnar FIFOs:asp* FIFO: 1.1 Giga items/secmore complex timing assumptions not easily formalizedrequires explicit latches, separate from logic!adding logic processing between stages significant overheadmicropipeline: 1.7 Giga items/sectwo parallel FIFOs, each only 0.85 Giga/secvery expensive transition latchescannot add logic processing to FIFO!,34,P