{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:38:38Z","timestamp":1787337518159,"version":"build-2736575974"},"reference-count":25,"publisher":"Society for Industrial & Applied Mathematics (SIAM)","issue":"6","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["SIAM J. Comput."],"published-print":{"date-parts":[[2005,1]]},"abstract":"<jats:p>Parallel disks promise to be a cost effective means for achieving high bandwidth in applications involving massive data sets, but algorithms for parallel disks can be difficult to devise. To combat this problem, we define a useful and natural duality between writing to parallel disks and the seemingly more difficult problem of prefetching. We first explore this duality for applications involving read-once accesses using parallel disks. We get a simple linear time algorithm for computing optimal prefetch schedules and analyze the efficiency of the resulting schedules for randomly placed data and for arbitrary interleaved accesses to striped sequences. Duality also provides an optimal schedule for prefetching plus caching, where blocks can be accessed multiple times. Another application of this duality gives us the first parallel disk sorting algorithms that are provably optimal up to lower-order terms. One of these algorithms is a simple and practical variant of multiway mergesort, addressing a question that had been open for some time.<\/jats:p>","DOI":"10.1137\/s0097539703431573","type":"journal-article","created":{"date-parts":[[2005,9,7]],"date-time":"2005-09-07T21:00:16Z","timestamp":1126126816000},"page":"1443-1463","source":"Crossref","is-referenced-by-count":11,"title":["Duality Between Prefetching and Queued Writing with Parallel Disks"],"prefix":"10.1137","volume":"34","author":[{"given":"David A.","family":"Hutchinson","sequence":"first","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Peter","family":"Sanders","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]},{"given":"Jeffrey Scott","family":"Vitter","sequence":"additional","affiliation":[],"role":[{"vocabulary":"crossref","role":"author"}]}],"member":"351","published-online":{"date-parts":[[2006,7,27]]},"reference":[{"key":"R1","doi-asserted-by":"publisher","DOI":"10.1145\/48529.48535"},{"key":"R2","doi-asserted-by":"publisher","DOI":"10.1007\/PL00009158"},{"key":"R3","doi-asserted-by":"crossref","unstructured":"S. Albers and M. B\u00fcttner,\n                      Integrated prefetching and caching in single and parallel disk systems\n                      , in Proceedings of the 15th Annual ACM Symposium on Parallel Algorithms and Architectures, San Diego, 2003, pp. 109\u2013117.","DOI":"10.1145\/777412.777431"},{"key":"R4","doi-asserted-by":"crossref","unstructured":"Susanne Albers, Naveen Garg, Stefano Leonardi, Minimizing stall time in single and parallel disk systems, ACM, New York, 1999, 454\u2013462MR1715594","DOI":"10.1145\/276698.276858"},{"key":"R5","doi-asserted-by":"publisher","DOI":"10.1016\/S0167-8191(97)00015-X"},{"key":"R6","doi-asserted-by":"publisher","DOI":"10.1007\/s00224-002-1031-0"},{"key":"R7","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"R8","volume-title":"Online computation and competitive analysis","author":"Borodin Allan","year":"1998"},{"key":"R9","doi-asserted-by":"publisher","DOI":"10.1145\/235543.235544"},{"key":"R10","doi-asserted-by":"crossref","unstructured":"F. Dehne, W. Dittrich, and D. Hutchinson,\n                      Efficient external memory algorithms by simulating coarse\u2010grained parallel algorithms\n                      , in Proceedings of the 9th Annual ACM Symposium on Parallel Algorithms and Architectures, Newport, RI, 1997, pp. 106\u2013115.","DOI":"10.1145\/258492.258503"},{"key":"R11","doi-asserted-by":"crossref","unstructured":"F. Dehne, W. Dittrich, D. Hutchinson, and A. Maheshwari,\n                      Reducing I\/O complexity by simulating coarse grained parallel algorithms\n                      , in proceedings of the 13th Annual International Parallel Processing Symposium, IEEE, San Juan, Puerto Rico, 1999, pp. 14\u201320.","DOI":"10.1109\/IPPS.1999.760428"},{"key":"R12","doi-asserted-by":"crossref","unstructured":"R. Dementiev and P. Sanders,\n                      Asynchronous parallel disk sorting\n                      , in Proceedings of the 15th Annual ACM Symposium on Parallelism in Algorithms and Architectures, San Diego, 2003, pp. 138\u2013148.","DOI":"10.1145\/777412.777435"},{"key":"R13","doi-asserted-by":"crossref","unstructured":"David Hutchinson, Peter Sanders, Jeffrey Vitter, Duality between prefetching and queued writing with parallel disks, Lecture Notes in Comput. Sci., Vol. 2161, Springer, Berlin, 2001, 62\u201373MR1913542","DOI":"10.1007\/3-540-44676-1_5"},{"key":"R14","doi-asserted-by":"crossref","unstructured":"D. A. Hutchinson, P. Sanders, and J. S. Vitter,\n                      The power of duality for prefetching and sorting with parallel disks\n                      , in Proceedings of the 12th Annual ACM Symposium on Parallel Algorithms and Architectures (SPAA Revue), Crete Island, Greece, 2001, pp. 334\u2013335.","DOI":"10.1145\/378580.378760"},{"key":"R15","doi-asserted-by":"crossref","unstructured":"M. Kallahalla and P. J. Varman,\n                      Optimal read\u2010once parallel disk scheduling\n                      , in Proceedings of the 6th Annual Workshop on Input\/Output in Parallel and Distributed Systems, Atlanta, GA, 1999, pp. 68\u201377.","DOI":"10.1145\/301816.301835"},{"key":"R16","doi-asserted-by":"crossref","unstructured":"M. Kallahalla and P. J. Varman,\n                      Optimal prefetching and caching for parallel I\/O systems\n                      , in Proceedings of the 13th Annual Symposium on Parallel Algorithms and Architectures, Crete Island, Greece, 2001, pp. 219\u2013228.","DOI":"10.1145\/378580.378648"},{"key":"R17","doi-asserted-by":"publisher","DOI":"10.1109\/TC.2002.1047757"},{"key":"R18","doi-asserted-by":"publisher","DOI":"10.1137\/S0097539797326976"},{"key":"R19","volume-title":"The art of computer programming","author":"Knuth Donald","year":"1975"},{"key":"R20","doi-asserted-by":"crossref","unstructured":"M. H. Nodine and J. S. Vitter,\n                      Deterministic distribution sort in shared and distributed memory multiprocessors\n                      , in Proceedings of the 5th Annual ACM Symposium on Parallel Algorithms and Architectures, Velen, Germany, 1993, pp. 120\u2013129.","DOI":"10.1145\/165231.165247"},{"key":"R21","doi-asserted-by":"publisher","DOI":"10.1145\/210332.210343"},{"key":"R22","unstructured":"P. Sanders, S. Egner, and J. Korst,\n                      Fast concurrent access to parallel disks\n                      , in Proceedings of the 11th Annual ACM\u2010SIAM Symposium on Discrete Algorithms, San Francisco, 2000, pp. 849\u2013858."},{"key":"R23","doi-asserted-by":"crossref","unstructured":"Jeffrey Vitter, External memory algorithms, Massive Comput., Vol. 4, Kluwer Acad. Publ., Dordrecht, 2002, 359\u2013416MR1965532","DOI":"10.1007\/978-1-4615-0005-6_10"},{"key":"R24","unstructured":"Jeffrey Vitter, David Hutchinson, Distribution sort with randomized cycling, SIAM, Philadelphia, PA, 2001, 77\u201386MR1958394"},{"key":"R25","doi-asserted-by":"publisher","DOI":"10.1007\/BF01185207"}],"container-title":["SIAM Journal on Computing"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/epubs.siam.org\/doi\/pdf\/10.1137\/S0097539703431573","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2026,8,21]],"date-time":"2026-08-21T18:15:06Z","timestamp":1787336106000},"score":1,"resource":{"primary":{"URL":"https:\/\/epubs.siam.org\/doi\/10.1137\/S0097539703431573"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2005,1]]},"references-count":25,"journal-issue":{"issue":"6","published-print":{"date-parts":[[2005,1]]}},"alternative-id":["10.1137\/S0097539703431573"],"URL":"https:\/\/doi.org\/10.1137\/s0097539703431573","relation":{},"ISSN":["0097-5397","1095-7111"],"issn-type":[{"value":"0097-5397","type":"print"},{"value":"1095-7111","type":"electronic"}],"subject":[],"published":{"date-parts":[[2005,1]]}}}