Submitted by Mariana Dornelles Vargas (marianadv) on 2015-05-28T14:17:29Z No. of bitstreams: 1 Getlb.pdf: 3597932 bytes, checksum: 9c794d7c5c59244cce8b65e3ccd9e1d3 (MD5) / Made available in DSpace on 2015-05-28T14:17:29Z (GMT). No. of bitstreams: 1 Getlb.pdf: 3597932 bytes, checksum: 9c794d7c5c59244cce8b65e3ccd9e1d3 (MD5) Previous issue date: 2013 / Nenhuma / Transações eletrônicas financeiras - em inglês EFT (Electronic Funds Transfer) - representam uma realidade em expansão que impulsiona a aproximação entre consumidores e fornecedores. As transações podem ser originadas de diferentes meios de captura da informação e são transmitidas para um centro de processamento, que decodifica, executa e retorna os resultados no menor tempo possível. Em especial, a presente dissertação de mestrado está enquadrada no dia-a-dia da empresa GetNet e no balanceamento de carga sobre um de seus sistemas de processamento. O sistema em estudo dispõe atualmente de uma arquitetura na qual as transações são recebidas em um nó centralizador, representado por um chaveador Cisco, e são distribuídas para Máquinas Processadoras (MP) segundo o algoritmo de escalonamento Round Robin. Esse algoritmo é adequado para as situações onde as MP são homogêneas e o tempo de rede entre elas e o nó centralizador é também uniforme. Essa configuração pode ser restritiva para um sistema transacional que precisa estar dimensionado para atender uma empresa em expansão geográfica que use MP em diferentes localizações. Em adição, a atuação do algoritmo Round Robin permite que transações sejam repassadas para MP que já possuem alta carga de trabalho ou se encontram indisponíveis. Nesse contexto, essa dissertação descreve uma arquitetura para o sistema transacional chamada GetLB, que proporciona um balanceamento de carga a partir do chaveador com base em monitoração das máquinas de processamento. A infraestrutura GetLB propõe um novo escalonador chamado LL (Load Level). Diferente do Round Robin, para cada transação i, LL calcula n funções LL(i; j), onde j é a MP alvo e n a quantidade das mesmas. Para tal, serão verificadas as suas condições para atender à demanda conforme índices de ocupação de CPU, memória, disco e estado das filas das máquinas processadoras, entre outros. A eficiente combinação desses fatores, para o despacho de transações, configura a contribuição científica do trabalho. Assim como a eficiência em notificar o chaveador quando ocorrem eventos assíncronos no sistema, como parada ou perda de capacidade de processamento de alguma máquina. A arquitetura GetLB também visa proporcionar capacidade de operação com heterogeneidade de máquinas processadoras, possibilitando o uso de máquinas especialistas para certos tipos de transações e a integração de MPs de diferentes redes (domínios administrativos). Os resultados dos testes mostraram que GetLB é mais eficiente que Round-Robin em muitos aspectos, sobressaindo mais em situações de heterogeneidade de recursos e dinamicidade de eventos. Verificou-se também que as notificações acrescentam muito valor ao sistema, auxiliando na manutenção e melhoria contínua da solução. / Electronic financial transactions represents an expanding reality that drives the approach between consumers and suppliers. Transactions can be originated from different information’s capture terminals and are transmitted to a processing center, which decodes, executes and returns the results in the shortest time possible. In particular, this dissertation is framed in the day-to-day operations of GetNet, a network and service provider company, and load balancing on one of its processing systems. The system under study currently has an architecture in which transactions are received at a centralized node, represented by a Cisco switch, and are distributed to machines processors (MP) according to Round Robin scheduling algorithm. This algorithm is suitable for situations where the MP are homogeneous and network transfer time between them and the centralized node is also uniform. This setting can be restrictive for a transactional system that needs to be sized to meet an expanding company and uses geographic MP at different locations. In addition, the performance of Round Robin algorithm enables transactions to be passed to MP who already have high workload or are unavailable. In this context, this work describes an architecture for a transactional system called GetLB, which provides load balancing from the switch based on processing machines’s monitoring. The infrastructure GetLB proposes a new scheduler called LL (Load Level). Unlike the Round Robin, for each transaction i, LL calculates n functions LL (i, j) where j is the target MP and n quantity of machines. This will check their conditions to meet demand as occupancy rate of CPU, memory, disk, and state of the queues of processing machines, among others. The efficient mix of these factors to dispatch transactions, sets the scientific work. As well as the efficiency to notify the switch when asynchronous events occur in the system, such as stopping or loss of processing capacity of some machine. The architecture also aims to provide GetLB operation capability with heterogeneous processing machines, enabling the use of machinery specialists for certain types of transactions and the integration of MPs from different networks (administrative domains). The test results showed that GetLB is more efficient than Round-Robin in many aspects and stand out in case of heterogeneous resources and dynamic events. It was also found that the notifications adds much value to system, assisting in the maintenance and continuous solution’s improvement

