Tuğba Torun

Research Areas:

Scientific computing

Parallel programming

Graph and hypergraph partitioning models

Selected work

S. Acer, T. Torun and C. Aykanat, "Improving Medium-Grain Partitioning for Scalable Sparse Tensor Decomposition," in IEEE Transactions on Parallel and Distributed Systems, vol. 29, no. 12, pp. 2814-2825, 1 Dec. 2018, doi: 10.1109/TPDS.2018.2841843.

Abstract: Tensor decomposition is widely used in the analysis of multi-dimensional data. The canonical polyadic decomposition (CPD) is one of the most popular decomposition methods and commonly found by the CPD-ALS algorithm. High computational and memory costs of CPD-ALS necessitate the use of a distributed-memory-parallel algorithm for efficiency. The medium-grain CPD-ALS algorithm, which adopts multi-dimensional cartesian tensor partitioning, is one of the most successful distributed CPD-ALS algorithms for sparse tensors. This is because cartesian partitioning imposes nice upper bounds on communication overheads. However, this model does not utilize the sparsity pattern of the tensor to reduce the total communication volume. The objective of this work is to fill this literature gap. We propose a novel hypergraph-partitioning model, CartHP, whose partitioning objective correctly encapsulates the minimization of total communication volume of multi-dimensional cartesian tensor partitioning. Experiments on twelve real-world tensors using up to 1024 processors validate the effectiveness of the proposed CartHP model. Compared to the baseline medium-grain model, CartHP achieves average reductions of 52, 43 and 24 percent in total communication volume, communication time and overall runtime of CPD-ALS, respectively.

keywords: {data analysis;distributed memory systems;graph theory;matrix decomposition;minimisation;parallel algorithms;sparse matrices;tensors;total communication volume;multidimensional cartesian tensor partitioning;scalable sparse tensor decomposition;multidimensional data;canonical polyadic decomposition;memory costs;distributed-memory-parallel algorithm;medium-grain CPD-ALS algorithm;sparse tensors;medium-grain partitioning;distributed CPD-ALS algorithms;hypergraph-partitioning model;CartHP model;sparsity pattern;literature gap;Tensile stress;Program processors;Partitioning algorithms;Solid modeling;Mathematical model;Runtime;Matrix decomposition;Sparse tensor;canonical polyadic decomposition;cartesian partitioning;load balancing;communication volume;hypergraph partitioning},

URL: https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=8368258&isnumber=8531999

Get in touch at tugba.uzluer@bilkent.edu.tr