Analisando esquemas de balanceamento de carga para minimizar o tempo geral de execução
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 conhecidaXX. Suponha que existemnn cargas de trabalho e mmescravos 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:
Comece instantaneamente o processamento de qualquer kk cargas de trabalho em qualquer nó livre.
Receba instantaneamente a confirmação da conclusão por um nó de um lote iniciado anteriormente kk cargas de trabalho.
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 kk divide nn.
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=0t=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:
Existe uma maneira melhor de planejar estaticamente cargas de trabalho do que dividir lotes de kk cargas de trabalho entre os mm escravos o mais uniformemente possível (também podemos assumir, por uma questão de simplicidade, que mm divide n/kn/k, para que os lotes possam ser programados estaticamente de maneira completamente uniforme)? Se sim, como?
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 XX?
Um balanceador de carga dinâmico simples pode agendar ii lotes de kk cargas de trabalho para cada escravo inicialmente e, em seguida, quando os nós concluírem o ii lotes, programe um lote adicional de kkcargas 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:
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:
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 XX?
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.
Qual é o papel de kk? Se você só pode agendar exatamentekk cargas de trabalho (e não menos), não é equivalente a falar de cargas de trabalho únicas que levam kkvezes quanto tempo? Todas as cargas de trabalho chegam a t = 0?
Não seria mais natural supor que os tempos de execução sejam f( Eu) / sf(I)/s com EuI uma instância ("carga de trabalho"), ff uma função conhecida e ssa 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.
@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)).
@ 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).
Para a nova versão em que você tenta minimizar o makepan, sua programação estática ainda possui o valor esperado ideal.
Deixei MMseja a variável aleatória para o makespan. DeixeiFiFi seja o escravo do tempo iiestá terminado. Nós então temos issoM=maxi(Xi)M=maxEu(XEu). DeixeicicEu ser o número de trabalhos alocados ao escravo iEu. Então nós temos issoXEu=∑cEui = 1X=cEuXXi=∑i=1ciX=ciX.
E se FEu( X )Fi(x) é a função cumulativa de distribuição de probabilidade para XX, então P( M< m )P(M<m) = P(maxEu(XEu) < m )=P(maxEu(XEu)<m) =∏EuP(XEu< m )=∏EuP(XEu<m) =∏EuP(cEuX< m )=∏EuP(cEuX<m) =∏EuP( X<mcEu)=∏EuP(X<mcEu) =∏EuF(mcEu)=∏EuF(mcEu) é a função cumulativa de distribuição de probabilidade para MM. Isso significa queEM=∫∞- ∞x (∏EuF(xcEu))′dxEM=∫-∞∞x(∏EuF(xcEu))′dx, como normal.
Minimizando EMEM equivale a minimizar ∏EuF(xcEu)∏EuF(xcEu), o que significa que queremos manter tudo cEucEus igualmente baixo (como FFestá 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.
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".
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.
@ 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 :)
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.
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.