Similarity Search with Tensor Core Units

被引：5

作者：

Ahle, Thomas D. ^{[1
,2
]}

Silvestri, Francesco ^{[3
]}

机构：

[1] IT Univ, Copenhagen, Denmark

[2] BARC, Copenhagen, Denmark

[3] Univ Padua, Padua, Italy

来源：

SIMILARITY SEARCH AND APPLICATIONS, SISAP 2020 | 2020年 / 12440卷

关键词：

Similarity search; Tensor core units; Dimensionality reduction; Similarity join; Locality sensitive hashing;

D O I：

10.1007/978-3-030-60936-8_6

中图分类号：

TP18 [人工智能理论];

学科分类号：

081104 ; 0812 ; 0835 ; 1405 ;

摘要：

Tensor Core Units (TCUs) are hardware accelerators developed for deep neural networks, which efficiently support the multiplication of two dense root m x root m matrices, where m is a given hardware parameter. In this paper, we show that TCUs can speed up similarity search problems as well. We propose algorithms for the Johnson-Lindenstrauss dimensionality reduction and for similarity join that, by leveraging TCUs, achieve a Omega(root m) speedup up with respect to traditional approaches.

引用

页码：76 / 84

页数：9

共 16 条

[1]

Ahle T.D., 2019, ARXIV190901821

[2]

Ahle T.D., 2020, ARXIV200612608

[3]

Ahle T.D., 2020, P 1 13 INT C SIM SEA

[4]

Ahle TD, 2020, PROCEEDINGS OF THE THIRTY-FIRST ANNUAL ACM-SIAM SYMPOSIUM ON DISCRETE ALGORITHMS (SODA'20), P141

[5] On the Complexity of Inner Product Similarity Join [J].

Ahle, Thomas D. ;

Pagh, Rasmus ;

Razenshteyn, Ilya ;

Silvestri, Francesco .

PODS'16: PROCEEDINGS OF THE 35TH ACM SIGMOD-SIGACT-SIGAI SYMPOSIUM ON PRINCIPLES OF DATABASE SYSTEMS, 2016, :151-164

[6]

Ailon N., 2006, STOC'06. Proceedings of the 38th Annual ACM Symposium on Theory of Computing, P557, DOI 10.1145/1132516.1132597

[7] Fast Dimension Reduction Using Rademacher Series on Dual BCH Codes [J].

Ailon, Nir ;

Liberty, Edo .

DISCRETE & COMPUTATIONAL GEOMETRY, 2009, 42 (04) :615-630

[8] Limits on the Universal Method for Matrix Multiplication [J].

Alman, Josh .

34TH COMPUTATIONAL COMPLEXITY CONFERENCE (CCC 2019), 2019, 137

[9] Brief Announcement: A Computational Model for Tensor Core Units [J].

Chowdhury, Rezaul ;

Silvestri, Francesco ;

Vella, Flavio .

PROCEEDINGS OF THE 32ND ACM SYMPOSIUM ON PARALLELISM IN ALGORITHMS AND ARCHITECTURES (SPAA '20), 2020, :519-521

[10]

Dakkak A., 2019, P INT C SUP ICS

← 1 2 →