Design of Multithreaded Estimation of Distribution Algorithms

Jiri Ocenasek, Josef Schwarz, Martin PelikanGECCO 2003 · DOI

TL;DR

This paper introduces the Multithreaded Mixed Bayesian Optimization Algorithm (MMBOA), a novel parallel approach for Estimation of Distribution Algorithms (EDAs) designed for clusters of workstations. MMBOA effectively tackles the computational bottleneck of building probabilistic models by using multithreading to overlap communication latencies with model building and sampling, leading to significant performance improvements.

What Problem Does This Paper Address?

Estimation of Distribution Algorithms (EDAs) are a powerful class of evolutionary algorithms that learn probabilistic models from promising solutions to generate new candidate solutions. A key challenge in EDAs, particularly those using Bayesian networks, is the computational cost of building and updating these models. While previous work has explored parallelizing EDAs, the authors identify a gap in efficiently parallelizing the construction of Bayesian networks with decision trees on distributed systems like clusters of workstations. Specifically, communication latencies between workstations can severely hinder performance. This paper aims to address this by proposing a multithreaded approach that overlaps communication with computation, making parallel EDAs more efficient on such architectures.

Methods

The core contribution of this paper is the Multithreaded Mixed Bayesian Optimization Algorithm (MMBOA). MMBOA builds upon the Mixed Bayesian Optimization Algorithm (MBOA), which uses decision trees to represent local probability distributions within a Bayesian network. The novelty lies in its parallel implementation on a cluster of workstations.

Key methodological aspects include:

  • Horizontal Layout for Offspring Generation: Similar to PBOA, MMBOA adopts a "horizontal" layout where each workstation is responsible for generating parts of the offspring population. This is generally preferred for coarse-grained parallelism.
  • Multithreaded Processing: Each workstation employs two threads:
  • A high-priority builder thread responsible for constructing decision trees (the model-building part).
  • A low-priority generator thread responsible for sampling new solutions using the built decision trees.
  • Overlapping Communication and Computation: The multithreaded design allows the builder thread to communicate with a master workstation for job requests and model updates while the generator thread samples previously built models. This overlap is crucial for hiding communication latencies.
  • Restricted Ordering for Acyclicity: To ensure the dependency graph remains acyclic without explicit cycle detection, MMBOA utilizes a predefined topological ordering of nodes, similar to DBOA. This allows for independent construction of decision trees.
  • Simulation with TRANSIM: The proposed algorithm was simulated using the TRANSIM tool, a CASE tool for predicting the performance of parallel algorithms. This allowed for evaluation without requiring a full implementation on a physical cluster.

Datasets

Not discussed in the paper. The paper focuses on the algorithmic design and simulation of performance, rather than evaluation on specific benchmark datasets.

Key Insights and Ideas

  • Multithreading as a Latency Hiding Mechanism: The most significant insight is the effective use of multithreading on each workstation to overlap communication with computation. This is particularly effective in distributed environments where communication latencies are a major bottleneck.
  • Builder-Generator Thread Interleaving: The separation of model building (builder thread) and solution generation (generator thread) into distinct, prioritized threads on each workstation is key to achieving efficiency. The high priority of the builder thread ensures that model construction progresses even when the generator thread is waiting for communication.
  • Scalability on Clusters: The proposed horizontal layout and multithreaded approach are well-suited for clusters of workstations, a common and cost-effective parallel computing platform.
  • Generalizability of Parallel Decision Tree Construction: The authors suggest that the technique for parallel decision tree construction is not limited to EDAs and could be applied to other machine learning tasks.

Key Results

The simulation results using TRANSIM demonstrated the efficiency and scalability of MMBOA.

  • Efficiency: The algorithm showed good performance for a large number of processors.
  • Scalability: The speedup achieved by MMBOA improved with increasing problem size (n). Figure 4 shows that the speedup approaches ideal case, with differences becoming negligible as problem size increases.
  • Workload Balance: The workload balance of each distributed process is adapted, suggesting suitability for heterogeneous clusters.
  • Simulation Parameters: The simulation used parameters measured from a real computing environment (Athlon-600 cluster) and realistic communication speeds and latencies (100Mb/s, 0.5ms).

Limitations and Future Work

  • SMT Support: The current implementation of the MPI standard does not directly support multithreaded processing, necessitating simulation. The authors mention that while Simultaneous Multithreading (SMT) is becoming popular, its integration with MPI for this specific algorithm would require further investigation.
  • Ideal vs. Real Speedup: The achieved speedup slightly differs from the ideal case due to unavoidable communication latencies, particularly when generating the last gene of a chromosome.
  • Future Work: The authors suggest exploring the application of their parallel decision tree construction technique to other areas of machine learning, data mining, and artificial intelligence. They also note that the proposed technique is a topic for future research outside the scope of Evolutionary Computation.

Summary updated

BibTeX
@inproceedings{ocenasek2003design,
  author = {Jiri Ocenasek and Josef Schwarz and Martin Pelikan},
  title = {{Design of Multithreaded Estimation of Distribution Algorithms}},
  booktitle = {GECCO},
  year = {2003},
  doi = {10.1007/3-540-45110-2\_1},
}
Figure