The collective computing model

Abstract

The parallel computing model used in this paper, the Collective Computing Model (CCM), is a variant of the well-known Bulk Synchronous Parallel (BSP) model. The synchronicity imposed by the BSP model restricts the set of available algorithms and prevents the overlapping of computation and communication. Other models, like the LogP model, allow asynchronous computing and overlapping but depend on the use of specific libraries. The CCM describes a system exploited through a standard software platform providing facilities for group creation, collective operations and remote memory operations. Based in the BSP model, two kinds of supersteps are considered: Division supersteps and Normal supersteps. The structure of divisions produced by the Division Functions and the partnership relation among processors give place to communication patterns among processors that are topologically similar to a hypercube. We have named the resulting structures Dynamic Polytopes To illustrate these concepts, the Fast Fourier Transform Algorithm is used. Computational results prove the accuracy of the model in four different parallel computers: a Parsytec Power PC, a Cray T3E, a Silicon Graphics Origin 2000 and a Digital Alpha Server.

Keywords

• parallelism
• bulk synchronous parallel model
• supersteps
• performance prediction
• parallel computer