Trilhas, Otimização de Concorrência e Inicialização Probabilística em Sistemas Sob Reversão de Arestas
Autores
|
4579 |
414,131,632
|
|
|
4580 |
414,131,632
|
|
|
4581 |
414,131,632
|
Informações:
Publicações do PESC
O Escalonamento por Reversão de Arestas (ERA) é um algoritmo de escalonamento para sistemas distribuídos com compartilhamento de recursos em alta carga. Este trabalho prova que os problemas de decisão relacionados à maximização e à minimização da concorrência do ERA são NP-completos para grafos com grau máximo menor ou igual a 4 e para grafos cúbicos planares, respectivamente. Também é provado que o problema de minimização do inverso da concorrência não é aproximável, se P é diferente de NP, por um fator igual ao do problema de coloração. Com o conceito de trilha, é provado que os ciclos principais determinam o máximo e o mínimo intervalo inoperante, além de outros atributos da execução do ERA. Sobre os algoritmos probabilísticos de inicialização do ERA, prova-se que Alg-Cor tem convergência sub-exponencial, para grafos completos, e linear, quando usa-se o número de faces do dado igual ao número de nós do grafo. Para Alg-Arestas, são analisadas expressões para P[T(m)>=u(m)+w] e P[T(m)=w], onde T(m) é o tempo de convergência do algoritmo em um grafo de m arestas, w é um inteiro positivo qualquer e u(m) é o tempo esperado de convergência do algoritmo.
Scheduling by Edges Reversal (SER) is a scheduling algorithm for distributed systems with heavy loaded resource sharing. This work proves that the decision problems associated to the maximization and minimization of SR concurrency are NP-complete for graphs with maximum degree <= 4 and for cubic and planar graphs, respectively. It also proves the non-approximability in a factor less than n^(1/7 - E), if P <> NP, of the inverse of concurrency minimization problem. Using track concept, it's also proven that the critic cycles determine maximum and minimum non-operation interval, besides other properties of ERA excecution. About the probalistic ERA initialization algorithms, it's proven that Alg-Cor has sub-exponential convergence for complet graphs and linear convergence when f = n faces dies are used. For Alg-Arestas, expressions for P[T(m) >= log f m + 1 + w] and P{t(m) = w], where T(m) is the convergence of the algorithm with m edges, are analysed and w > 0.