Singh / Shukla Low Power Hardware Synthesis from Concurrent Action-Oriented Specifications

1. Auflage 2010
ISBN: 978-1-4419-6481-6
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 154 Seiten

Human lives are getting increasingly entangled with technology, especially comp- ing and electronics. At each step we take, especially in a developing world, we are dependent on various gadgets such as cell phones, handheld PDAs, netbooks, me- cal prosthetic devices, and medical measurement devices (e.g., blood pressure m- itors, glucometers). Two important design constraints for such consumer electronics are their form factor and battery life. This translates to the requirements of reduction in the die area and reduced power consumption for the semiconductor chips that go inside these gadgets. Performance is also important, as increasingly sophisticated applications run on these devices, and many of them require fast response time. The form factor of such electronics goods depends not only on the overall area of the chips inside them but also on the packaging, which depends on thermal ch- acteristics. Thermal characteristics in turn depend on peak power signature of the chips. As a result, while the overall energy usage reduction increases battery life, peak power reduction in?uences the form factor. One more important aspect of these electronic equipments is that every 6 months or so, a newer feature needs to be added to keep ahead of the market competition, and hence new designs have to be completed with these new features, better form factor, battery life, and performance every few months. This extreme pressure on the time to market is another force that drives the innovations in design automation of semiconductor chips.

Autoren/Hrsg.

Singh, Gaurav

Shukla, Sandeep Kumar

Inhaltsverzeichnis

