Search

We consider a variant of the well-known, NP-complete problem of minimum cut linear arrangement for directed acyclic graphs. In this variant, we are given a directed acyclic graph and asked to find a topological ordering such that the maximum number of cut edges at any point in this ordering is minimum.In our main variant the vertices and edges have weights, and the aim is to minimize the maximum weight of cut edges in addition to the weight of the last vertex before the cut.There is a known, polynomial time algorithm [Liu, SIAM J. Algebra. Discr., 1987] for the cases where the input graph is a rooted tree. We focus on the variant where the input graph is a directed series-parallel graph, and propose a polynomial time algorithm.Directed acyclic graphs are used to model scientific applications where the vertices correspond to the tasks of a given application and the edges represent the dependencies between the tasks. In such models, the problem we address reads as minimizing the peak memory requirement in an execution of the application.Our work, combined with Liu's work on rooted trees addresses this practical problem in two important classes of applications.

Hiperçizgeler, bir kenarın herhangi bir sayıda düğümü bağlayabilme özelliği olduğu, çizgelerin genelleştirilmis bir versiyonudur. Bu genelleme ile hiperçizgeler yüksek bir modelleme gücüne sahiptir öyle ki kombinatöriyel bilimsel hesaplama alanında birçok önemli problem hiperçizgeler ile güçlü bir şekilde modellenebilmektedir. Bu tez ise hiperçizge tabanlı yöntemler kullanılarak veri bölümleme problemlerinin çözülmesini araştırmaktadır. Bu tez üç ana bölümden oluşmaktadır. Birinci bölümde, özyinelemeli çizge ikiye-bölümleme kullanarak, verimli bir hiperçizge bölümlere aracının nasıl oluşturulduğu gösterilmektedir. İkinci ve üçüncü bölümlerde, paralel hesaplamadaki iki önemli veri bölümleme probleminin hiperçizge bölümleme ile nasıl modellendiği gösterilmektedir. Birinci problem paralel sorgu hesaplama için indeksin terim-tabanlı bölümlenmesi problemidir. İkincisi ise yeni önerilen bir paralel matriks vektör çarpımında kullanılmak üzere yine yeni önerilen bir seyrek matriks bölümleme problemidir. Bu tezde, hiperçizge tabanlı modelleri ile daha kaliteli veri bölümleme elde edildiği gösterilmektedir.Anahtar sozcukler: hipercizge, veri bolumleme, kombinatoriyel algoritmalar. A hypergraph is a general version of graph where the edges may connect any number of vertices. By this flexibility, hypergraphs has a larger modeling power that may allow accurate formulaion of many problems of combinatorial scientific computing. This thesis discusses the use of hypergraph-based approaches to solve problems that require data partitioning. The thesis is composed of three parts. In the first part, we show how to implement hypergraph partitioning efficiently using recursive graph bipartitioning. The remaining two parts show how to formulate two important data partitioning problems in parallel computing as hypergraph partitioning. The first problem is global inverted index partitioning for parallel query processing and the second one is row-columnwise sparse matrix partitioning for parallel matrix vector multiplication, where both multiplication and sparse matrix partitioning schemes has novelty. In this thesis, we show that hypergraph models achieve partitions with better quality. 116

One-dimensional (1D) partitioning of sparse matrices results in lower quality partitioning than two-dimensional (2D) partitionings in the context of parallel sparse matrix vector multiply (SpMxV) operations. However, 2D partitioning schemes incur two communication phases. We propose a novel sparse matrix partitioning scheme which achieves a single communication phase as in 1D schemes and partitions the nonzeros with a flexibility close to that in 2D schemes. In the proposed partitioning scheme, a nonzero is assigned to either the receiver or the sender processor associated with the related input- or output-vector entries. We observe that a fine-grain partitioning should satisfy this constraint for most of the nonzeros. Based on this observation, we propose a simple yet effective heuristic to obtain such a partition in two steps. In the first step, we obtain partitions on the rows, columns, and nonzeros of the given matrix using some known methods. In the second step, we refine the nonzero partition such that the aforementioned constraint is met while keeping the row and column partitions obtained in the first step intact. We demonstrate that the proposed partitioning scheme improves the performance of parallel SpMxV operations both in theory and practice with respect to 1D and 2D partitionings.

