Design Methodologies and CAD Toolsfor Leakage Power Optimization inFPGAsbyHassan HassanA thesispresented to the University of Waterlooin fulfillment of thethesis requirement for the degree ofDoctor of PhilosophyinElectrical and Computer EngineeringWaterloo, Ontario, Canada, 2008c© Hassan Hassan 2008I hereby declare that I am the sole author of this thesis. This is a true copy of thethesis, including any required final revisions, as accepted by my examiners.I understand that my thesis may be made electronically available to the public.iiAbstractThe scaling of the CMOS technology has precipitated an exponential increasein both subthreshold and gate leakage currents in modern VLSI designs. Conse-quently, the contribution of leakage power to the total chip power dissipation forCMOS designs is increasing rapidly, which is estimated to be 40% for the cur-rent technology generations and is expected to exceed 50% by the 65nm CMOStechnology. In FPGAs, the power dissipation problem is further aggravated whencompared to ASIC designs because FPGA use more transistors per logic functionwhen compared to ASIC designs. Consequently, solving the leakage power problemis pivotal to devising power-aware FPGAs in the nanometer regime. This thesisfocuses on devising both architectural and CAD techniques for leakage mitigationin FPGAs. Several CAD and architectural modifications are proposed to reducethe impact of leakage power dissipation on modern FPGAs.Firstly, multi-threshold CMOS (MTCMOS) techniques are introduced to FP-GAs to permanently turn OFF the unused resources of the FPGA, FPGAs arecharacterized with low utilization percentages that can reach 60%. Moreover, sucharchitecture enables the dynamic shutting down of the FPGA idle parts, thus re-ducing the standby leakage significantly. Employing the MTCMOS technique inFPGAs requires several changes to the FPGA architecture, including the place-ment and routing of the sleep signals and the MTCMOS granularity. On the CADlevel, the packing and placement stages are modified to allow the possibility ofdynamically turning OFF the idle parts of the FPGA. A new activity generationalgorithm is proposed and implemented that aims to identify the logic blocks in adesign that exhibit similar idleness periods. Several criteria for the activity genera-tion algorithm are used, including connectivity and logic function. Several versionsof the activity generation algorithm are implemented to trade power savings withruntime. A newly developed packing algorithm uses the resulting activities to min-imize leakage power dissipation by packing the logic blocks with similar or closeactivities together. By proposing an FPGA architecture that supports MTCMOSand developing a CAD tool that supports the new architecture, an average powersavings of 30% is achieved for a 90nm CMOS process while incurring a speed penaltyof less than 5%. This technique is further extended to provide a timing-sensitiveversion of the CAD flow to vary the speed penalty according to the criticality ofeach logic block.Secondly, a new technique for leakage power reduction in FPGAs based on theuse of input dependency is developed. Both subthreshold and gate leakage poweriiiare heavily dependent on the input state. In FPGAs, the effect of input dependencyis exacerbated due to the use of pass-transistor multiplexer logic, which can exhibitup to 50% variation in leakage power due to the input states. In this thesis, a newalgorithm is proposed that uses bit permutation to reduce subthreshold and gateleakage power dissipation in FPGAs. The bit permutation algorithm provides anaverage leakage power reduction of 40% while having less than 2% impact on theperformance and no penalty on the design area.Thirdly, an accurate probabilistic power model for FPGAs is developed to quan-tify the savings from the proposed leakage power reduction techniques. The pro-posed power model accounts for dynamic, short circuit, and leakage power (includ-ing both subthreshold and gate leakage power) dissipation in FPGAs. Moreover,the power model accounts for power due to glitches, which accounts for almost20% of the dynamic power dissipation in FPGAs. The use of probabilities in thepower model makes it more computationally efficient than the other FPGA powermodels in the literature that rely on long input sequence simulations. One of themain advantages of the proposed power model is the incorporation of spatial cor-relation while estimating the signal probability. Other probabilistic FPGA powermodels assume spatial independence among the design signals, thus overestimatingthe power calculations. In the proposed model, a probabilistic model is proposedfor spatial correlations among the design signals. Moreover, a different variation isproposed that manages to capture most of the spatial correlations with minimumimpact on runtime. Furthermore, the proposed power model accounts for the inputdependency of subthreshold and gate leakage power dissipation. By comparing theproposed power model to HSpice simulation, the estimated power is within 8% andis closer to HSpice simulations than other probabilistic FPGA power models by anaverage of 20%.ivAcknowledgementsI would like to express my sincere gratitude to my supervisors Prof. MohamedElmasry and Dr. Mohab Anis for their guidance and expertise. Without theirknowledge and support, this work would not have been possible. I would also liketo thank Prof. Farid Najm, Prof. Anthony Vannelli, Prof. Catherine Gebotys, andProf. John Vanderkooy for reviewing this work as well as their valuable commentsto make the thesis come out in this current form.I am also grateful to Prof. Andrew Kennings who first introduced me to FPGACAD design in the ECE647, which was one of the most interesting courses I at-tended during my study at Waterloo. I am thankful to Prof. James Barby, whoseguidelines in teaching and course management will always be in mind if I ever getthe chance to teach a course in the future.I have been fortunate to work with many wonderful people in the VLSI researchgroup in the University of Waterloo. I am thankful to all of them for their timeand ideas that made this work more productive and my time spent at Waterloomemorable. I always remember the funny as well as informative discussions I usedto have with some of my friends in the lab, including Ayman Hassan, MohamedAbu Rahma, and Mohamed Elsaid. During my PhD studies in the University ofWaterloo, I interacted with a wide group of interesting people that will always bemy friends, including, Mohamed El-Abd, Shady Hassan, and Hatem Elbehiry.I would like to thank Dr. Nizar Abdallah and Dr. Julien Dunoyer of Actel Corp.for their valuable discussion and support during my visit to Actel headquarters in2007.Moreover, I would like to express my deepest gratitude to my parents for goingthrough so much in supporting my academic choices, even though it meant beingaway from them. Finally, I am deeply thankful to my wife who joined and supportedme in the final and rough stages of this journey. I really appreciate her supportduring my defense exam.vContentsList of Tables xiList of Figures xiiList of Algorithms xvi1 Introduction 11.1 Motivation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 11.2 Thesis Contributions . . . . . . . . . . . . . . . . . . . . . . . . . . 21.3 Thesis Organization . . . . . . . . . . . . . . . . . . . . . . . . . . . 32 FPGA Overview: Architecture and CAD 42.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 42.2 FPGA Logic Resources Architecture . . . . . . . . . . . . . . . . . 52.2.1 Altera Stratix III Logic Resources . . . . . . . . . . . . . . . 62.2.2 Xilinx Virtex-5 Logic Resources . . . . . . . . . . . . . . . . 62.2.3 Actel ProASIC3/IGLOO Logic Resources . . . . . . . . . . 82.3 FPGA Routing Resources Architecture . . . . . . . . . . . . . . . . 82.4 CAD for FPGAs . . . . . . . . . . . . . . . . . . . . . . . . . . . . 92.4.1 Logic Synthesis . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.2 Packing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 102.4.3 Placement . . . . . . . . . . . . . . . . . . . . . . . . . . . . 112.4.4 Timing Analysis . . . . . . . . . . . . . . . . . . . . . . . . . 12vi2.4.5 Routing . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132.5 Versatile Place and Route (VPR) CAD Tool . . . . . . . . . . . . . 132.5.1 VPR Architectural Assumptions . . . . . . . . . . . . . . . . 142.5.1.1 VPR Logic Architecture . . . . . . . . . . . . . . . 142.5.1.2 VPR Routing Resources Architecture . . . . . . . . 152.5.2 Basic Logic Packing Algorithm: VPack . . . . . . . . . . . . 172.5.3 Timing-Driven Logic Block Packing: T-VPack . . . . . . . . 192.5.4 Placement: VPR . . . . . . . . . . . . . . . . . . . . . . . . 202.5.5 Routing: VPR . . . . . . . . . . . . . . . . . . . . . . . . . . 222.5.5.1 Routability-Driven Router . . . . . . . . . . . . . . 223 Leakage Power in Modern FPGAs 233.1 Dynamic Power Reduction Techniques in FPGAs . . . . . . . . . . 233.2 CMOS Technology Scaling Trends and Leakage Power in VLSI Circuits 243.3 CMOS Devices Leakage Mechanisms . . . . . . . . . . . . . . . . . 273.4 Current Situation of Leakage Power in Nanometer FPGAs . . . . . 283.5 Leakage Power Reduction Techniques in FPGAs . . . . . . . . . . . 293.5.1 Leakage Power Reduction in the Logic Blocks . . . . . . . . 293.5.2 Leakage Power Reduction in Routing Circuitry . . . . . . . . 313.6 Power Reduction Techniques in Commercial FPGAs . . . . . . . . . 333.6.1 Altera Stratix III Power Reduction Techniques . . . . . . . . 333.6.2 Xilinx Virtex-5 Power Reduction Techniques . . . . . . . . . 343.6.3 Actel IGLOO Power Reduction Techniques . . . . . . . . . . 344 Power Estimation in FPGAs 354.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 364.2 Power Estimation in VLSI: An Overview . . . . . . . . . . . . . . . 374.2.1 Simulation-Based Power Estimation Techniques . . . . . . . 374.2.2 Probabilistic-Based Power Estimation Techniques . . . . . . 39vii4.3 A Survey of FPGA Power Estimation Techniques . . . . . . . . . . 414.3.1 Commercial FPGA Power Estimation Techniques . . . . . . 444.3.1.1 Spreadsheet Power Estimation Tools . . . . . . . . 444.3.1.2 CAD Power Estimation Tools . . . . . . . . . . . . 454.4 Spatial Correlation and Signal Probabilities Calculations . . . . . . 454.5 Exploration Phase: Locating Spatial Correlation . . . . . . . . . . . 464.6 Proposed Signal Probabilities Calculation Algorithm Under SpatialCorrelation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 474.7 Power Calculations due to Glitches . . . . . . . . . . . . . . . . . . 514.8 Signal Probabilities and Power Dissipation . . . . . . . . . . . . . . 524.8.1 Dynamic Power Dissipation . . . . . . . . . . . . . . . . . . 534.8.2 Leakage Power Dissipation . . . . . . . . . . . . . . . . . . . 544.8.3 Gate Leakage Power Dissipation . . . . . . . . . . . . . . . . 564.9 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . 564.10 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 655 Leakage Power Reduction in FPGAs Using MTCMOS Techniques 665.1 Introduction . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 665.2 MTCMOS FPGA Architecture . . . . . . . . . . . . . . . . . . . . 695.3 Sleep Transistor Design and Discharge Current Processing . . . . . 725.3.1 Sleep Transistor Sizing . . . . . . . . . . . . . . . . . . . . . 725.3.2 Mutually Exclusive Discharge Current Processing . . . . . . 755.3.3 Logic-Based Discharge Current Processing . . . . . . . . . . 765.3.4 Topological Sorting and Discharge Current Addition . . . . 775.4 Activity Profile Generation . . . . . . . . . . . . . . . . . . . . . . . 805.4.1 Connection-based Activity Profile Generation Algorithm (CAP) 825.4.2 Logic-based Activity Profile (LAP) Generation . . . . . . . . 865.4.2.1 Activity Vectors . . . . . . . . . . . . . . . . . . . 865.4.2.2 Hamming Distance: A Measure of the CorrelationBetween Activity Profiles . . . . . . . . . . . . . . 88viii5.4.2.3 The LAP Algorithm Operation . . . . . . . . . . . 895.4.2.4 Reverse Logic Activity Profile (R-LAP) GenerationAlgorithm . . . . . . . . . . . . . . . . . . . . . . . 915.5 Activity Packing Algorithms . . . . . . . . . . . . . . . . . . . . . . 935.5.1 Activity T-VPack (AT-VPack) . . . . . . . . . . . . . . . . . 935.5.2 Force-based Activity T-VPack (FAT-VPack) . . . . . . . . . 955.5.3 Timing-Driven MTCMOS (T-MTCMOS) AT-VPack . . . . 965.6 Power Estimation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 975.7 Results and Discussions . . . . . . . . . . . . . . . . . . . . . . . . 985.7.1 Experimental Setup . . . . . . . . . . . . . . . . . . . . . . . 995.7.2 Algorithms Comparison . . . . . . . . . . . . . . . . . . . . 1005.7.3 Impact of Activity Packing on Performance . . . . . . . . . 1015.7.4 Leakage Savings Breakdown . . . . . . . . . . . . . . . . . . 1045.7.5 Impact of Utilization and ON Time on Leakage Savings . . . 1055.7.6 Impact of the Sleep Region Size . . . . . . . . . . . . . . . . 1075.7.7 Scalability of the Proposed Algorithms with Technology Scaling1075.8 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1086 Leakage Power Reduction in FPGAs Through Input Pin Reorder-ing 1096.1 Leakage Power and Input State Dependency in FPGAs . . . . . . . 1106.1.1 Subthreshold Leakage Current . . . . . . . . . . . . . . . . . 1106.1.1.1 Drain Induced Barrier Lowering (DIBL) . . . . . . 1116.1.1.2 Body Effect . . . . . . . . . . . . . . . . . . . . . . 1126.1.2 Gate Leakage . . . . . . . . . . . . . . . . . . . . . . . . . . 1136.1.3 Low-Leakage States in Pass-Transistor Multiplexers . . . . . 1136.1.4 Leakage Power in Inverters/Buffers . . . . . . . . . . . . . . 1156.2 Proposed Input Pin Reordering Algorithm . . . . . . . . . . . . . . 1156.2.1 Logic Pin Reordering (LPR) Algorithm . . . . . . . . . . . . 117ix6.2.1.1 Input Pins Padding . . . . . . . . . . . . . . . . . . 1176.2.1.2 Input Pins Swapping . . . . . . . . . . . . . . . . . 1176.2.1.3 Most Probable States . . . . . . . . . . . . . . . . 1196.2.1.4 Unutilized Logic Resources . . . . . . . . . . . . . 1206.2.2 Routing Switches Pin Reordering (RPR) Algorithm . . . . . 1216.2.2.1 Input Pins Padding . . . . . . . . . . . . . . . . . . 1216.2.2.2 Most Probable States . . . . . . . . . . . . . . . . 1216.2.2.3 Unutilized Routing Resources . . . . . . . . . . . . 1226.3 Experimental Results . . . . . . . . . . . . . . . . . . . . . . . . . . 1226.3.1 Pin Reordering and Performance . . . . . . . . . . . . . . . 1246.3.2 Pin Reordering and Technology Scaling . . . . . . . . . . . . 1266.4 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1267 Conclusions and Future Work 1297.1 Conclusions . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1297.2 Future Work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 130Bibliography 132xList of Tables2.1 VPR temperature update schedule [28]. . . . . . . . . . . . . . . . . 213.1 Constant field scaling of the CMOS process. . . . . . . . . . . . . . 263.2 FPGA leakage power for typical designs and design-dependent vari-ations [48]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 284.1 Relative error in the switching activity from the proposed algorithmwhen compared to [92]. . . . . . . . . . . . . . . . . . . . . . . . . . 584.2 Relative error in the switching activity from the proposed algorithmwhen compared to [92]. . . . . . . . . . . . . . . . . . . . . . . . . . 584.3 Small benchmark circuits. . . . . . . . . . . . . . . . . . . . . . . . 594.4 Percentage change in power estimation under spatial correlation whencompared to spatial independence. . . . . . . . . . . . . . . . . . . 625.1 Leakage power Savings for the different activity profile packing algo-rithms across several FPGA benchmarks. . . . . . . . . . . . . . . . 1006.1 Leakage current in a minimum-sized inverter. . . . . . . . . . . . . 1156.2 Leakage savings by the proposed pin reordering algorithm acrossseveral FPGA benchmarks. . . . . . . . . . . . . . . . . . . . . . . . 123xiList of Figures2.1 Modern FPGA fabric. . . . . . . . . . . . . . . . . . . . . . . . . . 52.2 Altera’s Stratix III ALM architecture [10]. . . . . . . . . . . . . . . 72.3 Xilinx’s Vertex-5 slice architecture [11]. . . . . . . . . . . . . . . . . 72.4 Actel’s ProASIC3/IGLOO VersaTile architecture [12]. . . . . . . . . 82.5 Routing resources in island-style FPGAs. . . . . . . . . . . . . . . . 92.6 A typical FPGA CAD flow. . . . . . . . . . . . . . . . . . . . . . . 102.7 An example of packing. . . . . . . . . . . . . . . . . . . . . . . . . . 112.8 Building blocks of SRAM programmable FPGAs used by VPR. . . 142.9 VPR BLE architecture. . . . . . . . . . . . . . . . . . . . . . . . . . 152.10 VPR logic cluster architecture. . . . . . . . . . . . . . . . . . . . . . 152.11 VPR FPGA routing architecture. chan width x = 1, chan width y= 1, chan width io = 0.5, io rat = 2, Fc,input = 3, Fc,output = 1, andFc,pad = 2. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 162.12 Switch topologies supported by VPR. . . . . . . . . . . . . . . . . . 172.13 Packing LUTs and registers into BLEs [28]. . . . . . . . . . . . . . 192.14 Adding a BLE to a cluster can decrease the number of used clusterinputs [28]. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 202.15 FPGA model assumed by the VPR placer. . . . . . . . . . . . . . . 213.1 Gate length scaling of CMOS technologies [1]. . . . . . . . . . . . . 253.2 Leakage power contribution to the total chip power [1]. . . . . . . . 263.3 Leakage current mechanisms of deep submicron devices [46]. . . . . 273.4 VDD programmable low-power FPGA resources [49]. . . . . . . . . . 30xii3.5 Programmable low-power routing switches [58]. . . . . . . . . . . . 324.1 A circuit that exhibits spatial correlation through reconvergent paths. 464.2 A graph representation of the circuit in Figure 4.1. . . . . . . . . . 474.3 A circuit that exhibits spatial correlation. . . . . . . . . . . . . . . 494.4 A 2:1 pass transistor logic multiplexer. . . . . . . . . . . . . . . . . 544.5 DIBL impact on subthreshold leakage in FPGA pass transistor devices. 554.6 Average relative error in estimating the signal probabilities underspatial correlation by varying the number of cycles considered. . . . 594.7 Percentage error in estimating the signal probabilities under spatialcorrelation when compared to HSpice versus the length of the inputsequence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 604.8 Percentage error in estimating the signal probabilities under spatialindependence when compared to HSpice versus the length of theinput sequence. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 614.9 Percentage error between power estimated with and without spatialcorrelation when compared to HSpice. . . . . . . . . . . . . . . . . . 614.10 Average percentage change in power dissipation to account for spatialcorrelation for different technology nodes. . . . . . . . . . . . . . . . 644.11 Average percentage change in leakage power dissipation with andwithout spatial correlation for different technology node. . . . . . . 644.12 Average percentage change in dynamic power dissipation with andwithout spatial correlation for different technology node. . . . . . . 654.13 Percentage change in power dissipation between spatial correlationand independence versus the cluster size. . . . . . . . . . . . . . . . 655.1 MTCMOS architecture. (a) General MTCMOS architecture, (b)Equivalent ST circuit in the active mode. . . . . . . . . . . . . . . . 675.2 FPGA CAD flowchart. (a) Conventional VPR flowchart. (b) Pro-posed CAD flowchart integrated in the VPR flow. . . . . . . . . . . 685.3 MTCMOS FPGA architecture. The logic blocks connected to onesleep transistor are called sleep region. . . . . . . . . . . . . . . . . 695.4 MTCMOS-based FPGA fabric with sleep transistors. . . . . . . . . 71xiii5.5 Sleep transistor implementations. (a) NMOS footer. (b) PMOSheader. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 715.6 Mutually exclusive discharge current processing. . . . . . . . . . . . 755.7 Mutually exclusive discharge current processing. . . . . . . . . . . . 765.8 Linear vector approximation of discharge current and logic-basedcurrent vectors summation. . . . . . . . . . . . . . . . . . . . . . . 775.9 Different types of sleep regions. . . . . . . . . . . . . . . . . . . . . 785.10 Steps of the current feasibility check for a combinational connectedsleep region. (a) A is selected to be deleted, (b) A is ordered in thefirst position and B and C are selected for deletion, (c) B and C areordered in the same position, (d) Final ordering, (e) Current vectorssummation . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 795.11 Steps of the current feasibility check for a sequential connected sleepregion. (a) Both A and B are selected for deletion, (b) A and B areordered on the same position, with B an unconnected node and C ismarked for deletion, (c) C is ordered in the next position, (d) Finalordering, (e) Current vectors summation. . . . . . . . . . . . . . . . 805.12 Leakage power savings vs the maximum activity region capacity. . . 845.13 Average activity region size across several benchmarks vs. δ. . . . . 855.14 CAP activity generation flow for maxCap = 4 and δ = 0.2 . . . . . 855.15 A circuit example. . . . . . . . . . . . . . . . . . . . . . . . . . . . 875.16 Speed penalty experienced in the different benchmarks due to theuse of sleep transistors. . . . . . . . . . . . . . . . . . . . . . . . . . 1025.17 ‘s298’ leakage savings vs maximum speed penalty for the R-LAP andT-MTCMOS combination. . . . . . . . . . . . . . . . . . . . . . . . 1035.18 ‘s298’ leakage savings vs minimum speed penalty for the R-LAP andT-MTCMOS combination. . . . . . . . . . . . . . . . . . . . . . . . 1035.19 Critical path distribution for timing-driven MTCMOS designs. . . . 1045.20 Leakage power savings breakdown. . . . . . . . . . . . . . . . . . . 1055.21 Percentage savings in power for different FPGA fabric utilizationsusing the combination of R-LAP and T-MTCMOS. . . . . . . . . . 106xiv5.22 Percentage savings in power for different utilizations and operationaltime using the combination of R-LAP and T-MTCMOS. . . . . . . 1065.23 Impact of the sleep region size on the leakage savings. . . . . . . . . 1075.24 Impact of technology scaling on power savings. . . . . . . . . . . . . 1086.1 DIBL effect in a 90nm CMOS process. . . . . . . . . . . . . . . . . 1126.2 DIBL impact on subthreshold leakage in FPGA pass-transistor devices.1126.3 Gate leakage dominant states in FPGA pass-transistor devices. . . . 1136.4 Total leakage dominant states in FPGA pass-transistor devices. . . 1146.5 Inputs to pass-transistors pairs. . . . . . . . . . . . . . . . . . . . . 1146.6 Gate leakage dominant states in FPGA pass-transistor devices. . . . 1166.7 VPR CAD flow with the proposed pin reordering algorithms. . . . . 1166.8 Input padding for logic blocks with inputs less than the maximum. 1186.9 Input pin swapping for logic blocks to minimize leakage power dissi-pation. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1196.10 Leakage savings breakdown in logic blocks. . . . . . . . . . . . . . . 1236.11 Leakage savings breakdown in the routing resources. . . . . . . . . . 1246.12 Performance penalty due to the proposed algorithm. . . . . . . . . . 1256.13 Leakage savings to avoid affecting the performance. . . . . . . . . . 1256.14 Trading leakage savings to reduce critical path delay in RCP. . . . . 1276.15 Leakage current vs. technology. . . . . . . . . . . . . . . . . . . . . 1286.16 Total leakage dominant states in FPGA pass transistor devices. . . 128xvList of Algorithms2.1 SA generic placer pseudocode. . . . . . . . . . . . . . . . . . . . . . 122.2 VPack pseudocode [28]. . . . . . . . . . . . . . . . . . . . . . . . . . 184.1 The exploration phase pseudocode used to identify reconvergent pathsin a circuit. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 484.2 Probabilities calculation under spatial correlation algorithm. . . . . 505.1 Pseudocode of the proposed logic-based discharge current processingalgorithm. . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 815.2 Pseudocode of the proposed CAP algorithm. . . . . . . . . . . . . . 865.3 Pseudocode of LAP. . . . . . . . . . . . . . . . . . . . . . . . . . . 915.4 Pseudocode of the proposed R-LAP. . . . . . . . . . . . . . . . . . . 935.5 Pseudocode for the AT-VPACK algorithm. . . . . . . . . . . . . . . 95xviChapter 1Introduction1.1 MotivationFueled by the increase in functionality and size of modern Field ProgrammableGate Arrays (FPGAs) , the market for FPGAs has witnessed a notable expansionin the past few years. This increase in demand has pushed FPGA vendors to designmodern FPGAs using state-of-the-art CMOS technologies. Consequently, modernFPGAs suffer greatly from the deep submicron issues that affected the ASIC indus-try earlier along the technology scaling road. The biggest deep submicron challengethat hurdles further expansions of the use of FPGAs in the VLSI industry is leak-age power dissipation. In order for FPGAs to continue competing with the ASICindustry, FPGA vendors must tackle this issue using architectural and/or CADtechniques.The continuous scaling of the CMOS process has attracted FPGA vendors tointegrate more and more devices on the same chip to increase the chip function-ality. As a result, the power dissipation of modern FPGAs increased significantly.Much of this increase in power dissipation is attributed to the increase in leakagepower dissipation which is expected to exceed 50% of the FPGA power dissipationas modern FPGAs start using the 65nm CMOS process [1]. In addition, the exces-sive scaling of the MOS gate oxide thickness tox resulted in a significant increase inthe gate oxide tunneling current, thus exacerbating the leakage problem. In recentexperiments, it was found that both the subthreshold and gate leakage power dis-sipation increase by about 5X and 30X, respectively, across successive technologygenerations [2].Traditionally, FPGA vendors were concerned with performance and area opti-1mization to reduce the gap between FPGAs and ASIC designs. In the past fewyears, a shift in the industry towards power optimization has been witnessed asnew power efficient FPGAs are introduced to the market. However, these powerefficient FPGAs are mainly concerned with dynamic power reduction. With theexpected dominance of leakage power dissipation, FPGA vendors are starting tomove towards developing low-leakage FPGA devices.1.2 Thesis ContributionsThis thesis will provide several CAD and architectural modifications to FPGAdesigns to reduce the impact of leakage power dissipation on modern FPGAs.Leakage reduction techniques have been applied in ASIC designs for the past fewyears. One of the most successful techniques is the use of Multi-threshold CMOS(MTCMOS). MTCMOS employs a high threshold voltage Vth (HVT) device, calledsleep transistor (ST), in a circuit that is made of low-Vth devices (LVT). Hence,the design benefits from the high performance of the LVT devices and the reducedleakage power dissipation of the HVT device. In this thesis, MTCMOS techniqueswill be employed in FPGAs for leakage power reduction. Moreover, this architecturewill enable shutting down the unused or idle parts of the FPGA, thus reducing theirstandby leakage significantly. Employing this technique in FPGAs requires severalchanges to the FPGA architecture, including the placement of the sleep transistors;location and connections to the sleep transistors, as well as the CAD design flow.The packing and placement stages of the CAD flow will be changed to reflect theaddition of the sleep transistor and allow the possibility of turning OFF the idleparts of the FPGA. Furthermore, a new step is added in the CAD flow to identifythe logic blocks that share common idleness periods so they can be collectivelyturned OFF during their idle periods.Leakage power is characterized by being significantly state dependent. Depend-ing on the input vector, the leakage power dissipation can vary by about 50%. Inthis thesis, a new methodology for leakage power optimization in FPGAs is pro-posed that depends on the state dependency of leakage power. By varying theorder of the inputs to the logic blocks, the logic block leakage power is noticeablyreduced. Moreover, the algorithm changes the deign configuration to put the FPGAcomponents in the lowest leakage power mode.In order to measure the leakage power savings from the proposed power op-timization techniques, a newly proposed accurate power model for FPGAs is ex-2plained in this thesis. The power model takes into consideration the spatial corre-lation among the design signals. In addition, the power model developed is veryflexible in terms of being able to estimate power dissipation in different FPGAarchitectures.1.3 Thesis OrganizationThis thesis is organized as follows: an overview of the architecture; logic and rout-ing architecture, and CAD flow of FPGAs is presented in Chapter 2. Chapter 3discusses the current status of leakage power dissipation in modern FPGAs as wellas some of the methods proposed in the literature to address power dissipation inFPGAs. Chapter 4 presents the newly proposed accurate power modeling tech-nique for FPGAs. The proposed MTCMOS implementation of FPGAs is discussedin Chapter 5. The input reordering leakage power minimization methodology isproposed in Chapter 6. Finally, this thesis is concluded in Chapter 7 and possiblefuture work is discussed.3Chapter 2FPGA Overview: Architectureand CAD2.1 IntroductionFueled by the increase in the time-to-market pressures, the rise in ASIC maskand development costs, and increase in the Field Programmable Gate Arrays (FP-GAs) performance and system-level features, more and more traditionally ASICdesigners are migrating their designs to programmable logic devices. Moreover,programmable logic devices progressed both in terms of resources and performance.The latest FPGAs have come to provide platform solutions that are easily customiz-able for system connectivity, Digital Signal Processing (DSP), and/or data process-ing applications. These platform building tools accelerate the time-to-market byautomating the system definition and integration phases of the System on Pro-grammable Chip (SoPC) development.The market of programmable logic devices is dominated by two main prod-ucts; FPGAs and Complex Programmable Logic Devices (CPLDs). FPGAs mostlyemploy a look-up table approach to implement logic functions, while CPLDs usesum-of-products for logic implementation. Recently, FPGA vendors provided acomprehensive alternative to FPGAs for large volume demands called structuredASICs [3, 4]. Structured ASICs offer a complete solution from prototype to high-volume production, and maintain the powerful features and high-performance ar-chitecture of their equivalent FPGAs with the programmability removed. Struc-tured ASIC solutions not only provide performance improvement, but also resultin significant high-volume cost reduction over FPGAs.4FPGAs consist of programmable logic resources embedded in a sea of pro-grammable interconnects. The programmable logic resources can be configuredto implement any logic function, while the interconnects provide the flexibility toconnect any signal in the design to any logic resource. The programming technol-ogy for the logic and interconnect resources can be Static Random Access Memory(SRAM), flash memory [5], or antifuse [6, 7]. SRAM-based FPGAs offer in-circuitreconfigurability at the expense of being volatile, while antifuse are write-once de-vices. Flash-based FPGAs provide an intermediate alternative by providing recon-figurability as well as non-volatility. The most popular programming technology instate-of-the-art FPGAs is SRAM.Traditionally, FPGAs consist of input/output pads, logic resources, and routingresources. However, state-of-the-art FPGAs usually include embedded memory,DSP blocks, Phase-Locked Loops (PLLs), embedded processors, and other specialfeature blocks, as shown in Figure 2.1. These features allowed FPGAs to be anattractive alternative for some SoPC designs. The next Sections shed light on someof the available commercial FPGA architectures and FPGA CAD flow.I/O PadsLogic ResourcesRouting ResourcesDSPBlocksMemory BlocksSpecial FeatureBlocksFigure 2.1: Modern FPGA fabric.2.2 FPGA Logic Resources ArchitectureThe logic blocks in FPGAs are responsible for implementing the functionalityneeded by each application. Increasing the functional capability of the logic blocks5increases the number of logic functions that can be packed into it. Moreover, in-creasing the size of logic blocks, i.e., increasing the number of inputs to each logicblock, increases the number of logic functions performed by each logic block aswell as improving the area/delay performance of the logic block [8]. However, thiscomes on the expense of wasted resources because not all of the blocks will have allof their inputs fully utilized.Most commercial FPGAs employ look-up tables (LUTs) to implement the logicblocks. A k-input LUT consists of 2k configuration bits in which the required truthtable is programmed during the configuration stage. The almost standard numberof inputs for LUTs is four, which was proven optimum for area and delay objectives[9]. However, this number can vary depending on the targeted application by thevendor. Moreover, modern FPGAs utilize a hierarchial architecture where everygroup of basic logic blocks are grouped together into a bigger logic structure, logiccluster. The remaining of this Section describes the programmable logic resourcesin three of the most popular commercial FPGAs.2.2.1 Altera Stratix III Logic ResourcesThe logic blocks in Altera’s Stratix III are called Adaptive Logic Modules (ALMs).An 8-input ALM contains a variety of LUT-based resources that can be dividedbetween two adaptive LUTs [10]. Being adaptive, ALMs can perform the con-ventional 4-input LUT operations as well as implementing any function of up to6-inputs and some 7-input functions. Besides the adaptive LUTs, ALMs containtwo programmable registers, two dedicated full adders, a carry chain, a shared arith-metic chain, and a register chain. Using these components, ALMs can efficientlyperform arithmetic and shift operations. A detailed view of an ALM is shown inFigure 2.2. Every eight ALMs are grouped together to form a Logic Array Block(LAB).2.2.2 Xilinx Virtex-5 Logic ResourcesThe slice is the basic logic resource in Xilinx Virtex-5 FPGAs. Slices consist offour LUTs, wide function multiplexers, and carry logic [11]. Figure 2.3 showsthe architecture of a typical Virtex-5 slice. The slices employ four 6-LUTs that arecapable of performing any 6-input logic function. Functions with up to 8-inputs canbe implemented using multiplexers to combine the output of two LUTs. Every twointerconnected slices are grouped together in a Configurable Logic Block (CLB) [11].6CLRQDCLRQDreg_chain_in labclkreg_chain_outadder0adder16-input LUT6-input LUTCombinational ALUT0Combinational ALUT1carry_outshared_arith_outTo general or local routingTo general or local routingTo general or local routingTo general or local routingcarry_inshared_arith_indataf1dataedataddatacdatabdataadatae0dataf0Figure 2.2: Altera’s Stratix III ALM architecture [10].Figure 2.3: Xilinx’s Vertex-5 slice architecture [11].72.2.3 Actel ProASIC3/IGLOO Logic ResourcesActel ProASIC3/IGLOO FPGAs employ a flash-based architecture, instead of theconventional SRAM-based FPGAs used by both Altera and Xilinx, to store theconfiguration bits. The flash architecture provides the FPGAs with both reconfig-urability and non-volatility. The ProASIC3/IGLOO FPGAs employ the VersaTile3-input logic block that can implement any 3-input logic function as well as se-quential functionality, as shown in Figure 2.4 [12]. Furthermore, the hierarchalarchitecture is not employed in the ProASIC3/IGLOO FPGAs and the output ofeach VersaTile can be directly routed to either the fast local lines or long routingresources. Another interesting characteristic of the VersaTile is that it does notadopt the conventional LUT architecture in FPGAs, as shown in Figure 2.4.CLKX2CLR/ENABLEX1CLRXCData X3 F2YLFigure 2.4: Actel’s ProASIC3/IGLOO VersaTile architecture [12].2.3 FPGA Routing Resources ArchitectureRouting resources in FPGAs can be divided into two components; segmented localrouting and dedicated routing . Segmented local routing is used to provide con-nection among the logic blocks. As depicted in Figure 2.5, the segmented wiresare prefabricated in channels to provide programmable connections between switchblocks, connection blocks, and logic blocks. The number of wires in one channel isusually denoted by W [13].8LogicBlockProgrammable Switch BlockProgrammable Connection BlockLong WireFigure 2.5: Routing resources in island-style FPGAs.The I/O of the logic blocks are dynamically connected to the segmented routingchannels on all four sides using connection blocks . The number of wires in eachchannel to which a logic block pin can connect to is called the connection blockflexibility Fc. In addition, the switch blocks provide programmable connectivitybetween the horizontal and vertical wires. The switch block flexibility Fs is definedas the number of wires to which each incoming wire can connect to in a switchblock. The segment length of a certain wire segment is defined as the number oflogic blocks spanned by the routing wire. Modern FPGAs use a combination ofwires of different segment lengths to achieve the optimum performance in terms ofroutability, delay, or both.Dedicated routing is used for global signals that fan out to a large numberof logic blocks, e.g., clock and reset, thus providing low-skew. Moreover, somecommercial FPGAs employ PLLs and Delay-Locked Loops (DLLs) for further skewreduction. Modern FPGAs have the flexibility to provide different clock domainsinside the FPGA to enable asynchronous designs.2.4 CAD for FPGAsFPGAs are implemented using a huge number of programmable switches that areused to implement a certain logic function. The CAD tools of FPGAs transformthe design, entered either as a schematic or using a hardware description language,9to a stream of ‘1’s and ‘0’s that program the FPGA during the configuration time.The flow chart in Figure 2.6 shows the different steps involved in the CAD flow fora typical FPGA design.Packing PlacementRoutingCircuit descriptionLogic SynthesisFPGA configuration fileFigure 2.6: A typical FPGA CAD flow.2.4.1 Logic SynthesisIn the synthesis phase, the circuit description is converted to a netlist of basic logicgates. This phase is usually divided into two different stages; logic optimizationand technology mapping [14–17].Logic optimization is a technology-independent stage that involves simplifyingthe logic function of the design without the use of any technology information. Anyredundant logic is removed at this stage. The optimized user circuit is then mappedinto LUTs and flip-flops in the technology mapping stage, where each k-boundedlogic function in the circuit is mapped into a k-LUT. This step resolves to findinga set of k-feasible cuts that include all the nodes in the circuit in such a way tominimize the delay, area, and/or power dissipation of the final implementation.The process of technology mapping is often treated as a covering problem.2.4.2 PackingThe packing phase converts the netlist of LUTs and flip-flops into a netlist of logicblocks, as shown in Figure 2.7. The input netlist is converted into clusters of10logic blocks that can be mapped into the physical logic blocks of the FPGA. Mostpacking algorithms minimize the number of resulting logic blocks, the number ofconnections between them, and/or the delay along the critical path. The packingalgorithm has to consider the physical limitations of the actual logic blocks of theFPGA in terms of the maximum number of LUTs in a logic block and the numberof distinct input signals and clocks a logic block has.ECBDAEEBACFigure 2.7: An example of packing.Packing algorithms can be categorized as either bottom-up [14, 18–20] or top-down [21,22]. Bottom-up packing algorithms build each cluster individually arounda seed LUT until the cluster is full. However, top-down packing approaches parti-tion the LUTs into clusters by successive circuit subdivision. Bottom-up algorithmsare much faster and simpler than top-down approaches because they only considerlocal connections. However, this comes at the expense of solution quality.2.4.3 PlacementIn the placement phase, the packed logic blocks are distributed among the phys-ical logic blocks in the FPGA fabric. Placement algorithms try to minimize thedelay along the critical path and enhance the resulting circuit routability. Avail-able placement algorithms can be classified into three categories; min-cut [23, 24],analytic [25, 26], and simulated annealing [27–29] based algorithms. Most of thecommercial placement tools for FPGAs employ simulated annealing-based algo-rithms because of their flexibility to adapt to a wide variety of optimization goals.11Simulated annealing (SA) placement tools depend on the SA algorithm, whichis derived from the annealing process used to cool molten metals [30]. Initially, arandom initial placement for all the logic blocks is generated. Afterwards, pairs oflogic blocks are selected at random as candidates for swapping to improve the costfunction. If the swap results in a decrease in the cost function, it is directly allowed,otherwise, it is only allowed with a probability that decreases as the algorithmprogresses, thus allowing less worsening swaps after every iteration. A pseudocodefor the SA placer is listed in Algorithm 2.1.Algorithm 2.1 SA generic placer pseudocode.S = RandomPlacement()T = InitialTemperature()while ExitCriterion() == False do/* Outer loop */while InnerLoopCriterion () == False do/* Inner loop */Snew = GenerateViaMove(S)∆C = Cost(Snew) - Cost(S)r = random(0,1)if r < e−∆C/T thenS = Snewend ifend whileT = UpdateTemp()end while2.4.4 Timing AnalysisTiming analysis [31] is used to guide placement and routing CAD tools in FPGAsto: (1) determine the speed of the placed and routed circuit and (2) estimate theslack of each source-sink connection during routing to identify the critical paths.Timing analysis is usually performed on a directed graph representing the circuit,where the nodes represent LUTs or registers and the edges represent connections.The minimum required clock period of the circuit can be determined by abreadth first search through the graph, starting from the primary inputs, to findthe arrival time at node i using the following relationTarrival(i) = max∀j∈fanin(i){Tarrival(j) + delay(j, i)} , (2.1)12where delay(j, i) is the delay on the edge between j and i. The required time atnode i is calculated by a breadth-first search of the graph, starting from the primaryoutputs, and using the following relationTrequired(i) = min∀j∈fanout(i){Trequired(j) + delay(i, j)} . (2.2)Afterwards, the slack on the connection between node i and j is calculated asslack(i, j) = Trequired(j)− Tarrival(i)− delay(i, j) . (2.3)Connections with a zero slack are critical connections, while those with a positiveslack are non-critical ones that can be routed using longer routes.2.4.5 RoutingThe routing phase assigns the available routing resources in the FPGA to the dif-ferent connections between the logic blocks in the placed design [28]. The objectiveof a typical routing algorithm is to minimize the delay along the critical path andavoid congestions in the FPGA routing resources. Generally, routing algorithmscan be classified into global routers and detailed routers . Global routers consideronly the circuit architecture without paying attention to the number and type ofwires available, while detailed routers assign the connections to specific wires in theFPGA.2.5 Versatile Place and Route (VPR) CAD ToolThe CAD flow used in this thesis is based on the Versatile Place and Route (VPR)CAD tool. VPR is a popular academic placement and routing tool for FPGAs [28].Moreover, VPR is the core for Altera’s Modeling Toolkit (FMT) CAD tool [32,33].VPR is usually used in conjunction with T-VPack [18, 27], a timing-driven logicblock packing algorithm. VPR consists of two main parts; a placer and routerand an area and delay model. These two components interact together to findout the optimum placement and routing that satisfies a set of conditions. ThisSection describes the FPGA architecture supported by VPR as well as giving aquick overview about the tool flow.132.5.1 VPR Architectural AssumptionsVPR assumes an SRAM-based architecture, where SRAM cells hold the configura-tion bits for all the pass-transistors multiplexers and tri-state buffers in the FPGAin both logic and routing resources, as shown in Figure 2.8(a). The SRAMs used arethe six-transistor SRAM cell made of minimum size transistors, as shown in Figure2.8(b). Moreover, an island-style FPGA is assumed by VPR, where the logic clus-ters are surrounded by routing tracks from all sides. VPR uses an architecture fileto describe the underlying FPGA architecture used. The architecture file containsinformation about the logic block size, wire segment length, connection topologies,and other information used by VPR. The use of the architecture file allows VPRto work on a wide range of FPGA architectures. However, there are some generalarchitectural assumptions made by VPR which are discussed in this Section.SRAM SRAM(a) Programmable switches andtri-state buffers in VPRFPGA architecture.VDDLoad linesfor loading the values during configurationQ QProgram lineTo enable configuration(b) Six-transistor SRAM circuit.Figure 2.8: Building blocks of SRAM programmable FPGAs used by VPR.2.5.1.1 VPR Logic ArchitectureVPR targets the hierarchal or cluster-based logic architecture, where every N ofthe smallest logic element, called Basic Logic Element (BLE), are grouped togetherto a form a Cluster of Logic Blocks . Each BLE consists of a k-LUT, a D flip-flop(DFF), and a 2:1 multiplexer (MUX), as shown in Figure 2.9. Such configurationallows both the registered and unregistered versions of the output to be readily14available. Local routing resources are used to connect the BLEs inside each logiccluster to each other and to the inputs/outputs of the logic cluster, as shown inFigure 2.10. As noticed in Figure 2.10, not all of the BLE inputs are accessiblefrom outside. However, any of the BLEs inputs can be connected to any of theBLEs outputs or any of the external inputs.LUT DFF2:1 MUX...Figure 2.9: VPR BLE architecture.BLE (1)BLE (1)......Output 1Output Nk-inputsI-inputs...ClockFigure 2.10: VPR logic cluster architecture.A logic cluster is defined in the architecture file by four main parameters: (1)the size of its LUTs k, (2) the number of BLEs in the cluster N , (3) the numberof external inputs to the cluster I, and (4) the number of external clock inputsMclk. It should be noted that VPR assumes minimum-sized transistors are used toimplement the LUTs, as a result, the capacitances of these transistors are ignored.However, VPR accounts for the capacitance of the internal routing tracks withinthe logic cluster.2.5.1.2 VPR Routing Resources ArchitectureVPR divides the routing resources characterization into three categories: channel,switch block, and wire parameters. The channel information specifies the channel15width and the connections between between the IO pads and logic blocks from oneside and the routing tracks from the other side. The channel width parametersinclude the width of horizontal (chan width x ) and vertical (chan width y) routingchannels, the width of the IO channel (chan width io), and the number of IO padsthat fit in one row or column of logic clusters (io rat). The connections betweenthe routing tracks and either the logic blocks or IO pads are defined by the numberof tracks connected to each logic block input (Fc,input) and output (Fc,output) andthe number of tracks connected to each IO pad (Fc,pad). As an example, Figure2.11 shows a high-level view of a sample VPR FPGA routing model and the valuesof the parameter used to describe the channel.LogicClustersI/OPadsRoutingTracksLogic ClusterVertical ChannelHorizontal ChannelIO ChannelSwitch BlockConnections between the tracks and logic block input pinConnections between tracks inside a switch blockConnections between the tracks and logic block ouput pinConnections between the IO pads and the tracksFigure 2.11: VPR FPGA routing architecture. chan width x = 1, chan width y =1, chan width io = 0.5, io rat = 2, Fc,input = 3, Fc,output = 1, and Fc,pad = 2.Switch blocks are used to provide programmable connectivity between the hor-izontal and vertical routing tracks, as shown in Figure 2.11. VPR characterizesswitch blocks by their resistance (R), input capacitance (Cin), output capaci-tance (Cout), intrinsic delay (Tdel), connection flexibility (Fs), switch type (whetherbuffered or not), and the switch block topology. The connection flexibility of aswitch is defined as the number of connections available for each pin to other pins onthe other sides of the switch. Figure 2.8(a) shows the unbuffered and buffered ver-sions of the switch blocks supported by VPR. Four different topologies of switchescan be used within VPR: Disjoint [34], Universal [35], Wilton [36], and Imran [37],16as shown in Figure 2.12.0 31 20 31 203120312(a) Disjoint switchblock.0 31 20 31 203120312(b) Universalswitch block.0 31 20 31 203120312(c) Wilton switchblock.0 31 20 31 203120312(d) Imran switchblock.Figure 2.12: Switch topologies supported by VPR.Finally, VPR describes wire segments by: the usage frequency of the segment inthe FPGA (segment frequency), the number of logic clusters spanned by the wire(segment length), the resistance (Rmetal) and capacitance (Cmetal) per unit length,the switch type that connects the wire and logic clusters (opin switch), the switchtype that connects the wire with other wires (wire switch).2.5.2 Basic Logic Packing Algorithm: VPackVPack is a logic packing algorithm that converts an input netlist of LUTs andregisters into a netlist of logic clusters. The packing is done in a hierarchial mannerin two stages: packing LUTs and registers into BLEs and packing a group of N ,or less, BLEs into logic clusters. The pseudocode for VPack is listed in Algorithm2.2.The first stage of VPack is a pattern matching algorithm that packs a registerand a LUT into one BLE when the output of the LUT fans out to only one register,as shown in Figure 2.13. The second phase packs the BLEs into logic blocks toachieve two objectives: (1) fill the logic clusters to their full capacity N and (2)minimize the number of inputs to each cluster. These two objectives originate fromthe two main goals of packing: area reduction and improving routability. Packingstarts by putting BLEs into the current cluster sequentially in a greedy mannerwhile satisfying the following hard constrains:1. the number of BLEs must be less than or equal to the cluster size N ,2. the number of externally generated signals, and used inside the cluster, mustbe less than or equal to the number of inputs to the cluster I,17Algorithm 2.2 VPack pseudocode [28].Let: UnclusteredBLEs be the set of BLEs not contained in any cluster- C be the set of BLEs in the current cluster- LogicClusters be the set of clusters (where each cluster is a set of BLEs)UnclusteredBLEs = PatternMatchToBLEs (LUTs, Registers)LogicClusters = NULLwhile UnclusteredBLEs != NULL do/* More BLEs to cluster */C = GetBLEwithMostUsedInputs (UnclusteredBLEs)while |C| < N do/* Cluster is not full */BestBLE = MaxAttractionLegalBLE (C, UnclusteredBLEs)if BestBLE == NULL then/* No BLE can be added to cluster */breakend ifUnclusteredBLEs = UnclusteredBLEs - BestBLEC = C ∪ BestBLEend whileif |C| < N then/* Cluster not full — try hill-climbing */while |C| < N doBestBLE = MINClusterInputIncreaseBLE (C, UnclusteredBLEs)C = C ∪ BestBLEUnclusteredBLEs = UnclusteredBLEs - BestBLEend whileif ClusterIsIllegal (C) thenRestoreToLastLegalState (C, UnclusteredBLEs)end ifend ifLogicClusters = LogicClusters ∪ Cend while3. the number of distinct clock signals needed by the cluster must be less thanor equal to the number of clock inputs Mclk.A seed BLE is selected for each cluster such that it has the maximum number ofinputs among the unclustered BLEs. Other unclustered BLEs B are attracted to18LUTReg.(a)LUT and register packinginto one BLELUTReg.LUT(b) LUT and register packing into two BLEsFigure 2.13: Packing LUTs and registers into BLEs [28].the cluster C in such a way as to maximize the attraction() objective functionAttraction(B) = |Nets(B) ∩NetsC| , (2.4)where Nets(x) are the nets connected to BLE (or cluster) x. This process continuesuntil the cluster is filled to its maximum capacity N .If the cluster does not reach its maximum capacity, but the number of inputsused by the BLEs inside it reaches I, a hill-climbing stage is invoked. In this stage,unclustered BLEs are added to the cluster in such a way to minimize the increasein the number of inputs to the cluster, an example of that is depicted in Figure2.14. This is achieved by minimizing the following cost function∆cluster inputs(B) = |Fanin(B)| − |Nets(B) ∩Nets(C)| . (2.5)It is worth mentioning that the hill-climbing stage allows violating the number ofinputs constraint while executing, but does not permit violating the clock inputsconstraint. The hill-climbing phase terminates when the cluster size reaches N . Ifthe cluster is infeasible, i.e., its inputs are more than I, the algorithm retracts tothe last feasible cluster. Afterwards, VPack selects a new seed BLE and constructsa new cluster.2.5.3 Timing-Driven Logic Block Packing: T-VPackT-Vpack [18, 27] is a modified version of the VPack algorithm that attempts tominimize the number of inter-cluster connections along the critical path, besidespacking the clusters to their maximum capacity. This achieves speed up along thecritical path as local interconnects (intra-cluster connections) are faster than inter-cluster interconnects. T-VPack employs a timing analyzer to calculate the slack19BLE BLEa b cd eBLEa bcBLE BLEa bd eBLEbcAdd another BLEFigure 2.14: Adding a BLE to a cluster can decrease the number of used clusterinputs [28].along the connections in the design and identify the critical path(s). The criticalitymeasure of a connection is calculated asConnectionCriticality(i) = 1− slack(i)MaxSlack, (2.6)where MaxSlack is the largest slack in the circuit.In T-VPack, the BLE with the highest criticality, i.e., the BLE connected tothe nets with the highest ConnectionCriticality, is selected as the seed BLE forthe cluster. Afterwards, BLEs are attracted to the cluster to maximize a modifiedversion of the Attraction() function in Eq. (2.4), given byAttraction(B) = λ× Criticality(B) + (1− λ)× Nets(B) ∩Nets(C)MaxNets, (2.7)where MaxNets is and λ is Criticality(B)2.5.4 Placement: VPRVPR models that the FPGA as a block array of logic clusters bounded by routingtracks, as shown in Figure 2.15. Simulated Annealing (SA) is used as the opti-mization algorithm for placement in VPR using an adaptive annealing schedule toadapt to the current placement at any time instant.The initial temperature is selected from the basic features of the circuit. Assumethat the total number of logic clusters in the design is Nclusters. After the initialrandom placement is evaluated, Nclusters pairwise swaps are performed and theinitial temperature is calculated as 20 times the standard deviation of the cost ofthe different Nclusters combinations evaluated. Moreover, the number of inner moves20LogicClustersI/OPadsRoutingChannelsFigure 2.15: FPGA model assumed by the VPR placer.performed at each temperature is evaluated asMovesPerTemperature = InnerNum×N4/3clusters , (2.8)where InnerNum is a constant and usually set to 10.Another feature of the adaptive SA algorithm used in VPR is the way thetemperature is updated. In conventional SA, almost all of the moves are accepted athigh temperatures, while at low temperatures, only improving moves are accepted.In the adaptive SA [28], the cooling scheme tries to prolong the time spent inthese cost improving temperatures (medium and low temperatures) at the expenseof possibly cost worsening temperatures (high temperatures) using the followingtemperature update relationshipTnew = γ × Told , (2.9)where γ is evaluated with respect to the percentage of moves accepted (α), accordingto Table 2.1.Table 2.1: VPR temperature update schedule [28].α γ0.96 < α 0.50.8 < α ≤ 0.96 0.90.15 < α ≤ 0.8 0.95α ≤ 0.15 0.8212.5.5 Routing: VPRVPR incorporates two different routing algorithms; a routability-driven router anda timing-driven router.2.5.5.1 Routability-Driven RouterThe VPR routability-driven router is based on the Pathfinder algorithm [38]. ThePathfinder algorithm repeatedly rips-up and re-routes every net in the circuit dur-ing each routing iteration until all congestions are removed. Initially, all nets arerouted to minimize the delay, even if this results in congestion. Afterwards, routingiterations are applied to overused routing resources to resolve such congestions. InVPR, the cost of using a routing resource n when it is reached by connecting it torouting resource m is given byCost(n) = b(n)× h(n)× p(n) + BendCost(n,m) , (2.10)where b(n), h(n), and p(n) are the base cost, historical congestion, and presentcongestion, respectively. b(n) is set to the delay of n, delay(n). h(n) is incrementedafter each routing iteration in which n is overused. p(n) is set to ‘1’ if routing thecurrent net through n will not result in congestion and increases with the amountof overuse of n. The BendCost(n,m) is used to penalize bends in global routing toimprove the detailed routability.2.5.5.1.1 Timing-Driven RouterThe timing-driven router in VPR is based on the Pathfinder, but timing informationis considered during every routing iteration. Elmore delay models are used tocalculate the delays, and hence, timing information in the circuit. In order toinclude timing information, the cost of including a node n in a net’s routing isgiven byCost(n) = Crit(i, j)× delay(n, topology) + [1− Crit(i, j)]× b(n)× h(n)× p(n) ,(2.11)where a connection criticality Crit(i, j) is given byCrit(i, j) = max{[MaxCrit− slack(i, j)Dmax]η, 0}, (2.12)where Dmax is the critical path delay and η and MaxCrit are parameters thatcontrol how a connection’s slack impacts the congestion-delay tradeoff in the costfunction.22Chapter 3Leakage Power in Modern FPGAsThe tremendous growth of the semiconductor industry in the past few decades isfueled by the aggressive scaling of the semiconductor technology following Moore’sLaw. As a result, the industry witnessed an exponential increase in the chip speedand functional density with a significant decrease in power dissipation and cost perfunction [39]. However, as the CMOS devices enter the nanometer regime, leakagecurrent is becoming one of the main hurdling blocks to Moore’s law. According toMoore himself, the key challenge for continuing process scaling in the nanometerera is leakage power reduction [40]. Thus, circuit designers and CAD engineershave to work hand in hand with device designers to deliver high-performance andlow-power systems for future CMOS devices.In this Chapter, the leakage power problem is discussed in the VLSI industryin general and in FPGAs in particular. Moreover, the proposed techniques in theliterature to combat both dynamic and leakage power dissipation in FPGAs arepresented and their advantages and disadvantages are discussed.3.1 Dynamic Power Reduction Techniques in FP-GAsMost of the low-power design techniques proposed for FPGAs targeted dynamicpower dissipation. These works were motivated by the fact that dynamic powerdissipation constituted most of the power dissipation in old CMOS technologies,180nm and before. In [41], a hierarchal interconnect architecture is proposed toreduce dynamic power dissipation in the interconnect multiplexers. The basic idea23behind this work was to reduce the capacitance of the interconnects by reducingthe number of wire segments connected to each switch box. Moreover, the authorsproposed the use of lower supply voltage to reduce the total power dissipation.A low swing signalling scheme was proposed in [42] for FPGAs for total powerreduction. The authors used level converters at both sides of long interconnectsthat reduces the voltage of the transmitted signal. Moreover, the authors proposeda symmetric mesh architecture for the FPGA interconnects that reduces the totalwire capacitance.An efficient power-aware CAD flow was implemented in [43]. The authors in-troduced power figures of merits to the cost function at every level of the FPGACAD design flow. The main idea of the work is to minimize the capacitance ofsignals with high switching activity. In the technology mapping phase, the au-thors include the switching activity of the feasible cuts evaluated during mapping.The clustering phase tries to cluster the logic blocks connected to a high activitynet together to reduce the net capacitance. Similarly, during the placement stage,clusters connected to high activity nets are placed close to each other.A power-aware technology mapping methodology for FPGAs was proposed in[44] that aims to keep nets with high switching activity out of the FPGA routingnetwork and takes an activity-conscious approach to logic replication. As result,the wire capacitance of high activity nets is reduced significantly.A methodology to reduce glitching power in FPGAs was proposed in [45] thatrelies on adding extra programmable delays to balance path delays. By adding extradelays to nets with positive slacks, the authors managed to equalize the delays atmost of the inputs to each logic block in the design. As a result, glitching power isreduced to almost zero.3.2 CMOS Technology Scaling Trends and Leak-age Power in VLSI CircuitsThe main driving forces that govern the CMOS technology scaling trend are theoverall circuit requirements; the maximum power dissipation, the required chipspeed, and the needed functional density. The overall device requirements suchas the maximum MOSFET leakage current, minimum MOSFET drive current,and desired transistor size are determined to meet the overall circuit requirements.Similarly, the choices for MOSFET scaling and design, including the choice of24physical gate length Lg and equivalent oxide thickness of the gate dielectric tox,etc., are made to meet the overall device requirements. Figure 3.1 depicts thescaling trend for the CMOS feature size across several technology generations aswell as some future predictions according to the semiconductor roadmap publishedby the International Technology Roadmap for Semiconductors (ITRS) [1].1801309065 45 32 2225035050001002003004005006001993 1995 1997 1999 2001 2004 2007 2010 2013 2016YearFeature Size (nm)Figure 3.1: Gate length scaling of CMOS technologies [1].There are two common types of scaling trends in the CMOS process: constantfield scaling and constant voltage scaling. Constant field scaling yields the largestreduction in the power-delay product of a single transistor. However, it requiresa reduction in the power supply voltage as the minimum feature size is decreased.Constant voltage scaling does not suffer from this problem, therefore, it providesvoltage compatibility with older circuit technologies. The disadvantage of constantvoltage scaling is that the electric field increases as the minimum feature length isreduced, resulting in velocity saturation, mobility degradation, increased leakagecurrents, and lower breakdown voltages. Hence, the constant field scaling is themost widely used scaling approach in the CMOS industry. Table 3.1 summarizesthe constant field scaling in the CMOS process.In order to maintain the switching speed improvement of the scaled CMOSdevices, the threshold voltage VTH of the devices is also scaled down to maintaina constant device overdrive. However, decreasing VTH results in an exponentialincrease in the subthreshold leakage current,ID ∝ 10VGS−VTH+ηVDSS , (3.1)where S = nkTqln10. Moreover, as the technology is scaled down, the oxide thicknesstox is also scaled down, as shown in Table 3.1. The scaling down of tox results inan exponential increase in the gate oxide leakage current.25Table 3.1: Constant field scaling of the CMOS process.Parameter Symbol Constant Field ScalingGate Length L 1/αGate Width W 1/αField ε 1Oxide Thickness tox 1/αSubstrate Doping Na αGate Capacitance CG 1/αOxide Capacitance Cox αCircuit Delay td 1/αPower Dissipation Pd 1/α2Area A 1Power Density P/A 1As a result of the continuous scaling of VTH and tox, the contribution of thetotal leakage power to the total chip power dissipation is increasing notably. Thecontribution of leakage power is expected to exceed 50% of the total chip power bythe 65nm CMOS process [1], as shown in Figure 3.2.Normalized PowerYear1990 1995 2000 2005 2010 2015 20200.00000010.00010.011100500 350 250 180 130 90 65 45 22Technology Node (nm)Dynamic PowerLeakage PowerFigure 3.2: Leakage power contribution to the total chip power [1].263.3 CMOS Devices Leakage MechanismsThere are six short-channel leakage current mechanisms in CMOS devices. Figure3.3 summarizes the leakage current types that affect state-of-the-art CMOS devices[46]. I1 is the reverse-bias pn junction leakage; I2 is the subthreshold leakage; I3is the oxide tunneling current; I4 is the gate current due to hot-carrier injection;I5 is the Gate Induced Drain Leakage (GIDL); and I6 is the channel punchthroughcurrent. Currents I2, I5, and I6 are OFF-state leakage currents, while I1 and I3occur in both ON and OFF states. I4 can occur in the OFF state, but moretypically occurs during the transistor transition [46]. The main sources for leakagepower dissipation in current CMOS technologies are the subthreshold leakage andgate oxide leakage currents.GateSource Drainn+n+p-wellI3,I4I2I1I5bodyI6Figure 3.3: Leakage current mechanisms of deep submicron devices [46].There are two main components for the reverse-bias pn junction leakage I1;minority carrier diffusion/drift near the edge of the depletion region and electron-hole pair generation in the depletion region of the reverse-biased junction. I2 flowsbetween the source and drain in a MOSFET when the gate voltage is below Vth.I3 occurs by electrons tunneling from the substrate to the gate and also from thegate to the substrate through the gate oxide layer. I4 occurs due to electrons orholes gaining sufficient energy from the applied electric field to cross the interfacepotential barrier and enter into the oxide layer. I5 is due to the high field effect inthe drain junction of the MOSFET. Because of the proximity of the drain and thesource, the depletion regions at the drain-substrate and source-substrate junctionsextend into the channel. Channel length reduction and the increase in the reversebias across the junctions push the junctions nearer to each other until they almostmerge, thus leading to the punchthrough current I6.27Out of these six different leakage current mechanisms experienced by currentCMOS devices, subthreshold and gate leakage currents are the most dominantleakage currents. Furthermore, the contribution of subthreshold leakage current tothe total leakage power is much higher than that of gate leakage current, especiallyat above room temperature operating conditions. The contribution of gate leakagecurrent to the leakage power dissipation is expected to increase significantly with thetechnology scaling, unless high K materials are introduced in the CMOS fabricationindustry [1].3.4 Current Situation of Leakage Power in Nanome-ter FPGAsFor FPGAs to support reconfigurability, more transistors are used than those usedin an ASIC design that performs the same functionality. Consequently, leakagepower dissipation in FPGAs is higher than that in their ASIC counterpart. It wasreported in [47] that on average, the leakage power dissipation in FPGA designsis almost 5.4 times that of their ASIC counterparts under worst-case operatingconditions. The excess leakage power dissipated in FPGAs is mainly due to theprogramming logic that is not present in ASIC designs.A study of the leakage power dissipation in a 90nm CMOS FPGA was performedin [48], of which the results are summarized in Table 3.2. By comparing the averageleakage power dissipation of a typical 90nm CMOS FPGA at 25◦C and 85◦C, itcan be seen that the average leakage power increases by four times. Moreover, theresults in the first column are for a utilization of 75%, hence, the leakage powerdissipation for a 1,000 CLB FPGA would be in the range of 4.2mW. If these FPGAsare to be used in a wireless mobile application, which has a typical leakage currentof 300µA, then the maximum number of CLBs that can be used would be 86 CLBsfor the 25◦C and 20 CLBs for the 85◦C.Table 3.2: FPGA leakage power for typical designs and design-dependent variations[48].TTypical PLEAK Best-Case Worst-Case(avg. input data; UCLB = 75%) input data input data25◦C 4.25µW/CLB -12.8% +13.0%85◦C 18.9µW/CLB -31.1% +26.8%28In addition, the dependance of leakage on the input data increases significantlywith the temperature. This can be deduced from Table 3.2 as the variation due tothe worst and best cases input vectors change from ±13% at 25◦C to about ±28%at 85◦C. Furthermore, in another experiment conducted in [48], it was found outthat for a 50% CLB utilization, 56% of the leakage power was consumed in theunused part of the FPGA. Hence, in future FPGAs these unused parts have to beturned down to reduce this big portion of leakage power dissipation.3.5 Leakage Power Reduction Techniques in FP-GAsWith the increasing contribution of leakage power to the total power dissipation,leakage power started to take a front seat in FPGAs power reduction. In thisSection, a survey of the leakage reduction techniques in FPGAs proposed in theliterature is presented.3.5.1 Leakage Power Reduction in the Logic BlocksIn [49], a dual-VDD power reduction approach for FPGA logic and routing resourcesis proposed. The buffers in the FPGA fabric have the flexibility to either connectto a high or a low VDD depending on the criticality of the net. Nets with highcriticality are routed through logic and routing resources controlled by high-VDDswitches and less critical nets are routed through low-VDD resources. Thus, in eachLUT, the designer can select either of the two VDDs according to the performancerequirements. In addition, some of the logic elements can be hardwired directlyto either of the supply lines. Figure 3.4 shows the different logic blocks available(Figure 3.4(a) high-VDD block H-Block, Figure 3.4(b) low-VDD block L-Block, andFigure 3.4(c) programmable-VDD block P-Block).The CAD flow that makes use of the proposed architecture is developed toefficiently select the values of the dual supply voltage, as pre-defined VDD valueswere not used to increase the power savings. Furthermore, a level converter is usedto transform the output of a low-VDD LUT to the high VDD value to avoid shortcircuit power dissipation. The average power savings achieved from this approach isabout 14%. This approach suffers from the complexity of finding the correct value ofthe low-VDD during each configuration. Moreover, the use of level converters adds29LogicBlockHigh-VDD(a) H-BlockLogicBlockLow-VDD(b) L-BlockLogicBlockHigh-VDDLow-VDDConfigBitConfigBit(c) P-BlockFigure 3.4: VDD programmable low-power FPGA resources [49].a huge area and power penalty to the final design. This approach also requiresexternal circuitry to generate the two supply voltages needed.The idea was further extended by the authors in [50] by including a two-bitcontrol for the VDD supply to enable power-gating for the unused FPGA resources.By enabling power gating, the percentage power savings was increased to 50%.Another extension for this methodology was presented in [51], where the authorsproposed a dual-Vt fabric in addition to the dual-Vdd. In this architecture, thethreshold voltage VTH of the pass transistors inside the LUT is lowered accordingto the VDD to minimize the performance losses due to lowering VDD. The dual-Vdddual-Vt approach achieves an average power savings of 13.6% and 14.1% for com-binational and sequential circuits, respectively. In addition to the above mentionedissues for the dual-Vdd approach, the dual-Vt requires a double-well technologyto support body biasing, which is an expensive process. A similar approach forleakage power dissipation was proposed in [52], where dual voltage is enabled bythe use of header and footer devices to change the LUT voltage supply.In [53,54], an active leakage power reduction methodology was proposed for boththe logic blocks and the routing resources that use pass transistor multiplexers. Themain idea behind that work is that the amount of leakage current depends on theinputs to the circuit. Hence, by manipulating the inputs, the unused parts of theFPGA can be placed in a low-leakage state. Moreover, by utilizing the complementof the signals, the authors managed to reduce the leakage of the used parts of theFPGA. The static probabilities of the signals were used to estimate the dominantstates of the signals and then an optimization problem was developed to makethat dominant state a low-leakage one. The average active leakage power reductionachieved by this method was 25% for a 90nm CMOS process.30In [55], a leakage reduction technique that depends on the use of sleep transistorsto switch off the power supply from the unutilized parts of the FPGA was proposed.Moreover, the parts of the FPGA that exploit similar idleness periods are turnedon/off during runtime. The logic blocks with similar idleness profile are placed closeto each other in the FPGA fabric using a region constrained placement. However,the authors of [55] did not provide a method to automatically identify these logicblocks that have similar activity profiles. They resorted to a manual step, which inturn is inappropriate to be included in a CAD flow. Moreover, during the placementstage, the region constrained placement algorithm tries to place all those blocks withthe same activity profile right beside each other, irrespective of the connectionsbetween these logic blocks and the other logic blocks that have a different activityprofile. This approach can seriously affect the delays of the placed design, especiallyin designs with a large number of critical nets. Finally, the authors presented resultsbased on only one benchmark without considering the fact that the amount of powersaving depends on the benchmark used.In [56], the authors proposed to use the unutilized pins inside the logic block toreduce the glitching power inside the LUT. The methodology is based on forcingthe unused pins to constant values in such a way that glitches do not occur inthe pass-transistor multiplexer. Moreover, the authors also use the placement androuting stages of the CAD flow to reduce the length of the wires that have transitionprobabilities.3.5.2 Leakage Power Reduction in Routing CircuitryThe ability to program and reprogram the FPGA results in a huge overhead in therouting resources of the FPGA. As a result, the routing circuitry is the main sourceof power dissipation in FPGAs. A number of recent studies reported that 60%-70%of the total FPGA power dissipation is consumed in the routing resources [57].In [58], two low leakage routing switch designs were proposed to operate in threedifferent modes; high-speed, low-speed, or sleep mode, as shown in Figure 3.5. Themain idea is based on the use of sleep transistors to block the supply voltage VDDwhen the circuit is idle. The difference between the routing switches in Figure3.5 is that the one in Figure 3.5(b) uses body biasing to change Vth of the PMOStransistors by tieing their bodies to the virtual ground line VV D.In the two configurations in Figure 3.5, both sleep transistors, MNX and MPXare on when the circuit is operating in the high-speed mode, thus acting as a31~SLEEP LOW_POWER v SLEEPVDD VDDVVDOUTMPXMNX(a)~SLEEP LOW_POWER v SLEEPVDD VDDVVDOUTMPXMNX(b)Figure 3.5: Programmable low-power routing switches [58].transmission gate and driving the circuit with a full rail-to-rail voltage. MPX isturned off in the low-speed mode, while MNX is kept on, thus reducing the circuitdrive to VDD − Vth to GND and lowering its speed. In the low-speed mode, thecircuit power consumption, both dynamic and leakage power dissipation, is reduced.In the sleep mode, both MNX and MPX are turned off, thus blocking the supplyfrom the circuit.On average, the configuration in Figure 3.5(a) offers leakage and dynamic powerreduction in the low-power mode by 36-40% and 28%, respectively, while the leakagereduction in the sleep mode is 61%. The routing switch in 3.5(b) reduces theaverage leakage and dynamic power dissipation by 28-30% in the low-power modewhile offering a 36% area reduction.In [57], the authors compared the pros and cons of several low-leakage tech-niques available in the ASIC domain and their chances of being applied to theFPGA domain. All of the leakage mitigation techniques were applied to the rout-ing resources of the FPGA. The authors experimented with logic duplication inthe memory cells of the routing resources and and achieved a two-fold decrease inleakage power dissipation with a 1.3X-2X increase in the FPGA area. A dual-Vtdesign of the routing resources, where LVT devices are used to route critical netsand HVT devices are used to route non-critical ones, achieved a leakage power re-duction of 70% without any area penalty. Body biasing techniques, to change VTHof the routing multiplexers pass transistors, achieved a 1.7X-2.5X leakage powerreduction, with an area increase of 1.6X-2X. However, body biasing techniques areexpensive, process wise, because of the need for an extra step during fabrication.Gate biasing was also used to lower the VGS of the off devices below zero to mini-32mize their subthreshold leakage current, leakage current is proportional to VGS. A2.5X-4X of leakage power reduction was witnessed by gate biasing with a negligiblearea penalty.In [59], the authors proposed a heterogenous routing structure, where the wirelengths are varied and the devices used in the routing resources too are varied. Acombination of transistors with high-Vth, regular device, devices with long channellengths are used to trade off the final design performance with the leakage powerdissipation. The CAD flow identifies the signals with low criticality and forcesthem to get rerouted to slower paths that use either high-Vth devices or deviceswith longer channel lengths. A similar approach was proposed in [60], however,only high-Vth devices were used.3.6 Power Reduction Techniques in CommercialFPGAsIn the past few years, FPGA vendors started adding power reduction techniques totheir commercial FPGAs. Most commercial FPGAs use SRAM cells with high-Vthdevices to limit the power dissipation in the configuration SRAM. In this Section,the methodologies used in commercial FPGAs for power reduction in three of themost popular FPGAs will be presented.3.6.1 Altera Stratix III Power Reduction TechniquesThe Stratix III devices are equipped with the ability to operate at two core voltages;1.1V and 0.9V. The programmable power supply powers the logic and routingresources, DSP blocks, memory blocks, and clock networks. However, the I/O padsare kept operating at a fixed voltage of 1.1V. The ability to operate at a lowersupply voltage achieves both dynamic and leakage power dissipation since dynamicpower is proportional to the square of the supply voltage while leakage power isproportional to the supply voltage.In addition, the Stratix III devices offer supply voltage programmability insidethe core by giving the designers the flexibility to change the supply voltage ofindividual logic blocks inside the device. In this case, performance is traded offwith power dissipation. However, this property is only available for the logic blocks,thus limiting the power savings achieved. The main disadvantage of the dual core33devices is that two external supply voltages are needed, which does not make sucha device a strong choice in hand-held applications.3.6.2 Xilinx Virtex-5 Power Reduction TechniquesThe Virtex-5 devices use clock gating techniques for dynamic power dissipationreduction. The logic blocks in the Virtex-5 devices have an enable control forthe input clock signals that can disable the clock when needed, thus reducing thedynamic power dissipation. Moreover, the clock tree is also equipped with a controlto prevent further propagation of the clock signals when needed.3.6.3 Actel IGLOO Power Reduction TechniquesA main advantage for IGLOO FPGAs is the use of flash for their configurationbits, compared to SRAM used in Stratix III and Virtex-5. Flash power dissipationis much lower than that of SRAM. Moreover, IGLOO devices are equipped with aFlash Freeze technology that enables the user to put the whole FPGA in a standbymode when needed. The Flash Freeze is programmable, so it can automaticallybring the deice up again when certain conditions are satisfied. This technology isenabled by the non-volatile nature of the flash cells used in IGLOO. As a result,IGLOO devices offer significant dynamic and leakage power dissipation.34Chapter 4Power Estimation in FPGAsWith power dissipation posing as an important factor in the design phase of FPGAs,power estimation and analysis techniques have become huge challenges for FPGAvendors. Power characterization is an important step in designing power efficientFPGA architectures and FPGA applications. Designers need a method to quantifythe power advantage of the architectural design decisions without having to gothrough fabrication. Moreover, FPGA users need to check the power efficiency ofthe several possible implementations without actually going through the lengthydesign phase.Power models for FPGAs need to consider both components of power dissipa-tion, dynamic and leakage power. To further improve the accuracy of the powermodel, all the subcomponents of both dynamic power (switching, short circuit, andglitch power), and leakage power (subthreshold and gate leakage power), need tobe accounted for. In addition, other factors that affect power dissipation, includingspatial correlation and input dependency of leakage power, should be considered,especially in the sub-nanometer regime since their impact is highlighted as theCMOS minimum feature size is scaled down.In this Chapter, a newly proposed power estimation methodology under spatialcorrelation for FPGAs is presented. Moreover, the proposed power estimation tech-nique accounts for glitching power as well as the dependency of leakage power onthe input states. The Chapter starts by a quick introduction to the power estima-tion problem in general in Section 4.1. An overview of the main research projectsthat targeted power estimation in the VLSI in general and FPGAs in particularis given in Sections 4.2 and 4.3, respectively. Section 4.4 describes the impact ofspatial correlation on power estimation. The proposed algorithms for power esti-mation under spatial correlations and glitching power estimation are presented in35Sections 4.5 and 4.6 and Section 4.7, respectively. Section 4.8 describes the powermodeling strategy used in this work. Finally, the results and the discussions of thisChapter are presented in Section 4.9.4.1 IntroductionModern CMOS processes suffer from two dominant sources of power dissipation;dynamic and leakage power. Dynamic power dissipation can be divided into switch-ing, glitch, and short circuit power dissipation, while leakage power dissipation canbe further divided into subthreshold leakage and gate leakage power dissipation.Historically, CMOS circuits were dominated by dynamic power dissipation, how-ever, by the 65nm CMOS process, leakage power is expected to dominate the totalpower dissipation, as explained in Chapter 3. In addition, further down the scalingroad, gate leakage power is expected to surpass subthreshold power dissipation,especially at lower operating temperatures, as predicted by the semiconductorsroadmap issued by the ITRS [1], unless high K materials are used to implementthe devices gates.All sources of power dissipation in CMOS circuits exhibit significant state de-pendency. In order to develop an accurate power model, accurate informationabout signal probabilities needs to be available. Several works in the literaturehave addressed this problem and a complete survey was presented in [61].The switching component of the dynamic power dissipation is expressed asPowerdyn =12× fclk × V 2DD ×n∑i=1Ci × αi , (4.1)where fclk is the circuit clock frequency, VDD is the supply and swing voltage, Ciis the capacitance of the ith node in the circuit, and αi is a measure of the numberof transitions per clock cycle experienced by node i. As a result, the problem ofswitching power estimation resolves to finding the capacitance and measure of thenumber of transitions at every node.Glitching power occurs because of the spurious transitions at some circuit nodesdue to unbalanced path delays. Consequently, glitching power results in an increasein the number of transitions at every circuit node that is susceptible to glitches.Hence, the impact of glitching power can be modeled just by adding a factor tothe transitions estimate α in Eq. (4.1). Finally, short circuit power dissipationis the power dissipated due the presence of a direct current path from the power36supply to the ground during the rise and fall times of each transition. Hence,short circuit power is a function of the rise and fall times and the load capacitance.Several research projects have been directed to provide an accurate estimate ofshort circuit power dissipation [62–65]. However, the simplest method to accountfor short circuit power dissipation is to set it as a percentage of the dynamic powerdissipation, usually 10% [66].4.2 Power Estimation in VLSI: An OverviewThe power estimation is defined as the problem of evaluating the average powerdissipation in a digital circuit [61]. Power estimation techniques fall into two maincategories: simulation-based or probabilistic-based approaches.4.2.1 Simulation-Based Power Estimation TechniquesIn simulation-based techniques, a random sequence of input vectors is generated andused to simulate the circuit to estimate the power dissipation. The first approachesdeveloped were based on the use of SPICE simulations to simulate the whole circuitusing a long sequence of input vectors [67,68]. However, the use of such methods intoday’s VLSI industry is impractical, especially with the huge levels of integrationachieved, that it might take days if not weeks to simulate a complete chip usingSPICE. Moreover, these methods are significantly pattern dependent due to the useof a random sequence of input vectors. If an intelligent method is used to select theinput sequence, these methods would provide the most accurate power estimation.Several simplifications of these methodologies were proposed to reduce the com-putational complexity of power estimation [69–72]. The methods still rely on simu-lations, but instead of using SPICE simulations, other level of circuits simulationswere performed including switch-level and logic-based simulations. These method-ologies trade accuracy for faster runtime. In order to perform these simulations,the power supply and ground are assumed constant. However, these methods stillsuffer from pattern dependency since there is a need to generate a long sequenceof input vectors to achieve the required accuracy. Although these simulations aremore efficient than SPICE simulations, yet they are somewhat impractical to usefor large circuits, especially if a long input sequence is used to increase the methodaccuracy.37In order to solve the pattern dependency problem of simulation-based powerestimation methods, several statistical methods had been proposed [73–78]. Thesestatistical methods aim to quantify two parameters: the length of the input sequenceand the stopping criteria for simulation, required to achieve a predefined powerestimate accuracy.The earliest of these studies focused on the use of Monte Carlo simulationsto estimate the total average power [73]. A random sequence of N input vectorswas independently generated and used to simulate the circuit. Let p̄ and s be theaverage and standard deviation of the power measured over a time period T andPav is the average power. Hence, the error in the average power estimated can beexpressed with a confidence of (1− α)× 100% as|p̄− Pav|p̄ Isleep thenC = C −Belsebreakend ifend foractivity regions according to their activity profile. Logic blocks with similar activitylabels have similar activity profiles. In this work, two activity profile generationalgorithms are proposed: Connection Activity Profile (CAP) generation and LogicActivity Profile (LAP) generation, as well as a modification for the LAP algorithmReverse-LAP (R-LAP).815.4.1 Connection-based Activity Profile Generation Algo-rithm (CAP)The main criterion used by CAP to identify the activity profiles is connectivity.Logic blocks that are connected to each other are expected to have similar activityprofiles. The main reasoning behind this assumption is that whenever the inputsto a logic block change, its output is expected to change as well, which in turn willcause the logic blocks connected to its output to switch too. This is a pessimisticapproximation of the real case as the change in the output depends on the logicimplemented by the logic block.The algorithm begins with the circuit primary inputs and greedily allocatesactivity regions as it traverses the circuit netlist by means of a simple depth-firstgraph search algorithm, thus, resulting in a fast and computationally efficient algo-rithm. While traversing the circuit netlist, whenever a new logic block is reached,it is necessary to determine whether to add this logic block to the current activityregion, or to place it in a new activity region. There are two principal driving coststhat need to be considered at each node: the size of the activity region and theattraction of a certain logic block to that activity region.Reducing the size of the activity region provides the clustering algorithm withmore flexibility to pack only those logic blocks that manifest the same activity, notthose that have close activity profiles. Although this leads to a greater leakagesavings, increasing the number of activity regions results in increasing the numberof sleep signals used, thus causing a power-inefficient implementation, as well ascomplicating the control circuitry for generating these signals. Furthermore, thealgorithm must be expansive while each logic block is processed. The addition ofany logic block to the current activity region, implies the addition of all of its fan-inand fan-out logic blocks, because the algorithm is connection-based. Consequently,the number of fan-ins and fan-outs of any logic block, should be considered duringthe process and the cost of adding the current logic block to the current activityregion is expressed ascost1 =currCap + α×Neighbors−maxCapmaxCap, (5.8)where maxCap is the predefined maximum capacity for the activity region, currCapis the current capacity of the activity region, Neighbors is the number of logicblocks directly connected to B and not yet placed in any activity region, and α is aweighting constant to control the quality of the final solution. The use of Neighbors82provides the cost function with the ability to look around the current logic blockto examine which other logic blocks are expected to be attracted to the currentactivity region, if the logic block under investigation is placed in it. It should benoted that the value of Neighbors can be easily evaluated during the file parsingstage without the need for a special pre-processing phase. The parameters thatneed to be tuned in (5.8) are maxCap and α.The value of maxCap should be a function of the circuit size to ensure its scal-ability with the different circuits. In this work, maxCap is selected as a functionof the number of logic blocks on the longest path in the circuit. Reducing maxCapenables the activity generation algorithm to pack only those logic blocks that man-ifest the same activity, i.e., closely connected to each other, not those that haveclose activity profiles, thus resulting in a large number of activity regions, as well assleep regions. Although this leads to more leakage savings, yet increasing the num-ber of activity regions results in increasing the number of sleep signals used, thuscomplicating the control circuitry needed for generating these signals. On the otherhand, a large value for maxCap will result in a large activity region with a shortsleep time, thus reducing the leakage power savings resulting from the algorithm.By running the algorithm on several benchmarks for a wide variety of valuesfor maxCap, it was found that a value for maxCap of 1.5 times the longest pathfrom input to output in the circuit provides the best results in terms of powersavings. The average leakage power savings across the tested benchmarks is plottedin Figure 5.12. Increasing maxCap than 1.5 times the longest path in the circuitresults in having excessively large activity regions that have limited leakage powersaving capability. On the other hand, decreasing maxCap increases the number ofactivity regions in the final design, thus resulting in a complex and power-hungrysleep-signal generation circuitry.On the other hand, α controls the expansive ability of the algorithm. The valueof α should range between 0 and 1, where a 0 value means that the algorithmconsiders that adding the current logic block to the cluster will not attract otherlogic blocks to it. A value of 1 for α means that adding the current logic block tothe cluster will result in adding all of the logic blocks connected to it as well. Inthis work, the value of α is updated adaptively according to currCap based on thefollowing relationα =0.3 currCap < 0.5×maxCap0.6 0.5×maxCap ≤ currCap < 0.7×maxCap1 0.7×maxCap ≤ currCap830510152025300.4 0.6 0.8 1 1.2 1.4 1.6 1.8 2maxCap (x longest path length)Average Power Savings (%)Large sleep regions with short sleep periodsLarge number of sleep regions with complex sleep signal generationFigure 5.12: Leakage power savings vs the maximum activity region capacity.The second cost function is the attraction between logic block B and the currentactivity region C, which is expressed ascost2 = Nets(B) ∩Nets(C) , (5.9)where ∩ denotes the number of nets shared between B and C. The decision ofwhether or not a certain logic block should be added to the current activity regionresolves to a comparison between cost1 and cost2δ × cost2 − cost1 ≥ 0 ⇒ add to the current activity regionδ × cost2 − cost1 < 0 ⇒ start a new activity regionwhere δ is a normalization factor. It should be noted that cost1 is always nega-tive, ranging from -1 to 0, unless the activity region capacity exceeds that of themaximum capacity. On the other hand, cost2 is a positive integer. When δ is closeto 0, the activity region maximum capacity maxCap is the main limiting factorto assigning activity labels, thus all activity regions will have capacity equals tomaxCap. When δ is close to 1, the attraction to the activity region is the drivingfactor for activity labeling, thus the activity region capacity might exceed maxCap.In order to determine the optimum value of δ, the CAP algorithm is run severaltimes for values of δ ranging from 0 to 1 across different benchmarks and the ca-pacity of the activity region is recorded in each case. The average activity regionsize, in terms of maxCap, across all the tested benchmarks is plotted in Figure5.13, which shows that the average activity region size increases with δ. The value840.811.21.41.61.80.1 0.3 0.5 0.7 0.9Activity Region (x maxCap)Over-filled sleep regionUnder-filled sleep regionFigure 5.13: Average activity region size across several benchmarks vs. δ.ADFBEcost 1|D =-0.6cost 2|D = 1CADFBEC(a)(d)cost 1|F = 0.25cost 2|F = 1ADFBEcost 1|B = -0.35cost 2|B = 1CADFBEC(e)(b)cost 1|E = -0.5cost 2|E = 1cost 1|C = -0.75cost 2|C = 1ADFBECON when the inputs of A or B changeON when the inputs of B or C change(c)cost 1|B = 0cost 2|B = 1Figure 5.14: CAP activity generation flow for maxCap = 4 and δ = 0.2of δ used in this work is 0.2 which results in an average activity region capacity ofabout 1.03maxCap. A value greater than that will result in larger activity regions.Figure 5.14 depicts an example of activity generation by the modified CAPalgorithm for a maximum activity region size of four. Figure 5.14 indicates thatthe algorithm begins with node A and then studies its child D to select the paththat minimizes the total cost function, which in this case is D. Following that thechildren and parents of D are examined (E and B, respectively). At that point, bothB and E have equal cost1, hence, cost2 is checked and E is selected because it hasthe smallest cost2. The procedure continues until the algorithms starts processingF , at which the activity region will be full and a new activity region will start.Hence, F and C will be in the same activity region. The pseudocode for themodified CAP algorithm is given in Algorithm 5.2.85Algorithm 5.2 Pseudocode of the proposed CAP algorithm.Create an undirected graph from the netlistTraverse the graph using DFSfor each node i dofor each node j connected to i docalculate cost1,j and cost2,jif cost1,j ≤ min cost1 thenmin node = jend ifend forif δ ×min cost2 −min cost1 > 0 thenadd to the current activity regionelsestart a new activity regionend ifend for5.4.2 Logic-based Activity Profile (LAP) GenerationThe Logic-based Activity Profile (LAP) generation algorithm depends on repre-senting the activities of the logic blocks as a binary sequence. The circuit topologyis ignored in the LAP algorithm and instead the circuit logic function is used tofind the optimum clustering that prolongs the OFF periods of each logic block. Inorder to properly explain this algorithm, several definitions and notations will befirst introduced.5.4.2.1 Activity VectorsDefinition 1: Activity VectorGiven a net x in a circuit netlist, the activity vector Ax of x is defined as:Ax = [ a1 a2 a3 .... a2n−1 a2n ]T ,where n is the total number of inputs to the circuit, ai is a binary variable that is ‘1’if any of the outputs of the circuit depend on net x for evaluation when the inputsto the circuit are given by the ith input vector, and T represents the transpose ofthe vector.In FPGAs, each logic block has only one output; thus, the activity vector ofeach net resolves to be the activity vector of the logic block driving that net. The86circuit in Figure 5.15 provides an example of the operation of LAP, where the logicof each block is depicted underneath the circuit. Logic blocks F and G must beON all of the time to generate the outputs of the circuit f and g, respectively.Consequently, the activity vectors Af and Ag for blocks F and G, respectively, aregiven byAf = [ 1 1 1 1 1 1 1 1 ]T ,Ag = [ 1 1 1 1 1 1 1 1 ]T .On the other hand, for computing the activity vector at the inputs of block F ,DabdEcFefG gI hHid = a.b e = a.b’+a’.b f = c.d+c’.e g = a+fi = a.c h = e+iFigure 5.15: A circuit example.it is noteworthy that block D will be only used to generate the output signal f ifthe input c is ‘1’. Similarly, block E is only used when c is ‘0’. Hence, the activityvectors for D and E, when f is evaluated, are represented byAd = [ 0 1 0 1 0 1 0 1 ]T ,Ae|f = [ 1 0 1 0 1 0 1 0 ]T .However, to evaluate h, E will have the following activity vector:Ae|h = [ 1 1 1 1 1 1 1 0 ]T .Hence, the resulting Ae is given byAe = Ae|f + Ae|h = [ 1 1 1 1 1 1 1 0 ]T .Finally, the activity vector for i is given byAi = [ 1 1 0 0 0 0 1 1 ]T .87From this discussion, it can be deduced that if F , G, and H are active forall the input combinations, packing them together will result in improved results.Moreover, E will be active for almost all of the input combinations except for onlyone, thus it can also be packed with F , G, and H in the same cluster. Therefore,the cluster containing E, F , G, and H will be always ON. On the other hand, Dand I have similar activity profiles for half of the input combinations, thus it willbe a good strategy to group them together and turn OFF this cluster for half ofthe circuit operational time.From the above discussion, it can be deduced that the complexity of the originalLAP algorithm is proportional to 2n where n is the total number of circuit inputs.In large circuits with hundreds of inputs, this complexity renders the LAP algorithmimpractical. In the next subsections, several modifications are proposed to reduceits complexity significantly.5.4.2.2 Hamming Distance: A Measure of the Correlation Between Ac-tivity ProfilesThe relation between the activity profiles of the different logic blocks is evaluatedby means of the Hamming distance between their activity vectors.Definition 2: Hamming DistanceGiven two binary sequences of length n; An and Bn, the Hamming distance d(a,b)between these two sequences is defined asd(a,b) =n−1∑k=0|ak − bk| , (5.10)where ak and bk are the kth elements of An and Bn, respectively.Hence, the Hamming distances between the activity vectors of the signals inFigure 5.15 are evaluated asd(f,g) = 0 d(f,d) = 4 d(f,e) = 1 d(f,i) = 4d(g,d) = 4 d(g,e) = 1 d(g,i) = 4 d(e,d) = 5d(e,i) = 5 d(e,h) = 1 d(d,i) = 4 d(d,h) = 4d(i,h) = 4It can be noticed that the Hamming distance between the activity vectors of anytwo logic block is a measure of the correlation between their activity profiles. AHamming distance close to the absolute minimum of zero, indicates that the two88blocks will exhibit the same activity profile, thus when positioned together in thesame cluster will result in maximum power savings and vice versa. This is verified byexamining the values of the Hamming distances above and the results stated in theprevious sub-section. However, the Hamming distance between the activity vectorsof two logic blocks does not take into consideration the probability of occurrenceof the different input combinations, which can notably affect the quality of theresults. The Weighted Hamming Distance is used to efficiently incorporate thevarious probabilities of the circuit input combinations.Definition 3: Weighted Hamming DistanceGiven two binary sequences of length n; An and Bn, and a weighting vector Wn,the weighted Hamming distance dw(a,b) between these two sequences is defined asdw(a,b) =n−1∑k=0wk × |ak − bk| , (5.11)where ak, bk, and wk are the kth elements of An, Bn, and Wn, respectively.The use of the weighted Hamming distance is not a sufficient measure for thedifference in activity between the different logic blocks. If for example, there are 2logic blocks with a weighted Hamming distance between them of 1. However, thisnet at which they differ is an active net that continuously toggles. This impliesthat the ST will switch frequently, increasing the dynamic power dissipation to theextent that it might override any savings in leakage power dissipation. In order toavoid such condition, the transition density [80] of the net needs to be consideredwhile calculating the Hamming distance. The transition density D is defined as theaverage number of transitions per unit time.Definition 4: Transition Weighted Hamming DistanceGiven the weighted Hamming distance dw(a,b) between two activity vectors; A andB, and Di the transition density of signal i, the transition weighted Hammingdistance dw(a,b) between these two activity vectors is defined asdw(a,b) = dw(a,b) ×max{DA, DB} . (5.12)5.4.2.3 The LAP Algorithm OperationThe LAP algorithm consists of two main phases: activity vector generation andactivity labeling. The activity vector generation phase exhaustively simulates thecircuit by iterating all the input vectors and finding the values of all the circuit netsresulting from that input vector. Afterwards, for each input vector iteration, each89signal (or block) is tested to investigate whether or not it affects the evaluation of thecircuit outputs. This is performed by complementing the value of the signal underconsideration and then proceeding from that point towards the circuit outputs. Ifthe output of the logic blocks that have this net as an input will change, thenthis change is taken to the next circuit level, otherwise, a ‘0’ is placed in thecorresponding row of the input vector. If a loop is found, then this net is given ‘1’in its activity vector for that input combination. It should be noted that the numberof levels checked from the net under consideration increases the computational timesignificantly. In order to limit this computational complexity, the number of levelsto be checked is limited to three. After exhaustively generating all the activityvectors for all the circuit nets, the static probability of each net is calculated.The next step is the calculation of the Hamming distance between each two logicblocks in the design. This is performed recursively through all the design elements.The transition weighted Hamming distance dw between every two logic blocks isthen calculated. At this point, the activity labels can be assigned according to theweighted Hamming distance. However, this approach can result in performancedeterioration as the connections between the different logic blocks is not considered.Since those logic blocks that will have a similar activity label are expected to beplaced in the same sleep region, i.e., will be placed close to each other. Hence,it seems that the wire length should be included in the activity labeling as well.Since at this stage the algorithm does not have any information about where eachblock will be placed, an approximation for the wire length is adopted. If any twologic blocks share one net, then the distance between them l is considered as zero,e.g., E and F in Figure 5.15. If there is one level of logic blocks in between anytwo logic blocks, then the distance is considered as 1, and so on.In order to combine the transition weighted Hamming distance and the distancebetween logic blocks, logic blocks are assigned activity labels by minimizing the costfunction given belowmin{dw + δ × l} , (5.13)where δ is a normalization constant selected to be 0.5. To avoid having activityregions with a large number of logic blocks, which will decrease the leakage savings,the size of the activity region is limited to 1.5 times the longest path from input tooutput in the circuit. This value was obtained by running the algorithm on severalbenchmarks. Assigning a constant value for activity region size, irrespective of thecircuit size, results in impractical results. Increasing the activity region size morethan 1.5 times the longest path in the circuit results in having excessively largeactivity regions that are usually not fully filled up by the algorithm. On the other90hand, reducing the activity region size increases the number of activity regions inthe final design.Hence, the algorithm starts to greedily assign activity labels to the logic blocksaccording to (5.13) until the maximum activity region size is reached. Afterwards, anew logic block is selected as a seed cell for a new activity region and the procedureis repeated. The pseudocode of the algorithm is listed in Algorithm 5.3.Algorithm 5.3 Pseudocode of LAP.for all the input combinations dofor all the nets in the circuit dofind the value of the netend forfor each net in the circuit dotoggle the value of the netActivity[input vector][net] = 0proceed with the new value of the netif the value of any output changes thenActivity[input vector][net] = 1end ifend forend forfor each net in the circuit dofind the static probabilityfind the transition densityfind the distance to each net in the circuitend for5.4.2.4 Reverse Logic Activity Profile (R-LAP) Generation AlgorithmIn this section, the Reverse Logic Activity Profile (R-LAP) generation algorithm ispresented. The R-LAP algorithm is a modification of the LAP algorithm that offersa significant execution time improvement as well as more leakage power savings.R-LAP represents the logic blocks activity profiles using an activity vector, similarto the LAP algorithm.915.4.2.4.1 R-LAP Algorithm OperationIn order to reduce the complexity of the LAP algorithm, this work proposes theReverse Logic-based Activity Profile (R-LAP) generation algorithm. In the R-LAPalgorithm, instead of generating the activity vectors for the outputs of each logicblock, R-LAP generates the activity vectors of the inputs to each logic block. Thisis performed by checking each logic block whether its ith input will contributeto the output when the other inputs are given by a certain combination. If theith input is needed for evaluating the output, then a ‘1’ is placed in the inputsignal activity vector that corresponds to this input combination, otherwise, a ‘0’is entered. Hence, the complexity of the algorithm is O(2(m−1) × m), where m isthe number of inputs to the logic block, which is usually around four [28].As an example, for the circuit shown in Figure 5.15, when ‘b’ is ‘0’, ‘a’ is notneeded to evaluate ‘d’. On the other hand, ‘a’ is always needed to evaluate ‘e’.By taking a look at logic block F , ‘e’ is not needed to evaluate ‘f ’ when ‘c’ is ‘1’.Similarly, ‘d’ is only needed when ‘c’ is ‘1’. Furthermore, ‘f ’ is needed to evaluate‘g’ when ‘c’ is ‘0’. Hence, the R-LAP algorithm will evaluate the activity vectorsof the different signals in Figure 5.15 asAd|c = [ 0 1 ] Ae|c = [ 1 0 ] Af |c = [ 1 0 ]Hence, it can be deduced that placing F and E in the same sleep region will resultin maximum power leakage savings as they both can be turned OFF when ‘c’ is ‘1’.For each logic block, the different activity vectors for all of its inputs are gener-ated as mentioned above. As a result, each net will have p different activity vectorsassociated with it, where p is the number of the net fanout. In order to find theHamming distance between the logic blocks inside any sleep region, a large activityvector is generated using the smaller activity vectors of each logic block inside it,and then the Hamming distance is evaluated from the sleep region activity vec-tor. It should be noted that the R-LAP algorithm generates the activity vectorsfor each logic block with respect to all the other logic blocks it is connected to.Furthermore, sleep regions are usually filled by logic blocks that share connectionsto reduce the total wirelength and enhance the final design performance. Hence,there is no need to generate the activity vectors for each logic block with respectto all the other logic blocks in the circuit that they do not share a connection with.The pseudocode of the R-LAP algorithm is listed in Algorithm 5.4.92Algorithm 5.4 Pseudocode of the proposed R-LAP.for each logic block i dofor each input j of i dofor each of the other inputs combinations k doEvaluate the output of block i when input j is ‘0’Evaluate the output of block i when input j is ‘1’if i|j=0 == i|j=1 thenAj|i[k] = 0elseAj|i[k] = 1end ifend forend forend for5.5 Activity Packing AlgorithmsModern island-style FPGAs have a hierarchal architecture, where several logicblocks are packed together to form clusters. The packing process takes a netlist ofLUTs and registers and outputs a netlist of logic clusters. The main aim of theavailable packing algorithms is to minimize the total area (by packing clusters totheir full capacity), minimize the delay (by packing LUTs on a certain critical pathtogether [18]), and/or maximize routability (by minimizing the number of inputs toeach cluster). However, the goal of minimizing power dissipation, either dynamicor leakage power dissipation, has been rarely addressed. In this work, the activityprofiles obtained earlier are incorporated into the T-VPack [18] algorithm to packlogic blocks to minimize leakage power dissipation.5.5.1 Activity T-VPack (AT-VPack)In this work, the T-VPack algorithm is modified to include activity profiles, thusthe modified T-VPack is called Activity T-VPack (AT-VPack). In AT-VPack, aset of logic blocks are selected as candidates to be added to the cluster underinvestigation. The selection criteria for these candidate logic blocks are: (i) thecombined discharge current of the logic blocks inside the cluster plus the logicblock to be added does not exceed Isleep and (ii) the activity label of the logic blockto be added is the same as that of the logic blocks inside the cluster. From the pool93of candidate logic blocks, the one that maximizes Attraction and satisfies the threehard constraints of VPack is selected to be added to the cluster. If AT-VPack failsto fill out all of the spaces in the cluster, the hill-climbing approach used in theoriginal T-VPack is invoked to start filling the vacant places while satisfying both(i) and (ii).Unlike T-VPack, AT-VPack might still be unable to fill the cluster to its max-imum capacity due to the additional two constraints (i) and (ii). Hence, a secondhill-climbing stage is used that employs simulated annealing to swap the logic blocksin the cluster with other candidate logic blocks that have not been clustered yetand then try to fill the cluster. If the set of logic blocks currently in the clusteris given by A and the set of logic blocks that had not been clustered is called B,the algorithm swaps block i from set A with block j from set B while satisfyingconstraint (iii) using the following cost functionmin{α[κ(Attraction(Ai)−Attraction(Bj))+(1−κ)number of vacant placestotal number of places]},(5.14)where α is a variable that represents the transition weighted Hamming distancebetween A and Bj (α = 1 + dw) and κ is a weighting constant (0 ≤ κ ≤ 1) thatis used to give importance to either filling up the cluster with any blocks or toconsider the attraction force. A small value of κ would result in a faster fillingfor the cluster, while a decrease in the Attraction() can be tolerated, while a largevalue will keep the decrease in Attraction() to a minimum and accepting partiallyfilled clusters. By performing several experiments using AT-VPack for differentFPGA benchmarks, it is found that the best value for κ is 0.5. The value chosenfor α forces the algorithm to start looking at first for blocks with the same activityas the cluster before looking for blocks with other activities. Even when it doeslook for logic blocks with different activities, it always searches for those with closeactivity profiles. This ensures maximum leakage savings (clusters with blocks thathave different activity profiles will be on for a longer period).Moreover, the cost function in (5.14) minimizes the loss in the quality of thesolution, in terms of the attraction force, by minimizing the difference betweenAttraction(Ai) and Attraction(Bj). Similarly, the current constraint is kept asa hard constraint throughout this hill-climbing stage. By the end of this hill-climbing stage, the cluster is full to its maximum capacity. A pseudocode for AT-VPACK algorithm is listed in Algorithm 5.5. In addition, the starting temperatureparameter of the simulated annealing and the number of inner iterations to be94performed are chosen not to be large to speed up the packing process and avoiddecreasing the quality of the original solution.Algorithm 5.5 Pseudocode for the AT-VPACK algorithm.Perform T-VPACK with 2 extra constraints:- Icluster ≤ Isleep- activityblocks in cluster is constantwhile there are empty spaces in the cluster dofor all unclustered blocks dofind blocks i and j with min cost (equation(5.14))add i to the clusterif max Icluster ¿ Isleep thenremove iend ifend forend whileThe ability of AT-VPack in minimizing the number of logic blocks used in thedesign can be verified by finding the maximum number of unfilled clusters in eachbenchmark. Among all of the benchmarks tested, the maximum number of unfilledclusters is 4, which is less than 1% of the total number of clusters in the design.5.5.2 Force-based Activity T-VPack (FAT-VPack)The Activity T-VPack (A-VPack) algorithm suffers from long execution time be-cause it added two hard constraints to the conventional T-VPack algorithm; (i) thecombined discharge current of the logic blocks inside the cluster plus the logic blockto be added does not exceed Isleep and (ii) the activity profile of the logic block tobe added is the same as that of the logic blocks inside the cluster. As a result thisalgorithm suffers from a long runtime. In this work, the FAT-VPack algorithm isproposed to reduce the complexity of the AT-VPack algorithm by getting rid ofone of the added hard constraints used in AT-VPack. The activity profiles of thedifferent logic blocks are added to the Attraction() function in Eq. (2.7) by includ-ing a new activities gain function. It should be noted that the constraint on themaximum discharge current of the activity region is still adopted in the FAT-VPackalgorithm.The ActivityGain is a representation of how close is the activity vector of blockB to that of cluster C. In R-LAP algorithm, the ActivityGain(B,C) of adding95block B to cluster C is calculated asActivityGain(B) =2n − d̄w(b,c)2n. (5.15)where n is the number of cluster inputs.The total FAT-VPack gain function used in this work is given byAttraction(B) = (1− α) ×[λ× Criticality(B) + (1− λ)× SharingGain(B,C)]+ α× ActivityGain(B, C) (5.16)where α is weighting constant (0 ≤ α ≤ 1). Setting a large value for α will forcethe packing algorithm to pack the blocks that have the shortest Hamming distancein the same cluster, hence, same sleep region, without giving much weight to thetiming information and wirelength. In the following experiments, α will be set to0.5 and the impact of its value on both the leakage savings and speed penalty willbe discussed later.5.5.3 Timing-Driven MTCMOS (T-MTCMOS) AT-VPackIn both the AT-VPack and FAT-VPack algorithms, the total discharge currentconstraint was kept as a hard constraint for all the clusters. In the T-MTCMOSalgorithm, the maximum discharge current is varied from one cluster to the other.From Eq. (5.6), it can be noticed that for the same WL∣∣sleepof the sleep transistor,the performance loss depends on Isleep. A sleep region with a large Isleep will have alarger performance loss than another one with smaller Isleep, if they employ equal-sized sleep transistors.This work makes use of this observation to avoid incurring a large performancepenalty on the critical path. Hence, the maximum performance loss along thecritical path can be limited to a value smaller than that along non-critical ones,i.e., timing-driven MTCMOS (T-MTCMOS). The timing information of the logicblocks is used to vary Isleep of each cluster according to its criticality using theproposed T-MTCMOS technique.The maximum discharge current inside any cluster should not exceed the valueused in (5.6) for a speed penalty of x%. The value of the discharge current can varyfrom one cluster to the other depending on the criticality of each cluster, hence,the speed penalty imposed on the cluster. In order to account for the differentcriticalities along the signal paths, Isleep(C) is formulated asIsleep(C) =[1 + δ(1− Criticality(C)Max Criticality)]× Îsleep , (5.17)96where Îsleep is the maximum discharge current calculated for the minimum perfor-mance penalty, i.e., 3%, δ is a weighting constant, Criticality(C) is the criticalityof cluster C, and Max Criticality is the criticality of the critical path(s) of the cir-cuit. From (5.17), it can be noticed that if the criticality of the cluster is equal tothe maximum criticality of the circuit, i.e., the cluster lies on the critical path, thevalue of Isleep will be equal to that for the minimum performance penalty, i.e., 3%,otherwise, a larger value for Isleep will be used, hence, a larger performance penalty.The weighting factor δ is used to make sure that after adding block B to clusterC, the path does not become a critical path itself. If δ is set to a value close to0, then all of the sleep regions will have an Isleep very close to that for a 3% per-formance penalty. On the other hand, if δ is set to 1.6, the sleep regions will havea wide variety of Isleep values, hence speed penalties, with a maximum penalty of8%. However, a large value for δ increases the possibility that the added perfor-mance penalty might cause some uncritical paths to become critical. By conductingseveral experiments on the value of Isleep, it was discovered that by adopting anadaptive update technique for δ, shown below, depending on the criticality ratio(Criticality(C)/Max Criticality), resulted in no new critical paths while havinga wide variety for Isleep values.0 < Criticality(C)/Max Criticality ≤ 0.5 δ = 1.60.5 < Criticality(C)/Max Criticality ≤ 0.8 δ = 0.80.8 < Criticality(C)/Max Criticality ≤ 1 δ = 05.6 Power EstimationIn order to evaluate the performance of the proposed algorithms, the power dissi-pation in the placed and routed design is compared to that of the same benchmarkwithout sleep transistors. The power model proposed in Chapter 4, which calculatesdynamic, short-circuit, and leakage power, is used to estimate the power dissipationin the design without sleep transistors. In order to measure the power dissipationin the design with sleep transistors, several modifications are added to the powermodel.There are two standby modes for any circuit; full standby and partial standby.In the fully standby state, the whole circuit is in the idle state and all of the sleeptransistors in the circuit should be turned off. During that period, the circuit onlyconsumes standby leakage power. During partial standby, some parts of the circuitare in the active state and other parts are in the idle state. Hence, some of the97sleep transistors are turned ON and others are OFF. Thus, the circuit will consumea combination of dynamic power and active and standby leakage power.The total power dissipation Pt is expressed asPt = ton × Pon + toff × Pidle , (5.18)where ton and toff are the percentages of ON and OFF times of the FPGA and Ponand Pidle are the power dissipation during the active and idle modes of operationof the FPGA. Pon is expressed asPon = [Pdyn + Psckt + Pleak]utilized + Pleak|unutilized , (5.19)where Pdyn, Psckt, and Pleak are the dynamic, short-circuit, and active leakage powerdissipations, respectively, in the utilized logic blocks, while Pleak|unutilized is thestandby leakage in the unutilized logic blocks.Three different modifications were done to the power model presented in Chap-ter 4. (1) Leakage current is calculated only due to the sleep transistor rather thancalculating the leakage through all the devices in the circuit because the sleep tran-sistors act as a bottleneck for the subthreshold leakage current. (2) Short circuitpower dissipation is approximated as 15% of the dynamic power dissipation ratherthan the 10% used in the original model to account for the increased rise/fall timesof the logic blocks with sleep transistors. The 15% approximation was evaluatedby simulating logic blocks with and without an sleep transistor using HSpice. (3)The dynamic power consumed in the sleep transistor during switching between theON and OFF states is calculated and added to the total power dissipation.5.7 Results and DiscussionsIn this section, the capability of the proposed activity profile generation algorithmspresented in Section 5.4 and the packing algorithms discussed in Section 5.5 toreduce leakage power dissipation will be tested. The CAP, LAP, and R-LAP algo-rithms are integrated into the VPR tool together with the AT-VPack, FAT-VPack,and T-MTCMOS. In addition, the power model presented in Chapter 4 with themodifications discussed in Section 5.6 is used to estimate the power savings achievedby each combination of activity profile generation algorithm and activity packingalgorithm in the final design. It should be noted that the proposed logic-baseddischarge current processing algorithm is used to calculate the discharge currents98of the sleep regions. The proposed algorithms are tested on several FPGA bench-marks to assess their capability in minimizing both standby and active leakagepower dissipation.The decision whether to keep a utilized sleep region ON all of the time or dy-namically switching between ON and OFF depending on its activity profile is basedon a balance between the leakage power savings resulting from turning it OFF dur-ing its idle periods and the dynamic power dissipated in the sleep transistor duringthe transition. Whenever the dynamic power dissipated in the sleep transistor dur-ing waking up or putting the cluster into sleep exceeds the leakage savings fromany cluster, the cluster is kept always ON. Leakage power savings can be achievedwhen the cluster stays OFF for a certain period of time, Tbreak even. In this work,the transition density [80], the average number of transitions per cycle, is used asa measure of how long a signal stays in a certain state. Based on the transitiondensity of each sleep signal, if the signal experiences a large number of transitionssuch that Tbreak even is never or rarely reached, the sleep region is kept always ON,otherwise, it is dynamically turned ON and OFF depending on the activity profile.5.7.1 Experimental SetupIn the first set of experiments, the sleep region size is set to one cluster and eachcluster has four logic blocks. This is only a starting point for the experiments andlater on the optimum size of the sleep region will be evaluated. Moreover, theselected size is close to the optimum sleep region size reported in [118].It should be noted that the maximum allowable performance loss due to thesleep transistors in all of the benchmarks is kept fixed at 5% in the AT-VPack andFAT-VPack algorithm, i.e., x in Eq. (5.6) is set to 0.05. However, in the case ofthe T-MTCMOS algorithm, the value of x is varied depending on the criticality ofthe logic blocks in the sleep region.All the circuits tested are mapped onto the smallest square FPGA array thatcan accommodate them, i.e., maximum utilization percentage. The case wherethe design is mapped onto the minimum FPGA array is called 100% utilization.Moreover, the design is assumed to be operating without standby periods for thewhole benchmark. This case is referred to as 100% ON time. Initially, the resultsreported are for a 90nm CMOS process, however, towards the end of this section,the proposed leakage reduction algorithms are applied to 130nm, 65nm, and 45nmCMOS technologies.995.7.2 Algorithms ComparisonTable 5.1 lists the results of applying the different activity generation algorithmswith a variety of the proposed activity packing algorithms on several FPGA bench-marks under the above mentioned conditions. The power dissipated by each designis calculated using the modified power model discussed in Chapter 4 and the per-centage savings in the total power are listed in Table 5.1. It should be noted thatTable 5.1 does not iterate the results from all the possible combinations of the pro-posed algorithms. Only the combinations that achieve large leakage power savingsare reported.Table 5.1: Leakage power Savings for the different activity profile packing algo-rithms across several FPGA benchmarks.Benchmark% of Unutilized % Savings in Power (100% on time)Clusters CAP & LAP & R-LAP & R-LAP &AT-VPack AT-VPack FAT-VPack T-MTCMOSalu4 4.5 10.82 17.23 37.05 61.78apex2 2.48 10.35 15.54 29.09 55.8apex4 2.16 8.59 13.38 25.74 50.91bigkey 2.72 9.59 14.92 30.42 56.62clma 0.76 7.37 12.09 24.48 50.82des 0.25 7.49 11.99 24.47 51.97diffeq 6 11.51 17.74 36.07 57.48dsip 4.7 8.79 14.18 30.23 50.49elliptic 5.9 10.2 16.42 32.03 51.24ex1010 0.26 7.73 12.09 23.07 48.49ex5p 6.92 11.14 17.51 35.92 54.3frisc 1.56 8.08 12.97 24.51 50.98misex3 2.21 9.37 14.57 29.86 58.33pdc 0.78 6.8 11.29 21.5 46.34s298 8.32 14.28 21.06 40.94 56.75s38417 5.6 12.46 18.21 36.34 60.19s38584.1 1.56 8.17 12.93 25.73 51.51seq 0 4.62 7.14 15.23 32.03spla 3.6 8.73 12.85 27.41 50.08tseng 8.3 13.25 19.75 39.32 56.37Average Leakage9.47 14.69 29.47 52.62Power Savings (%)The power savings presented in Table 5.1, show that the combination of theR-LAP and the FAT-VPack algorithms provide more leakage power savings thanthe combination of CAP and LAP with AT-VPack. Furthermore, integrating theT-MTCMOS algorithm with R-LAP results in the highest power savings.The combination of logic-based discharge current processing, R-LAP, and FAT-VPack result in higher power savings than the combination of CAP and LAP with100AT-VPack because the FAT-VPack algorithm can cluster logic blocks that haveclose activity profiles, not necessarily the same activity profile, by finding a cor-relation between their activity profiles, hence, achieve more leakage savings. Onthe other hand, the AT-VPack algorithm can only pack the logic blocks with thesame activity profiles in the same cluster, otherwise, the cluster is left ON at alltimes. In addition, the logic-based discharge current processing algorithm providesthe packing algorithm with the flexibility to pack those logic blocks that have simi-lar activity profiles without violating the discharge current constraint. As a result,more power savings can be achieved.On the other hand, the T-MTCMOS algorithm achieves more power savingsthan FAT-VPack across all of the benchmarks. The average improvement in thepower savings is almost 50%. The main reason behind the increase in power savingsis that in FAT-VPack, the discharge current constraint is a hard constraint acrossall of the benchmarks, thus the algorithm might fill a cluster with logic blocks thathave different activity profiles and satisfy the current constraint, although thereare other blocks that have closer activity profiles but violate the current constraint.On the other hand, T-MTCMOS allows the current constraint to be violated to acertain extent along non-critical paths, thus giving more freedom to the packingalgorithm to pack logic blocks with close activity profiles to achieve more leakagepower savings.5.7.3 Impact of Activity Packing on PerformanceAs mentioned earlier, the use of sleep transistors results in a performance penaltydue to the added resistance of the sleep transistor to the ground. Moreover, bothFAT-VPack and T-MTCMOS do not result in the same packing as that foundby the conventional T-VPack, because of the added constraints, either dischargecurrent or activity profile, or gain functions to the optimization problem. Hence,the resulting packing might suffer from an additional speed degradation because ofthat reason. In this work, the performance loss of the critical path is considered asan indication of the performance loss for the whole design. In this experiment, thedelays along the critical paths in the placed designs and packed using the proposedpacking algorithms are compared to those when the designs are packed and placedusing the conventional VPR flow. Figure 5.16 plots the average speed penaltiesamong all of the benchmarks used in this work. Moreover, Figure 5.16 shows themaximum and minimum speed penalties experienced in the different benchmarksfor each case.101024681012R-LAP + FAT-Vpack R-LAP + T-MTCMOSAlgorithm Used% Performance PenaltyMin Average MaxFigure 5.16: Speed penalty experienced in the different benchmarks due to the useof sleep transistors.From Figure 5.16 it can be deduced that the resulting design from T-MTCMOSoutperforms that of FAT-VPack in terms of timing properties. The FAT-VPackalgorithm incurs a minimum of 5% delay penalty across all the paths in the design.However, T-MTCMOS increases the delay across the critical path by a minimumof 3% while making sure no other critical paths get created.In another experiment, the maximum performance penalty allowed in T-MTCMOSis varied from 8% to 14%, while the minimum performance penalty is kept at 3%and the results for the ‘s298’ benchmark are plotted in Figure 5.17. It was noticedthat for a sleep region of size 4 logic blocks, the leakage savings increased with themaximum speed penalty until a speed penalty of 10%, after which the curve almostflattens. The increase in leakage savings can be justified by the fact that increasingthe maximum speed penalty allows the packing algorithm to pack logic blocks thatexhibit similar activity profiles in the same cluster without worrying about theirdischarge current. On the other hand, as the speed penalty is increased beyond acertain limit, the packing algorithm can not achieve more leakage savings becausethe sleep regions are now packed to their maximum (4 logic blocks). However, asthe number of logic blocks per sleep regions is increased, more leakage savings canbe experienced, as shown in Figure 5.17. It should be noted that increasing thesize of the sleep region beyond 8 logic blocks, results in an increase in the leakagesavings, however, the dynamic power dissipation in the sleep transistors, which aresignificantly up-sized, increases to cancel out most of the leakage savings.In another experiment, the maximum speed penalty is set to 12 for the ‘s298’1023035404550556065708 9 10 11 12 13 14Percentage speed penalty along non-critical pathsPercentage Power Savings4-BLE sleep region6-BLE sleep region8-BLE sleep regionFigure 5.17: ‘s298’ leakage savings vs maximum speed penalty for the R-LAP andT-MTCMOS combination.benchmark while varying the minimum speed penalty (Figure 5.18). As the mini-mum performance penalty increases (by up-sizing the sleep transistor), the leakagesavings increases, until a certain limit after which the savings decrease because ofthe increase in dynamic power of the sleep transistors. It can be noticed that thebreakpoint gets smaller as the size of the sleep region increases because larger sleepregions employ large sleep transistors.0501001502002503 4 5 6 7 8 9 10Percentage delay along the critical pathPercentage laekage savings 4-BLE 6-BLE 8-BLEFigure 5.18: ‘s298’ leakage savings vs minimum speed penalty for the R-LAP andT-MTCMOS combination.Figure 5.19 plots the relative path delays distribution in the ‘ex5p’ benchmarkwith respect to the critical path delay. From Figure 5.19 it can be deduced thatthe number of critical paths did not increase. In addition, the maximum circuitdelay changed by only 3%. The final shape of the delay distribution can be varied103by changing δ.02004006008001000120014000.5 0.6 0.7 0.8 0.9 1Relative Delay w.r.t. the Critical DelayNo. of PathsBefore T-MTCMOSAfter T-MTCMOSFigure 5.19: Critical path distribution for timing-driven MTCMOS designs.5.7.4 Leakage Savings BreakdownIn each benchmark, the leakage power savings consist of two parts; savings frompermanently turning OFF all the unused clusters and savings from dynamicallyturning ON and OFF the used clusters in the design depending on their activityprofile. By taking a look at the results for the ‘seq’ benchmark in Table 5.1, thisbenchmark has no unused clusters while the power savings achieved ranges from7.14% to 15.23%, depending on the combination of the activity profile generationand the packing algorithms used. This power savings is entirely from dynami-cally turning ON and OFF the different used clusters in the design depending ontheir activity profile. On the other hand, the ‘s298’ benchmark has the maximumpercentage of unused blocks among all of the benchmarks and it resulted in themaximum power savings, ranging from 21.06% to 40.94% depending on the activ-ity generation and packing algorithm used.In order to quantify the leakage power savings provided by the unused andused clusters of the design, the power savings from each source is recorded foreach benchmark. Figure 5.20 plots the average power savings achieved by eachcombination of algorithms used across all the benchmarks. It should be noted thatthe average power savings achieved by turning OFF the unused clusters is 4.92% andis constant across all the combination of algorithms used. This is mainly becauseall the combination of algorithms provide almost the same number of clusters afterpacking, hence, the number of unused clusters remains the same. Figure 5.20104shows that even for the least power efficient combination of algorithms (CAP &AT-VPack), the power savings from the used clusters is almost double that fromthe unused clusters. The contribution of the used clusters to the total power savingsincreases with the algorithm efficiency.0102030405060CAP & AT-Vpack LAP & AT-Vpack R-LAP & FAT-VpackR-LAP & T-MTCMOSAlgorithm UsedPercentage Power SavingsSavings in Unused ClustersSavings in Used ClustersFigure 5.20: Leakage power savings breakdown.5.7.5 Impact of Utilization and ON Time on Leakage Sav-ingsIn reality, the utilization percentage is less than the 100% utilization assumptionused in finding the results in Table 5.1. Typically, the utilization in FPGAs rangesfrom 80% to 60% [55]. In order to investigate the impact of the utilization per-centage on the total power savings by turning OFF the unused logic blocks, thebenchmarks are mapped on a larger FPGA fabric and the results are plotted inFigure 5.21 for utilization percentages of 80% and 60% using the R-LAP and T-MTCMOS combination. It can be noticed that the power savings achieved bypermanently turning OFF the unused clusters increases almost exponentially withdecreasing the utilization percentage.Moreover, the 100% ON time assumption made earlier is impractically high.The average on time of most applications is around 50% to 20% for some hand-105051015202560 80 100Percentage UtilizationPower Savings from the Unused ClustersFigure 5.21: Percentage savings in power for different FPGA fabric utilizationsusing the combination of R-LAP and T-MTCMOS.held applications [111]. Hence, the same benchmarks are tested again using ONtimes of 100%, 60%, and 40% and the average power savings from the used clustersof the FPGA are plotted in Figure 5.22. From Figure 5.22, it can be noticedthat with reducing the operational time increases the total power savings from theproposed algorithms significantly.01020304050607080CAP & AT-Vpack LAP & AT-Vpack R-LAP & FAT-Vpack R-LAP & T-MTCMOSAlgorithm UsedPercentage Power Savings in the Used Clusters 100% ON time 60% ON time 40% ON timeFigure 5.22: Percentage savings in power for different utilizations and operationaltime using the combination of R-LAP and T-MTCMOS.1065.7.6 Impact of the Sleep Region SizeIn another experiment, several sizes for the sleep region are tested for differentcluster sizes. The size of the cluster is changed from 3 to 6 logic blocks and thesize of the sleep region is changed from 1 to 5 clusters. The leakage savings in eachof these experiments are recorded and plotted in Figure 5.23. From Figure 5.23,it can be noticed that for each cluster size, there is an optimum sleep region size.Moreover, leakage savings is always maximum for sleep regions of size around 8 logicblocks. This proves the fact stated earlier that too large (will require a large sleeptransistor, which results in large standby leakage and dynamic power dissipation inthe sleep transistor) and too small (will result in partially unfilled clusters, whichwill increase the area and decrease the number of permanently OFF sleep regions,hence, increases the total leakage power) sleep regions will result in lower leakagesavings.05101520253035401 2 3 4 5# of blocks in the sleep region 3 BLEs 4 BLEs 5 BLEs 6 BLEs% Power SavingsFigure 5.23: Impact of the sleep region size on the leakage savings.5.7.7 Scalability of the Proposed Algorithms with Technol-ogy ScalingIn order to investigate the scalability of the proposed algorithms, the R-LAP FAT-VPack combination as well as the R-LAP T-MTCMOS combination are applied toseveral current CMOS technologies (130nm, 90nm) and predictive CMOS technolo-107gies (65nm, 45nm) [124]. The average power savings across all the benchmarks areplotted in Figure 5.24.01020304050607080130nm 90nm 65nm 45nmCMOS TechnologyTotal Power SavingsR-LAP + FAT-VPack R-LAP + T-MTCMOSFigure 5.24: Impact of technology scaling on power savings.5.8 ConclusionsIn this Chapter, the proposed MTCMOS architecture for FPGAs is introduced.Moreover, the developed algorithms for activity generation (CAP, LAP, and R-LAP) and activity packing (AT-VPack, FAT-VPack, and T-MTCMOS) are pre-sented. It was found that the combination of the R-LAP algorithm and T-MTCMOSresults in the maximum leakage power savings and minimum performance penaltyon the final design.108Chapter 6Leakage Power Reduction inFPGAs Through Input PinReorderingInput dependency of leakage power has been witnessed in VLSI circuits in general[125] and in FPGAs in particular [48], where it was reported that 4X variations inleakage power can be experienced in commercial 90nm FPGAs.Input signal forcing techniques have been used in [53] to reduce the active leak-age power dissipation in FPGAs. Since leakage current is heavily state dependent,by manipulating the inputs of some logic blocks, the unused parts of the FPGAcan be placed in a low-leakage state. Moreover, by utilizing the complements of thesignals, the authors have managed to reduce the total leakage power of the utilizedparts of the FPGA. However, the methodology in [53] is based on the assumptionthat only one output state can result in the minimum leakage power dissipation.This is basically due to the fact that the authors only studied the power dissipationin the inverters, without trying to find a low-leakage state in the pass-transistormultiplexers. It will be demonstrated in this thesis that there is more than one lowleakage state that can be further exploited to achieve a bigger reduction in leakagepower dissipation. The technique proposed in [53] focuses on leakage power mini-mization only in the inverters and buffers of the FPGA without considering leakagepower minimization in the other parts of the FPGA, including the pass-transistormultiplexers.In FPGAs, input signal forcing is a substantial leakage power reduction tech-nique, since FPGAs depend on pass-transistor logic in their design, where power109dissipation is strongly state dependent. In this Chapter, a complete new methodol-ogy, based on input pin reordering, is developed to reduce the total leakage powerdissipation in all components of FPGAs, unlike [53] that focuses only on the in-verter, without incurring any area or performance penalties in the final design. Inthe proposed methodology, the logic and routing resources are handled differentlyto achieve maximum leakage savings. Moreover, a modified version of the proposedmethodology is implemented to improve the performance along the critical path,and still achieves significant leakage power savings in the design. Moreover, theimpact of technology scaling on the lowest leakage states is investigated in thiswork.This Chapter is organized as follows; the state dependency of leakage power inFPGAs is discussed in Section 6.1. The proposed input pin reordering algorithm isintroduced in Section 6.2. Finally, the results of applying the proposed algorithmon the generic FPGA architecture are discussed in Section 6.3.6.1 Leakage Power and Input State Dependencyin FPGAsLeakage current in nanometer CMOS technologies has two main components; sub-threshold and gate leakage currents. Subthreshold leakage current flows from thedrain to the source of an OFF CMOS device. On the other hand, gate leakagecurrent flows through the gate of the device to or from one or both the diffusionterminals. Gate leakage has both an ON and OFF component, with its OFF com-ponent almost ignorable relative to the ON part [46]. Both components of leakagepower exhibit strong dependency on the state of the input signals as discussed inthis Section.6.1.1 Subthreshold Leakage CurrentThe subthreshold leakage current Isub is defined as the current that flows betweenthe drain and source of a MOS device when VGS is less than VTH . Isub is formulatedasIsub = µoCoxWL(m− 1)× v2T × e(VGS−VTH)/mvT × (1− e−VDS/vT ) , (6.1)where µo is the device mobility, Cox is the oxide capacitance, W and L are thedevice dimensions, vT is the thermal voltage (kT/q), and m is the subthreshold110swing coefficient, which is given bym = 1 +3toxWdm, (6.2)where tox is the oxide thickness and Wdm is the maximum depletion layer width.The contribution of the subthreshold leakage current to the total power dissipationincreases with technology scaling due to the continuous reduction in VTH to improvethe device performance.The input state dependency on the subthreshold leakage current can be readilyseen in Eq. (6.1) in the dependence of Isub on VDS and VGS. Two dominantfactors affect the input dependency of subthreshold leakage current: Drain InducedBarrier Lowering (DIBL) and Body Effect. Subthreshold leakage current is also astrong function of the temperature, increasing significantly with increasing the chiptemperature.6.1.1.1 Drain Induced Barrier Lowering (DIBL)In nanometer CMOS devices with short channels, the drain-source potential has astrong impact on the band bending over a significant part of the CMOS device. Asa result, the threshold voltage of the CMOS devices becomes a function of the drainsource voltage. Applying a large drain to source voltage to the CMOS device resultsin decreasing the threshold voltage, hence, increasing the subthreshold current.Figure 6.1 plots the change in VTH and the subthreshold leakage current Isub ofa minimum size 90nm NMOS device with the change in VDS from 0V to 1.2V.It should be noted that this 90nm CMOS process has a supply voltage of 1.2V,thus the change in the drain to source voltage plotted in Figure 6.1 can be readilyexperienced during operation. Figure 6.1 shows that for two equal-sized transistors,their VTH can differ by almost 25% and their leakage current can vary by 4.5X, dueto the DIBL effect, because of a difference in VDS equal to the supply voltage.Pass-transistor multiplexers used in FPGAs can experience four different valuesof VDS, as shown in Figure 6.2. The transistors in the first and last stages of themultiplexer are the only ones that can experience the worst case VDS of VDD. Themiddle stages can experience a maximum of VDD − VTH because of the weak ‘1’passed by the NMOS pass-transistors. From Figure 6.2, it can be deduced that themaximum leakage current occurs when the signals at both diffusion terminals of amultiplexer transistor are different, i.e., to have the largest value of VDS.From the above discussion, it can be concluded that a means of reducing sub-threshold leakage in pass-transistors multiplexers is to ensure that the majority of1110 0.4 0.8 1.20.150.20.25VDS (V)VTH (V)0 0.4 0.8 1.2051015202530VDS (V)I DS (nA)Figure 6.1: DIBL effect in a 90nm CMOS process.Increasing VdsIncreasing IleakFigure 6.2: DIBL impact on subthreshold leakage in FPGA pass-transistor devices.the pass-transistors experiences the smallest VDS. It should be noted that if thefirst stage of the multiplexer is designed to have the smallest VDS, the total multi-plexer subthreshold current will be limited significantly, since the total subthresholdcurrent has to flow through them.6.1.1.2 Body EffectThe impact of the body to source voltage VBS on VTH has been witnessed in CMOSdevices for several technology generations. The effect of body bias is formulated asVTH = VTH0 + γ(√|Φs| − VBS −√|Φs|), (6.3)112where VTH0 is the ideal VTH at zero VBS, γ is the body bias coefficient, and Φs is thesurface potential. Having a negative VBS would result in increasing the thresholdvoltage, which in turn will reduce the subthreshold leakage current.It should be noted that CMOS devices in pass-transistor multiplexers will neverexperience a positive VBS, since the body of the pass-transistors is always connectedto GND. Pass-transistors with logic ‘0’ at one or both of the diffusion terminals willnot experience body effect as VBS would be zero. However, those devices with logic‘1’ at both their diffusion terminals will experience subthreshold leakage currentreduction due to body effect because their |VBS| would be maximum, either VDDor VDD − VTH .6.1.2 Gate LeakageGate leakage exists in both the ON and OFF states of the CMOS devices [46].However, the off component of the gate leakage is ignorable with respect to theON component. The value of gate leakage is a strong function of both VGS andVDS. Large values of |VGS| and small values of VDS generate a large gate leakagecurrent. Figure 6.3 shows the two dominant gate leakage current configurationsand how they depend on the input state. The gate leakage resulting from theother input configurations is much smaller than these two configurations and canbe safely assumed zero, at least for the 90nm CMOS process used in this thesis. Itshould be noted that the gate leakage current is not a function of the temperature,and thus, stays constant with the change in the chip temperature.VDD VDD - VTH0 0Increasing IgateVDD0Figure 6.3: Gate leakage dominant states in FPGA pass-transistor devices.6.1.3 Low-Leakage States in Pass-Transistor MultiplexersFrom the above discussion, it can be concluded that there is one or more input stateswhere the leakage power will be minimum in pass-transistor multiplexers. The input113state depends on the relative magnitude of the subthreshold leakage current to thatof the gate leakage current. In [96] it was reported that the gate leakage powerdissipation is less than 1/20 of the subthreshold leakage power dissipation in 90nmFPGAs at room temperature. In the experiments done in this work, the maximumgate leakage current in a 90mn minimum-sized device is in the order of 300pA, whichis much less than than the smallest subthreshold leakage current measured which isin the order of 1nA. Moreover, the contribution of the gate leakage power decreaseswith the increase in temperature due to the strong dependence on subthresholdleakage power on the temperature. Consequently, in this work, the most dominantleakage states are considered to be those of the subthreshold leakage current. Figure6.16 shows the input states that result in the lowest and highest leakage currentthat can be experienced in FPGAs pass-transistors.VDD VDD - Vth0 000(1) (2)(a) Lowest leakage states.0 VDD - Vth0 VDD0 0(1) (2)(b) Highest leakage states.Figure 6.4: Total leakage dominant states in FPGA pass-transistor devices.The configuration labeled (1) in Figure 6.4(a) results in the lowest leakage cur-rent. The highest leakage state is the one labeled (1) in Figure 6.4(b), whichexperiences the highest VDS, hence, the maximum DIBL effect and no body effect.By looking at the low leakage states shown in Figure 6.4(b), it can be deduced thatthe lowest leakage states occur if every pair of pass-transistors in the multiplexerhave inputs with similar value, as shown in Figure 6.5(a). The highest leakage stateoccur whenever the inputs to the multiplexer pair are different, as shown in Figure6.5(b). (a) Pass-transistor pair with similar inputs. (b) Pass-transistor pair with different inputs.Figure 6.5: Inputs to pass-transistors pairs.1146.1.4 Leakage Power in Inverters/BuffersIn this experiment a minimum-sized inverter is designed to have equal rise and falltimes to minimize short circuit power dissipation. This is achieved by increasing thewidth of the PMOS device while keeping the NMOS device to minimum width tobalance the difference in mobility of the two devices. The inverter is then simulatedusing HSpice and the total leakage power is recorded in both cases when the outputof the inverter is ‘1’ and ‘0’. The values of the measured leakage current are recordedin Table 6.1. As seen in Table 6.1, even if the PMOS and NMOS devices of theinverter are designed to have equal driving capabilities, the NMOS still leaks morethan the PMOS device. The ratio between the NMOS total leakage current to thatof the PMOS is almost 2X. This is mainly due to the inverse narrow width effectexperienced by trench isolated CMOS devices. PMOS devices in trench isolateddevices experience an increase in VTH with the initial increase in the width of thedevice. Afterwards, the leakage current starts increasing with the device width. Asa result, PMOS devices in the inverters sink a smaller subthreshold leakage currentthan the NMOS devices because of their larger width.Table 6.1: Leakage current in a minimum-sized inverter.Inverter Output Total Leakage Current‘0’ 17.03nA‘1’ 31.12nAThis is an interesting phenomenon as it can be used to further reduce leakageinside LUTs pass-transistors multiplexers. Multiplexers need inverters to generatethe complement of the control signals, which are generated inside the LUT usingminimum-sized inverters similar to the one simulated above, as shown in Figure 6.6.If the input control signal are all zeros, A and B in Figure 6.6, then all the inverterswould have a high output, thus, sinking the largest leakage current. Hence, it ismore leakage efficient to avoid having the most probable input state being all zeros,where all the inverters would generate the highest leakage current.6.2 Proposed Input Pin Reordering AlgorithmThe proposed pin reordering algorithm for leakage power reduction utilizes theconclusions developed in Section 6.1 to reduce total leakage power in the pass-transistor multiplexers. The algorithm consists of two phases; the first one targets115BĀABFigure 6.6: Gate leakage dominant states in FPGA pass-transistor devices.leakage reduction in the FPGA logic blocks, Logic Pin Reordering (LPR), and thesecond phase targets the routing switches, Routing Pin Reordering (RPR). TheLPR stage is performed right after synthesis and before the packing stage, whileRPR is performed after the routing stage, as shown in Figure 6.7. Again, the CADflow used in this thesis is based on the VPR CAD flow [28] where the packing isperformed using T-VPack and placement and routing is performed using the VPRCAD tool.Figure 6.7: VPR CAD flow with the proposed pin reordering algorithms.1166.2.1 Logic Pin Reordering (LPR) AlgorithmThe LPR algorithm reorders the input pins in such a way to have the maximumnumber of signals with similar polarities at the inputs of any multiplexer pair, asshown in Figure 6.5(a). The algorithm also avoids having the input configurationwith the highest probability to be the one with all zeros to further minimize leakagepower in the LUT, as explained in Section 6.2. Furthermore, the LPR algorithmhandles logic blocks differently according to the number of inputs of each logicblock. The LPR algorithm is divided into four separate phases as discussed in thenext subsections.6.2.1.1 Input Pins PaddingIn most FPGA CAD tools, whenever a logic block has inputs less than the maximumnumber of allowable inputs to a logic block, the unused inputs are either left floatingor connected to either VDD or GND. The choice whether to connect the unused inputpin to either rail does not follow a certain reasoning, but rather it is an architecturechoice. In this thesis, a padding methodology is proposed to make use of the factthat multiplexer pairs with similar inputs at both diffusion ends sink less leakagecurrent than those with different inputs, as shown in Figure 6.5.If a logic block has inputs less than the maximum number of allowable inputs,the extra inputs are padded in such a way to create the largest number of low-leakage multiplexer pairs. As an example, assume that the maximum number ofinputs for every logic block is three and the logic block shown in Figure 6.8(a)has only two inputs, A and B. The LPR algorithm then pads the extra input Cto the circuit, as shown in Figure 6.8(b). C is a fixed signal that can be set toeither ‘1’ or ‘0’. It should be noted that all modern FPGAs have the ability togenerate a constant signal from within the logic block with no need to use anyextra resources. As a result, the circuit with the padded inputs will have all of itsfirst level multiplexer pairs with identical signals at both inputs, as shown in Figure6.8(b), hence, maximum leakage reduction can be achieved in this case. It shouldbe noted that the inputs padded into the circuit always go into the least significantbits of the multiplexer.6.2.1.2 Input Pins SwappingThe second phase of the LPR algorithm is involved with the swapping of the inputpins to have the maximum number of multiplexer pairs with similar signals at117(a) Logic block withinputs less thanthe maximum.(b) Resulting circuit after in-put padding.Figure 6.8: Input padding for logic blocks with inputs less than the maximum.their inputs. Assume that the inputs to a 4-input logic block are A0A1A2A3. Thealgorithm picks the first input signal from the synthesized circuit A0 and looks atthe outputs of the logic function implemented when A1A2A3 are given by ‘000’,while A0 is both ‘0’ and ‘1’. If the two outputs are equal, the counter for A0 isincremented by 1. Afterwards, the algorithm looks at the outputs of the functionwhen A1A2A3 are given by ‘001’, and so on until all the 23 different combinationsare considered. The same procedure is repeated for the other 3 inputs A1, A2,and A3. The input with the highest count of equal signals is selected as the leastsignificant input pin. The computational complexity of this phase is O(m× 2m−1),where m is the maximum number of inputs to the logic block. A conventional valueof m is 4 [28].As an example of the algorithm operation, consider the 2-input logic block shownin Figure 6.9(a). The count of signals with similar input multiplexers would be zerofor A and two for B. Hence, the algorithm would move B to be the least significantbit of the multiplexer instead of A. The resulting logic block with configurationSRAM bits is shown in Figure 6.9(b), where it can be seen that now the first stagemultiplexers have signals with similar polarity at their inputs.After identifying the least significant input, the algorithm tries to find the orderof the remaining inputs using the same methodology. However, in finding the leastsignificant input pin, the inputs to the multiplexer are known since they are thecontents of the configuration SRAM cells. In the following multiplexer stages,1180Ā101AAĀBBout(a) Logic block before input pinsswapping.0110BBĀAoutBB(b) Resulting circuit after inputswapping.Figure 6.9: Input pin swapping for logic blocks to minimize leakage power dissipa-tion.static probability is used to find the most probable value expected at their inputs.If the static probability of the control input to the least significant multiplexeris higher than 0.5, the algorithm assumes that all the values connected to thetransistor controlled by the least significant pin will pass to the second stage. Onthe other hand, if the static probability is less than 0.5, the inputs controlled by thecompliment of the least significant input pin are assumed to go through. The sameprocedure used to select the least significant pin is used to order the remaininginput pins.It should be noted that most of the leakage savings is achieved from the selectionof the least significant input pin. This is mainly because the leakage current in themultiplexer will be limited to the smallest leakage current on the path. However,rearranging the pins of the latter stages adds an extra amount of leakage savingsby adding more resistance in the leakage current path. It is worth mentioning thatthis phase of LPR does not add any physical overhead to the design, since it merelyrearranges the input pins and the configuration SRAM contents.6.2.1.3 Most Probable StatesAs presented in Section 6.1.4, CMOS inverters dissipate almost 2X more leakagepower when their output is ‘1’. Since the multiplexers use several inverters togenerate the needed input signals to control the multiplexer, then it might be119wise to avoid having the most probable input being given by all zeros. Such aninput will generate the highest leakage power dissipation in the inverters inside themultiplexer. As a matter of fact, it is more desirable to have the most probableinput being all ones.To make use of this property, the LPR algorithm looks at the static probabilitiesof the different input combinations to each multiplexer, if the highest one containsa large number of zeros, i.e., more than half the maximum number of inputs, thealgorithm tries to avoid that by inverting one or more of the input signals. Thiscan be easily done in FPGAs as it only implies changing the contents of the SRAMcells in the logic blocks that are connected to this signal.The LPR algorithm looks at the set of inputs that need to be inverted and triesto invert only a small number of them that is needed to counterbalance the effect ofthe large number of zero inputs. As an example, consider a 4-input logic block thathas the most probable input being ‘1000’. Then the algorithm would need to toggletwo of the three least significant inputs to counterbalance the effect of the majorityof zeros in the most probable inputs. The toggling is performed by toggling thecontents of the configuration SRAM cells in the logic block that generates thesesignals. The choice of which signals to toggle is based on the probabilities of thenext most probable inputs. If a certain signal appears ‘0’ more than once in the firstfive most probable inputs states, that it has a higher probability of being selected byLPR to be toggled. If the five most probable input states have static probabilitiesgiven by P1,2,3,4,5,, and the value of the input j in input state i is given by Ij,i. Theinputs selected for toggling are those the maximizemax∀j5∑i=0Ij,i × Pi . (6.4)6.2.1.4 Unutilized Logic ResourcesThe unutilized logic resources should always be placed in a low-leakage state toavoid wasting leakage current. From the discussion presented in Section 6.1 andsummarized in Figure 6.4(b) and Table 6.1, the lowest leakage state occurs when allthe SRAM cells store ‘0’. In addition, the input to the inverters that generate thecontrol signals inside the logic blocks should be connected to VDD. Since FPGAshave the flexibility to connect any input inside the logic blocks to either of the supplyrails, then this phase of LPR guarantees placing the unutilized logic resources in alow-leakage mode without incurring any physical costs.1206.2.2 Routing Switches Pin Reordering (RPR) AlgorithmThe routing architecture assumed in this work is the disjoint architecture with aflexibility of three. The RPR algorithm is composed of three phases.6.2.2.1 Input Pins PaddingThe input padding phase of the RPR algorithm is similar to that of the LPRalgorithm. If one of the routing multiplexers has one of its inputs left floating,that input is connected to a constant signal in such a way to reduce the leakagepower in that multiplexer, according to the guidelines in Section 6.1. Similar tothe logic phase, these multiplexers have the flexibility to generate constant signalsfrom within, thus reducing the need for extra hardware. However, the inputs tothe drains of the pass-transistors of the routing switches are not known beforehand,unlike the logic blocks which are dictated by the contents of the configuration SRAMcells. This work depends on the static input probabilities of the routed signals toestimate the most probable value of the signal and based on that pad the vacantinput signals accordingly to minimize the leakage power dissipation.6.2.2.2 Most Probable StatesSome of the routing resources employed in FPGAs are buffered routing switches,where the output of the multiplexer is connected to a buffer to transmit the signalfor a long distance across the FPGA fabric. However, these buffered switches areprone to the input dependency of the leakage power dissipation in the buffers,especially since they are designed with large dimensions. This observation is thecore of the earlier work proposed in [53].The leakage power dissipation in the buffers can be minimized by avoiding thestate with the highest leakage. Inside the buffer, both inverters dissipate leakagepower dissipation, however, the second inverter dissipates more leakage power be-cause it is designed with a larger size. Consequently, the desired low-leakage stateis that of the second inverter. According to that, the low-leakage state is when theinput to the buffer is ‘1’. Since the input to the buffer is not previously known,static probability is used to estimate the most probable input to all the bufferedrouting switches. If the most probable input is not ‘1’, then the input is invertedsimply by inverting the values of the logic blocks connected to that net. It is note-worthy that this phase of the RPR algorithm is applied first since it might affect the121actions taken by input padding phase. The algorithm used in this work is similarto the one presented in [53].6.2.2.3 Unutilized Routing ResourcesSimilar to the LPR algorithm, the RPR is applied to place all the unutilized routingresources in a low-leakage state. This is performed by generating constant signalswithin the unused routing multiplexers to manipulate them into the lowest leakagestate.6.3 Experimental ResultsThe proposed leakage power reduction pin reordering algorithm is tested on a 90nmCMOS process using several FPGA benchmarks [28]. The algorithm takes as aninput a readily synthesized circuit and then rearranges the inputs to each LUTto result in the minimum leakage power dissipation. The benchmark circuits aresynthesized using the SIS sequential circuit synthesis tool [126]. Both the LPRand RPR algorithms are integrated into the VPR CAD flow [28] according to theflowchart shown in Figure 6.7. The leakage power modeling is performed usingthe proposed power modeling approach presented in Chapter 4 to take the statedependency of leakage power into consideration.The proposed pin reordering algorithm is applied to several FPGA benchmarksand the percentage leakage savings are listed in Table 6.2 for a 4-input LUT com-pared to the control case. Moreover, Table 6.2 also lists the total leakage savingsachieved by [53]. The total average leakage savings is around 50% across all thebenchmarks tested, while that achieved by [53] is around 24.72%. It can be easilyshown that the proposed algorithm outperforms that of [53] in terms of leakagesavings. In addition, Table 6.2 shows how the leakage savings due to the LPR al-gorithm vary with the number of inputs to the logic blocks. The larger the numberlogic blocks with inputs less than 4, the higher the leakage savings due to LPR dueto its padding phase.Figure 6.10 shows a breakdown of the leakage savings due to the LPR phase.It can be shown that the maximum savings are generated by the input swappingphase. Figure 6.10 shows that very small leakage savings originate from placingthe unutilized logic into a low-leakage state because the benchmarks tested weremapped into the smallest FPGA square array that can hold them, thus resulting122Table 6.2: Leakage savings by the proposed pin reordering algorithm across severalFPGA benchmarks.BenchmarkPercentage of logic blocks with Avg Leakage Avg Leakage Tot. Leakage Avg Leakage2 inputs 3 inputs 4 inputsSavings in Savings in Savings Savings (%)Logic (%) Routing (%) (%) [53]alu4 0.07 0.29 0.62 60.92 40.76 50.3 20.7apex4 0.01 0.42 0.55 57.34 41.35 48.9 26.5des 0.05 20 0.74 57.28 45.74 50.96 29.99dsip 0 0 0.98 20.13 45.72 33.16 20.86frisc 0.07 0.27 0.64 68.34 42.18 54.61 26.16pdc 0.01 0.21 0.76 52.07 42.28 47.18 24.5s298 0.08 0.22 0.68 58.84 42.27 50.12 26.85s38584.1 0.25 0.18 0.53 79.48 43.79 61.49 16.48spla 0.01 0.24 0.74 53.78 42.8 48.02 21.2apex2 0.06 0.31 0.62 56.68 41.51 48.78 30.36bigkey 0.2 0 0.79 64.08 43.43 53.28 28.69clma 0.06 0.24 0.69 49.91 42.6 46 17.79diffeq 0.09 0.29 0.61 67.87 41.32 53.8 27.02elliptic 0.12 0.28 0.59 60.01 44.07 51.27 27.19ex5p 0.04 0.21 0.74 40.80 41.27 41.04 36.7misex3 0.04 0.35 0.59 66.08 39.29 52.2 18.7s38417 0.04 0.41 0.52 57.10 43.74 50.27 18.83seq 0.07 0.33 0.59 68.44 41.72 54.2 24.7tseng 0.12 0.27 0.6 70.58 43.47 56.05 19.18ex1010 0.04 0.42 53 69.84 41.09 54.09 31.9Average 58.98 42.38 50.29 24.72in the absolute minimum unutilized logic resources. It should be noted that if thebenchmarks were mapped into more practical FPGA sizes, the percentage leakagesavings in the unutilized resources would increase notably. Figure 6.10: Leakage savings breakdown in logic blocks.The leakage power savings achieved using RPR breakdown is shown in Figure6.11. It can be noticed that the average savings in the unutilized routing resourcesis larger than that resulting for the logic resource. This is mainly because thepercentage of unutilized routing resources is usually larger than that of the logic123resources. Another observation is that the percentage leakage savings in the invert-ers is larger in the routing resources, which can be justified by the fact that theinverters used in the routing resources are of larger sizes than those used in thelogic resources, thus they consume larger leakage. Figure 6.11: Leakage savings breakdown in the routing resources.6.3.1 Pin Reordering and PerformanceThe pin swapping algorithm results in changing the VTH of the transistors in thepass transistor multiplexers due to the DIBL and body effects previously explained.Its main aim is to have a net increase in VTH to result in subthreshold leakagesavings. As a result, the delay through these multiplexers ends up increasing.In order to investigate the impact of changing the input ordering on the designperformance, several SPICE simulations were performed to calculate the averagedelay through the pass transistor multiplexer for all the possible input combinations.A look-up table is then structured for all the possible delays. To quantify theincrease in delay due to the proposed algorithms, the delay across the critical pathof the resulting designs are compared to those designed using the regular VPRand the performance penalty is plotted in Figure 6.12. It can be seen that theperformance penalty is always less 3% across all benchmarks tested.In another experiment, the algorithm was applied in such a way to avoid chang-ing the logic blocks and routing resources along the benchmark critical path. Thecritical path is identified using the state dependent delay look-up table explainedabove. Logic blocks and routing resources along the critical path are marked as donot touch for the LPR and RPR algorithms not to change them. This version ofthe algorithm is called No-change for the Critical Path (NCP). The NCP versionresults in less leakage savings than those recorded in Table 6.2. The leakage savingsresulting from the NCP versions are plotted in Figure 6.13 for all the benchmarks124 ! " ##$ %&' (&)*+,%$ %+*-. /0 12Figure 6.12: Performance penalty due to the proposed algorithm.tested. The horizontal line represents the average of the leakage reduction, which isaround 49.14%, which is slightly less than the average savings in Table 6.2 (50.29%). ! " # ! " $ %%& '() (*'+ (,- .*/0123456789:;Figure 6.13: Leakage savings to avoid affecting the performance.In another experiment, instead of leaving the logic and routing resources alongthe critical path unchanged, the pin swapping algorithm is applied to actually125increase the multiplexers Vth. As a result, the leakage power along the critical pathincreases, while the delay along it is reduced. This provides a means of trading offsome of the leakage savings to improve the circuit performance. This version of thealgorithm is called Reduce the Critical Path (RCP). Figure 6.14 plots the percentageleakage savings as well as the improvement in the design performance for eachbenchmark achieved by the RCP version. The average performance improvementis 2.4% while the average reduction in leakage savings is 47.7%.6.3.2 Pin Reordering and Technology ScalingBased on the ITRS report [1], both types of leakage currents are expected to in-crease significantly with the technology scaling as shown in Figure 6.15. However,the increase in the gate leakage current is expected to be steeper resulting in gateleakage current exceeding subthreshold leakage current in future CMOS technolo-gies.The minimum leakage state depends heavily on the relative magnitude of thesubthreshold leakage and gate leakage currents. Hence, it is expected that the min-imum leakage states will change for each technology. In the next set of experiments,the minimum leakage state is evaluated for several future technology nodes [124]using the BSIM4 leakage model. The results are presented in Figure 6.16. It canbe noticed that the state where the input and the output of the multiplexer aregiven by ‘0’ is no longer the minimum leakage states for technologies beyond the90nm. This is because this state has the maximum gate leakage current, so oncethe contribution of gate leakage current starts to dominate the total leakage cur-rent, the total leakage of that state will increase. The next observation is that asthe technology is scaled down, the body effect starts to have a smaller effect onthe device Vth, hence, the total leakage of the state where the input and outputare given by ‘1’ starts to increase. Moreover, the gate leakage of that state is thesecond highest gate leakage current achievable.6.4 ConclusionIn this Chapter, a leakage reduction algorithm is proposed for FPGAs without anyphysical or performance penalties by employing the input dependency of leakagepower. Input reordering is used to place the logic and routing resources in theirlowest leakage state. The proposed methodology targets both the logic and routing126 ! " # ! " $ %%& '() (*'+ (,- .*/0123456789:;(a) Leakage savings for the RCP version. ! " ##$ %&' (&)*+,%- ).&(/%)%+0123456789:;<(b) Performance improvement for the RCP version.Figure 6.14: Trading leakage savings to reduce critical path delay in RCP.resources using the LPR and RPR algorithms, respectively. The newly developedalgorithm achieves an average leakage savings of 50%. Another version of theproposed algorithm is also developed that results in a performance improvement of2.4%, while achieving an average leakage reduction of 47.7%.127 I gatedensity (A/cm2)I sub(μA/μm)Technology Node Figure 6.15: Leakage current vs. technology.0 VDD - Vth0 VDDVDD VDD - Vth0 0Increasing Ileak(a) 90nm.0 VDD - Vth0 VDDVDD VDD - Vth0 0Increasing Ileak(b) 65nm and 45nm.0 VDD - Vth0 VDDVDD VDD - Vth0 0Increasing Ileak(c) 32nm and 22nm.Figure 6.16: Total leakage dominant states in FPGA pass transistor devices.128Chapter 7Conclusions and Future Work7.1 ConclusionsThis thesis proposed several methodologies for leakage power reduction in mod-ern nanometer FPGAs. The use of supply gating using Multi-Threshold CMOS(MTCMOS) techniques was proposed to enable turning OFF the unused resourcesof the FPGA, which are estimated to be close to 30% of the total FPGA area.Moreover, the utilized resources are allowed to enter a sleep mode dynamically dur-ing run-time depending on certain circuit conditions. Several new activity profilingtechniques (CAP, LAP, and R-LAP) were proposed to identify the FPGA resourcesthat will share common idleness periods, such that these resources will be turnedOFF together. To increase the benefits from the MTCMOS FPGA architecture,new packing techniques (AT-VPack, FAT-VPack, and T-MTCMOS) were proposedto include the logic blocks activities and pack those with similar activity profile to-gether. The proposed techniques were applied to several FPGA benchmarks, andit was found out that the combination of R-LAP and T-MTCMOS for activity andpacking algorithms, respectively, yields the most leakage savings while incurring theminimum performance penalty. On average, the R-LAP and T-MTCMOS combi-nation yields about 52% leakage savings, while the performance loss affecting thecritical paths was kept at 3%.Another techniques proposed in this thesis for leakage power reduction in FP-GAs is the pin reordering algorithm. The pin reordering algorithm makes use ofthe input state dependency of leakage power to place as much as possible of theFPGA circuits in a low leakage mode without incurring and physical or perfor-mance penalties. The guidelines for finding the lowest leakage power dissipation129mode were derived and it was shown how they vary with every process node depend-ing on the relative magnitude of subthreshold and gate leakage power components.The proposed pin reordering technique was applied to several FPGA benchmarksand resulted in an average of 50% leakage power savings. Furthermore, anotherversion of the proposed algorithm is also developed that results in a performanceimprovement of 2.4%, while achieving an average leakage reduction of 47.7%.In order to quantify the amount of power savings achieved by the proposed leak-age reduction techniques, an accurate power model for FPGAs is developed. Thenew power model considers both dynamic and leakage power dissipation. Moreover,glitching power of FPGA designs is also calculated. Furthermore, spatial correlationbetween design signals is also accounted for to calculate the total power dissipationin FPGAs. The accuracy of the model is within 10% of HSpice simulations whilespatial independence approaches are within 25% of HSpice.7.2 Future WorkWhile this thesis attempted to provide practical methods for leakage power reduc-tion in modern FPGAs, it provides a road to a bigger project that requires furtherresearch. The first goal of any future work would be to apply the proposed MTC-MOS design methodology to existing FPGA macros. FPGA vendors provide theirusers with ready-made designed macros that implement specific functionality, suchas adders and multipliers. These macros have pre-known functionality and theycan be designed easily using the proposed MTCMOS techniques to provide a low-leakage alternative for power sensitive applications. Along the same line of thought,some new FPGA macros can also be designed that serve a certain consumer market.Examples of these macros include MPEG and JPEG encoders/decoders. Finally,the MTCMOS techniques proposed in this thesis can be modified to be implementedin the ASIC design domain.A second area for future research is to investigate the impact of parameter vari-ations on the proposed leakage reduction techniques. Parameter variations affectCMOS designs by reducing the final yield. The impact of parameter variationsincreases as the device feature size is scaled down. For future CMOS technologies,there is a need to design low power design techniques that are immune to parametervariations. It should be noted that leakage power is very sensitive to any small vari-ations in the device parameters. Moreover, future FPGA power models should beable to calculate total power dissipation under the impact of parameter variations.130A third area for possible future research is to develop an analytical methodologyto calculate leakage power dissipation inside the FPGA logic blocks under all inputconfigurations. In this thesis, lookup tables resulting from HSpice simulations wereused both in the developed power model and pin reordering algorithm. Theselookup tables can be replaced by the analytical method to speed up the setup phasesof these algorithms while providing portability over as much CMOS technologiesas possible.131Bibliography[1] The International Technology Roadmap for Semiconductors website. [Online].Available: http://public.itrs.net[2] S. Borkar, “Design Challenges of Technology Scaling,” IEEE Micro, vol. 19,no. 4, pp. 23–29, 1999.[3] B. Zahiri, “Structured ASICs: Opportunities and Challenges,” in Proc. ofIntl. Conf. on Computer Design, 2003, pp. 404–409.[4] R. R. Taylor and H. Schmit, “Creating a Power-Aware Structured ASIC,” inProc. of Intl. Symp. on Low Power Electronics and Design, 2004, pp. 74–77.[5] K. J. Han, N. Chan, S. Kim, B. Leung, V. Hecht, B. Cronquist, D. Shum,A. Tilke, L. Pescini, M. Stiftinger, and R. Kakoschke, “Flash-based FieldProgrammable Gate Array Technology With Deep Trench Isolation,” in Proc.of IEEE Custom Integrated Circuits Conf., 2007, pp. 89–91.[6] S. D. Brown, “An Overview of Technology, Architecture and CAD Tools forProgrammable Logic Devices,” in Proc. of IEEE Custom Integrated CircuitsConf., 1994, pp. 69–76.[7] J. Greene, E. Hamdy, and S. Beal, “Antifuse Field Programmable Gate Ar-rays,” Proc. IEEE, vol. 81, no. 7, pp. 1042–1056, July 1993.[8] E. Ahmed and J. Rose, “The Effect of LUT and Cluster Size on Deep-Submicron FPGA Performance and Density,” in Proc. of ACM Intl. Symp.on Field Programmable Gate Arrays, 2000, pp. 3–12.[9] J. Rose, R. J. Francis, D. Lewis, and P. Chow, “Architecture of Field-Programmable Gate Arrays: The Effect of Logic Block Functionality on AreaEfficiency,” IEEE J. Solid-State Circuits, vol. 25, no. 5, pp. 1217–1225, Oct.1990.132[10] Altera Corp. Stratix III Device Handbook. [Online]. Available:http://www.altera.com/literature/hb/stx3/stratix3 handbook.pdf[11] Xilinx Inc. Vertix-5 FPGA User Guide. [Online]. Available:http://www.xilinx.com/support/documentation/user guides/ug190.pdf[12] Actel Corp. ProASIC3 Handbook. [Online]. Available:http://www.actel.com/documents/PA3 HB.pdf[13] J. Rose and S. Brown, “Flexibility of Interconnection Structures for Field-Programmable Gate Arrays,” IEEE J. Solid-State Circuits, vol. 26, no. 3, pp.277–282, 1991.[14] J. Cong and M. Smith, “A Parallel Bottom-Up Clustering Algorithm withApplications to Circuit Partitioning in VLSI Design,” in Proc. of IEEE/ACMDesign Automation Conf., 1993, pp. 755–760.[15] J. Cong, J. Peck, and Y. Ding, “Rasp: A general logic synthesis system forsram-based fpgas,” in Proc. of IEEE/ACM Design Automation Conf., 1996,pp. 137–143.[16] J. Cong, C. Wu, and Y. Ding, “Cut ranking and pruning: Enabling a generaland efficient fpga mapping solution,” in Proc. of ACM Intl. Symp. on FieldProgrammable Gate Arrays, 1999, pp. 29–35.[17] A. Ling, D. P. Singh, and S. D. Brown, “Fpga technology mapping: A studyof optimality,” in Proc. of IEEE/ACM Design Automation Conf., 2005, pp.427–432.[18] A. Marquardt, V. Betz, and J. Rose, “Using Cluster-Based Logic Blocks andTiming-Driven Packing to Improve FPGA Speed and Density,” in Proc. ofACM Intl. Symp. on Field Programmable Gate Arrays, 1999, pp. 37–46.[19] J. Cong, L. Hargen, and A. B. Kahng, “Random Walks for Circuit Cluster-ing,” in Proc. of IEEE Intl. Conf. on Application Specific Integrated Circuits,1991, pp. 14–21.[20] J. Cong and S. K. Lim, “Edge Separability Based Circuit Clustering with Ap-plication to Circuit Partitioning,” in Proc. of IEEE/ACM Asia South PacificDesign Automation Conf., 2000, pp. 429–434.133[21] L. W. Hagen and A. B. Kahng, “Combining Problem Reduction and AdaptiveMulti-Start: a New Technique for Superior Iterative Partitioning,” IEEETrans. Computer-Aided Design, vol. 16, no. 7, pp. 709–717, July 1997.[22] D. J.-H. Huang and A. B. Kahng, “When Clusters Meet Partitions: NewDensity-Based Methods for Circuit Decomposition,” in Proc. of EuropeanDesign and Test Conf., 1995, pp. 60–64.[23] A. E. Dunlop and B. W. Kernighan, “A Procedure for Placement of StandardCell VLSI Circuits,” IEEE Trans. Computer-Aided Design, vol. 4, no. 1, pp.92–98, 1985.[24] D. J.-H. Huang and A. B. Kahng, “Partitioning-Based Standard-Cell GlobalPlacement with an Exact Objective,” in Proc. of ACM Intl. Symp. on PhysicalDesign, 1997, pp. 18–25.[25] J. M. Kleinhans, G. Sigl, F. M. Johannes, and K. J. Antreich, “GOR-DIAN: VLSI Placement by Quadratic Programming and Slicing Optimiza-tion,” IEEE Trans. Computer-Aided Design, vol. 10, no. 3, pp. 356–365, Mar.1991.[26] A. Srinivasan, K. Chaudhary, and E. S. Kuh, “Ritual : A Performance DrivenPlacement Algorithm for Small Cell ICs,” in Proc. of Intl. Conf. on ComputerAided Design, 1991, pp. 48–51.[27] A. Marquardt, V. Betz, and J. Rose, “Timing-Driven Placement for FPGAs,”in Proc. of ACM Intl. Symp. on Field Programmable Gate Arrays, 2000, pp.203–213.[28] V. Betz, J. Rose, and A. Marquardt, Architecture and CAD for Deep-Submicron FPGAs. Norwell, MA: Kluwer Academic Publishers, 1999.[29] C. Sechen and A. Sangiovanni-Vincentelli, “The TimberWolf Placement andRouting Package,” IEEE J. Solid-State Circuits, vol. 20, no. 4, pp. 510–522,Apr. 1985.[30] S. Kirpatrick, C. D. Gelatt, and M. P. Vecchi, “Optimization by SimulatedAnnealing,” Science, vol. 220, 4598, pp. 671–680, 1983.[31] R. B. Hitchcock, “Timing Verification and the Timing Analysis Program,” inProc. of IEEE/ACM Design Automation Conf., 1982, pp. 594–604.134[32] D. Lewis, E. Ahmed, G. Baeckler, V. Betz, M. Bourgeault, D. Cashman,D. Galloway, M. Hutton, C. Lane, A. Lee, P. Leventis, S. Marquardt, C. Mc-Clintock, K. Padalia, B. Pedersen, G. Powell, B. Ratchev, S. Reddy, J. Schle-icher, K. Stevens, R. Yuan, R. Cliff, and J. Rose, “The Stratix II logic androuting architecture ,” in Proc. of ACM Intl. Symp. on Field ProgrammableGate Arrays, 2005, pp. 14–20.[33] D. Lewis, V. Betz, D. Jefferson, A. Lee, C. Lane, P. Leventis, S. Marquardt,C. McClintock, B. Pedersen, G. Powell, S. Reddy, C. Wysocki, R. Cliff, andJ. Rose, “The StratixTM Routing and Logic Architecture,” in Proc. of ACMIntl. Symp. on Field Programmable Gate Arrays, 2003, pp. 12–20.[34] G. G. Lemieux and S. D. Brown, “A Detailed Routing Algorithm for Allocat-ing Wire Segments in Field-Programmable Gate Arrays,” in Proc. of ACMPhysical Design Workshop, 1993, pp. 215–226.[35] Y.-W. Chang, D. F. Wong, and C. K. Wong, “Universal Switch Modules forFPGA Design,” ACM Trans. Des. Autom. Electron. Syst., vol. 1, no. 1, pp.80–101, Jan. 1996.[36] S. J. Wilton, “Architectures and algorithms for field-programmable gatearrays with embedded memory,” Ph.D. dissertation, Univ. of Toronto,Toronto, 1997. [Online]. Available: http://www.eecg.toronto.edu/ ja-yar/pubs/theses/Wilton/StevenWilton.pdf[37] M. I. Masud and S. J. Wilton, “A New Switch Block for Segmented FPGAs,”in Proc. of Intl. Workshop on Field Programmable Logic and Applications,1999, pp. 274–281.[38] C. Ebeling, L. McMurchie, S. A. Hauck, and S. Burns, “Placement AndRouting Tools For The Triptych FPGA,” IEEE Trans. VLSI Syst., vol. 3,no. 4, pp. 473–482, Dec. 1995.[39] G. E. Moore, “Lithography and the Future of Moore’s Law,” in Proc. Opti-cal/Laser Microlithography VIII, vol. 2440, 1995, pp. 2–17.[40] ——, “No Exponential is Forever: But “Forever” Can Be Delayed,” in Dig.of Tech. Papers IEEE Intl. Solid-State Circuits Conf., 2003, pp. 2–17.[41] E. Kusse and J. Rabaey, “Low-Energy Embedded FPGA Structures,” in Proc.of Intl. Symp. on Low Power Electronics and Design, 1998, pp. 155–160.135[42] V. George, H. Zhang, and J. Rabaey, “The Design of a Low Energy FPGA,”in Proc. of Intl. Symp. on Low Power Electronics and Design, 1999, pp. 188–193.[43] J. Lamoureux and S. Wilton, “On the Interaction Between Power-AwareFPGA CAD Algorithms,” in Proc. of Intl. Conf. on Computer Aided Design,2003, pp. 701–708.[44] J. Anderson and F. N. Najm, “Power-Aware Technology Mapping for LUT-Based FPGAs,” in Proc. of IEEE Intl. Conf. on Field-Programmable Tech-nology, 2002, pp. 211–218.[45] J. Lamoureux, G. G. Lemieux, and S. J. E. Wilton, “GlitchLess: An ActiveGlitch Minimization Technique for FPGAs,” in Proc. of ACM Intl. Symp. onField Programmable Gate Arrays, 2007, pp. 156–165.[46] K. Roy, S. Mukhopadhyay, and H. Mahmoodi-Meimand, “Leakage Cur-rent Mechanisms and Leakage Reduction Techniques in Deep-SubmicrometerCMOS Circuits,” Proc. IEEE, vol. 91, no. 2, pp. 305–327, Feb 2003.[47] I. Kuon and J. Rose, “Measuring the Gap Between FPGAs and ASICs,” inProc. of ACM Intl. Symp. on Field Programmable Gate Arrays, 2006, pp.21–30.[48] T. Tuan and B. Lai, “Leakage Power Analysis of a 90nm FPGA,” in Proc. ofIEEE Custom Integrated Circuits Conf., 2003, pp. 57–60.[49] F. Li, Y. Lin, L. He, and J. Cong, “FPGA Power Reduction Using Config-urable Dual-Vdd,” in Proc. of IEEE/ACM Design Automation Conf., 2004,pp. 735–740.[50] F. Li, Y. Lin, and L. He, “Vdd Programmability to Reduce FPGA Intercon-nect Power,” in Proc. of Intl. Conf. on Computer Aided Design, 2004, pp.760–765.[51] F. Li, Y. Lin, L. He, and J. Cong, “Low-Power FPGA Using Pre-defined Dual-Vdd/Dual-Vt Fabrics,” in Proc. of ACM Intl. Symp. on Field ProgrammableGate Arrays, 2004, pp. 42–50.[52] N. Azizi and F. Najm, “Look-Up Table Leakage Power Reduction for FP-GAs,” in Proc. of IEEE Custom Integrated Circuits Conf., 2005, pp. 187–190.136[53] J. Anderson, F. N. Najm, and T. Tuan, “Active Leakage Power Optimiza-tion for FPGAs,” in Proc. of ACM Intl. Symp. on Field Programmable GateArrays, 2004, pp. 33–41.[54] J. H. Anderson and F. N. Najm, “Active Leakage Power Optimization ForFPGAs,” IEEE Trans. Computer-Aided Design, vol. 25, no. 3, pp. 423–437,2006.[55] A. Gayasen, Y. Tsai, N. Vijaykrishnan, M. Kandemir, M. J. Irwin, andT. Tuan, “Reducing leakage energy in fpgas using region-constrianed place-ment,” in Proc. of ACM Intl. Symp. on Field Programmable Gate Arrays,2004, pp. 51–58.[56] S. Gupta, J. Anderson, L. Farragher, and Q. Wang, “CAD Techniques forPower Optimization in Virex-5 FPGAs,” in Proc. of IEEE Custom IntegratedCircuits Conf., 2007, pp. 85–88.[57] A. Rahman and V. Polavarapuv, “Evaluation of Low-Leakage Design Tech-niques for Field Programmable Gate Arrays,” in Proc. of ACM Intl. Symp.on Field Programmable Gate Arrays, 2004, pp. 23–30.[58] J. Anderson and F. N. Najm, “Low-Power Programmable Routing Circuitryfor FPGAs,” in Proc. of Intl. Conf. on Computer Aided Design, 2004, pp.602–609.[59] A. Rahman, S. Das, T. Tuan, and A. Rahut, “Heterogeneous Routing Ar-chitecture for LowPower FPGA Fabric,” in Proc. of IEEE Custom IntegratedCircuits Conf., 2005, pp. 183–186.[60] A. Kumar and M. Anis, “A Leakage-Tolerant Dual-Vt CAD Flow for FP-GAs,” IEEE Trans. Computer-Aided Design, vol. 26, no. 1, pp. 53–66, Jan.2007.[61] F. N. Najm, “A Survey of Power Estimation Techniques in VLSI Circuits,”IEEE Trans. VLSI Syst., vol. 2, no. 4, pp. 446–455, Dec. 1994.[62] S. R. Vemuru and N. Scheinberg, “Short-circuit Power Dissipation EstimationFor CMOS Logic Gates,” IEEE Trans. Circuits Syst. I, vol. 41, no. 11, pp.762–765, Nov. 1994.[63] Q. Wang and S. B. Vrudhula, “On Short Circuit Power Estimation Of CMOSInverters,” Proc. of Intl. Conf. on Computer Design, pp. 70–75, 1998.137[64] E. Acar, R. Arunachalam, and S. R. Nassif, “Predicting Short Circuit Powerfrom Timing Models,” in Proc. of IEEE/ACM Asia South Pacific DesignAutomation Conf., 2003, pp. 277–282.[65] H. Fatemi, S. Nazarian, and M. Pedram, “A Current-based Method forShort Circuit Power Calculation under Noisy Input Waveforms,” in Proc. ofIEEE/ACM Asia South Pacific Design Automation Conf., 2007, pp. 774–779.[66] K. Poon, S. Wilton, and A. Yan, “A Detailed Power Model for Field-Programmable Gate Arrays,” ACM Trans. Des. Autom. Electron. Syst.,vol. 10, no. 2, pp. 279–302, Apr. 2005.[67] S. M. Kang, “Accurate Simulation of Power Dissipation in VLSI Circuits,”IEEE J. Solid-State Circuits, vol. 21, pp. 889–891, Oct. 1986.[68] G. Y. Yacoub and W. H. Ku, “An Accurate Simulation Technique for Short-Circuit Power Dissipation Based on Current Component Isolation,” in Proc.of Intl. Symp. on Circuits and Systems, 1989, pp. 1157–1161.[69] T. H. Krodel, “PowerPlay-Fast Dynamic Power Estimation Based on LogicSimulation,” in Proc. of Intl. Conf. on Computer Design, 1991, pp. 96–100.[70] F. Rouatbi, B. Haroun, and A. J. Al-Khalili, “Power Estimation Tool for Sub-Micron CMOS VLSI Circuits,” in Proc. of Intl. Conf. on Computer AidedDesign, 1992, pp. 204–209.[71] Tony D. Givargis, Frank Vahid, and Jörg Henkel, “Trace-driven System-level Power Evaluation of System-on-a-chip Peripheral Cores,” in Proc. ofIEEE/ACM Asia South Pacific Design Automation Conf., 2001, pp. 306–312.[72] A. K. Murugavel and N. Ranganathan, “Petri Net Modeling of Gate andInterconnect Delays for Power Estimation,” in Proc. of IEEE/ACM DesignAutomation Conf., 2002, pp. 455–460.[73] R. Burch, F. N. Najm, P. Yang, and T. N. Trick, “A Monte Carlo Approachfor Power Estimation,” IEEE Trans. VLSI Syst., vol. 1, no. 1, pp. 63–71,Mar. 1993.[74] M. G. Xakellis and F. N. Najm, “Statistical Estimation of the SwitchingActivity in Digital Circuits,” in Proc. of IEEE/ACM Design AutomationConf., 1994, pp. 728–733.138[75] A. M. Hill and S.-M. S. Kang, “Determining Accuracy Bounds for Simulation-Based Switching Activity Estimation,” IEEE Trans. Computer-Aided Design,vol. 15, no. 6, pp. 611–618, June 1996.[76] R. Marculescu, D. Marculescu, and M. Pedram, “Sequence Compaction forPower Estimation: Theory and Practice,” IEEE Trans. Computer-Aided De-sign, vol. 18, no. 7, pp. 973–993, July 1999.[77] A. Murugavel, N. Ranganathan, R. Chandramouli, and S. Chavali, “Least-Square Estimation of Average Power in Digital CMOS Circuits,” IEEE Trans.VLSI Syst., vol. 10, no. 1, pp. 55–58, Feb. 2002.[78] X. Liu and M. C. Papaefthymiou, “A Markov Chain Sequence Generator forPower Macromodeling,” IEEE Trans. Computer-Aided Design, vol. 23, no. 7,pp. 1048–1062, July 2004.[79] M. A. Cirit, “Estimating Dynamic Power Consumption of CMOS Circuits,”in Proc. of Intl. Conf. on Computer Aided Design, 1987, pp. 534–537.[80] F. N. Najm, “Transition Density: A New Measure of Activity in DigitalCircuits,” IEEE Trans. Computer-Aided Design, vol. 12, no. 2, pp. 310–323,Feb. 1993.[81] A. Ghosh, S. Devadas, K. Keutzer, and J. White, “Estimation of AverageSwitching Activity in Combinational and Sequential Circuits,” in Proc. ofIEEE/ACM Design Automation Conf., 1992, pp. 253–259.[82] R. Marculescu, D. Marculescu, and M. Pedram, “Efficient Power Estima-tion for Highly Correlated Input Streams,” in Proc. of IEEE/ACM DesignAutomation Conf., 1995, pp. 628–634.[83] ——, “Probabilistic Modeling of Dependencies During Switching ActivityAnalysis,” IEEE Trans. Computer-Aided Design, vol. 17, no. 2, pp. 73–83,Feb. 1998.[84] C.-Y. Tsui, M. Pedram, and A. M. Despain, “Efficient Estimation of DynamicPower Consumption Under a Real Delay Model,” in Proc. of Intl. Conf. onComputer Aided Design, 1993, pp. 224–228.[85] R. Marculescu, D. Marculescu, and M. Pedram, “Switching Activity AnalysisConsidering Spatiotemporal Correlations,” in Proc. of Intl. Conf. on Com-puter Aided Design, 1994, pp. 294–299.139[86] J. C. Costa, J. C. Monteiro, and S. Devadas, “Switching Activity EstimationUsing Limited Depth Reconvergent Path Analysis,” in Proc. of Intl. Symp.on Low Power Electronics and Design, 1997, pp. 184–189.[87] S. Bhanja and N. Ranganathan, “Switching Activity Estimation of VLSICircuits Using Bayesian Networks,” IEEE Trans. VLSI Syst., vol. 11, no. 4,pp. 558–567, Aug. 2003.[88] K. Weiß, C. Oetker, I. Katchan, T. Steckstor, and W. Rosenstiel, “PowerEstimation Approach for SRAM-Based FPGAs,” in Proc. of ACM Intl. Symp.on Field Programmable Gate Arrays, 2000, pp. 195–202.[89] L. Shang, A. S. Kaviani, and K. Bathala, “Dynamic Power Consumptionin VirtexTM-II FPGA Family,” in Proc. of ACM Intl. Symp. on Field Pro-grammable Gate Arrays, 2002, pp. 157–164.[90] V. Degalahal and T. Tuan, “Methodlogy for High Level Estimation of FPGAPower Consumption,” in Proc. of IEEE/ACM Asia South Pacific Design Au-tomation Conf., 2005, pp. 657–660.[91] J. H. Anderson and F. N. Najm, “Power Estimation Techniques in FPGAs,”IEEE Trans. VLSI Syst., vol. 12, no. 10, pp. 1015–1027, 2004.[92] K. Poon, A. Yan, and S. Wilton, “A Flexible Power Model for FPGAs,” inProc. of ACM Intl. Symp. on Field Programmable Gate Arrays, 2002, pp.312–321.[93] F. Li, D. Chen, L. He, and J. Cong, “Architecture Evaluation for Power-Effecient FPGAs,” in Proc. of ACM Intl. Symp. on Field Programmable GateArrays, 2003, pp. 175–184.[94] F. Li, Y. Lin, H. Lei, D. Chen, and J. Cong, “Power Modeling and Character-istics of Field Programmable Gate Arrays,” IEEE Trans. VLSI Syst., vol. 24,no. 11, pp. 1712–1724, 2005.[95] Y. Lin, F. Li, and L. He, “Power Modeling and Architecture Evaluation forFPGAs with Novel Circuits for Vdd Programmability,” in Proc. of ACM Intl.Symp. on Field Programmable Gate Arrays, 2005, pp. 199–207.[96] A. Kumar and M. Anis, “An Analytical State Dependent Leakage PowerModel for FPGAs,” in Proc. of Design, Automation, and Test in Europe,2006, pp. 612–617.140[97] T.-L. Chou and K. Roy, “Statistical Estimation of Sequential Circuit Activ-ity,” in Proc. of Intl. Conf. on Computer Aided Design, 1995, pp. 34–37.[98] H. Y. Lui, C. H. Lee, and R. H. Patel, “Power Estimation and ThermalBudgeting Methodlogy for FPGAs,” in Proc. of IEEE Custom IntegratedCircuits Conf., 2004, pp. 711–714.[99] Altera Corp. PowerPlay Early Power Estimator. [Online]. Available:http://www.altera.com/literature/ug/ug stx3 epe.pdf[100] Xilinx Inc. Xilinx Power Estimator User Guide. [Online]. Available:http://www.xilinx.com/products/design resources/power central/ug440.pdf[101] Actel Corp. IGLOO Power Calculator. [Online]. Available:http://www.actel.com/documents/IGLOOpowercalculator.zip[102] Altera Corp. PowerPlay Power Analysis. [Online]. Available:http://www.altera.com/literature/hb/qts/qts qii53013.pdf[103] Actel Corp. SmartPower v8.2 Users Guide. [Online]. Available:http://www.actel.com/documents/smartpower ug.pdf[104] H.-J. Wunderlich, “PROTEST: A Tool for Probabilistic Testability Analysis,”in Proc. of IEEE/ACM Design Automation Conf., 1985.[105] S. C. Seth, L. Pan, and V. D. Agrawal, “PREDICT - Probabilistic Estimationof Digital Circuit Testability,” in Dig. of Tech. Papers IEEE Intl. Symp. onFault-Tolerant Comp., 1985.[106] F. Maamari and J. Rajski, “A Reconvergent Fanout Analysis for EfficientExact Fault Simulation of Combinational Circuits,” in Dig. of Tech. PapersIEEE Intl. Symp. on Fault-Tolerant Comp., 1988.[107] S. Chakravarty and H. B. Hunt, “On Computing Signal Probability and De-tection Probability of Stuck-At Faults,” IEEE Trans. Comput., vol. 39, no. 11,pp. 1369–1377, Nov. 1990.[108] C.-Y. Tsui, M. Pedram, and A. M. Despain, “Exact and Approximate Meth-ods for Calculating Signal and Transition Probabilities in FSMs,” in Proc. ofIEEE/ACM Design Automation Conf., 1994, pp. 18–23.[109] Stratix III Device Handbook, Altera Corp. [Online]. Available:http://www.altera.com/literature/hb/stx3/stratix3 handbook.pdf141[110] P. Schneider and S. Krishnamoorthy, “Effects of Correlations on Accuracy ofPower Analysis - An Experimental Study,” in Proc. of Intl. Symp. on LowPower Electronics and Design, 1996, pp. 113–116.[111] J. Kao and A. Chandrakasan, “Dual-Threshold Voltage Techniques for Low-Power Digital Circuits,” IEEE J. Solid-State Circuits, vol. 35, no. 7, pp.1009–1018, July 2000.[112] S. Mutoh, T. Douseki, Y. Matsuya, T. Aoki, S. Shigematsu, and J. Ya-mada, “1-V Power Supply High-speed Digital Circuit Technology WithMultithreshold-voltage CMOS,” IEEE J. Solid-State Circuits, vol. 30, no. 8,pp. 847–854, Aug. 1995.[113] S. Shigematsu, S. Mutoh, Y. M. Y. Tanabe, and J. Yamada, “A 1-V High-Speed MTCMOS Circuit Scheme for Power-Down Application Circuits,”IEEE J. Solid-State Circuits, vol. 32, no. 6, pp. 861–869, June 1997.[114] M. Anis, S. Areibi, and M. Elmasry, “Design and Optimization of Multi-threshold CMOS (MTCMOS) Circuits,” IEEE Trans. Computer-Aided De-sign, vol. 22, no. 10, pp. 1324–1342, Oct. 2003.[115] Altera. Stratix Device Handbook, Volume 1. [Online]. Available:http://www.altera.com/literature/hb/stx/stratix handbook.pdf[116] Xilinx. Two Flows for Partial Reconfiguration: Mod-ule Based or Difference Based. [Online]. Available:http://direct.xilinx.com/bvdocs/publications/xapp290.pdf[117] Z. Hu, A. Buyuktosunoglu, V. Srinivasan, V. Zyuban, H. Jacobson, andP. Bose, “Microarchitectural Techniques for Power Gating of ExecutionUnits,” in Proc. of Intl. Symp. on Low Power Electronics and Design, 2004,pp. 32–37.[118] A. Rahman, S. Das, T. Tuan, and S. Trimberger, “Determination of PowerGating Granularity for FPGA Fabric,” in Proc. of IEEE Custom IntegratedCircuits Conf., 2006, pp. 9–12.[119] S. V. Kosonocky, M. Immediato, P. Cottrell, T. Hook, R. Mann, andJ. Brown, “Enchanced Multi-Threshold (MTCMOS) Circuits using VariableWell Bias,” in Proc. of Intl. Symp. on Low Power Electronics and Design,2001, pp. 165–169.142[120] H.-O. Kim, Y. Shin, H. Kim, and I. Eo, “Physical Design Methodol-ogy of Power Gating Circuits for Standard-Cell-Based Design,” in Proc. ofIEEE/ACM Design Automation Conf., 2006, pp. 109–112.[121] B. Calhoun, F. Honoré, and A. Chandrakasan, “A Leakage ReductionMethodology for Distributed MTCMOS,” IEEE J. Solid-State Circuits,vol. 39, no. 5, pp. 818–826, May 2004.[122] T. Tuan, S. Kao, A. Rahman, S. Das, and S. Trimberger, “A 90nm Low-PowerFPGA for Battery-Powered Applications,” in Proc. of ACM Intl. Symp. onField Programmable Gate Arrays, 2006, pp. 3–11.[123] D. A. James Kao, Anantha Chandrakasan, “Transistor Sizing Issues and Toolfor Multi-threshold CMOS Technology,” in Proc. of IEEE/ACM Design Au-tomation Conf., 1997, pp. 409–414.[124] The Berkeley Predictive Technology Model website. [Online]. Available:http://www-device.eecs.berkeley.edu/∼ptm/[125] R. S. Guindi and F. N. Najm, “Design Techniques for Gate-Leakage Reduc-tion in CMOS Circuits,” in Proc. of IEEE Intl. Symp. on Quality of ElectronicDesign, 2003, pp. 61–65.[126] E. M. Sentovich, K. J. Singh, L. Lavagno, C. Moon, R. Murgai, A. Saldanha,H. Savoj, P. R. Stephan, R. K. Brayton, and A. Sangiovanni-Vincentelli,“SIS: A System for Sequential Circuit Synthesis,” Department of ElectricalEngineering and Computer Science, University of California, Berkeley, CA,Tech. Rep. UCB/ERL M92/41, May 1992.143List of Publications Resulting from this Work1. H. Hassan, M. Anis, and M. Elmasry, “CAD Techniques for Leakage-TolerantMTCMOS FPGAs,” IEEE Transactions on VLSI, submitted for publication.2. H. Hassan, M. Anis, and M. Elmasry, “Total Power Modeling in FPGAsUnder Spatial Correlation,” IEEE Transactions on VLSI, accepted for pub-lication.3. H. Hassan, M. Anis, and M. Elmasry, “Input Vector Reordering for Leak-age Power Reduction in FPGAs,” IEEE Transactions on CAD, accepted forpublication.4. H. Hassan, M. Anis, and M. Elmasry, “A Timing Driven Algorithm for Leak-age Reduction in MTCMOS FPGAs,” in Proc. ACM Asia and South PacificDesign Automation Conference, 2007, pp. 678–683.5. H. Hassan, M. Anis, A. El Daher, and M. Elmasry, “Activity Packing in FP-GAs for Leakage Power Reduction,” in Proc. ACM/IEEE Design Automationand Test in Europe Conference, 2005, pp. 212–217.6. H. Hassan, M. Anis, and M. Elmasry, “A leakage-aware CAD flow for MTC-MOS FPGA architectures,” in Proc. ACM/IEEE International Symposiumon Low Power Electronics and Design, 2005, pp. 257–262.7. H. Hassan, M. Anis, and M. Elmasry, “Design Methodology and CAD Toolsfor Nanometer FPGAs: Optimization for Leakage Power,” in SIGDA Ph.D.Forum at the ACM/IEEE Design Automation Conference, 2008, (abstract -poster).8. H. Hassan, M. Anis, and M. Elmasry, “Leakage-aware Placement for FPGAs,”in Proc. ACM International Symposium on FPGAs, 2005, pp. 267 (abstract- poster).144

Low leakage techniques for FPGAs

Abstract

Extracted data

Low leakage techniques for FPGAs

Abstract

Extracted data

Related items

Related items