| In high-performance computing, distributed systems enhance performance by devoting multiple processors to a single problem. However, the performance of a distributed system is often less than optimal due to synchronization problems, communication overhead, I/O delays, and inefficient algorithms. To efficiently use the resources provided by distributed systems, designers need tools to evaluate job performance and match problems with candidate architectures.;While performance is a typical goal of using distributed systems, it is difficult to develop efficient programs for such systems because the computation must be efficiently distributed and managed on multiple autonomous processors. In particular, communication and synchronization problems are characteristic of distributed environments but rarely occur on serial machines.;The research presented here seeks to determine the effects of algorithmic communication and synchronization requirements on performance in a distributed system. Analysis of common algorithmic structures will be used to develop a framework for predicting upper and lower bounds on execution time based on detailed serial timings and estimates of communication times. Such a framework will allow prediction of an algorithm's performance on a distributed system before implementation of the distributed version. To determine the validity of this approach, five algorithms with well-known communication patterns will be studied and implemented on a real object-oriented distributed system (Pleiades using ESP). Finally, the actual execution times will be compared to the bounds predicted by the model. |
