{"status":"ok","message-type":"work","message-version":"1.0.0","message":{"indexed":{"date-parts":[[2025,9,19]],"date-time":"2025-09-19T07:09:57Z","timestamp":1758265797170},"reference-count":35,"publisher":"Association for Computing Machinery (ACM)","issue":"3","content-domain":{"domain":[],"crossmark-restriction":false},"short-container-title":["Proc. VLDB Endow."],"published-print":{"date-parts":[[2019,11]]},"abstract":"<jats:p>SIMD is an instruction set in mainstream processors, which provides the data level parallelism to accelerate the performance of applications. However, its advantages diminish when applications suffer from heavy cache misses. To eliminate cache misses in SIMD vectorization, we present interleaved multi-vectorizing (IMV) in this paper. It interleaves multiple execution instances of vectorized code to hide memory access latency with more computation. We also propose residual vectorized states to solve the control flow divergence in vectorization. IMV can make full use of the data parallelism in SIMD and the memory level parallelism through prefetching. It reduces cache misses, branch misses and computation overhead to significantly speed up the performance of pointer-chasing applications, and it can be applied to executing entire query pipelines. As experimental results show, IMV achieves up to 4.23X and 3.17X better performance compared with the pure scalar implementation and the pure SIMD vectorization, respectively.<\/jats:p>","DOI":"10.14778\/3368289.3368290","type":"journal-article","created":{"date-parts":[[2020,9,11]],"date-time":"2020-09-11T03:17:35Z","timestamp":1599794255000},"page":"226-238","source":"Crossref","is-referenced-by-count":14,"title":["Interleaved multi-vectorizing"],"prefix":"10.14778","volume":"13","author":[{"given":"Zhuhe","family":"Fang","sequence":"first","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Beilei","family":"Zheng","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]},{"given":"Chuliang","family":"Weng","sequence":"additional","affiliation":[{"name":"East China Normal University, China"}]}],"member":"320","published-online":{"date-parts":[[2019,11]]},"reference":[{"key":"e_1_2_1_1_1","volume-title":"https:\/\/github.com\/fzhedu\/db-imv","author":"Source Code IMV","year":"2019","unstructured":"IMV Source Code . https:\/\/github.com\/fzhedu\/db-imv , 2019 . IMV Source Code. https:\/\/github.com\/fzhedu\/db-imv, 2019."},{"key":"e_1_2_1_2_1","volume-title":"https:\/\/software.intel.com\/en-us\/vtune-amplifier-cookbook-top-down-microarchitecture-analysis-method","author":"TMAM.","year":"2019","unstructured":"Intel Vtune TMAM. https:\/\/software.intel.com\/en-us\/vtune-amplifier-cookbook-top-down-microarchitecture-analysis-method , 2019 . Intel Vtune TMAM. https:\/\/software.intel.com\/en-us\/vtune-amplifier-cookbook-top-down-microarchitecture-analysis-method, 2019."},{"key":"e_1_2_1_3_1","doi-asserted-by":"publisher","DOI":"10.1007\/s41019-019-0088-6"},{"key":"e_1_2_1_4_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2013.6544839"},{"key":"e_1_2_1_5_1","first-page":"225","volume-title":"CIDR","author":"Boncz P. A.","year":"2005","unstructured":"P. A. Boncz , M. Zukowski , and N. Nes . MonetDB\/X100: Hyper-pipelining query execution . In CIDR , pages 225 -- 237 , 2005 . P. A. Boncz, M. Zukowski, and N. Nes. MonetDB\/X100: Hyper-pipelining query execution. In CIDR, pages 225--237, 2005."},{"key":"e_1_2_1_6_1","doi-asserted-by":"publisher","DOI":"10.1145\/1272743.1272747"},{"key":"e_1_2_1_7_1","doi-asserted-by":"publisher","DOI":"10.1145\/3132847.3132916"},{"key":"e_1_2_1_8_1","doi-asserted-by":"publisher","DOI":"10.14778\/1454159.1454171"},{"key":"e_1_2_1_9_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDEW.2018.00024"},{"key":"e_1_2_1_10_1","doi-asserted-by":"publisher","DOI":"10.1007\/978-3-030-18590-9_70"},{"key":"e_1_2_1_11_1","volume-title":"ADMS","author":"Gubner T.","year":"2017","unstructured":"T. Gubner and P. Boncz . Exploring query execution strategies for JIT, vectorization and SIMD . In ADMS , 2017 . T. Gubner and P. Boncz. Exploring query execution strategies for JIT, vectorization and SIMD. In ADMS, 2017."},{"key":"e_1_2_1_12_1","volume-title":"GPGPU, page 3","author":"Han T. D.","year":"2011","unstructured":"T. D. Han and T. S. Abdelrahman . Reducing branch divergence in GPU programs . In GPGPU, page 3 , 2011 . T. D. Han and T. S. Abdelrahman. Reducing branch divergence in GPU programs. In GPGPU, page 3, 2011."},{"key":"e_1_2_1_13_1","doi-asserted-by":"publisher","DOI":"10.14778\/2735508.2735518"},{"key":"e_1_2_1_14_1","doi-asserted-by":"publisher","DOI":"10.14778\/2809974.2809988"},{"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.14778\/3236187.3236216"},{"issue":"13","key":"e_1_2_1_17_1","first-page":"2209","article-title":"Everything you always wanted to know about compiled and vectorized queries but were afraid to ask","volume":"11","author":"Kersten T.","year":"2018","unstructured":"T. Kersten , V. Leis , A. Kemper , T. Neumann , A. Pavlo , and P. A. Boncz . Everything you always wanted to know about compiled and vectorized queries but were afraid to ask . PVLDB , 11 ( 13 ): 2209 -- 2222 , 2018 . T. Kersten, V. Leis, A. Kemper, T. Neumann, A. Pavlo, and P. A. Boncz. Everything you always wanted to know about compiled and vectorized queries but were afraid to ask. PVLDB, 11(13):2209--2222, 2018.","journal-title":"PVLDB"},{"key":"e_1_2_1_18_1","doi-asserted-by":"publisher","DOI":"10.1145\/1807167.1807206"},{"key":"e_1_2_1_19_1","doi-asserted-by":"publisher","DOI":"10.1145\/3243176.3243185"},{"key":"e_1_2_1_20_1","doi-asserted-by":"publisher","DOI":"10.14778\/2856318.2856321"},{"key":"e_1_2_1_21_1","doi-asserted-by":"publisher","DOI":"10.1109\/PACT.2001.953307"},{"key":"e_1_2_1_22_1","first-page":"1","volume-title":"DaMoN","author":"Lang H.","year":"2018","unstructured":"H. Lang , A. Kipf , L. Passing , P. A. Boncz , T. Neumann , and A. Kemper . Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines . In DaMoN , pages 1 -- 8 , 2018 . H. Lang, A. Kipf, L. Passing, P. A. Boncz, T. Neumann, and A. Kemper. Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines. In DaMoN, pages 1--8, 2018."},{"key":"e_1_2_1_23_1","doi-asserted-by":"publisher","DOI":"10.1007\/s00778-019-00547-y"},{"key":"e_1_2_1_24_1","doi-asserted-by":"publisher","DOI":"10.1145\/2588555.2610507"},{"key":"e_1_2_1_25_1","doi-asserted-by":"publisher","DOI":"10.1007\/s007780000031"},{"key":"e_1_2_1_26_1","doi-asserted-by":"publisher","DOI":"10.14778\/3151113.3151114"},{"key":"e_1_2_1_27_1","doi-asserted-by":"publisher","DOI":"10.14778\/2002938.2002940"},{"key":"e_1_2_1_28_1","doi-asserted-by":"publisher","DOI":"10.1145\/2723372.2747645"},{"key":"e_1_2_1_29_1","first-page":"1","volume-title":"DaMoN","author":"Polychroniou O.","year":"2014","unstructured":"O. Polychroniou and K. A. Ross . Vectorized bloom filters for advanced SIMD processors . In DaMoN , pages 1 -- 6 , 2014 . O. Polychroniou and K. A. Ross. Vectorized bloom filters for advanced SIMD processors. In DaMoN, pages 1--6, 2014."},{"key":"e_1_2_1_30_1","doi-asserted-by":"publisher","DOI":"10.1145\/3329785.3329928"},{"key":"e_1_2_1_31_1","doi-asserted-by":"publisher","DOI":"10.14778\/3149193.3149202"},{"key":"e_1_2_1_32_1","doi-asserted-by":"publisher","DOI":"10.1109\/CGO.2013.6494989"},{"key":"e_1_2_1_33_1","doi-asserted-by":"publisher","DOI":"10.1109\/ICDE.2007.368997"},{"key":"e_1_2_1_34_1","doi-asserted-by":"publisher","DOI":"10.1145\/216585.216588"},{"key":"e_1_2_1_35_1","doi-asserted-by":"publisher","DOI":"10.1145\/564691.564709"}],"container-title":["Proceedings of the VLDB Endowment"],"original-title":[],"language":"en","link":[{"URL":"https:\/\/dl.acm.org\/doi\/pdf\/10.14778\/3368289.3368290","content-type":"unspecified","content-version":"vor","intended-application":"similarity-checking"}],"deposited":{"date-parts":[[2022,12,28]],"date-time":"2022-12-28T09:41:33Z","timestamp":1672220493000},"score":1,"resource":{"primary":{"URL":"https:\/\/dl.acm.org\/doi\/10.14778\/3368289.3368290"}},"subtitle":[],"short-title":[],"issued":{"date-parts":[[2019,11]]},"references-count":35,"journal-issue":{"issue":"3","published-print":{"date-parts":[[2019,11]]}},"alternative-id":["10.14778\/3368289.3368290"],"URL":"https:\/\/doi.org\/10.14778\/3368289.3368290","relation":{},"ISSN":["2150-8097"],"issn-type":[{"value":"2150-8097","type":"print"}],"subject":[],"published":{"date-parts":[[2019,11]]}}}