{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,6,19]],"date-time":"2025-06-19T04:51:44Z","timestamp":1750308704801,"version":"3.41.0"},"reference-count":18,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2012,12,5]],"date-time":"2012-12-05T00:00:00Z","timestamp":1354665600000},"content-version":"vor","delay-in-days":0,"URL":"https:\/\/www.acm.org\/publications\/policies\/copyright_policy#Background"}],"content-domain":{"domain":["dl.acm.org"],"crossmark-restriction":true},"short-container-title":["SIGARCH Comput. Archit. News"],"published-print":{"date-parts":[[2012,12,5]]},"abstract":"<jats:p>A novel efficient hardware architecture to optimize the execution time of dynamic programming-based (DP) pairwise sequence alignment algorithms in hardware is proposed. It is realized by introducing an efficient overlapped scheduling of alignment matrix computation and substitution coefficients' pre-loading onto processing elements (PEs) in folded systolic arrays. A new metric is also proposed as an independent performance evaluator to compare different core implementations on different FPGA platforms fairly. Implementation results show that the new hardware architecture for sequence alignment achieves a minimum of 40 percent area normalized speed-up compared to the state-of-the-art hardware implementation, with the speed-up growing linearly with the number of folds e.g. 120 percent speed-up for 16-fold. Compared to equivalent software implementations, the novel hardware architecture achieves a minimum of 103x speed-up, with the speed-up growing linearly with the number of folds e.g. 140x speed-up for 20-fold.<\/jats:p>","DOI":"10.1145\/2411116.2411121","type":"journal-article","created":{"date-parts":[[2012,12,11]],"date-time":"2012-12-11T13:13:42Z","timestamp":1355231622000},"page":"26-31","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":6,"title":["Efficient architecture and scheduling technique for pairwise sequence alignment"],"prefix":"10.1145","volume":"40","author":[{"given":"M. N.","family":"Isa","sequence":"first","affiliation":[{"name":"System Level, Integration Group, School of Engineering, University of Edinburgh, U.K"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"K.","family":"Benkrid","sequence":"additional","affiliation":[{"name":"System Level, Integration Group, School of Engineering, University of Edinburgh, U.K"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"T.","family":"Clayton","sequence":"additional","affiliation":[{"name":"System Level, Integration Group, School of Engineering, University of Edinburgh, U.K"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2012,12,5]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"crossref","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models for Proteins and Nucleic Acids: Cambridge University Press","author":"Durbin R.","year":"1998","unstructured":"R. Durbin , Eddy, S., Krogh, A., Mitchison, G , Biological Sequence Analysis: Probabilistic Models for Proteins and Nucleic Acids: Cambridge University Press , Cambridge UK , 1998 . R. Durbin, Eddy, S., Krogh, A., Mitchison, G, Biological Sequence Analysis: Probabilistic Models for Proteins and Nucleic Acids: Cambridge University Press, Cambridge UK, 1998."},{"key":"e_1_2_1_2_1","volume-title":"International Workshop on Field Programmable Logic and Applications","author":"Hoang D. T.","year":"1992","unstructured":"D. T. Hoang , \" FPGA Implementation of Systolic Sequence Alignment ,\" presented at International Workshop on Field Programmable Logic and Applications , Vienna, Austria , 1992 . D. T. Hoang, \"FPGA Implementation of Systolic Sequence Alignment,\" presented at International Workshop on Field Programmable Logic and Applications, Vienna, Austria, 1992."},{"key":"e_1_2_1_3_1","volume-title":"A SIMD solution to the sequence comparison problem on the MGAP,\" presented at International Conference on Application Specific Array Processors","author":"Borah M.","year":"1994","unstructured":"M. Borah , R. S. Ba}wa, S. Hannenhalli , and M. J. Irwin , \" A SIMD solution to the sequence comparison problem on the MGAP,\" presented at International Conference on Application Specific Array Processors , 1994 . M. Borah, R. S. Ba}wa, S. Hannenhalli, and M. J. Irwin, \"A SIMD solution to the sequence comparison problem on the MGAP,\" presented at International Conference on Application Specific Array Processors, 1994."},{"unstructured":"L. G. David M. Dahle Eric Rice Richard Hughey \"The UCSC Kestrel General Purpose Parallel Processor. \" presented at PDPTA 1999.  L. G. David M. Dahle Eric Rice Richard Hughey \"The UCSC Kestrel General Purpose Parallel Processor. \" presented at PDPTA 1999.","key":"e_1_2_1_4_1"},{"key":"e_1_2_1_5_1","volume-title":"Massively parallel solutions for molecular sequence analysis,\" presented at International Symposium on Parallel and Distributed Processing (IPDPS","author":"Schmidt B.","year":"2002","unstructured":"B. Schmidt , H. Schroder , and M. Schimmler , \" Massively parallel solutions for molecular sequence analysis,\" presented at International Symposium on Parallel and Distributed Processing (IPDPS 2002 ), 2002. B. Schmidt, H. Schroder, and M. Schimmler, \"Massively parallel solutions for molecular sequence analysis,\" presented at International Symposium on Parallel and Distributed Processing (IPDPS 2002), 2002."},{"key":"e_1_2_1_6_1","first-page":"609","article-title":"SAMBA: hardware accelerator for biological sequence comparison","volume":"13","author":"Guerdoux-Jamet P.","year":"1997","unstructured":"P. Guerdoux-Jamet and D. Lavenier , \" SAMBA: hardware accelerator for biological sequence comparison ,\" Journal of Computer applications in the biosciences : CABIOS , vol. 13 , pp. 609 -- 615 , 1997 . P. Guerdoux-Jamet and D. Lavenier, \"SAMBA: hardware accelerator for biological sequence comparison,\" Journal of Computer applications in the biosciences : CABIOS, vol. 13, pp. 609--615, 1997.","journal-title":"Journal of Computer applications in the biosciences : CABIOS"},{"key":"e_1_2_1_7_1","first-page":"191","article-title":"BioSCAN: a network sharable computational resource for searching biosequence databases","volume":"12","author":"Singh R. K.","year":"1996","unstructured":"R. K. Singh , D. L. Hoffman , S. G. Tell , and C. T. White , \" BioSCAN: a network sharable computational resource for searching biosequence databases ,\" Computer applications in the biosciences : CABIOS , vol. 12 , pp. 191 -- 196 , 1996 . R. K. Singh, D. L. Hoffman, S. G. Tell, and C. T. White, \"BioSCAN: a network sharable computational resource for searching biosequence databases,\" Computer applications in the biosciences : CABIOS, vol. 12, pp. 191--196, 1996.","journal-title":"Computer applications in the biosciences : CABIOS"},{"key":"e_1_2_1_8_1","volume-title":"Proceedings of the International Conference on","author":"Chow E.","year":"1991","unstructured":"E. Chow , T. Hunkapiller , J. Peterson , and M. S. Waterman , \" Biological information signal processor,\" presented at Application Specific Array Processors, 1991 . Proceedings of the International Conference on , 1991 . E. Chow, T. Hunkapiller, J. Peterson, and M. S. Waterman, \"Biological information signal processor,\" presented at Application Specific Array Processors, 1991. Proceedings of the International Conference on, 1991."},{"doi-asserted-by":"publisher","key":"e_1_2_1_9_1","DOI":"10.1109\/TVLSI.2008.2005314"},{"doi-asserted-by":"publisher","key":"e_1_2_1_10_1","DOI":"10.1145\/1328554.1328565"},{"key":"e_1_2_1_11_1","volume-title":"An FPGA-based parameterised and scalable optimal solutions for pairwise biological sequence analysis,\" presented at 2011 NASAIESA Conference on Adaptive Hardware and Systems (AHS)","author":"Isa M. N.","year":"2011","unstructured":"M. N. Isa , K. Benkrid , T. Clayton , C. Ling , and A. T. Erdogan , \" An FPGA-based parameterised and scalable optimal solutions for pairwise biological sequence analysis,\" presented at 2011 NASAIESA Conference on Adaptive Hardware and Systems (AHS) , 2011 . M. N. Isa, K. Benkrid, T. Clayton, C. Ling, and A. T. Erdogan, \"An FPGA-based parameterised and scalable optimal solutions for pairwise biological sequence analysis,\" presented at 2011 NASAIESA Conference on Adaptive Hardware and Systems (AHS), 2011."},{"key":"e_1_2_1_12_1","volume-title":"12th International Conference on Field-Programmable Logic and Applications: Springer-Verlag","author":"Yoshiki Y.","year":"2002","unstructured":"Y. Yoshiki , M. Yosuke , M. Tsutomu , and K. Akihiko , \" High Speed Homology Search Using Run-Time Reconfiguration,\" in Proceedings of the Reconfigurable Computing Is Going Mainstream , 12th International Conference on Field-Programmable Logic and Applications: Springer-Verlag , 2002 . Y. Yoshiki, M. Yosuke, M. Tsutomu, and K. Akihiko, \"High Speed Homology Search Using Run-Time Reconfiguration,\" in Proceedings of the Reconfigurable Computing Is Going Mainstream, 12th International Conference on Field-Programmable Logic and Applications: Springer-Verlag, 2002."},{"doi-asserted-by":"publisher","key":"e_1_2_1_13_1","DOI":"10.1109\/TCSII.2005.853340"},{"doi-asserted-by":"publisher","key":"e_1_2_1_14_1","DOI":"10.1016\/0022-2836(82)90398-9"},{"volume-title":"CA 2009.","author":"Guide Family User","unstructured":"\"Virtex-5 Family User Guide ,\" Iilinx, Inc. , San Jose , CA 2009. \"Virtex-5 Family User Guide,\" Iilinx, Inc., San Jose, CA 2009.","key":"e_1_2_1_15_1"},{"volume-title":"CA 2009.","author":"Overview Family","unstructured":"\"Virtex-5 Family Overview ,\" Iilinx, Inc. , San Jose , CA 2009. \"Virtex-5 Family Overview,\" Iilinx, Inc., San Jose, CA 2009.","key":"e_1_2_1_16_1"},{"doi-asserted-by":"crossref","unstructured":"Y.\n      Yamaguchi \"\n  FPGA-Based Smith-Waterman Algorithm: Analysis and Novel Design Reconfigurable Computing: Architectures Tools and Applications \" vol. \n  6578 Lecture Notes in Computer Science\n  : \n  Springer Berlin I Heidelberg 2011 pp. \n  181\n  --\n  192\n  .   Y. Yamaguchi et al. \"FPGA-Based Smith-Waterman Algorithm: Analysis and Novel Design Reconfigurable Computing: Architectures Tools and Applications \" vol. 6578 Lecture Notes in Computer Science: Springer Berlin I Heidelberg 2011 pp. 181--192.","key":"e_1_2_1_17_1","DOI":"10.1007\/978-3-642-19475-7_20"},{"doi-asserted-by":"publisher","key":"e_1_2_1_18_1","DOI":"10.1109\/TCSII.2007.909857"}],"container-title":["ACM SIGARCH Computer Architecture News"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2411116.2411121","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/2411116.2411121","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:13:59Z","timestamp":1750277639000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/2411116.2411121"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2012,12,5]]},"references-count":18,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2012,12,5]]}},"alternative-id":["10.1145\/2411116.2411121"],"URL":"https:\/\/doi.org\/10.1145\/2411116.2411121","relation":{},"ISSN":["0163-5964"],"issn-type":[{"type":"print","value":"0163-5964"}],"subject":[],"published":{"date-parts":[[2012,12,5]]},"assertion":[{"value":"2012-12-05","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}