PIM ¡]Processor-in-Memory¡^ architectures have been proposed in recent years for the purpose of reducing performance gap between processor and memory. This new class of computer architectures attempts to integrate processor and memory on a single one chip¡CWe proposed a new transformation and parallelizing system named SAGE ¡]Statement Analysis Group Evaluation¡^to fully utilize the host processor and memory processors in PIM systems. In this thesis, we focus on designing a load-balance optimization mechanism for the job scheduling. The experimental results of this mechanism are also discussed.

Este trabalho consiste na elaboração de um modelo para programação de atividades e alocação de técnicos que executam tarefas de instalação, manutenção preventiva e visita diagnóstica em equipamentos utilizados na produção de bens de consumo em escala industrial. O modelo utiliza técnicas de pesquisa operacional visando minimizar os custos envolvidos. O modelo em questão descreve as fases para a elaboração da programação das atividades e da alocação dos técnicos para executá-las, trazendo como contribuição ao tema restrições como acordo sindical de banco de horas celebrado com os empregados e nível de serviço prestado ao cliente. O presente modelo considera ainda eventuais penalidades existentes por atraso no início da instalação dos equipamentos comercializados. O modelo define as atividades que deverão ser atendidas prioritariamente e os impactos econômicos de tal decisão, distribuindo a carga de trabalho de forma mais uniforme possível entre os técnicos dentro do horizonte de planejamento. / This paper presents a model to schedule the activities and allocation of technicians that perform tasks of installation, preventive maintenance and diagnostic visits in equipments used in the production of consuming goods in industrial scale. The model uses operation research techniques aiming at minimizing the costs involved in these activities. The model in question describes the phases of scheduling and allocation of technicians in order to perform their activities. It brings as contribution to this theme constrains such as union agreement on Accumulation of hours regime entered with the employees and the level of service rendered to the client. This model also considers the occasional existing penalties due to delays at the beginning of the installation of the sold equipments. This model defines which activities must be prioritized as well as their economic impacts, distributing the workload in the most even way among the technicians within the planning horizon.

Considerando-se o contexto de gerenciamento energético em grades móveis, neste trabalho foram propostos dois algoritmos de escalonamento (Maximum Regret e Greedy) que, além de minimizar o consumo de energia, visam assegurar o cumprimento dos requisitos de qualidade de serviço das aplicações submetidas pelos usuários. Tais algoritmos foram projetados a partir de soluções heurísticas para o problema de escalonamento ciente de consumo de energia em grades móveis, que foi modelado como um problema de otimização envolvendo variáveis binárias. Por meio de experimentos, que consideraram tanto cenários estáticos quanto dinâmicos, foi demonstrada a viabilidade dos algoritmos de escalonamento propostos em relação à redução do consumo de energia. Em seu pior caso, o algoritmo Maximum Regret foi 12,18% pior que o referencial determinado pela melhor solução do solver Gurobi; já no pior caso do algoritmo Greedy, tal diferença foi de apenas 8,14% / Considering the context of energy management in mobile grids, this work proposes two scheduling algorithms (Maximum Regret and Greedy) that aim not only to reduce the energy consumption of the mobile devices, but also to ensure the QoS (Quality of Service) requirements of the running applications. These algorithms were designed based on heuristics for the energy aware scheduling problem in mobile grids, which was modeled as an optimization problem with integer variables. The performances of the proposed scheduling algorithms were evaluated by an extensive set of experiments, which demonstrated the feasibility of the adopted approach regarding energy consumption minimization. In its worst case, the Maximum Regret algorithm was 12.18% worse than the best solution provided by the Gurobi solver. While in the Greedys worst case the performance difference was just 8.14%

Este trabalho consiste na elaboração de um modelo para programação de atividades e alocação de técnicos que executam tarefas de instalação, manutenção preventiva e visita diagnóstica em equipamentos utilizados na produção de bens de consumo em escala industrial. O modelo utiliza técnicas de pesquisa operacional visando minimizar os custos envolvidos. O modelo em questão descreve as fases para a elaboração da programação das atividades e da alocação dos técnicos para executá-las, trazendo como contribuição ao tema restrições como acordo sindical de banco de horas celebrado com os empregados e nível de serviço prestado ao cliente. O presente modelo considera ainda eventuais penalidades existentes por atraso no início da instalação dos equipamentos comercializados. O modelo define as atividades que deverão ser atendidas prioritariamente e os impactos econômicos de tal decisão, distribuindo a carga de trabalho de forma mais uniforme possível entre os técnicos dentro do horizonte de planejamento. / This paper presents a model to schedule the activities and allocation of technicians that perform tasks of installation, preventive maintenance and diagnostic visits in equipments used in the production of consuming goods in industrial scale. The model uses operation research techniques aiming at minimizing the costs involved in these activities. The model in question describes the phases of scheduling and allocation of technicians in order to perform their activities. It brings as contribution to this theme constrains such as union agreement on Accumulation of hours regime entered with the employees and the level of service rendered to the client. This model also considers the occasional existing penalties due to delays at the beginning of the installation of the sold equipments. This model defines which activities must be prioritized as well as their economic impacts, distributing the workload in the most even way among the technicians within the planning horizon.

