{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,31]],"date-time":"2026-01-31T07:38:44Z","timestamp":1769845124200,"version":"3.49.0"},"reference-count":20,"publisher":"Association for Computing Machinery (ACM)","issue":"4","license":[{"start":{"date-parts":[[2016,12,16]],"date-time":"2016-12-16T00:00:00Z","timestamp":1481846400000},"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":["ACM Trans. Archit. Code Optim."],"published-print":{"date-parts":[[2016,12,28]]},"abstract":"<jats:p>\n            This article exposes and proves some mathematical facts about optimal cache replacement that were previously unknown or not proved rigorously. An explicit formula is obtained, giving OPT hits and misses as a function of past references. Several mathematical facts are derived from this formula, including a proof that OPT miss curves are always convex, and a new algorithm called\n            <jats:italic>OPT tokens<\/jats:italic>\n            , for reasoning about optimal replacement.\n          <\/jats:p>","DOI":"10.1145\/3017992","type":"journal-article","created":{"date-parts":[[2016,12,19]],"date-time":"2016-12-19T17:06:31Z","timestamp":1482167191000},"page":"1-19","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":13,"title":["Some Mathematical Facts About Optimal Cache Replacement"],"prefix":"10.1145","volume":"13","author":[{"given":"Pierre","family":"Michaud","sequence":"first","affiliation":[{"name":"Inria, RENNES Cedex"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2016,12,16]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/321623.321632"},{"key":"e_1_2_1_2_1","volume-title":"International Symposium on High Performance Computer Architecture (HPCA).","author":"Beckmann N."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.52.0078"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.181.0002"},{"key":"e_1_2_1_5_1","doi-asserted-by":"publisher","DOI":"10.1145\/2491894.2466482"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/268806.268810"},{"key":"e_1_2_1_7_1","unstructured":"E. G. Coffman and P. J. Denning. 1973. Operating Systems Theory. Prentice-Hall.   E. G. Coffman and P. J. Denning. 1973. Operating Systems Theory. Prentice-Hall."},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1016\/0167-6377(95)00021-B"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ISCA.2016.17"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1016\/0196-6774(85)90037-9"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2015.09.004"},{"key":"e_1_2_1_12_1","volume-title":"Technical Report CSE-TR-447-02. University of Michigan.","author":"Lin W.-F.","year":"2002"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1147\/sj.92.0078"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1109\/MICRO.2007.14"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1137\/0205052"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1109\/TC.1985.1676566"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/166955.166974"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/12.752656"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2006.11.009"},{"key":"e_1_2_1_22_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.ipl.2007.12.001"}],"container-title":["ACM Transactions on Architecture and Code Optimization"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3017992","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/3017992","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T04:24:17Z","timestamp":1750220657000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/3017992"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2016,12,16]]},"references-count":20,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2016,12,28]]}},"alternative-id":["10.1145\/3017992"],"URL":"https:\/\/doi.org\/10.1145\/3017992","relation":{},"ISSN":["1544-3566","1544-3973"],"issn-type":[{"value":"1544-3566","type":"print"},{"value":"1544-3973","type":"electronic"}],"subject":[],"published":{"date-parts":[[2016,12,16]]},"assertion":[{"value":"2016-08-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-11-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2016-12-16","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}