Compiling for Parallel Multithreaded Computation on Symmetric Multiprocessors

Shared-memory symmetric multiprocessors (SMP's) based on conventional microprocessors are by far the most common parallel architecture today, and will continue to be so for the forseeable future. This thesis describes techniques to compile and schedule Id-S, a dialect of the implicitly parallel language Id, for execution on SMP's. We show that previous implementations of Id for conventional microprocessors incurred an overhead of at least 40-300% over an efficient sequential implementation of Id-S. We break down this overhead into various presence-tag checking and scheduling overheads. Given this overhead, we conclude that a fine-grained, element-wise synchronizing implementation of Id is not suitable for use on small-scale SMP's. We then describe a parallelization technique for Id-S that discovers both DAG and loop parallelism. Our parallelization exploits Id-S's single-assignment semantics for data structures. We show that for many programs, our technique can discover ample paralleli..