/FastPartitioner

A fast hypergraph partitioner that runs on the GPU

Primary LanguageC++MIT LicenseMIT

FastPartitioner

Table of Contents

Hypergraph Definition

A hypergraph H = (V, N) is defined as a set of vertices V and a set of nets (hyperedges) N among those vertices. A net n ∈ N is a subset of vertices and the vertices in n are called its pins.

Hypergraph



Figure 1: A hypergraph representation with 4 nets (edges) (N1, N2, N3, N4) and 8 vertices (v1, v2, v3, v4, v5,v6,v7,v8). Pin sets of the nets are given below.
N1 = {v1, v2, v3}
N2 = {v1, v6, v7, v8}
N3= {v3, v4, v5}
N4= {v6,v7}


Hypergraph partitioning

A K-way partition of a hypergraph H is a partition of its vertex set, which is denoted as ∏ = {V1, V2, . . . , Vk}, where
• parts are pairwise disjoint, i.e., Vk ∩ Vl = ∅ for all 1 ≤ k ≤ l ≤ K
• each part Vk is a nonempty subset of V, i.e., Vk ⊆ V and Vk ≠ ∅ for 1 ≤ k ≤ K,
• the union of K parts is equal to V,

Let Wk denote the total vertex weight in Vk, that is Wk = ∑ v∈Vk w[v] and Wavg denote the weight of each part when the total vertex weight is equally distributed, that is Wavg = ∑ v∈Vk w[v] / K. If each part Vk ∈ Π satisfies the balance criterion
Wk ≤ Wavg(1 + ε), for k = 1, 2, . . . , K
We say that Π is ε-balanced where ε is called the maximum allowed imbalance ratio.

Hypergraph_partition





Figure 2: A partitioning result of a hypergraph with 4 nets (N1, N2, N3, N4) and 8 vertices (v1, v2, .., v8) into 4 parts. Resulting partitions are given below.
P1 = {v1, v2}
P2 = {v3, v4, v5}
P3= {v6, v7, v8}






Partitioning Metrics

Quality of the hypergraph partitioninig problem is evaluated based on different metrics. These metrics are generally based on the connectivity of the hypernets after the partitioning. One can find detailed information about the metrics that we are interested in this project below.

Cut Net

Cut net is the total number of hypernets that have connectivity values more than 1(Basically connected to more than 1 partition).

Total Volume(k-1, connectivity - 1)

Total volume is the most popular metric in the literature. It's calculated over a sum of connectivity values of the edges with substracting 1 from them. It's also called k-1 or connectivity - 1 for that reason.

Total Message

Total message is a metric that based on possible communication requirements between the partitions. Each net has a special vertex in it's vertex set called the source node and all the other nodes of it called target nodes. We say a message is sent from partition of a source node of a net to it's partitions of it's target nodes. Then total message is the total number of different communication pairs among the partitions.

Maximum Send Message

Maximum send message is the number of messages that is send by the part which sends the most messages. Algorithms for this metric focuses on removing the bottleneck which caused by some processor by being responsible for most of the communication between the parts.

Maximum Send Message

Maximum send volume is the cost that is caused by the part which has the source nodes of nets that causes the most connections between the parts when they summed . Algorithms for this metric focuses on removing the bottleneck which caused by some processor by being responsible for most of the communication over the nets.

Maximum Send Message

Maximum send received volume is the cost that is caused by the part which has the source nodes of nets that causes the most connections between the parts when they summed and in addition to that it's target nodes which causes communication with other parts. Algorithms for this metric focuses on removing the bottleneck which caused by some processor by being responsible for most of the communication over the nets.

Build FastPartitioner itself can partition and reorder hypergraphs and tensors. Moreover, it can automate experimenting process leveraging other tools. Those tools are Splatt and PaToH. You need to install those tools and their dependencies to fully employ FastPartitioner capabilities. Please note that FastPartitioner assumes user have a CUDA capable GPU.