Search

Sparse deep neural networks (DNNs) emerged as the result of search for networks with less storage and lower computational complexity. The sparse DNN inference is the task of using such trained DNN networks to classify a batch of input data. We propose an efficient, hybrid model- and data-parallel DNN inference using hypergraph models and partitioners. We exploit tiling and weak synchronization to increase cache reuse, hide load imbalance, and hide synchronization costs. Finally, a blocking approach allows application of this new hybrid inference procedure for deep neural networks. We initially experiment using the hybrid tiled inference approach only, using the first five layers of networks from the IEEE HPEC 2019 Graph Challenge, and attain up to 2 x speedup versus a data-parallel baseline.

This HDR investigates three classes of problems at the interplay of discrete algorithms, combinatorial optimization, and numerical methods. The three problem classes are that of partitioning, matching, and ordering.Partitioning problems arise in task decomposition for parallel computing, where load balance and low communication cost are two objectives. We discuss acyclic partitioning of directed acyclic graphs and hypergraphs. While our contributions for the former problem concern combinatorial tools for the desired partitioning objectives and constraints, those for the second problem concern the use of hypergraph partitioning tools for efficient tensor decomposition in distributed memory systems.Matching problems arise in settings where agents compete for exclusive access to resources. We present approximation algorithms for matchings in graphs and effective heuristics for finding matchings in hypergraphs. We also investigate the problem of finding Birkhoff--von Neumann decompositions with a small number of permutation matrices and present complexity results and theoretical insights into this problem. Ordering problems arise when one wants to permute sparse matrices and tensors into desirable forms. We propose heuristics to permute sparse matrices into special forms to reduce the height of the resulting elimination tree. We also propose heuristics to cluster nonzeros of a given sparse tensor around the diagonal in order to improve the performance of certain tensor operations.The general research area is called combinatorial scientific computing (CSC). In CSC, the contributions have practical and theoretical flavor. For all problems discussed in this document, we have the design, analysis, and implementation of algorithms along with many experiments. The theoretical results are included in this document, some with proofs; the reader is invited to the original papers for the omitted proofs. A similar approach is taken for presenting the experiments. While most results for observing theoretical findings in practice are included, the reader is referred to the original papers for some other results (e.g., run time analysis).

We discuss the use of hypergraph partitioning based methods in fill-reducing orderings of sparse matrices for Cholesky, LU and QR factorizations. For the Cholesky factorization, we investigate a recent result on pattern-wise decomposition of sparse matrices, generalize the result, and develop algorithmic tools to obtain more effective ordering methods. The generalized results help us formulate the fill-reducing ordering problem for LU factorization as we do for the Cholesky case, without ever symmetrizing the given matrix $A$ as $|A| + |A^T|$ or $|^AT ||A|$. For the QR factorization, we adopt a recently proposed technique to use hypergraph models in a fairly standard manner. The method again does not form the possibly much denser matrix $|A^T ||A|$. We also discuss alternatives for LU and QR factorization cases where the symmetrized matrix can be used. We provide comparisons with the most common alternatives in all three cases.

42 pages, available as LIP research report RR-2009-15; Numerical linear algebra and combinatorial optimization are vast subjects; as is their interaction. In virtually all cases there should be a notion of sparsity for a combinatorial problem to arise. Sparse matrices therefore form the basis of the interaction of these two seemingly disparate subjects. As the core of many of today's numerical linear algebra computations consists of the solution of sparse linear system by direct or iterative methods, we survey some combinatorial problems, ideas, and algorithms relating to these computations. On the direct methods side, we discuss issues such as matrix ordering; bipartite matching and matrix scaling for better pivoting; task assignment and scheduling for parallel multifrontal solvers. On the iterative method side, we discuss preconditioning techniques including incomplete factorization preconditioners, support graph preconditioners, and algebraic multigrid. In a separate part, we discuss the block triangular form of sparse matrices.

