Make the most out of your SIMD investments: counter control flow divergence in compiled query pipelines

Abstract

Increasing single instruction multiple data (SIMD) capabilities in modern hardware allows for the compilation of data-parallel query pipelines. This means GPU-alike challenges arise: control flow divergence causes the underutilization of vector-processing units. In this paper, we present efficient algorithms for the AVX-512 architecture to address this issue. These algorithms allow for the fine-grained assignment of new tuples to idle SIMD lanes. Furthermore, we present strategies for their integration with compiled query pipelines so that tuples are never evicted from registers. We evaluate our approach with three query types: (i) a table scan query based on TPC-H Query 1, that performs up to 34% faster when addressing underutilization, (ii) a hashjoin query, where we observe up to 25% higher performance, and (iii) an approximate geospatial join query, which shows performance improvements of up to 30%.

Document type: Conference object

Full document

Original document

The different versions of the original document can be found in:

• https://ir.cwi.nl/pub/27874

• https://ir.cwi.nl/pub/27874/27874.pdf

• https://ir.cwi.nl/pub/28788

• https://link.springer.com/content/pdf/10.1007/s00778-019-00547-y.pdf under the license cc-by

• http://dl.acm.org/ft_gateway.cfm?id=3211928&ftid=1978228&dwn=1,

http://dx.doi.org/10.1145/3211922.3211928 under the license http://www.acm.org/publications/policies/copyright_policy#Background

• http://link.springer.com/content/pdf/10.1007/s00778-019-00547-y.pdf,

http://link.springer.com/article/10.1007/s00778-019-00547-y/fulltext.html,

http://dx.doi.org/10.1007/s00778-019-00547-y under the license https://creativecommons.org/licenses/by/4.0

• https://dblp.uni-trier.de/db/journals/vldb/vldb29.html#LangPKBNK20,

https://link.springer.com/article/10.1007/s00778-019-00547-y,

https://ir.cwi.nl/pub/28788,

https://ir.cwi.nl/pub/28788/Lang2019_Article_MakeTheMostOutOfYourSIMDInvest.pdf,

https://academic.microsoft.com/#/detail/2961966181

• https://ir.cwi.nl/pub/27874,

http://dx.doi.org/10.1145/3211922.3211928

• https://ir.cwi.nl/pub/28788,

http://dx.doi.org/10.1007/s00778-019-00547-y

• https://www.narcis.nl/publication/RecordID/oai%3Acwi.nl%3A28788,

https://dblp.uni-trier.de/db/conf/damon/damon2018.html#LangKPB0K18,

https://ir.cwi.nl/pub/27874,

https://dl.acm.org/citation.cfm?doid=3211922.3211928,

https://ir.cwi.nl/pub/27874/27874.pdf,

https://dl.acm.org/citation.cfm?id=3211928,

https://academic.microsoft.com/#/detail/2806132641

DOIS: 10.1007/s00778-019-00547-y 10.1145/3211922.3211928