FundaÃÃo Cearense de Apoio ao Desenvolvimento Cientifico e TecnolÃgico / Diversos projetos nacionais e internacionais, como o dados.gov.br e o Linking Open Data, foram desenvolvidos com a finalidade de fomentar a criaÃÃo da Web de dados, que surge como uma nova abordagem para efetivamente publicar, recuperar e descrever dados distribuÃdos na Web. Diante desse cenÃrio, tais projetos enfrentam o desafio de criar e manter os dados estruturados que seguem os princÃpios do Linked Data, descritos no modelo de dados RDF e representados por ontologias. Esse desafio envolve outras tarefas complexas, tais como: reusar o vocabulÃrio das ontologias largamente utilizadas na elaboraÃÃo de novas ontologias (com a finalidade de promover a interoperabilidade e a integraÃÃo entre as aplicaÃÃes) e permitir a detecÃÃo de inconsistÃncias entre os termos de uma determinada ontologia. Com o objetivo de propor uma soluÃÃo para esse desafio, o problema de gerenciamento de ontologias foi abordado nesta dissertaÃÃo. Na literatura, existe uma grande variedade de trabalhos disponÃveis com diferentes enfoques e processos que propÃem o gerenciamento de ontologias. Entretanto, poucos trabalhos preocupam-se em auxiliar o especialista do domÃnio na elaboraÃÃo de uma ontologia que representa um entendimento correto sobre a semÃntica das ontologias envolvidas, visto que, para isso faz-se necessÃrio considerar as restriÃÃes lÃgicas das ontologias originais e propagÃ-las para as novas ontologias. AlÃm disso, foi percebido que, nos trabalhos anteriores, existe a necessidade de utilizar vÃrias ferramentas durante o processo de gerenciamento de ontologias, o que aumenta o esforÃo manual a ser despendido pelo especialista do domÃnio na elaboraÃÃo de novas ontologias. Sendo assim, a fim de oferecer algumas funcionalidades diferenciadas e de modo integrado ao gerenciamento de ontologias, foi desenvolvido um protÃtipo, denominado OntologyManagementTool. O protÃtipo desenvolvido considera as ontologias nÃo apenas como vocabulÃrio, mas como teorias lÃgicas, isto Ã, leva em conta tambÃm o seu conjunto de restriÃÃes. Cada ontologia manipulada à primeiramente normalizada para atender ao formalismo da LÃgica Descritiva, com um nÃmero especÃfico de restriÃÃes. Posteriormente, essa ontologia à transformada em um grafo de restriÃÃes, e assim, à possÃvel gerenciÃ-la a partir de um conjunto de operaÃÃes algÃbricas sobre o grafo. Destacam-se as seguintes operaÃÃes: uniÃo, interseÃÃo, diferenÃa eprojeÃÃo. ApÃs a execuÃÃo de cada uma dessas operaÃÃes, à possÃvel obter uma nova ontologia, bem como, o mapeamento entre as ontologias envolvidas. O trabalho proposto teve a sua aplicabilidade comprovada a partir de experimentos executados em ontologias descrevendo fontes de dados reais. Os resultados obtidos mostraram que a complexidade para gerar o grafo de restriÃÃes à linear em relaÃÃo ao nÃmero de restriÃÃes das ontologias; jà a complexidade do processamento das operaÃÃes algÃbricas (interseÃÃo, diferenÃa e projeÃÃo) à quadrÃtica em relaÃÃo ao nÃmero de vÃrtices do grafo de restriÃÃes, sendo importante evidenciar que o fator determinante para obtenÃÃo dessa complexidade à o procedimento escolhido para lidar com as restriÃÃes de inclusÃo, denominado fecho transitivo.

