This project attempts to study the inter-relationship between parallel algorithms and architectures. The objective is to understand the impediments to the efficient performance of parallel algorithms on realistic parallel architectures. Our study attempts to relate the algorithmic characteristics with the architectural features by quantifying the different overheads that limit the scalability of a parallel system. The main idea is to isolate and quantify the overheads in a parallel system arising from the interaction of the algorithm with the architecture. Such an isolation can help in evaluating the match between algorithm and architecture, and can help in identifying bottlenecks in the algorithm for possible algorithm re-design, or suggest architectural enhancements. We experiment with real-world applications on a wide range of parallel machines. From these experiments, we identify parallel kernels that are representative of the computationally intensive phases of the applications. Through a combination of simulation and analytical techniques, we identify, isolate, and quantify the different overheads that arise from the interaction of these kernels with the underlying hardware. We have conducted scalability studies of parallel kernels, drawn from different application domains, on several hardware platforms using an execution-driven simulator called SPASM. Issues being currently investigated include exploring new application domains; enhancing SPASM to include several hardware platforms; parallelizing SPASM; and using our framework towards synthesizing architectural requirements for building large scale parallel systems from an application perspective.
U. Ramachandran, H. Venkateswaran, A. Sivasubramaniam, A. Singla. Issues in Understanding the Scalability of Parallel Systems. Proceedings of the First International Workshop on Parallel Processing, December, 1994.
U. Ramachandran, H. Venkateswaran. Towards Realizing Scalable High Performance Parallel Systems. Suggesting Computer Science Agenda(s) for High Performance Computing, ACM Press.
A. Sivasubramaniam, U. Ramachandran, H. Venkateswaran. A Comparative Evaluation of Techniques for Studying Parallel Systems. Technical Report GIT-CC-94/38. Georgia Institute of Technology.
A. Sivasubramaniam, A. Singla, U. Ramachandran, H. Venkateswaran. A Simulation-based Scalability Study of Parallel Systems. In Journal of Parallel and Distributed Computing, Vol. 22(3):411-426, 1994.
A. Sivasubramaniam, A. Singla, U. Ramachandran, H. Venkateswaran. On Characterizing Bandwidth Requirements of Parallel Applications. ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, May 1995. Also available as GIT-CC-94/31.
A. Sivasubramaniam, A. Singla, U. Ramachandran, H. Venkateswaran. An Approach to Scalability Study of Shared Memory Parallel Systems. In Proceedings of the ACM SIGMETRICS Conference on Measurement and Modeling of Computer Systems, May 1994.
A. Sivasubramaniam, A. Singla, U. Ramachandran, H. Venkateswaran. Abstracting Network Characteristics and Locality Properties of Parallel Systems. In Proceedings of the First International Symposium on High Performance Computer Architecture, January 1995. Also available as GIT-CC-93/63.
W. B. Ligon, U. Ramachandran. Evaluating Multigauge Architectures for Computer Vision. In Journal of Parallel and Distributed Computing, Vol (21):323-333, 1994.
U. Ramachandran, G. Shah, S. Ravikumar, J. Muthukumarasamy. Scalability Study of KSR-1. In Proceedings of the 22nd International Conference on Parallel Processing. 1993.
A. Sivasubramaniam, U. Ramachandran, H. Venkateswaran. A Computational Model for Message-Passing. In Proceedings of the International Parallel Processing Symposium, 1992. Extended version available as GIT-CC-91/11.
A. Sivasubramaniam, G. Shah, J. Lee, U. Ramachandran, H. Venkateswaran. Experimental Evaluation of Algorithmic Performance on Two Shared Memory Multiprocessors. In Proceedings of the International Symposium on Shared Memory Multiprocessing, 1991. Revised version available as GIT-CC-92/10.
I. Yanasak et al. Parallelizing Sequential Algorithms for the Generalized Assignment Problem. Proceedings of the DIMACS Implementation Challenge, October 1994.