No estudo do
escalonamento em computação paralela veremos como alocar
processadores à tarefas, para isto supomos que as aplicações
são fornecidas na forma de grafo de precedência. Nesta representação
os vértices correspondem as tarefas e as arestas indicam as relações
de precedência.
Estudaremos
principalmente duas questões:
1) o
custo que deve ser considerado quando uma tarefa não está
alocada no mesmo processador que os seus predecessores diretos;
2) o
caso em que o grafo de precedência é construido durante a
execução da aplicação.
1) Escalonamento com atraso de comunicação.A maior parte das máquinas paralelas consiste de um conjunto de processadores sequênciais interligados através de uma rede de interconexão. Como existe uma distância (física) entre os diferentes processadores a comunicação entre eles não é imediata. Ocorrem atrasos (delays) de comunicação que devem ser considerados.Estudaremos os custos de comunicação através da introdução de atrasos nos problemas de escalonamento em máquinas paralelas, assim como introduziremos modelos realísticos (que tem como objetivo aproximar o comportamento de máquinas paralelas reais, ex BSP, LogP, malleable tasks).2) Escalonamento dinâmico.Neste caso, a decisão sobre a alocação de tarefas é feita dinâmicamente, conforme as tarefas estejam prontas para serem executadas. Em geral os algoritmos de decisão são simples e fornecem bons resultados. Abordaremos também o problema de balanceamento de carga (load balancing).Uma outra abordagem possível para o escalonamento dinâmico pode ser vista na página do professor Lêonidas.
Comentários ? Sugestões ? envie uma mensagem para gold@ime.usp.br