6
Considerando a evolução do grafo gerado pelas aplicações dinâmicas, Konig e Roch
observam que estas podem ser classificadas em dois grupos distintos: regulares e irregu-
lares [12]. As aplicações ditas regulares possuem uma estrutura de execução previsível.
Dessa forma, a estratégia de escalonamento po de ser desenvolvida considerando um pa-
drão no relacionamento entre tarefas, embora não sejam conhecidos nem o número de
tarefas a serem executadas, nem os custos computacionais associados. Para as aplicações
irregulares, não é possível identificar um padrão na estrutura de execução, dificultando
as operações de escalonamento, em particular quando se busca otimizar algum índice de
desempenho.
Deve-se notar que otimização de índices de desempenho é resultado de alguma po-
lítica de distribuição de carga empregada pelo mecanismo de escalonamento. Durante o
escalonamento podem ser aplicadas estratégias com objetivo de distribuir a carga compu-
tacional gerada pelo programa em execução pelos rec ursos de processamento disponíveis.
Nesse trabalho as estratégias trabalhadas serão voltadas a minimizar o tempo total de pro-
cessamento, sendo manipuladas as atividades de cálculo geradas pelo programa, embora
técnicas semelhantes possam ser aplicadas a qualquer outra fonte de custo, como dados
ou comunicações. Diversas heurísticas de escalonamento [13, 7, 14, 15, 16, 8] exploram
conhecimento sobre a estrutura do programa para otimização de índices de desempe-
nho. Tais estratégias servirão de base de estudo para implementação de um suporte ao
escalonamento dinâmico em arquiteturas do tipo aglomerado de computadores [17].
Feitelson relatou em 1995 [18] que, embora as pesquisas sobre técnicas de escalona-
mento explorando a estrutura de execução de programas fossem populares, sua exploração
prática em ambientes de execução era bastante reduzida. Esta realidade é ainda obser-
vada, existindo poucas opções (como Athapascan-1 [3] e Cilk [2]) desenvolvidas com esse
propósito. O problema que se coloca é como realizar o escalonamento em nível aplicativo
[19], ou seja, como permitir que a estratégia de escalonamento seja realizada de forma
associada ao programa em execução de forma a obter otimizações de desempenho.
Para explorar eficientemente uma arquitetura paralela, o programa deve ser dividido
em tarefas concorrentes e uma estratégia de escalonamento deve garantir eficiência no uso
dos recursos de processamento. Entretanto, as ferramentas de programação clássicas
exigem do programador conhecimentos específicos referentes à arquitetura sobre a qual
será executado seu programa, pois é sua responsabilidade tanto codificar a aplicação, como
distribuir tarefas a processadores e dados a módulos de memória [20]. Assim, além de
estar programando sua aplicação, também é de sua responsabilidade introduzir instruções
para realização do escalonamento do programa. Isso é ineficiente, pois além de obrigar o
programador a usar uma linguagem de mais baixo nível (a do escalonamento), também
faz com que a aplicação não seja portável, já que está intimamente ligada à arquitetura
para a qual foi programada. A menor alteração nessa arquitetura, como, por exemplo,
a incorporação de novos processadores, pode não refletir em ganho de desempenho na