NDLI: Code optimization of parallel programs: evolutionary vs. revolutionary approaches

Please wait, while we are loading the content...

Perfdiff: a framework for performance difference analysis in a virtual machine environment

Fast liveness checking for ssa-form programs

Accurate critical path prediction via random trace construction

Latency-tolerant software pipelining in a production compiler

Removing redundancy via exception check motion

Spice: speculative parallel iteration chunk execution

Code optimization of parallel programs: evolutionary vs. revolutionary approaches

Automatic array inlining in java virtual machines

Near-optimal instruction selection on dags

Efficient fine-grained binary instrumentationwith applications to taint-tracking

Parallel-stage decoupled software pipelining

Fault-safe code motion for type-safe languages

Pipa: pipelined profiling and analysis on multi-core systems

Issues and challenges in compiling for graphics processors

Phase-based adaptive recompilation in a JVM

Comprehensive path-sensitive data-flow analysis

Branch-on-random

Modulo scheduling for highly customized datapaths to increase hardware reusability

Prefetching irregular references for software cache on cell

Program optimization space pruning for a multithreaded gpu

Parallelism by design: data analysis with sawzall

Prediction and trace compression of data access addresses through nested loop recognition

Cole: compiler optimization level exploration

Compiling for vector-thread architectures

Code optimization of parallel programs: evolutionary vs. revolutionary approaches

Content Provider	ACM Digital Library
Author	Sarkar, Vivek
Abstract	Code optimization has a rich history that dates back over half a century. Over the years, it has contributed deep innovations to address challenges posed by new computer system and programming language features. Examples of the former include optimizations for improved register utilization, instruction-level parallelism, vector parallelism, multiprocessor parallelism and memory hierarchy utilization. Examples of the latter include optimizations for procedural, object-oriented, functional and domain-specific languages as well as dynamic optimization for managed runtimes. These optimizations have contributed significantly to programmer productivity by reducing the effort that programmers need to spend on hand-implementing code optimizations and by enabling code to be more portable, especially as programming models and computer architectures change. While compiler frameworks are often able to incorporate new code optimizations in an evolutionary manner, there have been notable periods in the history of compilers when more revolutionary changes were necessary. Examples of such paradigm shifts in the history of compilers include interprocedural whole program analysis, coloring-based register allocation, static single assignment form, array dependence analysis, pointer alias analysis, loop transformations, adaptive profile-directed optimizations, and dynamic compilation. The revolutionary nature of these shifts is evidenced by the fact that production-strength optimization frameworks (especially those in industry) had to be rewritten from scratch or significantly modified to support the new capabilities. In this talk, we claim that the current multicore trend in the computer industry is forcing a new paradigm shift in compilers to address the challenge of code optimization of parallel programs, regardless of whether the parallelism is implicit or explicit in the programming model. All computers --- embedded, mainstream, and high-end --- are now being built from multicore processors with little or no increase in clock speed per core. This trend poses multiple challenges for compilers for future systems as the number of cores per socket continues to grow, and the cores become more heterogeneous. In addition, compilers have to keep pace with emerging parallel programming models embodied in a proliferation of new libraries and new languages. To substantiate our claim, we examine the historical foundations of code optimization including intermediate representations (IR's), abstract execution models, legality and cost analyses of IR transformations and show that they are all deeply entrenched in the von Neumann model of sequential computing. We discuss ongoing evolutionary efforts to support optimization of parallel programs in the context of existing compiler frameworks, and their inherent limitations for the long term. We then outline what a revolutionary approach will entail, and identify where its underlying paradigm shifts are likely to lie. We provide examples of past research that are likely to influence future directions in code optimization of parallel programs such as program dependence graphs, partitioning and scheduling of lightweight parallelism, synchronization optimizations, communication optimizations, transactional memory optimizations, code generation for heterogeneous accelerators, impact of memory models on code optimization, and general forms of data and computation alignment. Finally, we briefly describe the approach to code optimization of parallel programs being taken in the Habanero Multicore Software Research project at Rice University.
Starting Page	1
Ending Page	1
Page Count	1
File Format	PDF
ISBN	9781595939784
DOI	10.1145/1356058.1356087
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-04-06
Publisher Place	New York
Access Restriction	Subscribed
Subject Keyword	Multicore processors Parallel programs Code optimization
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in