Scaling Linear Solvers to Petascale Systems

Analytical Modeling – Basics

• A number of performance measures are intuitive.

• Wall clock time – the time from the start of the first processor to the stopping time of the last processor in a parallel ensemble. But how does this scale when the number of processors or problem instance is changed, or the program is ported to another machine?

• How much faster is the parallel version? This begs the obvious followup question – what is the baseline serial version with which we compare? Can we use a suboptimal serial program to make our parallel program look

• Raw FLOP count – What good are FLOP counts when they dont solve a problem?

Scaling Characteristics of Parallel Programs

• The efficiency E of a parallel program can be written in terms

of speedup S, serial time T_{S} and parallel time T_{P} as:

E = \frac{S}{p} = \frac{T_{S}}{pT_{P}}

or

E = \frac{1}{1 + \frac{T_{o}}{T_{S}}} .  (1)

• The total overhead function T_{o} here is defined as T_{o} = pT_{P} − T_{S}.

• The total overhead function T_{o} is an increasing function of p.

Scaling Characteristics of Parallel Programs

• For a given problem size (i.e., the value of T_{S} remains constant), as we increase the number of processing elements, T_{o} increases.

• The overall efficiency of the parallel program goes down. This is the case for all parallel programs.

• Total overhead function T_{o} is a function of both problem size T_{S} and the number of processing elements p.

• In many cases, T_{o} grows sublinearly with respect to T_{S}.

• In such cases, the efficiency increases if the problem size is increased keeping the number of processing elements constant.

• For such systems, we can simultaneously increase the problem size and number of processors to keep efficiency constant.

• Such systems are called scalable parallel systems.

• Recall that cost-optimal parallel systems have an efficiency of Θ(1).

• Scalability and cost-optimality are therefore related.

• A scalable parallel system can always be made cost-optimal if the number of processing elements and the size of the computation are chosen appropriately.

Isoefficiency Metric of Scalability

• For a given problem size, as we increase the number of processing elements, the overall efficiency of the parallel system goes down for all systems.

• For some systems, the efficiency of a parallel system increases if the problem size is increased while keeping the number of processing elements constant.

Variation of efficiency: (a) as the number of processing elements is in creased for a given problem size; and (b) as the problem size is increased for a given number of processing elements. The phenomenon illustrated in graph (b) is not common to all parallel systems.

• What is the rate at which the problem size must increase with respect to the number of processing elements to keep the efficiency fixed?

• This rate determines the scalability of the system. The slower this rate, the better.

Isoefficiency Metric of Scalability

• We can write parallel runtime as:

T_{P} = \frac{W + T_{o}(W, p)}{p}  (2)

Here, W is the problem size, i.e., the number of basic steps in the algorithm.

• The resulting expression for speedup is

S = \frac{W}{T_{P}} = \frac{W p}{W + T_{o}(W, p)}.

• Finally, we write the expression for efficiency as

E = \frac{S}{p} = \frac{W}{W + T_{o}(W, p)} = \frac{1}{1 + T_{o}(W, p)/W} .  (3)

– Typeset by FoilTEX – 9

• For scalable parallel systems, efficiency can be maintained at a fixed value (between 0 and 1) if the ratio T_{o}/W is maintained at a constant value.

• For a desired value E of efficiency,

E = \frac{1}{1 + T_{o}(W, p)/W} ,
\frac{T_{o}(W, p)}{W} = \frac{1 − E}{E},
W = \frac{E}{1 − E}T_{o}(W, p).  (4)

• If K = E/(1 − E) is a constant depending on the efficiency to be maintained, since T_{o} is a function of W and p, we have

W = KT_{o}(W, p).  (5)

• The problem size W can usually be obtained as a function of p by algebraic manipulations to keep efficiency constant.

• This function is called the isoefficiency function.

• This function determines the ease with which a parallel system can maintain a constant efficiency and hence achieve speedups increasing in proportion to the number of processing elements.

Pseudo-Analytical Approach to Performance Prediction