La méthode multipôle permet d'accélérer les produits matrices-vecteurs, utilisés par les solveurs itératifs pour déterminer le comportement électromagnétique, d'un objet soumis à une onde incidente. Nos travaux ont pour but d'adapter cette méthode pour la rendre efficace sur les architectures hétérogènes contenant des GPU. Pour cela, nous utilisons une ordonnanceur dynamique, StarPU, qui effectuera la distribution des tâches de calcul au sein d'un nœud. Pour la parallélisation en mémoire distribuée, nous effectuerons un ordonnancement statique des boîtes, couplé à un ordonnancement dynamique des interactions proches. / The Fast Multipole Method can speed up matrix-vector products, found in iterative solvers in order to compute the electromagnetics response of an object subject to an incident wave. We have intended to adapt this method to make it effective on heterogeneous architectures with GPUs. For this purpose, we use a dynamic scheduler named StarPU, which distributes the tasks within a node. For the parallelization in distributed memory, we distribute the tasks statically but we distribute the near interactions dynamically..

Les nouvelles architectures de calcul intensif intègrent de plus en plus de microprocesseurs qui eux-mêmes intègrent un nombre croissant de cœurs de calcul. Cette multiplication des unités de calcul dans les architectures ont fait apparaître des topologies fortement hiérarchiques. Ces architectures sont dites NUMA. Les algorithmes de simulation numérique et les solveurs de systèmes linéaires qui en sont une brique de base doivent s'adapter à ces nouvelles architectures dont les accès mémoire sont dissymétriques. Nous proposons dans cette thèse d'introduire un ordonnancement dynamique adapté aux architectures NUMA dans le solveur PaStiX. Les structures de données du solveur, ainsi que les schémas de communication ont dû être modifiés pour répondre aux besoins de ces architectures et de l'ordonnancement dynamique. Nous nous sommes également intéressés à l'adaptation dynamique du grain de calcul pour exploiter au mieux les architectures multi-cœurs et la mémoire partagée. Ces développements sont ensuite validés sur un ensemble de cas tests sur différentes architectures. / New supercomputers incorporate many microprocessors which include themselves one or many computational cores. These new architectures induce strongly hierarchical topologies. These are called NUMA architectures. Sparse direct solvers are a basic building block of many numerical simulation algorithms. They need to be adapted to these new architectures with Non Uniform Memory Accesses. We propose to introduce a dynamic scheduling designed for NUMA architectures in the PaStiX solver. The data structures of the solver, as well as the patterns of communication have been modified to meet the needs of these architectures and dynamic scheduling. We are also interested in the dynamic adaptation of the computation grain to use efficiently multi-core architectures and shared memory. Experiments on several numerical test cases will be presented to prove the efficiency of the approach on different architectures.

