Kernighan Lin Algorithm

[joaquinffernandez]

Basic Definitions

Given a SBG $G(V,E)$ and an initial partition $(A,B)$ of $V$, define external cost and internal cost as:
$\forall a \in A \rightarrow E_a = \sum_{y \in B} c_{ay} $
$\forall a \in A \rightarrow I_a = \sum_{x \in A} c_{ax} $

Now we can define:
$\forall a \in A \rightarrow D_a = E_a - I_a $

To compute the difference, internal cost and external cost assume that each partition is represented as:

$A = \{ A_1, A_2, \cdots, A_k\}$ where $A_i \cap A_j = \emptyset | \forall i,j \in \{1,\cdots,k\}, i \neq j$

and let:
$\mathbf{ED} = E.preImage(A_i) = \{ ed_1, \cdots, ed_m\}$ (This should be $map_1$ or $map_2$)
which is the set of all the domains of the set-edges that contains the set $A_i$ from the partition that is included in some set-vertex of the original graph.

Now, assume that $\#ed_i = \mathbf{Q} | \forall i \in \{1, \cdots,m\}$, i.e. all the set-edges involved on each partition interval have the same cardinality.

Algorithm
With these assumptions, we can define the KL-SBG algorithm as follows:

$\mathbf{KL-SBG}(G, P = (A,B), C):$

• $A_c = A$
• $B_c = B$
• $max\_par\_sum = 0$
• $max\_par\_sum\_set = \emptyset$
• $par\_sum = 0$
• $A_v = \emptyset$
• $B_v = \emptyset$
• $GM = \mathbf{compute\_diff}(A_c, B_c, G, C)$
• $\mathbf{while}(A_c \neq \emptyset \wedge B_c \neq \emptyset):$
  • $< i, j, g, s > = \mathbf{max\_diff}(GM)$
  • $(A', B')=\mathbf{update\_sets} (A_c, B_c, A_v, B_v, i, j, s)$
  • $\mathbf{update\_sum} (par\_sum, g, max\_par\_sum, max\_par\_sum\_set, A', B')$
  • $\mathbf{update\_diff} (A_c, B_c, i, j, s, GM, G)$
• $\mathbf{if}(max\_par\_sum\_set \neq \emptyset):$
  • $(A^{\star}, B^{\star}) = max\_par\_sum\_set$
  • $A = (A/A^{\star}) \cup B^{\star}$
  • $B = (B/B^{\star}) \cup A^{\star}$
• return

$\mathbf{KL-SBG-BIPART}(G, P = (A,B), C):$

• $A' = A$
• $B' = B$
• $\mathbf{KL-SBG}(G, (A,B), C)$
• $\mathbf{while}(A' \neq A \wedge B' \neq B):$
  • $A' = A$
  • $B' = B$
  • $\mathbf{KL-SBG}(G, (A,B), C)$
• return

$\mathbf{update\_sets} (A_c, B_c, A_v, B_v, i, j, s):$

• $A' = \{ a_k \in A_i | k \leq s\}$
• $B' = \{ b_k \in B_j | k \leq s\}$
• $A_v = A_v \cup A'$
• $B_v = B_v \cup B'$
• $A_c = A_c / A'$
• $B_c = B_c / B'$
• return $(A', B')$

$\mathbf{compute\_EC\_IC}(P, Q, S, map_1, map_2):$

