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,[email protected]
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?
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.