PPD: Balanceamento de Carga e Scheduling2
Fernando Silva
DCC-FCUP
2
(Alguns dos slides são baseados nos de Kathy Yelick, www.cs.berkeley.edu/ yelick)
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling3
1 / 21
Objectivo do Scheduling
Os conceitos de balanceamento de carga e de scheduling são muito
próximos e, normalmente, usam-se com o mesmo significado.
O objectivo de uma estratégia de scheduling
é maximizar o desempenho de sistema paralelo, transferindo tarefas de
processadores mais sobrecarregados para outros que estejam mais leves.
Uma estratégia de scheduling envolve duas decisões importantes:
determinar quais as tarefas que podem ser executadas em paralelo, e
determinar onde executar as tarefas paralelas
A tomada de decisão é normalmente feita com base ou em conhecimento
prévio ou em informação em tempo de execução.
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling4
2 / 21
Dificuldades para o Scheduling
O desenho de uma estratégia de scheduling depende das propriedades das
tarefas:
Custos das tarefas
I
I
têm todas as tarefas o mesmo custo?
se não têm, quando são esses custos conhecidos?
F
antes da execução, quando a tarefa é criada, ou apenas quando
termina?
Dependências entre tarefas
I
I
as tarefas podem ser executadas em qualquer ordem?
se não podem, quando são conhecidas as dependências?
F
antes da execução, quando a tarefa é criada, ou apenas quando
termina?
Localidade
I
I
é importante que algumas tarefas executem no mesmo processador (ou
próximo deste) para reduzir custos de comunicação?
quando é que se conhece a informação sobre comunicação?
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling5
3 / 21
Custo de Tarefas
Scheduling de um conjunto de tarefas nos casos seguintes:
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling6
4 / 21
Dependências entre tarefas
Scheduling de um grafo tarefas nos casos seguintes:
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling7
5 / 21
Localidade de tarefas
Scheduling de um conjunto de tarefas nos casos seguintes:
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling8
6 / 21
Soluções de Scheduling
Scheduling Estático - as decisões são tomadas em tempo de
compilação.
I
I
I
análise estática de programas para estimar tamanho das tarefas; esta
informação é difícil de obter e geralmente incompleta.
mapeamento estático da árvore de pesquisa na arquitectura paralela
(mapeamento óptimo é NP-completo).
construção de um grafo dirigido com os nós a representarem tarefas e
as ligações representarem dependências nos dados ou comunicação;
determinar ordem de execução que minimize o tempo de execução.
Scheduling Dinâmico (ou partilha adaptativa de trabalho) - faz uso
de informação do estado da computação em tempo de execução, para
tomar decisões.
I
Exemplo: verifica a carga dos processadores para assegurar um
balanceamento de carga dinâmico nos processadores.
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling9
7 / 21
Porquê Scheduling Dinâmico?
Para uma grande classe de problemas, o seu espaço de soluções
corresponde a uma árvore de procura.
Estes problemas são frequentemente:
computacionalmente exigentes
admitem muitas estratégias diferentes de paralelização
requerem balanceamento dinâmico de carga
Exemplos:
enumeração de sub-grafos de tamanho k de um dado grafo
procura de padrões em redes sociais ou biológicas
problema da colocação das rainhas num tabuleiro
problemas divide-and-conquer e branch-and-bound
árvore de execução do Prolog
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling10
8 / 21
Árvore de procura
a árvore é construída dinamicamente durante ou com a execução
podem ter sub-problemas comuns em caminhos diferentes
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling11
9 / 21
Procura em paralelo
Considere-se:
uma pesquisa DFS da árvore
scheduling estático: enquanto houver processadores não ocupados,
atribuir a próxima nova tarefa.
Podemos e devemos fazer melhor!
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling12
10 / 21
Estratégias de Scheduling Dinâmico
As estratégias de scheduling dinâmico podem ser:
centralizadas
I
I
I
assumem um scheduler central que reúne informação sobre todo o
sistema, nomeadamente carga, e toma as decisões de transferência de
tarefas.
funciona bem num sistema de memória partilhada, mas com um
número de processadores reduzido.
é ineficiente num sistema de memória distribuída, pois requer muita
comunicação para manter o scheduler com informação actualizada.
distribuídas
I
I
existe um scheduler por processador que tomam decisões autónomas
sobre partilha de trabalho.
o objectivo é manterem o seu processador ocupado e balancear a carga
no sistema.
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling13
11 / 21
Scheduling Centralizado
O scheduler tem uma fila única de tarefas
1. responde a pedidos dos processadores (ou workers), ou
2. os workers acedem autonomamente à fila, sincronizando através de
locks
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling14
12 / 21
Master-Worker
Estratégia centralizada em sistemas de memória distribuída
Decisão de distribuíção de tarefas concentrada no master-worker
Workers executam ciclo:
I
I
I
I
pedir trabalho
receber trabalho
executar trabalho
enviar resultado
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling15
13 / 21
Questões com a estratégia centralizada
Evitar contenção no acesso à fila de tarefas partilhada
Suponha que as tarefas correspondem a um intervalo de índices de
um ciclo (iterações independentes). Seja K o tamanho da tarefa:
I
I
Se K for grande, reduz-se contenção no acesso à fila.
Se K for pequeno, simplifica-se o balanceamento de carga.
Ideias:
I
I
I
Usar tarefas maiores no início (maior número de índices) para evitar
overhead excessivo e menores mais próximo do fim.
No acesso de ordem i à fila, seleccionar uma tarefa com tamanho
dRi /pe, onde Ri é número total de tarefas em sobra e p é o número de
processadores.
O tamanho Ki é função do trabalho sobrante, mas também da
variância do custo da tarefa.
F
F
F
I
a variância é estimada usando informação histórica
variância elevada ⇒ tamanhos menores
variança baixa ⇒ tamanhos maiores
Enquadrar diferenças de processamento.
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling16
14 / 21
Filas distribuídas de tarefas (ou Work-Pools)
Extensão natural para sistemas distribuídos, mas também para
memória partilhada.
Permite que workers sem trabalho tomem a iniciativa de procurar
trabalho, ou que workers ocupados possam partilhar tarefas.
São úteis quando
I
I
se está com um sistema de memória distribuída
existe muita sincronização ou muitas tarefas pequenas
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling17
15 / 21
Scheduling Distribuído
As decisões de partilha podem ser:
sender initiated (ou work distribution)- os workers mais ocupados,
procuram outros menos ocupados para lhe atribuir tarefas.
I
melhor para pequenas cargas.
receiver-initiated (ou work-stealing) - os workers que ficam sem
trabalho, procuram um worker com muito trabalho e pede para
partilhar.
I
melhor para grandes cargas do sistema.
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling18
16 / 21
Como seleccionar um worker a quem pedir trabalho
Round-robin:
I
targetk = (targetk + 1) mod procs.
polling/stealing aleatório
I
Quando um processador precisa de trabalho, selecciona aleatoriamente
um processador e envia-lhe um pedido.
repete último:
I
I
por questões de localidade pode haver vantagem voltar a pedir ao
último worker,
se este não tiver trabalho, passa a um dos esquemas anteriores.
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling19
17 / 21
Como dividir trabalho?
Número de tarefas a distribuir? Dividir a meio?
Quais as tarefas:
I
I
topmost: tarefas do início da fila (mais antigas)
bottomost: tarefas do fim da fila (mais recentes)
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling20
18 / 21
Estratégias de partilha 1/2
Sender-initiated
Quando um worker gera uma nova tarefa, o seu scheduler procura o
processador mais livre e atribui-lhe a tarefa para execução. Se não for
bem sucedido, guarda na fila local.
Receiver-initiated
As tarefas geradas por workers são colocadas sempre na sua fila local.
Quando um worker procura uma tarefa para execução, o scheduler
procura primeiro na sua fila local. Se estiver vazia, então procura uma
tarefa fora (também referido por work-stealing).
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling21
19 / 21
Estratégias de partilha 2/2
Adaptative I
Combina as estratégias sender-initiated e receiver initiated. Os
workers são classificados como Senderds ou Receivers mediante o
valor de um parâmetro Threshold. Um worker é sender se o númerod
e tarefas na sua fila estiver acima do threshold, será receiver no caso
contrário.
Adaptative II
Melhora a heurística Adaptative I, introduzindo dois parâmetros Low
e High para classificar os workers como Senders, Receivers ou
Neutrals. Um worker muda dinamicamente o seu comportamento,
função da quantidade de trabalho na sua fila:
I
I
I
#tasks < high ⇒ comportamento sender
#tasks < low ⇒ comportamento receiver
neutral se low ≤ #tasks ≤ high
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling22
20 / 21
Exemplo da evolução das filas de tarefas
Fernando Silva (DCC-FCUP)
PPD: Balanceamento de Carga e Scheduling23
21 / 21