GERAÇÃO DE ALGORITMOS DE ESCALONAMENTO ?· Denison Menezes GERAÇÃO DE ALGORITMOS DE ESCALONAMENTO…

  • View
    215

  • Download
    3

Embed Size (px)

Transcript

  • Denison Menezes

    GERAO DE ALGORITMOS DEESCALONAMENTO PARASIMULAO DE GRADES

    COMPUTACIONAIS

    So Jos do Rio Preto2012

  • Denison Menezes

    GERAO DE ALGORITMOS DEESCALONAMENTO PARASIMULAO DE GRADES

    COMPUTACIONAIS

    Dissertao de Mestrado elaborada juntoao Programa de PsGraduao em Cinciada Computao rea de Concentraoem Sistemas de Computao, como partedos requisitos para a obteno do ttulo deMestre em Cincia da Computao.

    Orientador: Aleardo Manacero Junior

    So Jos do Rio Preto2012

  • Denison Menezes

    GERAO DE ALGORITMOS DE ESCALONAMENTO PARA SIMULAO DEGRADES COMPUTACIONAIS

    Dissertao apresentada para obteno do ttulo de Mestre em Cincia da Com-putao, rea de Concentrao em Sistemas de Computao junto ao Programa dePs-Graduao em Cincia da Computao do Instituto de Biocincia, Letras e Cin-cias Exatas da Universidade Estadual Paulista Jlio de Mesquita Filho, Campus deSo Jos do Rio Preto.

    Banca Examinadora:

  • iii

    A liberdade no tem preo, a mera possibilidade de obt-la j vale a pena.

    Isaac Asimov

  • iv

    Agradecimentos

    Neste momento gostaria de agradecer a todos que estiveram envolvidos, diretamente

    ou indiretamente com o desenvolvimento desse trabalho, aos amigos de longa data, as

    amizades construdas durante o mestrado, e os familiares que me apoiaram e incentiva-

    ram durante todo o trajeto at aqui trilhado.

    No possvel mencionar todos que de alguma forma foram fundamentais para

    realizao deste trabalho, mas devo agradecer meu orientador, Professor Doutor Aleardo

    Manacero Junior por toda ateno e suporte dado sempre que necessitei. Por sua

    pacincia em solucionar as dificuldades encontradas e meus erros, conduzindo para

    uma sada sempre que me deparava com um obstculo. Devo essa dissertao a ele pela

    amizade e ateno.

    Agradeo tambm de forma muito especial a Professora Doutora Renata Spolon

    Lobato. A ela devo, no apenas incontveis indicaes de preciosas leituras, mas,

    sobretudo por todo apoio fornecido, fazendo s vezes de orientador durante a ausncia

    do professor Aleardo.

    Agradeo ao aporte financeiro concedido pela Pr-Reitoria de Ps-Graduao (PROPG)

    da UNESP, e pela infraestrutura necessria presente no laboratrio de Grupo de Siste-

    mas Paralelos e Distribudos (GSPD) da UNESP campus de So Jos do Rio Preto.

    Agradeo aos amigos do GSPD pela contribuio no projeto, ajudas e sugestes

    especialmente ao Diogo Tavares, Aldo Ianelo Guerra, Silas Fernandes, Paulo Henrique

    Oliveira, Gabriel Covello Furlanetto, Rafael Souza Stabile, Gabriel Saraiva, e o Matheus

    Della Croce Oliveira. Aos funcionrios da UNESP pela ateno e esmero com que me

    atenderam durante a realizao da pesquisa.

    Agradeo aos meus pais, Jos Menezes e Maria Benedita de Menezes, e meus ir-

    mos pelo afeto, solidariedade e compreenso. A namorada e companheira, Aline Pe-

    reira Paes, pelo incentivo e por suportar a distncia e ausncia devido dedicao na

    pesquisa.

  • v

    Resumo

    A crescente necessidade por poder computacional, unida com o progresso atingido

    nos computadores pessoais e redes de interconexo, fez surgir diversas propostas, tais

    como grades computacionais, para tornar a computao de alto desempenho mais barata

    e acessvel. Como contraponto, a maior acessibilidade aos recursos para computao

    de alto desempenho oferecida pelas grades, criou um universo de usurios tipicamente

    no especialistas em computao paralela, aumentando a demanda por ferramentas de

    avaliao de desempenho e de apoio ao desenvolvimento de sistemas. Visando criar

    uma ferramenta de simulao de grades com facilidade de uso, mesmo para usurios

    no especialistas em programao, vem sendo desenvolvido o simulador de grades com-

    putacionais iSPD (iconic Simulator of Parallel and Distributed systems). Como o esca-

    lonamento de tarefas essencial na computao distribuda, o iSPD necessitava de uma

    interface para a especificao de escalonadores no ambiente simulado que mantivesse

    os conceitos de fcil modelagem. Este trabalho de pesquisa apresenta a proposta e de-

    senvolvimento de tcnicas que permitam que o usurio do iSPD modele novas polticas

    de escalonamento de forma automatizada e simples. Estas tcnicas foram aplicadas em

    um novo componente capaz de interpretar algoritmos de escalonamento especificados

    pelo usurio adicionando-os a um banco de algoritmos pr-disponibilizados.

    Palavras-chave: Simulao, escalonamento, computao em grade

  • vi

    Abstract

    The increasing demand for more computing power, associated with the progress

    in personal computers and interconnection networks, culminated in proposals to make

    high performance computing cheaper and more accessible such as computer grids. The

    greater accessibility to resources for high performance computing offered by grids cre-

    ated a universe of users lacking of parallel programming expertise, increasing the de-

    mand for tools for performance evaluation and systems development support. Aiming

    for the development of a grid performance evaluation tool that could be easy to use,

    even for people not expert in parallel programming, iSPD (iconic Simulator of Parallel

    and Distributed systems) has been developed. Since task scheduling in distributed sys-

    tems is a critical process, iSPD needed an easy approach to specify scheduling policies

    for a grid. This work presents the development, and its associated results, of a set of

    techniques that allow the iSPDs user to model scheduling policies in an automated and

    simple way. These techniques were applied to a new component capable of interpret-

    ing scheduling algorithms specified by a user, adding them to a pre-built algorithms

    database. Results achieved with this component show that the used approach is right.

    Keywords: Simulation, scheduling, grid computing

  • Sumrio

    Lista de Figuras x

    Lista de Tabelas xii

    1 Introduo 13

    1.1 Motivao . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 14

    1.2 Objetivo . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

    1.3 Organizao do texto . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 16

    2 Simuladores de grades computacionais 18

    2.1 Grade computacional . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 18

    2.1.1 Tipos de Grades Computacionais . . . . . . . . . . . . . . . . . . 21

    2.1.2 Escalonadores . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 22

    2.2 Simuladores de grades computacionais . . . . . . . . . . . . . . . . . . . 24

    2.2.1 SimGrid . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 24

    2.2.2 GridSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 27

    2.2.3 OptorSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 30

    2.2.4 GangSim . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 32

    2.3 iSPD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33

    2.3.1 Criao de modelos . . . . . . . . . . . . . . . . . . . . . . . . . . 34

    2.4 Comparao entre os simuladores de grades computacionais . . . . . . . 36

  • Sumrio viii

    2.5 Consideraes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 39

    3 iSPD 40

    3.1 Arquitetura do iSPD . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 40

    3.1.1 Interface grfica . . . . . . . . . . . . . . . . . . . . . . . . . . . . 41

    3.1.2 Interpretador de modelos . . . . . . . . . . . . . . . . . . . . . . 42

    3.1.3 Motor de simulao . . . . . . . . . . . . . . . . . . . . . . . . . 44

    3.2 Consideraes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 46

    4 Gerao e gerenciamento de escalonadores 47

    4.1 Mdulo de escalonadores . . . . . . . . . . . . . . . . . . . . . . . . . . . 47

    4.1.1 Caso de uso . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 48

    4.1.2 Atividades . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 50

    4.2 Gerao automatizada de escalonadores . . . . . . . . . . . . . . . . . . 51

    4.2.1 Interface grfica do gerador de Escalonadores . . . . . . . . . . . 52

    4.2.2 Gramtica de gerao de algoritmos de escalonamento . . . . . . 53

    4.2.3 Gerenciamento dos escalonadores no iSPD . . . . . . . . . . . . . 57

    4.3 Especificao do Motor de simulao . . . . . . . . . . . . . . . . . . . . 59

    4.3.1 Simulador de eventos discretos . . . . . . . . . . . . . . . . . . . 61

    4.3.2 Modelo de filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 62

    4.3.3 Mestre-escravo e o escalonamento . . . . . . . . . . . . . . . . . . 64

    4.4 Implementao do mdulo de escalonadores . . . . . . . . . . . . . . . . 65

    4.5 Implementao do Motor de simulao . . . . . . . . . . . . . . . . . . . 67

    4.5.1 Simulador de eventos discretos . . . . . . . . . . . . . . . . . . . 68

    4.5.2 Modelo de filas . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

    4.5.3 Escalonamento . . . . . . . . . . . . . . . . . . . . . . . . . . . . 69

    4.6 Consideraes finais . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 71

  • Sumrio ix

    5 Ambiente e resultados experimentais 73

    5.1 Validao do motor de simulao . . . . . . . . . . . . . . . . . . . . . . 73

    5.1.1 Ambiente computacional . . . . . . . . . . . . . . . . . . . . . . . 74

    5.1.2 Algoritmos de escalonamento . . . . . . . . . . . . . . . . . . . . 75

    5.1.3 Resultados . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 77

    5.