Algoritmos para economia de energia no escalonamento de workflows em nuvens computacionais

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Algoritmos para economia de energia noescalonamento de workflows em nuvens

computacionais

Elaine N. Watanabe, Pedro P. V. Campos,Kelly R. Braghetto, Daniel M. Batista

Instituto de Matemática e EstatísticaUniversidade de São Paulo, São Paulo, Brasil

elainew,pedrovc,kellyrb,batista@ime.usp.br

Simpósio Brasileiro de Redes de Computadores e SistemasDistribuídos - 2014

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Motivação

Data centers [BB10]: 2% do CO2 no mundoServidores (Google) [BH07]:

Análise de milhares de servidores durante 6 mesesCPUs operavam entre 10% a 50%Ineficiente energeticamenteGastos extras

Custos em 2014 [B07]:Refrigeração e Energia elétrica(75%) > Equipamento(25%)

Uma das possíveis soluções

Computação em nuvem!

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Computação em nuvem

Máquinas virtuais (VMs)

Alto desempenho(TOP500: posição 64em 11/2013)

Ambiente elástico(sob demanda)

Candidato à execução deWorkflows

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Workflows científicos

Descrição de um experimentocientíficoConjunto de tarefas interligadas

AquisiçãoProcessamentoAnáliseVisualizaçãoEtc.

E no contexto da nuvem?

Problema?Dependência entre os dados

Possível solução?Novas políticas de escalonamento!

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Objetivos

Avaliar o escalonamento de workflows em nuvenscomputacionais visando à economia de energia

3 novos algoritmos de escalonamentoPowerHEFTLookaheadHEFT-DynamicAllocationVMTask Clustering

Uso do simulador CloudSim-DVFS

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Trabalhos relacionados

Topcuoglu et al. 2002: HEFT(Heterogeneous Earliest-Finish-Time)

Mais de mil citações no Google Acadêmico

Aksanli et al. 2012: GENSim

Estudo comparativo de eficiência energéticaSimular batch jobs e service jobsSem suporte a VMs

Kliazovich et al. 2012: GreenCloud

Comparação entre simuladores existentesAvaliar componentes da rede, não apenas os servidoresNão possui código aberto

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Trabalhos relacionados

Beloglazov et al. 2012: CloudSimEficiência energética em nuvemCloudSim + simulações energéticasSem suporte a workflows

Weiwei and Deelman 2012: WorkflowSim (CloudSim)Simulação de workflows em nuvens computacionaisconsiderando simulação de falhasSem suporte a simulações energéticas

Guérout et al. 2013: CloudSim-DVFS (CloudSim)Suporte à simulação energética de workflows em nuvenscomputacionaisEscalonadores com número de VMs fixas

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

CloudSim-DVFS

Disponível em outubro/2013

Uso do DVFS (Dimensionamento dinâmico de voltagem efrequência): De acordo com o uso de CPU, altera-se frequênciae voltagem da CPU, economizando energia

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Modelo energético

PTOT = (1−α)PCPUOciosa +(α)PCPUCargaMaxima (1)

onde α é o uso de CPU e PCPUOciosa e PCPUCargaMaxima são aspotências da CPU a 0% e 100% de utilização, respectivamente.

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Frequências utilizadas para criação de VMs

Frequências (GHz) 0.8 1.0 1.2 1.5 1.7CPU ociosa (W) 140 146 153 159 167

CPU carga máxima (W) 228 238 249 260 272

Tabela: Frequências da nuvem privada (Grid’5000 Reims) utilizadas porGuérout et al. 2013 para criar a lista de VMs

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Workflows

DAG (Grafo Orientado Acíclico)

Nós: custo de computação

Arestas: custo de comunicação(transferência de dados)

Caminhos críticos e não-críticos

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Escalonadores do CloudSim-DVFS

Performance: frequência máxima sempre

OnDemand: frequência máxima se CPU em uso e mínimaquando ociosa

Optimal: diminuir consumo energético nos caminhos não-críticoscom VMs "mais lentas"

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT: Heterogeneous Earliest Finish Time

Tarefa VM 1 VM 2 VM 3 rank(ti )1 14,9 11,9 9,9 57,92 13,8 11,1 9,2 45,63 11,7 9,4 7,8 34,34 13,8 9,2 12,7 45,65 12,7 10,2 8,5 44,76 13,8 11,1 9,2 34,27 7,4 6 5 24,68 5,3 4,3 3,5 22,89 19,1 15,3 12,7 34,1

10 22,3 17,9 14,9 18,3

Tarefas em ordemdecrescente de rank:1,2,4,5,3,6,9,7,8,10

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

VM 1 = VM do tipo"mais rápida"(Tipo 1)

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

Aloca a tarefa demaior rank na VM 1

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

Simula a alocação dasdemais tarefas

Qual o consumoenergético?

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

Simula a criação deuma nova VM (Tipo 1)

Qual o consumoenergético?

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

Simula a criação deuma nova VM (Tipo 2)

Qual o consumoenergético?

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

Simula a criação deuma nova VM (Tipo 3)

Qual o consumoenergético?

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

PowerHEFTLookahead

Qual caso obteve omenor consumoenergético?

É melhor criar umanova VM? De qualtipo?

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

VM 1 = VM do tipo"mais rápida"(Tipo 1)

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Aloca a tarefa demaior rank

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Aloca a tarefa demaior rank

