Particionamento Automático de Redes de Restrições para Execução Paralela

Particionamento Automático de Redes de Restrições para Execução Paralela Xu Yi Mestrado em Ciência de Computadores Departamento de Ciência de Computadores 2013 Orientador Inês de Castro Dutra Professora Auxiliar Faculdade de Ciências da Universidade do Porto Todas as correções determinadas pelo júri, e só essas, foram efetuadas. O Presidente do Júri, Porto, ______/______/_________ Acknowledgments First I would like to thank my supervisor that made this thesis possible, Prof. Dr. Inˆes Dutra My friends that helped through this part of my life. Finally my family for their never ending support. ii Resumo Este trabalho concentra-se no desenvolvimento de um m´etodo de particionamento de restri¸c˜oes baseado na bisse¸c˜ao recursiva espectral de Hendrickson e Leland. As restri¸c˜oes s˜ao representadas num grafo que ´e particionado atrav´es de c´alculos de vetores pr´oprios e valores pr´oprios de uma matriz laplaciana associada ao grafo. Utilizamos dez grafos com caracter´ısticas variadas para o particionamento e comparamos os resultados com um segundo m´etodo baseado em “min-cut” (corte m´ınimo do grafo) chamado Max Aggregation. As m´etricas de avalia¸c˜ao utilizadas foram n´umero de arestas, n´umero de v´ertices, densidade e grau m´edio dos v´ertices. Os resultados mostram que o m´etodo de bisse¸c˜ao espectral recursiva, em geral, produz um n´umero maior de grupos do que o m´etodo Max Aggregation, o que pode favorecer um melhor aproveitamento dos processadores e pode permitir a troca de mensagens simultˆanea entre os v´arios grupos. iii Abstract This work focuses on the development of a partitioning method for constraints networks based on the recursive spectral bisection of Hendrickson and Leland. Constraints are represented in a graph that is partitioned by calculation of eigenvectors and eigenvalues of a Laplacian matrix associated with the graph. We used ten graphs with various characteristics for partitioning and compared the results with a second method based on min-cut called Max Aggregation. The evaluation metrics used were number of edges, number of nodes, density and average degree of nodes. The results show that the spectral recursive bisection method generally produces a number of groups greater than the Max aggregation method, which can promote better use of the processors and can allow the exchange of simultaneous messages between the various groups. iv Conte´udo Resumo iii Abstract iv Lista de Tabelas viii Lista de Figuras x 1 Introdu¸c˜ao 1 1.1 Contextualiza¸c˜ao .............................. 1 1.2 Motiva¸c˜ao.................................. 3 1.3 Objetivos .................................. 3 1.4 Contribui¸c˜oes ................................ 4 1.5 Organiza¸c˜ao da Disserta¸c˜ao . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Fundamenta¸c˜ao Te´orica 6 2.1 Problemas de Satisfa¸c˜ao de Restri¸c˜oes . . . . . . . . . . . . . . . . . . . 6 2.2 Grafos e Problemas Relacionados [20] . . . . . . . . . . . . . . . . . . . 10 v 2.2.1 Parti¸c˜oes e Agrupamentos (Clusterings) . . . . . . . . . . . . . 11 2.2.2 Fun¸c˜oes Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . 12 2.2.3 Algoritmos de Particionamento em Grafos . . . . . . . . . . . . 13 2.2.4 M´etodo da Bisse¸c˜ao Espectral Recursivo . . . . . . . . . . . . . 15 3 Utiliza¸c˜ao do m´etodo de Bisse¸c˜ao 17 3.1 Algoritmos.................................. 17 3.2 Exemplo de aplica¸c˜ao do algoritmo . . . . . . . . . . . . . . . . . . . . 19 3.3 Implementa¸c˜ao ............................... 21 4 Materiais e M´etodos 23 4.1 Compara¸c˜ao entre os dois algoritmos . . . . . . . . . . . . . . . . . . . 24 5 Resultados 27 5.1 Grupo de grafos com densidade baixa . . . . . . . . . . . . . . . . . . . 28 5.2 Grupo de grafos com densidade m´edia . . . . . . . . . . . . . . . . . . 29 5.3 Grafo de densidade alta . . . . . . . . . . . . . . . . . . . . . . . . . . 31 5.4 Discuss˜ao .................................. 31 6 Conclus˜oes e Trabalhos Futuros 43 A C´odigo fonte 45 B Resultados de Execu¸c˜ao 54 B.0.1 Grafo1 ............................... 54 vi B.0.2 Grafo2 ............................... 54 B.0.3 Grafo3 ............................... 54 B.0.4 Grafo4 ............................... 56 B.0.5 Grafo5 ............................... 56 B.0.6 Grafo6 ............................... 56 B.0.7 Grafo7 ............................... 56 B.0.8 Grafo8 ............................... 57 B.0.9 Grafo9 ............................... 57 B.0.10Grafo10............................... 58 Referˆencias 58 vii Lista de Tabelas 4.1 Caracter´ısticas dos Grafos Originais . . . . . . . . . . . . . . . . . . . . 25 5.1 Caracter´ısticas dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . 33 5.2 N´umero de V´ertices dos Grafos . . . . . . . . . . . . . . . . . . . . . . 34 5.3 N´umero de arestas dos Grafos . . . . . . . . . . . . . . . . . . . . . . . 35 5.4 Densidade dos Grafos . . . . . . . . . . . . . . . . . . . . . . . . . . . . 36 5.5 Grau m´edio dos v´ertices . . . . . . . . . . . . . . . . . . . . . . . . . . 37 viii CAP´ ITULO 1. INTRODUC¸ ˜ AO 5 motiva¸c˜ao e objetivos inerentes a este trabalho. Cap´ıtulo 2 – Neste cap´ıtulo apresentamos a fundamenta¸c˜ao te´orica sobre m´etodos de bisse¸c˜ao. Neste cap´ıtulo, tamb´em efetuamos um levantamento das redes de restri¸c˜oes e paraleliza¸c˜ao de redes de restri¸c˜oes. Cap´ıtulo 3 – Neste cap´ıtulo apresentamos a descri¸c˜ao do m´etodo de bisse¸c˜ao espectral utilizado neste trabalho, explicando a estrutura de dados utilizada, bem como a sua implementa¸c˜ao. Cap´ıtulo 4 – Neste cap´ıtulo apresentamos os Materiais e M´etodos utilizados para a realiza¸c˜ao das experiˆencias. Apresentamos os grafos classificados em categorias relacionadas com a sua densidade e explicamos o m´etodo de avalia¸c˜ao do particionamento. Cap´ıtulo 5 – Neste cap´ıtulo s˜ao apresentados e analisados os resultados obtidos ap´os a execu¸c˜ao das experiˆencias, de acordo com as m´etricas de desempenho. Cap´ıtulo 6 – Finalmente, este cap´ıtulo apresenta as considera¸c˜oes finais, onde ´e efetuado um balan¸co sobre todo o trabalho realizado, com especial destaque para os objetivos propostos. O cap´ıtulo termina com uma abordagem ao trabalho futuro. Cap´ıtulo 2 Fundamenta¸c˜ao Te´orica Neste cap´ıtulo, apresentamos os conceitos fundamentais para o entendimento do restante do trabalho. Introduzimos problemas de satisfa¸c˜ao de restri¸c˜oes, sua representa¸c˜ao em grafos, algoritmos para resolvˆe-los e suas complexidades, assim como, exemplos de problemas. Tamb´em neste cap´ıtulo, apresentamos os principais m´etodos de particionamento em grafos. 2.1 Problemas de Satisfa¸c˜ao de Restri¸c˜oes Um modelo que envolva vari´aveis, seus dom´ınios e restri¸c˜oes entre vari´aveis ´e chamado de problema de satisfa¸c˜ao de restri¸c˜oes ou rede de restri¸c˜oes [18] . Neste texto ´e utilizada a nota¸c˜ao problema de satisfa¸c˜ao de restri¸c˜oes (Constraint Satisfaction Problem - CSP). Um CSP ´e um tipo especial de problema de busca que possui estados e dom´ınios. Os estados s˜ao conjuntos de vari´aveis. O estado inicial ´e um conjunto de vari´aveis com valores poss´ıveis iniciais. O estado final ´e um conjunto de vari´aveis com valores que respeitem as restri¸c˜oes do problema. O dom´ınio ´e o conjunto poss´ıvel de valores que uma vari´avel pode assumir, que pode ser discreto ou cont´ınuo e finito ou infinito. 6 CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 7 O CSP define restri¸c˜oes sobre vari´aveis e um dom´ınio que relaciona cada vari´avel a um conjunto de valores. Um solver ´e um m´etodo para resolver CSPs. V´arios solvers de CSP possuem complexidade polinomial. O objetivo dos solvers ´e transformar um CSP, que tem espa¸co de busca exponencial, em outro equivalente com os dom´ınios menores para as vari´aveis [15]. Para encontrar as solu¸c˜oes o solver passa por fases de elimina¸c˜ao de valores do dom´ınio das vari´aveis, de acordo com as restri¸c˜oes. Os solvers dependem do dom´ınio das vari´aveis. No caso de restri¸c˜oes no dom´ınio real (infinito), s˜ao utilizados m´etodos matem´aticos como elimina¸c˜ao de Gauss e FourierMoutzkin ou m´etodos computacionais como o Simplex [22]. No caso de dom´ınios finitos, uma classe importante dos algoritmos para resolver CSPs ´e a classe dos algoritmos de consistˆencia de arcos[12]. Estes algoritmos tˆem complexidade exponencial dependente do n´umero de vari´aveis, n´umero de restri¸c˜oes e tamanho do dom´ınio de cada vari´avel. Para solucionar CSPs que possuem dom´ınios finitos s˜ao necess´arias duas escolhas: a da vari´avel e a do valor da vari´avel. A escolha da vari´avel pode ser most-constrained, most-constraining ou least-constrained. Na escolha most-constrained ´e escolhida a vari´avel de menor dom´ınio. Na most-constraining, a vari´avel escolhida ´e a que restringe ao m´aximo os dom´ınios das outras vari´aveis. Na least-constrained a vari´avel com maior dom´ınio ´e escolhida. Al´em disso, least-constrained utiliza uma heur´ıstica baseada na minimiza¸c˜ao do n´umero de falhas para evitar backtracking. A escolha do valor da vari´avel, tamb´em, pode ser feita utilizando-se v´arios m´etodos: least-constraining, menor valor, valor m´edio, maior valor ou valor sequencial. Pelo princ´ıpio least constraining, o valor escolhido ´e aquele que afeta menos o conjunto de valores das outras vari´aveis. A escolha dos valores menor, m´edio ou maior consiste em escolher, respectivamente, o menor, o valor m´edio ou o maior valor do conjunto de valores do dom´ınio. A escolha de um valor seq¨uencial consiste em selecionar o pr´oximo valor do dom´ınio que ainda n˜ao foi escolhido. CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 8 As heur´ısticas utilizadas para a sele¸c˜ao da pr´oxima vari´avel ou do pr´oximo valor a ser atribu´ıdo a uma vari´avel tˆem como objetivo principal reduzir o espa¸co de procura tentando encontrar solu¸c˜oes de uma forma mais r´apida. Mas ainda para muitos problemas, ou estas heur´ısticas n˜ao s˜ao aplic´aveis ou n˜ao temos informa¸c˜ao suficiente sobre o problema para aplic´a-las da forma mais eficaz. Uma alternativa para acelerar a execu¸c˜ao passa, portanto por encontrar subgrupos (semi)independentes de restri¸c˜oes que possam ser processadas em paralelo. Considerando apenas problemas de satisfa¸c˜ao de restri¸c˜oes que possuem um conjunto de vari´aveis, um dom´ınio finito para cada vari´avel e um conjunto de restri¸c˜oes un´arias ou bin´arias, ´e poss´ıvel representar o CSP por um grafo de restri¸c˜oes, onde cada n´o representa uma vari´avel e cada arco representa uma restri¸c˜ao entre vari´aveis. Para exemplificar um problema de satisfa¸c˜ao de restri¸c˜oes sobre dom´ınios finitos, suponha o problema de se colocar Nrainhas em um tabuleiro de xadrez N×Nde tal forma que as rainhas n˜ao se ataquem. As rainhas se atacam se estiverem na mesma linha, na mesma coluna, na mesma diagonal ascendente ou na mesma diagonal descendente. Cada rainha deve ser colocada em uma linha do tabuleiro. O problema consiste em selecionar uma coluna para cada rainha, de forma que elas n˜ao se ataquem. Este ´e um problema cl´assico em satisfa¸c˜ao de restri¸c˜oes representativo de uma s´erie de aplica¸c˜oes (por exemplo, controle de tr´afego). Uma representa¸c˜ao em satisfa¸c˜ao de restri¸c˜oes deste problema consiste em associar cada rainha a uma vari´avel e fixar cada rainha numa linha do tabuleiro. Cada vari´avel pode assumir valores de 1 a N, que s˜ao os valores das colunas que as rainhas podem ocupar e que correspondem ao dom´ınio do problema. As restri¸c˜oes correspondem `as condi¸c˜oes necess´arias e suficientes para que as rainhas n˜ao se ataquem. Para exemplificar o conjunto de restri¸c˜oes, suponha que XeYsejam duas rainhas. As restri¸c˜oes para que a rainha Yseja colocada no tabuleiro de xadrez de forma que n˜ao ataque a rainha X, colocada anteriormente, podem ser escritas da seguinte forma: Y�=X, rainhas XeYn˜ao se atacam na mesma coluna; CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 9 Y�=X+I, rainhas XeYn˜ao se atacam numa das diagonais e Y+I�=X, rainhas XeYn˜ao se atacam na outra diagonal, onde I∈1, ..., N corresponde `a diferen¸ca entre as linhas que as rainhas coupam [16]. Para uma representa¸c˜ao em grafo, podemos colocar as vari´aveis ou as restri¸c˜oes nos v´ertices. Como o nosso objetivo ´e fazer o particionamento do grafo para execu¸c˜ao paralela e diminuir a comunica¸c˜ao (n´umero de arestas que cruzam de um v´ertice a outro), o mais natural ´e ter uma representa¸c˜ao em grafo, onde os v´ertices s˜ao as restri¸c˜oes e as arestas s˜ao as vari´aveis compartilhadas entre as restri¸c˜oes (considerando que as restri¸c˜oes s˜ao unidades de execu¸c˜ao). O grafo de restri¸c˜oes tradicional, em CSP, representa as vari´aveis nos n´os e as restri¸c˜oes nas arestas. Este tipo de grafo ´e usado em geral com algoritmos de consistˆencia de arcos. Nesta representa¸c˜ao, as dependˆencias entre os v´ertices (arestas) s˜ao restri¸c˜oes. A Figura 2.1 exemplifica este tipo de grafo para um CSP com 4 vari´aveis (V1,V2,V3,V4) e 3 restri¸c˜oes (V1=V2+ 1, V1=V3+ 2 e V1=V4+ 3). Figura 2.1: Grafo de restri¸c˜oes tradicional (retirado de [16]) Uma segunda forma de representar o problema considera as restri¸c˜oes como n´os e as vari´aveis comuns entre as restri¸c˜oes nas arestas. Com esta representa¸c˜ao, a dependˆencia entre os n´os passa ser as vari´aveis comuns entre eles. Considerando o mesmo CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 10 exemplo da Figura 2.1, a nova representa¸c˜ao do grafo de restri¸c˜oes ´e apresentada na Figura 2.2. Note que, para este exemplo, as 3 restri¸c˜oes possuem a mesma vari´avel em comum (V1). Com esta representa¸c˜ao o particionamento das restri¸c˜oes pode utilizar como fator para agrupar restri¸c˜oes as vari´aveis comuns entre as restri¸c˜oes. Figura 2.2: Grafo de restri¸c˜oes para particionamento (retirado de [16]) Este tipo de grafo pode ser particionado de forma que grupos de restri¸c˜oes possam ser executadas em paralelo. O nosso objetivo ´e decompor um grafo como este minimizando o n´umero de arestas entre os diferentes grupos. 2.2 Grafos e Problemas Relacionados [20] Um grafo G com pesos consiste de um conjunto de n´os Ve um conjunto de arestas E⊂V×Vque representam as rela¸c˜oes entre os n´os, assim como duas fun¸c˜oes de custo. Uma fun¸c˜ao atribui pesos aos v´ertices c:V→R>0e uma segunda fun¸c˜ao ω: E→Ratribui pesos `as arestas. Em geral, adotamos a vari´avel npara o n´umero de n´os e mpara o n´umero de arestas. Em um grafo n˜ao dirigido uma aresta (u, v)∈E implica uma aresta (v, u)∈Eem que ambos os pesos das arestas s˜ao iguais. Usamos a nota¸c˜ao de conjunto {u, v} ∈ Eno caso n˜ao dirigido. Estendemos ceωpara nota¸c˜ao de conjuntos, isto ´e, c(V�) := �v∈V�c(v)eω(E�) := �e∈E�ω(e). O conjunto Γ(u) := {v:{u, v}∈E}denota os vizinhos do n´o u. O grau de um n´o ´e o n´umero de seus vizinhos. Δ denota o grau m´aximo de um grafo. O grau ponderado de um n´o ´e a CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 11 soma dos pesos das suas arestas incidentes. Um grafo ´e bipartido se seu conjunto de n´os puder ser dividido em dois conjuntos disjuntos UeVde tal modo que (u, v)∈E implica u∈Uev∈Vou vice-versa. Um subgrafo ´e um grafo cujo n´o e conjunto de arestas s˜ao subconjuntos de um outro grafo. Chamamos de induzido a um subgrafo que tem todas as arestas poss´ıveis. 2.2.1 Parti¸c˜oes e Agrupamentos (Clusterings) Dado um n´umero k∈N>1e um grafo n˜ao dirigido com pesos n˜ao negativos nas arestas, o problema de particionamento do grafo consiste em obter blocos de n´os V1, . . . , Vk (subgrafos) cuja uni˜ao ´e o conjunto de n´os V, Isto ´e, 1. V1∪···∪Vk=V 2. Vi∩Vj= 0 ∀i�=j Uma restri¸c˜ao de balanceamento exige que todos os blocos tenham tamanho aproximadamente igual. Mais precisamente,isto exige que, ∀ ∈ 1. . . k :|vi|≤Lmax := (1+ε)�|V|/k�para algum parˆametro de desbalanceamento ε∈R≥0, no caso em que a fun¸c˜ao de custo dos v´ertices ´e igual a um. No caso de ε= 0, tamb´em usamos o termo perfeitamente balanceado. Um bloco Vi´e dito com pouca carga se |Vi|< Lmax e sobrecarregado se |Vi|> Lmax. Um agrupamento ´e tamb´em um particionamento dos v´ertices do grafo, contudo knormalmente n˜ao ´e conhecido e a restri¸c˜ao de balanceamento n˜ao ´e levada em considera¸c˜ao. Note-se que um particionamento tamb´em ´e um agrupamento de um gr´afico. Em ambos os casos, o objetivo consiste em minimizar ou maximizar uma fun¸c˜ao objetivo em particular. Duas fun¸c˜oes bem conhecidas para o problema de particionamento ser˜ao apresentadas na pr´oxima subse¸c˜ao. Um n´o v∈Vi que tem um vizinho w∈Vj,i�=j´e um n´o fronteira. Uma aresta entre dois blocos ´e tamb´em chamada aresta de corte. O conjunto Eij := {{u, v}∈E:u∈Vi, v ∈Vj} ´e o conjunto de arestas de corte entre dois blocos VieVj. Uma vis˜ao abstrata do grafo particionado ´e o chamado grafo quociente, onde os n´os representam os blocos e CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 12 as arestas s˜ao induzidas por conectividade entre os blocos, ou seja, existe uma aresta no grafo quociente se existir uma aresta entre os blocos no grafo particionado original. Um exemplo ´e dado na Figura 2.3. Dados dois agrupamentos ξ1eξ2, o agrupamento sobreposi¸c˜ao (overlay clustering) ´e o agrupamento em que cada bloco corresponde a um componente conexo do grafo Gε= (V, E\ε) onde ε´e a uni˜ao das arestas do corte de ξ1eξ2, Ou seja, todas as arestas que ligam os blocos em ξ1ou ξ2. Figura 2.3: Um grafo dividido em trˆes blocos de tamanho quatro `a esquerda e o seu grafo quociente correspondente `a direita. Existe uma aresta no grafo quociente se houver uma aresta entre os blocos correspondentes no grafo original. (Figura retirada de [20]). 2.2.2 Fun¸c˜oes Objetivo Na pr´atica, muitas vezes procuramos encontrar uma parti¸c˜ao que minimiza (ou maximiza) um objetivo. Provavelmente, a fun¸c˜ao objetivo mais importante ´e minimizar o corte total: �i<j ω(Eij) Sabe-se que existem fun¸c˜oes objectivo mais realistas (e mais complicadas) que dependem da natureza do problema que est´a a ser resolvido, mas a fun¸c˜ao de minimiza¸c˜ao do tamanho do corte tem sido adotada como um tipo de padr˜ao, uma vez que ´e geralmente correlacionada com outras formula¸c˜oes. CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 13 2.2.3 Algoritmos de Particionamento em Grafos Na literatura, podemos encontrar uma quantidade de algoritmos de particionamento em grafos. Segundo v´arios autores, o algoritmo mais popular para o particionamento de grafos para execu¸c˜ao paralela ´e o de bisse¸c˜ao espectral recursiva (Recursive Spectral Bissection) [17, 21, 6]. Algoritmos de particionamento em grafos podem ser divididos em dois grandes grupos: os de melhoramento local e os de melhoramento global. Os primeiros utilizam m´etodos de otimiza¸c˜ao local partindo de uma bisse¸c˜ao do grafo enquanto os m´etodos de otimiza¸c˜ao global partem do grafo inteiro. Uma segunda classifica¸c˜ao de algoritmos de particionamento est´a relacionada com a forma como os grafos s˜ao particionados. Desta forma, existem os m´etodos geom´etricos, que fazem o particionamento a partir da geometria do grafo (coordenadas), os m´etodos livres de coordenadas (coordinate-free), que consideram o grau de conectividade do grafo e os m´etodos dinˆamicos (consideram que o grafo muda ao longo do tempo) [14]. Devido `a quantidade muito grande de algoritmos de particionamento, nesta se¸c˜ao vamos nos concentrar apenas em dois m´etodos. Os dois s˜ao livres de coordenadas: Recursive Spectral Bissection [17, 6] e um algoritmo baseado no corte m´ınimo de um grafo com pesos [23], que se encaixa numa categoria de algoritmos que usam procura gulosa (“greedy”) para decompor o grafo em grupos de v´ertices. Nos concentramos nos m´etodos livres de coordenadas porque estes fazem o particionamento levando em considera¸c˜ao a conectividade e a estrutura do grafo, gerando, desta forma, parti¸c˜oes em que se consegue minimizar a quantidade de arestas entre os grupos de v´ertices, o que resulta num particionamento mais adequado para execu¸c˜ao paralela, visto que a diminui¸c˜ao de arestas significa na pr´atica a redu¸c˜ao de comunica¸c˜ao. O problema de reduzir o n´umero de arestas entre grupos ´e o mesmo que encontrar o corte m´ınimo de um grafo [5]. Fontes muito boas de informa¸c˜ao sobre algoritmos de particionamento podem ser encontradas no survey de Fj¨allstr¨om [4], no livro de Padua [14] (chapter on Domain Decomposition) e no artigo de Arora, Rao and Vazirani [1]. Uma varia¸c˜ao destes algoritmos considera que as arestas tˆem custo diferente de um, CAP´ ITULO 2. FUNDAMENTAC¸ ˜ AO TE ´ ORICA 14 ou seja, tˆem um peso associado. Neste caso, define-se o peso de um v´ertice como sendo o somat´orio dos pesos de suas arestas incidentes. Os algoritmos de procura gulosa normalmente usam uma estrat´egia em largura combinada com heur´ısticas para decompor o grafo em grupos de v´ertices. As heur´ısticas s˜ao normalmente baseadas em pesos dos v´ertices ou pesos das arestas. Neste trabalho, utilizamos um algoritmo chamado Heavy Decomposition Max Aggregation. Nesta soluc˜ao, o algoritmo gera os grupos com base no seguinte m´etodo [8, 23]: 1. Verificar o n´o Nque tem mais peso em todo o grafo (soma dos pesos das arestas ´e m´aximo dentre todos os v´ertices). 2. Verificar todos os v´ertices ligados a Ne selecionar aquele (ou aqueles) que tem aresta de maior peso. Um novo grafo ´e gerado sem esta aresta e com um novo v´ertice que agrupa o v´ertice Ncom os que a ele se ligam com arestas de maior peso. Um exemplo ´e mostrado na Figura 2.4. Figura 2.4: Exemplo de Max Aggregation (retirado de [23]) Neste grafo, o n´o Nselecionado corresponde ao v´ertice A(a vermelho), porque este ´e o mais pesado do grafo, ou seja, a soma dos pesos das arestas ´e o maior do grafo. Assim, N=A. Em seguida ´e procurado o v´ertice de peso m´aximo (Pmax) CAP´ ITULO 3. UTILIZAC¸ ˜ AO DO M´ ETODO DE BISSEC¸ ˜ AO 21 Figura 3.3: Bisse¸c˜ao do grafo(retirado de [16]) 3.3 Implementa¸c˜ao Este algoritmo foi implementado na linguagem Python e est´a descriot no Algoritmo 1. O c´odigo fonte pode ser visto no Apˆendice A. Os parˆametros de entrada do algoritmo bissecao s˜ao a matriz Laplaciana Le o n´umero de v´ertices do grafo, n, que tamb´em ´e a ordem da matriz. Gerar novos grafos G1eG2, se o n´umero de v´ertices de G1ou G2for menor ou igual a 3, imprimir os n´os do grafo, caso contr´ario, gerar nova matriz e chamar a func˜ao recursivamente. O parˆametro mapa ´e utilizado para mapear os v´ertices do grafo original nos v´ertices do novo grafo j´a representado como a matriz laplaciana. Para os valores do vetor x� que tˆem valor igual a zero (vetor x tinha algum valor igual ao valor da mediana), agrupamos os v´ertices correspondentes num novo grafo G3e aplicamos a bisse¸c˜ao novamente a este novo grafo. CAP´ ITULO 3. UTILIZAC¸ ˜ AO DO M´ ETODO DE BISSEC¸ ˜ AO 22 bissecao(L,n,mapa);1 begin;2 Calcular o segundo vetor pr´oprio da matriz L;3 Calcular o vetor x=√nu2;4 Calcular a mediana m dos valores de x;5 Calcular o vetor x�, onde x� i=−1, se xi< m ou x� i= +1,se xi> m;6 Se houver valores iguais a m, formar um grupo;7 Conta quantos 1 e −1 e 0 est˜ao no vetor x�;8 if contaum ou contamenorum ou contazero ≤3then9 imprimir n´o do grafo10 end11 if contaum >3then12 gerar novamatriz G1com tamanho contaum,bissecao(G1,contaum,mapa)13 end14 if contamenorum >3then15 gerar novamatriz G2com tamanho contamenorum,16 bissecao(G2,contamenorum,mapa) end17 if contazero >3then18 gerar novamatriz G3com tamanho contazero,bissecao(G3,contazero,mapa)19 end20 end21 Algorithm 1:bissecao(L,n,mapa) Cap´ıtulo 4 Materiais e M´etodos Neste cap´ıtulo descrevemos os materiais e a metodologia utilizados neste trabalho. Comparamos a nossa implementa¸c˜ao do m´etodo de bisse¸c˜ao recursiva com um m´etodo de particionamento em grafos baseado na escolha de v´ertices com maior n´umero de arestas, cujo algoritmo foi apresentado na Se¸c˜ao 2.2.3 (Max Aggregation). Comparamos tamb´em os resultados dos dois algoritmos com o grafo original. As m´etricas de compara¸c˜ao s˜ao: •n´umero total de v´ertices do grafo original e n´umero total de v´ertices dos grafos particionados com os dois algoritmos, considerando cada grupo de v´ertices do grafo original numa parti¸c˜ao como sendo um ´unico v´ertice no grafo particionado; •n´umero total de arestas do grafo original e n´umero total de arestas dos grafos particionados; •densidade dos grafos. A densidade representa o percentual de conex˜ao entre os n´os. O c´alculo de densidade ´e realizado dividindo-se o n´umero de arestas epelo n´umero de arestas num grafo correspondente completo com nn´os (densidade = e [n∗(n−1)]/2). •grau m´edio dos v´ertices. 23 CAP´ ITULO 4. MATERIAIS E M ´ ETODOS 24 •n´umero de arestas no corte do grafo. A Tabela 4.1 apresenta as principais caracter´ısticas dos grafos usados nos experimentos. Nesta tabela, os grafos est˜ao organizados em trˆes diferentes grupos de acordo com a sua densidade. Os grupos foram gerados utilizando um algoritmo de agrupamento baseado no algoritmo k-means com k=3. O primeiro grupo (grafos 1-5) foi considerado pouco denso. O segundo grupo foi considerado como de densidade m´edia. O ´ultimo grupo (com apenas um grafo representativo, Grafo 10) ´e de alta densidade (grafo totalmente conexo). Os resultados s˜ao apresentados na forma gr´afica (produzidos com a ferramenta dot) e na forma de tabela comparando as m´etricas. Trˆes grafos s˜ao apresentados para cada experimento, o grafo original, o grafo obtido com o algoritmo Max Aggregation e a o grafo obtido com o algoritmo de bisse¸c˜ao espectral recursiva. A implementa¸c˜ao do m´etodo de Bisse¸c˜ao Recursiva Espectral foi feita em Python, vers˜ao 2.7. Para calcular os valores pr´oprios e vetores pr´oprios utilizamos a biblioteca sympy. Esta biblioteca tem uma vantagem sobre outras com o mesmo prop´osito (por exemplo, numpy escipy), porque faz o m´aximo poss´ıvel de c´alculos de forma alg´ebrica e somente no fim realiza c´alculos num´ericos, reduzindo, assim, a propaga¸c˜ao de erros. 4.1 Compara¸c˜ao entre os dois algoritmos O algoritmo de Max Aggregation tem apenas como finalidade ler da entrada um conjunto de dados num´ericos correspondentes aos v´ertices e arestas do grafo, verificar dependˆencias entre eles atrav´es do n´umero de vari´aveis em comum, gerar o grafo (fazer liga¸c˜oes entre os v´ertices lidos da entrada), come¸car o processo de gera¸c˜ao de grupos e coloc´a-los num ficheiro com um formato pr´e-definido, que pode servir de entrada a outro programa que ir´a fazer as opera¸c˜oes correspondentes a cada subconjunto de v´ertices. CAP´ ITULO 4. MATERIAIS E M ´ ETODOS 25 Tabela 4.1: Caracter´ısticas dos Grafos Originais Densidade Baixa Densidade M´edia Densidade Alta Grafo 1 2 3 4 5 6 7 8 9 10 V´ertices 4 6 14 4 5 4 5 5 9 4 N´umero de arestas 3 9 55 4 7 5 9 9 33 6 Densidade 0.5 0.6 0.60 0.66 0.7 0.83 0.9 0.9 0.91 1 Grau m´edio dos v´ertices 1.5 3 7.85 2 3.2 2.5 3.4 3.6 7.3 3 CAP´ ITULO 4. MATERIAIS E M ´ ETODOS 26 O algoritmo de bisse¸c˜ao espectral recursivo cria conjuntos balanceados e conexos, que produzem um particionamento visualmente mais agrad´avel, por´em n˜ao necessariamente melhor. O algoritmo de bisse¸c˜ao espectral tende a gerar o menor n´umero de arestas entre os subconjuntos. Utilizando o m´etodo de bisse¸c˜ao recursiva, quanto maior o n´umero de partes que queremos obter de um grafo, maior ´e o n´umero de vetores pr´oprios computados. Os algoritmos de bisse¸c˜ao apresentam alguns problemas. Por exemplo, eles n˜ao aceitam um corte inicial menos atrativo, que produziria, mais tarde, redes com cortes melhores. Ou seja, estes algoritmos n˜ao possuem lookahead. Em bisse¸c˜ao, a tarefa de dividir o grafo em conjuntos de v´ertices (decomposi¸c˜ao do problema) ´e separado da atribui¸c˜ao de v´ertices para um processador espec´ıfico (problema de atribui¸c˜ao). O overhead de comunica¸c˜ao em um programa depende da decomposi¸c˜ao e da atribui¸c˜ao. Consequentemente, ´e prefer´ıvel considerar estes aspectos do problema juntos. Por exemplo, poder´ıamos escolher dois conjuntos com maior volume de comunica¸c˜ao entre eles para coloc´a-los topologicamente juntos numa arquitetura. Cap´ıtulo 5 Resultados Os m´etodos usados neste trabalho foram Max Aggregation e Bisse¸c˜ao Recursiva Espectral. Os grafos foram divididos em 3 grupos: baixa densidade, densidade m´edia e alta densidade. Nas se¸c˜oes seguintes mostramos os resultados do particionamento de cada um dos m´etodos e comparamos. Procuramos tamb´em estabelecer se algum m´etodo ´e adequado para algum dos grupos de grafos. As figuras relativas aos grafos 1 a 5 (Figuras 5.1 a 5.5) correspondem aos grafos de baixa densidade. As Figuras 5.6 a 5.9 correspondem aos grafos de densidade m´edia. A Figura 5.10 corresponde a um grafo de densidade alta. Cada uma destas figuras mostra o grafo original e os dois grafos particionados com o m´etodo Max Aggregation e com o m´etodo de Bisse¸c˜ao Recursiva Espectral. O grafo original representa um CSP sint´etico, onde cada v´ertice corresponde a uma restri¸c˜ao e cada aresta corresponde `as vari´aveis que conectam um par de restri¸c˜oes. No grafo particionado, cada subgrafo corresponde a um subconjunto de restri¸c˜oes. As arestas entre os subgrafos (blocos) correspondem `as vari´aveis comuns aos conjuntos de restri¸c˜oes de cada bloco. O algoritmo Max Aggregation leva em considera¸c˜ao que o peso entre as arestas ´e o n´umero de vari´aveis comuns entre blocos. O algoritmo de bisse¸c˜ao espectral assume que o peso entre os v´ertices ´e igual a um. A Tabela 5.1 mostra um resumo das caracter´ısticas dos grafos original e particiona27 CAP´ ITULO 5. RESULTADOS 28 dos em rela¸c˜ao ao n´umero de v´ertices, n´umero de arestas, densidade e grau m´edio de cada v´ertice. Apresentamos ainda um resumo das diferen¸cas entre os dois algoritmos para cada m´etrica usada na avalia¸c˜ao. Estes resultados s˜ao mostrados nas tabelas 5.2 a 5.5, onde um sinal de “-” indica uma redu¸c˜ao, um sinal de “+” indica um aumento e um sinal de “=” indica que n˜ao houve altera¸c˜ao de particionamento de um grafo para o outro. Original →MA significa a diferen¸ca do grafo original para o grafo particionado com o m´etodo Max Aggregation. Original →RB significa a diferen¸ca do grafo original para o grafo particionado com o m´etodo de bisse¸c˜ao espectral recursiva. MA →RB significa a diferen¸ca do m´etodo Max Aggregation para o m´etodo da Bisse¸c˜ao Recursiva. 5.1 Grupo de grafos com densidade baixa No grupo de densidade baixa, ambos os particionamentos s˜ao equivalentes para o Grafo1, apenas havendo uma troca de v´ertices (2 com 4 nas Figuras 5.1b e 5.1c). O Grafo2 pˆode ser particionado com o m´etodo Max Aggregation, mas o m´etodo de Bisse¸c˜ao Recursiva Espectral n˜ao produziu solu¸c˜ao devido a um problema no ambiente de execu¸c˜ao Python (a vers˜ao utilizada foi a 2.7). Uma das fun¸c˜oes da biblioteca sympy ´e fazer o m´aximo poss´ıvel de processamento alg´ebrico, apenas fazendo c´alculos num´ericos no final. Para este grafo em particular, quando a biblioteca recebe uma matriz com valores alg´ebricos para remover espa¸cos nulos (parte do “parser” da biblioteca, m´etodo nullspaces), o interpretador perde-se na computa¸c˜ao. O m´etodo para remo¸c˜ao de espa¸cos nulos de uma matriz alg´ebrica funciona bem quando n˜ao ´e chamado no contexto do programa. Fizemos um teste com um pequeno programa que passa como parˆametro para o m´etodo nullspaces uma matriz alg´ebrica e o interpretador n˜ao retorna resultados no programa, mas retorna resultados se a mesma chamada for feita no “prompt” do interpretador. Se a matriz tiver apenas valores num´ericos, a biblioteca comporta-se bem. CAP´ ITULO 5. RESULTADOS 29 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.1: Grafo1 O particionamento do Grafo3 (Figura 5.3), utilizando o m´etodo de bisse¸c˜ao espectral recursiva, gerou um grupo para cada v´ertice, o que n˜ao muda as caracter´ısticas do grafo original. J´a o m´etodo de Max Aggregation conseguiu dois grupos de dois v´ertices, o que representa uma melhora modesta no n´umero de arestas do grafo particionado em rela¸c˜ao ao grafo original. Para o Grafo4 (Figura 5.4), notamos que o Max Aggregation faz uma escolha de parti¸c˜oes que possui um n´umero de arestas entre grupos (n´umero de arestas do corte) maior do que o n´umero de arestas produzido pelo m´etodo de bisse¸c˜ao espectral recursiva. O n´umero de grupos tamb´em ´e menor para este ´ultimo m´etodo, indicando a necessidade de menor n´umero de processadores para a execu¸c˜ao das restri¸c˜oes do grafo. Na pr´atica, pode haver a necessidade de se adicionar mais processadores, portanto este m´etodo est´a sendo conservador para este grafo. Os particionamentos obtidos para o Grafo5 (Figura 5.5) s˜ao equivalentes, havendo apenas uma troca dos v´ertices (2,3) com (4,5) no grupo com maior n´umero de v´ertices. Como n˜ao estamos levando em considera¸c˜ao a quantidade de processamento por v´ertice, estes particionamentos podem fazer diferen¸ca na pr´atica. 5.2 Grupo de grafos com densidade m´edia No grupo de densidade m´edia, o Grafo6 (Figura 5.6) teve diferentes particionamentos com Max Aggregation e com bisse¸c˜ao espectral recursiva. Se levarmos em conside- CAP´ ITULO 5. RESULTADOS 30 (a) Original (b) Max Aggregation Figura 5.2: Grafo2 ra¸c˜ao o n´umero de arestas do grafo particionado, Max Aggregation fez um melhor particionamento, onde apenas dois processadores seriam necess´arios com uma troca de mensagens menos pesada (3 arestas) do que a troca de mensagens requerida pelos trˆes subgrafos gerados pelo m´etodo de bisse¸c˜ao recursiva espectral. No Grafo7 (Figura 5.7), apesar dos grupos de v´ertices obtidos por Max Aggregation estarem mais bem balanceados do que os grupos gerados pela bisse¸c˜ao espectral, o n´umero de arestas entre os grupos ´e maior do que no grafo obtido com a bisse¸c˜ao espectral. Na pr´atica isto poderia indicar um menor n´umero de comunica¸c˜oes entre os grupos. O Grafo8 (Figura 5.8) teve particionamentos equivalentes usando ambos os m´etodos, apenas com uma troca dos v´ertices 2 e 4 pelos grupos. O Grafo9 (Figura 5.9) foi particionado em quatro subgrupos com Max Aggregation e em seis subgrupos com bisse¸c˜ao recursiva. Embora o m´etodo de bisse¸c˜ao recursiva tenha um n´umero de arestas maior cruzando os grupos, este particionamento, na pr´atica, pode ser vantajoso do ponto de vista da execu¸c˜ao paralela, visto que trocas de mensagens atrav´es de arestas em grupos n˜ao relacionados podem ser efetuadas simultaneamente. Al´em disto, esta solu¸c˜ao ´e mais flex´ıvel porque permite a utiliza¸c˜ao de um maior n´umero de processadores do que a solu¸c˜ao produzida pelo Max Aggregation. CAP´ ITULO 5. RESULTADOS 37 Tabela 5.5: Grau m´edio dos v´ertices Densidade Baixa Densidade M´edia Densidade Alta Grafo 1 2 3 4 5 6 7 8 9 10 Grau m´edio dos v´ertices Grafo original 1.5 3 7.85 2 3.2 2.5 3.4 3.6 7.33 3 Max Aggregation(MA) 1.33 3.5 8.83 2 4 3 4.33 4 14.25 3 Recursive Bisection(RB) 1.33 7.85 2 4 2.33 4 4 10.66 3.33 Compara¸c˜ao Original →MA - + + = + + + + + = Original →RB - = = + - + + + + MA →RB = - = = - - = - + CAP´ ITULO 5. RESULTADOS 38 (a) original (b) Max Aggregation (c) Recursive Bisection Figura 5.3: Grafo3 CAP´ ITULO 5. RESULTADOS 39 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.4: Grafo4 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.5: Grafo5 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.6: Grafo6 CAP´ ITULO 5. RESULTADOS 40 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.7: Grafo7 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.8: Grafo8 CAP´ ITULO 5. RESULTADOS 41 (a) original (b) Max Aggregation (c) Recursive Bisection Figura 5.9: Grafo9 CAP´ ITULO 5. RESULTADOS 42 (a) Original (b) Max Aggregation (c) Recursive Bisection Figura 5.10: Grafo10 Cap´ıtulo 6 Conclus˜oes e Trabalhos Futuros Neste trabalho implementamos um algoritmo de particionamento de grafos baseado em bisse¸c˜ao espectral recursiva com o objetivo de dividir um CSP em subproblemas t˜ao independentes quanto poss´ıvel para posteriormente executar os diferentes subproblemas em diferentes processadores. Dos v´arios m´etodos dispon´ıveis para particionamento de grafos, os m´etodos espectrais s˜ao os mais vantajosos porque levam em considera¸c˜ao a conectividade dos grafos, o que ´e importante para execu¸c˜ao paralela, onde subgrupos de v´ertices representam computa¸c˜oes e arestas representam comunica¸c˜oes. Testamos 10 grafos com caracter´ısticas diferentes e comparamos os resultados da bisse¸c˜ao espectral recursiva com um m´etodo baseado em corte m´ınimo em grafos (“min-cut”), chamado Max Aggregation. Resultados foram avaliados quanto ao n´umero de v´ertices, n´umero de arestas, densidade e grau m´edio dos v´ertices. O algoritmo de Max Aggregation tende a ser mais conservador do que o algoritmo de bisse¸c˜ao espectral. Este tem a tendˆencia de ser mais agressivo no particionamento gerando um n´umero maior de grupos no grafo particionado do que o n´umero de grupos gerado pelo Max Aggregation. Na pr´atica, este n´umero maior de grupos pode ser ben´efico j´a que poder´a haver um grande n´umero de processadores dispon´ıveis. Neste trabalho, o m´etodo de bisse¸c˜ao espectral n˜ao leva em considera¸c˜ao que o grafo 43 CAP´ ITULO 6. CONCLUS ˜ OES E TRABALHOS FUTUROS 44 pode ter pesos nas arestas (quantidade de comunica¸c˜ao). Seria interessante modelar este tipo de grafo na matriz laplaciana e verificar os resultados de particionamento. Tamb´em seria interessante produzir particionamentos para grafos maiores (centenas ou milhares de v´ertices) e testar estes particionamentos num sistema paralelo de execu¸c˜ao de restri¸c˜oes. Tal sistema existe, mas no contexto deste trabalho, n˜ao foi poss´ıvel fazer estas experiˆencias. Apˆendice A C´odigo fonte import sympy as sp import math # o numero de vertices do grafo n=6 #matriz_original = [2,-1,0,-1,-1,3,-1,-1,0,-1,1,0,-1,-1,0,2] #input_simples1 """ matriz_original = [ 3, -1, -1, -1, -1, 1, 0, 0, -1, 0, 1, 0, -1, 0, 0, 1] """ #input_simple2 matriz_original = [ 5, -1, -1, -1, -1, -1, -1, 3, -1, -1, 0, 0, -1, -1, 4, 0, -1, -1, -1, -1, 0, 2, 0, 0, -1, 0, -1, 0, 2, 0, -1, 0, -1, 0, 0, 2 ] """ matriz_original = [ -5, 1, 1, 1, 1, 1, 1, -3, 1, 1, 0, 0, 1, 1, -4, 0, 1, 1, 1, 1, 0, -2, 0, 0, 1, 0, 1, 0, -2, 0, 1, 0, 1, 0, 0, -2 ] """ #input_simples3 """ matriz_original=[ # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 13, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, -1, -1, -1, -1, -1, -1, -1, 0, 0, -1, 0, 0, 45 APˆ ENDICE A. C ´ ODIGO FONTE 46 -1, -1, 10, -1, -1, -1, -1, -1, -1, 0, 0, -1, 0, -1, -1, -1, -1, 8, -1, -1, 0, -1, -1, 0, 0, -1, 0, 0, -1, -1, -1, -1, 9, -1, -1, -1, -1, 0, 0, -1, 0, 0, -1, -1, -1, -1, -1, 9, 0, -1, -1, 0, 0, -1, 0, -1, -1, -1, -1, 0, -1, 0, 6, 0, -1, 0, 0, -1, 0, 0, -1, -1, -1, -1, -1, -1, 0, 10, -1, -1, 0, -1, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, 9, 0, 0, -1, 0, 0, -1, 0, 0, 0, 0, 0, 0, -1, 0, 5, -1, -1, -1, 0, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 3, -1, 0, 0, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, -1, 12, 0, -1, -1, 0, 0, 0, 0, 0, 0, 0, 0, -1, 0, 0, 2, 0, -1, 0, -1, 0, 0, -1, 0, -1, 0, 0, 0, -1, 0, 5] """ """ matriz_original=[ # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 -13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -9, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1,-10, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, -8, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, -9, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, -9, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, -6, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,-10, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, -9, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, -5, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -3, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-12, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, -5] """ #input_simples4 """ matriz_original = [ 3, -1, -1, -1, -1, 2, 0, -1, -1, 0, 1, 0, -1, -1, 0, 2] """ #input_simple5 """ matriz_original=[ 4, -1, -1, -1, -1, -1, 3, 0, -1, -1, -1, 0, 3, -1, -1, -1, -1, -1, 3, 0, -1, -1, -1, 0, 3] """ #input_simple 6 """ matriz_original=[ 3, -1, -1, -1, -1, 2, 0, -1, -1, 0, 2, -1, -1, -1, -1, 3 ] """ #input_simples7 """ matriz_original = [ 4, -1, -1, -1, -1, -1, 3, -1, -1, 0, APˆ ENDICE A. C ´ ODIGO FONTE 53 for j in range(0,n): if(matriz[i][j]==1): soma+=(v[i]-v[j])**2 f=soma/n print "O numero de arestas que existe entre os conjuntos e:",f mapa=[0]*(n) for i in range(0,n): mapa[i]=i+1 func_bissecao(matriz_original,n,mapa) #func_arestas(matriz_original,n,matriz) Apˆendice B Resultados de Execu¸c˜ao B.0.1 Grafo 1 matriz_original = [ 3, -1, -1, -1, -1, 1, 0, 0, -1, 0, 1, 0, -1, 0, 0, 1] o vector indicador: [0, -2.00000000000000, 2.00000000000000, 0] media = 0 Solucoes : [0, -1, 1, 0] B.0.2 Grafo 2 matriz_original = [ 5, -1, -1, -1, -1, -1, -1, 3, -1, -1, 0, 0, -1, -1, 4, 0, -1, -1, -1, -1, 0, 2, 0, 0, -1, 0, -1, 0, 2, 0, -1, 0, -1, 0, 0, 2 ] N~ao foi possivel testar, eata entra um ciclo finito. B.0.3 Grafo 3 matriz_original=[ # 1 2 3 4 5 6 7 8 9 10 11 12 13 14 -13, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, -9, 1, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1,-10, 1, 1, 1, 1, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, -8, 1, 1, 0, 1, 1, 0, 0, 1, 0, 0, 54 APˆ ENDICE B. RESULTADOS DE EXECUC¸ ˜ AO 55 1, 1, 1, 1, -9, 1, 1, 1, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, -9, 0, 1, 1, 0, 0, 1, 0, 1, 1, 1, 1, 0, 1, 0, -6, 0, 1, 0, 0, 1, 0, 0, 1, 1, 1, 1, 1, 1, 0,-10, 1, 1, 0, 1, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, -9, 0, 0, 1, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1, 0, -5, 1, 1, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, -3, 1, 0, 0, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 1,-12, 0, 1, 1, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 0, -2, 0, 1, 0, 1, 0, 0, 1, 0, 1, 0, 0, 0, 1, 0, -5] o vector indicador: [-48.6415460280612, 3.74165738677394, \ 3.74165738677394, 3.74165738677394, 3.74165738677394, \ 3.74165738677394, 3.74165738677394, 3.74165738677394, \ 3.74165738677394, 3.74165738677394, 3.74165738677394, \ 3.74165738677394, 3.74165738677394, 3.74165738677394] media = 3.74165738677394 Solucoes : [-1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [3.60555127546399, 0, 0, 0, 0, 0, 0, \ 0, 0, 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [3.46410161513775, 0, 0, 0, 0, 0, 0, \ 0, 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [3.31662479035540, 0, 0, 0, 0, 0, 0, \ 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [3.16227766016838, 0, 0, 0, 0, 0, 0, \ 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [3.00000000000000, 0, 0, 0, 0, 0, 0, \ 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [2.82842712474619, 0, 0, 0, 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [2.64575131106459, 0, 0, 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0, 0] o vector indicador: [2.44948974278318, 0, 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0, 0] o vector indicador: [2.23606797749979, 0, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0, 0] APˆ ENDICE B. RESULTADOS DE EXECUC¸ ˜ AO 56 o vector indicador: [2.00000000000000, 0, 0, 0] media = 0 Solucoes : [1, 0, 0, 0] B.0.4 Grafo 4 matriz_original = [ 3, -1, -1, -1, -1, 2, 0, -1, -1, 0, 1, 0, -1, -1, 0, 2] o vector indicador: [0, 2.00000000000000, -4.00000000000000, \ 2.00000000000000] media = 1.00000000000000 Solucoes : [-1, 1, -1, 1] B.0.5 Grafo 5 matriz_original=[ 4, -1, -1, -1, -1, -1, 3, 0, -1, -1, -1, 0, 3, -1, -1, -1, -1, -1, 3, 0, -1, -1, -1, 0, 3] o vector indicador: [0, -2.23606797749979, 2.23606797749979, \ 0, 0] media = 0 Solucoes : [0, -1, 1, 0, 0] B.0.6 Grafo 6 matriz_original=[ 3, -1, -1, -1, -1, 2, 0, -1, -1, 0, 2, -1, -1, -1, -1, 3 ] o vector indicador: [0, -2.00000000000000, 2.00000000000000, 0] media = 0 Solucoes : [0, -1, 1, 0] B.0.7 Grafo 7 matriz_original = [ 4, -1, -1, -1, -1, -1, 3, -1, -1, 0, APˆ ENDICE B. RESULTADOS DE EXECUC¸ ˜ AO 57 -1, -1, 4, -1, -1, -1, -1, -1, 4, -1, -1, 0, -1, -1, 3] o vector indicador: [0, -2.23606797749979, 0, 0, 2.23606797749979] media = 0 Solucoes : [0, -1, 0, 0, 1] B.0.8 Grafo 8 matriz_original=[ 4, -1, -1, -1, -1, -1, 3, -1, 0, -1, -1, -1, 4, -1, -1, -1, 0, -1, 3, -1, -1, -1, -1, -1, 4] o vector indicador: [0, -2.23606797749979, 0, 2.23606797749979, 0] media = 0 Solucoes : [0, -1, 0, 1, 0] B.0.9 Grafo 9 matriz_original=[ 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, -1, -1, 0, -1, -1, -1, -1, -1, -1, 8, -1, -1, -1, -1, -1, -1, -1, -1, -1, 7, 0, -1, -1, -1, -1, -1, 0, -1, 0, 5, 0, -1, -1, -1, -1, -1, -1, -1, 0, 7, -1, -1, -1, -1, -1, -1, -1, -1, -1, 8] o vector indicador: [-3.00000000000000, 3.00000000000000, 0, \ 0, 0, 0, 0, 0, 0] media = 0 Solucoes : [-1, 1, 0, 0, 0, 0, 0, 0, 0] o vector indicador: [-2.64575131106459, 0, 2.64575131106459, \ 0, 0, 0, 0] media = 0 Solucoes : [-1, 0, 1, 0, 0, 0, 0] o vector indicador: [2.23606797749979, 2.23606797749979, \ -6.70820393249937, 2.23606797749979, 0] media = 2.23606797749979 Solucoes : [0, 0, -1, 0, -1] APˆ ENDICE B. RESULTADOS DE EXECUC¸ ˜ AO 58 B.0.10 Grafo 10 matriz_original=[ 3, -1, -1, -1, -1, 3, -1, -1, -1, -1, 3, -1, -1, -1, -1, 3] o vector indicador: [-2.00000000000000, 2.00000000000000, 0, 0] media = 0 Solucoes : [-1, 1, 0, 0] Referˆencias [1] Sanjeev Arora, Satish Rao, and Umesh Vazirani. Geometry, flows, and graphpartitioning algorithms. Commun. ACM, 51(10):96–105, October 2008. [2] C. Bessiere. Arc-consistency and Arc-consistency Again. Artificial Intelligence, 65:179–190, 1994. [3] C. Bessiere and E. C. Freuder. Using Constraint Metaknowledge to Reduce Arcconsistency Computation. Artificial Intelligence, 107(1):125–148, January 1999. [4] Per-Olof Fj¨allstr¨om. Algorithms for graph partitioning: a survey. Link¨oping Electronic Articles in Computer and Information Science, 3(10), 1998. [5] R. Gomory and T. Hu. Multi-terminal network flows. Journal of the Society for Industrial and Applied Mathematics, 9(4):551–570, 1961. [6] B. Hendrickson and R. Leland. Multidimensional Spectral Load Balancing. In Proceeding of 6th SIAM Conf. Parallel Proc. Sci. Comput., Sandia National Laboratories, pages 953–961, January 1993. [7] P. V. Hentenryck, Y. Deville, and C. Teng. A Generic Arc-consistency Algorithm and its Specializations. Artificial Intelligence, 57:291–321, 1992. [8] Karin Hogstedt, Doug Kimelman, V T Rajan, Tova Roth, and Mark Wegman. Graph cutting algorithms for distributed applications partitioning. SIGMETRICS Perform. Eval. Rev., 28(4):27–29, March 2001. [9] B.W. Kernighan and S. Lin. An Efficient Heuristic Procedure for Partitioning Graphs. The Bell Systems Technical Journal, 49(2), 1970. [10] V. Kumar. Algorithms for Constraint Satisfaction Problems: A Survey. Artificial Intelligence Magazine, 13(1):32–44, 1992. [11] A. K. Mackworth. Consistency in Networks of Relations. Artificial Intelligence, 8(1):99–118, 1977. [12] K. Marriot and P. J. Stuckey. Programming with constraints: An Introduction. MIT Press, 1998. [13] R. Mohr and T. C. Henderson. Arc and Path Consistency Revisited. Artificial Intelligence, 28(2):225–233, 1986. 59 REFERˆ ENCIAS 60 [14] D. Padua. Encyclopedia of Parallel Computing, volume 4 of Springer reference. Springer, 2011. [15] M. R. Pereira. Paraleliza¸c˜ao de Algoritmos de Consistˆencia de Arcos em um Cluster de PC´s. Disserta¸c˜ao de mestrado, COPPE - Engenharia de Sistemas e Computa¸c˜ao - Universidade Federal do Rio de Janeiro, Rio de Janeiro, Agosto 2001. [16] Marluce Rodrigues Pereira. Particionamento Autom´atico de Restri¸c˜oes. PhD thesis, Department of Systems and Computer Engineering, Federal University of Rio de Janeiro, Mar¸co 2006. [17] Alex Pothen, Horst D. Simon, and Kan-Pu Liou. Partitioning sparse matrices with eigenvectors of graphs. SIAM J. Matrix Anal. Appl., 11(3):430–452, May 1990. [18] Rina Dechter. Constraint Processing. Morgan Kaufmann, Maio 2003. [19] A. Ruiz-Andino, L. Araujo, F. S´aenz, and J. Ruz. Parallel Execution Models for Constraint Programming over Finite Domains. In Gopalan Nadathur, editor, Principles and Practice of Declarative Programming, Intl. Conf. PPDP, Paris, France, volume 1702 of Lecture Notes in Computer Science, pages 134–151. Springer, September 29–October 1 1999. [20] Christian Schulz. High Quality Graph Partitioning. PhD thesis, Faculty of Computer Science, Karlsruhe Institute of Technology, Jul 2013. [21] H.D. Simon. Partitioning of unstructured problems for parallel processing. Computing Systems in Engineering, 2(2–3):135 – 148, 1991. ¡ce:title¿Parallel Methods on Large-scale Structural Analysis and Physics Applications¡/ce:title¿. [22] G. R. Spendley, G. R. Hext, and F. R. Himsworth. Sequential Application of Simplex Designs in Optimization and Evolutionary Operation. Technometrics, 4:441–461, 1962. [23] F´abio Tavares. Particionamento e execu¸c˜ao paralela de redes de restri¸c˜oes. Technical report, University of Porto, Setembro 2008.