{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T09:02:31Z","timestamp":1758272551127,"version":"3.40.3"},"publisher-location":"Cham","reference-count":75,"publisher":"Springer International Publishing","isbn-type":[{"type":"print","value":"9783030206550"},{"type":"electronic","value":"9783030206567"}],"license":[{"start":{"date-parts":[[2019,1,1]],"date-time":"2019-01-01T00:00:00Z","timestamp":1546300800000},"content-version":"tdm","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":[[2019]]},"DOI":"10.1007\/978-3-030-20656-7_8","type":"book-chapter","created":{"date-parts":[[2019,6,4]],"date-time":"2019-06-04T23:02:40Z","timestamp":1559689360000},"page":"143-164","update-policy":"https:\/\/doi.org\/10.1007\/springer_crossmark_policy","source":"Crossref","is-referenced-by-count":3,"title":["Toward Efficient Architecture-Independent Algorithms for Dynamic Programs"],"prefix":"10.1007","author":[{"given":"Mohammad Mahdi","family":"Javanmard","sequence":"first","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Pramod","family":"Ganapathi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rathish","family":"Das","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Zafar","family":"Ahmad","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Stephen","family":"Tschudi","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Rezaul","family":"Chowdhury","sequence":"additional","affiliation":[],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"297","published-online":{"date-parts":[[2019,5,17]]},"reference":[{"key":"8_CR1","unstructured":"Standard Template Library for Extra Large Data Sets (STXXL). http:\/\/stxxl.sourceforge.net\/"},{"key":"8_CR2","unstructured":"The Stampede Supercomputing Cluster. https:\/\/www.tacc.utexas.edu\/stampede\/"},{"key":"8_CR3","unstructured":"The Stampede2 Supercomputing Cluster. https:\/\/www.tacc.utexas.edu\/systems\/stampede2\/"},{"key":"8_CR4","unstructured":"Top 500 Supercomputers of the World. https:\/\/www.top500.org\/lists\/2018\/06\/"},{"issue":"5","key":"8_CR5","doi-asserted-by":"publisher","first-page":"575","DOI":"10.1147\/rd.395.0575","volume":"39","author":"RC Agarwal","year":"1995","unstructured":"Agarwal, R.C., Balle, S.M., Gustavson, F.G., Joshi, M., Palkar, P.: A three-dimensional approach to parallel matrix multiplication. IBM J. Res. Dev. 39(5), 575\u2013582 (1995)","journal-title":"IBM J. Res. Dev."},{"issue":"1","key":"8_CR6","doi-asserted-by":"publisher","first-page":"3","DOI":"10.1016\/0304-3975(90)90188-N","volume":"71","author":"A Aggarwal","year":"1990","unstructured":"Aggarwal, A., Chandra, A.K., Snir, M.: Communication complexity of PRAMs. Theor. Comput. Sci. 71(1), 3\u201328 (1990)","journal-title":"Theor. Comput. Sci."},{"key":"8_CR7","volume-title":"The Design and Analysis of Computer Algorithms","author":"AV Aho","year":"1974","unstructured":"Aho, A.V., Hopcroft, J.E.: The Design and Analysis of Computer Algorithms. Pearson Education India, Noida (1974)"},{"key":"8_CR8","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1017\/S0962492914000038","volume":"23","author":"G Ballard","year":"2014","unstructured":"Ballard, G., Carson, E., Demmel, J., Hoemmen, M., Knight, N., Schwartz, O.: Communication lower bounds and optimal algorithms for numerical linear algebra. Acta Numer. 23, 1\u2013155 (2014)","journal-title":"Acta Numer."},{"key":"8_CR9","doi-asserted-by":"crossref","unstructured":"Ballard, G., Demmel, J., Holtz, O., Lipshitz, B., Schwartz, O.: Communication-optimal parallel algorithm for strassen\u2019s matrix multiplication. In: Proceedings of the Twenty-Fourth Annual ACM Symposium on Parallelism in Algorithms and Architectures, pp. 193\u2013204. ACM (2012)","DOI":"10.1145\/2312005.2312044"},{"issue":"3","key":"8_CR10","doi-asserted-by":"publisher","first-page":"866","DOI":"10.1137\/090769156","volume":"32","author":"G Ballard","year":"2011","unstructured":"Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Minimizing communication in numerical linear algebra. SIAM J. Matrix Anal. Appl. 32(3), 866\u2013901 (2011)","journal-title":"SIAM J. Matrix Anal. Appl."},{"issue":"6","key":"8_CR11","doi-asserted-by":"publisher","first-page":"32","DOI":"10.1145\/2395116.2395121","volume":"59","author":"G Ballard","year":"2012","unstructured":"Ballard, G., Demmel, J., Holtz, O., Schwartz, O.: Graph expansion and communication costs of fast matrix multiplication. J. ACM (JACM) 59(6), 32 (2012)","journal-title":"J. ACM (JACM)"},{"key":"8_CR12","volume-title":"Dynamic Programming","author":"R Bellman","year":"1957","unstructured":"Bellman, R.: Dynamic Programming. Princeton University Press, Princeton (1957)"},{"key":"8_CR13","doi-asserted-by":"crossref","unstructured":"Bender, M., Ebrahimi, R., Fineman, J., Ghasemiesfeh, G., Johnson, R., McCauley, S.: Cache-adaptive algorithms. In: SODA (2014)","DOI":"10.1137\/1.9781611973402.71"},{"issue":"5","key":"8_CR14","doi-asserted-by":"publisher","first-page":"241","DOI":"10.1016\/j.parco.2009.12.002","volume":"36","author":"A Bulu\u00e7","year":"2010","unstructured":"Bulu\u00e7, A., Gilbert, J.R., Budak, C.: Solving path problems on the GPU. Parallel Comput. 36(5), 241\u2013253 (2010)","journal-title":"Parallel Comput."},{"key":"8_CR15","unstructured":"Cannon, L.E.: A cellular computer to implement the Kalman filter algorithm. Technical report, Montana State University. Bozeman Engineering Research Labs (1969)"},{"key":"8_CR16","doi-asserted-by":"crossref","unstructured":"Carson, E., Knight, N., Demmel, J.: Avoiding communication in two-sided Krylov subspace methods. Technical report, EECS, UC Berkeley (2011)","DOI":"10.21236\/ADA555879"},{"key":"8_CR17","doi-asserted-by":"crossref","unstructured":"Cherng, C., Ladner, R.: Cache efficient simple dynamic programming. In: AofA, pp. 49\u201358 (2005)","DOI":"10.46298\/dmtcs.3368"},{"key":"8_CR18","doi-asserted-by":"crossref","unstructured":"Chowdhury, R., Ganapathi, P., Tang, Y., Tithi, J.J.: Provably efficient scheduling of cache-oblivious wavefront algorithms. In: Proceedings of the 29th ACM Symposium on Parallelism in Algorithms and Architectures, pp. 339\u2013350. ACM, July 2017","DOI":"10.1145\/3087556.3087586"},{"issue":"1","key":"8_CR19","doi-asserted-by":"publisher","first-page":"4","DOI":"10.1145\/3125632","volume":"4","author":"R Chowdhury","year":"2017","unstructured":"Chowdhury, R., et al.: AUTOGEN: automatic discovery of efficient recursive divide-&-conquer algorithms for solving dynamic programming problems. ACM Trans. Parallel Comput. 4(1), 4 (2017). https:\/\/doi.org\/10.1145\/3125632","journal-title":"ACM Trans. Parallel Comput."},{"key":"8_CR20","doi-asserted-by":"crossref","unstructured":"Chowdhury, R.A., Ramachandran, V.: Cache-efficient dynamic programming algorithms for multicores. In: SPAA, pp. 207\u2013216 (2008)","DOI":"10.1145\/1378533.1378574"},{"issue":"4","key":"8_CR21","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."},{"key":"8_CR22","volume-title":"Introduction to Algorithms","author":"TH Cormen","year":"2009","unstructured":"Cormen, T.H., Leiserson, C.E., Rivest, R.L., Stein, C.: Introduction to Algorithms, 3rd edn. The MIT Press, Cambridge (2009)","edition":"3"},{"issue":"2","key":"8_CR23","doi-asserted-by":"publisher","first-page":"203","DOI":"10.1007\/s00453-006-1224-z","volume":"47","author":"P D\u2019Alberto","year":"2007","unstructured":"D\u2019Alberto, P., Nicolau, A.: R-Kleene: a high-performance divide-and-conquer algorithm for the all-pair shortest path for densely connected networks. Algorithmica 47(2), 203\u2013213 (2007)","journal-title":"Algorithmica"},{"issue":"4","key":"8_CR24","doi-asserted-by":"publisher","first-page":"657","DOI":"10.1137\/0210049","volume":"10","author":"E Dekel","year":"1981","unstructured":"Dekel, E., Nassimi, D., Sahni, S.: Parallel matrix and graph algorithms. SIAM J. Comput. 10(4), 657\u2013675 (1981)","journal-title":"SIAM J. Comput."},{"issue":"1","key":"8_CR25","doi-asserted-by":"publisher","first-page":"A206","DOI":"10.1137\/080731992","volume":"34","author":"J Demmel","year":"2012","unstructured":"Demmel, J., Grigori, L., Hoemmen, M., Langou, J.: Communication-optimal parallel and sequential QR and LU factorizations. SIAM J. Sci. Comput. 34(1), A206\u2013A239 (2012)","journal-title":"SIAM J. Sci. Comput."},{"key":"8_CR26","unstructured":"Diament, B., Ferencz, A.: Comparison of parallel APSP algorithms (1999)"},{"key":"8_CR27","doi-asserted-by":"crossref","unstructured":"Djidjev, H., Thulasidasan, S., Chapuis, G., Andonov, R., Lavenier, D.: Efficient multi-GPU computation of all-pairs shortest paths. In: IPDPS, pp. 360\u2013369 (2014)","DOI":"10.1109\/IPDPS.2014.46"},{"key":"8_CR28","doi-asserted-by":"crossref","unstructured":"Driscoll, M., Georganas, E., Koanantakool, P., Solomonik, E., Yelick, K.: A communication-optimal n-body algorithm for direct interactions. In: IPDPS, pp. 1075\u20131084. IEEE (2013)","DOI":"10.1109\/IPDPS.2013.108"},{"key":"8_CR29","unstructured":"Frigo, M., Leiserson, C.E., Prokop, H., Ramachandran, S.: Cache-oblivious algorithms. In: FOCS, pp. 285\u2013297 (1999)"},{"issue":"1","key":"8_CR30","doi-asserted-by":"publisher","first-page":"107","DOI":"10.1016\/0304-3975(89)90101-1","volume":"64","author":"Z Galil","year":"1989","unstructured":"Galil, Z., Giancarlo, R.: Speeding up dynamic programming with applications to molecular biology. TCS 64(1), 107\u2013118 (1989)","journal-title":"TCS"},{"issue":"2","key":"8_CR31","first-page":"213","volume":"21","author":"Z Galil","year":"1994","unstructured":"Galil, Z., Park, K.: Parallel algorithms for dynamic programming recurrences with more than $$O(1)$$ O ( 1 ) dependency. JPDC 21(2), 213\u2013222 (1994)","journal-title":"JPDC"},{"key":"8_CR32","doi-asserted-by":"publisher","DOI":"10.1017\/CBO9780511574931","volume-title":"Algorithms on Strings, Trees and Sequences","author":"D Gusfield","year":"1997","unstructured":"Gusfield, D.: Algorithms on Strings, Trees and Sequences. Cambridge University Press, New York (1997)"},{"issue":"4","key":"8_CR33","doi-asserted-by":"publisher","first-page":"292","DOI":"10.1287\/trsc.28.4.292","volume":"28","author":"MB Habbal","year":"1994","unstructured":"Habbal, M.B., Koutsopoulos, H.N., Lerman, S.R.: A decomposition algorithm for the all-pairs shortest path problem on massively parallel computer architectures. Transp. Sci. 28(4), 292\u2013308 (1994)","journal-title":"Transp. Sci."},{"key":"8_CR34","doi-asserted-by":"crossref","unstructured":"Harish, P., Narayanan, P.: Accelerating large graph algorithms on the GPU using CUDA. In: HiPC, pp. 197\u2013208 (2007)","DOI":"10.1007\/978-3-540-77220-0_21"},{"key":"8_CR35","doi-asserted-by":"crossref","unstructured":"Holzer, S., Wattenhofer, R.: Optimal distributed all pairs shortest paths and applications. In: PODC, pp. 355\u2013364. ACM (2012)","DOI":"10.1145\/2332432.2332504"},{"issue":"9","key":"8_CR36","doi-asserted-by":"publisher","first-page":"1017","DOI":"10.1016\/j.jpdc.2004.03.021","volume":"64","author":"D Irony","year":"2004","unstructured":"Irony, D., Toledo, S., Tiskin, A.: Communication lower bounds for distributed-memory matrix multiplication. J. Parallel Distrib. Comput. 64(9), 1017\u20131026 (2004)","journal-title":"J. Parallel Distrib. Comput."},{"key":"8_CR37","doi-asserted-by":"crossref","unstructured":"Itzhaky, S., et al.: Deriving divide-and-conquer dynamic programming algorithms using solver-aided transformations. In: OOPSLA, pp. 145\u2013164. ACM (2016)","DOI":"10.1145\/3022671.2983993"},{"key":"8_CR38","unstructured":"Jenq, J.F., Sahni, S.: All pairs shortest paths on a hypercube multiprocessor (1987)"},{"issue":"11","key":"8_CR39","doi-asserted-by":"publisher","first-page":"1235","DOI":"10.1016\/0167-8191(93)90029-K","volume":"19","author":"SL Johnsson","year":"1993","unstructured":"Johnsson, S.L.: Minimizing the communication time for matrix multiplication on multiprocessors. Parallel Comput. 19(11), 1235\u20131257 (1993)","journal-title":"Parallel Comput."},{"key":"8_CR40","unstructured":"Katz, G.J., Kider Jr., J.T.: All-pairs shortest-paths for large graphs on the GPU. In: ACM SIGGRAPH\/EUROGRAPHICS, pp. 47\u201355 (2008)"},{"issue":"6","key":"8_CR41","doi-asserted-by":"publisher","first-page":"16","DOI":"10.1109\/MCSE.2013.95","volume":"15","author":"P Kogge","year":"2013","unstructured":"Kogge, P., Shalf, J.: Exascale computing trends: adjusting to the \u201cnew normal\u201d for computer architecture. Comput. Sci. Eng. 15(6), 16\u201326 (2013)","journal-title":"Comput. Sci. Eng."},{"key":"8_CR42","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"165","DOI":"10.1007\/11751649_18","volume-title":"Computational Science and Its Applications - ICCSA 2006","author":"P Krusche","year":"2006","unstructured":"Krusche, P., Tiskin, A.: Efficient longest common subsequence computation using bulk-synchronous parallelism. In: Gavrilova, M.L., et al. (eds.) ICCSA 2006. LNCS, vol. 3984, pp. 165\u2013174. Springer, Heidelberg (2006). https:\/\/doi.org\/10.1007\/11751649_18"},{"key":"8_CR43","volume-title":"Introduction to Parallel Computing: Design and Analysis of Algorithms","author":"V Kumar","year":"1994","unstructured":"Kumar, V., Grama, A., Gupta, A., Karypis, G.: Introduction to Parallel Computing: Design and Analysis of Algorithms, vol. 400. Benjamin\/Cummings, Redwood City (1994)"},{"issue":"2","key":"8_CR44","doi-asserted-by":"publisher","first-page":"124","DOI":"10.1016\/0743-7315(91)90083-L","volume":"13","author":"V Kumar","year":"1991","unstructured":"Kumar, V., Singh, V.: Scalability of parallel algorithms for the all-pairs shortest-path problem. J. Parallel Distrib. Comput. 13(2), 124\u2013138 (1991)","journal-title":"J. Parallel Distrib. Comput."},{"issue":"9","key":"8_CR45","first-page":"1270","volume":"18","author":"W Liu","year":"2007","unstructured":"Liu, W., Schmidt, B., Voss, G., Muller-Wittig, W.: Streaming algorithms for biological sequence alignment on GPUs. TPDS 18(9), 1270\u20131281 (2007)","journal-title":"TPDS"},{"key":"8_CR46","unstructured":"Liu, W., Schmidt, B., Voss, G., Schroder, A., Muller-Wittig, W.: Bio-sequence database scanning on a GPU. In: IPDPS, 8 pp. (2006)"},{"key":"8_CR47","unstructured":"Lund, B., Smith, J.W.: A multi-stage CUDA kernel for Floyd-Warshall. arXiv preprint arXiv:1001.4108 (2010)"},{"issue":"2","key":"8_CR48","first-page":"1","volume":"9","author":"SA Manavski","year":"2008","unstructured":"Manavski, S.A., Valle, G.: CUDA compatible GPU cards as efficient hardware accelerators for Smith-Waterman sequence alignment. BMC Bioinform. 9(2), 1 (2008)","journal-title":"BMC Bioinform."},{"key":"8_CR49","doi-asserted-by":"crossref","unstructured":"Matsumoto, K., Nakasato, N., Sedukhin, S.G.: Blocked all-pairs shortest paths algorithm for hybrid CPU-GPU system. In: HPCC, pp. 145\u2013152 (2011)","DOI":"10.1109\/HPCC.2011.28"},{"issue":"9","key":"8_CR50","doi-asserted-by":"publisher","first-page":"2625","DOI":"10.1109\/TPDS.2017.2671868","volume":"28","author":"H Meyerhenke","year":"2017","unstructured":"Meyerhenke, H., Sanders, P., Schulz, C.: Parallel graph partitioning for complex networks. IEEE Trans. Parallel Distrib. Syst. 28(9), 2625\u20132638 (2017)","journal-title":"IEEE Trans. Parallel Distrib. Syst."},{"key":"8_CR51","doi-asserted-by":"crossref","unstructured":"Nishida, K., Ito, Y., Nakano, K.: Accelerating the dynamic programming for the matrix chain product on the GPU. In: ICNC, pp. 320\u2013326 (2011)","DOI":"10.1109\/ICNC.2011.62"},{"key":"8_CR52","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1","DOI":"10.1007\/978-3-642-33078-0_1","volume-title":"Algorithms and Architectures for Parallel Processing","author":"K Nishida","year":"2012","unstructured":"Nishida, K., Nakano, K., Ito, Y.: Accelerating the dynamic programming for the optimal polygon triangulation on the GPU. In: Xiang, Y., Stojmenovic, I., Apduhan, B.O., Wang, G., Nakano, K., Zomaya, A. (eds.) ICA3PP 2012. LNCS, vol. 7439, pp. 1\u201315. Springer, Heidelberg (2012). https:\/\/doi.org\/10.1007\/978-3-642-33078-0_1"},{"key":"8_CR53","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"1004","DOI":"10.1007\/978-3-642-01970-8_101","volume-title":"Computational Science \u2013 ICCS 2009","author":"G Rizk","year":"2009","unstructured":"Rizk, G., Lavenier, D.: GPU accelerated RNA folding algorithm. In: Allen, G., Nabrzyski, J., Seidel, E., van Albada, G.D., Dongarra, J., Sloot, P.M.A. (eds.) ICCS 2009. LNCS, vol. 5544, pp. 1004\u20131013. Springer, Heidelberg (2009). https:\/\/doi.org\/10.1007\/978-3-642-01970-8_101"},{"issue":"4","key":"8_CR54","doi-asserted-by":"publisher","first-page":"26","DOI":"10.1109\/MM.2015.71","volume":"35","author":"MJ Schulte","year":"2015","unstructured":"Schulte, M.J., et al.: Achieving exascale capabilities through heterogeneous computing. IEEE Micro 35(4), 26\u201336 (2015)","journal-title":"IEEE Micro"},{"issue":"2","key":"8_CR55","doi-asserted-by":"publisher","first-page":"99","DOI":"10.1016\/j.ipl.2004.03.015","volume":"91","author":"JF Sibeyn","year":"2004","unstructured":"Sibeyn, J.F.: External matrix multiplication and all-pairs shortest path. IPL 91(2), 99\u2013106 (2004)","journal-title":"IPL"},{"key":"8_CR56","doi-asserted-by":"crossref","unstructured":"Solomon, S., Thulasiraman, P.: Performance study of mapping irregular computations on GPUs. In: IPDPS Workshops and PhD Forum, pp. 1\u20138 (2010)","DOI":"10.1109\/IPDPSW.2010.5470770"},{"key":"8_CR57","doi-asserted-by":"crossref","unstructured":"Solomonik, E., Ballard, G., Demmel, J., Hoefler, T.: A communication-avoiding parallel algorithm for the symmetric eigenvalue problem. In: SPAA, pp. 111\u2013121. ACM (2017)","DOI":"10.1145\/3087556.3087561"},{"key":"8_CR58","doi-asserted-by":"crossref","unstructured":"Solomonik, E., Buluc, A., Demmel, J.: Minimizing communication in all-pairs shortest paths. In: IPDPS, pp. 548\u2013559 (2013)","DOI":"10.21236\/ADA580350"},{"issue":"1","key":"8_CR59","doi-asserted-by":"crossref","first-page":"3","DOI":"10.1145\/2897188","volume":"3","author":"E Solomonik","year":"2016","unstructured":"Solomonik, E., Carson, E., Knight, N., Demmel, J.: Trade-offs between synchronization, communication, and computation in parallel linear algebra computations. TOPC 3(1), 3 (2016)","journal-title":"TOPC"},{"key":"8_CR60","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"90","DOI":"10.1007\/978-3-642-23397-5_10","volume-title":"Euro-Par 2011 Parallel Processing","author":"E Solomonik","year":"2011","unstructured":"Solomonik, E., Demmel, J.: Communication-optimal parallel 2.5D matrix multiplication and LU factorization algorithms. In: Jeannot, E., Namyst, R., Roman, J. (eds.) Euro-Par 2011. LNCS, vol. 6853, pp. 90\u2013109. Springer, Heidelberg (2011). https:\/\/doi.org\/10.1007\/978-3-642-23397-5_10"},{"key":"8_CR61","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"290","DOI":"10.1007\/978-3-642-14403-5_31","volume-title":"Parallel Processing and Applied Mathematics","author":"P Steffen","year":"2010","unstructured":"Steffen, P., Giegerich, R., Giraud, M.: GPU parallelization of algebraic dynamic programming. In: Wyrzykowski, R., Dongarra, J., Karczewski, K., Wasniewski, J. (eds.) PPAM 2009. LNCS, vol. 6068, pp. 290\u2013299. Springer, Heidelberg (2010). https:\/\/doi.org\/10.1007\/978-3-642-14403-5_31"},{"key":"8_CR62","doi-asserted-by":"crossref","unstructured":"Striemer, G.M., Akoglu, A.: Sequence alignment with GPU: performance and design challenges. In: IPDPS, pp. 1\u201310 (2009)","DOI":"10.1109\/IPDPS.2009.5161066"},{"key":"8_CR63","doi-asserted-by":"crossref","unstructured":"Tan, G., Sun, N., Gao, G.R.: A parallel dynamic programming algorithm on a multi-core architecture. In: SPAA, pp. 135\u2013144. ACM (2007)","DOI":"10.1145\/1248377.1248399"},{"key":"8_CR64","doi-asserted-by":"crossref","unstructured":"Tang, Y., You, R., Kan, H., Tithi, J., Ganapathi, P., Chowdhury, R.: Improving parallelism of recursive stencil computations without sacrificing cache performance. In: WOSC, pp. 1\u20137 (2014)","DOI":"10.1145\/2686745.2686752"},{"issue":"6","key":"8_CR65","doi-asserted-by":"publisher","first-page":"977","DOI":"10.1023\/A:1013588221172","volume":"108","author":"A Tiskin","year":"2002","unstructured":"Tiskin, A.: Bulk-synchronous parallel Gaussian elimination. J. Math. Sci. 108(6), 977\u2013991 (2002)","journal-title":"J. Math. Sci."},{"key":"8_CR66","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"369","DOI":"10.1007\/978-3-540-45145-7_35","volume-title":"Parallel Computing Technologies","author":"A Tiskin","year":"2003","unstructured":"Tiskin, A.: Communication-efficient parallel gaussian elimination. In: Malyshkin, V.E. (ed.) PaCT 2003. LNCS, vol. 2763, pp. 369\u2013383. Springer, Heidelberg (2003). https:\/\/doi.org\/10.1007\/978-3-540-45145-7_35"},{"issue":"2","key":"8_CR67","doi-asserted-by":"publisher","first-page":"179","DOI":"10.1016\/j.future.2006.04.017","volume":"23","author":"A Tiskin","year":"2007","unstructured":"Tiskin, A.: Communication-efficient parallel generic pairwise elimination. Future Gener. Comput. Syst. 23(2), 179\u2013188 (2007)","journal-title":"Future Gener. Comput. Syst."},{"key":"8_CR68","series-title":"Lecture Notes in Computer Science","doi-asserted-by":"publisher","first-page":"178","DOI":"10.1007\/3-540-48224-5_15","volume-title":"Automata, Languages and Programming","author":"A Tiskin","year":"2001","unstructured":"Tiskin, A.: All-pairs shortest paths computation in the BSP model. In: Orejas, F., Spirakis, P.G., van Leeuwen, J. (eds.) ICALP 2001. LNCS, vol. 2076, pp. 178\u2013189. Springer, Heidelberg (2001). https:\/\/doi.org\/10.1007\/3-540-48224-5_15"},{"key":"8_CR69","doi-asserted-by":"crossref","unstructured":"Tithi, J.J., Ganapathi, P., Talati, A., Aggarwal, S., Chowdhury, R.: High-performance energy-efficient recursive dynamic programming with matrix-multiplication-like flexible kernels. In: IPDPS, pp. 303\u2013312 (2015)","DOI":"10.1109\/IPDPS.2015.107"},{"issue":"5","key":"8_CR70","doi-asserted-by":"publisher","first-page":"62","DOI":"10.1109\/MCSE.2014.80","volume":"16","author":"J Towns","year":"2014","unstructured":"Towns, J., et al.: XSEDE: accelerating scientific discovery. Comput. Sci. Eng. 16(5), 62\u201374 (2014)","journal-title":"Comput. Sci. Eng."},{"key":"8_CR71","doi-asserted-by":"publisher","first-page":"2.2","DOI":"10.1145\/996546.996553","volume":"8","author":"Gayathri Venkataraman","year":"2003","unstructured":"Venkataraman, G., Sahni, S., Mukhopadhyaya, S.: A blocked all-pairs shortest-paths algorithm. JEA 8, 2\u20132 (2003)","journal-title":"Journal of Experimental Algorithmics"},{"key":"8_CR72","unstructured":"Volkov, V., Demmel, J.: LU, QR and Cholesky factorizations using vector capabilities of GPUs. EECS, UC Berkeley, Technical report UCB\/EECS-2008-49, May 2008"},{"key":"8_CR73","doi-asserted-by":"publisher","DOI":"10.1007\/978-1-4899-6846-3","volume-title":"Introduction to Computational Biology: Maps","author":"MS Waterman","year":"1995","unstructured":"Waterman, M.S.: Introduction to Computational Biology: Maps. Sequences and Genomes. Chapman & Hall Ltd., New York (1995)"},{"key":"8_CR74","doi-asserted-by":"crossref","unstructured":"Wu, C.C., Wei, K.C., Lin, T.H.: Optimizing dynamic programming on graphics processing units via data reuse and data prefetch with inter-block barrier synchronization. In: ICPADS, pp. 45\u201352 (2012)","DOI":"10.1109\/ICPADS.2012.17"},{"key":"8_CR75","doi-asserted-by":"crossref","unstructured":"Xiao, S., Aji, A.M., Feng, W.c.: On the robust mapping of dynamic programming onto a graphics processing unit. In: ICPADS, pp. 26\u201333 (2009)","DOI":"10.1109\/ICPADS.2009.110"}],"container-title":["Lecture Notes in Computer Science","High Performance Computing"],"original-title":[],"language":"en","link":[{"URL":"http:\/\/link.springer.com\/content\/pdf\/10.1007\/978-3-030-20656-7_8","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,9,19]],"date-time":"2022-09-19T13:39:08Z","timestamp":1663594748000},"score":1,"resource":{"primary":{"URL":"http:\/\/link.springer.com\/10.1007\/978-3-030-20656-7_8"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019]]},"ISBN":["9783030206550","9783030206567"],"references-count":75,"URL":"https:\/\/doi.org\/10.1007\/978-3-030-20656-7_8","relation":{},"ISSN":["0302-9743","1611-3349"],"issn-type":[{"type":"print","value":"0302-9743"},{"type":"electronic","value":"1611-3349"}],"subject":[],"published":{"date-parts":[[2019]]},"assertion":[{"value":"17 May 2019","order":1,"name":"first_online","label":"First Online","group":{"name":"ChapterHistory","label":"Chapter History"}},{"value":"ISC High Performance","order":1,"name":"conference_acronym","label":"Conference Acronym","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"International Conference on High Performance Computing","order":2,"name":"conference_name","label":"Conference Name","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Frankfurt","order":3,"name":"conference_city","label":"Conference City","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Germany","order":4,"name":"conference_country","label":"Conference Country","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"2019","order":5,"name":"conference_year","label":"Conference Year","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"16 June 2019","order":7,"name":"conference_start_date","label":"Conference Start Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"20 June 2019","order":8,"name":"conference_end_date","label":"Conference End Date","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"34","order":9,"name":"conference_number","label":"Conference Number","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"supercomputing2019","order":10,"name":"conference_id","label":"Conference ID","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"https:\/\/www.isc-hpc.com\/","order":11,"name":"conference_url","label":"Conference URL","group":{"name":"ConferenceInfo","label":"Conference Information"}},{"value":"Double-blind","order":1,"name":"type","label":"Type","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Linklings","order":2,"name":"conference_management_system","label":"Conference Management System","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"70","order":3,"name":"number_of_submissions_sent_for_review","label":"Number of Submissions Sent for Review","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"17","order":4,"name":"number_of_full_papers_accepted","label":"Number of Full Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"0","order":5,"name":"number_of_short_papers_accepted","label":"Number of Short Papers Accepted","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"24% - The value is computed by the equation \"Number of Full Papers Accepted \/ Number of Submissions Sent for Review * 100\" and then rounded to a whole number.","order":6,"name":"acceptance_rate_of_full_papers","label":"Acceptance Rate of Full Papers","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"4-5","order":7,"name":"average_number_of_reviews_per_paper","label":"Average Number of Reviews per Paper","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"n\/a","order":8,"name":"average_number_of_papers_per_reviewer","label":"Average Number of Papers per Reviewer","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}},{"value":"Yes","order":9,"name":"external_reviewers_involved","label":"External Reviewers Involved","group":{"name":"ConfEventPeerReviewInformation","label":"Peer Review Information (provided by the conference organizers)"}}]}}