Analisando esquemas de balanceamento de carga para minimizar o tempo geral de execução

7

Suponha que um determinado aplicativo paralelo use um design mestre-escravo para processar um grande número de cargas de trabalho. Cada carga de trabalho leva algum número de ciclos para ser concluída; o número de ciclos que uma determinada carga de trabalho levará é dado por uma variável aleatória conhecidaX. Suponha que existemn cargas de trabalho e mescravos equivalentes (nós de processamento). Naturalmente, uma versão mais geral dessa questão aborda o caso de escravos de diferentes capacidades, mas ignoramos isso por enquanto.

O mestre não pode processar cargas de trabalho, mas pode distribuir cargas de trabalho para nós escravos e monitorar o progresso dos nós escravos. Especificamente, o mestre pode executar as seguintes ações:

  1. Comece instantaneamente o processamento de qualquer k cargas de trabalho em qualquer nó livre.
  2. Receba instantaneamente a confirmação da conclusão por um nó de um lote iniciado anteriormente k cargas de trabalho.
  3. A qualquer momento e instantaneamente, determine o estado de todos os nós (livre ou ocupado), bem como o número de cargas de trabalho concluídas e o número de cargas de trabalho restantes.

Por uma questão de simplicidade, assuma k divide n.

Existem pelo menos duas categorias de estratégias de balanceamento de carga para minimizar o tempo total de execução de todas as cargas de trabalho usando todos os escravos (para esclarecer, estou falando sobre o tempo do makepan ou do relógio de parede, não o tempo agregado do processo, independente do tempo de execução). estratégia de balanceamento de carga usada sob as suposições simplificadoras feitas nesta pergunta): estática e dinâmica. Em um esquema estático, todas as decisões de posicionamento são tomadas no momentot=0. Em um esquema dinâmico, o mestre pode tomar decisões de posicionamento usando informações sobre o progresso que está sendo feito por alguns escravos e, como tal, pode ser obtida uma melhor utilização (na prática, existem custos indiretos associados ao planejamento dinâmico em comparação ao planejamento estático, mas nós ignore-os). Agora, para algumas perguntas:

  1. Existe uma maneira melhor de planejar estaticamente cargas de trabalho do que dividir lotes de k cargas de trabalho entre os m escravos o mais uniformemente possível (também podemos assumir, por uma questão de simplicidade, que m divide n/k, para que os lotes possam ser programados estaticamente de maneira completamente uniforme)? Se sim, como?
  2. Usando a melhor política de planejamento estático, qual deve ser a média e o desvio padrão para o tempo total de execução, em termos da média μ e desvio padrão σ do X?

Um balanceador de carga dinâmico simples pode agendar i lotes de k cargas de trabalho para cada escravo inicialmente e, em seguida, quando os nós concluírem o i lotes, programe um lote adicional de kcargas de trabalho para cada escravo por ordem de chegada. Portanto, se dois nós escravos são inicialmente agendados com 2 lotes de 2 cargas de trabalho e o primeiro escravo termina seus dois lotes, um lote adicional é agendado para o primeiro escravo, enquanto o segundo escravo continua trabalhando. Se o primeiro escravo concluir o novo lote antes que o segundo lote termine seu trabalho inicial, o mestre continuará agendando para o primeiro escravo. Somente quando o segundo escravo concluir a execução de seu trabalho, será emitido um novo lote de cargas de trabalho. Exemplo:

         DYNAMIC           STATIC
         POLICY            POLICY

     slave1  slave2    slave1  slave2
     ------  ------    ------  ------

t<0    --      --        --      --

t<1  batch1  batch3    batch1  batch3
     batch2  batch4    batch2  batch4
                       batch5  batch7
                       batch6  batch8

t=1    --    batch3    batch5  batch3
             batch4    batch6  batch4
                               batch7
                               batch8

t<2  batch5  batch3    batch5  batch3
             batch4    batch6  batch4
                               batch7
                               batch8

t=2    --    batch4    batch6  batch4
                               batch7
                               batch8

t<3  batch6  batch4    batch6  batch4
                               batch7
                               batch8

t=3    --      --        --    batch7
                               batch8

t<4  batch7  batch8      --    batch7
                               batch8

t=4    --      --        --    batch8

t<5      -DONE-          --    batch8

t=5                      --      --

t < 6                      -DONE-

Para esclarecimento, os lotes 1 e 2 levam 1/2 segundo cada para serem processados, o lote 3 leva 2 segundos para serem processados ​​e os lotes 4-8 levam 1 segundo para serem processados. Esta informação não é conhecida a priori; no esquema estático, todos os trabalhos são distribuídos em t = 0, enquanto no esquema dinâmico, a distribuição pode levar em consideração quais são os tempos de execução reais dos trabalhos. Notamos que o esquema estático leva um segundo a mais que o esquema dinâmico, com o slave1 trabalhando 3 segundos e o slave2 trabalhando 5 segundos. No esquema dinâmico, os dois escravos trabalham por 4 segundos completos.

Agora, a pergunta que motivou a escrever isso:

  1. Usando a política de balanceamento de carga dinâmico descrita acima, qual deve ser a média e o desvio padrão para o tempo total de execução, em termos da média μ e desvio padrão σ do X?

Os leitores interessados ​​têm minhas garantias de que isso não é lição de casa, embora provavelmente não seja muito mais difícil do que se poderia esperar obter como lição de casa em determinados cursos. Dado que, se alguém se opuser a isso e exigir que eu mostre algum trabalho, ficarei feliz em obrigar (embora não saiba quando terei tempo no futuro próximo). Essa questão é, na verdade, baseada em algum trabalho que eu nunca cheguei a fazer um semestre ou dois atrás, e os resultados empíricos foram onde a deixamos. Obrigado pela ajuda e / ou esforço, ficarei interessado em ver o que vocês montaram.