• Analytical approaches provide precise asymptotic estimates of scalability. They can be applied to algorithms and provide gross guidance to architecture design.

• Empirical approaches work on performance extrapolation. They are often inaccurate and work on realizations of programs. They provide little guidance to algorithm and architecture designers.

• Simulation-based approaches combine static analysis, dynamic profiling, and a discrete-event based simulation. They are often slow, and are only as accurate as the simulation.

• We adopt an analytical approach to performance modeling, but parametrize models using experimental data.

Pseudo-Analytical Approach to Performance Prediction

• Approach based on factoring out program behavior and machine characteristics.

• Characterize program behavior (computation requirements, communication overheads) using experimental data fitted on asymptotic estimates.

• Characterize platform using experimental data for communication overheads for underlying permutations.

• Match program and platform characterizations for accurate performance modeling.

Scalability Case Study: Spike Solver Performance

Table 1: Spike TA0 Algorithm Steps

Number Description  Cost
1  Factorize the Diagonal Blocks  O(n × k^{2})
2  Compute Tips of Spikes  O(k^{3})
3  Communicate Tips of Spikes  O(k^{2})
4  Factorize The Reduced System  O(k^{3})
5  Modify the Right Hand Side  O(n × k)
6  Communicate Tips of MRHS  O(k)
7  Solve the Reduced System  O(k^{2})
8  Communicate Soln. of Reduced System  O(k)
9  Matrix Vector Multiplication  O(k^{2})
10  Retrieve the Solution  O(n × k)

Scalability Case Study: Spike Solver Performance

Parametrizations of various steps for an IBM JS21.

– Typeset by FoilTEX – 15

Scalability Case Study: Spike Solver Performance

Observed and predicted speedups on the IBM JS21.

– Typeset by FoilTEX – 16

Scalability Case Study: Spike Solver Performance

• Isoefficiency of the Spike solver is close to linear (O(p)).

• This implies that strong scaling should yield close to linear speedups.

Scalability Case Study: Spike Solver Performance

Observed and predicted scaled speedups on the IBM JS21.

– Typeset by FoilTEX – 18

Scalability Case Study: Spike Solver Performance

Predicted Spike Scaling to petaFLOPS onn the IBM JS21.

– Typeset by FoilTEX – 19

Scalability Case Study: Spike Solver Performance

Shared address space nodes, though complicate life!

Parametrizations of various steps for an SGI Altix.

Scalability Analysis: Conclusions

• Proposed and demonstrated a novel pseudoanalytical approach for scalability analysis.

• Technique factors application and architecture abstractions to enable portability studies.

• Application to Spike solver shows high degree of predictive accuracy.

• Demonstrated projected scaling of Spike to petascale.

Scalability Analysis: Conclusions

• Complete study by analysing a broader class of platforms.

• Characterize other test-cases to fully validate scalability analysis methodology.

Reference Slides

– Typeset by FoilTEX – 23

Other Scalability Metrics

• A number of other metrics have been proposed, dictated by specific needs of applications.

• For real-time applications, the objective is to scale up a system to accomplish a task in a specified time bound.

• In memory constrained environments, metrics operate at the limit of memory and estimate performance under this problem growth rate.

Other Scalability Metrics: Scaled Speedup

• Speedup obtained when the problem size is increased linearly with the number of processing elements.

• If scaled speedup is close to linear, the system is considered scalable.

• If the isoefficiency is near linear, scaled speedup curve is close to linear as well.

• If the aggregate memory grows linearly in p, scaled speedup increases problem size to fill memory.

• Alternately, the size of the problem is increased subject to an upper-bound on parallel execution time.

Scaled Speedup: Example

• The serial runtime of multiplying a matrix of dimension n×n with a vector is t_{c}n^{2}.

• For a given parallel algorithm,

S = \frac{t_{c}n^{2}}{t_{c}\frac{n^{2}}{p} + t_{s} log p + t_{w}n}  (6)

• Total memory requirement of this algorithm is Θ(n^{2}).

