{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,3,9]],"date-time":"2026-03-09T18:29:18Z","timestamp":1773080958501,"version":"3.50.1"},"reference-count":30,"publisher":"Association for Computing Machinery (ACM)","issue":"1","license":[{"start":{"date-parts":[[2010,1,1]],"date-time":"2010-01-01T00:00:00Z","timestamp":1262304000000},"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. Math. Softw."],"published-print":{"date-parts":[[2010,1]]},"abstract":"<jats:p>Today computers have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I\/O traffic to slower memories in the hierarchy. In this article, we study the computation of option pricing using the binomial and trinomial models on processors with a multilevel memory hierarchy. We derive lower bounds on memory traffic between different levels of the hierarchy for these two models. We also develop algorithms for the binomial and trinomial models that have near-optimal memory traffic between levels. We have implemented these algorithms on an UltraSparc IIIi processor with a 4-level of memory hierarchy and demonstrated that our algorithms outperform algorithms without cache blocking by a factor of up to 5 and operate at 70% of peak performance.<\/jats:p>","DOI":"10.1145\/1644001.1644008","type":"journal-article","created":{"date-parts":[[2010,1,19]],"date-time":"2010-01-19T20:14:58Z","timestamp":1263932098000},"page":"1-30","update-policy":"https:\/\/doi.org\/10.1145\/crossmark-policy","source":"Crossref","is-referenced-by-count":10,"title":["Cache-optimal algorithms for option pricing"],"prefix":"10.1145","volume":"37","author":[{"given":"John E.","family":"Savage","sequence":"first","affiliation":[{"name":"Brown University, Providence, RI"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Mohammad","family":"Zubair","sequence":"additional","affiliation":[{"name":"Old Dominion University, Norfolk, VA"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2010,1,22]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.385.0563"},{"key":"e_1_2_1_2_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.383.0265"},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1145\/28395.28428"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/SFCS.1987.31"},{"key":"e_1_2_1_5_1","doi-asserted-by":"crossref","unstructured":"Anderson E. Bai Z. Bischof C. H. Blackford S. Demmel J. Dongarra J. J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. C. 1999. LAPACK Users' Guide 3rd ed. SIAM Philadelphia PA. http:\/\/www.netlib.org\/lapack\/lug\/. Anderson E. Bai Z. Bischof C. H. Blackford S. Demmel J. Dongarra J. J. Du Croz J. Greenbaum A. Hammarling S. McKenney A. and Sorensen D. C. 1999. LAPACK Users' Guide 3rd ed. SIAM Philadelphia PA. http:\/\/www.netlib.org\/lapack\/lug\/.","DOI":"10.1137\/1.9780898719604"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1016\/S0022-0000(74)80046-2"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1016\/0304-405X(79)90015-1"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/77626.79170"},{"key":"e_1_2_1_9_1","volume-title":"FOCS '99: Proceedings of the 40th Annual Symposium on the Foundations of Computer Science. IEEE Computer Society Press","author":"Frigo M."},{"key":"e_1_2_1_10_1","unstructured":"Garg R. P. and Sharapov I. 2001. Techniques for Optimizing Applications: High Performance Computing. Prentice Hall PTR Englewood Cliffs NJ. Garg R. P. and Sharapov I. 2001. Techniques for Optimizing Applications: High Performance Computing. Prentice Hall PTR Englewood Cliffs NJ."},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1016\/j.parco.2003.09.003"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1356052.1356053"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1145\/285861.285865"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.1147\/rd.471.0031"},{"key":"e_1_2_1_15_1","volume-title":"Computer Architecture: A Quantitative Approach. Morgan Kaufmann","author":"Hennessy J. L.","year":"2007"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1137\/S0036144501393266"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.1145\/800076.802486"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/292395.292412"},{"key":"e_1_2_1_19_1","volume-title":"FRONTIERS '96: Proceedings of the 6th Symposium on the Frontiers of Massively Parallel Computation. IEEE Computer Society Press","author":"Kumar V."},{"key":"e_1_2_1_20_1","unstructured":"Kwok Y. 1998. Mathematical Models of Financial Derivatives. Springer-Verlag Singapore. Kwok Y. 1998. Mathematical Models of Financial Derivatives. Springer-Verlag Singapore."},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/TPDS.2004.44"},{"key":"e_1_2_1_22_1","volume-title":"Computing and Combinatorics, D.-Z. Du and M. Li, Eds","author":"Savage J. E."},{"key":"e_1_2_1_23_1","unstructured":"Savage J. E. 1998. Models of Computation: Exploring the Power of Computing. Addison Wesley Reading MA. Savage J. E. 1998. Models of Computation: Exploring the Power of Computing. Addison Wesley Reading MA."},{"key":"e_1_2_1_24_1","unstructured":"Savage J. E. and Vitter J. S. 1987. Parallelism in space-time trade-offs. In Advances in Computing Research F. Preparata Ed. Number 4. JAI Press Inc. Greenwich CT 117--146. Savage J. E. and Vitter J. S. 1987. Parallelism in space-time trade-offs. In Advances in Computing Research F. Preparata Ed. Number 4. JAI Press Inc. Greenwich CT 117--146."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1145\/1463768.1463780"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.1155\/2009\/681708"},{"key":"e_1_2_1_27_1","doi-asserted-by":"crossref","unstructured":"Thulasiram R. K. and Bondarenko D. A. 2002. Performance evaluation of parallel algorithms for pricing multidimensional financial derivatives. icppw 00 306--313. Thulasiram R. K. and Bondarenko D. A. 2002. Performance evaluation of parallel algorithms for pricing multidimensional financial derivatives. icppw 00 306--313.","DOI":"10.1109\/ICPPW.2002.1039745"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1561\/0400000014"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.1145\/1248377.1248394"},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-540-69839-5_64"}],"container-title":["ACM Transactions on Mathematical Software"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644001.1644008","content-type":"unspecified","content-version":"vor","intended-application":"text-mining"},{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.1145\/1644001.1644008","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2025,6,18]],"date-time":"2025-06-18T20:26:43Z","timestamp":1750278403000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.1145\/1644001.1644008"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2010,1]]},"references-count":30,"journal-issue":{"issue":"1","published-print":{"date-parts":[[2010,1]]}},"alternative-id":["10.1145\/1644001.1644008"],"URL":"https:\/\/doi.org\/10.1145\/1644001.1644008","relation":{},"ISSN":["0098-3500","1557-7295"],"issn-type":[{"value":"0098-3500","type":"print"},{"value":"1557-7295","type":"electronic"}],"subject":[],"published":{"date-parts":[[2010,1]]},"assertion":[{"value":"2008-06-01","order":0,"name":"received","label":"Received","group":{"name":"publication_history","label":"Publication History"}},{"value":"2009-06-01","order":1,"name":"accepted","label":"Accepted","group":{"name":"publication_history","label":"Publication History"}},{"value":"2010-01-22","order":2,"name":"published","label":"Published","group":{"name":"publication_history","label":"Publication History"}}]}}