{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T05:10:09Z","timestamp":1730437809733,"version":"3.28.0"},"reference-count":48,"publisher":"Institute of Electronics, Information and Communications Engineers (IEICE)","issue":"11","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["IEICE Trans. Inf. & Syst."],"published-print":{"date-parts":[[2023,11,1]]},"DOI":"10.1587\/transinf.2022edp7230","type":"journal-article","created":{"date-parts":[[2023,10,31]],"date-time":"2023-10-31T22:34:44Z","timestamp":1698791684000},"page":"1783-1795","source":"Crossref","is-referenced-by-count":0,"title":["A Multi-FPGA Implementation of FM-Index Based Genomic Pattern Search"],"prefix":"10.1587","volume":"E106.D","author":[{"given":"Ullah","family":"IMDAD","sequence":"first","affiliation":[{"name":"Department of Information & Computer Science, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Akram","family":"BEN AHMED","sequence":"additional","affiliation":[{"name":"National Institute of Advanced Industrial Science and Technology (AIST)"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kazuei","family":"HIRONAKA","sequence":"additional","affiliation":[{"name":"Department of Information & Computer Science, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Kensuke","family":"IIZUKA","sequence":"additional","affiliation":[{"name":"Department of Information & Computer Science, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Hideharu","family":"AMANO","sequence":"additional","affiliation":[{"name":"Department of Information & Computer Science, Keio University"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"532","reference":[{"key":"1","doi-asserted-by":"crossref","unstructured":"[1] A. Putnam, A.M. Caulfield, E.S. Chung, D. Chiou, K. Constantinides, J. Demme, H. Esmaeilzadeh, J. Fowers, G.P. Gopal, J. Gray, M. Haselman, S. Hauck, S. Heil, A. Hormati, J.-Y. Kim, S. Lanka, J. Larus, E. Peterson, S. Pope, A. Smith, J. Thong, P.Y. Xiao, and D. Burger, \u201cA Reconfigurable Fabric for Accelerating Large-scale Datacenter Services,\u201d Proc. 41st Annual International Symposium on Computer Architecuture, ISCA '14, Piscataway, NJ, USA, pp.13-24, IEEE Press, 2014. 10.1109\/isca.2014.6853195","DOI":"10.1109\/ISCA.2014.6853195"},{"key":"2","doi-asserted-by":"crossref","unstructured":"[2] J. Fowers, K. Ovtcharov, M. Papamichael, T. Massengill, M. Liu, D. Lo, S. Alkalay, M. Haselman, L. Adams, M. Ghandi, S. Heil, P. Patel, A. Sapek, G. Weisz, L. Woods, S. Lanka, S.K. Reinhardt, A.M. Caulfield, E.S. Chung, and D. Burger, \u201cA Configurable Cloud-Scale DNN Processor for Real-Time AI,\u201d 2018 ACM\/IEEE 45th Annual International Symposium on Computer Architecture (ISCA), pp.1-14, June 2018. 10.1109\/isca.2018.00012","DOI":"10.1109\/ISCA.2018.00012"},{"key":"3","unstructured":"[3] Europian Union, \u201cEUROEXA: Path to Exascale.\u201d https:\/\/euroexa.eu\/ (accessed 2021-3-15)."},{"key":"4","doi-asserted-by":"crossref","unstructured":"[4] T. Inage, K. Hironaka, K. Iizuka, K. Ito, Y. Fukushima, M. Namiki, and H. Amano, \u201cM-KUBOS\/PYNQ Cluster for multi-access edge computing,\u201d 2021 Ninth International Symposium on Computing and Networking (CANDAR), pp.95-101, 2021. 10.1109\/candar53791.2021.00020","DOI":"10.1109\/CANDAR53791.2021.00020"},{"key":"5","doi-asserted-by":"crossref","unstructured":"[5] Y. Fukushima, K. Iizuka, and H. Amano, \u201cParallel implementation of cnn on multi-fpga cluster,\u201d 2021 Ninth International Symposium on Computing and Networking (CANDAR), 2021.","DOI":"10.1109\/MCSoC51149.2021.00019"},{"key":"6","doi-asserted-by":"publisher","unstructured":"[6] Y. Turakhia, G. Bejerano, and W.J. Dally, \u201cDarwin: A genomics co-processor provides up to 15,000x acceleration on long read assembly,\u201d SIGPLAN Not., vol.53, no.2, pp.199-213, March 2018. 10.1145\/3296957.3173193","DOI":"10.1145\/3296957.3173193"},{"key":"7","doi-asserted-by":"crossref","unstructured":"[7] P. Ferragina and G. Manzini, \u201cOpportunistic data structures with applications,\u201d Proceedings 41st Annual Symposium on Foundations of Computer Science, pp.390-398, 2000. 10.1109\/sfcs.2000.892127","DOI":"10.1109\/SFCS.2000.892127"},{"key":"8","unstructured":"[8] M. Burrows and D.J. Wheeler, \u201cA block-sorting lossless data compression algorithm,\u201d tech. rep., 1994."},{"key":"9","doi-asserted-by":"crossref","unstructured":"[9] M.M.I. Ullah, A. Ben Ahmed, and H. Amano, \u201cImplementation of fm-index based pattern search on a multi-fpga system,\u201d Applied Reconfigurable Computing. Architectures, Tools, and Applications, ed. F. Rinc\u00f3n, J. Barba, H.K.H. So, P. Diniz, and J. Caba, Cham, vol.12083, pp.376-391, Springer International Publishing, 2020. 10.1007\/978-3-030-44534-8_28","DOI":"10.1007\/978-3-030-44534-8_28"},{"key":"10","doi-asserted-by":"crossref","unstructured":"[10] C. Zhang, D. Wu, J. Sun, G. Sun, G. Luo, and J. Cong, \u201cEnergy-Efficient CNN Implementation on a Deeply Pipelined FPGA Cluster,\u201d Proc. 2016 International Symposium on Low Power Electronics and Design, ISLPED '16, New York, NY, USA, pp.326-331, Association for Computing Machinery, 2016. 10.1145\/2934583.2934644","DOI":"10.1145\/2934583.2934644"},{"key":"11","doi-asserted-by":"crossref","unstructured":"[11] W. Zhang, J. Zhang, M. Shen, G. Luo, and N. Xiao, \u201cAn Efficient Mapping Approach to Large-Scale DNNs on Multi-FPGA Architectures,\u201d 2019 Design, Automation Test in Europe Conference Exhibition (DATE), pp.1241-1244, March 2019. 10.23919\/date.2019.8715174","DOI":"10.23919\/DATE.2019.8715174"},{"key":"12","doi-asserted-by":"crossref","unstructured":"[12] T. Ueno, A. Koshiba, and K. Sano, \u201cVirtual Circuit-Switching Network with Flexible Topology for High-Performance FPGA Cluster,\u201d IEEE International Conference on Application-specific Systems, Architectures and Processors (ASAP), pp.41-48, 2021. 10.1109\/asap52443.2021.00013","DOI":"10.1109\/ASAP52443.2021.00013"},{"key":"13","doi-asserted-by":"crossref","unstructured":"[13] Y. Sano, R. Kobayashi, N. Fujita, and T. Boku, \u201cPerformance evaluation on gpu-fpga accelerated computing considering interconnections between accelerators,\u201d International Symposium on Highly-Efficient Accelerators and Reconfigurable Technologies, pp.10-16, June 2022. 10.1145\/3535044.3535046","DOI":"10.1145\/3535044.3535046"},{"key":"14","doi-asserted-by":"crossref","unstructured":"[14] C. Wu, S. Bandra, T. Geng, V. Sachdeva, W. Sherman, and M. Herbordt, \u201cSystem-Level Modeling of GPU\/FPGA Clusters for Molecular Dynamics Simulation,\u201d IEEE High Performance Extreme Computing Conference (HPEC), 2021. 10.1109\/hpec49654.2021.9622838","DOI":"10.1109\/HPEC49654.2021.9622838"},{"key":"15","doi-asserted-by":"crossref","unstructured":"[15] T. Geng, T. Wang, A. Sanaullah, C. Yang, R. Patel, and M. Herbordt, \u201cA Framework for Acceleration of CNN Training on Deeply-Pipelined FPGA Clusters with Work and Weight Load Balancing,\u201d 2018 28th International Conference on Field Programmable Logic and Applications (FPL), pp.394-398, 2018. 10.1109\/fpl.2018.00074","DOI":"10.1109\/FPL.2018.00074"},{"key":"16","doi-asserted-by":"publisher","unstructured":"[16] A. Mondigo, T. Ueno, K. Sano, and H. Takizawa, \u201cscalability analysis of deeply pipelined tsunami simulation with multiple fpgas,\u201d IEICE Trans. Inf. & Syst., vol.E102-D, no.5, pp.1029-1036, 2019. 10.1587\/transinf.2018rcp0007","DOI":"10.1587\/transinf.2018RCP0007"},{"key":"17","doi-asserted-by":"publisher","unstructured":"[17] K. Sano, Y. Hatsuda, and S. Yamamoto, \u201cMulti-fpga accelerator for scalable stencil computation with constant memory bandwidth,\u201d IEEE Trans. Parallel Distrib. Syst., vol.25, no.3, pp.695-705, 2014. 10.1109\/tpds.2013.51","DOI":"10.1109\/TPDS.2013.51"},{"key":"18","doi-asserted-by":"crossref","unstructured":"[18] C. Zhang, D. Wu, J. Sun, G. Sun, G. Luo, and J. Cong, \u201cEnergy-Efficient CNN Implementation on a Deeply Pipelined FPGA Cluster,\u201d ISLPED, pp.326-331, 2016. 10.1145\/2934583.2934644","DOI":"10.1145\/2934583.2934644"},{"key":"19","doi-asserted-by":"publisher","unstructured":"[19] T.F. Smith and M.S. Waterman, \u201cIdentification of common molecular subsequences,\u201d Journal of Molecular Biology, vol.147, no.1, pp.195-197, 1981. 10.1016\/0022-2836(81)90087-5","DOI":"10.1016\/0022-2836(81)90087-5"},{"key":"20","doi-asserted-by":"crossref","unstructured":"[20] S.B. Needleman and C.D. Wunsch, \u201cA general method applicable to the search for similarities in the amino acid sequence of two proteins,\u201d Journal of Molecular Biology, vol.48, no.3, pp.443-453, 1970. 10.1016\/0022-2836(70)90057-4","DOI":"10.1016\/0022-2836(70)90057-4"},{"key":"21","doi-asserted-by":"crossref","unstructured":"[21] C.W. Yu, K.H. Kwong, K.H. Lee, and P.H.W. Leong, \u201cA smith-waterman systolic cell,\u201d Field Programmable Logic and Application, ed. P.Y.K. Cheung and G.A. Constantinides, Berlin, Heidelberg, vol.2778, pp.375-384, Springer Berlin Heidelberg, 2003. 10.1007\/978-3-540-45234-8_37","DOI":"10.1007\/978-3-540-45234-8_37"},{"key":"22","doi-asserted-by":"crossref","unstructured":"[22] P. Zhang, G. Tan, and G.R. Gao, \u201cImplementation of the smith-waterman algorithm on a reconfigurable supercomputing platform,\u201d Proc. 1st International Workshop on High-Performance Reconfigurable Computing Technology and Applications: Held in Conjunction with SC07, HPRCTA '07, New York, NY, USA, pp.39-48, Association for Computing Machinery, 2007. 10.1145\/1328554.1328565","DOI":"10.1145\/1328554.1328565"},{"key":"23","doi-asserted-by":"crossref","unstructured":"[23] E. Rucci, C. Garcia, G. Botella, A. De Giusti, M. Naiouf, and M. Prieto-Matias, \u201cAccelerating smith-waterman alignment of long dna sequences with opencl on fpga,\u201d Bioinformatics and Biomedical Engineering, ed. I. Rojas and F. Ortu\u00f1o, Cham, vol.10209, pp.500-511, Springer International Publishing, 2017. 10.1007\/978-3-319-56154-7_45","DOI":"10.1007\/978-3-319-56154-7_45"},{"key":"24","doi-asserted-by":"crossref","unstructured":"[24] D.J. Lipman and W.R. Pearson, \u201cRapid and sensitive protein similarity searches,\u201d Science, vol.227, no.4693, pp.1435-41, 1985. 10.1126\/science.2983426","DOI":"10.1126\/science.2983426"},{"key":"25","doi-asserted-by":"crossref","unstructured":"[25] S.F. Altschul, T.L. Madden, A.A. Sch\u00fcffer, J. Zhang, Z. Zhang, W. Miller, and D.J. Lipman, \u201cGapped BLAST and PSI-BLAST: a new generation of protein database search programs,\u201d Nucleic Acids Research, vol.25, no.17, pp.3389-3402, Sept. 1997. 10.1093\/nar\/25.17.3389","DOI":"10.1093\/nar\/25.17.3389"},{"key":"26","doi-asserted-by":"publisher","unstructured":"[26] N. Homer, B. Merriman, and S.F. Nelson, \u201cBfast: An alignment tool for large scale genome resequencing,\u201d PLOS ONE, vol.4, no.11, pp.1-12, Nov. 2009. 10.1371\/journal.pone.0007767","DOI":"10.1371\/journal.pone.0007767"},{"key":"27","doi-asserted-by":"publisher","unstructured":"[27] Z. Ning, A.J. Cox, and J.C. Mullikin, \u201cSsaha: A fast search method for large dna databases,\u201d Genome Research, vol.11, no.10, pp.1725-1729, 2001. 10.1101\/gr.194201","DOI":"10.1101\/gr.194201"},{"key":"28","doi-asserted-by":"publisher","unstructured":"[28] Y. Sogabe and T. Maruyama, \u201cA fast and accurate fpga system for short read mapping based on parallel comparison on hash table,\u201d IEICE Trans. Inf. & Syst., vol.E100-D, no.5, pp.1016-1025, 2017. 10.1587\/transinf.2016edp7262","DOI":"10.1587\/transinf.2016EDP7262"},{"key":"29","doi-asserted-by":"crossref","unstructured":"[29] F. Xia, Y. Dou, and J. Xu, \u201cFpga-based accelerators for blast families with multi-seeds detection and parallel extension,\u201d 2008 2nd International Conference on Bioinformatics and Biomedical Engineering, pp.58-62, 2008. 10.1109\/icbbe.2008.21","DOI":"10.1109\/ICBBE.2008.21"},{"key":"30","doi-asserted-by":"crossref","unstructured":"[30] C.B. Olson, M. Kim, C. Clauson, B. Kogon, C. Ebeling, S. Hauck, and W.L. Ruzzo, \u201cHardware acceleration of short read mapping,\u201d 2012 IEEE 20th International Symposium on Field-Programmable Custom Computing Machines, pp.161-168, 2012. 10.1109\/fccm.2012.36","DOI":"10.1109\/FCCM.2012.36"},{"key":"31","doi-asserted-by":"publisher","unstructured":"[31] B. Langmead and S.L. Salzberg, \u201cFast gapped-read alignment with bowtie 2,\u201d Nat Methods, vol.9, no.4, pp.357-359, 2012. 10.1038\/nmeth.1923","DOI":"10.1038\/nmeth.1923"},{"key":"32","doi-asserted-by":"publisher","unstructured":"[32] R. Li, C. Yu, Y. Li, T.-W. Lam, S.-M. Yiu, K. Kristiansen, and J. Wang, \u201cSOAP2: an improved ultrafast tool for short read alignment,\u201d Bioinformatics, vol.25, no.15, pp.1966-1967, June 2009. 10.1093\/bioinformatics\/btp336","DOI":"10.1093\/bioinformatics\/btp336"},{"key":"33","doi-asserted-by":"crossref","unstructured":"[33] H. Li and R. Durbin, \u201cFast and accurate short read alignment with Burrows-Wheeler transform,\u201d Bioinformatics, vol.25, no.14, pp.1754-1760, May 2009. 10.1093\/bioinformatics\/btp324","DOI":"10.1093\/bioinformatics\/btp324"},{"key":"34","doi-asserted-by":"publisher","unstructured":"[34] R. Luo, T. Wong, J. Zhu, C.-M. Liu, X. Zhu, E. Wu, L.-K. Lee, H. Lin, W. Zhu, D.W. Cheung, H.-F. Ting, S.-M. Yiu, S. Peng, C. Yu, Y. Li, R. Li, and T.-W. Lam, \u201cSoap3-dp: Fast, accurate and sensitive gpu-based short read aligner,\u201d PLOS ONE, vol.8, no.5, pp.1-11, May 2013. 10.1371\/journal.pone.0065632","DOI":"10.1371\/journal.pone.0065632"},{"key":"35","doi-asserted-by":"publisher","unstructured":"[35] Y. Liu, B. Schmidt, and D.L. Maskell, \u201cCUSHAW: a CUDA compatible short read aligner to large genomes based on the Burrows-Wheeler transform,\u201d Bioinformatics, vol.28, no.14, pp.1830-1837, May 2012. 10.1093\/bioinformatics\/bts276","DOI":"10.1093\/bioinformatics\/bts276"},{"key":"36","doi-asserted-by":"publisher","unstructured":"[36] E.B. Fernandez, J. Villarreal, S. Lonardi, and W.A. Najjar, \u201cFhast: Fpga-based acceleration of bowtie in hardware,\u201d IEEE\/ACM Trans. Comput. Biol. Bioinf., vol.12, no.5, pp.973-981, 2015. 10.1109\/tcbb.2015.2405333","DOI":"10.1109\/TCBB.2015.2405333"},{"key":"37","doi-asserted-by":"publisher","unstructured":"[37] H.M. Waidyasooriya and M. Hariyama, \u201cHardware-acceleration of short-read alignment based on the burrows-wheeler transform,\u201d IEEE Trans. Parallel Distrib. Syst., vol.27, no.5, pp.1358-1372, 2016. 10.1109\/tpds.2015.2444376","DOI":"10.1109\/TPDS.2015.2444376"},{"key":"38","doi-asserted-by":"publisher","unstructured":"[38] J. Arram, T. Kaplan, W. Luk, and P. Jiang, \u201cLeveraging fpgas for accelerating short read alignment,\u201d IEEE\/ACM Trans. Comput. Biol. Bioinf., vol.14, no.3, pp.668-677, 2017. 10.1109\/tcbb.2016.2535385","DOI":"10.1109\/TCBB.2016.2535385"},{"key":"39","doi-asserted-by":"crossref","unstructured":"[39] K. Azegami, K. Musha, K. Hironaka, A.B. Ahmed, M. Koibuch, Y. Hu, and H. Amano, \u201cA stdm (static time division multiplexing) switch on a multi-fpga system,\u201d 2019 IEEE 13th International Symposium on Embedded Multicore\/Many-core Systems-on-Chip(MCSoC), pp.328-333, Oct. 2019. 10.1109\/mcsoc.2019.00053","DOI":"10.1109\/MCSoC.2019.00053"},{"key":"40","doi-asserted-by":"crossref","unstructured":"[40] M. Schoeberl, F. Brandner, J. Spars\u00f8, and E. Kasapaki, \u201cA Statically Scheduled Time-Division-Multiplexed Network-on-Chip for Real-Time Systems,\u201d 2012 IEEE\/ACM Sixth International Symposium on Networks-on-Chip, pp.152-160, 2012. 10.1109\/nocs.2012.25","DOI":"10.1109\/NOCS.2012.25"},{"key":"41","unstructured":"[41] PALTEK, Fpga computing platform m-kubos, https:\/\/www.paltek.co.jp\/design\/original\/m-kubos (accessed 2022-06-02)."},{"key":"42","doi-asserted-by":"publisher","unstructured":"[42] Y. Sun and H. Amano, \u201cFic-rnn: A multi-fpga acceleration framework for deep recurrent neural networks,\u201d IEICE Trans. Inf. & Syst., vol.E103-D, no.12, pp.2457-2462, 2020. 10.1587\/transinf.2020pap0003","DOI":"10.1587\/transinf.2020PAP0003"},{"key":"43","doi-asserted-by":"crossref","unstructured":"[43] Y. Yamauchi, A.B. Ahmed, K. Hironaka, K. IIzuka, and H. Amano, \u201cHorizontal division of deep learning applications with all-to-all communication on a multi-FPGA system,\u201d 2020 Eighth International Symposium on Computing and Networking Workshops (CANDARW), pp.277-281, 2020. 10.1109\/candarw51189.2020.00060","DOI":"10.1109\/CANDARW51189.2020.00060"},{"key":"44","doi-asserted-by":"publisher","unstructured":"[44] K. Ito, K. Iizuka, K. Hironaka, Y. Hu, M. Koibuchi, and H. Amano, \u201cImproving the performance of circuit-switched interconnection network for a multi-fpga system,\u201d IEICE Trans. Inf. & Syst., vol.E104-D, no.12, pp.2029-2039, 2021. 10.1587\/transinf.2021pap0002","DOI":"10.1587\/transinf.2021PAP0002"},{"key":"45","doi-asserted-by":"publisher","unstructured":"[45] Y. Hu and M. Koibuchi, \u201cOptimizing Slot Utilization and Network Topology for Communication Pattern on Circuit-Switched Parallel Computing Systems,\u201d IEICE Trans. Inf. & Syst., vol.E102-D, no.2, pp.247-260, 2019. 10.1587\/transinf.2018edp7225","DOI":"10.1587\/transinf.2018EDP7225"},{"key":"46","doi-asserted-by":"publisher","unstructured":"[46] M. Yamakura, R. Takano, A.B. Ahmed, M. Sugaya, and H. Amano, \u201cA multi-tenant resource management system for multi-fpga systems,\u201d IEICE Trans. Inf. & Syst., vol.E104-D, no.12, pp.2078-2088, 2021. 10.1587\/transinf.2021pap0005","DOI":"10.1587\/transinf.2021PAP0005"},{"key":"47","unstructured":"[47] INA228, https:\/\/www.ti.com\/product\/ina228 (accessed 2022-06-02)."},{"key":"48","doi-asserted-by":"crossref","unstructured":"[48] K. Iizuka, H. Takagi, A. Kamei, K. Hironaka, and H. Amano, \u201cPower analysis of directly-connected fpga clusters,\u201d 2022 IEEE Symposium in Low-Power and High-Speed Chips (COOL CHIPS), pp.1-6, 2022. 10.1109\/coolchips54332.2022.9772675","DOI":"10.1109\/COOLCHIPS54332.2022.9772675"}],"container-title":["IEICE Transactions on Information and Systems"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E106.D\/11\/E106.D_2022EDP7230\/_pdf","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2024,11,1]],"date-time":"2024-11-01T04:50:00Z","timestamp":1730436600000},"score":1,"resource":{"primary":{"URL":"https:\/\/www.jstage.jst.go.jp\/article\/transinf\/E106.D\/11\/E106.D_2022EDP7230\/_article"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2023,11,1]]},"references-count":48,"journal-issue":{"issue":"11","published-print":{"date-parts":[[2023]]}},"URL":"https:\/\/doi.org\/10.1587\/transinf.2022edp7230","relation":{},"ISSN":["0916-8532","1745-1361"],"issn-type":[{"type":"print","value":"0916-8532"},{"type":"electronic","value":"1745-1361"}],"subject":[],"published":{"date-parts":[[2023,11,1]]},"article-number":"2022EDP7230"}}