Scaled Speedup: Example (continued)

Consider the case of memory-constrained scaling.

• We have m = Θ(n^{2}) = Θ(p).

• Memory constrained scaled speedup is given by

S′ = \frac{t_{c}c × p}{t_{c}\frac{c×p}{p} + t_{s} log p + t_{w}\sqrt{c × p}}

or S′ = O(\sqrt{p}).

• This is not a particularly scalable system.

Scaled Speedup: Example (continued)

Consider the case of time-constrained scaling.

• We have T_{P} = O(n^{2}/p).

• Since this is constrained to be constant, n^{2} = O(p).

• Note that in this case, time-constrained speedup is identical to memory constrained speedup.

• This is not surprising, since the memory and time complexity of the operation are identical.

Scaled Speedup: Example

• The serial runtime of multiplying two matrices of dimension n×n is t_{c}n^{3}.

• The parallel runtime of a given algorithm is:

T_{P} = t_{c}\frac{n^{3}}{p} + t_{s} log p + 2t_{w} \frac{n^{2}}{\sqrt{p}}

• The speedup S is given by:

S = \frac{t_{c}n^{3}}{t_{c}\frac{n^{3}}{p} + t_{s} log p + 2t_{w} \frac{n^{2}}{\sqrt{p}}}  (7)

– Typeset by FoilTEX – 29

Scaled Speedup: Example (continued)

Consider memory-constrained scaled speedup.

• We have memory complexity m = Θ(n^{2}) = Θ(p), or n^{2} = c × p.

• At this growth rate, scaled speedup S′ is given by:

S′ = \frac{t_{c}(c × p)^{1.5}}{t_{c}\frac{(c×p)^{1.5}}{p} + t_{s} log p + 2t_{w} \frac{c×p}{\sqrt{p}}} = O(p)

• Note that this is scalable.

– Typeset by FoilTEX – 30

Scaled Speedup: Example (continued)

Consider time–constrained scaled speedup.

• We have T_{P} = O(1) = O(n^{3}/p), or n^{3} = c × p.

• Time-constrained speedup S′′ is given by:

S′′ = \frac{t_{c}c × p}{t_{c}\frac{c×p}{p} + t_{s} log p + 2t_{w} \frac{(c×p)^{2/3}}{\sqrt{p}}} = O(p^{5/6})

• Memory constrained scaling yields better performance.

– Typeset by FoilTEX – 31

Serial Fraction f

• If the serial runtime of a computation can be divided into a

totally parallel and a totally serial component, we have:

W = T_{ser} + T_{par}.

• From this, we have,

T_{P} = T_{ser} + \frac{T_{par}}{p}.

T_{P} = T_{ser} + \frac{W − T_{ser}}{p}  (8)

– Typeset by FoilTEX – 32

Serial Fraction f

• The serial fraction f of a parallel program is defined as:

f = \frac{T_{ser}}{W}.

Therefore, we have:

T_{P} = f × W + \frac{W − f × W}{p}
\frac{T_{P}}{W} = f + \frac{1 − f}{p}

– Typeset by FoilTEX – 33

Serial Fraction

• Since S = W/T_{P}, we have

\frac{1}{S} = f + \frac{1 − f}{p} .

• From this, we have:

f = \frac{1/S − 1/p}{1 − 1/p}.  (9)

• If f increases with the number of processors, this is an indicator of rising overhead, and thus an indicator of poor scalability.

Serial Fraction: Example

Consider the problem of extimating the serial component of the matrix-vector product.

We have:

f = \frac{\frac{t_{c} \frac{n^{2}}{p}+t_{s} log p+t_{w}n}{t_{c}n^{2}}}{1 − 1/p}  (10)

or

f = \frac{t_{s}p log p + t_{w}np}{t_{c}n^{2}} × \frac{1}{p − 1}
f ≈ \frac{t_{s} log p + t_{w}n}{t_{c}n^{2}}

Here, the denominator is the serial runtime and the numerator is the overhead.

– Typeset by FoilTEX – 35