Tarefa dependente daanterior? Podeexecutar na mesmaVM

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Tarefa paralelizável?Aloca uma nova VMdo tipo "mais lenta"

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Paralelize o máximoque puder

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Uma VM lenta vaiexecutar mais de umatarefa?

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Troque por uma VMmais rápida, pois podeser um caminho crítico

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Faça isso para todosos casos

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Continue a alocação

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

HEFT-DynamicAllocationVM

Alocação final comdependência de dados

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Task Clustering

Reconhece duas VMs"mais lentas"que vãoexecutar apenas umatarefa cada

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Task Clustering

Agrupa as tarefas emuma única VM "maisrápida"

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Experimentos

Ambiente de Teste: o mesmo utilizado por [Guérout et al. 2013]1 VM por hostTipos de VMs: conforme frequências para DVFS

Escalonadores:Performance (PERF)DVFS: OnDemand (ONDEM) e Optimal (OPT)PowerHEFTLookahead (POWERHEFT)HEFTHEFT-DynamicAllocation-VM (DAVM)HEFT-DynamicAllocation-VM-TaskClustering (DAVM-TC)Optimal-TaskClustering (OPT-TC)

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Figura: Exemplo da estrutura do workflow (a) Sipht (codificação de genes),(b) Cybershake (caracterização de zonas de risco de terremotos.) e (c)Montage (mosaico astronômico).

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Montage

Figura: Comparativo do consumo energético e makespan do DAG Montageutilizando diferentes políticas de escalonamento de tarefas.

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Roteiro

1 Motivação

2 Conceitos

3 PowerHEFTLookahead

4 HEFT-DynamicAllocationVM

5 Task Clustering

6 Experimentos

7 Conclusões

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Conclusões

Resultados

Redução do consumo energético na maioria dos casos,chegando até a 22.7%

Task clustering pode ser vantajoso tanto em relaçãoao consumo energético quanto ao tempo de execução

Estrutura de interligação das tarefas no workflow influencia noescalonamento

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Conclusões

Contribuições

Três novos algoritmos para escalonamento de workflowsvisando a eficiência energética sem impacto significativo nomakespan

Estudo comparativo com algoritmos existentes

Dados e código abertos à comunidade

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Trabalhos futuros

SimulaçõesOutros ambientes de testeOutros modelos energéticosUso de cargas de trabalho dinâmicas

Novas abordagens com o HEFT

Validação dos resultados em ambiente real

Possibilidades de:Integração do WorkflowSim ao CloudSim-DVFSUtilização de escalonadores dinâmicos ao invés de estáticosAdição da estimativa de consumo energético de outroscomponentes do data center

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Muito obrigada!Perguntas?

elainew@ime.usp.br

Agradecimentos

FAPESP (processo número: 2011/24114-0) e CAPES

Rodrigo N. Calheiros e Tom Guérout (CloudSim-DVFS)

Weiwei Chen (WorkflowSim)

Daniel A. Cordeiro (explicação sobre o HEFT)

Disponível em:https://github.com/pedropaulovc/CloudSim_DVFShttp://www.ime.usp.br/~elainew

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Bibliografia

L.A. Barroso e U. Hölzle. The case for energy-proportional computing.Computer, 40(12):33–37, 2007.

Tom Guérout, Thierry Monteil, Georges Da Costa, RodrigoNeves Calheiros, Rajkumar Buyya e Mihai Alexandru. Energy-awaresimulation with dvfs. Simulation Modelling Practice and Theory, v.39, i.1,p.76-91, 2013.

H. Topcuoglu, S. Hariri e Min-You Wu. Performance-effective andlow-complexity task scheduling for heterogeneous computing. IEEETransactions on Parallel and Distributed Systems, 13(3):260–274, 2002.

A. Beloglazov e R. Buyya. Energy Efficient Resource Management inVirtualized Cloud Data Centers. Energy Efficient Resource Managementin Virtualized Cloud Data Centers, 826–831, 2007.

C. Belady. In the data center, power and cooling costs more than the itequipment it supports Energy Efficient Resource Management inVirtualized Cloud Data Centers, 2007.

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Bibliografia

S. Murugesan. Harnessing green IT: Principles and practices ITprofessional, 24–33,2008.

J. Vöckler, G. Juve, E. Deelman, M. Rynge and B. BerrimanExperiences using cloud computing for a scientific workflowapplication Proceedings of the 2nd international workshop onScientific cloud computing, 15–24,2011.

L.F. Bittencourt, E. Madeira, N.L.S. Fonseca Scheduling in hybridclouds Communications Magazine, IEEE, 42–47,2012.

Motivação Conceitos PowerHEFTLookahead HEFT-DynamicAllocationVM Task Clustering Experimentos Conclusões

Bibliografia

B. Aksanli, J. Venkatesh and T. Rosing Using DatacenterSimulation to Evaluate Green Energy Integration Computer,56–64,2012.

D. Kliazovich, P. Bouvry and S.U. Khan GreenCloud: apacket-level simulator of energy-aware cloud computing datacenters The Journal of Supercomputing, 1263–1283,2012.

C. Weiwei and E. Deelman WorkflowSim: A toolkit for simulatingscientific workflows in distributed environments IEEE 8thInternational Conference on E-Science (e-Science), 1-8,2012.