Incremental Parallelization with Migration

This dissertation presents a new methodology for developing parallel distributed programs in a series of incremental steps to achieve incremental parallelism and incremental performance improvement. The methodology takes advantage of threads that are able to migrate through the network and thus are able to follow distributed data. This allows the data to be partitioned and distributed first, which guarantees that elements that are used together in a computation are collocated on the same node. Next, the loops in the code are tiled to minimize migration among nodes. After deciding on the location at which each loop is to execute, the necessary migration and remote access statements are inserted to make the code executable. This process is repeated based on feedback obtained from the execution,which may improve the overall performance by suggesting a different data distribution or a different coarseness of tiling. We show each steps and the performance data for two well-known application. Also, we illustrate the trade-offs using a well-known application with two different data distributions