[WIP] Global communication cost

[francosansone]

Proposal of new algorithms to compute global cost based on connected components in set based graphs.

$\mathbf{external\_cost\_by\_connected\_component}(component\_set):$

• $\mathbf{if} \mathbf{not} component\_set \in \mathbf{keys}(ec\_by\_cc)$
  • $nodes\_cc = \mathbf{cc\_map}(component\_set)$
  • $comm\_by\_set = \mathbf{get\_comm\_by\_set}(nodes\_cc)$
  • $ec\_by\_cc[component\_set] = comm\_by\_set$
• $\mathbf{return} ec\_by\_cc[component\_set]$

Where:

• $\mathbf{cc\_map}$ is the piecewise map with the connected components.
• $\mathbf{get\_comm\_by\_set}$ returns the edges that connect any node of the input set with other nodes, communication between nodes of the set is discarded (this is provided by the local communication module).

$\mathbf{internal\_cost\_of\_connected\_component}(component\_set):$

• $\mathbf{if} \mathbf{not} component\_set \in \mathbf{keys}(ic\_by\_cc)$
  • $nodes\_cc = \mathbf{cc\_map}(component\_set)$
  • $edges\_cc = \mathbf{compute\_ic\_of\_cc}(nodes\_cc)$
  • $ic\_by\_cc[component\_set] = edges\_cc$
• $\mathbf{return} ic\_by\_cc[component\_set]$

Where:

• $\mathbf{cc\_map}$ is the piecewise map with the connected components.
• $\mathbf{compute\_ic\_of\_cc}$ computes communication between set pieces of the connected components, following the same idea as presented here, iterating and computing intersection to detect edges that communicates set pieces.

We should think of ways to leverage this information to move set pieces among different partitions.