IX ELAVIO
FABIANA SIMÕES E SILVA
ORIENTADORA: VITÓRIA PUREZA
DEPTO. DE ENGENHARIA DE PRODUÇÃO
UNIVERSIDADE FEDERAL DE SÃO CARLOS
SÃO CARLOS - SP- BRASIL
* APOIO PARCIAL: FAPESP
DESIGNAÇÃO DE TAREFAS EM
APLICAÇÕES DE MULTIPROCESSADORES
DE PROCESSAMENTO DE SINAL DIGITAL
UTILIZANDO ALGORITMOS GENÉTICOS
2
O PROBLEMA DE DESIGNAÇÃO DE TAREFAS EM
AMBIENTES PARALELOS
 A melhor designação de tarefas depende da
aplicação.
 Objetivo: Obter a designação com o menor atraso
total.
 Atraso Total: Tempo transcorrido entre o
surgimento do sinal na porta de entrada e a
produção de um sinal processado na porta de
saída.
 O cálculo do atraso total requer a escolha de uma
arquitetura de multiprocessadores.
3
ARQUITETURA RDAD
INPUT
OUTPUT
Processador
1
Processador
Mestre (0)
Processador
2
Processador
N
 O envio de sinal é sincronizado.
 Tempos de comunicação interprocessadores:



0 ciclo: Proc(suc)=Proc(pred).
1 ciclo: Proc(suc)=Proc(pred) + 1 ou Proc(suc)=0 ou
Proc(pred)=0.
2 ciclos: outros.
4
DIAGRAMA DE TAREFAS
4
70, 50, 50
2
70, 80, 40
8
50, 50, 40
5
40, 30, 50
INPUT
1
50, 50, 50
10
50, 50, 50
6
30, 10, 10
3
20, 30, 10
OUTPUT
9
10, 20, 20
7
20, 10, 10
5
CÁLCULO DO ATRASO
2
2
4
4
1
4
2
1
I
2
2
1
1
34
1
1
1
6
0
3
8
1
0
2
O
0
7
2
1
1
9
1
6 ciclos
10
2
0
5
0
5
0
3
2
0
Dada uma designação de tarefas, há um caminho crítico
(atraso)  obter a designação com o caminho crítico mais
curto.
6
ALGORITMO DE CHINNECK et. al. (2003)
 Constrói uma lista dinâmica de programação de tarefas
baseada em estimativas de caminhos críticos e revisada a cada
designação.
 Utiliza o conhecimento das características de comunicação
interprocessadores da arquitetura RDAD e as propriedades do
processador mestre.
 Heurística construtiva.
Investigar métodos iterativos como busca local e meta- heurísticas
7
ALGORITMOS GENÉTICOS (AG)
 Técnicas de busca heurística baseadas nas teorias da
evolução.
 Uma solução particular de um problema é chamada de
cromossoma ou indíviduo.
 As variáveis de decisão estão associadas aos genes do
cromossoma.
 A busca heurística é realizada em uma população de
soluções e não de solução em solução como em outras
meta-heurísticas (Busca Tabu, Simulated Annealing) 
Busca Multi-direcional.
8
REPRESENTAÇÃO DO CROMOSSOMA
Vetor v de números inteiros com n posições , onde n é o número
de tarefas do diagrama. Em v(i) é armazenado o número do
processador para o qual a tarefa i foi designada.
tarefas
processadores
1
2
3
4
5
6
7
8
9
10
0
2
3
1
3
3
4
4
2
0
Tarefa 3 designada ao
processador 3.
9
FUNÇÃO DE APTIDÃO (FIT)
fit (i ) 
atraso _ m áxim o atraso(i )
j n
 (atraso _ m áxim o atraso( j ))
j 1
 fit(i): aptidão do cromossoma i.
 atraso_máximo: atraso máximo de um cromossoma da população.
 atraso(i): atraso do cromossoma i.
 n: tamanho da população.
10
OPERADORES GENÉTICOS
 MUTAÇÃO: Introdução da diversidade genética da população.
Cromossoma antes da
mutação
1 2 3 4 5 6 7 8
0 1 1 0 1 1 0 1
Cromossoma depois da
mutação
1 2 3 4 5 6 7 8
1 1 1 0 0 1 0 1
genes aos quais
será aplicada
mutação
genes aos quais
foi aplicada
mutação
Escolha aleatória de uma tarefa e sua designação para um novo processador
Tarefa a ser aplicada a mutação
Tarefa 4 designada ao processador 1
2
3
4
5
6
7
8
9 10
1
2
3
4
5
6
7
8
9 10
0 1
0
2
3
3
1
2
3
0 1
0
12 3
3
1
2
3
1
0
0
11
OPERADORES GENÉTICOS
 Cruzamento: 1 ponto.
