A Parallel BP Algorithm for the Discretizable Distance Geometry Problem

Abstract : We propose a parallel version of the Branch & Prune (BP) algorithm for the Discretizable Distance Geometry Problem (DDGP), which consists in a subclass of Distance Geometry Problems (DGPs) that can be discretized. The main idea is to split a DDGP instance in as many subinstances as the number of processors involved in the computation, and to invoke the sequential version of BP on each processor. Due to the flexibility of the discretizing orderings that can be defined on the vertex sets of graphs G representing DDGP instances, the subdivision of the original instance can be performed so that all solutions generated by locally solving the several subinstances are represented in a common coordinate system. This way, the communication phase of the parallel algorithm, where the local solutions are combined in order to generate the final set of solutions, is very efficient. We present some preliminary computational experiments and we study the behavior of the algorithm in relation to the number of considered processors. We also give some directions for transforming DDGP instances in parallelizable instances, and to modify them in order to improve the efficiency of the proposed parallel algorithm.
Type de document :
Communication dans un congrès
Workshop on Parallel Computing and Optimization (PCO12), 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS12), 2012, Shanghai, China. 2012
Liste complète des métadonnées

https://hal.inria.fr/hal-00756947
Contributeur : Antonio Mucherino <>
Soumis le : samedi 24 novembre 2012 - 13:49:36
Dernière modification le : mercredi 16 mai 2018 - 11:23:35

Identifiants

  • HAL Id : hal-00756947, version 1

Citation

Antonio Mucherino, Gramacho Warley, Carlile Lavor, Nelson Maculan. A Parallel BP Algorithm for the Discretizable Distance Geometry Problem. Workshop on Parallel Computing and Optimization (PCO12), 26th IEEE International Parallel & Distributed Processing Symposium (IPDPS12), 2012, Shanghai, China. 2012. 〈hal-00756947〉

Partager

Métriques

Consultations de la notice

486