Performance evaluation of the parallel polytree approximation distribution algorithm on three network technologies

Abstract

This paper proposes two parallel variants of an Estimation of Distribution Algorithm (EDA) that represents the probability distribution by means of a single connected graphical model based on a polytree structure. The main goal is to design a new and more effi cient EDA. Our algorithm is based on the master/slave model that allows to perform the estimation of the probability distribution (the most time-consuming phase in EDAs) in a parallel way. The aim of our experimental studies is manifold. Firstly, we show that our parallel versions achieve a notable reduction of the total execution time with respect to existing algorithms. Secondly, we study the behavior of the algorithm from the numerical point of view, analyzing the different versions. Finally, our methods are evaluated over three interconnection networks (Fast Ethernet, Gigabit Ethernet, and Myrinet) and a study on the infl uence of the parallel platform in the communication is performed.