{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2026,1,8]],"date-time":"2026-01-08T22:30:26Z","timestamp":1767911426020,"version":"3.49.0"},"reference-count":29,"publisher":"Association for Computing Machinery (ACM)","issue":"4","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2015,12]]},"abstract":"<jats:p>In-memory databases rely on pointer-intensive data structures to quickly locate data in memory. A single lookup operation in such data structures often exhibits long-latency memory stalls due to dependent pointer dereferences. Hiding the memory latency by launching additional memory accesses for other lookups is an effective way of improving performance of pointer-chasing codes (e.g., hash table probes, tree traversals). The ability to exploit such inter-lookup parallelism is beyond the reach of modern out-of-order cores due to the limited size of their instruction window. Instead, recent work has proposed software prefetching techniques that exploit inter-lookup parallelism by arranging a set of independent lookups into a group or a pipeline, and navigate their respective pointer chains in a synchronized fashion. While these techniques work well for highly regular access patterns, they break down in the face of irregularity across lookups. Such irregularity includes variable-length pointer chains, early exit, and read\/write dependencies.<\/jats:p>\n          <jats:p>This work introduces Asynchronous Memory Access Chaining (AMAC), a new approach for exploiting inter-lookup parallelism to hide the memory access latency. AMAC achieves high dynamism in dealing with irregularity across lookups by maintaining the state of each lookup separately from that of other lookups. This feature enables AMAC to initiate a new lookup as soon as any of the in-flight lookups complete. In contrast, the static arrangement of lookups into a group or pipeline in existing techniques precludes such adaptivity. Our results show that AMAC matches or outperforms state-of-the-art prefetching techniques on regular access patterns, while delivering up to 2.3x higher performance under irregular data structure lookups. AMAC fully utilizes the available microarchitectural resources, generating the maximum number of memory accesses allowed by hardware in both single- and multi-threaded execution modes.<\/jats:p>","DOI":"10.14778\/2856318.2856321","type":"journal-article","created":{"date-parts":[[2016,2,1]],"date-time":"2016-02-01T14:10:31Z","timestamp":1454335831000},"page":"252-263","source":"Crossref","is-referenced-by-count":44,"title":["Asynchronous memory access chaining"],"prefix":"10.14778","volume":"9","author":[{"given":"Onur","family":"Kocberber","sequence":"first","affiliation":[{"name":"EcoCloud, EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Babak","family":"Falsafi","sequence":"additional","affiliation":[{"name":"EcoCloud, EPFL"}],"role":[{"role":"author","vocabulary":"crossref"}]},{"given":"Boris","family":"Grot","sequence":"additional","affiliation":[{"name":"University of Edinburgh"}],"role":[{"role":"author","vocabulary":"crossref"}]}],"member":"320","published-online":{"date-parts":[[2015,12]]},"reference":[{"key":"e_1_2_1_1_1","doi-asserted-by":"publisher","DOI":"10.1145\/339647.339691"},{"key":"e_1_2_1_2_1","volume-title":"Proceedings of the 25th International Conference on Very Large Data Bases","author":"Ailamaki A.","year":"1999","unstructured":"A. Ailamaki , D. J. DeWitt , M. D. Hill , and D. A. Wood . DBMSs on a modern processor: Where does time go ? In Proceedings of the 25th International Conference on Very Large Data Bases , 1999 . A. Ailamaki, D. J. DeWitt, M. D. Hill, and D. A. Wood. DBMSs on a modern processor: Where does time go? In Proceedings of the 25th International Conference on Very Large Data Bases, 1999."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.14778\/2336664.2336678"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544839"},{"key":"e_1_2_1_5_1","volume":"2014","author":"Balkesen C.","unstructured":"C. Balkesen , J. Teubner , G. Alonso , and M. Ozsu . Main-memory hash joins on modern processor architectures. In IEEE Transactions on Knowledge and Data Engineering , volume PP, 2014 . C. Balkesen, J. Teubner, G. Alonso, and M. Ozsu. Main-memory hash joins on modern processor architectures. In IEEE Transactions on Knowledge and Data Engineering, volume PP, 2014.","journal-title":"Main-memory hash joins on modern processor architectures. In IEEE Transactions on Knowledge and Data Engineering"},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735496.2735499"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/1989323.1989328"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272747"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1145\/375663.375688"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564710"},{"key":"e_1_2_1_11_1","doi-asserted-by":"publisher","DOI":"10.1145\/2694344.2694359"},{"key":"e_1_2_1_12_1","doi-asserted-by":"publisher","DOI":"10.1145\/1114252.1114260"},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2011.5767961"},{"key":"e_1_2_1_14_1","unstructured":"Intel Xeon Processor 5600 Series Datasheet Vol 2. http:\/\/intel.ly\/1Am4SVw.  Intel Xeon Processor 5600 Series Datasheet Vol 2. http:\/\/intel.ly\/1Am4SVw."},{"key":"e_1_2_1_15_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735703.2735704"},{"key":"e_1_2_1_16_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_17_1","doi-asserted-by":"publisher","DOI":"10.14778\/1687553.1687564"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/2540708.2540748"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/237090.237190"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.1109\/TKDE.2002.1019210"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780000031"},{"key":"e_1_2_1_22_1","unstructured":"Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors. http:\/\/intel.ly\/1QFmyky.  Performance Analysis Guide for Intel Core i7 Processor and Intel Xeon 5500 Processors. http:\/\/intel.ly\/1QFmyky."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1145\/342009.335449"},{"key":"e_1_2_1_24_1","unstructured":"SPARC Strong Prefetch. http:\/\/bit.ly\/1OceJlN.  SPARC Strong Prefetch. http:\/\/bit.ly\/1OceJlN."},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2007.66"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.5555\/509058.509096"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.1145\/1995441.1995442"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.5555\/1083592.1083602"},{"key":"e_1_2_1_29_1","doi-asserted-by":"publisher","DOI":"10.5555\/1315451.1315487"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/2856318.2856321","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T10:23:41Z","timestamp":1672223021000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/2856318.2856321"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2015,12]]},"references-count":29,"journal-issue":{"issue":"4","published-print":{"date-parts":[[2015,12]]}},"alternative-id":["10.14778\/2856318.2856321"],"URL":"https:\/\/doi.org\/10.14778\/2856318.2856321","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2015,12]]}}}