Tese de mestrado integrado. Engenharia Informática e Computação. Faculdade de Engenharia. Universidade do Porto. 2010

Este trabalho apresenta uma avaliação do algoritmo EBS, uma política de escalonamento proposta para sistemas de tempo real flexíveis com qualidade de serviço baseado em limites superiores para tempos médios de resposta. Experimentos têm demonstrado propriedades vantajosas da política EBS em servidores Web com diferenciação de serviço. O objetivo do presente estudo é compreender o comportamento da EBS em relação à diferentes parâmetros que descrevem a carga de trabalho. Esse conhecimento é útil para obtenção de um melhor aproveitamento computacional. São apresentados experimentos e resultados que analisam a influência de cada um dos fatores considerados na qualidade do serviço oferecido. A partir desses resultados são tecidas conclusões acerca de abordagens para o dimensionamento de carga e de capacidade do servidor / This Master degree project has presented an evaluation of the EBS algorithm, a scheduling policy proposed for soft real-time systems with quality of service based on upper limits for average response times. Experiments have shown advantageous properties of the EBS policy on Web servers with service differentiation. The aim of this study is to understand the behavior of the EBS in relation to different parameters that describe the workload. This knowledge is useful for obtaining a better use of computing. Experiments and results are presented analyzing the influence of each factor considering the quality of service offered. From these results, conclusions are woven about approaches to the design load and server capacity

Este trabalho apresenta uma avaliação do algoritmo EBS, uma política de escalonamento proposta para sistemas de tempo real flexíveis com qualidade de serviço baseado em limites superiores para tempos médios de resposta. Experimentos têm demonstrado propriedades vantajosas da política EBS em servidores Web com diferenciação de serviço. O objetivo do presente estudo é compreender o comportamento da EBS em relação à diferentes parâmetros que descrevem a carga de trabalho. Esse conhecimento é útil para obtenção de um melhor aproveitamento computacional. São apresentados experimentos e resultados que analisam a influência de cada um dos fatores considerados na qualidade do serviço oferecido. A partir desses resultados são tecidas conclusões acerca de abordagens para o dimensionamento de carga e de capacidade do servidor / This Master degree project has presented an evaluation of the EBS algorithm, a scheduling policy proposed for soft real-time systems with quality of service based on upper limits for average response times. Experiments have shown advantageous properties of the EBS policy on Web servers with service differentiation. The aim of this study is to understand the behavior of the EBS in relation to different parameters that describe the workload. This knowledge is useful for obtaining a better use of computing. Experiments and results are presented analyzing the influence of each factor considering the quality of service offered. From these results, conclusions are woven about approaches to the design load and server capacity

As arquiteturas multiprocessadas heterogêneas têm como objetivo principal a extração de maior desempenho da execução dos processos, por meio da utilização de núcleos apropriados às suas demandas. No entanto, a extração de maior desempenho é dependente de um mecanismo eficiente de escalonamento, capaz de identificar as demandas dos processos em tempo real e, a partir delas, designar o processador mais adequado, de acordo com seus recursos. Este trabalho tem como objetivo propor e implementar o modelo de um escalonador para arquiteturas multiprocessadas heterogêneas, baseado em software e hardware, aplicado ao sistema operacional Linux e ao processador SPARC Leon3, como prova de conceito. Nesse sentido, foram implementados monitores de desempenho dentro dos processadores, os quais identificam as demandas dos processos em tempo real. Para cada processo, sua demanda é projetada para os demais processadores da arquitetura e em seguida é realizado um balanceamento visando maximizar o desempenho total do sistema, distribuindo os processos entre processadores, de modo a diminuir o tempo total de processamento de todos os processos. O algoritmo de maximização Hungarian, utilizado no balanceamento do escalonador, foi desenvolvido em hardware, proporcionando paralelismo e maior desempenho na execução do algoritmo. O escalonador foi validado por meio da execução paralela de diversos benchmarks, resultando na diminuição dos tempos de execução em relação ao escalonador sem suporte à heterogeneidade / Heterogeneous multiprocessor architectures have as main objective the extraction of higher performance from processes through the use of appropriate cores to their demands. However, the extraction of higher performance is dependent on an efficient scheduling mechanism, able to identify in real-time the demands of processes and to designate the most appropriate processor according to their resources. This work aims at design and implementations of a model of a scheduler for heterogeneous multiprocessor architectures based on software and hardware, applied to the Linux operating system and the SPARC Leon3 processor as proof of concept. In this sense, performance monitors have been implemented within the processors, which in real-time identifies the demands of processes. For each process, its demand is projected for the other processors in the architecture and then it is performed a balancing to maximize the total system performance by distributing processes among processors. The Hungarian maximization algorithm, used in balancing scheduler was developed in hardware, providing greater parallelism and performance in the execution of the algorithm. The scheduler has been validated through the parallel execution of several benchmarks, resulting in decreased execution times compared to the scheduler without the heterogeneity support

