A Load Balance Algorithm Modeled on the Knapsack Problem for Parallel Fuzzy c-Means Cluster Analysis
Marta Modenesi (COPPE/Federal University of Rio de Janeiro, Brazil)Alexandre Evsukoff (COPPE/Federal University of Rio de Janeiro, Brazil)
Myrian Costa (COPPE/Federal University of Rio de Janeiro)
Abstract:
This work proposes a load balance algorithm to parallel processing based on a variation of the classical knapsack problem. The problem considers the distribution of a set of partitions, defined by the number of clusters, over a set of processors attempting to achieve a minimal overall processing cost.
The work is an optimization for the parallel fuzzy c-means (FCM) clustering analysis algorithm proposed in a previous work composed by two dis-tinct parts: the cluster analysis, properly said, using the FCM algorithm to calculate of clusters centers and the PBM index to evaluate partitions, and the load balance, which is modeled by the multiple knapsack problem and im-plemented through a heuristic that incorporates the restrictions related to cluster analysis in order to gives more efficiency to the parallel process.
Keywords:
Large Scale Simulations in CS&E (earth, environment, finance, geoscience, engineering, ...), Parallel and Distributed Computing, Cluster Computing, Optimization
