| There has been considerable interest in building multithreaded machines because of advances in VLSI technology and the inherent latency-tolerance feature of the multithreaded architecture. We believe that the multithreaded architecture is a promising model for the next generation of high-performance computers.; As for other computing machines, it is essential to have adequate compiler support for multithreaded architectures so that programming efficiency can be dramatically improved. This thesis presents novel compilation techniques for the non-preemptive multithreaded model (such as EARTH). Once started, a non-preemptive thread will run to completion without being interrupted. Such a model can be easily implemented with off- the-shelf processors. However, the non-preemptive execution model poses more requirements on the compiler. The key problem is to partition a program into a collection of threads, respecting data and control constraints. Such a partition requires substantial compiler analysis to guarantee the correctness and efficiency of the partitioned code.; This thesis has made contributions to the design and development of an efficient compiler for multithreaded architectures. The major contributions are as follows:; On the theoretic side, we proved that (1) thread partitioning for minimizing total execution time is an NP-hard problem; (2) the run length of a schedule generated by any list-scheduling based partitioning algorithm is no more than twice that of the optimal schedule; (3) we designed an advanced heuristic partitioning algorithm to achieve near-optimum partitions.; On the compiler side, we simplified the advanced partitioning algorithm and proposed a heuristic partitioning framework based on remote-paths. The intermediate representation used in the framework is program dependence flow graph, which can hierarchically capture program data and control dependencies to facilitate thread partitioning. A series of compiler analyses have been proposed to develop such a partitioning framework and two code generators have been implemented for two multithreaded models.; On the experimental side, we implemented a collection of irregular (non-array) benchmarks. The experimental results show the effectiveness of our partitioning algorithms, the generality of our partitioning framework, and the positive performance impacts of our optimizations on thread partitioning. |
