Skip to Main content Skip to Navigation
Conference papers

Large scale kronecker product on supercomputers

Abstract : The Kronecker product, also called tensor product, is a fundamental matrix algebra operation, which is widely used as a natural formalism to express a convolution of many interactions or representations. Given a set of ma- trices, we need to multiply their Kronecker product by a vector. This operation is a critical kernel for iterative algo- rithms, thus needs to be computed efficiently. In a previous work, we have proposed a cost optimal parallel algorithm for the problem, both in terms of floating point computation time and interprocessor communication steps. However, the lower bound of data transfers can only be achieved if we really consider (local) logarithmic broadcasts. In practice, we consider a communication loop instead. Thus, it be- comes important to care about the real cost of each broad- cast. As this local broadcast is performed simultaneously by each processor, the situation is getting worse on a large number of processors (supercomputers). We address the problem in this paper in two points. In one hand, we pro- pose a way to build a virtual topology which has the lowest gap to the theoretical lower bound. In the other hand, we consider a hybrid implementation, which has the advantage of reducing the number of communicating nodes. We il- lustrate our work with some benchmarks on a large SMP 8-Core supercomputer.
Document type :
Conference papers
Complete list of metadata

Cited literature [8 references]  Display  Hide  Download
Contributor : Sabine Starita <>
Submitted on : Wednesday, May 30, 2012 - 5:01:16 PM
Last modification on : Wednesday, October 14, 2020 - 3:52:20 AM
Long-term archiving on: : Friday, August 31, 2012 - 2:28:43 AM


Files produced by the author(s)



Claude Tadonki. Large scale kronecker product on supercomputers. 23rd International Symposium on Computer Architecture and High Performance Computing - SBAC-PAD 2011 - WAMCA 2011, Oct 2011, Victoria, Brazil. pp.1-4, ⟨10.1109/WAMCA.2011.10⟩. ⟨in2p3-00702588⟩



Record views


Files downloads