The manufacturing industries play a significant role in contributing to the economy of a country. Among various manufacturing industries, the semiconductor manufacturing (SM) industries is one of the fastest growing industries in the world having worldwide sales of $31 billion in the month of December 2016. Semiconductors are required by large number of industries, including Telecommunications, Medical Electronics, Automobile, Defence and Aerospace, Consumer Electronics, etc.,. Today, without semiconductors, the technology that we count on every day would not be possible. Because of these, the demand for SM industry is increased rapidly. In addition, most of the semiconductor based products‘ life is very short. Due to these, SM industry is highly competitive industry. Thus, to utilize the resources effectively, to handle the huge demand, and to deliver the product on-time, efficient scheduling is important in SM industry. SM process can be broadly classified into Wafer Fabrication (called as wafer fab), Wafer Probing, Assembly, and Final Testing. Scheduling is more important in wafer fab due to complex operations involving with multiple types of machines and re-entrant, expensive machines, and time-consuming process involved. Thus, this study concerns about scheduling in wafer fab, particularly diffusion operation. The diffusion operation, carried out on batch processing machine, heavily impacts the production rate of wafer fab and in turn the SM industry. This is due to the fact that, diffusion operation requires relatively longest processing time among all the operations in the wafer fab. Due to these, diffusion operation is the bottleneck operations in the wafer fab. Based on the detailed literature review, this study addresses a new research problem on dynamic scheduling (DS) of diffusion furnace(s) by considering together the various real-life problem characteristics: Non-identical parallel diffusion furnaces, Machine eligibility restriction, Incompatible-job families, Job and/or resource related real time events, and Non-agreeable release time and due-date. In addition, due to the importance of on-time delivery this study deals with five due-date based scheduling objectives: Total weighted tardiness (TWT), Number of tardy jobs (NT), On time delivery (OTD) rate, Total earliness and lateness (TE/L) and Maximum lateness (Lmax) as a single objective as well as multi objectives. Here, the multi objectives are developed, considering all the five due-date based scheduling objectives in a linear form by randomly assigning equal and unequal weights to each of the due-date based single objectives considered in this study. With these, the main objective of this thesis is to study the impact of job and/or resource related real time events (JR-RTE) on the relative efficiency of the proposed dynamic scheduling algorithms for diffusion furnace(s) while optimizing each of the due-date based scheduling objectives considered in this study. The research problem considered in this study is decomposed into five phases. From the analysis of the literature, it is observed that, there is no earlier study has the mathematical models for dynamic scheduling (DS) of diffusion furnaces to optimize all the due-date based scheduling objectives, considered in this study. Due to this, in the first phase, fourteen (0-1) mixed integer linear programming (MILP) models are proposed for DS of diffusion furnaces (seven models for DS of single diffusion furnace and seven models for DS of non-identical parallel diffusion furnaces) to optimize the due-date based single objectives: TWT, NT, OTD rate, TE/L, and Lmax and multi objectives: MO1 and MO2. All the proposed (0-1) MILP models are demonstrated for its workability by developing a suitable numerical example, LINGO set code (which generates each of the proposed (0-1) MILP model for any given data), and solving using LINGO solver. Further, based on the analysis of the literature a suitable experimental design is proposed and generated 15 small-scale test data. The computational complexity of each of the proposed (0-1) MILP models is discussed empirically by solving 15 small-scale test data. Due to the computational intractability of the proposed (0-1) MILP models for DS of diffusion furnaces, the second phase of the research focuses on a simple alternative approach based on dispatching rules, as the analysis of the literature reveals that dispatching rules are heavily used in the SM industry. However, there is no study in the literature presenting a comparative analysis of various dispatching rules particularly due-date based dispatching rules (DDR) for DS of diffusion furnace(s) to optimize various due-date based scheduling objectives. Accordingly, in the second phase, this study proposes a simple Greedy Algorithm (GA) based on DDR (called as GA-DDR) for Dynamic Scheduling of Single Diffusion Furnace (DS-SDF). Further, this study proposes twenty variants of GA-DDR considering various due-date based dispatching rules such as Earliest Due-Date, Flow Due-Date, Operational Due-Date, Modified Operational Due-Date, Critical Ratio, Minimum Slack First, Cost OVER Time, ten versions of Apparent Tardiness Cost (ATC) [including a new ATC rule proposed in this study] & five versions of Batch Apparent Tardiness Cost (BATC) [including a new BATC rule proposed in this study] for DS-SDF. All these twenty variants of GA-DDR are implemented in Turbo C. An experimental design is proposed in this phase for generating large-scale test data. Accordingly, 270 large-scale problem instances (representing 27 problem configurations and 10 instances per configurations) are generated. With these, a series of computational experiments are carried out to understand the relative efficiency of the twenty proposed variants of GA-DDR as follows: The efficiency of each of the twenty proposed variants of GA-DDR for DS-SDF with respect to each of the scheduling objectives considered in this study is analysed in comparison with optimal objective function value obtained from the corresponding (0-1) MILP models for 15 small-scale problem instances using the standard performance measures: Average Relative Percentage Deviation (ARPD) and Maximum Relative Percentage Deviation (MRPD). Further, for each of the 270 problem instances the efficiency of each of the twenty proposed variants of GA-DDR for DS-SDF with respect to each of the scheduling objectives is analysed in comparison with estimated objective function value, which is computed by giving the twenty feasible solutions obtained for each instances as input to Weibull distribution, (i) empirically using the performance measures: ARPD, MRPD, Integrated Rank (IRANK), & Global comparison based on Worst Solution (GCWS), and (ii) statistically by using the performance measures: Mean, Median, and 95% confidence interval. From the overall analysis, at the end of the second phase of the study, six efficient variants of GA-DDR among the twenty proposed variants of GA-DDR are identified for DS-SDF and discussed the insights for their better performance. In these six efficient variants of GA-DDR, two variants of GA-DDR uses the new ATC rule and/or BATC rule proposed by the author of this thesis. The second phase of the research considers only dynamic arrival of jobs in all the twenty variants of GA-DDR. But, in the real-life various unexpected job related real time events: rush job, due-date change, early/late arrival of job, change in job priority, and job cancellation and/or resource related real time events: machine breakdown, operator illness, tool failure, shortage of material, and defective material will occur in addition to the dynamic arrival of jobs. From the literature, it is observed that, all the studies in the dynamic scheduling of diffusion furnaces consider only future arrival of jobs and no study considering real time events. Further, to the best of our knowledge, the research studies on discrete processing machines develop various rescheduling algorithm or modify the existing algorithm whenever real time events occur while taking the scheduling decision. However, due to the longest operation time requirements at diffusion furnace and the computerized tracking system in the shop floor of wafer fab, we strongly propose a research hypothesis that modifying appropriately the work-in-process (WIP) data and/or the availability time of the corresponding diffusion furnace(s) for next scheduling depending upon the occurrence of job and/or resource related real time events respectively by utilizing the existing computerized tracking system in the shop floor is sufficient, and changing any proposed efficient algorithms for DS-SDF is not required. This hypothesis is proved both empirically and statistically in the third phase of this research, considering the twenty proposed variants of GA-DDR for DS-SDF and the proposed experimental design. Accordingly, this study propose a formal researchable hypothesis that there is no impact of JR-RTE on the relative efficiency of the twenty proposed variants of GA-DDR for DS-SDF while optimizing each of the due-date based scheduling objectives considered in this study. For testing the proposed hypothesis, this study proposed adjusted GA-DDR (with JR-RTE) for each of the proposed GA-DDR, in which there is step to update the WIP data if job related event occurs, and/or the next available time of corresponding diffusion furnace(s) for scheduling the same if resource related event occurs, before finalizing the scheduling decision. Each of the 270 large-scale problem instances generated using the proposed experimental design is solved by each of the 20 adjusted variants of GA-DDR (with JR-RTE). The comparison on the relative efficiency of each of the 20 proposed variants of GA-DDR and adjusted GA-DDR (with JR-RTE) is carried out using the performance measures: ARPD and MRPD [that is, ARPD(GA-DDR) vs. ARPD(adjusted GA-DDR with JR-RTE), and MRPD(GA-DDR) vs. MRPD(adjusted GA-DDR with JR-RTE)] while optimizing each of the seven scheduling objectives considered in this study. The empirical analysis of the comparisons reveals that there is no change in the relative efficiency of each of the 20 proposed variants of GA-DDR and the corresponding 20 adjusted variants of GA-DDR (with JR-RTE) while optimizing each of the scheduling objectives considered in this study. Further, this study proved the proposed hypothesis statistically by conducting the Spearman‘s rank order correlation between each of the 20 variants of GA-DDR and adjusted GA-DDR (with JR-RTE) for DS-SDF while optimizing each of the seven due-date based scheduling objectives considered in this study. From the empirical and statistical analyses carried out in the third phase of the study indicated that, no need to adjust the proposed variants of GA-DDR for any occurrences of real time events for obtaining efficient schedule. The SM industry normally would have more than one non-identical diffusion furnaces and that too in parallel. Due to some technical reasons, some jobs are processed only in specific diffusion furnace(s) available in the shop floor (this is called as machine eligibility restriction in scheduling theory). Hence, the impact of JR-RTE on the dynamic scheduling (DS) of non-identical parallel diffusion furnaces (NPDF) with machine eligibility restriction (MER) is addressed in the fourth phase of this study. In the fourth phase of the research study, the twenty proposed variants of GA-DDR for DS-SDF extended appropriately for DS-NPDF with MER [called as Extended GA-DDR (EGA-DDR)]. Further, a few new problem parameters required for NPDF with MER are identified from the literature and extended the proposed experimental design and generated 270 problem instances for representing NPDF with MER. For testing the proposed hypothesis on the impact of JR-RTE on DS-NPDF with MER, exactly the similar research processes carried out for comparing GA-DDR vs. adjusted GA-DDR (with JR-RTE) is followed for comparing EGA-DDR vs. adjusted EGA-DDR (with JR-RTE). Both empirical and statistical analyses clearly proved that there is no impact of JR-RTE on the relative efficiency of the twenty variants of EGA-DDR for DS-NPDF with MER while optimizing each of the due-date based scheduling objectives considered in this study and no need to adjust the variants of EGA-DDR for any occurrences of real time events for obtaining efficient schedule. So far, the study addressed the development of efficient GA-DDR and EGA-DDR for DS-SDF and DS-NPDF with MER respectively and studied the impact of JR-RTE on the relative efficiency of these proposed GA-DDR and EGA-DDR. Now, in the final phase of the research study, the impact of JR-RTE on the meta heuristics: Simulated Annealing (SA) and Tabu Search (TS), one at a time, for DS-SDF while minimizing TWT are studied. Accordingly, the required parameters for these two meta heuristics are identified from the literature and the meta heuristics: SA and TS, considering each of the six solutions obtained from the six efficient variants of GA-DDR respectively as initial solution are implemented. From the analysis of the solutions obtained, for each of the 270 problem instances, from each of the six efficient variants of GA-DDR and from each of the meta heuristics: SA and TS, it appears that the six efficient proposed variants of GA-DDR seems to be robust in terms of both quality and computational time requirements in obtaining efficient solution. Further, to study the impact of JR-RTE on meta heuristics: SA and TS, this study considers (a) six solutions obtained from each of the six efficient variants of GA-DDR for DS-SDF as the initial solution and obtained six final solutions respectively from each of the meta heuristics, and (b) six solutions obtained from each of the six adjusted variants of GA-DDR (with JR-RTE) for DS-SDF as the initial solution and obtained six final solutions respectively from each of the meta heuristics. For each of the meta heuristics, these two sets of final solutions, obtained for each of the 270 problem instances, are compared empirically and statistically, based on various performance measures considered in this study, and proved the research hypothesis defined in this study. The major research contributions of this study are as follows - By analyzing the literature on scheduling diffusion furnaces and the real-life situation in scheduling diffusion furnaces, a new research problem on dynamic scheduling (DS) of diffusion furnaces with incompatible-job families, machine eligibility restriction, non-agreeable release time and due-date, considering job and/or resource related real time events (JR-RTE) along with dynamic job arrival to optimize due-date based scheduling objectives: TWT, NT, OTD rate, TE/L, and Lmax as a single objective as well as multi objective was defined. - Seven (0-1) MILP models for each of DS-SDF and DS-NPDF were proposed for optimizing each of the seven due-date based scheduling objectives considered in this study and the computational complexity was observed. - Due to the computational complexity of the proposed (0-1) MILP models and the popularity of the dispatching rules in the semiconductor manufacturing industry, this study proposed and compared the twenty variants of (i) greedy algorithm based on due-date based dispatching rules (GA-DDR) for DS-SDF, and (ii) Extended GA-DDR for DS-NPDF with machine eligibility restriction (MER). - The impact of JR-RTE on the twenty proposed variants of (a) GA-DDR for DS-SDF, and (b) EGA-DDR for DS-NPDF with MER was studied and observed that modifying the data appropriately by utilizing the existing computerized tracking system available in the shop floor is sufficient and rescheduling or modifying the existing algorithms are not required when the occurrences of JR-RTE happens. - Finally, single solution based meta heuristics: Simulated Annealing (SA) and Tabu Search (TS), considering each of the six solution obtained from each of the six efficient variants of GA-DDR proposed in this study as initial solution respectively, were proposed for DS-SDF to minimize TWT. Performance analysis of the solution obtained from each of the six efficient variants of GA-DDR and from each of the meta heuristics were carried out and observed that efficient variants of GA-DDR seems to be robust in terms of both quality and computational time requirements in obtaining efficient solution. In addition, the impact of JR-RTE on the meta heuristics: SA and TS were studied and proved the research hypothesis proposed in this study. Although, this study considers many real-life problem characteristics, there are certain limitations in this study. Though this study proposed mathematical model for DS-NPDF, the required additional constraint on Machine Eligibility is not considered in this study. Further, the impact of JR-RTE on the meta heuristics: SA and TS were studied considering only DS-SDF and not for DS-NPDF with MER. In addition to overcoming the limitations mentioned here, there are many immediate future research directions for the problem studied in this thesis such as proposing the greedy algorithms for scheduling diffusion operation along with upstream or downstream operation, and proposing population based meta heuristics for the research problem defined in this study.