PAIS
FILHOS
Ponto de cruzamento
1
2
3
4
5
6
7
8 9 10
1
2
3
4
5
6
7
8 9 10
0
1
0
2
3
0
2
3
4
0
1
0
2
3
0
0
4
1
2
3
4
5
6
7
8 9 10
1
2
3
4
5
6
7
8 9 10
1
2
3
0
3
2
0
4
1
2
3
0
3
2
2
3
1
0
1
Se o cruzamento produzir filhos
infactíveis
0
1
REPARAÇÃO
12
1
4
BUSCA COM ALGORITMO GENÉTICO
 Gere uma população inicial com m indivíduos.
Enquanto (geração corrente  maxger) ou (população não
homogênea) repita:
 Calcule a aptidão de cada individuo;
 Selecione os indivíduos para nova população;
 Aplique cruzamento com probabilidade pc e
“Reparação”;
 Aplique mutação com probabilidade pm e
“Reparação”;
Ao longo de todo o processo, armazene a melhor solução
obtida.
13
Implementações: Algoritmos Puro, Inteligente 1, Inteligente 2
ALGORITMO PURO - Escolhas aleatórias na
seleção da tarefa e processador na REPARAÇÃO
1
2
3
4
5
6
7
8
1
2
3
0
3
2
2
3
CRUZAMENTO
PROCESSADOR 2:
9 10
capacidade violada
1 4
Tarefa escolhida:6
1
2
3
1
2
3
Tarefas: 2, 6 e 7
Pode ser designada ao processador 1 ou 4.
4 5 6 7 8 9 10
Processador 4 escolhido
0
3
4
2
3
1
4
MUTAÇÃO
1
2
3
4
2
1
0
4
5
3
6
3
7
0
8 9 10
2
3
4
Processador 1 escolhido
Tarefa 4: Pode ser designada
ao processador 0 ou 1.
1
2
3
4
2
1
0
1
5
3
6
3
7
0
8 9 10
2
3
4
14
INTELIGENTE 1- Escolhas determinísticas na
seleção do processador na REPARAÇÃO
CRUZAMENTO
1
2
3
4
5
6
7
8 9 10
1
2
3
0
3
2
2
3
1
Tarefa 6: Pode ser designada
ao processador 1 ou 4.
4
•Processador 1 => atraso de 7 ciclos.
1
2
1
2
•Processador 4 => atraso de 8 ciclos.
3 4 5 6 7 8 9 10
Processador 1 escolhido
3
0
3
1
2
3
1
4
MUTAÇÃO
1
2
3
4
2
1
0
1
5
3
6
3
7
0
8 9 10
2
3
4
Processador 0 => atraso de 6
Processador 4 => atraso de 7
Tarefa 4: Pode ser designada
ao processador 0 ou ao 4.
1
2
3
4
2
1
0
0
5
3
6
3
7
0
8 9 10
2
3
4
15
INTELIGENTE 2- Escolhas determinísticas na
seleção da tarefa e processador na REPARAÇÃO
1
2
3
4
5
6
7
8
1
2
3
0
3
2
2
3
CRUZAMENTO PROCESSADOR 2:
9 10
capacidade violada
1 4
Tarefas: 2, 6 e 7
Analisa-se todas as tarefas:
• tarefa 2: só cabe no processador 4
Processador 4 => Atraso 7
=> Melhor processador: 4
• tarefa 6: cabe no processador 1 e no 4
=> Melhor processador: 1
Processador 1 => Atraso 6
Processador 4 => Atraso 8
• tarefa 7: Não cabe em nenhum processador
existente.
=> Melhor processador: 5
Processador 5 => Atraso 10
16
INTELIGENTE 2
Tarefa escolhida:6
1
2
3
4
5
6
7
8 9 10
1
2
3
0
3
1
2
3
1
4
Processador 1 escolhido
MUTAÇÃO
• Igual a Inteligente 1: escolhe-se o melhor processador para
designar a tarefa que sofrerá a mutação.
17
PARÂMETROS UTILIZADOS
 Tamanho da População: 20 indivíduos.
 Probabilidade de Cruzamento (pc): análise.
 Probabilidade de Mutação (pm): análise.
 Critérios de Parada:
Obtenção da solução ótima.
Número limite de gerações (Maxger= 2000).
Geração de população homogênea.
18
EXPERIMENTOS COMPUTACIONAIS
 Experimentos iniciais: 10 problemas-teste (5 a 96 tarefas), obtidos
em Chinneck et. al (2003) e através de um gerador aleatório de grafos
de tarefas (Lavoie,1999).
 Para todos os três algoritmos, pequeníssimas probabilidades de
mutação resultam nas melhores performances.
 Quanto maior o número de tarefas menor deve ser o valor de pm.
 O algoritmo Genético Inteligente 2 tem vantagem em termos de
qualidade de solução em relação aos dois primeiros algoritmos,
mas utiliza um tempo de execução maior.
 Selecionado pm = 0,01 para os 3 algoritmos nos experimentos
posteriores.
 Selecionados pc= 0,4 (algoritmo puro),
