AIRCC's International Journal of Computer Science and Information Technology

Open Access Open Access  Restricted Access Subscription Access

Improved Computing Performance for Listing Combinatorial Algorithms Using Multi-processing MPI and Thread Library


Affiliations
1 University of Education and Science, University of Danang, Viet Nam
 

This study builds up two parallel algorithms to improve computing performance for two listing binary and listing permutation algorithms. The problems are extremely interesting and practically applicable in many fields in our daily life. To parallel execution, we divide the data set input and allocate them to the processors. The article focuses on (i) the analysis of the research situation of the related works to compare and evaluate the existing problems of previous works, (ii) the analysis of the input data structure to divide data for the sub processors, (iii) the construction of parallel algorithms - proof of correctness and analysis of computing complexity, and (iv) experiments in multi-processing MPI and Thread library. Then the comparison of the results of the parallel algorithm with the sequential algorithm and the comparison of the execution time on different sub processors is discussed.

Keywords

Parallel Algorithms, Listing Binary, Listing Permutation, Bounded Sequences, Substituend, Inversion.
User
Notifications
Font Size

  • Nguyen Dinh Lau, Parallel algorithm list permutations,@ 2017,ISBN: 978-604-67-1009-7, 2324/11/2017, Quy Nhon, Binh Dinh, Vietnam, pp 348-353.

  • Nguyen Dinh Lau, Parallel algorithm for the graph, Doctoral dissertation, University of Technology, The University of Da Nang, 2015.

  • Hoang Chi Thanh, Parallel Generation of Permutations by Inversion Vectors,Proceedings of IEEERIVF International Conference on Computing and Communication Technologies, IEEE, ISBN: 9781-4673-0308-8, 2012, pp.129-132.

  • Hoang Chi Thanh, Parallelizing a new algorithm for the set partition problem, Annals UMCS Information AIX, 2(2010) pp. 21-28, DOI:10.2478/v10065-010-0049-1, 2010, (http://dlibra.umcs.lublin.pl/dlibra/plain-content?id=12053)

  • Hoang Chi Thanh, Nguyen Thi Thuy Loan. Nguyen Duy Ham, From Permutations to Iterative Permutations, International Journal of Computer Science Engineering and Technology, Vol 2, Issue 7, 2012, pp. 1310-1315.

  • Hoang Chi Thanh, Parallel combinatorial algorithms for multi-sets and their applications, International Journal of Software Engineering and Knowledge Engineering, Vol. 23, No. 01, 2013, pp.81-99

  • Hoàng Chi Thanh, Inheritance principle and some bounded sequence problems, The Journal of Computer Science and Cybernetics, T.29 S.1, 2013, pp. 79-91.

  • Ivan Stojmenovic, Listing combinatorial objects in parallel, The international journal of parallel emergent and distributed systems, vol. 21, no. 2, April 2006, pp. 127–146.

  • Akl, S.G., Gries, D. and Stojmenovic, I., An optimal parallel algorithm for generating combinations, Information Processing Letters, 33, 1989, pp. 135–139.

  • Akl, S.G., Meijer, H. and Stojmenovi, I., An optimal systolic algorithm for generating permutations in lexicographic order, Journal of Parallel and Distributed Computing, 20(1), 1994, pp. 84–91.

  • Akl, S.G. and Stojmenovic I., Parallel algorithms for generating integer partitions and compositions, The Journal of Combinatorial Mathematics and Combinatorial Computing, 13, 1983, pp. 107–120.

  • Chen, G.H. and Chern, M.S., Parallel generation of permutations and combinations, BIT, 26, 1986, pp. 277–283.

  • Cosnard, M. and Ferreira, A.G., Generating permutations on a VLSI suitable linear network, The Computer Journal, 32(6),1989, pp. 571–573.

  • Djokic, B., Miyakawa, M., Sekiguchi, S., Semba, I. and Stojmenovic, I., Parallel algorithms for generating subsets and set partitions. In: T. Asano, T. Ibaraki, H. Imai and T. Nishizeki (Eds.) Proceedings of SIGAL International Symposium on Algorithms, Tokyo, Japan, Lecture Notes in Computer Science, Vol. 450, 1990, pp. 76–85.

  • Even, S., Algorithmic Combinatorics (New York: Macmillan). Er, M.C., 1988, A parallel algorithm for cost-optimal generation of permutations of r out of n items, Journal of Information & Optimization Sciences, 9, 1973, pp. 53–56.

  • Elhage, H. and Stojmenovic, I., Systolic generation of combinations from arbitrary elements, Parallel Processing Letters, 2(2/3), 1992, pp. 241–248.

  • Gupta, P. and Bhattacharjee, G.P., Parallel generation of permutations, The Computer Journal, 26(2), 1983, pp. 97–105.

  • Kapralski, A., New methods for the generation of permutations, combinations, and other combinatorial objects in parallel, Journal of Parallel and Distributed Computing, 17, 1993, pp. 315– 326.

  • Seyed H. Roosta, Parallel Processing and Parallel Algorithms, Theory and Computation,USA,Springer 1999.

  • Steve Fortune and James Wyllie, Parallelism in random access machines, STOC '78 Proceedings of the tenth annual ACM symposium on Theory ofcomputing, 1978, pp 114-118.

  • Nguyen Dinh Lau, Tran Quoc Chien, Phan Phu Cuong, Le Hong Dung, On the implementation of Goldberg’s maximum Flow Algorithm in extended mixed network, International Journal of computer Science & Information Technology, Vol 9, No 6 pp. 93-102, 2017.

  • Nguyen Dinh Lau, Tran Quoc Chien,Algorithm to Find Maximum Concurent Multicommodity Linear Flow with Limited Cost on Extended Traffic Network with Single Regulating Coeffitient on Two-Side Lines, The International Journal of Computer Networks & Communications, V 9 N2, pp: 57-67, 2017.

  • Nguyen Dinh Lau, Tran Quoc Chien,Traveling Salesman Problem in Distributed Envirenment, Computer Sciencs & Information Technology (CSIT), Fourth International Conference on Advanced Information Technologies and Applications (ICAITA 2015), pp. 19-28, 2015.

  • Peter S. Pacheco, An Introduction to Parallel Programming, Morgan Kaufmann Publishers is an imprint of Elsevier, ISBN 978-0-12-374260-5 (hardback), 2011


Abstract Views: 242

PDF Views: 102




  • Improved Computing Performance for Listing Combinatorial Algorithms Using Multi-processing MPI and Thread Library

Abstract Views: 242  |  PDF Views: 102

Authors

Nguyen Dinh Lau
University of Education and Science, University of Danang, Viet Nam

Abstract


This study builds up two parallel algorithms to improve computing performance for two listing binary and listing permutation algorithms. The problems are extremely interesting and practically applicable in many fields in our daily life. To parallel execution, we divide the data set input and allocate them to the processors. The article focuses on (i) the analysis of the research situation of the related works to compare and evaluate the existing problems of previous works, (ii) the analysis of the input data structure to divide data for the sub processors, (iii) the construction of parallel algorithms - proof of correctness and analysis of computing complexity, and (iv) experiments in multi-processing MPI and Thread library. Then the comparison of the results of the parallel algorithm with the sequential algorithm and the comparison of the execution time on different sub processors is discussed.

Keywords


Parallel Algorithms, Listing Binary, Listing Permutation, Bounded Sequences, Substituend, Inversion.

References