We also present experimental results for the selection algorithm that reinforce our claims.
ALEXANDROS GERBESSIOTIS SOFTWARE
The main reward of quantifying these complications is that it allows transportable software to be written for parallel machines that fit the model. While these algorithms are fairly simple themselves, descriptions of their performance in terms of the BSP parameters is somewhat involved. We also establish that optimality to within small multiplicative constant factors can be achieved for a wide range of parallel machines. We show that our methods improve previous results upon both the communication requirements and the amount of parallel slack required to achieve optimal performance. In this paper we present a new randomized selection algorithm on the Bulk-Synchronous Parallel (BSP) model of computation, along with an application of this algorithm to dynamic data structures, namely Parallel Priority Queues (PPQs). Moreover, our methods are within a 1 + o(1) multiplicative factor of the. In particular, our new randomized sorting algorithm improves previously known BSP randomized sorting algorithms upon the amount of parallel slackness required to achieve optimality. Applications to computational geometry and sorting are also presented. This technique allows elegant high-level design and analysis of algorithms, using data structures similar to those of sequential models.
We propose multi-way search as a general tool for the design, analysis and implementation of BSP algorithms. In this work we undertake the architecture independent study of the computation and communication requirements of searching ordered h-level graphs, which include many of the standard data structures. The implementation of data structures on distributed memory models such as the Bulk-Synchronous Parallel (BSP) model, rather than shared memory ones such as the Parallel Random Access Machine (PRAM), offers a serious challenge.
0 kommentar(er)
