Integrating Amdahl-like Laws and Divisible Load Theory

Yang Cao, Fei Wu, Thomas G. RobertazziParallel 2019 · arXiv

TL;DR

This paper bridges the gap between Amdahl's Law, which models sequential bottlenecks in parallel computing, and Divisible Load Theory (DLT), which handles large, parallelizable datasets. By integrating these, the authors provide a more realistic mathematical framework for designing efficient future computing systems, showing how DLT-specific inefficiencies can be incorporated into Amdahl-like models.

What Problem Does This Paper Address?

Modern computing systems, from cloud platforms to distributed networks, are becoming increasingly complex. While our ability to build these systems outpaces our theoretical understanding of how to design them optimally, there's a pressing need for robust mathematical models. Amdahl's Law, a foundational concept, highlights the limitations imposed by sequential parts of a program on overall speedup. However, it doesn't account for the complexities of distributing and processing large, divisible workloads across networked processors, which is common in applications like big data processing and image analysis. Divisible Load Theory (DLT) addresses this by modeling how such loads can be optimally distributed and processed in parallel. This paper aims to unify these two perspectives, creating a more comprehensive model for system design.

Methods

The core of this paper is the integration of Amdahl's Law with Divisible Load Theory. Amdahl's Law is presented in its classic form, defining speedup ($S$) as the ratio of serial execution time to parallel execution time, considering a fraction ($f$) of the workload that is parallelizable and a serial fraction ($1-f$). DLT is then introduced as a framework for handling loads that can be arbitrarily divided and processed in parallel across multiple processors, focusing on minimizing the overall finish time (makespan).

The paper proposes a generalized Amdahl-like equation: $S_{AMDAHL} = \frac{1}{(1-f) + \frac{f}{S_{DLT}(n)}}$, where $S_{DLT}(n)$ represents the speedup achieved by a divisible load model with $n$ processors. This equation allows for the incorporation of DLT-specific factors like communication delays, network topology, and load distribution policies into an Amdahl-like framework. The authors analyze three fundamental load distribution protocols within a single-level tree network (star topology): sequential distribution, simultaneous distribution with staggered start, and simultaneous distribution with simultaneous start. They derive closed-form speedup expressions for these models, particularly for homogeneous processor systems.

Datasets

Not discussed in the paper. The paper focuses on theoretical modeling and analysis, using parameters defined within the models themselves for evaluation.

Key Insights and Ideas

  • Amdahl's Law as an Upper Bound: The paper demonstrates that pure Amdahl's Law, when applied to divisible load scenarios, acts as an upper bound on achievable speedup. This is because it doesn't account for inefficiencies inherent in divisible load processing, such as communication overhead and synchronization.
  • DLT Enhances Realism: Integrating DLT into Amdahl-like models provides a more realistic assessment of system performance by accounting for factors like network topology, communication delays, and load distribution strategies.
  • Simultaneous Distribution Outperforms Sequential: Systems employing simultaneous distribution of load (both staggered and simultaneous start) generally achieve higher speedups than those using sequential distribution. This is attributed to processors being able to start receiving load earlier.
  • Simultaneous Start is Superior: Among simultaneous distribution methods, "simultaneous start" (where computation begins as soon as load reception starts) yields higher speedups than "staggered start" (where computation waits for all load to be received).
  • Homogeneous Processors Offer Higher Speedup: For the specific parameters and models analyzed, systems with homogeneous processors generally exhibit higher speedup values compared to heterogeneous systems. This is because the homogeneous system effectively leverages the highest processing speed available across all processors.
  • Parallelizable Load Fraction is Crucial: As expected, a higher fraction of parallelizable workload ($f$) leads to significantly higher speedups, especially as $f$ approaches 1 (fully parallelizable).

Key Results

The paper presents analytical speedup expressions for three DLT models on a single-level tree network. For instance, for homogeneous processors:

  • Sequential Distribution: $S_{DLT, homo}(n) = 1 + \frac{1 - (1-\sigma)^n}{\sigma}$, where $\sigma$ relates to communication and computation intensity.
  • Simultaneous Distribution, Staggered Start: $S_{DLT, homo}(n) = 1 + k \times n$, where $k$ is a factor related to processing and communication speeds.
  • Simultaneous Distribution, Simultaneous Start: $S_{DLT, homo}(n) = 1 + k \times n$, where $k = \omega_0/\omega$ (ratio of root to processor inverse computing speed).

Figures 3-6 visually demonstrate these results, showing speedup curves for different processor counts and parallelizable load fractions. For example, Figure 4 shows that for a homogeneous system with 30 processors, the speedup for simultaneous distribution with staggered start is 4.25, while for simultaneous distribution with simultaneous start, it's also around 4.25 (though the underlying model is different). Figure 6 illustrates that as the parallelizable fraction ($f$) increases, speedup also increases dramatically, reaching values around 20 for $f=1$.

Limitations and Future Work

The authors acknowledge that for more complex models, analytical solutions might not be feasible, and numerical methods may be required. They also note that their analysis primarily focuses on a single-level tree network topology and specific load distribution protocols.

Future work could involve:

  • Extending the integration to other Amdahl-like variants, such as Gustafson's Law, which considers scaling problem size.
  • Applying these integrated models to a wider range of network topologies (e.g., meshes, hypercubes).
  • Investigating the impact of more intricate load distribution policies.
  • Exploring how to numerically solve and integrate more complex DLT models into Amdahl-like equations.
  • Considering additional real-world system inefficiencies like task creation overhead, synchronization, resource contention, and memory issues.

Summary updated

Abstract

Integrating Amdahl's and Amdahl-like laws with Divisible Load Theory promises mathematical design methodology that will make possible the efficient design of tomorrow's systems.
BibTeX
@inproceedings{cao2019integrating,
  author = {Yang Cao and Fei Wu and Thomas G. Robertazzi},
  title = {{Integrating Amdahl-like Laws and Divisible Load Theory}},
  booktitle = {Parallel},
  year = {2019},
}
Figure