Juan Luis García Zapata from the University of Extremadura will present his work on “Spectral graph partition: old and new results”
Abstract: A distributed application is modeled as a weighted graph where tasks or processes are the vertices and the edge between two task is weight by the total volume of communications between them. The problem of graph bi-partitioning is to find, among all possible partitions of the set of tasks into two equal parts, that partition that minimizes communication of one of the two parts to the other. This is of practical interest in mapping tasks to processors of a particular architecture, to take advantage of the
communication channels on the machine.
We’ll talk about the spectral solution to the problem of bipartition. It is based on certain eigenvector of the Laplacian matrix of the graph. The presentation will be based on visual and intuitive examples. We also discuss modifications in this classical solution, to incorporate into the graph model a computational load of tasks, perhaps uneven. Also to do the partition into two parts of predefined volume (for example 1/3 and 2/3 of the total load), for mapping to heterogeneous architectures.
