Solving the Langford problem in parallel

Author

Jaillet, Christophe ; Krajecki, Michaël

Author_Institution

Departement de Mathematiques et Informatique, Univ. de Reims Champagne-Ardenne, France

fYear

2004

fDate

5-7 July 2004

Firstpage

83

Lastpage

90

Abstract

In this paper, the parallel resolution of the Langford problem is studied. Two different approaches are developed. First, an explicit construction of all the solutions is done using a shared memory. The application associated to this approach is written in C using the standard OpenMP library. Second, a parallelization of the algebraic method introduced by Godfrey is proposed. The application is taking advantage of MPI and has revealed efficient up to 128 processors. This solution opens up some new perspectives such as solving the already resolved instances of the problem more quickly and solving the next two open instances of the problem in a near future.

Keywords

application program interfaces; combinatorial mathematics; constraint theory; message passing; parallel algorithms; shared memory systems; C language; Langford problem; MPI; OpenMP library; algebraic method parallelization; message passing interface; parallel algorithm; parallel processing; shared memory; Libraries; Load management; Parallel algorithms; Personal communication networks; Scalability; Scheduling; Langford problem; MPI; OpenMP; parallel algorithm;

fLanguage

English

Publisher

ieee

Conference_Titel

Parallel and Distributed Computing, 2004. Third International Symposium on/Algorithms, Models and Tools for Parallel Computing on Heterogeneous Networks, 2004. Third International Workshop on

Print_ISBN

0-7695-2210-6

Type

conf

DOI

10.1109/ISPDC.2004.46

Filename

1372053