Made available in DSpace on 2015-02-04T21:45:26Z (GMT). No. of bitstreams: 1 Flavio Viotti.pdf: 1730754 bytes, checksum: f35e841f26e66594080afaa5ef6d730b (MD5) Previous issue date: 2008-09-22 / Aplicações Bag-of-Tasks compostas por tarefas independentes que compartilham arquivos são frequentes em diversas areas da ciência. Exemplos de tais aplicações incluem buscas massivas (como por exemplo, quebramento de chaves), mineração de dados, simulação pelo método de Monte Carlo, manipulação de imagens, entre outros. Grades computacionais são bastante favoráveis para a execução desse tipo de aplicação, provendo capacidade computacional através da agregação de recursos distribuídos. Entretanto, a baixa escalabilidade frequentemente limita o desempenho na execução de tais aplicações. Esta dissertação apresenta uma proposta de implementação de um escalonador de tarefas para grades computacionais, que tem como principal objetivo melhorar a escalabilidade de aplicaçõess Bag-of-Tasks que compartilham arquivos, coordenando de forma mais eficiente a transferência de arquivos pela rede e a distribuição das tarefas entre as máquinas que compoem a grade, com o objetivo de melhorar a escalabilidade das aplicações. As técnicas de escalonamento hierárquico e de agrupamento de tarefas são implementadas pelo escalonador, e resultados experimentais mostram que a implementação proposta permite ganhos de desempenho.

Submitted by Rosivalda Pereira (mrs.pereira@ufma.br) on 2017-05-30T19:56:59Z No. of bitstreams: 1 FernandoCasteloBranco.pdf: 834917 bytes, checksum: 637b3f82aba4cce981014b690d89cb95 (MD5) / Made available in DSpace on 2017-05-30T19:56:59Z (GMT). No. of bitstreams: 1 FernandoCasteloBranco.pdf: 834917 bytes, checksum: 637b3f82aba4cce981014b690d89cb95 (MD5) Previous issue date: 2016-07-25 / In recent decades, the increasing use of mobile technologies has motivated the development of new techniques and algorithms to provide high transmission rates in mobile networks. Among them, LTE (Long Term Evolution) technology is one of the most significant standards for fourth generation (4G) mobile telephony. Due to its high data rates, LTE becomes very attractive to several kinds of applications. However, the quality of the transmissions can be severely impacted by the radio resources scheduling process, since it can lead to fluctuations in the delay and in the application data rates. To perform resource allocation in LTE networks, the scheduler uses various parameters estimated from the radio environment. This process can lead to the occurrence of erroneous estimates, which should be mitigated in order to deal with the inaccuracies of the wireless environments. In this context, this master thesis presents a fuzzy-based downlink scheduler for LTE networks, named PAFS (Performance-Aware Fuzzy Scheduler). The results show that the proposed scheduler promotes a suitable allocation of the radio resources, improving the performance of different QoS (Quality of Service) parameters without compromising the fairness among the system users. / Nas últimas d´ecadas, o aumento da utilização de tecnologias de comunicações móveis tem motivado o desenvolvimento de novas técnicas e algoritmos capazes de prover altas taxas de transmissão em redes celulares. Entre elas, a tecnologia LTE (Long Term Evolution) é um dos padrões mais significativos para a telefonia móvel de quarta geração (4G). Devido às suas elevadas taxas de dados, o LTE torna-se muito atraente para vários tipos de aplicações. No entanto, a qualidade das transmissões pode ser severamente impactada pelo processo de escalonamento de recursos de rádio, uma vez que pode levar a flutuações no atraso e nas taxas de dados das aplicações. Para executar a alocação de recursos em redes LTE, o escalonador utiliza vários parâmetros estimados a partir do ambiente de rádio. Esse processo pode levar à ocorrência de estimativas erradas, o que deve ser mitigado de forma a lidar com as imprecisões dos ambientes sem fio. Neste contexto, este trabalho apresenta um escalonador de enlace de descida baseado em lógica nebulosa chamado PAFS (Performance-Aware Fuzzy Scheduler ). Os resultados mostram que o escalonador proposto promove uma alocação adequada dos recursos de rádio, melhorando o desempenho de diferentes parâmetros de QoS (Quality of Service – Qualidade de Servi¸co) sem comprometer a justiça entre os usuários do sistema.