• $D = map_1.preImage(S)$
• $I = map_2.image(D)$
• $IC' = (P \cap I) / S$
• $IC = map_2.preImage(IC')$
• $EC' = (I / IC) \cap Q$
• $EC = map_2.preImage(EC')$
• return $(EC,IC)$

$\mathbf{compute\_diff}(P = \{P_1,\cdots, P_k\}, G):$

• $D = <>$
• $\forall P_i \in P$
  • $(EC_i, IC_i) = \mathbf{compute\_EC\_IC}(P, P_i, G.map_1(), G.map_2())$
  • $(EC_i, IC_i) = (EC_i, IC_i) \cup \mathbf{compute\_EC\_IC}(P, P_i, G.map_2(), G.map_1())$
  • $D.push\_back((EC_i, IC_i))$
• return $D$

$\mathbf{compute\_diff}(A, B, G, C):$

• $D_A = \mathbf{compute\_diff}(A, G)$
• $D_B = \mathbf{compute\_diff}(B, G)$
• $GM = \mathbf{compute\_gain\_matrix} (D_A, D_B, C)$
• return $GM$

$\mathbf{compute\_gain\_matrix} (D_A, D_B, C):$

• $G= <>$
• $\forall d_i \in D_A$:
  • $gain_{d_i} = <>$
  • $\forall d_j \in D_B$:
    • $s = \mathbf{min}(\# d_i, \# d_j)$
    • $g = \mathbf{diff} (d_i, s) + \mathbf{diff} (d_j, s) - 2 \times c_{a,b}$
    • $gain_{d_i}.\mathbf{insert}(i,j,g,s)$
  • $G.\mathbf{insert}(gain_{d_i})$

Notes:
Here $\mathbf{diff}$ refers to the tuple $d_i=(EC_i, IC_i)$ restricted to the maximum number of elements possible $s$.

$\mathbf{max\_diff}(GM):$

• $gain = GM.\mathbf{pop}()$
• $g_{max} = < i,j,g,s > = gain.\mathbf{pop}()$
• $gain.\mathbf{update}(s)$
• $GM.\mathbf{insert}(gain)$
• return $g_{max}$

$\mathbf{update\_diff} (P, D_A, D_B, i, j, s, GM, G, lookup):$

• $\mathbf{I_{upd}} = \{ P_1, \cdots, p_n\}= \mathbf{image}(EC'_j, G) \cap P$
• $\forall p_k \in I_{upd}:$
  • $\mathbf{if}(lookup = row):$
    • $GM.\mathbf{update\_row}(k,j, s)$
  • $\mathbf{else}:$
    • $GM.\mathbf{update\_row}(j,k, s)$
• $\mathbf{E_{upd}} = \{ P_1, \cdots, p_n\}= \mathbf{image}(IC'_i, G) \cap P$
• $\forall p_k \in I_{upd}:$
  • $\mathbf{if}(lookup = row):$
    • $GM.\mathbf{update\_row}(k,j, s)$
  • $\mathbf{else}:$
    • $GM.\mathbf{update\_row}(j,k, s)$

$\mathbf{update\_diff} (A_c, B_c, D_A, D_B, i, j, s, GM, G):$

• $\mathbf{update\_diff} (A_c, D_A, D_B, i, j, s, GM, G, row)$
• $\mathbf{update\_diff} (B_c, D_A, D_B, j, i, s, GM, G, column)$
• return

$\mathbf{update\_sum} (par\_sum, g, max\_par\_sum, max\_par\_sum\_set, A', B'):$

• $par\_sum = par\_sum + g$
• $\mathbf{if}(par\_sum > max\_par\_sum):$
  • $max\_par\_sum = par\_sum$
  • $max\_par\_sum\_set = max\_par\_sum\_set \cup (A', B')$
• return

[joaquinffernandez]

Leaving here some refs:

• https://epubs.siam.org/doi/epdf/10.1137/1.9781611975215.7
• https://inria.hal.science/hal-04404141/
• https://faculty.cc.gatech.edu/~umit/PaToH/manual.pdf
• https://github.com/KaHIP/KaHIP
• https://dl.acm.org/doi/abs/10.1145/3529090
• https://dl.acm.org/doi/10.1145/3571808#sec-4

[joaquinffernandez]

COMPUTE GAINS CONSIDERING PARTITION IMBALANCE
In order to define $\mathbf{compute\_partition\_imbalance}$ function we must take into account the following considerations:
Let
$B = \lceil{\frac{W(\mathbf{V})}{k}}\rceil$
$Im = \epsilon \times B$
$LMax = B+Im$
$LMin = B-Im$
where:

• $\epsilon$ is a given parameter with $0 \le \epsilon \le 1$
• $W(\mathbf{V})$ is the total weigth of the SBG nodes.
• $k$ is number of partitions to compute.

In this context $Im$ means the maximum load imbalance allowed for each partition with $\epsilon$ used as the imbalanace parameter.
So given a partition $\mathbf{P} = \{P_1,\cdots, P_k\}$ of $\mathbf{V}$ the following condition should be valid:

$\forall P_i \in \mathbf{P} \rightarrow LMin \le W(P_i) \le LMax $

In addition, we have that each partition is composed of intervals: $\forall P_i \in P \rightarrow P_i = \{I_{1}^{i},\cdots, I_{m}^{i}\}$, so we can define:
$w(I_{j}^{i})$
that represents the weight of an individual element of the j-th interval of the i-th partition.

This function defined below returns two vectors containing the possible node imbalance for each partition considering the node weights and the allowed imbalance, I.e. here we look for possible $\mathbf{number}$ of nodes that can be moved from one partition to the other taking into account the node weights. Note that until now we considered that all nodes have the same constant weight.

$\mathbf{compute\_partition\_imbalance}(I_j^a, I_j^b, P_a, P_b, W, w):$

• $i_a= <>$ // candidate node imbalance values for partition A
• $i_b= <>$ // candidate node imbalance values for partition B
• $bal\_part = \mathbf{min}(w(I_j^a)\times\# I_j^a, w(I_j^b)\times\# I_j^b)$ // This represents the balanced value that keeps the current work load in both partitions.
• $nodes\_bal\_part_a = \lfloor\frac{bal\_part}{w(I_j^a)}\rfloor$ // How many nodes from partition $a$ we need to meet the balance constraint.
• $nodes\_bal\_part_b = \lfloor\frac{bal\_part}{w(I_j^b)}\rfloor$ // The same for partition $b$
• $i_a.\mathbf{insert}(nodes\_bal\_part_a)$
• $i_b.\mathbf{insert}(nodes\_bal\_part_b)$

Now that we have our first balanced candidates, look for the imbalanced ones which is basically the same procedure for the imbalance max and min values.

• $\mathbf{partition\_imbalance}(I_j^a,P_a,P_b, i_a,i_b)$
• $\mathbf{partition\_imbalance}(I_j^b,P_b,P_a, i_b,i_a)$
• return $<i_a, i_b>$

With $\mathbf{partition\_imbalance}$ defined as:

$\mathbf{partition\_imbalance}(I_j,P_1, P_2, i_1,i_2):$

• $max\_imbal\_part = LMax - W(P_2)$ // This value represents the maximum imbalance allowed for the partition.
• $min\_imbal\_part = W(P_1) - LMin$ // This value represents the minimum imbalance allowed for the partition.
• $nodes\_imbal\_part = \lfloor\frac{max\_imbal\_part}{w(I_j)}\rfloor$ // How many nodes can we send to the other partition without breaking the upper imbalance bound.
• $min\_nodes\_imbal\_part = \lfloor\frac{min\_imbal\_part}{w(I_j)}\rfloor$ // How many nodes can we send to the other partition without breaking our lower imbalance bound.
• if $nodes\_imbal\_part > min\_nodes\_imbal\_part$:
  • $nodes\_imbal\_part = min\_nodes\_imbal\_part$
• if $nodes\_imbal\_part > \# I_j$:
  • $nodes\_imbal\_part = \# I_j$
• $i_1.\mathbf{insert}(nodes\_imbal\_part)$ // Insert the candidate in the vector (remove duplicates).
• $i_2.\mathbf{insert}(0)$

Finally, we can define:

$\mathbf{compute\_gain\_matrix} (A, B, D_A, D_B, C, W, w):$

• $G= <>$
• $\forall d_i \in D_A$:
  • $gain_{d_i} = <>$
  • $\forall d_j \in D_B$:
    • $<i_a, i_b> = \mathbf{compute\_partition\_imbalance}(I_i^A, I_j^B, A, B, W, w)$
    • $<g, s_a, s_b> = \mathbf{get\_max\_gain} (i_a, i_b, d_i, d_j)$
    • $gain_{d_i}.\mathbf{insert}(i,j,g,s_a, s_b)$
  • $G.\mathbf{insert}(gain_{d_i})$

$\mathbf{get\_max\_gain} (Im_a, Im_b, d_i, d_j):$

• $max\_gain = 0$
• $s_a = 0$
• $s_b = 0$
• $\forall im_a \in Im_a$:
  • $\forall im_b \in Im_b$:
    • $g = \mathbf{diff} (d_i, im_a) + \mathbf{diff} (d_j, im_b) - 2 \times c_{a,b}$
    • if $g > max\_gain$:
      • $max\_gain = g$
      • $s_a = im_a$
      • $s_b = im_b$
• return $<g, s_a, s_b>$

This new version of $\mathbf{compute\_gain\_matrix}$ should replace the one defined in the first version