nÃo hà / This work presents a scale-space based approach to assist dynamic resource provisioning. The application of this theory makes it possible to eliminate the presence of irrelevant information from a signal that can potentially induce wrong or late decision making. Dynamic provisioning involves increasing or decreasing the amount of resources allocated to an application in response to workload changes. While monitoring both resource consumption and application-specic metrics is fundamental in this process since the latter is of great importance to infer information about the former, dealing with these pieces of information to provision resources in dynamic environments poses a big challenge. The presence of unwanted characteristics, or noise, in a signal that represents the monitored metrics favors misleading interpretations and is known to aect forecast models. Even though some forecast models are robust to noise, reducing its inuence may decrease training time and increase eciency. Because a dynamic environment demands decision making and predictions on a quickly changing landscape, approximations are necessary. Thus it is important to realize how approximations give rise to limitations in the forecasting process. On the other hand, being aware of when detail is needed, and when it is not, is crucial to perform ecient dynamic forecastings. In a cloud environment, resource provisioning plays a key role for ensuring that providers adequately accomplish their obligation to customers while maximizing the utilization of the underlying infrastructure. Experiments are shown considering simulation of both reactive and proactive strategies scenarios with a real-world trace that corresponds to access rate. Results show that embodying scale-space theory in the decision making stage of dynamic provisioning strategies is very promising. It both improves workload analysis, making it more meaningful to our purposes, and lead to better predictions.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / Clustering is a data mining technique that brings together elements of a data set such so that the elements of a same group are more similar to each other than to those from other groups. This thesis studied the problem of processing the clustering based on density DBSCAN algorithm distributedly through the MapReduce paradigm. In the distributed processing it is important that the partitions are processed have approximately the same size, provided that the total of the processing time is limited by the time the node with a larger amount of data leads to complete the computation of data assigned to it. For this reason we also propose a data set partitioning strategy called G2P, which aims to distribute the data set in a balanced manner between partitions and takes into account the characteristics of DBSCAN algorithm. More Specifically, the G2P strategy uses grid and graph structures to assist in the division of space low density regions. Distributed DBSCAN the algorithm is done processing MapReduce two stages and an intermediate phase that identifies groupings that can were divided into more than one partition, called candidates from merging. The first MapReduce phase applies the algorithm DSBCAN the partitions individually. The second and checks correcting, if necessary, merge candidate clusters. Experiments using data sets demonstrate that true G2P-DBSCAN strategy overcomes the baseline adopted in all the scenarios, both at runtime and quality of obtained partitions. / ClusterizaÃao à uma tÃcnica de mineraÃÃo de dados que agrupa elementos de um conjunto de dados de forma que os elementos que pertencem ao mesmo grupo sÃo mais semelhantes entre si que entre elementos de outros grupos. Nesta dissertaÃÃo nÃs estudamos o problema de processar o algoritmo de clusterizaÃÃo baseado em densidade DBSCAN de maneira distribuÃda atravÃs do paradigma MapReduce. Em processamentos distribuÃdos à importante que as partiÃÃes de dados a serem processadas tenham tamanhos proximadamente iguais, uma vez que o tempo total de processamento à delimitado pelo tempo que o nà com uma maior quantidade de dados leva para finalizar a computaÃÃo dos dados a ele atribuÃdos. Por essa razÃo nÃs tambÃm propomos uma estratÃgia de particionamento de dados, chamada G2P, que busca distribuir o conjunto de dados de forma balanceada entre as partiÃÃes e que leva em consideraÃÃo as caracterÃsticas do algoritmo DBSCAN. Mais especificamente, a estratÃgia G2P usa estruturas de grade e grafo para auxiliar na divisÃo do espaÃo em regiÃes de baixa densidade. Jà o processamento distribuÃdo do algoritmo DBSCAN se dà por meio de duas fases de processamento MapReduce e uma fase intermediÃria que identifica clusters que podem ter sido divididos em mais de uma partiÃÃo, chamados de candidatos à junÃÃo. A primeira fase de MapReduce aplica o algoritmo DSBCAN nas partiÃÃes de dados individualmente, e a segunda verifica e corrige, caso necessÃrio, os clusters candidatos à junÃÃo. Experimentos utilizando dados reais mostram que a estratÃgia G2P-DBSCAN se comporta melhor que a soluÃÃo utilizada para comparaÃÃo em todos os cenÃrios considerados, tanto em tempo de execuÃÃo quanto em qualidade das partiÃÃes obtidas.

CoordenaÃÃo de AperfeÃoamento de Pessoal de NÃvel Superior / A noÃÃo de jogo eletrÃnico remete a entretenimento reservado Ãs horas vagas, mas, alÃm de uma indÃstria bilionÃria, tambÃm à origem potencial de diversos temas de pesquisa, tanto voltados a suas respectivas Ãreas quanto de interesse da prÃpria indÃstria de jogos. Nesse contexto, nas Ãltimas dÃcadas, foram produzidos trabalhos que lidam com esse tipo de produto como base para problemas a serem tratados pela teoria dos algoritmos. Neste trabalho trazemos resultados de complexidade e algoritmos relacionados a 3 jogos com caracterÃsticas em comum, Bloxorz, On The Edge e Bobbin 3D. / The electronic game concept refers to reserved entertainment to spare time , but in addition to a billion dollar industry , is also potential source of several research topics , both directed to their respective areas of interest as own gaming industry . In this context, in recent decades, work has been done to deal with this type of product based on for problems to be addressed by the theory of algorithms. In this work we bring complexity results and algorithms related to three games with common characteristics , Bloxorz , On The Edge and Bobbin 3D.