0,3 (inteligente 1) e 0,8
(inteligente 2) nos experimentos posteriores.
19
RESULTADOS COMPUTACIONAIS
 24 diagramas
ALGORITMOS GENÉTICOS
(5 a 96 tarefas).
QUALIDADE
DA SOLUÇÃO
Diagrama de
tarefas
# de
tarefas
Chinneck et.
Al.
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
D15
D16
D17
D18
D19
D20
D21
D22
D23
D24
5
6
9
9
9
10
12
12
13
15
15
16
19
21
22
24
24
25
30
46
46
46
80
96
MÉDIA
4/3
6/5
4/3
4/3
7/6
5/5
5/4
5/4
8/5
4/5
6/5
4/5
6/6
8/7
5/8
8/8
12/11
6/8
11/11
25/31
7/11
17/20
36/36
41/47
10,17/10,71
PURO
pc=0.4
pm=0.01
A/#proc
INT 1
pc=0.3
pm=0.01
A/#proc
INT 2
pc=0.8
pm=0.01
A/#proc
INT 2
Outros pc e
pm
A/#proc
4/3
6/4
5/3
4/3
8/6
6/5
5/4
5/4
6/5
5/5
6/5
5/5
6/6
11/7
5/8
8/8
13/10
9/7
14/11
29/30
9/11
22/19
49/32
46/42
11,92/10,12
4/3
6/4
4/3
5/3
8/6
6/5
4/4
5/4
5/5
5/5
6/5
5/5
5/6
10/7
5/8
7/8
13/10
7/8
12/10
29/28
9/11
20/20
42/32
45/44
11,12/10,17
4/3
6/4
4/3
4/3
7/6
5/5
4/4
5/3
5/5
5/5
6/5
5/5
5/6
8/7
5/8
7/7
10/10
7/7
12/10
25/28
7/11
17/17
40/34
44/46
10,29/10,08
4/3
6/4
4/3
4/3
7/6
5/5
4/4
5/3
5/5
4/5
6/5
4/5
5/6
8/7
5/8
7/7
10/10
6/7
11/10
25/28
7/11
16/18
36/32
41/41
9,79/9,83
20
RESULTADOS COMPUTACIONAIS
TEMPOS DE EXECUÇÃO
Diagrama
de tarefas
# de
tarefas
D1
D2
D3
D4
D5
D6
D7
D8
D9
D10
D11
D12
D13
D14
D15
D16
D17
D18
D19
D20
D21
D22
D23
D24
5
6
9
9
9
10
12
12
13
15
15
16
19
21
22
24
24
25
30
46
46
46
80
96
MÉDIA
PURO
pc= 0,4
pm= 0,01
Tempo
Tempo total
melhor
(segundos)
(segundos)
0
0,05
0
0
0
0
0,05
0,43
0
1,04
0
0,66
0
0,6
0
0,55
0,61
0,83
0,66
1,65
0,72
0,72
0,77
1,49
1,05
1,27
1,59
2,14
0
2,47
1,37
2,09
1,15
2,53
1,1
1,21
3,18
3,18
3,9
5,22
0,66
6,2
4,84
5,49
7,52
13,07
5,38
14,55
1,44
2,81
INTELIGENTE 1
pc= 0,3
pm= 0,01
Tempo
Tempo total
melhor
(segundos)
(segundos)
0
0
0
0,11
0,06
0,06
0,22
0,71
0
1,15
0
0,71
1,43
1,43
0
1,38
0,61
0,66
0,11
1,81
1,43
1,64
0,66
1,87
1,21
2,09
1,64
2,74
0
4,45
2,64
3,41
1,37
3,41
1,81
1,81
2,03
4,94
11,04
13,3
0,6
37,29
13,95
14,94
68,87
91,01
379,53
392,93
20,38
24,33
INTELIGENTE 2
pc= 0,8
pm= 0,01
Tempo
Tempo total
melhor
(segundos)
(segundos)
0
0
0
0
0
0,66
0,22
0,94
0
2,09
0,77
0,77
0,27
1,32
0,38
0,6
0,33
0,66
0,06
0,77
0,66
0,82
0,66
0,88
1,04
3,51
0,98
1,92
0
14,83
4,06
6,21
4,4
6,87
1,1
5,93
3,9
8,68
28,56
30,92
1,43
229,37
47,24
54,54
440,78
597,86
1989,4
2725,02
105,26
153,97
21
CONCLUSÕES E PERSPECTIVAS
 Elaboradas três implementações de algoritmos genéticos
preliminares.
 A melhor implementação proposta (Inteligente 2) melhorou em
25% de casos, as soluções da heurística de Chinneck et. al.
 Quanto maior o número de tarefas, pior é desempenho dos
algoritmos.
 Cruzamento de um ponto.
 Incorporação de maior informação sobre o problema:
 Utilização de operadores de cruzamento de 2 ou mais pontos
 Desenvolvimento de operadores de cruzamento mais
específicos.
 Aplicação de buscas locais após um número de gerações
especificado.
22