Chapter 1. Introduction1. Scripting Languages and High-Performance Computing2. Atlas Shrugged?3. The Many Core Revolution4. Synthetic Programming5. Evaluation and Contributions6. ConclusionChapter 2. Code Synthesis, Meta-Programming, and Library-Directed Optimization1. Run-time Code Generation2. Meta-Programming3. Special Topics: DSLs and Auto-Tuners4. ConclusionChapter 3. The Synthetic Programming Environment1. Design Goals2. Design Methodology3. The Synthetic Programming Environment4. Processor5. InstructionStream6. ISAs and Instructions7. Memory Abstractions8. ConclusionChapter 4. Synthetic Programming1. Synthetic Programming Basics2. Synthetic Components3. Managing Execution4. Data Sharing5. Communication6. Continual Specialization7. Working With Native Libraries8. Debugging9. A Note on Safety10. ConclusionChapter 5. Library-Defined Semantics and Optimizations1. Synthetic Components2. Variables3. The Iterator Library4. ConclusionChapter 6. Application: Interactive Particle System1. The Particle System2. Numeric Particle System3. Synthetic Particle System, Version 14. Synthetic Particle System, Version 25. Particle System Comparison6. ConclusionChapter 7. Application: Chemical Fingerprint Comparison1. The Chemical Fingerprint Application2. Implementations3. Results4. Related WorkChapter 8. Application: BLASTP on the Cell BE1. BLAST Overview2. Related Work3. Synthetic BLAST4. Discussion5. ConclusionChapter 9. Application: Interactive SPE Programming and Debugging1. Interactive SPE2. SPE Debugger3. ConclusionChapter 10. ConclusionBibliographySYNTHETIC PROGRAMMING: USER-DIRECTEDRUN-TIME CODE SYNTHESIS FOR HIGHPERFORMANCE COMPUTINGChristopher E. MuellerSubmitted to the faculty of the University Graduate Schoolin partial fulfillment of the requirementsfor the degreeDoctor of Philosophyin the Department of Computer ScienceIndiana UniversityMay 25, 2007Accepted by the Graduate Faculty, Indiana University, in partial fulfillment of the require-ments for the degree of Doctor of Philosophy.Andrew Lumsdaine, Ph.D.Mehmet Dalkilic, Ph.D.Dennis Gannon, Ph.D.Arun Chauhan, Ph.D.May 25, 2007DRAFT: April 23, 2 007 iiCopyright 2007Christopher E. MuellerAll rights reservedDRAFT: April 23, 2 007 iiiContentsChapter 1. Introduction 21. Scripting Languages and High-Performance Computing 32. Atlas Shrugged? 63. The Many Core Revolution 94. Synthetic Programming 105. Evaluation and Contributions 126. Conclusion 13Chapter 2. Code Synthesis, Meta-Programming, and Library-Directed Optimization 141. Run-time Code Generation 152. Meta-Programming 183. Special Topics: DSLs and Auto-Tuners 204. Conclusion 22Chapter 3. The Synthetic Programming Environment 231. Design Goals 232. Design Methodology 253. The Synthetic Programming Environment 264. Processor 275. InstructionStream 296. ISAs and Instructions 31DRAFT: April 23, 2 007 iv7. Memory Abstractions 368. Conclusion 38Chapter 4. Synthetic Programming 401. Synthetic Programming Basics 412. Synthetic Components 443. Managing Execution 454. Data Sharing 465. Communication 476. Continual Specialization 497. Working With Native Libraries 508. Debugging 529. A Note on Safety 5410. Conclusion 54Chapter 5. Library-Defined Semantics and Optimizations 551. Synthetic Components 562. Variables 603. The Iterator Library 644. Conclusion 75Chapter 6. Application: Interactive Particle System 761. The Particle System 772. Numeric Particle System 783. Synthetic Particle System, Version 1 804. Synthetic Particle System, Version 2 855. Particle System Comparison 866. Conclusion 87Chapter 7. Application: Chemical Fingerprint Comparison 881. The Chemical Fingerprint Application 89DRAFT: April 23, 2 007 v2. Implementations 913. Results 934. Related Work 94Chapter 8. Application: BLASTP on the Cell BE 951. BLAST Overview 962. Related Work 993. Synthetic BLAST 1004. Discussion 1135. Conclusion 114Chapter 9. Application: Interactive SPE Programming and Debugging 1151. Interactive SPE 1162. SPE Debugger 1193. Conclusion 123Chapter 10. Conclusion 124Bibliography 127DRAFT: April 23, 2 007 vi1AbstractScripting and interpreted languages are important tools for software engineering and areoften used in place of compiled languages for application development. While they enablea high level of developer productivity, their run-time environments limit the overall perfor-mance attainable with any given application. To develop performance-critical applications,developers continue to rely on compiled languages. However, recent changes in micropro-cessor design have begun to push the limits of compiled languages, making it difficult fordevelopers to fully utilize the available hardware resources.This thesis presents synthetic programming, a new approach to generating high-per-formance code and developing parallel applications from scripting languages. Syntheticprogramming is based on the synthetic programming environment, a collection of librariesthat provide direct access to low-level processing resources from the Python programminglanguage. Using the synthetic programming environment, developer’s can create applica-tions using machine-level instructions directly from Python, enabling a number of optimiza-tion strategies not readily available from compiled languages.In this thesis, synthetic programming is evaluated for feasibility and applicability. Todemonstrate the feasibility of synthetic programming, the synthetic programming envi-ronment was developed for three complete instruction sets (PowerPC, AltiVec/VMX, CellBE SPU) and two operating systems (OS X and Linux). Using the synthetic programmingenvironment on G5 and Cell Broadband Engine-based systems, synthetic programming isdemonstrated to be applicable for a broad range of common high-performance problemsfrom SIMD programming to automated loop optimization and multi-core application devel-opment.DRAFT: April 23, 2 0071IntroductionScripting and interpreted languages have become important tools for software develop-ment, with languages such as Visual Basic, C#, Java, Python, and Perl replacing compiledlanguages such as C, C++, and FORTRAN as the primary tools for application develop-ment. Scripting languages enable a high level of developer productivity through languagefeatures designed for usability and large collections of libraries for common tasks. Whileessential for general application development, scripting languages are based on run-timeenvironments that do not lend themselves to high-performance computing. To