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

The modeling flexibility provided by hypergraphs has drawn a lot of interest from the combinatorial scientific community, leading to novel models and algorithms, their applications, and development of associated tools. Hypergraphs are now a standard tool in combinatorial scientific computing. The modeling flexibility of hypergraphs however, comes at a cost: algorithms on hypergraphs are inherently more complicated than those on graphs, which sometimes translate to nontrivial increases in processing times. Neither the modeling flexibility of hypergraphs, nor the runtime efficiency of graph algorithms can be overlooked. Therefore, the new research thrust should be how to cleverly trade-off between the two. This work addresses one method for this trade-off by solving the hypergraph partitioning problem by finding vertex separators on graphs. Specifically, we investigate how to solve the hypergraph partitioning problem by seeking a vertex separator on its net intersection graph (NIG), where each net of the hypergraph is represented by a vertex, and two vertices share an edge if their nets have a common vertex. We propose a vertex-weighting scheme to attain good node-balanced hypergraphs, since NIG model cannot preserve node balancing information. Vertex-removal and vertex-splitting techniques are described to optimize cutnet and connectivity metrics, respectively, under the recursive bipartitioning paradigm. We also developed an implementation for our GPVS-based HP formulations by adopting and modifying a state-of-the-art GPVS tool onmetis. Experiments conducted on a large collection of sparse matrices confirmed the validity of our proposed techniques.