Fast Search of the Optimal Contraction Sequence in Tensor Networks
Fast Search of the Optimal Contraction Sequence in Tensor Networks
复制标题
张量网络中最优收缩序列的快速搜索
DOI：
10.1109/jstsp.2021.3051231
复制
发表时间：
2021
影响因子：
7.5
通讯作者：
Xie, Yuan
中科院分区：
文献类型：
--
作者：
Liang, Ling;Xu, Jianyu;Deng, Lei;Yan, Mingyu;Hu, Xing;Zhang, Zheng;Li, Guoqi;Xie, Yuan
张量网络和张量计算广泛应用于量子物理、电子设计自动化和机器学习等科学和工程领域。作为张量网络最基本的操作之一，张量收缩消除了张量之间的共享顺序，并产生紧凑的子网络。不同的压缩序列通常会产生不同的存储和计算成本，并且搜索最优序列被称为困难问题。先前的工作已经设计了启发式和快速算法来解决这个问题，然而，一些问题仍然没有解决。例如，数据格式和数据结构效率不高，建模过程中的约束条件不切实际，搜索最优解可能失败，搜索成本非常高。在本文中，我们首先介绍了一个顺序表示，并设计了一个基于邻接矩阵的数据结构，以有效地加快搜索的最佳收缩序列。然后，我们提出了一个外积修剪方法，以减少搜索空间的开销。最后，我们使用多线程优化在我们的实现，以进一步提高执行性能。我们还对影响搜索时间的因素进行了深入的分析。该工作为最优收缩序列搜索提供了从高层数据结构和搜索算法到底层执行并行的全栈解决方案，将有利于广泛的张量相关应用。
Tensor network and tensor computation are widely applied in scientific and engineering domains like quantum physics, electronic design automation, and machine learning. As one of the most fundamental operations for tensor networks, a tensor contraction eliminates the sharing orders among tensors and produces a compact sub-network. Different contraction sequence usually yields distinct storage and compute costs, and searching the optimal sequence is known as a hard problem. Prior work have designed heuristic and fast algorithms to solve this problem, however, several issues still remain unsolved. For example, the data format and data structure are not efficient, the constraints during modeling are impractical, the search of the optimal solution might fail, and the search cost is very high. In this paper, we first introduce aorder representation and design an adjacency matrix-based data structure to efficiently accelerate the search of the optimal contraction sequence. Then, we propose an outer product pruning method with acceptable overhead to reduce the search space. Finally, we use a multithread optimization in our implementation to further improve the execution performance. We also present in-depth analysis of factors that influence the search time. This work provides a full-stack solution for optimal contraction sequence search from both high-level data structure and search algorithm to low-level execution parallelism, and it will benefit a broad range of tensor-related applications.
登录
查看更多内容
关于优化一类并行执行约简多维循环
DOI：
10.1142/s0129626497000176
发表时间：
1997
期刊：
Parallel Process. Lett.
影响因子：
--
作者：
Chi;P. Sadayappan;R. Wenger
通讯作者：
R. Wenger
DOI：
--
发表时间：
2013
期刊：
影响因子：
--
作者：
G. Evenbly;R. N. C. Pfeifer
通讯作者：
R. N. C. Pfeifer
二维空间维度的纠缠重整化。
影响因子：
8.6
作者：
G. Evenbly;G. Vidal
通讯作者：
G. Vidal
影响因子：
2.2
作者：
Szilárd Szalay;Max Pfeffer;V. Murg;Gergely Barcza;F. Verstraete;R. Schneider;O. Legeza
通讯作者：
Szilárd Szalay;Max Pfeffer;V. Murg;Gergely Barcza;F. Verstraete;R. Schneider;O. Legeza
识别具有成本效益的公共子表达式以减少张量收缩评估中的操作次数
DOI：
--
发表时间：
2006
期刊：
International Conference on Conceptual Structures
影响因子：
--
作者：
Albert Hartono;Q. Lu;X. Gao;S. Krishnamoorthy;M. Nooijen;Gerald Baumgartner;D. Bernholdt;Venkatesh Choppella;R. Pitzer;J. Ramanujam;A. Rountev;P. Sadayappan
通讯作者：
P. Sadayappan