Partitioning a lenient parallel language into sequential threads

Multithreading is attractive in a large-scale parallel system since it allows split-phase memory operations and fast context switching between computations without blocking the processor. The performance of multithreaded architectures depends significantly on the quality of multithreaded codes. In this paper, we describe an enhanced thread formation scheme to produce efficient sequential threads from programs written in Id^-, a lenient parallel language. This scheme features graph partitioning based only on long latency instructions, a combination of multiple switches and merges introducing a generalized switch-and-merge, thread merging, and redundant arc elimination using thread precedence relations. Simulation results show that our scheme reduces control and branch instructions effectively