nÃo hà / The Min-Degree Constrained Minimum Spannig Tree - MD-MST is to find a minimum spanning tree of a graph where each vertex is a leaf of the tree or satisfies a constraint of minimum degree. The leaf vertices are called terminals and the others are the central vertices. We define and study a variation of this problem, which we denote MDF-MST, where the terminal and central vertices are fixed. We show that the problem is NP-Hard and is in FPT, parameterized by the number of central vertices. We also identify cases where the problem becomes polynomial. We propose several integer programming formulations for the problem and compare the quality of lower bound generated by their linear relaxations. We propose and teste a Lagrangian Relaxation for the problem, which we also use to define Lagrangian heuristics. We define greedy heuristics, a VND Local search and a VNS heuristic. We present a Bendersâs Decomposition. We propose a new general heuristic that combines ingredients from the Bendersâs decomposition with subgradient method, which we call subgradient heuristic. We apply this heuristic to the MDF-MST. All these algorithms have been implemented, tested and compared among them and with the CPLEX solver. The computational efficiency of the proposed algorithms, especially the Lagrangian heuristics, is comparable with that of CPLEX, and even better in several cases. Some of these algorithms were adapted for the MD-MST and DC-MST (inthelatter,thedegreeconstraintisofmaximumdegree). Whencomparingthecomputational results with the literature, we conclude that the algorithms are competitive. / O Problema de Ãrvore Geradora MÃnima com RestriÃÃo de Grau MÃnimo (Min-Degree Constrained Minimum Spannig Tree - MD-MST) consiste em encontrar uma Ãrvore geradora mÃnima de um grafo onde cada vÃrtice ou à folha da Ãrvore ou satisfaz uma restriÃÃo de grau mÃnimo. Os vÃrtices folhas sÃo chamados terminais e os demais sÃo os centrais. Definimos e estudamos uma variaÃÃo desse problema, que denotamos MDF-MST, onde os terminais e centrais sÃo definidos a priori. Mostramos que o problema à NP-DifÃcil e està na Classe FPT, parametrizado pelo nÃmero de centrais. Identificamos tambÃm casos onde o problema torna-se polinomial. Propomos vÃrias formulaÃÃes de programaÃÃo inteira para o problema e comparamos teÃrica e computacionalmente a qualidade do limite inferior gerado por suas relaxaÃÃes lineares. Propomos e testamos uma relaxaÃÃo lagrangeana para o problema, que usamos tambÃm para definir heurÃsticas lagrangenas. Definimos heurÃsticas gulosas, uma busca VND e uma heurÃstica VNS. Apresentamos uma decomposiÃÃo de Benders. Propomos uma nova heurÃstica geral que combina ingredientes da decomposiÃÃo de Benders com mÃtodo de subgradientes, a qual denominamos HeurÃstica de Subgradientes. Aplicamos tal heurÃstica ao MDF-MST. Todos esses algoritmos foram implementados, testados, comparados entre si e com o solver CPLEX. A eficiÃncia computacional dos algoritmos propostos, especialmente a relaxaÃÃo lagrangeana, à competitiva com a do CPLEX, e superior em vÃrios casos. Alguns desses algoritmos foram adaptados para o problema MD-MST e seu correlato DC-MST (este Ãltimo onde a restriÃÃo sobre os centrais à de grau mÃximo). Quando comparamos os resultados computacionais com a literatura

The explosion of personal positioning devices like GPS-enabled smartphones has enabled the collection and storage of a huge amount of positioning data in the form of trajectories. Thereby, trajectory data have brought many research challenges in the process of recovery, storage and knowledge discovery in mobility as well as new applications to support our society in mobility terms. Other research area that has been receiving great attention nowadays is the area of complex network or science of networks. Complex network is the first approach to model complex system that are present in the real world, such as economic markets, the Internet, World Wide Web and disease spreading to name a few. It has been applied in different field, like Computer Science, Biology and Physics. Therefore, complex networks have demonstrated a great potential to investigate the behavior of complex systems through their entities and the relationships that exist among them. The present dissertation, therefore, aims at exploiting approaches to analyze mobility data using a perspective of complex networks. The first exploited approach stands for the trajectories as the main entities of the networks connecting each other through a similarity function. The second, in turn, focuses on points of interest that are visited by people, which perform some activities in these points. In addition, this dissertation also exploits the proposed methodologies in order to develop a software tool to support users in mobility analysis using complex network techniques.

