aillet Constructing Optimal Golomb Rulers in Parallel

Abstract — In this paper, a construction of the Golomb optimal rulers is studied with a tree search approach. Improvements to the basic algorithm are given and it is parallelized using a shared memory. The application associated to this approach is written in C using the standard OpenMP and MPI libraries. The algorithm takes advantage of a collaboration mech-anism between the processors. Different load balancing strategies are studied. The application has proved efficient up to 32 processors. This solution opens up some new perspectives such as solving the already resolved instances of the problem more quickly, and solving next open instances in the future. Index Terms — Golomb ruler, parallel algorithm, load balancing, shared memory, OpenMP, distributed memory