MAIA, Adyson Magalhães. Um mercanismo para escalonamento de pacotes no uplink da rede LTE no contexto da comunicação máquina-a-máquina. 2013. 66 f. Dissertação (Mestrado em Ciência da Computação)-Universidade Federal do Ceará, Fortaleza, 2013. / Submitted by Anderson Silva Pereira (anderson.pereiraaa@gmail.com) on 2017-01-10T17:01:54Z No. of bitstreams: 1 2013_dis_ammaia.pdf: 1825299 bytes, checksum: 3f411e2308c0764db18086299cea938c (MD5) / Approved for entry into archive by Rocilda Sales (rocilda@ufc.br) on 2017-01-11T15:37:41Z (GMT) No. of bitstreams: 1 2013_dis_ammaia.pdf: 1825299 bytes, checksum: 3f411e2308c0764db18086299cea938c (MD5) / Made available in DSpace on 2017-01-11T15:37:41Z (GMT). No. of bitstreams: 1 2013_dis_ammaia.pdf: 1825299 bytes, checksum: 3f411e2308c0764db18086299cea938c (MD5) Previous issue date: 2013 / Cellular networks are expected to play an important role in the future of Internet of Things (IoT) and in the Machine-to-Machine (M2M) communication with the LTE network gaining increasing highlights for this purpose. However, improvements in the LTE network are necessary because of the intrinsic characteristics of M2M communication, such as the large number of devices and the diversity of the requirements of their applications, which differen- tiate from the Human-to-Human (H2H) communication for which the network was initially designed. Among these improvements, it includes improving the uplink packet scheduler of LTE standard to dealing the M2M communication and meets your requirements without serious impacts on the H2H communication. This work proposes a mechanism for the uplink packet scheduler in the context of M2M communication that uses current and past information from the network and each device to satisfy their requirements of Quality of Service (QoS), avoid the problem of starvation and control the congestion caused by these devices. The results indicate that the proposal can reduce the impact of the M2M communication over the H2H and ensure justice in resource allocation, however, the level of satisfaction of QoS requirements decreases with increasing of H2H traffic. / As redes celulares são esperadas para desempenhar um importante papel no futuro da Internet das Coisas (Internet of Things - IoT) e na comunicação Máquina-a-Máquina (Machine-to-Machine - M2M), com a rede LTE ganhando cada vez mais destaque tanto da academia quanto da indústria na implantação deste cenário. Contudo, melhorias na rede LTE são necessárias devido às características intrínsecas da comunicação M2M, como a grande quantidade de dispositivos e a diversidade nos requerimentos das suas aplicações, que os diferenciam da comunicação Humano-a-Humano (Human-to-Human - H2H) para a qual a rede foi inicialmente projetada. Dentre essas melhorias, está o aperfeiçoamento no escalonamento de pacotes no uplink definido no padrão para que trate o caso da comunicação M2M e atenda aos seus requerimentos sem causar grandes impactos na comunicação H2H. Este trabalho propõe um mecanismo para o escalonamento de pacotes no uplink da rede LTE no contexto da comunicação M2M que utiliza as informações atuais e passadas da rede e de cada dispositivo para satisfazer os requisitos de Qualidade de Serviço (QoS) dos dispositivos M2M, evitar o problema de inanição e controlar o congestionamento causado por estes dispositivos. Os resultados obtidos indicam que a proposta consegue reduzir o impacto da comunicação M2M sobre a H2H e garantir justiça na alocação de recursos. No entanto, o nível de satisfação dos requisitos de QoS dos dispositivos M2M diminui com o aumento do tráfego H2H.

