A Parallel BP Algorithm for the Discretizable Distance Geometry Problem - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Année : 2012

A Parallel BP Algorithm for the Discretizable Distance Geometry Problem

Résumé

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.
Fichier non déposé

Dates et versions

hal-00756947 , version 1 (24-11-2012)

Identifiants

  • HAL Id : hal-00756947 , version 1

Citer

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. ⟨hal-00756947⟩
268 Consultations
0 Téléchargements

Partager

Gmail Facebook X LinkedIn More