Considerando-se o contexto de gerenciamento energético em grades móveis, neste trabalho foram propostos dois algoritmos de escalonamento (Maximum Regret e Greedy) que, além de minimizar o consumo de energia, visam assegurar o cumprimento dos requisitos de qualidade de serviço das aplicações submetidas pelos usuários. Tais algoritmos foram projetados a partir de soluções heurísticas para o problema de escalonamento ciente de consumo de energia em grades móveis, que foi modelado como um problema de otimização envolvendo variáveis binárias. Por meio de experimentos, que consideraram tanto cenários estáticos quanto dinâmicos, foi demonstrada a viabilidade dos algoritmos de escalonamento propostos em relação à redução do consumo de energia. Em seu pior caso, o algoritmo Maximum Regret foi 12,18% pior que o referencial determinado pela melhor solução do solver Gurobi; já no pior caso do algoritmo Greedy, tal diferença foi de apenas 8,14% / Considering the context of energy management in mobile grids, this work proposes two scheduling algorithms (Maximum Regret and Greedy) that aim not only to reduce the energy consumption of the mobile devices, but also to ensure the QoS (Quality of Service) requirements of the running applications. These algorithms were designed based on heuristics for the energy aware scheduling problem in mobile grids, which was modeled as an optimization problem with integer variables. The performances of the proposed scheduling algorithms were evaluated by an extensive set of experiments, which demonstrated the feasibility of the adopted approach regarding energy consumption minimization. In its worst case, the Maximum Regret algorithm was 12.18% worse than the best solution provided by the Gurobi solver. While in the Greedys worst case the performance difference was just 8.14%

Orientador: Jacques Wainer / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-20T14:02:06Z (GMT). No. of bitstreams: 1 Tampelini_LeonardoGarcia_M.pdf: 834632 bytes, checksum: b0f1d3f3d777417870d8ddd0d317ab8e (MD5) Previous issue date: 2012 / Resumo: Com a disseminação de tecnologias de gerenciamento empresarial, empresas procuram promover serviços mais ágeis e de maior qualidade. Neste contexto, áreas como gerenciamento de workflow vêm contribuindo para uma melhor organização na distribuição de tarefas. A aproximação da área de escalonamento com workflow demonstra um grande potencial para atender tais requisitos; porém, uma escassez de trabalhos voltados ao tratamento de estruturas de roteamento paralelas, comumente encontradas em modelos de workflow, é perceptível na literatura de escalonamento. Este trabalho tem por objetivo aproximar essas duas áreas apresentando três novas abordagens de escalonamento voltadas à ordenação de casos dentro de estruturas de roteamento paralelas (AND). Para alcançar tal objetivo, um conjunto de simuladores foi implementado representando o ambiente dinâmico de workflow, suas incertezas, bem como os diferentes cenários onde estruturas do tipo AND podem ocorrer. O desempenho de tais políticas foi comparado com regras amplamente utilizadas em sistemas de workflow, como FIFO (First In First Out), EDD (Earliest Due Date) e SPT (Shortest Processing Time). A análise dos resultados foi efetivada por meio de uma análise de variância (ANOVA) juntamente com o teste de Tukey. Os resultados mostram que é mais vantajoso utilizar técnicas específicas para estrutura de roteamento AND do que apenas aplicar as técnicas mais utilizadas / Abstract: With the dissemination of business management technologies, companies look for to promoting faster services with higher quality. In this context, areas such as workflow management have contributed to a better organization in the distribution of tasks. The approach between scheduling area and workflow area shows great potential to attend these requirements, but a lack of studies directed to the treatment of parallel routing structures, commonly found in workflow models, is apparent escalation in the literature about scheduling. This work aims to approximate these two areas, presenting three new scheduling approaches, directed to the raging of the cases within routing structures parallel (AND). To reach this objective a set of simulators was implemented, representing the dynamic workflow environment, their uncertainties, as well as the different scenarios where that structures such as AND may occur. The performance of these politics was compared with rules widely used in workflow systems, such as FIFO (First In First Out), EDD (Earliest Due Date) and SPT (Shortest Processing Time). The results show that it is more advantageous to use techniques focused on AND routing structure than only apply the most utilized ones / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

