Applying scheduling by edge reversal to constraint partitioning

Author

Pereira, Marluce Rodrigues ; Vargas, Patrícia Kayser ; França, Felipe M G ; De Castro, Maria Clicia Stelling ; de Castro Dutra, I.

Author_Institution

Univ. Fed. do Rio de Janeiro, Brazil

fYear

2003

fDate

10-12 Nov. 2003

Firstpage

134

Lastpage

141

Abstract

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.

Keywords

computational complexity; constraint theory; distributed algorithms; graph theory; optimisation; processor scheduling; Alg-Colour algorithm; Alg-Edges algorithm; Alg-Neigh algorithm; NP-hard problem; acyclic orientation algorithm; constraint graph representation; constraint partitioning; constraint satisfaction problem; distributed scheduling mechanism; edge reversal scheduling; Concurrent computing; Distributed algorithms; Distributed computing; NP-hard problem; Partitioning algorithms; Processor scheduling; Programming environments; Scheduling algorithm; System recovery; Time factors;

fLanguage

English

Publisher

ieee

Conference_Titel

Computer Architecture and High Performance Computing, 2003. Proceedings. 15th Symposium on

Print_ISBN

0-7695-2046-4

Type

conf

DOI

10.1109/CAHPC.2003.1250331

Filename

1250331