1;Preface;6
2;Acknowledgments;17
3;Contents;18
4;List of Figures;22
5;List of Tables;24
6;Acronyms;25
7;1 Introduction ;26
7.1;1.1 Motivation;26
7.2;1.2 High-Level Synthesis;27
7.2.1;1.2.1 CDFG-Based High-Level Synthesis;28
7.2.2;1.2.2 Esterel-Based High-Level Synthesis;30
7.2.3;1.2.3 CAOS-Based High-Level Synthesis;30
7.3;1.3 Low-Power Hardware Designs;31
7.3.1;1.3.1 Power-Aware High-Level Synthesis;32
7.4;1.4 Verification of Power-Optimized Hardware Designs;34
7.4.1;1.4.1 Verification Using CAOS;34
7.5;1.5 Problems Addressed;35
7.6;1.6 Organization;36
8;2 Related Work ;38
8.1;2.1 High-Level Synthesis;38
8.1.1;2.1.1 C-Based Languages and Tools;38
8.1.2;2.1.2 Other Languages and Tools;39
8.2;2.2 Low-Power High-Level Synthesis;39
8.2.1;2.2.1 Dynamic Power Reduction;39
8.2.2;2.2.2 Peak Power Reduction;42
8.2.3;2.2.3 Summary -- Low-Power High-Level Synthesis Work;43
8.3;2.3 Power Estimation Using High-Level Models;43
8.4;2.4 Verification of High-Level Models;46
8.4.1;2.4.1 SpecC;47
8.4.2;2.4.2 SystemC;47
8.4.3;2.4.3 Other Work;48
8.4.4;2.4.4 Summary -- High-Level Verification Work;48
9;3 Background ;50
9.1;3.1 CDFG-Based High-Level Synthesis;50
9.2;3.2 Concurrent Action-Oriented Specifications;51
9.2.1;3.2.1 Concurrent Execution of Actions;51
9.2.2;3.2.2 Mutual Exclusion and Conflicts;52
9.2.3;3.2.3 Hardware Synthesis;52
9.2.4;3.2.4 Example;53
9.3;3.3 Power Components;54
9.3.1;3.3.1 Average Power;54
9.3.2;3.3.2 Transient Characteristics of Power;55
9.3.3;3.3.3 Low-Power High-Level Synthesis;55
9.4;3.4 Complexity Analysis of Algorithms;56
9.4.1;3.4.1 NP-Completeness;56
9.4.2;3.4.2 Approximation Algorithm;56
9.5;3.5 Formal Methods for Verification;57
9.5.1;3.5.1 Model Checking;58
10;4 Low-Power Problem Formalization ;60
10.1;4.1 Definitions;60
10.2;4.2 Other Details;63
10.2.1;4.2.1 Schedule of a Design;63
10.2.2;4.2.2 Re-scheduling of Actions;64
10.2.3;4.2.3 Cost of a Schedule;64
10.2.4;4.2.4 Low-Power Goal;65
10.2.5;4.2.5 Factorizing an Action;65
10.3;4.3 Formalization of Low-Power Problems;66
10.3.1;4.3.1 Peak Power Problem;66
10.3.2;4.3.2 Dynamic Power Problem;66
10.3.3;4.3.3 Peak Power Problem Is NP-Complete;67
10.3.4;4.3.4 Dynamic Power Problem Is NP-Complete;67
11;5 Heuristics for Power Savings ;69
11.1;5.1 Basic Heuristics;70
11.1.1;5.1.1 Peak Power Reduction;70
11.1.2;5.1.2 Dynamic Power Reduction;72
11.1.3;5.1.3 Example Applications;74
11.2;5.2 Refinements of Above Heuristics;77
11.2.1;5.2.1 Re-scheduling of Actions;77
11.2.2;5.2.2 Factorizing and Re-scheduling of Actions;81
11.2.3;5.2.3 Functional Equivalence;83
11.2.4;5.2.4 Example Applications;86
12;6 Complexity Analysis of Scheduling in CAOS-Based Synthesis ;89
12.1;6.1 Related Background;90
12.1.1;6.1.1 Confluent Set of Actions;90
12.1.2;6.1.2 Peak Power Constraint;90
12.2;6.2 Scheduling Problems Without a Peak Power Constraint;90
12.2.1;6.2.1 Selecting a Largest Non-conflicting Subset of Actions;90
12.2.2;6.2.2 Constructing Minimum Length Schedules;94
12.3;6.3 Scheduling Problems Involving a Power Constraint;96
12.3.1;6.3.1 Packing Actions in a Time Slot Under Peak Power Constraint;97
12.3.2;6.3.2 Maximizing Utility Subject to a Power Constraint;99
12.3.3;6.3.3 Combination of Makespan and Power Constraint;100
12.3.4;6.3.4 Approximation Algorithms for MM-PP;103
12.3.5;6.3.5 Approximation Algorithms for MPP-M;105
13;7 Dynamic Power Optimizations ;107
13.1;7.1 Related Background;107
13.1.1;7.1.1 Clock-Gating of Registers;107
13.1.2;7.1.2 Operand Isolation;107
13.2;7.2 Clock-Gating of Registers;108
13.3;7.3 Insertion of Gating Logic;110
13.3.1;7.3.1 Other Versions of Algorithm 2;114
13.4;7.4 Experiment and Results;115
13.4.1;7.4.1 Algorithm 1;115
13.4.2;7.4.2 Algorithm 2;117
13.4.3;7.4.3 RTL Power Estimation;122
13.5;7.5 Summary;124
14;8 Peak Power Optimizations ;126
14.1;8.1 Related Background;127
14.2;8.2 Formalization of Peak Power Problem;129
14.3;8.3 Peak Power Reduction Algorithm;130
14.3.1;8.3.1 Handling Combinational Path Dependencies;131
14.4;8.4 Experiments and Results;133
14.4.1;8.4.1 Designs;133
14.4.2;8.4.2 Gate-Level Average Power and Peak PowerComparisons;134
14.4.3;8.4.3 Effects on Latency, Area, and Energy;134
14.4.4;8.4.4 RTL Activity Reduction;135
14.5;8.5 Summary;136
14.6;8.6 Issues Related to Proposed Algorithm;136
15;9 Verifying Peak Power Optimizations Using SPIN Model Checker ;137
15.1;9.1 Related Background;138
15.2;9.2 Formal Description of CAOS-Based High-Level Synthesis;140
15.2.1;9.2.1 Hardware Description;140
15.2.2;9.2.2 Scheduling of Actions;141
15.3;9.3 Correctness Requirements for CAOS Designs;144
15.3.1;9.3.1 AOA Semantics;144
15.3.2;9.3.2 Concurrent Semantics;144
15.3.3;9.3.3 Comparing Two Implementations;145
15.4;9.4 Converting CAOS Model to PROMELA Model;146
15.4.1;9.4.1 Why SPIN?;146
15.4.2;9.4.2 Generating PROMELA Variables and Processes;146
15.4.3;9.4.3 Adding Scheduling Information to PROMELA Model;146
15.4.4;9.4.4 Sample PROMELA Models;148
15.5;9.5 Formal Verification Using SPIN;150
15.5.1;9.5.1 Verifying Correctness Requirement 1 (CR-1);150
15.5.2;9.5.2 Verifying Correctness Requirement 2 (CR-2);150
15.5.3;9.5.3 Verifying Correctness Requirement 3 (CR-3);151
15.5.4;9.5.4 Sample Experiments;152
15.6;9.6 Summary;153
16;10 Epilogue ;162
17;References;165
18;Index;171