A computação paralela permite uma série de vantagens para a execução de aplicações de grande porte, sendo que o uso efetivo dos recursos computacionais paralelos é um aspecto relevante da computação de alto desempenho. Este trabalho apresenta uma metodologia que provê a execução, de forma automatizada, de aplicações paralelas baseadas no modelo BSP com tarefas heterogêneas. É considerado no modelo adotado, que o tempo de computação de cada tarefa secundária não possui uma alta variância entre uma iteração e outra. A metodologia é denominada de ASE e é composta por três etapas: Aquisição (Acquisition), Escalonamento (Scheduling) e Execução (Execution). Na etapa de Aquisição, os tempos de processamento das tarefas são obtidos; na etapa de Escalonamento a metodologia busca encontrar a distribuição de tarefas que maximize a velocidade de execução da aplicação paralela, mas minimizando o uso de recursos, por meio de um algoritmo desenvolvido neste trabalho; e por fim a etapa de Execução executa a aplicação paralela com a distribuição definida na etapa anterior. Ferramentas que são aplicadas na metodologia foram implementadas. Um conjunto de testes aplicando a metodologia foi realizado e os resultados apresentados mostram que os objetivos da proposta foram alcançados. / Parallel computing allows for a series of advantages on the execution of large applications and the effective use of parallel resources is an important aspect in the High Performance Computing. This work presents a methodology to provide the execution, in an automated way, of parallel applications based on BSP model with heterogeneous tasks. In this model it is assumed that the computation time between iterations does not have a high variance. The methodology is entitled ASE and it is composed by three stages: Acquisition, Scheduling and Execution. In the Acquisition step, the tasks\' processing time are obtained; In the Scheduling step, the methodology finds the ideal arrangement to distribute the tasks to maximize the execution speed and, simultaneously, minimize the use of resources. This is made using an algorithm developed in this work; and lastly the Execution step, where the parallel application is executed in the distribution defined in the previous step. The tools used in the methodology were implemented. A set of tests to apply the methodology were made and the results shown that the objectives were reached.

A computação paralela permite uma série de vantagens para a execução de aplicações de grande porte, sendo que o uso efetivo dos recursos computacionais paralelos é um aspecto relevante da computação de alto desempenho. Este trabalho apresenta uma metodologia que provê a execução, de forma automatizada, de aplicações paralelas baseadas no modelo BSP com tarefas heterogêneas. É considerado no modelo adotado, que o tempo de computação de cada tarefa secundária não possui uma alta variância entre uma iteração e outra. A metodologia é denominada de ASE e é composta por três etapas: Aquisição (Acquisition), Escalonamento (Scheduling) e Execução (Execution). Na etapa de Aquisição, os tempos de processamento das tarefas são obtidos; na etapa de Escalonamento a metodologia busca encontrar a distribuição de tarefas que maximize a velocidade de execução da aplicação paralela, mas minimizando o uso de recursos, por meio de um algoritmo desenvolvido neste trabalho; e por fim a etapa de Execução executa a aplicação paralela com a distribuição definida na etapa anterior. Ferramentas que são aplicadas na metodologia foram implementadas. Um conjunto de testes aplicando a metodologia foi realizado e os resultados apresentados mostram que os objetivos da proposta foram alcançados. / Parallel computing allows for a series of advantages on the execution of large applications and the effective use of parallel resources is an important aspect in the High Performance Computing. This work presents a methodology to provide the execution, in an automated way, of parallel applications based on BSP model with heterogeneous tasks. In this model it is assumed that the computation time between iterations does not have a high variance. The methodology is entitled ASE and it is composed by three stages: Acquisition, Scheduling and Execution. In the Acquisition step, the tasks\' processing time are obtained; In the Scheduling step, the methodology finds the ideal arrangement to distribute the tasks to maximize the execution speed and, simultaneously, minimize the use of resources. This is made using an algorithm developed in this work; and lastly the Execution step, where the parallel application is executed in the distribution defined in the previous step. The tools used in the methodology were implemented. A set of tests to apply the methodology were made and the results shown that the objectives were reached.

