HIERARCHICAL MODELING OF PARALLEL ALGORITHMS ON MULTIPROCESSORS: QUICK-SORT, A CASE STUDY

[摘要] Performance of parallel algorithms on multiprocessors has been traditionally analyzed by looking at either the algorithm or the architecture of the multiprocessor system. However, it is important to study the combined effect of both these factors in order to evaluate and predict performance. A hierarchical and hybrid methodology has been adopted in this thesis to study the performance of a parallel algorithm. Parallel Quick-Sort is chosen as an example to demonstrate the method. A wide range of issues including the effect of communication and synchronization mechanisms, data allocation schemes and two different architectures are discussed in the context of the performance of parallel quick-sort.

[发布机构] Rice University