The resource demand on embedded devices is constantly growing. This is caused by the sheer explosion of software based functions in embedded systems, that are growing far faster than the resources of the single-core and multi-core embedded processors. As one of the limitation is the computing power of the processors we need to explore ways to use this resource more efficiently. We identified that during the run-time of the embedded devices the resource demand of the software functions is permanently changing dependent on the device situation. To enable an embedded device to take advantage of this dynamic resource demand, the allocation of the software functions to the processor must be handled by a scheduler that is able to evaluate the resource demand of the software functions in relation to the device situation. This marks a change in embedded devices from static defined software systems to dynamic software systems. Above that we can increase the efficiency even further by extending the approach from a single device to a distributed or networked system (many-core system). However, existing approaches to deal with dynamic resource allocation are focused on individual devices and leave the optimization potential of manycore systems untouched. Our concept will extend the existing Hierarchical Asynchronous Multi-Core Scheduler (HAMS) concept for individual devices to many-core systems. This extension introduces a dynamic situation aware scheduler for many-core systems which take the current workload of all devices and the system-situation into account. With our approach, the resource efficiency of an embedded many-core system can be increased. The following paper will explain the architecture and the expected results of our concept.

Les besoins croissants en puissance de calcul sont généralement satisfaits en fédérant de plus en plus d’ordinateurs (ou noeuds) pour former des infrastructures distribuées. La tendance actuelle est d’utiliser la virtualisation système dans ces infrastructures, afin de découpler les logiciels des noeuds sous-jacents en les encapsulant dans des machines virtuelles. Pour gérer efficacement ces infrastructures virtualisées, de nouveaux gestionnaires logiciels ont été mis en place. Ces gestionnaires sont pour la plupart hautement centralisés (les tâches de gestion sont effectuées par un nombre restreint de nœuds dédiés). Cela limite leur capacité à passer à l’échelle, autrement dit à gérer de manière réactive des infrastructures de grande taille, qui sont de plus en plus courantes. Au cours de cette thèse, nous nous sommes intéressés aux façons d’améliorer cet aspect ; l’une d’entre elles consiste à décentraliser le traitement des tâches de gestion, lorsque cela s’avère judicieux. Notre réflexion s’est concentrée plus particulièrement sur l’ordonnancement dynamique des machines virtuelles, pour donner naissance à la proposition DVMS (Distributed Virtual Machine Scheduler). Nous avons mis en œuvre un prototype, que nous avons validé au travers de simulations (notamment via l’outil SimGrid), et d’expériences sur le banc de test Grid’5000. Nous avons pu constater que DVMS se montrait particulièrement réactif pour gérer des infrastructures virtualisées constituées de dizaines de milliers de machines virtuelles réparties sur des milliers de nœuds. Nous nous sommes ensuite penchés sur les perspectives d’extension et d’amélioration de DVMS. L’objectif est de disposer à terme d’un gestionnaire décentralisé complet, objectif qui devrait être atteint au travers de l’initiative Discovery qui fait suite à ces travaux. / The increasing need in computing power has been satisfied by federating more and more computers (called nodes) to build the so-called distributed infrastructures. Over the past few years, system virtualization has been introduced in these infrastructures (the software is decoupled from the hardware by packaging it in virtual machines), which has lead to the development of software managers in charge of operating these virtualized infrastructures. Most of these managers are highly centralized (management tasks are performed by a restricted set of dedicated nodes). As established, this restricts the scalability of managers, in other words their ability to be reactive to manage large-scale infrastructures, that are more and more common. During this Ph.D., we studied how to mitigate these concerns ; one solution is to decentralize the processing of management tasks, when appropriate. Our work focused in particular on the dynamic scheduling of virtual machines, resulting in the DVMS (Distributed Virtual Machine Scheduler) proposal. We implemented a prototype, that was validated by means of simulations (especially with the SimGrid tool) and with experiments on the Grid’5000 test bed. We observed that DVMS was very reactive to schedule tens of thousands of virtual machines distributed over thousands of nodes. We then took an interest in the perspectives to improve and extend DVMS. The final goal is to build a full decentralized manager. This goal should be reached by the Discovery initiative,that will leverage this work.