Submitted by Ricardo Cedraz Duque Moliterno (ricardo.moliterno@uefs.br) on 2015-10-20T23:41:57Z No. of bitstreams: 1 Disserta??o-Danilo-Vers?o-final-p?s-banca .pdf: 11564872 bytes, checksum: 0a0388f802ddac466fce74bea4b02895 (MD5) / Made available in DSpace on 2015-10-20T23:41:57Z (GMT). No. of bitstreams: 1 Disserta??o-Danilo-Vers?o-final-p?s-banca .pdf: 11564872 bytes, checksum: 0a0388f802ddac466fce74bea4b02895 (MD5) Previous issue date: 2015-08-19 / Coordena??o de Aperfei?oamento de Pessoal de N?vel Superior - CAPES / Recently Wireless Sensor Networks have gained attention of researchers and industry around the world, such that many projects and solutions have been developed for various scenarios and applications. Such networks are formed by small sensor nodes with low processing power, few memory and few energy. Thus, resources are scarce, particularly energy, where, in most cases these nodes are powered by batteries, which is a crucial point in the network design. A kind of sensor network in which camera-enabled sensors are inserted are call Wireless Visual Sensor Networks. Because of this, these networks become able to recover large quantities of environment information which may to be interesting for several applications. However, in general, sensor networks are very vulnerable due to the nature of the communication and due also to the sensor nodes are, sometimes, in remote, hostile and hard to reach areas. Moreover, the sensor nodes are potentially inexpensive devices that can be easily purchased or designed by others to attack the network. So to mitigate these vulnerabilities, research in security area for such networks are required. However, traditional security mechanisms lead to very overhead of computing and communication can compromise the network performance when they are adopted. Thinking about it, this master's thesis aims to propose a new paradigm to ensure security for wireless visual sensor networks, being presented through a theoretical mathematical model to perform differentiation of areas in the monitoring environment to then considering the particularities of the application monitoring to provide security at different levels. Called Adaptive Encryption, this theoretical model can be used for various applications requiring different security assurances for different network locations, implying providing security at acceptable levels while consuming less network resources, above all energy. / Recentemente as Redes de Sensores Sem Fio t?m ganhado a aten??o de pesquisadores, da ind?stria e do meio acad?mico ao redor do mundo todo, de modo que muitos projetos e solu??es t?m sido desenvolvidas para diversos cen?rios e aplica??es. Essas redes s?o formadas por pequenos n?s sensores com pouco poder de processamento, mem?ria e energia. Sendo assim, os recursos s?o bastante escassos, principalmente energia, onde, na maioria das vezes estes n?s s?o alimentados por baterias, sendo este um ponto crucial no projeto da rede. Um tipo de rede de sensores em que os n?s possuem c?meras de v?deo embutidas s?o chamadas de Redes de Sensores Visuais Sem Fio. Devido a isso, tais redes se tornam capazes de recuperar grandes quantidades de informa??es do ambiente o que pode ser interessante para diversas aplica??es. Todavia, de forma geral, as redes de sensores s?o muito vulner?veis devido a natureza da comunica??o e devido tamb?m aos n?s sensores estarem, algumas vezes, em locais remotos, hostis e de dif?cil acesso. Al?m disso, os n?s sensores s?o dispositivos potencialmente baratos que podem ser facilmente adquiridos ou projetados por terceiros a fim de atacar a rede. Ent?o, visando atenuar essas vulnerabilidades, pesquisas na ?rea de seguran?a para tais redes s?o necess?rias. Contudo, os mecanismos de seguran?a tradicionais geram muito sobrecarga de computa??o e comunica??o podendo comprometer o desempenho da rede quando s?o adotados. Pensando nisso, este trabalho de mestrado tem como objetivo propor um novo paradigma para garantir seguran?a para redes de sensores visuais sem fio, sendo apresentado atrav?s um modelo matem?tico te?rico para realizar diferencia??o de ?reas no ambiente de monitoramento para, ent?o, considerando as particularidades da aplica??o de monitoramento, prover seguran?a em diferentes n?veis. Chamado de Criptografia Adaptativa, este modelo te?rico pode ser utilizado por diversas aplica??es que necessitem de garantias de seguran?a diferenciadas para diferentes locais da rede, o que implica em prover seguran?a em n?veis aceit?veis consumindo menos recursos da rede, principalmente energia.

