Applying scheduling by edge reversal to constraint partitioning

• M. R. Pereira UFRJ
• P. K. Vargas UFRJ
• F. M. G. Franca UFRJ
• M. C. S. de Castro UFRJ / UERJ
• I. de Castro Dutra UFRJ

Resumo

Scheduling by edge reversal (SER) is a fully distributed scheduling mechanism based on the manipulation of acyclic orientations of a graph. This work uses SER to perform constraint partitioning of constraint satisfaction problems (CSP). In order to apply the SER mechanism, the graph representing the constraints must receive an acyclic orientation. Since obtaining an optimal acyclic orientation is an NP-hard problem, we study three nondeterministic strategies known in the literature: Alg-Neigh, Alg-Edges, and Alg-Colour. We implemented the three algorithms and the SER scheduling mechanism, applying them to the CSP constraint networks generated from 3 applications. Our results show that SER has a great potential to perform a good partitioning of the constraint graphs.

Palavras-chave: Processor scheduling, Distributed computing, NP-hard problem, Partitioning algorithms, Scheduling algorithm, Time factors, Concurrent computing, Programming environments, Distributed algorithms, System recovery