As arquiteturas multiprocessadas heterogêneas têm como objetivo principal a extração de maior desempenho da execução dos processos, por meio da utilização de núcleos apropriados às suas demandas. No entanto, a extração de maior desempenho é dependente de um mecanismo eficiente de escalonamento, capaz de identificar as demandas dos processos em tempo real e, a partir delas, designar o processador mais adequado, de acordo com seus recursos. Este trabalho tem como objetivo propor e implementar o modelo de um escalonador para arquiteturas multiprocessadas heterogêneas, baseado em software e hardware, aplicado ao sistema operacional Linux e ao processador SPARC Leon3, como prova de conceito. Nesse sentido, foram implementados monitores de desempenho dentro dos processadores, os quais identificam as demandas dos processos em tempo real. Para cada processo, sua demanda é projetada para os demais processadores da arquitetura e em seguida é realizado um balanceamento visando maximizar o desempenho total do sistema, distribuindo os processos entre processadores, de modo a diminuir o tempo total de processamento de todos os processos. O algoritmo de maximização Hungarian, utilizado no balanceamento do escalonador, foi desenvolvido em hardware, proporcionando paralelismo e maior desempenho na execução do algoritmo. O escalonador foi validado por meio da execução paralela de diversos benchmarks, resultando na diminuição dos tempos de execução em relação ao escalonador sem suporte à heterogeneidade / Heterogeneous multiprocessor architectures have as main objective the extraction of higher performance from processes through the use of appropriate cores to their demands. However, the extraction of higher performance is dependent on an efficient scheduling mechanism, able to identify in real-time the demands of processes and to designate the most appropriate processor according to their resources. This work aims at design and implementations of a model of a scheduler for heterogeneous multiprocessor architectures based on software and hardware, applied to the Linux operating system and the SPARC Leon3 processor as proof of concept. In this sense, performance monitors have been implemented within the processors, which in real-time identifies the demands of processes. For each process, its demand is projected for the other processors in the architecture and then it is performed a balancing to maximize the total system performance by distributing processes among processors. The Hungarian maximization algorithm, used in balancing scheduler was developed in hardware, providing greater parallelism and performance in the execution of the algorithm. The scheduler has been validated through the parallel execution of several benchmarks, resulting in decreased execution times compared to the scheduler without the heterogeneity support