Submitted by Caroline Xavier (caroline.xavier@pucrs.br) on 2017-11-14T10:44:09Z No. of bitstreams: 1 DIS_MATHEUS_CRESPI_SCHENFELD_COMPLETO.pdf: 6989470 bytes, checksum: 4a16f12e8953d43da2cb18cc63c6119a (MD5) / Approved for entry into archive by Caroline Xavier (caroline.xavier@pucrs.br) on 2017-11-14T10:44:28Z (GMT) No. of bitstreams: 1 DIS_MATHEUS_CRESPI_SCHENFELD_COMPLETO.pdf: 6989470 bytes, checksum: 4a16f12e8953d43da2cb18cc63c6119a (MD5) / Made available in DSpace on 2017-11-14T10:44:39Z (GMT). No. of bitstreams: 1 DIS_MATHEUS_CRESPI_SCHENFELD_COMPLETO.pdf: 6989470 bytes, checksum: 4a16f12e8953d43da2cb18cc63c6119a (MD5) Previous issue date: 2017-03-23 / Internet of Things (IoT) is considered a computational evolution that advocates the existence of a large number of physical objects embedded with sensors and actuators, connected by wireless networks and communicating through the Internet. From the beginning of the concept to the present day, IoT is widely used in the various sectors of industry and also in academia. One of the needs encountered in these areas was to be connected to IoT devices or subsystems throughout the world. Thus, cloud computing gains space in these scenarios where there is a need to be connected and communicating with a middleware to perform the data processing of the devices. The concept of cloud computing refers to the use of memory, storage and processing of shared resources, interconnected by the Internet. However, IoT applications sensitive to communication latency, such as medical emergency applications, military applications, critical security applications, among others, are not feasible with the use of cloud computing, since for the execution of all calculations and actions messaging between devices and the cloud is required. Solving this limitation found in the use of cloud computing, the concept of fog computing arises and whose main idea is to create a federated processing layer, still in the local network of the computing devices of the ends of the network. In addition to fog computing, there is also edge computing operating directly on the devices layer, performing some kind of processing, even with little computational complexity, in order to further decrease the volume of communication, besides collaborating to provide autonomy in decision making yet in the Things layer. A major challenge for both fog and edge computing within the IoT scenario is the definition of a system architecture that can be used in different application domains, such as health, smart cities and others. This work presents a system architecture for IoT devices capable of enabling data processing in the devices themselves or the closest to them, creating the edge computing layer and fog computing layer that can be applied in different domains, improving Quality of Services (QoS) and autonomy in decision making, even if the devices are temporarily disconnected from the network (offline). The validation of this architecture was done within two application scenarios, one of public lighting in smart city environment and another simulating an intelligent agricultural greenhouse. The main objectives of the tests were to verify if the use of the concepts of edge and fog computing improve system efficiency compared to traditional IoT architectures. The tests revealed satisfactory results, improving connection times, processing and delivery of information to applications, reducing the volume of communication between devices and core middleware, and improving communications security. It also presents a review of related work in both academia and industry. / Internet das Coisas (IoT) ? considerada uma evolu??o computacional que preconiza a exist?ncia de uma grande quantidade de objetos f?sicos embarcados com sensores e atuadores, conectados por redes sem fio e que se comunicam atrav?s da Internet. Desde o surgimento do conceito at? os dias atuais, a IoT ? amplamente utilizada nos diversos setores da ind?stria e tamb?m no meio acad?mico. Uma das necessidades encontradas nessas ?reas foi a de estar conectado com dispositivos ou subsistemas de IoT espalhados por todo o mundo. Assim, cloud computing ganha espa?o nesses cen?rios, onde existe a necessidade de estar conectado e se comunicando com um middleware para realizar o processamento dos dados dos dispositivos. O conceito de cloud computing refere-se ao uso de mem?ria, armazenamento e processamento de recursos compartilhados, interligados pela Internet. No entanto, aplica??es IoT sens?veis ? lat?ncia de comunica??o, tais como, aplica??es m?dico-emergenciais, aplica??es militares, aplica??es de seguran?a cr?tica, entre outras, s?o invi?veis com o uso de cloud computing, visto que para a execu??o de todos os c?lculos e a??es ? necess?ria a troca de mensagens entre dispositivos e nuvem. Solucionando essa limita??o encontrada na utiliza??o de cloud computing, surge o conceito de fog computing, cuja ideia principal ? criar uma camada federada de processamento ainda na rede local dos dispositivos de computa??o das extremidades da rede. Al?m de fog computing tamb?m surge edge computing operando diretamente na camada dos dispositivos, realizando algum tipo de processamento, mesmo que de pouca complexidade computacional, a fim de diminuir ainda mais o volume de comunica??o, al?m de colaborar para prover autonomia na tomada de decis?es ainda na camada das coisas. Um grande desafio tanto para fog quanto para edge computing dentro do cen?rio de IoT ? a defini??o de uma arquitetura de sistema que possa ser usada em diferentes dom?nios de aplica??o, como sa?de, cidades inteligentes entre outros. Esse trabalho apresenta uma arquitetura de sistema para dispositivos IoT capaz de habilitar o processamento de dados nos pr?prios dispositivos ou o mais pr?ximo deles, criando a camada de edge e fog computing que podem ser aplicadas em diferentes dom?nios, melhorando a Qualidade dos Servi?os (QoS) e autonomia na tomada de decis?o, mesmo se os dispositivos estiverem temporariamente desconectados da rede (offline). A valida??o dessa arquitetura foi feita dentro de dois cen?rios de aplica??o, um de ilumina??o p?blica em ambiente de IoT e outro simulando uma estufa agr?cola inteligente. Os principais objetivos das execu??es dos testes foram verificar se a utiliza??o dos conceitos de edge e fog computing melhoram a efici?ncia do sistema em compara??o com arquiteturas tradicionais de IoT. Os testes revelaram resultados satisfat?rios, melhorando os tempos de conex?o, processamento e entrega das informa??es ?s aplica??es, redu??o do volume de comunica??o entre dispositivos e core middleware, al?m de melhorar a seguran?a nas comunica??es. Tamb?m ? apresentada uma revis?o de trabalhos relacionados tanto no meio acad?mico como no da ind?stria.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-04-03T14:37:48Z No. of bitstreams: 1 MARCELO_RUARO_TES.pdf: 4683751 bytes, checksum: 6eb242e44efbbffa6fa556ea81cdeace (MD5) / Approved for entry into archive by Tatiana Lopes (tatiana.lopes@pucrs.br) on 2018-04-13T17:30:40Z (GMT) No. of bitstreams: 1 MARCELO_RUARO_TES.pdf: 4683751 bytes, checksum: 6eb242e44efbbffa6fa556ea81cdeace (MD5) / Made available in DSpace on 2018-04-13T17:37:13Z (GMT). No. of bitstreams: 1 MARCELO_RUARO_TES.pdf: 4683751 bytes, checksum: 6eb242e44efbbffa6fa556ea81cdeace (MD5) Previous issue date: 2018-03-16 / Sistemas multi-n?cleos intra-chip s?o o estado-da-arte em termos de poder computacional, alcan?ando de d?zias a milhares de elementos de processamentos (PE) em um ?nico circuito integrado. Sistemas multi-n?cleos de prop?sito geral assumem uma admiss?o din?mica de aplica??es, onde o conjunto de aplica??es n?o ? conhecido em tempo de projeto e as aplica??es podem iniciar sua execu??o a qualquer momento. Algumas aplica??es podem ter requisitos de tempo real, requisitando n?veis de qualidade de servi?o (QoS) do sistema. Devido ao alto grau de imprevisibilidade do uso dos recursos e o grande n?mero de componentes para se gerenciar, propriedades autoadaptativas tornam-se fundamentais para dar suporte a QoS em tempo de execu??o. A literatura fornece diversas propostas de QoS autoadaptativo, focado em recursos de comunica??o (ex., redes intra-chip), ou computa??o (ex., CPU). Contudo, para fornecer um suporte de QoS completo, ? fundamental uma autoconsci?ncia abrangente dos recursos do sistema, e assumir t?cnicas adaptativas que permitem agir em ambos os n?veis de comunica??o e computa??o para atender os requisitos das aplica??es. Para suprir essas demandas, essa Tese prop?e uma infraestrutura e t?cnicas de gerenciamento de QoS autoadaptativo, cobrindo ambos os n?veis de computa??o e comunica??o. No n?vel de computa??o, a infraestrutura para QoS consiste em um escalonador din?mico de tarefas de tempo real e um protocolo de migra??o de tarefas de baixo custo. Estas t?cnicas fornecem QoS de computa??o, devido ao gerenciamento da utiliza??o e aloca??o da CPU. A novidade do escalonador de tarefas ? o suporte a requisitos de tempo real din?micos, o que gera mais flexibilidade para as tarefas em explorar a CPU de acordo com uma carga de trabalho vari?vel. A novidade do protocolo de migra??o de tarefas ? o baixo custo no tempo de execu??o comparado a trabalhos do estado-da-arte. No n?vel de comunica??o, a t?cnica proposta ? um chaveamento por circuito (CS) baseado em redes definidas por software (SDN). O paradigma SDN para NoCs ? uma inova??o desta Tese, e ? alcan?ado atrav?s de uma arquitetura gen?rica de software e hardware. Para QoS de comunica??o, SDN ? usado para definir caminhos CS em tempo de execu??o. Essas infraestruturas de QoS s?o gerenciadas de uma forma integrada por um gerenciamento de QoS autoadaptativo, o qual segue o paradigma ODA (Observar, Decidir, Agir), implementando um la?o fechado de adapta??es em tempo de execu??o. O gerenciamento de QoS ? autoconsciente dos recursos do sistema e das aplica??es em execu??o, e pode decidir por adapta??es no n?vel de computa??o ou comunica??o, baseado em notifica??es das tarefas, monitoramento do ambiente, e monitoramento de atendimento de QoS. A autoadapta??o decide reativamente assim como proativamente. Uma t?cnica de aprendizagem do perfil das aplica??es ? proposta para tra?ar o comportamento das tarefas de tempo real, possibilitando a??es proativas. Resultados gerais mostram que o gerenciamento de QoS autoadaptativo proposto pode restaurar os n?veis de QoS para as aplica??es com um baixo custo no tempo de execu??o das aplica??es. Uma avalia??o abrangente, assumindo diversos benchmarks mostra que, mesmo sob diversas interfer?ncias de QoS nos n?veis de computa??o e comunica??o, o tempo de execu??o das aplica??es ? restaurado pr?ximo ao cen?rio ?timo, como 99,5% das viola??es de deadlines mitigadas. / Many-core systems-on-chip are the state-of-the-art in processing power, reaching from a dozen to thousands of processing elements (PE) in a single integrated circuit. General purpose many-cores assume a dynamic application admission, where the application set is unknown at design-time and applications may start their execution at any moment, inducing interference between them. Some applications may have real-time constraints to fulfill, requiring levels of quality of service (QoS) from the system. Due to the high degree of resource?s utilization unpredictability and the number of components to manage, self-adaptive properties become fundamental to support QoS at run-time. The literature provides several self-adaptive QoS proposals, targeting either communication (e.g., Network-on-Chip) or computation resources (e.g., CPU). However, to offer a complete QoS support, it is fundamental to provide a comprehensive self-awareness of the system?s resources, assuming adaptive techniques enabling to act simultaneously at the communication and computation levels to meet the applications' constraints. To cope with these requirements, this Thesis proposes a self-adaptive QoS infrastructure and management techniques, covering both the computation and communication levels. At the computation level, the QoS-driven infrastructure comprises a dynamic real-time task scheduler and a low overhead task migration protocol. These techniques ensure computation QoS by managing the CPU utilization and allocation. The novelty of the task scheduler is the support for dynamic real time constraints, which leverage more flexibility to tasks to explore the CPU according to a variable workload. The novelty of the task migration protocol is its low execution time overhead compared to the state-of-the-art. At the communication level, the proposed technique is a Circuit-Switching (CS) approach based on the Software Defined Networking (SDN) paradigm. The SDN paradigm for NoCs is an innovation of this Thesis and is achieved through a generic software and hardware architecture. For communication QoS, SDN is used to define CS paths at run-time. A self-adaptive QoS management following the ODA (Observe Decide Act) paradigm controls these QoS-driven infrastructures in an integrated way, implementing a closed loop for run time adaptations. The QoS management is self-aware of the system and running applications and can decide to take adaptations at computation or communication levels based on the task feedbacks, environment monitoring, and QoS fulfillment monitoring. The self-adaptation decides reactively as well as proactively. An online application profile learning technique is proposed to trace the behavior of the RT tasks and enabling the proactive actions. Results show that the proposed self-adaptive QoS management can restore the QoS level for the applications with a low overhead over the applications execution time. A broad evaluation, using known benchmarks, shows that even under severe QoS disturbances at computation and communication levels, the execution time of the application is restored near to the optimal scenario, mitigating 99.5% of deadline misses.

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-04-10T19:11:33Z No. of bitstreams: 1 FABIO_MIGUEL_BLASAK_DA_FONSECA_DIS.pdf: 2321276 bytes, checksum: 333d6e8a8d369d82fe548927b2edaad3 (MD5) / Approved for entry into archive by Tatiana Lopes (tatiana.lopes@pucrs.br) on 2018-04-13T16:22:42Z (GMT) No. of bitstreams: 1 FABIO_MIGUEL_BLASAK_DA_FONSECA_DIS.pdf: 2321276 bytes, checksum: 333d6e8a8d369d82fe548927b2edaad3 (MD5) / Made available in DSpace on 2018-04-13T16:28:48Z (GMT). No. of bitstreams: 1 FABIO_MIGUEL_BLASAK_DA_FONSECA_DIS.pdf: 2321276 bytes, checksum: 333d6e8a8d369d82fe548927b2edaad3 (MD5) Previous issue date: 2017-08-11 / The growing need to extend IT (Information Technology) resources to meet business needs has raised concerns about how to increase capacity with lower cost and greater use of data center. Therefore, in order to avoid underutilization of infrastructure resources virtualization is a trend towards cost reduction and consolidation of the server infrastructure, thus taking advantage of existing assets. However, with virtualization growth, there is a problem related to resources concurrence in consolidated environments, where diskintensive applications such as databases can be impacted in this type of environment, if they do not have their resources managed properly, can generate performance degradation and increasing execution time respectively. In order to optimize performance and reduce I/O contention, Kassiano J.M. [19] presented a study on the acceleration of Hadoop applications through manual adjustment of disk resource allocation, showing that it is possible to get performance gains. Therefore, proposed work follows this line of study, however, with objective of optimizing the execution of database applications in virtualized environments with shared resources, applying a dynamic adjustment policy of disk resources allocation. It aims to distribute disk resources optimally through an algorithm, avoiding that one or more processes consume all disk resources, while others wait to be executed or are being executed without minimum of appropriate disk resources, thus, taking more time to complete their execution. In order to demonstrate this scenario, workloads of OLTP (Online Transaction Processing) and DW (Data Warehouse) databases have been evaluated using the Orion data load simulator [24] and real captured data from a loading test provided by a large IT company in partnership with PUCRS University (Pontifical Catholic University of Rio Grande do Sul), through the Oracle RAT (Real Application Testing) [25]. Laboratory tests have been performed using the following test scenarios: without adjustment of disk resources, with static adjustment of disk resources and through a dynamic adjustment policy of disk resources based on performance metrics. In this case, it can be observed that dynamic policy obtained the best result among the other test groups, generating a gain of 23% for OLTP database workloads, 21% for DW database workloads and 18% for environments with different types of workloads in concurrency like DW and OLTP. / A crescente necessidade de extens?o dos recursos de TI (Tecnologia da Informa??o) para atender as demandas do neg?cio, geraram uma preocupa??o de como aumentar a capacidade com menor custo e maior aproveitamento do data center. Portanto, a fim de evitar a subutiliza??o de recursos de infraestrutura a virtualiza??o ? uma tend?ncia para redu??o de custos e consolidar a infraestrutura de servidores, aproveitando assim os ativos existentes. Entretanto, com o crescimento da virtualiza??o, surge um problema relacionado a concorr?ncia por recursos em ambientes consolidados, onde aplica??es com uso intensivo de disco, como bancos de dados, podem ser impactados neste tipo de ambiente, caso n?o tenham os seus recursos gerenciados apropriadamente, podendo gerar degrada??o no desempenho e consequentemente aumentando o tempo de execu??o. A fim de otimizar performance e reduzir a conten??o de E/S (Entrada/Sa?da), Kassiano J. M. [19] apresentou um estudo sobre a acelera??o de aplica??es Hadoop atrav?s de ajuste manual na aloca??o de recursos de disco, mostrando que ? poss?vel obter ganhos de performance. Logo, o trabalho proposto, segue esta linha de estudo, entretanto, com o objetivo de otimizar a execu??o de aplica??es de banco de dados em ambientes virtualizados com recursos compartilhados, aplicando uma pol?tica de ajuste din?mico de aloca??o de recursos de disco, a qual visa acelerar ainda mais os ganhos de performance. Essa pol?tica tem por objetivo distribuir os recursos de disco de forma otimizada, conforme algoritmo aplicado, evitando que um ou mais processos consumam todos os recursos de disco, enquanto outros aguardam para serem executados ou executam com o m?nimo de recursos de disco apropriados, por isso, levando maior tempo para concluir o processamento. Para evidenciar esta situa??o, foram avaliados workloads de banco de dados do tipo OLTP (Online Transaction Processing) e DW (Data Warehouse), utilizando o simulador de cargas de dados Orion [24] e com dados reais capturados de um teste de carga cedidos por uma empresa de TI de grande porte, em parceria com a universidade PUCRS (Pontif?cia Universidade Cat?lica do Rio Grande do Sul), atrav?s do recurso Oracle RAT (Real Application Testing) [25]. Foram realizados testes em laborat?rio utilizando os seguintes cen?rios de teste: sem ajuste de recursos de disco, com ajuste est?tico de recursos de disco e atrav?s de uma pol?tica de ajuste din?mico de recursos de disco com base em m?tricas deperformance. A partir disso, pode-se observar que a pol?tica din?mica obteve o melhor resultado entre os demais grupos de teste, gerando um ganho de 23% para a execu??o de workloads de banco de dados OLTP, 21% para workloads de banco de dados DW e 18% durante a execu??o de ambientes com workloads de tipos diferentes em concorr?ncia, exemplo: DW e OLTP.