Parallelism, memory anti-aliasing and correctness for trace scheduling compilers (disambiguation, flow-analysis, compaction)
Alexandru Eugen Nicolau · 1984
Trace scheduling 12 is a technique for transforming sequential programs into parallel code. When this investigation began, trace scheduling was unimplemented and many serious questions of appropriateness and effectiveness needed to be solved. Chief among them was disambiguation, the act of determining at compile time whether two indirect references are to certainly different locations. This thesis demonstrates that disambiguation is practical, correct and can be done efficiently in the presence of the extensive code motions introduced by trace scheduling. To demonstrate the practicality of disambiguation, a major implementation was undertaken which was part of the BULLDOG compiler for over a year. The effectiveness and necessity of the disambiguator became overwhelmingly obvious as the trace scheduling compiler was built. Turning it off made the parallelism we found decrease sharply. A trace scheduling compiler does many code motions that dramatically change the flow of control as code is generated. Disambiguation, and indeed trace scheduling, can't work correctly unless flow analysis information is constantly updated. However a global dynamic flow analysis is far too expensive. Unfortunately there are no intuitive reasons for believing that that is not required. It was therefore necessary to formally analyze our requirements. Through this process we were able to show that incremental and local flow analysis is always correct for our purposes. In the process, a proof of the correctness of trace scheduling evolved as well. Finally we studied new directions for disambiguation. In particular, a new technique, called Run Time Disambiguation was suggested and our implementation of this technique is described.