Aiken / Banerjee / Kejariwal Instruction Level Parallelism

1. Auflage 2016
ISBN: 978-1-4899-7797-7
Verlag: Springer
Format: PDF
Kopierschutz: 1 - PDF Watermark

E-Book, Englisch, 269 Seiten

This book precisely formulates and simplifies the presentation of Instruction Level Parallelism (ILP) compilation techniques. It uniquely offers consistent and uniform descriptions of the code transformations involved. Due to the ubiquitous nature of ILP in virtually every processor built today, from general purpose CPUs to application-specific and embedded processors, this book is useful to the student, the practitioner and also the researcher of advanced compilation techniques. With an emphasis on fine-grain instruction level parallelism, this book will also prove interesting to researchers and students of parallelism at large, in as much as the techniques described yield insights that go beyond superscalar and VLIW (Very Long Instruction Word) machines compilation and are more widely applicable to optimizing compilers in general. ILP techniques have found wide and crucial application in Design Automation, where they have been used extensively in the optimization of performance as well as area and power minimization of computer designs.




Alex Aiken is the Alcatel-Lucent Professor and the current chair of the Computer Science Department at Stanford. His research interests include most areas of programming languages and compilers and particularly automated methods of analysis for both high performance and high reliability.
Utpal Banerjee has a PhD in mathematics from Carnegie-Mellon University and a PhD in computer science from the University of Illinois at Urbana-Champaign. He has taught at the University of Cincinnati, Arizona State University and the University of Illinois. Dr. Banerjee has served as a research staff member at Honeywell, Fairchild, Control Data and Intel corporations. His current affiliation is with the Department of Computer Science, University of California at Irvine. He has published a number of papers and books on restructuring compilers, including encyclopedia articles and a series of books on loop transformations. He is a fellow of the IEEE and a fellow of the ACM.Alexandru Nicolau's research is in the areas of Parallel Processing/ILP, and Embedded Systems/Design Automation. His interests focus on Computer Performance/power tradeoffs, parallelizing compilers, GPUs. His current work involves collaborations both within and outside UCI, most recently with researchers at Stanford, University of Michigan, UCLA, UCSD as part of a flagship NSF Expedition project, and a separate grant with UIUC. He authored over 300 peer-reviewed papers and several books. He is the Editor-in-Chief of the International Journal of Parallel Processing, and an IEEE Fellow.

Autoren/Hrsg.

Aiken, Alex

Banerjee, Utpal

Kejariwal, Arun

Nicolau, Alexandru

Inhaltsverzeichnis

1;Contents;6
2;List of Figures;10
3;List of Tables;13
4;Preface;14
5;Foreword;16
6;Acknowledgments;18
7;1 Introduction;19
7.1;1.1 Scope of the Book;19
7.2;1.2 Instruction-Level Parallelism;21
7.3;1.3 Outline of Topics;23
8;2 Overview of ILP Architectures;26
8.1;2.1 Historical Perspective;26
8.2;2.2 Superscalar and VLIW Machines;30
8.3;2.3 Early ILP Architectures;32
8.4;2.4 ILP Architectures in the 80's;37
8.5;2.5 ILP Architectures in the 90's;41
8.6;2.6 Itanium;52
8.6.1;2.6.1 The EPIC Philosophy;53
8.6.2;2.6.2 Itanium Architecture;55
9;3 Scheduling Basic Blocks;60
9.1;3.1 Introduction;60
9.2;3.2 Basic Concepts;61
9.3;3.3 Unlimited Resources;64
9.3.1;3.3.1 ASAP Algorithm;64
9.3.2;3.3.2 ALAP Algorithm;66
9.4;3.4 Limited Resources;67
9.4.1;3.4.1 List Scheduling;67
9.4.2;3.4.2 Linear Analysis;69
9.5;3.5 An Example;70
9.6;3.6 More Algorithms;75
9.6.1;3.6.1 Critical Path Algorithm;75
9.6.2;3.6.2 Restricted Branch and Bound Algorithm;79
9.6.3;3.6.3 Force-Directed Scheduling;83
9.7;3.7 Limited Beyond Basic Block Optimization;90
10;4 Trace Scheduling;95
10.1;4.1 Introduction;95
10.2;4.2 Basic Concepts;98
10.2.1;4.2.1 Program Model;98
10.2.2;4.2.2 Traces;101
10.2.3;4.2.3 Dependence;103
10.2.4;4.2.4 Schedules;103
10.2.5;4.2.5 Program Transformation;105
10.3;4.3 Traces without Joins;106
10.4;4.4 General Traces;116
10.5;4.5 Trace Scheduling Algorithm;125
10.6;4.6 Picking Traces;128
11;5 Percolation Scheduling;133
11.1;5.1 Introduction;133
11.2;5.2 The Core Transformations;134
11.2.1;5.2.1 Delete Transformation;136
11.2.2;5.2.2 Move-op Transformation;137
11.2.3;5.2.3 Move-test Transformation;138
11.2.4;5.2.4 Unify Transformation;139
11.3;5.3 Remarks;142
11.3.1;5.3.1 Termination;143
11.3.2;5.3.2 Completeness;144
11.3.3;5.3.3 Confluence;145
11.4;5.4 Extensions;145
11.4.1;5.4.1 Migrate Transformation;145
11.4.2;5.4.2 Trailblazing;146
11.4.3;5.4.3 Resource-Constrained Percolation Scheduling;147
12;6 Modulo Scheduling;149
12.1;6.1 Introduction;149
12.2;6.2 Unrolling;151
12.3;6.3 Preliminaries;154
12.4;6.4 Modulo Scheduling Algorithm;156
12.4.1;6.4.1 Remarks;162
12.4.1.1;Sufficiency of simple cycles;162
12.4.1.2;Infeasibility of MII;164
12.4.2;6.4.2 Limitations;164
12.5;6.5 Modulo Scheduling with Conditionals;166
12.5.1;6.5.1 Hierarchical Reduction;166
12.5.2;6.5.2 Enhanced Modulo Scheduling;168
12.5.3;6.5.3 Modulo Scheduling with Multiple InitiationIntervals;171
12.6;6.6 Iterative Modulo Scheduling;172
12.6.1;6.6.1 The Algorithm;173
12.6.1.1;Determining Scheduling Priority;175
12.6.1.2;Determining Earliest Start Time;176
12.6.1.3;Determining Candidate Time Slots;176
12.7;6.7 Optimizations;177
12.7.1;6.7.1 Modulo Variable Expansion;177
12.7.2;6.7.2 Using Loop Unrolling to Enhance Modulo Scheduling;178
13;7 Software Pipelining by Kernel Recognition;182
13.1;7.1 Introduction;182
13.1.1;7.1.1 Basic Idea;184
13.2;7.2 The URPR Algorithm;185
13.3;7.3 OPT: Optimal Loop Pipelining of Innermost Loops;189
13.4;7.4 General Handling of Conditionals;195
13.4.1;7.4.1 Perfect Pipelining;195
13.4.1.1;Compaction;196
13.4.1.2;The Algorithm;198
13.4.2;7.4.2 Enhanced Pipeline-Percolation Scheduling;208
13.4.3;7.4.3 Optimal Software Pipelining with Control Flow;214
13.5;7.5 Nested Loops;215
13.6;7.6 Procedure Calls;216
14;8 Epilogue;219
15;Bibliography;223
16;Index;261