The Cost of A BSP Algorithm
The cost of a superstep is determined as the sum of three terms; the cost of the longest running local computation, the cost of global communication between the processors, and the cost of the barrier synchronisation at the end of the superstep. The cost of one superstep for processors:
where is the cost for the local computation in process, and is the number of messages sent or received by process . Note that homogeneous processors are assumed here. It is more common for the expression to be written as where and are maxima. The cost of the algorithm then, is the sum of the costs of each superstep.
where is the number of supersteps.
, and are usually modelled as functions, that vary with problem size. These three characteristics of a BSP algorithm are usually described in terms of asymptotic notation, e.g. .
Read more about this topic: Bulk Synchronous Parallel
Famous quotes containing the words the cost and/or cost:
“History is strewn with the wrecks of nations which have gained a little progressiveness at the cost of a great deal of hard manliness, and have thus prepared themselves for destruction as soon as the the movements of the world gave a chance for it.”
—Walter Bagehot (1826–1877)
“I knew that the wall was the main thing in Quebec, and had cost a great deal of money.... In fact, these are the only remarkable walls we have in North America, though we have a good deal of Virginia fence, it is true.”
—Henry David Thoreau (1817–1862)