Guilherme Ottoni will present his preFPO on Monday October 1 at 11AM in Room 301. The members of his committee are: David August, advisor; Sharad Malik (EE) and Vivek Sarkar (Rice), readers; Margaret Martonosi and David Walker, nonreaders. Everyone is invited to attend his talk. His abstract follows below. -------------------- Global Instruction Scheduling for Multi-Threaded Architectures Recently, the microprocessor industry has moved toward chip multiprocessor (CMP) designs as a means of utilizing the increasing transistor counts in the face of physical and micro-architectural limitations. Despite this move, CMPs do not directly improve the performance of single-threaded codes, a characteristic of most applications. In effect, the move to CMPs has shifted even more the task of improving performance from the hardware to the software. Since developing parallel applications has long been recognized as significantly harder than developing sequential ones, it is very desirable to have automatic tools to extract parallelism from sequential applications. Unfortunately, automatic parallelization has only been successful in the restricted domain of scientific and data-parallel applications, which usually have regular array-based memory accesses and little control flow. In order to support parallelization of general-purpose applications, computer architects have proposed CMPs with light-weight, fine-grained (scalar) communication mechanisms. Despite such support, most existing compiler multi-threading techniques have generally demonstrated little effectiveness in extracting parallelism from non-scientific applications. The main reason for this is that such techniques are mostly restricted to extracting parallelism within local, straight-line regions of code. As observed in several limit studies, local regions of code have limited parallelism, and control dependence analysis and multiple control units are necessary to extract most of the parallelism opportunities. In this talk, I will describe a general compiler framework to perform Global Multi-Threaded (GMT) instruction scheduling, based on a Program Dependence Graph (PDG) representation, graph partitioning algorithms, and a novel Multi-Threaded Code Generation (MTCG) algorithm. Based on this framework, two techniques to perform GMT instructions scheduling are proposed. The first one, Decoupled Software Pipelining (DSWP), extracts pipeline parallelism from arbitrary loop nests. The second technique, GREMIO, is applicable to arbitrary (intra-procedural) code regions, and can also exploit other forms of parallelism. Finally, I will present several communication optimizations to improve the MTCG algorithm, and thus all GMT instruction scheduling techniques based on it. All these techniques are implemented in the VELOCITY compiler and evaluated on an accurate CMP simulator built on top of validated Itanium 2 core models. The results demonstrate the effectiveness of the proposed compiler techniques, with speedups on a number of real applications written in C.