A new Global Resource-constrained Percolation (GRiP) scheduling technique is presented for exploiting instruction level parallelism. Other techniques that have been proposed either have been prohibitively expensive in terms of computation or have limited parallelism. The GRiP technique has been implemented and simulation results are presented.

We develop a technique for extracting parallelism from ordinary (sequential) programs. The technique combines two fine-grain, instruction level code transformations to achieve effects similar to the wavefront method. Such effects were previously available only as transformations at coarser levels of granularity. By integrating the strengths of the wavefront method with the ability to extract fine-grain, irregular parallelism at the instruction level, our technique exploits previously untapped parallelism.

Chemistry Climate Model (CCM) codes are important \cite{csusft2cbooatpfccm} to understand how to mitigate global warming \cite{ifcoccmaapoape,pasgw}. However, to produce meaningful results, CCM codes require performance in the scale of PetaFlop (and soon ExaFlop) \cite{eesiteri} calculations. These scales have to be achieved within a reasonable power budget. It is therefore important to speedup as much as possible the execution of the already highly optimized state-of-the-art CCM codes.

Fast-J \cite{tfs} is a very important and widely used CCM code for simulations at different scales of magnitude, i.e., local, global and cosmic. Each scale of magnitude and its performance rely on a code, the Fast-J core code.

In this thesis, we speedup the Fast-J core, selecting and implementing some high-level compiler transformations, which are not efficiently performed by CPU compilers.

The optimizations consistently reach a performance speedup always greater than 4.5 for each scale of simulation. To quantify this performance improvement, we compare the execution times of the new optimizations with the execution times of the state-of-the-art, already highly optimized, CPU multi-threading code.

Graphics Processing Units (GPUs) are specialized hardware that was originally created to accelerate computer graphics and image processing. However, their highly parallel structure and their low costs per GFlop per Watt make them attractive as energy efficient performing architectures that accelerate other computationally-intensive scientific tasks.

NVIDIA is the market leader for GPUs. To protect its market leadership position, NVIDIA does not disclose its real assembly (ELF) Instruction Set Architectures (ISAs), keeps the compiler code closed, and does not disclose many of its low level GPU architectural features and machine behaviors. Optimization processes therefore become very time consuming and involves trials and errors.

In this thesis we design and implement a set of autonomic tools to reverse engineer the ELF ISAs and design and implement another set of autonomic tools to discover and quantify the GPU low level architectural features and machine behaviors. We also show that, even when implementing kernels using NVIDIA virtual assembly (PTX), more than 40% of the total performance is lost. This is compared to implementing the same kernels using the ELF ISAs and exploiting the insight yielded from the discovery, understanding, and quantification of the GPU low level architectural features and machine behaviors.

Multiple functional unit architectures have become increasingly widespread since they represent a viable design technique that allows to boost performance by concurrently executing many operations. Technology, though, allows the design of register files providing enough data-!bandwidth to support only few fast pipelined functional units.

One of the possible solutions is to partition the set of registers in multiple banks, each providing only part of the overall bandwidth required, and connect them to functional units by mean of a network.

This design scheme provides a non homogeneous register space requiring code with variables partitioned among the set of register files. Standard register allocation techniques are not suited for this task because of the different kind of resources that must be taken into consideration.

In this report we present a hypergraph-based paradigm that allows to model the process of partitioning; a coloring algorithm is used to assign variables to register files and if a legal coloring is not found, the code is partially rescheduled to allow the algorithm to proceed.

Experiments ran on a set of benchmarks show how the technique can frequently find a legal partitioning of variables without the needs for rescheduling; even when this is not possible, and code must be reorganized, very little performance degradation is usually introduced.

This paper introduces a new Tree Height Reduction (THR) technique for code compaction. THR, which is well known parallelizing method, has two interesting properties: while known compilation techniques can get constant factor of speed-up, THR has speed-up of O(n/logn). Furthermore, THR is able to compact code which seems, at first, uncompactable (due to data dependencies). The algorithm presented is incremental, local (so in each step, it is checking the the current operation and its predecessor rather than the whole expression tree to see whether compaction is possible) and applicable beyond basic block limits. THR is applied after all other optimization techniques, none of which change the semantics of the code, have been applied. THR is changing the semantics of the code, thus preserving, of course, the correctness of the intermediate and final values. Also, the reduction is controlled according to the resources available - so in case the compaction is feasible but there are not enough resources - it moves to the next operation. The algorithm produces compacted code suited for any tightly coupled multiprocessors (e.g. Very Long Instruction Word {or VLIW) machines). To our knowledge, it is the first local and incremental THR algorithm working across basic blocks boundaries published so far for code compaction.

Many large-scale scientific and engineering computations, e.g., some of the Grand Challenge problems [1], spend a major portion of execution time in their core loops computing band linear recurrences (BLR's). Conventional compiler parallelization techniques [4] cannot generate scalable parallel code for this type of computation because they respect loop-carried dependences (LCD's) in programs and there is a limited amount of parallelism in a BLR with respect to LCD's. For many applications, using library routines to replace the core BLR requires the separation of BLR from its dependent computation, which usually incurs significant overhead. In this paper, we present a new scalable algorithm, called the Regular Schedule, for parallel evaluation of BLR's. We describe our implementation of the Regular Schedule and discuss how to obtain maximum memory throughput in implementing the schedule on vector supercomputers. We also illustrate our approach, based on our Regular Schedule, to parallelizing programs containing BLR and other kinds of code. Significant improvements in CPU performance for a range of programs containing BLR implemented using the Regular Schedule in C over the same programs implemented using highly-optimized coded-in-assembly BLAS routines [11] are demonstrated on Convex C240. Our approach can be used both at the user level in parallel programming code containing BLR's, and in compiler parallelization of such programs combined with recurrence recognition techniques for vector supercomputers.

This paper presents a new approach to resource-constrained compiler extraction of fine-grain parallelism, targeted towards VLIW supercomputers, and in particular, the IBM VLIW (Very Large Instruction Word) processor. The algorithms described integrate resource limitations into Percolation Scheduling—a global parallelization technique—to deal with resource constraints, without sacrificing the generality and completeness of Percolation Scheduling in the process. This is in sharp contrast with previous approaches which either applied only to conditional-free code, or drastically limited the parallelization process by imposing relatively local heuristic resource constraints early in the scheduling process.