{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:40:31Z","timestamp":1758267631973,"version":"3.41.0"},"publisher-location":"Cham","reference-count":37,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783319436586"},{"type":"electronic","value":"9783319436593"}],"license":[{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"tdm","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"},{"start":{"date-parts":[[2016,1,1]],"date-time":"2016-01-01T00:00:00Z","timestamp":1451606400000},"content-version":"vor","delay-in-days":0,"URL":"http:\/\/www.springer.com\/tdm"}],"content-domain":{"domain":["link.springer.com"],"crossmark-restriction":false},"short-container-title":[],"published-print":{"date-parts":[[2016]]},"DOI":"10.1007\/978-3-319-43659-3_42","type":"book-chapter","created":{"date-parts":[[2016,8,8]],"date-time":"2016-08-08T02:54:01Z","timestamp":1470624841000},"page":"574-587","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":1,"title":["An Efficient Cache-oblivious Parallel Viterbi Algorithm"],"prefix":"10.1007","author":[{"given":"Rezaul","family":"Chowdhury","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pramod","family":"Ganapathi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Vivek","family":"Pradhan","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Jesmin Jahan","family":"Tithi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Yunpeng","family":"Xiao","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2016,8,9]]},"reference":[{"key":"42_CR1","unstructured":"Performance Application Programming Interface (PAPI). http:\/\/icl.cs.utk.edu\/papi\/"},{"key":"42_CR2","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"131","DOI":"10.1007\/978-3-642-28332-1_12","volume-title":"Language and Automata Theory and Applications","author":"P Bille","year":"2012","unstructured":"Bille, P., St\u00f6ckel, M.: Fast and cache-oblivious dynamic programming with local dependencies. In: Dediu, A.-H., Mart\u00edn-Vide, C. (eds.) LATA 2012. LNCS, vol. 7183, pp. 131\u2013142. Springer, Heidelberg (2012)"},{"issue":"1","key":"42_CR3","doi-asserted-by":"publisher","first-page":"78","DOI":"10.1006\/jmbi.1997.0951","volume":"268","author":"C Burge","year":"1997","unstructured":"Burge, C., Karlin, S.: Prediction of complete gene structures in human genomic DNA. J. Mol. Biol. 268(1), 78\u201394 (1997)","journal-title":"J. Mol. Biol."},{"key":"42_CR4","doi-asserted-by":"crossref","unstructured":"Cherng, C., Ladner, R.E.: Cache efficient simple dynamic programming. In: Proceedings of AofA, pp. 49\u201358 (2005)","DOI":"10.46298\/dmtcs.3368"},{"key":"42_CR5","doi-asserted-by":"crossref","unstructured":"Chin, W., Tan, S., Teo, Y.: Deriving efficient parallel programs for complex recurrences. In: Proceedings of PASCO, pp. 101\u2013110 (1997)","DOI":"10.1145\/266670.266697"},{"key":"42_CR6","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"579","DOI":"10.1007\/3-540-61626-8_78","volume-title":"Euro-Par \u201996 - Parallel Processing","author":"WN Chin","year":"1996","unstructured":"Chin, W.N., Darlington, J., Guo, Y.: Parallelizing conditional recurrences. In: Fraigniaud, P., Mignotte, A., Boug\u00e9, L., Robert, Y. (eds.) Euro-Par 1996. LNCS, vol. 1123, pp. 579\u2013586. Springer, Heidelberg (1996)"},{"key":"42_CR7","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ganapathi, P., Tithi, J.J., Bachmeier, C., Kuszmaul, B.C., Leiserson, C.E., Solar-Lezama, A., Tang, Y.: AutoGen: automatic discovery of cache-oblivious parallel recursive algorithms for solving dynamic programs. In: Proceedings of PPoPP, p. 10. ACM (2016)","DOI":"10.1145\/2851141.2851167"},{"key":"42_CR8","unstructured":"Chowdhury, R.A.: Cache-efficient algorithms and data structures: theory and experimental evaluation. Ph.D. thesis, Department of Computer Sciences, The University of Texas at Austin (2007)"},{"key":"42_CR9","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-oblivious dynamic programming. In: Proceedings of SODA, pp. 591\u2013600 (2006)","DOI":"10.1145\/1109557.1109622"},{"key":"42_CR10","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-efficient dynamic programming algorithms for multicores. In: Proceedings of SPAA, pp. 207\u2013216 (2008)","DOI":"10.1145\/1378533.1378574"},{"issue":"4","key":"42_CR11","doi-asserted-by":"publisher","first-page":"878","DOI":"10.1007\/s00224-010-9273-8","volume":"47","author":"RA Chowdhury","year":"2010","unstructured":"Chowdhury, R.A., Ramachandran, V.: The cache-oblivious Gaussian elimination paradigm: theoretical framework, parallelization and experimental evaluation. Theory Comput. Syst. 47(4), 878\u2013919 (2010)","journal-title":"Theory Comput. Syst."},{"issue":"7","key":"42_CR12","doi-asserted-by":"publisher","first-page":"911","DOI":"10.1016\/j.jpdc.2013.04.008","volume":"73","author":"RA Chowdhury","year":"2013","unstructured":"Chowdhury, R.A., Ramachandran, V., Silvestri, F., Blakeley, B.: Oblivious algorithms for multicores and networks of processors. J. Parallel Distrib. Comput. 73(7), 911\u2013925 (2013)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"3","key":"42_CR13","doi-asserted-by":"publisher","first-page":"495","DOI":"10.1109\/TCBB.2008.94","volume":"7","author":"RA Chowdhury","year":"2010","unstructured":"Chowdhury, R.A., Le, H.S., Ramachandran, V.: Cache-oblivious dynamic programming for bioinformatics. IEEE\/ACM Trans. Comput. Biol. Bioinf. 7(3), 495\u2013510 (2010)","journal-title":"IEEE\/ACM Trans. Comput. Biol. Bioinf."},{"key":"42_CR14","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2001","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms. MIT Press, Cambridge (2001)"},{"issue":"6","key":"42_CR15","doi-asserted-by":"publisher","first-page":"2531","DOI":"10.1109\/18.720548","volume":"44","author":"DJ Costello","year":"1998","unstructured":"Costello, D.J., Hagenauer, J., Imai, H., Wicker, S.B.: Applications of error-control coding. IEEE Trans. Inf. Theory 44(6), 2531\u20132560 (1998)","journal-title":"IEEE Trans. Inf. Theory"},{"key":"42_CR16","doi-asserted-by":"crossref","unstructured":"Cutting, D., Kupiec, J., Pedersen, J., Sibun, P.: A practical part-of-speech tagger. In: Proceedings of ANLC, pp. 133\u2013140. Association for Computational Linguistics (1992)","DOI":"10.3115\/974499.974523"},{"key":"42_CR17","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511790492","volume-title":"Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids","author":"R Durbin","year":"1998","unstructured":"Durbin, R., Eddy, S.R., Krogh, A., Mitchison, G.: Biological Sequence Analysis: Probabilistic Models of Proteins and Nucleic Acids. Cambridge University Press, Cambridge (1998)"},{"issue":"1","key":"42_CR18","first-page":"165","volume":"15","author":"M Ferreira","year":"2014","unstructured":"Ferreira, M., Roma, N., Russo, L.M.: Cache-oblivious parallel SIMD Viterbi decoding for sequence search in HMMER. Bioinformatics 15(1), 165 (2014)","journal-title":"Bioinformatics"},{"issue":"6","key":"42_CR19","doi-asserted-by":"publisher","first-page":"135","DOI":"10.1145\/773473.178255","volume":"29","author":"AL Fisher","year":"1994","unstructured":"Fisher, A.L., Ghuloum, A.M.: Parallelizing complex scans and reductions. ACM SIGPLAN Notices 29(6), 135\u2013146 (1994)","journal-title":"ACM SIGPLAN Notices"},{"key":"42_CR20","doi-asserted-by":"crossref","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: Proceedings of FOCS, pp. 285\u2013297 (1999)","DOI":"10.1109\/SFFCS.1999.814600"},{"issue":"5","key":"42_CR21","doi-asserted-by":"publisher","first-page":"835","DOI":"10.1109\/TCOM.1971.1090711","volume":"19","author":"J Heller","year":"1971","unstructured":"Heller, J., Jacobs, I.: Viterbi decoding for satellite and space communication. IEEE Trans. Commun. Technol. 19(5), 835\u2013848 (1971)","journal-title":"IEEE Trans. Commun. Technol."},{"key":"42_CR22","doi-asserted-by":"crossref","unstructured":"Klein, D., Manning, C.D.: A$$^*$$ parsing: fast exact Viterbi parse selection. In: Proceedings of NAACL, pp. 40\u201347 (2003)","DOI":"10.3115\/1073445.1073461"},{"issue":"1","key":"42_CR23","doi-asserted-by":"publisher","first-page":"64","DOI":"10.1147\/rd.151.0064","volume":"15","author":"H Kobayashi","year":"1971","unstructured":"Kobayashi, H.: Application of probabilistic decoding to digital magnetic recording systems. IBM J. Res. Dev. 15(1), 64\u201374 (1971)","journal-title":"IBM J. Res. Dev."},{"issue":"3","key":"42_CR24","doi-asserted-by":"publisher","first-page":"567","DOI":"10.1006\/jmbi.2000.4315","volume":"305","author":"A Krogh","year":"2001","unstructured":"Krogh, A., Larsson, B., Von Heijne, G., Sonnhammer, E.L.: Predicting transmembrane protein topology with a hidden Markov model: application to complete genomes. J. Mol. Biol. 305(3), 567\u2013580 (2001)","journal-title":"J. Mol. Biol."},{"key":"42_CR25","unstructured":"Liu, C.: cuHMM: A CUDA implementation of hidden Markov model training and classification. The Chronicle of Higher Education (2009)"},{"issue":"8","key":"42_CR26","doi-asserted-by":"crossref","first-page":"219","DOI":"10.1145\/2692916.2555264","volume":"49","author":"Saeed Maleki","year":"2014","unstructured":"Maleki, S., Musuvathi, M., Mytkowicz, T.: Parallelizing dynamic programming through rank convergence. In: Proceedings of PPoPP, pp. 219\u2013232 (2014)","journal-title":"ACM SIGPLAN Notices"},{"issue":"4","key":"42_CR27","first-page":"26","volume":"2","author":"S Maleki","year":"2016","unstructured":"Maleki, S., Musuvathi, M., Mytkowicz, T.: Low-rank methods for parallelizing dynamic programming algorithms. ACM Trans. Parallel Comp. 2(4), 26 (2016)","journal-title":"ACM Trans. Parallel Comp."},{"key":"42_CR28","unstructured":"Nam, H., Kwak, H.: Viterbi decoder for a high definition television (1998). http:\/\/www.google.com\/patents\/US5844945 US Patent 5,844,945"},{"issue":"Suppl 1","key":"42_CR29","doi-asserted-by":"crossref","first-page":"S199","DOI":"10.1093\/bioinformatics\/17.suppl_1.S199","volume":"17","author":"U. Ohler","year":"2001","unstructured":"Ohler, U., Niemann, H., Liao, G.C., Rubin, G.M.: Joint modeling of DNA sequence and physical properties to improve eukaryotic promoter recognition. Bioinformatics 17(Suppl. 1), S199\u2013S206 (2001)","journal-title":"Bioinformatics"},{"issue":"8","key":"42_CR30","doi-asserted-by":"publisher","first-page":"1034","DOI":"10.1101\/gr.3715005","volume":"15","author":"A Siepel","year":"2005","unstructured":"Siepel, A., Bejerano, G., Pedersen, J.S., Hinrichs, A.S., Hou, M., Rosenbloom, K., Clawson, H., Spieth, J., Hillier, L.W., Richards, S., et al.: Evolutionarily conserved elements in vertebrate, insect, worm, and yeast genomes. Genome Res. 15(8), 1034\u20131050 (2005)","journal-title":"Genome Res."},{"key":"42_CR31","doi-asserted-by":"crossref","unstructured":"Tan, G., Feng, S., Sun, N.: Locality and parallelism optimization for dynamic programming algorithm in bioinformatics. In: Proceedings of SC, p. 78 (2006)","DOI":"10.1109\/SC.2006.41"},{"issue":"5","key":"42_CR32","doi-asserted-by":"publisher","first-page":"862","DOI":"10.1109\/TPDS.2011.218","volume":"23","author":"S Tang","year":"2012","unstructured":"Tang, S., Yu, C., Sun, J., Lee, B.S., Zhang, T., Xu, Z., Wu, H.: EasyPDP: an efficient parallel dynamic programming runtime system for computational biology. IEEE Trans. Parallel Distrib. Syst. 23(5), 862\u2013872 (2012)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"42_CR33","doi-asserted-by":"crossref","unstructured":"Tang, Y., Chowdhury, R.A., Luk, C.K., Leiserson, C.E.: Coding stencil computations using the Pochoir stencil-specification language. In: Proceedings of HotPar (2011)","DOI":"10.1145\/1989493.1989508"},{"key":"42_CR34","doi-asserted-by":"crossref","unstructured":"Tithi, J.J., Ganapathi, P., Talati, A., Aggarwal, S., Chowdhury, R.A.: High-performance energy-efficient recursive dynamic programming with matrix-multiplication-like flexible kernels. In: Proceedings of IPDPS (2015)","DOI":"10.1109\/IPDPS.2015.107"},{"key":"42_CR35","doi-asserted-by":"crossref","unstructured":"Treibig, J., Hager, G., Wellein, G.: Likwid: a lightweight performance-oriented tool suite for x86 multicore environments. In: Proceedings of ICPPW, pp. 207\u2013216 (2010)","DOI":"10.1109\/ICPPW.2010.38"},{"issue":"2","key":"42_CR36","doi-asserted-by":"publisher","first-page":"260","DOI":"10.1109\/TIT.1967.1054010","volume":"13","author":"AJ Viterbi","year":"1967","unstructured":"Viterbi, A.J.: Error bounds for convolutional codes and an asymptotically optimum decoding algorithm. IEEE Trans. Inf. Theory 13(2), 260\u2013269 (1967)","journal-title":"IEEE Trans. Inf. Theory"},{"issue":"5","key":"42_CR37","doi-asserted-by":"publisher","first-page":"751","DOI":"10.1109\/TCOM.1971.1090700","volume":"19","author":"AJ Viterbi","year":"1971","unstructured":"Viterbi, A.J.: Convolutional codes and their performance in communication systems. IEEE Trans. Commun. Technol. 19(5), 751\u2013772 (1971)","journal-title":"IEEE Trans. Commun. Technol."}],"container-title":["Lecture Notes in Computer Science","Euro-Par 2016: Parallel Processing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-319-43659-3_42","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,4]],"date-time":"2025-06-04T15:58:06Z","timestamp":1749052686000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-319-43659-3_42"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016]]},"ISBN":["9783319436586","9783319436593"],"references-count":37,"URL":"https:\/\/doi.org\/10.1007\/978-3-319-43659-3_42","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2016]]},"assertion":[{"value":"9 August 2016","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"Euro-Par","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"European Conference on Parallel Processing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Grenoble","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"France","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2016","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"24 August 2016","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"26 August 2016","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"22","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"europar2016","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/europar2016.inria.fr\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"This content has been made available to all.","name":"free","label":"Free to read"}]}}