Abstract

Recent years, many applications have exploited graph-based computations for searching massive data through distributed processors and memories. In this study, we present Breadth First Search algorithm as a graph-based algorithm to organize large DNA dataset and parallelize the algorithm using two highly tuned parallel approaches named OpenMP and MPI on a cluster, besides tuning the serial version of the algorithm. OpenMP is implemented using domain decomposition method. MPI is applied after dividing the dataset into equal parts and changing it to a two-dimensional array. Both approaches are tested in Khwarizmi cluster with 8 Intel Xeon Processors at the School of Computer Sciences in USM. The two aforementioned experiments are implemented and evaluated with certain characteristics and the results show high performance is achieved in terms of speedup and efficiency in comparison with the serial version of the algorithm.

Keywords:

BFS, DNA searching, MPI, OpenMP, parallel computing,

References

1. Amer, A., H. Lu, P. Balaji and S. Matsuoka, 2015. Characterizing MPI and hybrid MPI+threads applications at scale: Case study with BFS. Proceeding of the IEEE Workshop on Parallel Programming Model for the Masses (PPMM, 2015), pp: 1075-1083.
   
2. Beamer, S., K. Asanovic and D.A. Patterson, 2011. Searching for a parent instead of fighting over children: A fast breadth-first search implementation for graph500. Tech. Rep. UCB/EECS-2011-117, EECS Department, University of California, Berkeley.
   
3. Beamer, S., A. Buluc, K. Asanovic and D. Patterson, 2013. Distributed memory breadth-first search revisited: Enabling bottom-up search. Proceeding of the IEEE 27th International Parallel and Distributed Processing Symposium Workshops and PhD Forum (IPDPSW, 2013), pp: 1618-1627.
   
4. Checconi, F., F. Petrini, J. Willcock, A. Lumsdaine, A.R. Choudhury and Y. Sabharwal, 2012. Breaking the speed and scalability barriers for graph exploration on distributed-memory machines. Proceeding of the 2012 IEEE International Conference for High Performance Computing, Networking, Storage and Analysis (SC), pp: 1-12.
   CrossRef    
5. Chung, I.H., R.E. Walkup, H.F. Wen and H. Yu, 2006. MPI performance analysis tools on blue gene/L. Proceeding of the ACM/IEEE SC 2006 Conference, pp: 16-16.
   
6. Cong, G., G. Almasi and V. Saraswat, 2010. Fast PGAS implementation of distributed graph algorithms. Proceedings of the International Conference for High Performance Computing, Networking, Storage and Analysis, pp: 1-11.
   CrossRef    
7. Donald, E.K., 1999. The art of computer programming. Sorting Search., 3: 426-458.
   
8. Edmonds, N., J. Willcock, T. Hoefler and A. Lumsdaine, 2010. Design of a large-scale hybrid-parallel graph library. Proceeding of the International Conference on High Performance Computing, Student Research Symposium. Goa, India.
   
9. Harish, P. and P.J. Narayanan, 2007. Accelerating large graph algorithms on the GPU using CUDA. Proceeding of the 14th International Conference on High Performance Computing (HiPC'07), pp: 197-208.
   CrossRef    
10. Hennessy, J.L. and D.A. Patterson, 2011. Computer architecture: A quantitative approach. Elsevier Science, Burlington.
    
11. Hong, S., S.K. Kim, T. Oguntebi and K. Olukotun, 2011a. Accelerating CUDA graph algorithms at maximum warp. ACM SIGPLAN Notices, 46(8): 267-276.
    CrossRef    
12. Hong, S., T. Oguntebi and K. Olukotun, 2011b. Efficient parallel graph exploration on multi-core CPU and GPU. Proceeding of the 2011 IEEE International Conference on Parallel Architectures and Compilation Techniques (PACT, 2011), pp: 78-88.
    CrossRef    
13. Kumar, V., A. Grama, A. Gupta and G. Karypis, 1994. Introduction to Parallel Computing: Design and Analysis of Algorithms. Benjamin/Cummings Publishing Co., Redwood City, CA.
    
14. Madduri, K., D. Ediger, K. Jiang, D. Bader and D. Chavarria-Miranda, 2009. A faster parallel algorithm and efficient multithreaded implementations for evaluating betweenness centrality on massive datasets. Proceeding of the IEEE International Symposium on Parallel and Distributed Processing (IPDPS, 2009), pp: 1-8.
    CrossRef    
15. Mizell, D. and K. Maschhoff, 2006. Early experiences with large-scale XMT systems. Proceeding of the Workshop on Multithreaded Architectures and Applications (MTAAP'09), May 2009.
    PMCid:PMC2704219    
16. Süß, M. and C. Leopold, 2006. Implementing irregular parallel algorithms with OpenMP. In: Nagel, W.E. (Eds.), Euro-Par 2006. LNCS 4128, Springer-Verlag, Berlin, Heidelberg, pp: 635-644.
    CrossRef    
17. Tran, H.N., J.J. Kim and B. He, 2015. Fast subgraph matching on large graphs using graphics processors. In: Renz, M. et al. (Eds.), DASFAA, 2015, Part 1, LNCS 9049, Springer International Publishing, Switzerland, pp: 299-315.
    CrossRef    
18. Yasui, Y., K. Fujisawa and K. Goto, 2013. NUMA-optimized parallel breadth-first search on multicore single-node system. Proceeding of the IEEE International Conference on Big Data, pp: 394-402.
    CrossRef    

Competing interests

The authors have no competing interests.

Open Access Policy

This article is distributed under the terms of the Creative Commons Attribution 4.0 International License (http://creativecommons.org/licenses/by/4.0/), which permits unrestricted use, distribution, and reproduction in any medium, provided you give appropriate credit to the original author(s) and the source, provide a link to the Creative Commons license, and indicate if changes were made.

Copyright

The authors have no competing interests.