GENERATION, OPTIMIZATION, AND EVALUATION OF MULTITHREADED CODE

The recent advent of multithreaded architectures holds many promises: the exploitation of intrathread locality and the latency tolerance of multithreaded synchronization can result in a more efficient processor utilization and higher scalability. The challenge for a code generati on scheme is to make effective use of the underlying hardware by gener ating large threads with a large degree of internal locality without l imiting the program level parallelism or increasing latency. Top-down code generation, where threads are created directly from the compiler' s intermediate form, is effective at creating a relatively large threa d. However, having only a limited view of the code at any one time lim its the quality of threads generated. These top-down generated threads can therefore be optimized by global, bottom-up optimization techniqu es. In this paper, we introduce the Pebbles multithreaded model of com putation and analyze a code generation scheme whereby top-down code ge neration is combined with bottom-up optimizations. We evaluate the eff ectiveness of this scheme in terms of overall performance and specific thread characteristics such as size, length, instruction level parall elism, number of inputs, and synchronization costs. (C) 1996 Academic Press, Inc.