La croissance exponentielle du nombre de dispositifs communicants et des services sans fils émergents fixe des objectifs toujours plus haut pour répondre à la demande de capacité sans cesse croissante des utilisateurs. Cela pose des défis constants pour atteindre les objectifs envisagés. La réutilisation spectrale élevée (High efficiency spectral reuse) a été adopté, cependant, elle conduit à des interférences accrues sur le réseau, ce qui dégrade les performances. L'OFDM (Orthogonal Frequency Division Multiplexing) est utilisé comme solution dans les réseaux de 4 G. Grâce à son orthogonalité, l'OFDM élimine l'interférence intra-cellulaire, mais l'interférence inter-cellule reste importante. Plusieurs méthodes connues sous le nom d'Inter-Cell interférences coordination (ICIC) ont été proposées pour les diminuer. L'ICIC permet la gestion des ressources radio coordonnée entre plusieurs cellules appelées ENodeB. Ces eNodeB peuvent partager les informations nécessaires grâce à l'interface X2 qui les relient, ces informations sont transmises par des messages LTE normalisés. Lorsque les ENodeBs sélectionnent égoïstement les ressources, la théorie de jeux non-coopératifs est largement appliquée pour trouver un juste équilibre. Dans cette thèse, nous mettons l'accent sur l'ICIC pour la liaison descendante d'un système OFDMA cellulaire dans le contexte du projet SOAPS (Spectrum opportuniste accès à la Sécurité publique). Ce projet a pour but l'amélioration de la planification des ressources de fréquences pour fournir des services à large bande dans les systèmes PMR (radiocommunications mobiles privées) en utilisant les technologies LTE. Nous adressons le problème d'ICIC en proposant quatre solutions différentes sous forme d'algorithmes entièrement décentralisés, ces algorithmes se basent sur la théorie des jeux non-coopératifs avec des équilibres de Nash purs des jeux considérés / The exponential growth in the number of communications devices has set out new ambitious targets to meet the ever-increasing demand for user capacity in emerging wireless systems. However, the inherent impairments of communication channels in cellular systems pose constant challenges to meet the envisioned targets. High spectral reuse efficiency was adopted as a solution to higher data rates. Despite its benefits, high spectral reuse leads to increased interference over the network, which degrades performances of mobile users with bad channel quality. To face this added interfence, OFDM (Orthogonal Frequency Division Multiplexing) is used for the new 4th generation network. Thanks to its orthogonality OFDM eliminates the intra-cellular interference, but when the same resources are used in two adjacents cells, the inter-cell interference becomes severe. To get rid of the latter, several methods for Inter-Cell Interference Coordination (ICIC) have been proposed. ICIC allows coordinated radio resources management between multiple cells. The eNodeBs can share resource usage information and interference levels over the X2 interface through LTE-normalized messages. Non-cooperative game theory was largely applied were eNodeBs selfishly selects resource blocks (RBs) in order to minimize interference. In this thesis, we stress on ICIC for the downlink of a cellular OFDMA system in the context of the SOAPS (Spectrum Opportunistic Access in Public Safety) project. This project focuses on the improvement of frequency resource scheduling for Broadband Services provision by PMR (Private Mobile Radio) systems using LTE technologies. We addressed this problem with four different solutions based on Non-cooperative game theory, three algorithms are devoted to RB selection in order to manage the interference, while the last one is a power control scheme with power economy and enhanced system performances