Patrick87
fonte
11
Qual é o papel de k? Se você só pode agendar exatamentek cargas de trabalho (e não menos), não é equivalente a falar de cargas de trabalho únicas que levam kvezes quanto tempo? Todas as cargas de trabalho chegam a t = 0?
Alex-Brink
Não seria mais natural supor que os tempos de execução sejam f(I)/s com I uma instância ("carga de trabalho"), f uma função conhecida e sa velocidade da máquina atual? Nesse caso, você pode usar as velocidades da máquina para informar suas decisões e aprender as velocidades, caso não as conheça (ou elas mudem). Tempos de execução aleatórios não lhe dar qualquer informação sobre como distribuir o seu trabalho.
Raphael
@AlextenBrink Sim, todas as cargas de trabalho chegam no tempo t = 0. De certo modo, sim, você pode assumir que k = 1 nesta pergunta ... mas X é para uma única carga de trabalho, não para um lote de k cargas de trabalho e, em Em qualquer caso, k pode ser algo que eu queira ajustar na prática (para superar as despesas gerais de latência da comunicação, talvez). Se você puder resolver o resto para k = 1, o salto para outro k deve ser direto (apenas descubra a distribuição Y = X + X + ... + X (k vezes)).
Patrick87
@ Rafael Concordo que os tamanhos aleatórios de carga de trabalho não fornecem informações úteis sobre como distribuir o trabalho ... essa é a intenção do problema. Várias simplificações estão sendo feitas aqui, mas o que mais me interessa é analisar esses métodos simples (estáticos e dinâmicos) com essas suposições simplificadas, antes (possivelmente) de expandir o escopo da pergunta (por exemplo, dizendo que temos mais informações sobre quanto trabalho uma carga de trabalho específica exigirá e eliminando a suposição de nós com desempenho uniforme ou constante).
22712 Patrick87
@ Rafael Na verdade, a motivação para esta pergunta é exatamente essa: se você não sabe nada sobre quanto tempo uma carga de trabalho específica levará, poderá fazer muito melhor do que os métodos estáticos e dinâmicos descritos acima? De qualquer forma, quão melhor é o método dinâmico comparado ao método estático (não pode ser pior, e forneço um exemplo em que a dinâmica é realmente melhor).
Patrick87

Respostas:

5

Atualizar:

Para a nova versão em que você tenta minimizar o makepan, sua programação estática ainda possui o valor esperado ideal.

Deixei Mseja a variável aleatória para o makespan. DeixeiFi seja o escravo do tempo iestá terminado. Nós então temos issoM=maxEu(XEu). DeixeicEu ser o número de trabalhos alocados ao escravo Eu. Então nós temos issoXi=i=1ciX=ciX.

E se Fi(x) é a função cumulativa de distribuição de probabilidade para X, então P(M<m) =P(maxEu(XEu)<m) =EuP(XEu<m) =EuP(cEuX<m) =EuP(X<mcEu) =EuF(mcEu) é a função cumulativa de distribuição de probabilidade para M. Isso significa queEM=-x(EuF(xcEu))dx e stddev(M)=(xEM)2(iF(xci))dx, como normal.

Minimizando EM equivale a minimizar EuF(xcEu), o que significa que queremos manter tudo cEus igualmente baixo (como Festá aumentando monotonicamente e entre 0 e 1). Isso significa que devemos distribuir igualmente todas as tarefas entre os escravos, exatamente o que sua agenda estática alcança.

Alex ten Brink
fonte
Acho que provavelmente não estava claro o que queria. Quando digo "tempo total", quero dizer "tempo do relógio de parede", não "tempo do processo". É claro que a programação não faz diferença se eu estiver interessado apenas em adicionar os tempos de execução de todos os programas. O que eu quero minimizar é o tempo total necessário para que todos os escravos terminem todo o trabalho. No exemplo que eu forneço, o tempo em que estou interessado é 4s; o tempo que você está falando é de 8 anos, acredito, já que é quanto tempo os escravos gastam em computação. Um escravo poderia terminar antes do outro, por exemplo, significando que minha métrica seria prejudicada por "retardatários".
precisa saber é o seguinte
Dito de outra forma, da maneira como pretendo a pergunta, meus esquemas estáticos e dinâmicos têm desempenho diferente para o exemplo que eu forneço, e a dinâmica se sai melhor. Se isso não estiver claro na minha pergunta, preciso editá-la.
precisa saber é o seguinte
@ Patric87: A palavra que você procura então é 'makespan', que é definida como a última vez que um escravo termina. Posso dar-lhe a análise para este caso também (talvez não hoje embora), mas vai ser um pouco mais :)
Alex ten Brink
Sim, makespan é um termo para isso. Suponho que seria melhor usar esse termo explicitamente na pergunta, para evitar confusões de outras pessoas que talvez não tenham experiência em entender o contexto da pergunta.
precisa saber é o seguinte
Talvez eu esteja enganado, mas X + X! = 2X, em geral, correto? E se o X for distribuído uniformemente, como rolos de matriz? Há uma diferença entre rolar um dado duas vezes e somar os números, e rolar um dado uma vez e multiplicar por dois (a média é a mesma, mas a forma e a dispersão diferem). O restante da análise parece bom, mas não tenho certeza de quais podem ser as implicações do meu argumento, se o argumento for válido. Eu acho que pode, pois mesmo que a média não seja afetada, o stdev é, e o máximo esperado dos valores esperados pode ser afetado pelo stdev ... isso parece intuitivamente plausível.
precisa saber é o seguinte