Submitted by Renata Lopes (renatasil82@gmail.com) on 2017-05-15T14:39:21Z No. of bitstreams: 1 thiagomarquessoares.pdf: 1372109 bytes, checksum: 0decc31aa35ac2d0364f017e2f671861 (MD5) / Approved for entry into archive by Adriana Oliveira (adriana.oliveira@ufjf.edu.br) on 2017-05-17T15:59:41Z (GMT) No. of bitstreams: 1 thiagomarquessoares.pdf: 1372109 bytes, checksum: 0decc31aa35ac2d0364f017e2f671861 (MD5) / Made available in DSpace on 2017-05-17T15:59:41Z (GMT). No. of bitstreams: 1 thiagomarquessoares.pdf: 1372109 bytes, checksum: 0decc31aa35ac2d0364f017e2f671861 (MD5) Previous issue date: 2017-03-09 / CAPES - Coordenação de Aperfeiçoamento de Pessoal de Nível Superior / O modelo LogP foi desenvolvido em 1993 para medir os efeitos da latência de comunicação, ocupação dos processadores e banda passante em multiprocessadores com memória distribuída. A ideia era caracterizar multiprocessadores de memória distribuída usando estes parâmetros chave, analisando seus impactos no desempenho. Este trabalho propõe um novo modelo, baseado no LogP, que descreve a influência destes parâmetros no desempenho de aplicações regulares executadas em um agregado (cluster) de computadores heterogêneos. O modelo considera que um agregado heterogêneo é composto por diferentes tipos de processadores, aceleradores e controladores de rede. Os resultados mostram que o pior erro nas estimativas feitas pelo modelo para o tempo de execução paralelo foi de 19,2%, e, em muitos casos, a execução estimada foi igual ou próxima do tempo real. Além disso, com base neste modelo, foi desenvolvido um escalonador, que baseado nas características da aplicação e do ambiente, escolhe um subconjunto de componentes que minimizem o tempo total de execução paralelo. O escalonador obteve êxito na escolha da melhor configuração para a execução de aplicações com diferentes comportamentos. / The LogP model was proposed in 1993 to measure the effects of communication latency, processor occupancy and bandwidth in distributed memory multiprocessors. The idea was to characterize distributed memory multiprocessor using these key parameters and study their impact on performance in simulation environments. This work proposes a new model, based on LogP, that describes the impacts on performance of regular applications executing on a heterogeneous cluster. The model considers that a heterogeneous cluster is composed of distinct types of processors, accelerators and networks. The results show that the worst error in the estimations of the parallel execution time was about 19,2%, and, in many cases, the estimated execution time is equal to or very close to the real one. In addition, based on this model, a scheduler was developed. Based on the applications and computational environment characteristics, the scheduler chooses the subset of processors, accelerators and networks that minimize the parallel execution time. For applications with different behaviors, the scheduler successfully chose the best configuration.

Made available in DSpace on 2016-08-29T15:33:23Z (GMT). No. of bitstreams: 1 tese_9278_Ata 337º.pdf: 642020 bytes, checksum: 75b1ea9fbbced5ea1bee7a6056858c98 (MD5) Previous issue date: 2015-10-13 / Este trabalho busca melhorar o processo migratório de máquinas virtuais implementando um escalonador de migrações baseado em dados provenientes de uma caracterização da carga de trabalho em uma nuvem privada. As migrações são necessárias para balanceamento de carga entre os hosts, contudo podem impactar negativamente no desempenho dos serviços. Por meio da caracterização empírica da nuvem estudada, foi observado uma grande desproporção entre o tempo de uma migração simples (menor tempo) e uma simultânea (maior tempo). Com base nesses dados, foi proposto um algoritmo para realizar o escalonamento das migrações, de forma serial (removendo a simultaneidade) e fundamentado no Shortest Job First. Os resultados do escalonador mostraram-se melhores em quase sua totalidade quando comparados ao arcabouço tecnológico base deste trabalho e o VMware. Foi possível reduzir o tempo médio e a quantidade de migrações ocorridas. / This work seeks to improve the virtual machines migration process implementing a migration scheduler based on data from a workload characterization in a private cloud. The migrations are necessary to load balancing among hosts, nevertheless they can negatively impact the performance of services. By empirical characterization of the studied cloud, it was observed a large disproportion between the time of a simple migration (shorter time) and a simultaneous one (longer time). Based on these data, it was proposed an algorithm to do the migrations scheduling, in a serial way (removing the simultaneity) and grounded on Shortest Job First. The results of the scheduler showed up better almost in its entirety compared to the VMware, it was possible to decrease 33% in the average time in 93% of the occurred migrations (total of 765 migrations).