The ever increasing demand for Internet traffic, storage and processing requires an ever increasing amount of hardware resources. In addition to this, infrastructure providers over-provision system architectures to serve users at peak times without performance delays. Over-provisioning leads to underutilization and thus to unnecessary power consumption. Therefore, there is a need for workload management strategies to map and schedule different services simultaneously in an energy-efficient manner without compromising performance, specially for heterogeneous micro-server architectures. This requires statistical models of how services interfere with each other, thereby affecting both performance and energy consumption. Indeed, the performance-energy behavior when mixing workloads is not well understood. This paper presents an interference analysis for heterogeneous workloads (i.e., CPU- and memory-intensive) on a big.LITTLE MPSoC architecture. We employ state-of-the-art tools to generate multiple single-application mappings and characterize the interference among two different services. We observed a performance degradation factor between 1.1 and 2.5. For some configurations, executing on different clusters resulted in reduced energy consumption with no performance penalty. This kind of detailed analysis give us first insights towards more general models for future workload management systems.

[ES] La constante necesidad de un mayor rendimiento para cumplir con la gran demanda de potencia de cómputo de las nuevas aplicaciones, (ej. sistemas de conducción autónoma), obliga a la industria a apostar por la tecnología basada en Sistemas en Chip con Procesadores Multinúcleo (MPSoCs) en sus sistemas embebidos de seguridad-crítica. Los sistemas MPSoCs generalmente incluyen una red en el chip (NoC) para interconectar los núcleos de procesamiento entre ellos, con la memoria y con el resto de recursos compartidos. Desafortunadamente, el uso de las NoCs dificulta alcanzar la predecibilidad en el tiempo, ya que pueden aparecer conflictos en muchos puntos y de forma distribuida a nivel de red. Para afrontar este problema, en esta tesis se propone un nuevo paradigma de diseño para NoCs de tiempo real donde los conflictos en la red son eliminados por diseño. Este nuevo paradigma parte del Grafo de Dependencia de Canales (CDG) para evitar los conflictos de red de forma determinista. Nuestra solución es capaz de inyectar mensajes de forma natural usando un periodo TDM igual al límite teórico óptimo sin la necesidad de usar un proceso offline exigente computacionalmente. La red se ha integrado en un sistema multinúcleo basado en tiles y adaptado a su jerarquía de memoria. Como segunda contribución principal, proponemos un nuevo planificador dinámico y distribuido capaz de alcanzar un rendimiento pico muy cercanos a las NoC basadas en un diseño wormhole sin comprometer sus garantías de tiempo real. El planificador se basa en nuestro diseño de red para explotar sus propiedades clave. Los resultados de nuestra NoC muestran que nuestro diseño garantiza la predecibilidad en el tiempo evitando interferencias en la red entre múltiples aplicaciones ejecutándose concurrentemente. La red siempre garantiza el rendimiento y también mejora el rendimiento respecto al de las redes wormhole en una red 4 x 4 en un factor de 3,7x cuando se inyecta trafico para generar interferencias. En una red 8 x 8 las diferencias son incluso mayores. Además, la red obtiene un ahorro de área total del 10,79% frente a una implementación básica de una red wormhole. El planificador propuesto alcanza una mejora de rendimiento de 6,9x y 14,4x frente la versión básica de la red DCFNoC para redes en forma de malla de 16 y 64 nodos, respectivamente. Cuando lo comparamos frente a un conmutador estándar wormhole se preserva un rendimiento de red del 95% al mismo tiempo que preserva la estricta predecibilidad en el tiempo. Este logro abre la puerta a nuevos diseños de NoCs de alto rendimiento con predecibilidad en el tiempo. Como contribución final, construimos una taxonomía de NoCs basadas en TDM con propiedades de tiempo real. Con esta taxonomía realizamos un análisis exhaustivo para estudiar y comparar desde tiempos de respuesta, a implementaciones con bajo coste, pasando por soluciones de compromiso para diseños de NoCs de tiempo real. Como resultado, obtenemos nuevos diseños de NoCs basadas en TDM. / [CA] La constant necessitat d'un major rendiment per a complir amb la gran demanda de potència de còmput de les noves aplicacions, (ex. sistemes de conducció autònoma), obliga la indústria a apostar per la tecnologia basada en Sistemes en Xip amb Processadors Multinucli (MPSoCs) en els seus sistemes embeguts de seguretat-crítica. Els sistemes MPSoCs generalment inclouen una xarxa en el xip (NoC) per a interconnectar els nuclis de processament entre ells, amb la memòria i amb la resta de recursos compartits. Desafortunadament, l'ús de les NoCs dificulta aconseguir la predictibilitat en el temps, ja que poden aparéixer conflictes en molts punts i de forma distribuïda a nivell de xarxa. Per a afrontar aquest problema, en aquesta tesi es proposa un nou paradigma de disseny per a NoCs de temps real on els conflictes en la xarxa són eliminats per disseny. Aquest nou paradigma parteix del Graf de Dependència de Canals (CDG) per a evitar els conflictes de xarxa de manera determinista. La nostra solució és capaç d'injectar missatges de mra natural fent ús d'un període TDM igual al límit teòric òptim sense la necessitat de fer ús d'un procés offline exigent computacionalment. La xarxa s'ha integrat en un sistema multinucli basat en tiles i adaptat a la seua jerarquia de memòria. Com a segona contribució principal, proposem un nou planificador dinàmic i distribuït capaç d'aconseguir un rendiment pic molt pròxims a les NoC basades en un disseny wormhole sense comprometre les seues garanties de temps real. El planificador es basa en el nostre disseny de xarxa per a explotar les seues propietats clau. Els resultats de la nostra NoC mostren que el nostre disseny garanteix la predictibilitat en el temps evitant interferències en la xarxa entre múltiples aplicacions executant-se concurrentment. La xarxa sempre garanteix el rendiment i també millora el rendiment respecte al de les xarxes wormhole en una xarxa 4 x 4 en un factor de 3,7x quan s'injecta trafic per a generar interferències. En una xarxa 8 x 8 les diferències són fins i tot majors. A més, la xarxa obté un estalvi d'àrea total del 10,79% front una implementació bàsica d'una xarxa wormhole. El planificador proposat aconsegueix una millora de rendiment de 6,9x i 14,4x front la versió bàsica de la xarxa DCFNoC per a xarxes en forma de malla de 16 i 64 nodes, respectivament. Quan ho comparem amb un commutador estàndard wormhole es preserva un rendiment de xarxa del 95% al mateix temps que preserva la estricta predictibilitat en el temps. Aquest assoliment obri la porta a nous dissenys de NoCs d'alt rendiment amb predictibilitat en el temps. Com a contribució final, construïm una taxonomia de NoCs basades en TDM amb propietats de temps real. Amb aquesta taxonomia realitzem una anàlisi exhaustiu per a estudiar i comparar des de temps de resposta, a implementacions amb baix cost, passant per solucions de compromís per a dissenys de NoCs de temps real. Com a resultat, obtenim nous dissenys de NoCs basades en TDM. / [EN] The ever need for higher performance to cope with the high computational power demands of new applications (e.g autonomous driving systems), forces industry to support technology based on multi-processors system on chip (MPSoCs) in their safety-critical embedded systems. MPSoCs usually include a network-on-chip (NoC) to interconnect the cores between them and, with memory and the rest of shared resources. Unfortunately, the inclusion of NoCs difficults achieving time predictability as network-level conflicts may occur in many points in a distributed manner. To overcome this problem, this thesis proposes a new time-predictable NoC design paradigm where conflicts within the network are eliminated by design. This new paradigm builds on top of the Channel Dependency Graph (CDG) in order to deterministically avoid network conflicts. Our solution is able to naturally inject messages using a TDM period equal to the optimal theoretical bound without the need of using a computationally demanding offline process. The network is integrated in a tile-based manycore system and adapted to its memory hierarchy. As a second main contribution, we propose a novel distributed dynamic scheduler that is able to achieve peak performance close to a wormhole-based NoC design without compromising its real-time guarantees. The scheduler builds on top of our NoC design to exploit its key properties. The results of our NoC show that our design guarantees time predictability avoiding network interference among multiple running applications. The network always guarantees performance and also improves wormhole performance in a 4 x 4 setting by a factor of 3.7x when interference traffic is injected. For a 8 x 8 network differences are even larger. In addition, the network obtains a total area saving of 10.79% over a standard wormhole implementation. The proposed scheduler achieves an overall throughput improvement of 6.9x and 14.4x over a baseline conflict-free NoC for 16 and 64-node meshes, respectively. When compared against a standard wormhole router 95% of its network throughput is preserved while strict timing predictability is kept. This achievement opens the door to new high performance time predictable NoC designs. As a final contribution, we build a taxonomy of TDM-based NoCs with real-time properties. With this taxonomy we perform a comprehensive analysis to study and compare from response time specific, to low resource implementation cost, through trade-off solutions for real-time NoCs designs. As a result, we derive new TDM-based NoC designs. / Picornell Sanjuan, T. (2021). Conflict-Free Networks on Chip for Real Time Systems [Tesis doctoral]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/177347 / TESIS