üOZETË üşPARALEL SEYREK MATRIS-VEKTOR CARPIMI VEüDOLAYLI YONTEMLERBora UşarcBilgisayar Mü hendisliği, Doktorau gTez Yüneticisi: Prof. Dr. Cevdet AykanatoAğustos, 2005gSeyrek matris-vektür carpımı (MxV) bir cok bilimsel hesaplama uygula-oş şmasının cekirdeğini oluşturmaktadır. Dolayısıyla, MxV carpımlarının par-ş g s şalelleştirilmesi, bilimsel hesaplama cevrelerinin ünem verdiği bir konudur. Bus ş o gkonuda yapılmış calışmalar yü k dengelemeye ve toplam haberleşme hacminisş s u sazaltmaya odaklanmıştır. Bu tezde, toplam haberleşme sayısının da ünemlis s oolabileceği güsterilmiştir.go s Ayrıca, işlemcilere düşen en bü yü k haberleşmes us uu shacminin ve sayısının niceliğinin de ünemli olabileceği güsterilmiştir. Bu dürtg o go s ohaberleşme ülşutü nü n azaltılmasını sağlayacak hiperşizge modelleri ve bu mod-s o cü u u g cellerin bülü mlenmesini sağlayacak yüntemler ünerilmiştir. Bu ünerilen model-ou g o o s olerin ve yüntemlerin, tek boyutlu ve iki boyutlu matris bülü mlendirilmesindeo ounasıl kullanılacağı güsterilmiştir. MxV işleminin en cok kullanıldıgı yer lineergo s s şsistem cüzü mlemelerinde kullanılan dolaylı yüntemlerdir. Bu dolaylı yüntemlerşo u o ocoğu zaman matris iyileştirme teknikleri kullanırlar. Matrislerin yaklaşık ters-şg s sleriyle iyileştirme tekniği, bir cok simetrik ve simetrik olmayan matris ceşitlerines g ş şsuygulanabilen ve cokşa kullanılan bir tekniktir. Bu teknik, temel olarak, MxVşcişleminin yerine ardışık MxV işlemlerini koyar. Yani, bir MxV işlemi, matrislerins s s syaklaşık tersleriyle iyileştirme tekniğini kullanan dolaylı yüntemlerde daha bü yü ks s g o uubir hesaplama işleminin sadece kü cuk bir parşasıdır. Ardışık MxV carpımlarınıns uşü c s şarasında etkileşim vardır. Bu etkileşimler, verimli paralelleştirme işin matris-s s s clerin bir arada bülü mlendirilmesini zorunlu kılmaktadır. Bu tezde, bir aradaoubülü mlendirmenin, değişik dolaylı yüntemler işin değişik matris bülü mlendirmeou gs o c gs oumodellerine yol aştıgı güsterilmiştir. Sıkşa kullanılan bir cok dolaylı yünteminc o s c ş ohangi matris bülü mlendirme modelleriyle paralelleştirilebileceği güsterilmiştir.ou s go sBu matris bülü mlendirme modellerinin elde edilmesini sağlamak işin, üncedenou g c oünerilmiş hiperşizge modellerini birleştirerek bileşik hiperşizge modelleri geliştireno s c s s c sviviiişlemler tanımlanmıştır. Bileşik hiperşizge modellerinin bülü mlenmesi ile ma-s s s c outrislerin bir arada bülü mlendirilebileceği güsterilmiştir. Yukarıda bahsedilenou go scalışmaların pratikte işe yarayıp yaramadıklarını gürmek işin, paralel MxVşs s o cişlemini yapan bir program yazdık. Bu programla yaptığımız deneyler sırasında,s gdaha genel bir paralel program sınıfının calışma sü resinin günder işlemlerininşs u o ssırasına bağlı olduğunu gürdü k. En iyi günder işlemi sırasının bazı varsayımlarg g ou o saltında nasıl bulunabileceğini güsterdik.g oAnahtar süzcükler : Seyrek matrisler, paralel matris-vektür carpımı, dolaylıou oşyüntemler, matris iyileştirme, matrislerin yaklaşık tersleriyle iyileştirme,o s s shiperşizge bülü mleme.c ou ABSTRACTPARALLEL SPARSE MATRIX-VECTOR MULTIPLIESAND ITERATIVE SOLVERSBora UşarcPh.D. in Computer EngineeringSupervisor: Prof. Dr. Cevdet AykanatAugust, 2005Sparse matrix-vector multiply (SpMxV) operations are in the kernel of manyscientiï¬c computing applications. Therefore, eï¬cient parallelization of SpMxVoperations is of prime importance to scientiï¬c computing community. Previousworks on parallelizing SpMxV operations consider maintaining the load balanceamong processors and minimizing the total message volume. We show that the to-tal message latency (start-up time) may be more important than the total messagevolume. We also stress that the maximum message volume and latency handledby a single processor are important communication cost metrics that should beminimized. We propose hypergraph models and hypergraph partitioning methodsto minimize these four communication cost metrics in one dimensional and twodimensional partitioning of sparse matrices. Iterative methods used for solvinglinear systems appear to be the most common context in which SpMxV operationsarise. Usually, these iterative methods apply a technique called preconditioning.Approximate inverse preconditioningâwhich can be applied to a large class ofunsymmetric and symmetric matricesâreplaces an SpMxV operation by a se-ries of SpMxV operations. That is, a single SpMxV operation is only a piece of alarger computation in the iterative methods that use approximate inverse precon-ditioning. In these methods, there are interactions in the form of dependenciesbetween the successive SpMxV operations. These interactions necessitate parti-tioning the matrices simultaneously in order to parallelize a full step of the subjectclass of iterative methods eï¬ciently. We show that the simultaneous partitioningrequirement gives rise to various matrix partitioning models depending on theiterative method used. We list the partitioning models for a number of widelyused iterative methods. We propose operations to build a composite hypergraphby combining the previously proposed hypergraph models and show that par-titioning the composite hypergraph models addresses the simultaneous matrixpartitioning problem. We strove to demonstrate how the proposed partitioningivvmethodsâboth the one that addresses multiple communication cost metrics andthe other that addresses the simultaneous partitioning problemâhelp in practice.We implemented a library and investigated the performances of the partitioningmethods. These practical investigations revealed a problem that we call messageordering problem. The problem asks how to organize the send operations to min-imize the completion time of a certain class of parallel programs. We show howto solve the message ordering problem optimally under reasonable assumptions.Keywords: Sparse matrices, parallel matrix-vector multiplication, iterative meth-ods, preconditioning, approximate inverse preconditioner, hypergraph partition-ing. 156