Hiperçizge Bölümleme (HB) ve Düğüm Ayıracı ile Çizge Bölümleme (DACB) problemleriliteratürde gayet bilinen, koşut ve bilimsel hesaplamalarda etkin biçimde kullanılan problemlerdir. Koşut hesaplamalarda tipik bir problem, verilerin ve görevlerin değişik sayıda işlemciye öyle şekilde dağıtılmasıdır ki hesaplamanın çalışma performansı zaman ve yer gereksinimleri açısından hızlı ve verimli olsun. Bunun yanında, DACB problemi seyrek doğrusal sistemlerin verimli çözülebilmesi için doluluk azaltan sıralama yapmak için etkin biçimde kullanılmaktadır. Bu da bilimsel hesaplamanın konu sahası içine girmektedir. Bu tez çalışmasında, HB ve DACB problemleri arasındaki ilişki incelenmektedir. Bu bağlamda, iki kombinatoriyal dönüştürüm açığa çıkarılmıştır. Birinci dönüştürme, HB probleminden DACB problemine, ikincisi ise DACB probleminden HB probleminedir. HB probleminden DACB problemine dönüştürmede girdi dönüşümü kolay olmamaktadır. Girdi dönüşümünden kasıt, verilen bir çizgeyi, problem dönüştürümü uygun olacak şekilde bir hiğerçizgeye dönüştürmektir. DACB probleminden HB problemine dönüştürümde ise çıktı dönüşümü kolay olmamaktadır. Burada da kasıt, verilen bir çizge bölümlemeyi asıl problemimiz olan hiperçizge bölümlemeye dönüştürmektir. Bu kısımda önemli ve faydalı imkansizlık sonuçları türetilmiştir. Bu kolay olmayan kısımlar derinliğince incelenmiş, etkili ve verimli çözümler ve yöntemler önerilmiştir.Bu çalışma çerçevesinde, bir HB tabanlı doluluk azaltan sıralama aracı olan oPaToH, gelişmiş girdi dönüşümleri ile genişletilmiştir. Bunun yanında, başka bir doluluk azaltan sıralama aracı olan onmetıs kullanılarak DACB tabanlı bir HB aracı olan ?hpmetis? üretilmiştir. Ayrıca, yine onmetis kullanılarak bir Dantzig-Wolfe ayrıştırma aracı olan ?dwmetis? üretilmiştir. Dantzig-Wolfe ayrıştırma ise doğrusal problemlerin etkin koşutlanmasında kullanılmaktadır. Deneysel sonuçlarımız gösterdi ki, genişletilen oPaToH, seyrek doğrusal sistem çözümünde hali hazırdaki iyi yöntemlere göre %20'lere varan iyileşme göstermiştir. Üretilen Dantzig-Wolfe ayrıştırma aracı dwmetis ise hali hazırda kullanılan HB tabanlı yöntemlere göre makul kalıte farklılıklarında 5 kata kadar hızlı sonuç üretebilmiştir. Bu sonuç da gayet değerlidir, çünkü toplam performans ölçülürken önçalışma zamanı da değer taşımaktadır. Sonuç olarak, bu çalışmada gösterildi ki koşut ve bilimsel hesaplama işlemlerinin, HB ve DACB problemlerini birbirlerine dönüştürümü kullanılarak daha hızlı çalışmaları sağlanabilmektedir. Hypergraph Partitioning (HP) and Graph Partitioning by Vertex Separator (GPVS)problems are very well known problems which are used in scienti ? c and parallel com-puting effectively. A typical problem in parallel computing is to partition the data/tasksinto several processors such that the overall performance of the computation gets morequali ? ed in terms of time and/or memory. Besides, GPVS is generally used for ? ll-reducing ordering of sparse matrices for solving sparse linear systems ef ? ciently whichlies in the area of scienti ? c computing. In this thesis, the relation between these twoproblems, HP and GPVS problems, are investigated. Two combinatorial reductions,from HP Problem to GPVS Problem and from GPVS Problem to HP Problem are dis-closed along with their theoretical bases. In practice, the nontrivial part of HP Problemto GPVS Problem reduction is the input transformation, that is, converting a graph toa hypergraph such that the reduction holds. The nontrivial part of the reduction fromGPVS Problem to HP Problem is the output transformation, that is, decoding a vertexseparator of the corresponding graph to a partition for the hypergraph. In this part,some useful impossibility results are derived. These nontrivial parts are investigateddeeply and effective and ef ? cient algorithms and methods are proposed.Furthermore, ?oPaToH?, an HP-based ? ll-reducing ordering tool based on PaToH,is enhanced along with implementation of input transformations. Besides, based on? ll-reducing ordering tool onmetis, a GPVS-based HP tool ?hpmetis? is derived anda Dantzig-Wolfe decomposition tool for ef ? cient parallelizm of linear programmingproblem solutions is constructed, which is called as ?dwmetis?. The ? ll-reducing or-dering results obtained with enhanced oPaToH produced more quali ? ed ordering re-sults such as up to %20 improvements for operation count compared to state-of-theart ordering tools such as onmetis. Note that decreasing operation count relates toperforming sparse linear equation solutions faster. The Dantzig-Wolfe decompositionresults with dwmetis produced results around 5 times faster than the state-of-the arthypergraph partitioning tool PaToH with comparable quality for net balancing. Thisis also valuable because the preprocessing overhead is also considered inside the totalexecution time, generally. As a result, in this work it is showed that parallel and sci-enti ? c computing applications can be performed faster by exploiting the combinatorialreductions between HP problem and GPVS problem. 105