HBJ model

In computer science, the Helman-Bader-JaJa model is a concise message-passing model of parallel computing defined with the following parameters:

• [math]\displaystyle{ p }[/math] is number of processors.
• [math]\displaystyle{ n }[/math] is the problem size.
• [math]\displaystyle{ m }[/math] is number of machine words in a packet sent over the network.
• [math]\displaystyle{ \tau }[/math] is the latency, or time at which a processor takes to initiate a communication on a network.
• [math]\displaystyle{ \sigma }[/math] is the bandwidth, or time per machine word at which a processor can inject or receive [math]\displaystyle{ m }[/math] machine words from the network.
• [math]\displaystyle{ T_{comp} }[/math] is the largest computation time expended on a processor.
• [math]\displaystyle{ T_{comm} }[/math] is the time spent in communication on the network.

This model assumes that for any subset of [math]\displaystyle{ q }[/math] processors, a block permutation among the [math]\displaystyle{ q }[/math] processors takes [math]\displaystyle{ (\tau+\sigma m) }[/math] time, where [math]\displaystyle{ m }[/math] is the size of the largest block.

Analysis of common parallel algorithms

Complexities of common parallel algorithms contained in the MPI libraries:

• Point to point communication: [math]\displaystyle{ O(\tau+\sigma m) }[/math]
• Reduction :[math]\displaystyle{ O(log(p) (\tau+\sigma m)) }[/math]
• Broadcast: [math]\displaystyle{ O(log(p) (\tau+\sigma m)) }[/math]
• Parallel prefix: [math]\displaystyle{ O(log(p){n\over p} (\tau+\sigma m)) }[/math]
• All to all: [math]\displaystyle{ O(p(\tau+\sigma m)) ) }[/math]