Particionamento Automático de Restrições
Autores
|
4542 |
474,160,543
|
|
|
4543 |
474,160,543
|
|
|
4544 |
474,160,543
|
Informações:
Publicações do PESC
Esta tese concentra-se no desenvolvimento de um novo método de particionamento de restrições geral para problemas de satisfação de restrições (CSPs). Uma restrição pode ser descrita em função de mais de um indexical, que explicita cada variável da restrição, gerando um grafo de granulosidade mais fina. Por isso, o novo método, denominado Grouping-Sink, pode ser aplicado a restrições e a indexicals. Ele agrupa nós (restrições ou indexicals) de um grafo baseando-se na dependência (variáveis comuns) existente entre os nós, buscando maior concorrência. O particionamento baseia-se na remoção de nós sinks num grafo com uma orientação acíclica (gerada por Alg-Colour). Os grupos obtidos são distribuídos entre processos ou processadores para uma execução paralela/distribuída.
Os resultados experimentais obtidos mostram que Grouping-Sink por indexicals e por restrições são métodos gerais para qualquer CSP, pois apresentam resultados melhores ou semelhantes aos outros particionamentos aos quais foram comparados.
As contribuições mais relevantes deste trabalho são o desenvolvimento dos algoritmos Grouping-Sink por indexicals e por restrições, duas formas de representação do grafo de restrições (com os nós sendo restrições e sendo indexicals), a adaptação do sistema PCSOS para validação do método, a execução numa máquina paralela real e a demonstração empírica de que Alg-Colour, o algoritmo de orientação acíclica utilizado neste trabalho, sempre gera nós sink que pertencem ao período.
This thesis focuses on the study of a new general constraint partitioning method to Constraint Satisfaction Problems (CSPs). A constraint can be represented as a set of indexicals, where each indexical makes explicit each variable of the constraint. An indexical graph is more fine-grained than a constraint graph. So, the new method named Grouping-Sink can be applied to constraints and to indexicals. Grouping-Sink groups nodes (constraints or indexicals) in a graph according to the dependency (common variables) between the nodes. It tries to get maximum concurrency, reducing the communication between the groups. Grouping-Sink removes sink nodes in a graph with acyclic orientation (obtained with Alg-Colour). The generated groups are distributed between processes or processors to execute in a parallel or distributed way.
The experimental results show that Grouping-Sink per indexicals and per constraints are general methods for partitioning CSPs. Their results are better or similar to the other partitioning methods implemented in PCSOS.
Our main contributions are the implementation of Grouping-Sink per indexicals and per constraints, two new forms of representing the constraint graph, the adaptation of the PCSOS system to validate the new methods, the execution in a real parallel machine, and the empirical demonstration that Alg-Colour always generates sink nodes that belong to the period.