In today's competitive environment, the importance of continuous production, quality improvement, and fast delivery has forced production and delivery processes to become highly reliable. Keeping equipment in good condition through maintenance activities can ensure a more reliable system. However, maintenance leads to temporary reduction in capacity that could otherwise be utilized for production. Therefore, the coordination of maintenance and production is important to guarantee good system performance. The central thesis of this dissertation is that integrating maintenance and production decisions increases efficiency by ensuring high quality production, effective resource utilization, and on-time deliveries. Firstly, we study the problem of integrated maintenance and production planning where machines are preventively maintained in the context of a periodic review production system with uncertain yield. Our goal is to provide insight into the optimal maintenance policy, increasing the number of finished products. Specifically, we prove the conditions that guarantee the optimal maintenance policy has a threshold type. Secondly, we address the problem of integrated maintenance planning and production scheduling where machines are correctively maintained in the context of a dynamic aircraft repair shop. To solve the problem, we view the dynamic repair shop as successive static repair scheduling sub-problems over shorter periods. Our results show that the approach that uses logic-based Benders decomposition to solve the static sub-problems, schedules over longer horizon, and quickly adjusts the schedule increases the utilization of aircraft in the long term. Finally, we tackle the problem of integrated maintenance planning and production scheduling where machines are preventively maintained in the context of a multi-machine production system. Depending on the deterioration process of machines, we design decomposed techniques that deal with the stochastic and combinatorial challenges in different, coupled stages. Our results demonstrate that the integrated approaches decrease the total maintenance and lost production cost, maximizing the on-time deliveries. We also prove sufficient conditions that guarantee the monotonicity of the optimal maintenance policy in both machine state and the number of customer orders. Within these three contexts, this dissertation demonstrates that the integrated maintenance and production decision-making increases the process efficiency to produce high quality products in a timely manner.