Projeto 2011.1

Descrição do Problema

Gerenciamos um provedor de Utility Computing. Oferecemos ciclos de CPU. Nossa infra-estrutura é composta de um cluster com N máquinas, ao qual vão ser alocados, em batch, K jobs para um dado cliente. Uma lista de jobs que é incluída, um após o outro, no cluster é o que chamaremos de workload. O cliente nos paga um valor que é inversamente proporcional ao tempo que levamos para completar todos os seus jobs, independentemente da ordem. Por isso, quanto mais rápido  completarmos os pedidos do cliente, mais rápido teremos as máquinas novamente disponíveis. Além disso mais receita obteremos.

Temos que encontrar um workload que tome o mínimo de tempo possível.

Os jobs solicitam alguma quantidade de máquinas por alguma quantidade de tempo. Essa solicitação é indivisível: uma vez começado o job, então as máquinas só voltarão a ficar disponíveis após o processamento deste job se haver completo. Para facilitar, a granulosidade de tempo considerada será igual a uma hora. Assim, um job solicita m máquinas por t horas.

Apesar de a execução de um job, uma vez iniciada, não poder ser interrompida, ocorre que a memória é plenamente (e utopicamente) compartilhada de modo instantâneo. Assim, os jobs podem trocar de uma máquina para outra, se for necessário. Isso facilita o trabalho de distribuição dos jobs.

Temos um módulo distribuidor que aloca máquinas para os jobs segundo um workload pré-definido: alguma ordem em que eles são apresentados. Este módulo busca encontrar slots de máquina/tempo vagos o mais antecipadamente possível, a fim de minimizar o tempo total desprendido. Ainda assim, a depender da ordem em que o distribuidor recebe os jobs (o workload), o tempo total de execução pode ser muito alto.

Para o cliente, porém, a ordem de execução é irrelevante, desde que todos os jobs se completem. De preferência o mais rápido possível.

O seu trabalho é desenvolver um scheduler, que receba uma lista de jobs e, considerando a capacidade (número de máquinas) disponíveis no cluster, encontre um workload que minimize o tempo total de execução.

Exemplo: suponha um cluster com 5 máquinas, e a seguinte lista de Jobs.

Caso o workload seja construído da forma como está a lista (um scheduler de eficiência duvidosa), após a inclusão do job #1 (3 máquinas por 2 horas) a alocação ficará assim.

 Em seguida, incluímos o Job #2 (4 máquinas por 3 horas). Note que ele não “cabe” nos tempos t=1 e t=2, já que ele precisa alocar 4 máquinas operando para si. A alocação fica como mostrado.

O Job #3 pede 2 máquinas por 3 horas. Fossem apenas 2 horas, e ele seria alocado para as máquinas m4 e m5 nos instantes t=1 e t=2. Isso, porém, não é possível. A alocação, então, é somo segue.

Para o Job #4 (4 máquinas por 2 horas) a alocação é feita para após o Job #3.

 Job #5: 5 máquinas por 2 horas. Não há muito o que fazer.

 O Job #6 pede 2 máquinas por 2 horas. Graças à esperteza de nosso distribuidor, este fica bem acomodado logo no início.

O job #7, com suas 2 máquinas por 5 horas vai para o final da fila.

 E finalmente o Job #8. 1 máquina apenas, mas por 12 horas. Para simplificar a representação, assumimos que o escalonador mudará, sempre que possível, os jobs para as máquinas mais à esquerda. A alocação final fica como está abaixo. Veja que a execução do último job terminará 24 horas depois do início da execução do primeiro.

Algumas soluções aleatórias, a título de ilustração (aproveite para treinar manualmente).

Ordem: J1, J5, J6, J4, J2, J3, J8, J7

Esta alocação já promoveu uma melhoria de 8 horas em relação ao workload anterior.

Outro workload aleatório. Ordem: J2, J4, J3, J8, J6, J5, J7, J1

Podemos usar uma hurística gulosa. Formaremos o workload tomando os jobs em tamanho crescente de número de máquinas e em seguida pelo número de horas. Cheque se a ordem e a alocação está correta.

Invertendo a heurística, podemos tomar os jobs em tamanho crescente de número de horas e em seguida pelo número de máquinas. Cheque se a alocação está correta.

