The scalability of multigrain systems
Donald Yeung · 1999
Researchers have recently proposed coupling small-to mediumscale multiprocessors to build large-scale shared memory machines, known as multigrain shared memory systems.Multigrain systems promise low cost because they leverage commodity multiprocessor nodes, and high performance because each multiprocessor node provides fine-grain shared memory mechanisms.Unfortunately, a quantitative study to evaluate the scalability of multigrain systems has thus far been lacking.Such scalability studies are difficult to undertake because of the limited system size that experimental evaluation can explore.This paper studies the scalability of multigrain systems using analysis.The paper proposes a novel methodology for analyzing program behavior on multigrain systems, called synchronization analysis.Synchronization analysis predicts communication volume by examining an application's synchronization behavior, an effective technique because on software DSMs, actual communication closely follows synchronization.Then, the paper presents a performance model that computes end-to-end application runtime based on an estimated cost for the predicted communication.On five shared memory applications, the performance model is accurate to within 18% of measured runtime for four applications, and within 22% for all five.Using the model, the paper conducts an in-depth study of multigrain system scalability.The paper shows that for multigrain systems with 512 processors, high performance can be achieved on four out of our five applications if each multiprocessor node is at least 16-way.