Performance Analysis of Bulk Synchronous Parallel Algorithms
Wellington Santos Martins · 1996
In the last few years, there has been considerable interest in general purpose computational models of parallel computation to permit independent development of hardware and software. The BSP and related models represent an important step in this direction. This paper presents a methodology for the performance analysis of bulk synchronous parallel algorithms based on parameters which reflect the two-level memory hierarchy advocated by these models. A parallel sorting algorithm is taken as a case study where it is shown a close agreement between theoretical and experimental results.