Universidade Federal de Ouro Preto
Instituto de Ciências Exatas e Biológicas
Departamento de Computação
COM272 – Inteligência Computacional
Alocação de processos a
computadores em uma rede em
anel lógico utilizando
Busca Tabu
Eduardo Magno Lages Figueiredo
< [email protected] >
Sibele Esteves Ramos
< [email protected] >
Introdução
Apresenta-se neste documento um algoritmo que implementa a busca
por uma boa solução a problemas combinatórios (np-difíceis).
O problema consiste na alocação de um conjunto de processos a um
conjunto de computadores.
Dois requisitos devem ser satisfeitos:
• Não sobrecarregar de nenhum computador com excesso de
processos alocados;
• A taxa de utilização da rede deve ser uniformemente distribuída
entre todos os computadores
Descrição do Problema
Este problema descreve um sistema computacional composto de
computadores (PC) interligados fisicamente através de um
barramento comum.
PC1
PC2
PC3
PC4
Como o meio de transmissão é único, apenas um dos computadores
poderá enviar ou receber mensagens por vez.
Descrição do Problema
Uma solução para evitar colisão de mensagens enviadas por
diferentes computadores é admitir que cada computador tenha seu
momento de utilização da rede.
PC1
Desta forma, foi implementada
logicamente uma topologia em
anel onde cada computador tem
um tempo (t) para transmissão.
PC4
PC2
PC3
Descrição do Problema
São consideradas para o problema, as características de cada máquina
que compõe o sistema computacional.
Para simplificar o problema, consideraremos apenas o desempenho
medido em Milhões de Instruções por Segundo (MIPS), de cada um
dos computadores.
90 MIPS
50 MIPS
30 MIPS
10 MIPS
Descrição do Problema
Temos um conjunto de processos (job) que devem ser alocados aos
computadores.
Cada um destes processos consome uma quantidade (w) de recursos
da máquina a qual for alocado. ( w medido em MIPS )
Os processos possuem ainda uma taxa de utilização da rede (lan)
medido em Megabits por segundo (Mb/s)
Quando o processo for alocado a um computador, este terá uma taxa
de utilização da rede definida pela lan de processo.
Descrição do Problema
P
C
1
P
C
3
TX
10
Lan
0
TX
50
Lan
0
P
C
2
P
C
4
JobA (10, 7)
JobB (20, 12)
JobC (10, 12)
JobE (10, 16)
JobF (30, 5)
JobG (30, 20)
TX
30
Lan
0
TX
90
Lan
0
JobD (15, 10)
Descrição do Problema
P
C
1
JobA (10, 7)
P
C
3
JobE (10, 16)
TX
0
Lan
7
TX
50
Lan
0
P
C
2
P
C
4
JobB (20, 12)
JobC (10, 12)
JobF (30, 5)
JobG (30, 20)
TX
30
Lan
0
TX
90
Lan
0
JobD (15, 10)
Descrição do Problema
P
C
1
JobA (10, 7)
P
C
3
TX
0
Lan
7
TX
50
Lan
0
P
C
2
JobB (20, 12)
JobC (10, 12)
P
C
4
TX
0
Lan
24
TX
90
Lan
0
JobD (15, 10)
JobE (10, 16)
JobF (30, 5)
JobG (30, 20)
Descrição do Problema
P
C
1
P
C
3
JobA (10, 7)
TX
0
JobD (15, 10)
Lan
7
TX
25
JobE (10, 16)
Lan
26
JobF (30, 5)
P
C
2
JobB (20, 12)
JobC (10, 12)
P
C
4
JobG (30, 20)
TX
0
Lan
24
TX
90
Lan
0
Descrição do Problema
P
C
1
P
C
3
JobA (10, 7)
TX
0
JobD (15, 10)
Lan
7
TX
25
JobE (10, 16)
Lan
26
P
C
2
JobB (20, 12)
P
C
4
JobF (30, 5)
JobC (10, 12)
JobG (30, 20)
Será que esta é a melhor solução ???
TX
0
Lan
24
TX
30
Lan
25
Redução ao problema da mochila
Cada processo (job) é um objeto;
Cada computador (PC) é uma mochila;
Os objetos possuem um peso (w) que é o consumo de recursos
computacionais e um benefício (lan) que é a taxa de utilização da
rede.
As mochilas possuem uma capacidade que é o desempenho do
computador.
Redução ao problema da mochila
Neste problema, não há apenas uma mochila. ( cada PC é uma );
Todos os objetos (jobs) devem ser alocados a alguma das mochilas;
Neste problema o objetivo não é conseguir o maior benefício
possível, e sim distribuir de forma o mais igualitária possível os
benefícios entre as mochilas.
Modelagem Matemática
Uma solução é um array de inteiros com n posições, onde n é o
numero de processos (job);
Cada posição representa um processo e o conteúdo da posição diz a
qual computador este processo está alocado;
Uma solução: s [1 – 2 – 2 – 3 – 3 – 4 – 4];
Um movimento um optimal (1-opt) é alocar um processo a outro
computador;
Um vizinho da solução s: s’ [2 – 2 – 2 – 3 – 3 – 4 – 4].
Modelagem Matemática
O cálculo de f(s) para este problema é dividido em duas partes:
f(s) =  f1(m) + f2(s)
0
f1(m) = MEDIAPENAL
MAXPENAL
se soma de pesos <= capacidade PC (w)
se w < soma de pesos <= 1,5 * w
se soma de pesos > 1,5 * w
f2(s) = maxLan – minLan
MAXPENAL e MEDIAPENAL são parâmetros do problema;
maxLan é o valor de lan do computador que possui maior acesso à
rede e minLan o que possui o menor acesso.
Dados do Algoritmo
Solução Inicial:
1
2
3
4
5
6
7
8
9
Tamanho
Lista Tabu
10
50
50
50
50
50
30
60
100
Função objetivo = 481
Iteração s/
Melhora
20
20
30
200
1000
2000
5000
5000
10000
Função
Objetivo
268
176
161
158
133
132
138
120
120
Total de
Iterações
49
52
95
335
2206
4228
5589
11832
16710
Dados do Algoritmo
Tamanho da lista tabu
50
No de iterações s/ melhora
1000
Média da Função Objetivo
123
Desvio
16,04 %
1
2
3
4
5
6
7
8
9
10
Função
Objetivo
120
122
117
132
118
138
119
124
134
106
Total de
Iterações
1147
1342
2148
3147
2049
1789
1627
1457
2529
2580
Conclusão
O algoritmo não é muito robusto porque as soluções iniciais são
geradas de forma aleatória e a Busca Tabu é fortemente dependente
da solução inicial;
Melhorias propostas ao algoritmo:
 Utilização de uma lista tabu de tamanho dinâmico;
 Utilização de um algoritmo para gerar uma melhor solução inicial;
Fevereiro / 2003