E uma entidade metafísica vinda da oitava dimensão sugeriu que o workload deveria ser: J4, J8, J2, J7, J3, J6, J1, J5. Calcule o tempo de execução neste caso. Será que pode haver solução melhor?

Um algoritmo que encontra a melhor solução exaurindo o espaço de busca, neste caso, não seria muito oneroso. Com efeito, ele teria que testar K! combinações. No exemplo, K=8 e 8! =40320.

Mas nós sabemos o que pode acontecer quando K cresce. Para K=30, por exemplo, teremos um total de aproximadamente 2,65x1032 combinações.

Escolha uma heurística bioinspirada e implemente um scheduler eficiente.

Seu scheduler deve encontrar uma solução e testá-la, sempre comparado com melhor algoritmo possível (que obviamente só pode ser executado em condições limitadas). A eficiência de seu Job será dada por To2/Tj2, onde To é o tempo do algoritmo ótimo e Tj é o tempo de seu scheduler.

Teste seu scheduler para cada uma das listas (algumas vezes para cada) e compare o resultado com que foi encontrado pelo melhor scheduler (OptimalScheduler). Este, obviamente, só precisa ser testado uma vez, já que é determinístico. Calcule a média e o erro máximo com confiança de 95%. Note que quanto maior a quantidade de experimentos, menor será seu intervalo de confiança.

Para testar seu scheduler, geramos 100 aleatórias de jobs com diferentes quantidades de máquinas e horas para cada um. Todos eles são limitados a 8 jobs, pois é o máximo que pode sr cumprido pelo OptimalScheduler em tempo razoável. O seu trabalho é reordenar os Jobs algoritmicamente, usando seu scheduler bio-inspirado. Veja os arquivos "lista0.txt", "lista1.txt", ..., "lista99.txt" no diretório "listas".

Por exemplo, o scheduler randômico (DummyScheduler) que está implementado, usando os jobs definidos no arquivo “jobslist_small.txt”, obteve um desempenho de 82,92%, mas com intervalo de confiança muito alto, de 5,19%, já que foram feitos apenas 24 testes.

Monte seus experimentos, verifique o desempenho de seu escalonador e discuta os resultados.

 Abordagem

O sistema está "quase" pronto. A versão que voces usarão como ponto de partida pode ser obtida aqui.

Há uma classe de fachada que lê um arquivo com os jobs e outro com o tamanho (em número de máquinas) do cluster. Ambos os arquivos são passados como parâmetros. Um terceiro parâmetro, que é onde seu trabalho se encaixa, determina o tipo do escalonador. 

Com isso a fachada cria um objeto do tipo JobsList, que armazena informações sobre os Jobs que devem ser executados, bem como sobre o cluster onde a execução se dará.

O distribuidor de Jobs já está implementado. No pacote você vai encontrá-lo implementado no método allocate() da classe Cluster. O distribuidor faz a melhor alocação possível, sem alterar a ordem dos jobs  que é previamente oferecida (veja os exemplos acima). O seu escalonador é que cuidará de encontrar a melhor ordem de forma a maxiizar o desempenho.

Na classe JobsList há duas listas (ArrayList) de Jobs. Uma com os Jobs na ordem em que foram lidos do arquivo (chamada jobs) e outra onde devem ficar os jobs otimizados (chamada optimizedJobs).É nesta última que deve ficar a solução final de seu escalonador.

Implementando um escalonador

Seu scheduler deve ser desenvolvido usando a interface Scheduler que já está disponível. Para implementar corretamente esta interface, ele precisará conter o método schedule(), que recebe um objeto do tipo JobList como parâmetro. Este método deve reorganizar os jobs (originalmente na lista jobs) e inserí-los na lista optimizedJobs. O escalonador chamado DummyScheduler dá uma idéia básica do processo. Observe que o método JobsUtils.copyJobs() já permite que você copie uma lista para outra.

Testando um workload

Haverá a necessidade de você testar diferentes listas de jobs durante o processo de otimização. Este teste pode ser feito de maneira bem simples. Usando a o objeto do tipo JobsList onde foram lidos os jobs do arquivo, copie a lista que você deseja testar para a lista de jobs otimizados (usando JobsUtils.copyJobs()) e em seguida execute o método evaluate(). Este método lhe devolverá um número inteiro, correspondente ao número de horas que o cluster levaria para executar a lista tal qual você a está construindo.