Title :
A parallel algorithm for enumerating combinations
Author :
Torres, Martha ; Goldman, Alfredo ; Barrera, Junior
Author_Institution :
Departamento de Ciencia da Computacao, Sao Paulo Univ.
Abstract :
We propose an efficient parallel algorithm with simple static and dynamic scheduling for generating combinations. It can use any number of processors (NPlesn-m+1) in order to generate the set of all combinations of C(n,m). The main characteristic of this algorithm is to require no integer larger than n during the whole computation. The performance results show that even without a perfect load balance, this algorithm has very good performance, mainly when n is large. Besides, the dynamic algorithm presents a good performance on heterogeneous parallel platforms
Keywords :
computational complexity; dynamic scheduling; parallel algorithms; processor scheduling; resource allocation; combinations enumeration; dynamic algorithm; dynamic scheduling; heterogeneous parallel platforms; load balance; parallel algorithm; static scheduling; Adaptive algorithm; Application software; Computer science; Concurrent computing; Dynamic scheduling; Genetics; Gold; Heuristic algorithms; Parallel algorithms; Scheduling algorithm;
Conference_Titel :
Parallel Processing, 2003. Proceedings. 2003 International Conference on
Conference_Location :
Kaohsiung
Print_ISBN :
0-7695-2017-0
DOI :
10.1109/ICPP.2003.1240626