Orientador: Akebo Yamakami / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-08-06T10:47:10Z (GMT). No. of bitstreams: 1 Bonfim_TatianeRegina_D.pdf: 1154007 bytes, checksum: 1b6dd7bc9c2e3eef16c1e3258710730c (MD5) Previous issue date: 2006 / Resumo: Este trabalho apresenta uma nova abordagem de resolução, por algoritmo memético e pela coevolução de algoritmo memético com redes neurais, para o problema de escalonamento de tarefas em máquinas paralelas idênticas e para o problema de job shop com parâmetros precisos. Para os problemas de escalonamento com parâmetros com incertezas, onde os parâmetros não são precisamente conhecidos, toma-se dificil classificar um determinado escalonamento ótimo. A noção de ótimo também torna-se imprecisa e o grau de otimalidade de um dado escalonamento ("o quanto um escalonamento é ótimo") pode ser caracterizada por um número fuzzy. Foi aplicado também o conceito de otimalidade possível para medir a possibilidade de um determinado escalonamento ser ótimo. O algoritmo memético foi aplicado para encontrar soluções para o problema, a rede neural foi aplicada para encontrar a função de fitness das soluções encontradas pelo algoritmo memético, e o conceito de possibilidade foi aplicado para avaliar as melhores soluções. Foram utilizadas as redes neurais backpropagation e com aprendizado por reforço para encontrar o valor da função de fitness. As simulações mostraram que as redes neurais apresentaram uma boa performance na coevolução com o algoritmo memético e na resolução dos problemas, e mostraram que o conceito de possibilidade teve uma boa perfomance na avaliação da otimalidade das soluções / Abstract: This work presents a new approach for the resolution of the problem of identical parallel machine scheduling and job shop scheduling with precise parameters, with memetic algorithm and memetic algorithm coevolving with neural networks. For problems with parameters with uncertainties, where the parameters of the problem are not precisely known, it is difficult to say in prior which schedule will be optimal. The notion of optimal also becomes imprecise and the degree of optimality of a given schedule ("how much a schedule is optimal") can be characterized by a fuzzy number. We was used also the concepts of possibility to measure the possibility of a given schedule be optimal. Memetic algorithm has been used to find the solutions of the problem, the neural network has been used to find the fitness function of these solutions, and the concept of possibility has been used to evaluate the best solutions. We was used neural networks with backpropagation and reinforcement learning to find the fitness function. Simulations showed that the neural networks presents a good performance in the coevolution of the memetic algorithm and in the resolution of the problems, and showed that the concept of possibility present a good performance in the evaluation of solutions optimality / Doutorado / Telecomunicações e Telemática / Doutor em Engenharia Elétrica

Orientador: Nelson Luis Saldanha da Fonseca / Tese (doutorado ) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-15T11:13:39Z (GMT). No. of bitstreams: 1 Batista_DanielMacedo_D.pdf: 4822882 bytes, checksum: 0875aace17a80193a116db65097ea804 (MD5) Previous issue date: 2010 / Resumo: Para que escalonadores em grades derivem escalonamentos, é necessário que se forneçam as demandas das aplicações e as disponibilidades dos recursos das grades. No entanto, a falta de controle centralizado, o desconhecimento dos usuários e a imprecisão das ferramentas de medição fazem com que as informações fornecidas aos escalonadores difiram dos valores reais que deveriam ser considerados para se obter escalonamentos quase-ótimos. A presente Tese introduz dois escalonadores de tarefas robustos às incertezas das informações providas como entrada ao escalonador. Um dos escalonadores lida com informações imprecisas sobre as demandas das aplicações, enquanto que o outro considera tanto imprecisões das demandas quanto da disponibilidade de recursos. A eficácia e a eficiência dos escalonadores robustos às incertezas são avaliadas através de simulação.Comparam-se os escalonamentos gerados pelos escalonadores robustos com os produzidos por escalonadores sensíveis às informações incertas. A eficácia de estimadores de largura de banda disponível são, também, avaliadas, através de medição, a luz da adoção destes em sistemas de grades, a fim de que se possa utilizar suas estimativas como informação de entrada a escalonadores robustos / Abstract: Schedulers need information on the application demands and on the grid resource availability as input to derive efficient schedules for the tasks of a grid application. However, information provided to schedulers differ from the true values due to the lack of central control in a grid and the lack of ownership of resources as well as the precision of estimations provided by measurement tools. This thesis introduces two robust schedulers based on fuzzy optimization. The first scheduler deals with uncertainties on the application demands while the other with uncertainties of both application demands and resource availability. The effectiveness of these schedulers are evaluated via simulation and the schedules produced by them are compared to those of their non-fuzzy counterpart. Moreover, the efficacy of available bandwidth estimators is assessed in order to evaluate their use in grid systems for providing schedulers with useful input information / Doutorado / Sistemas de Computação, Redes Multimidia / Doutor em Ciência da Computação