Partitioning a polyhedral processing network into K-balanced partitions with constraints

Graph Partitioning Algorithms play a major role in data analysis, machine learning, computer science, engineering, and related fields. Most useful graph partitioning criteria correspond to optimizing a ratio between the cut and the size of the partitions, this ratio leads to an NP-Complete problem. This makes it difficult to know whether the algorithm due to the optimization solution or not. In this thesis we present a algorithm that seeks and finds the solution of Graph Partitioning Problems in order to satisfy two major constraints. We use a classical approach to ratio problems where we repeatedly ask whether the solution is greater than or less than some constant which refers to our constraints. Given an un-weighted graph $G$ with V nodes and E edges and given a number K, the Graph Partitioning Problem is to divide the $V$ nodes into K parts such that the number of edges connecting nodes in different parts is minimized given the condition that each part contains roughly the same number of nodes. If the graph is weighted, i.e. the nodes and edges have weights associated with them, the problem requires the sum of the weights of the edges connecting nodes in different parts, in order to be minimized with given conditions that the sum of the weights in each part is roughly the same. The problem can be reduced into where the graph is split into n parts and then merging these nodes to make a fewer nodes which could be easier for partitioning in initial partitioning phase. A successful heuristic for partitioning large graphs is the Multi-Level Graph Partitioning approach, where the graph is recursively contracted to create smaller graphs which should reflect the same basic structure as the input graph. After applying an initial partitioning algorithm to the smallest graph, the contraction is undone and, at each level, a local search method is used to improve the partitioning induced by the coarser level. We used the Fiduccia-Mattheyses algorithm for refining the partition after initial partitioning step to improve the edge cuts. Although several successful Multi-Level partitioners have been developed in the last two decades, we had thought that certain aspects of the method are not well understood. Our main focus is on the Multi-Leveling approach to satisfy our constraints. First constraint is related to cut size between each pair of final partitions. So in order to meet this constraint we should consider the cut size not only in original graph but also between each final partitions, so that the cut size between each pair of partitions is less or equal than a specific number. The second constraint is related to resource which is related to each node. Specially at the initial partitioning step we should consider these constraints. We show how to obtain a solution that meets these constraints achieving a more balanced network. We will present the results and compare them to those of the Metis software that is the current state of the art package for graph partitioning.