Escalonamento em computação paralela

        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