Constructing and analyzing algorithms of tensor operation paralleling

Abstract

The algorithms of tensors' summing, multiplying and collapsing are observed in that issue from the perspectives of those paralleling possibilities. The graphs of these algorithms are developed and analyzed from the point of the forecasted values of the acceleration and efficiency. It is assumed that the time of execution for all computing operations is same and equal to a unit of time, and data transfer between computer devices is performed instantaneously without any time consuming (it is acceptable, for example, a parallel computing systems with shared memory). In particular, it is shown that for the tensors' addition the time of the fastest execution of algorithm for an unlimited number of processors is equal to the length of the maximum path in the graph. In other words, the minimum time of the algorithm will be achieved when the number of processors is equal to the number of components of the tensor. A similar analysis was performed for the algorithms of multiplication and convolution of tensors.