CFP last date
22 July 2024
Reseach Article

A New Scheduling Strategy for Solving the Motif Finding Problem on Heterogeneous Architectures

by H. M. Faheem, B. Konig-ries
International Journal of Computer Applications
Foundation of Computer Science (FCS), NY, USA
Volume 101 - Number 5
Year of Publication: 2014
Authors: H. M. Faheem, B. Konig-ries
10.5120/17685-8543

H. M. Faheem, B. Konig-ries . A New Scheduling Strategy for Solving the Motif Finding Problem on Heterogeneous Architectures. International Journal of Computer Applications. 101, 5 ( September 2014), 27-31. DOI=10.5120/17685-8543

@article{ 10.5120/17685-8543,
author = { H. M. Faheem, B. Konig-ries },
title = { A New Scheduling Strategy for Solving the Motif Finding Problem on Heterogeneous Architectures },
journal = { International Journal of Computer Applications },
issue_date = { September 2014 },
volume = { 101 },
number = { 5 },
month = { September },
year = { 2014 },
issn = { 0975-8887 },
pages = { 27-31 },
numpages = {9},
url = { https://ijcaonline.org/archives/volume101/number5/17685-8543/ },
doi = { 10.5120/17685-8543 },
publisher = {Foundation of Computer Science (FCS), NY, USA},
address = {New York, USA}
}
%0 Journal Article
%1 2024-02-06T22:30:55.514956+05:30
%A H. M. Faheem
%A B. Konig-ries
%T A New Scheduling Strategy for Solving the Motif Finding Problem on Heterogeneous Architectures
%J International Journal of Computer Applications
%@ 0975-8887
%V 101
%N 5
%P 27-31
%D 2014
%I Foundation of Computer Science (FCS), NY, USA
Abstract

The Motif Finding Problem is a well-known computationally intensive problem in bioinformatics. Exact solutions to finding a motif such as brute-force suffer from the intractability of their run time. To ameliorate this, different solutions relying on different hardware technologies have been proposed including the usage of FPGA or multicore architectures. Recently, deploying heterogeneous architectures that involve CPUs, GPUs, and FPGA kits seems to be very promising. The main goal is to speed up processing in order to achieve the result in a moderate time. The scheduling strategy dealing with such heterogeneity is one of the most important factors affecting the performance of the heterogeneous systems. In this paper, we introduce a new scheduling strategy that depends on the expected finish time when the problem is solved by only one type of architecture. The proposed scheduling strategy provides the fastest available processor type with a specific size of data items and instructs it to perform the parallel operations. Other slower architectures will get different sizes of data that can be processed exactly in the same time granted to the fastest architecture. This operation will be iterated until the finish of all the processing operations required to get the motif. Evaluation results of solving the motif finding problem using our proposed approach on a set of heterogeneous architectures versus the implementation on an individual architecture are compared. Results show that the new scheduling strategy yields much more advantageous results over the implementation on individual architectures. We believe that the proposed strategy is a step towards a well-defined framework for implementing run-time systems that support heterogeneous architectures

References
  1. P. Pevzner and S. Sze, " Combinatorial approaches to finding subtle signals in DNA sequences," Proceedings of the 8th International Conference on Intelligent Systems for Molecular Biology, 269–78, 2000.
  2. H. M. Faheem, "Accelerating Motif Finding Problem using Grid Computing with Enhanced Brute Force," The 12th International Conference on Advanced Communication Technology (ICACT), Korea, 2010.
  3. M. Raddad, N. El-Fishawi, and H. M. Faheem, "Implementation of Recursive Brute Force for Solving Motif Finding Problem on Multi-Core," International Journal of Systems Biology and Biomedical Technologies, 2 (3):1-18, 2013.
  4. R. Inta and D. J. Bowman, "An FPGA/GPU/CPU hybrid platform for solving hard computational problems," in Proceedings of the eResearch Australasia, Gold Coast, Australia, 2010.
  5. S. J. Park, D. R. Shires, and B. J. Henz, "Coprocessor computing with FPGA and GPU," in Proceedings of the Department of Defense High Performance ComputingModernization Program:Users Group Conference—Solving the Hard Problems, pp. 366–370, Seattle,Wash, USA, 2008.
  6. M. Showerman, J. Enos, A. Pant et al. , "QP: a heterogeneous multi-accelerator cluster," in Proceedings of the 10th LCI International Conference on High-Performance Cluster Computing, vol. 7800, pp. 1–8, Boulder, Colo, USA, 2009.
  7. D. B. Thomas, L. Howes, andW. Luk, "A comparison of CPUs, GPUs, FPGAs, and massively processor arrays for random number generation," in Proceedings of the 7th ACM SIGDA International Symposium on Field-Programmable Gate Arrays (FPGA '09), pp. 63–72, Monterey, Calif, USA, 2009.
  8. K. Underwood, "FPGAs vs. CPUs: trends in peak floatingpoint performance," in Proceedings of the 12th International Symposium on Field-Programmable Gate Arrays (FPGA '04), pp. 171–180, New York, NY, USA, February 2004.
  9. H. Topcuoglu, S. Hariri and M. Wu, "Performance-Effective and Low-Complexity Task Scheduling for Heterogeneous Computing", IEEE Transactions on Parallel and Distributed Systems, vol. 13, no. 3, pp. 260-274, 2002.
  10. L. C. Canon, E. Jeannot, R. Sakellariou and W. Zheng, "Comparative evaluation of the robustness of dag scheduling heuristics", in Sergei Gorlatch, Paraskevi Fragopoulou and Thierry Priol, Grid Computing - Achievements and Prospects, pp. 73-84, Springer, 2008.
  11. Y. Farouk, T. El-Deeb, and H. M. Faheem, "Massively Parallelized DNA Motif Search on FPGA," Bioinformatics - Trends and Methodologies, INTECH, 2011
Index Terms

Computer Science
Information Sciences

Keywords

Motif Finding Problem Heterogeneous architectures Scheduling Strategies