Thread/Computation Migration to Exploit Spatial Locality
Migrating computation between processors to exploit locality is a powerful approach to improve system performance. When it works well, it reduces message traffic and speeds computation. In other cases, it performs poorly and can slow program execution. Therefore, half the battle is knowing when to apply migration and when to fall back to conventional techniques. Because migration can be fairly easy to implement, it should be a part of every compiler writer’s toolbox and can be very useful in many contexts. The following papers explore some of the problem space, describe the Nomadic Threads architecture and implementation, and provide some performance results.
S. Jenks and J.-L. Gaudiot, “Nomadic Threads: A Migrating Multithreaded Approach to Remote Memory Accesses in Multiprocessors,” in Proceedings of the 1996 Conference on Parallel Architectures and Compilation Techniques (PACT’96), Boston, MA, 1996.
S. Jenks and J.-L. Gaudiot, “Exploiting Locality and Tolerating Remote Memory Access Latency Using Thread Migration,” International Journal of Parallel Programming, vol. 25, no. 4, pp. 281-304, August 1997.
S. Jenks and J.-L. Gaudiot, “An Evaluation of Thread Migration for Exploiting Distributed Array Locality,” in Proceedings of The 16th Annual International Symposium on High Performance Computing Systems and Applications (HPCS’2002), Moncton, New-Brunswick, Canada, 2002.
S. Jenks and J.-L. Gaudiot, “A Multithreaded Runtime System with Thread Migration for Distributed Memory Parallel Computing,” in Proceedings of High Performance Computing Symposium, 2003 Advanced Simulation Technologies Conference, Orlando, FL, 2003.
S. Jenks, “Multithreading and Thread Migration Using MPI and Myrinet,” in Proceedings of Parallel and Distributed Computing and Systems Conference, Cambridge, MA, 2004.
If there is interest, I will make available a working Linux version of the LLNL SISAL compiler and my Nomadic Threads compiler and runtime system for MPI clusters. This will be unsupported, but may be useful to some. Email me if you really want it and I will gauge the interest.