IMPLEMENTATION AND PERFORMANCE EVALUATION OF A PARALLELIZATION OF ESTIMATION OF BAYESIAN NETWORK ALGORITHMS

This paper presents, discusses and evaluates parallel implementations of a set of algorithms designed for optimization tasks: Estimation of Bayesian Network Algorithms (EBNAs). These algorithms belong to the family of Evolutionary Computation. Two different APIs have been combined: message passing and threads, with the aim of obtaining good performance levels in a wide range of parallel machines. Our approach has been to analyze the most computationally intensive sections of sequential implementations of EBNAs, and then to parallelize those sections using a master-worker design pattern. This way the resulting program exhibits exactly the same behavior of the sequential one, but runs faster. To evaluate our proposal, we have chosen a complex scenario where EBNAs can be applied: Feature Subset Selection (FSS) for supervised classification problems. For the experiments, three computing systems have been tested: two different clusters built from commodity components, and an 8-way multiprocessor. Programs have been executed on the target machines using different combination of message-passing processes and threads. Achieved performance is excellent, with efficiency around 1. These encouraging results do widen the spectrum of problems (and problem sizes) that can be solved, in reasonable times, with EBNAs.