Spelling suggestions: "subject:"multikulti""
91 |
Architecture Through the Senses: Navigating a World Without NoiseLe, Kim 04 June 2024 (has links)
For this thesis, I engage in a comprehensive study of Deaf culture by learning American Sign Language (ASL) and immersing myself within the Deaf community. My objective is to gain insights into their unique modes of interaction, daily lives, and spatial preferences. The research is motivated by the aspiration to apply this profound understanding to the design of a deaf-friendly academic building on Gallaudet University's campus. It is also motivated by the multi-sensory experience of architecture and it's impact on the users experiencing the space.
Situated prominently in front of the historic Union Market, which serves as a gathering point for people from all corners of Washington, D.C., the envisioned building aims to bridge the gap between Gallaudet University's enclosed campus and the bustling city. Through an innovative design approach, it seeks to impart a new identity to the campus, fostering inclusivity and connectivity.
The design process involves a meticulous analysis of the campus site across three distinct scales: city/campus, building, and user. Each scale informs different design moves of the proposed academic building through the exploration of the relationship between: the user and the building, the building and the campus, and the campus and the city. This approach ensures a holistic integration of new information, resulting in a structure that not only embraces DeafSpace principles but also addresses the broader context of the urban environment.
Beyond architectural aesthetics, the proposed structure will play a pivotal role in revitalizing the neglected part of the campus. By integrating Hansel Bauman's DeafSpace principles, it will serve as an example of how architecture can be enabling rather than disabling through discovering what accessibility means to the Deaf community, creating a vibrant hub that harmonizes with the existing environment and brings new life into the overlooked area.
This research not only contributes to a deeper understanding of Deaf culture but also showcases the potential of architectural design to facilitate meaningful connections, foster inclusivity, and rejuvenate neglected spaces within educational institutions. / Master of Architecture / For this thesis, I explore Deaf culture by learning American Sign Language (ASL) and engaging with the Deaf community. My goal is to understand their unique ways of communicating and living, which will inform the design of a new academic building at Gallaudet University, a school for the Deaf. This research is inspired by the idea that architecture can deeply affect how people experience spaces.
The proposed academic building will be located near the historic Union Market in Washington, D.C., creating a connection between the university's campus and the city. This design aims to give the campus additional space that fosters inclusivity, connectivity, and accessibility.
To create this design, I carefully studied the campus from three perspectives: the city and the campus, the building itself, and the individual user. This supports an understanding of how the new building interacts with its surrounding urban environment and its users.
The design will incorporate DeafSpace principles, developed by architect Hansel Bauman, which focus on the specific needs of the Deaf community. The new building is intended to make the campus more accessible and welcoming, transforming an underused part of the university into a vibrant, engaging space.
This project highlights how understanding Deaf culture can lead to better architectural designs that foster inclusion and revitalization within educational environments.
|
92 |
Apport du couplage entre dynamique d’apprentissage et propriétés collectives dans l’optimisation multi-contraintes par un système multi-agents et multi-robots / Contribution of the coupling between dynamic learning and collective properties in a multi-constraints optimizations by a multi-agent system and multi-robotsChatty, Abdelhak 30 June 2014 (has links)
Dans ce travail, nous proposons un système auto-organisé composé d'agents-robots contrôlés par une architecture de subsomption et des règles locales probabilistes de prises et de dépôts. Ces agents-robots sont capables, grâce au développement de leurs capacités cognitives de se créer une carte cognitive, d'apprendre plusieurs lieux buts et de planifier le retour vers ces buts. Bien que formellement l'algorithme ne permette pas à chaque agent de "mélanger ni de fusionner ou d'optimiser" plusieurs objectifs, nous montrerons que le système global est capable de réaliser une optimisation multi-objectifs. Particulièrement, la fusion de l'apprentissage local avec l'accumulation de décisions individuelles permet de faire émerger (i) des structures dans l'environnement et (ii) des dynamiques tel que le comportement de spécialisation ou les comportements que nous pouvons considérer comme étant "égoïstes" ou "altruistes". Nous montrons qu'un mécanisme d'imitation simple contribue à l'amélioration des performance de notre SMAC et de notre SMRC, à savoir l'optimisation de la durée pour découvrir des différentes ressources, le temps moyen de planification, le niveau global de satisfaction des agents et enfin le temps moyen de convergence vers une solution stable. Particulièrement, l'ajout d'une capacité d'imitation améliore la construction des cartes cognitives pour chaque agent et stimule le partage implicite des informations dans un environnement a priori inconnu. En effet, les découvertes individuelles peuvent avoir un effet au plan social et donc inclure l'apprentissage de nouveaux comportements au niveau individuel. Pour finir, nous comparons les propriétés émergentes de notre SMAC à un modèle mathématique basé sur la programmation linéaire (PL). Cette évaluation montre les bonnes performances de notre SMAC qui permet d'avoir des solutions proches des solutions de la PL pour un coût de calcul réduit. Dans une dernière série d'expériences, nous étudions notre système d'agrégation dans un environnement réel. Nous mettons en place un SMRC, composé par des robots qui sont capables d'effectuer les opérations de prise, de dépôt et de maintien. Nous montrons via les premiers tests d'agrégation que les résultats sont prometteurs. / In this work, we propose a self-organized system composed by agents-robots, controlled by a subsumption architecture with probabilistic local rules of deposits and taking. These agents-robots are able, thanks to the development of their cognitive abilities to create a cognitive map, to learn various goals' locations and to plan the return to these goals. Although formally the algorithm does not allow each agent to « mix or merge or optimize » several objectives, we show that the overall system is able to perform a multi-objective optimization. Specifically, the fusion of local learning with the accumulation of the individual decisions allows to emerge (i) structures in the environment and (ii) several dynamics such as specialization behavior or those that we can consider as « selfish » or « altruistic ». We show that the imitation strategy contributes to the improvement of the performance of our SMAC and our SMRC, namely the optimization of time to explore the various resources, the average planning time, the overall satisfaction level of agents and finally the the average time of convergence to a stable solution. Specifically, the addition of an imitation ability improves the construction of cognitive maps for each agent and stimulates the implicit sharing of informations in an unknown environment. Indeed, individual discoveries can affect the social level and therefore include learning new behaviors at the individual level. Finally, we compare the emergent properties of our SMAC with a mathematical model based on linear programming (LP). This evaluation shows the good performance of our SMAC which allows to obtain solutions close to the solution of the PL for a low cost of computation. In a final series of experiments, we study our aggregation system in a real environment. We set up a SMRC, composed by robots that are able to perform taking operations, deposits operations and refueling operations. We show through the first tests of aggregation that the results are promising.
|
93 |
A COMPACT, LIGHTWEIGHT, LOW POWER, MULTI-FUNCTION TELEMETRY RECEIVER/COMBINER SYSTEM PROVIDES "HANDS OFF" AUTOMATION FOR SYSTEMS COST REDUCTIONO'Cull, Douglas C. 10 1900 (has links)
International Telemetering Conference Proceedings / October 17-20, 1994 / Town & Country Hotel and Conference Center, San Diego, California / With the increased concerns for reducing cost and improving
reliability in today's telemetry systems, many users are
employing simulation and automation to guarantee reliable
telemetry systems operation. This places an increased demand
on the remote capabilities of the equipment used in the
telemetry system. Furthermore, emphasis has been placed on
the ability to decrease the space and power consumption of
the telemetry system to facilitate transportability of the a
single telemetry system to multiple sites. Finally, today's
telemetry systems demand that all equipment provide multiple
functions to provide the maximum performance for the lowest
system cost.
|
94 |
Multi-mode antennas for hemispherical field-of-view coveragePrinsloo, David Schalk Van der Merwe 03 1900 (has links)
Thesis ((PhD)--Stellenbosch University, 2015. / ENGLISH ABSTRACT: This dissertation proposes a multi-mode antenna element excited through a multiconductor
feed. It is shown that each of the orthogonal transverse electromagnetic modes supported by
the antenna feed results in a unique radiated far-field pattern that collectively allow for nearhemispherical
field-of-view coverage.
Three multi-mode antenna designs are presented: a dual-mode antenna, integrating a single linearly
polarised dipole antenna with a co-located monopole, as well as two quad-mode antenna
designs integrating two dual-polarised dipole elements with a co-located monopole element.
The dual-mode antenna is excited through a balanced transmission line feed supporting both
differential- and common-mode signals that, respectively, result in typical dipole-over-ground
and monopole radiated far-field patterns. The quad-mode antennas are each fed through a
quadraxial transmission line allowing for excitation through four orthogonal transverse electromagnetic
port modes.
To characterise the multi-mode response of the multi-mode antennas, generalised transformations
are derived by which the multi-mode S-parameters and radiated far-fields can be calculated
from the S-parameters and far-fields corresponding to single-ended excitations. These transformations
are implemented to validate the response of a dual-mode and quad-mode antenna design
through measurements.
An equivalent network representation for active multi-mode antennas is presented, including generalised
transformations relating the multi-mode signal and noise response of the low-noise amplifiers
to the two-port S-parameters and noise parameters of the low-noise amplifiers. Through
the use of classical beamforming algorithms, the performance of an active dual-mode and quadmode
antenna is presented. In the case of the active dual-mode antenna, it is shown that through
the added use of common-mode signals, a variation in sensitivity of less than 50% is achieved
in the E-plane. Similarly, the additional excitation modes supported by the active quad-mode
antenna is shown to result in a significant improvement in the polarimetric capabilities over the
field-of-view coverage. / AFRIKAANSE OPSOMMING: Hierdie proefskrif stel ’n multimodale antenna element voor wat deur ’n multi-geleier transmissielyn
gevoer word. Dit word gewys dat elk van die ortogonale transversale elektromagnetiese
opwekkingsmodusse wat deur die antenna voer ondersteun word, ’n unieke vêrveld stralingspatroon
skep, wat gesamentlik lei tot ’n hemisferiese gesigsveld.
Drie multimodale antenna ontwerpe word voorgestel: ’n dubbelmodale antenna, waarin ’n enkel
lineêrgepolariseerde dipool antenna en monopool mede-geleë word, asook twee viermodale antenna
ontwerpe waarin twee dubbelgepolariseerde dipool elemente geïntegreer word met medegeleë
monopool antenna elemente. Die dubbelmodale antenna word gevoer deur ’n gebalanseerde
transmissielyn wat beide differensiële- en gemene-modus seine ondersteun, waar elk onderskeidelik
dipool-oor-aardvlak en monopool stralingspatrone voortbring. Die viermodale antennas
word elk gevoer deur vier-as transmissielyne wat vier ortogonale transversale elektromagnetiese
opwekkingsmodusse ondersteun.
Om die multimodale gedrag van die drie multimodale antennas te karakteriseer, word veralgemeende
transformasies afgelei waardeur die multimodale strooiingsparameters asook die vêrveld
stralingspatrone vanaf enkelpoort strooiingsparameters en vêrvelde bereken word. Hierdie transformasies
word toegepas om die gedrag van ’n dubbel- en viermodale antenna ontwerp te karakteriseer
deur metings.
Ekwivalente netwerkvoorstellings vir aktiewe multimodale antennas word voorgestel, insluitend
veralgemeende transformasies om die multimodale sein asook ruis gedrag van die lae-ruis versterkers
betreklik te maak tot die tweepoort strooiingsparameters en ruisparameters van die laeruis
versterkers. Deur gebruik te maak van klasieke bundelvormingsalgoritmes, word die gedrag
van aktiewe dubbelmodale en viermodale antennas voorgestel. Vir die aktiewe dubbelmodale
antenna word daar aangedui dat die gesamentlike gebruik van differensiële- en gemene-modus
seine, ’n variasie in sensitiwiteit onder 50% tot gevolg het in die E-vlak. Soortgelyk word daar
aangedui dat die addisionele opwekkingsmodusse wat deur die aktiewe viermodale antenna ondersteun
word, tot ’n beduidende verbetering in die polarisasievermoë oor die gesigsveld lei.
|
95 |
Integration of unidirectional technologies into wireless back-haul architectureKretschmer, Mathias Raimund Otto January 2012 (has links)
Back-haul infrastructures of today's wireless operators must support the triple-play services demanded by the market or regulatory bodies. To cope with increasing capacity demand, the EU FP7 project CARMEN has developed a cost-effective heterogeneous multi-radio wireless back-haul architecture, which may also leverage the native multicast capabilities of broadcast technologies such as DVB-T to off-load high-bandwidth broadcast content delivery. However, the integration of such unidirectional technologies into a packet-switched architecture requires careful considerations. The contribution of this thesis is the investigation, design and evaluation of protocols and mechanisms facilitating the integration of such unidirectional technologies into the wireless back-haul architecture so that they can be configured and utilized by the spectrum and capacity optimization modules. This integration mainly concerns the control plane and, in particular, the aspects related to resource and capability descriptions, neighborhood, link and Multi Protocol Label Switching (MPLS) Label-Switched Path (LSP) monitoring, unicast and multicast LSP signalling as well as topology forming and maintenance. During the course of this study we have analyzed the problem space, proposed solutions to the resulting research questions and evaluated our approach. Our results show that the now Unidirectional Technology (UDT)-aware architecture can readily consider Unidirectional Technologies (UDTs) to distribute, for example, broadcast content.
|
96 |
Une approche globale pour la métrologie 3D automatique multi-systèmes / A global approach for automatic 3D part inspectionAudfray, Nicolas 17 December 2012 (has links)
La métrologie 3D permet la vérification de spécifications géométriques et dimensionnelles sur des pièces mécaniques. Ce contrôle est classiquement réalisé à partir de mesures avec des capteurs à contact montés sur des machines à mesurer tridimensionnelles. Ce type de mesures offre une très grande qualité de données acquises mais requiert un temps d'exécution relativement long. Les présents travaux s'attachent donc à développer les mesures optiques dans le cadre de la métrologie 3D qui, avec une qualité diminuée, permettent une exécution beaucoup plus rapide. L'absence de norme concernant ces systèmes de mesure a pour conséquence leur utilisation rare dans le cadre de la métrologie. En effet, le choix d'un système est généralement réalisé à partir de spécifications sur sa qualité. Nous proposons donc une méthode de qualification des systèmes de mesure optiques permettant de quantifier la qualité des données qu'ils fournissent. Les données ainsi qualifiées sont stockées dans une base de données. Un processus global d'inspection 3D multi-systèmes est mis en place, permettant le choix du système de numérisation le mieux adapté (à contact ou sans contact) en termes de qualité et de coût de numérisation, à partir des données qualifiées de la base de données. Lors de l'utilisation de systèmes de mesure optiques, la baisse de qualité est essentiellement due au bruit de numérisation inhérent à ce type de systèmes. Un filtre permettant d'éliminer ce bruit, tout en gardant le défaut de forme de la surface, est mis en place dans le processus afin de rendre possible la vérification de spécifications avec des intervalles de tolérance faibles à l'aide de systèmes de mesure optiques. / 3D metrology allows GD\&{}T verification on mechanical parts. This verification is usually calculated using data obtained with a touch probe mounted on a coordinate measuring machine. Such a measurement offers a high data quality but requires an expensive processing time. The proposed research aims at expanding optical measurements in 3D metrology, reducing execution time but with a lower data quality. The lack of standard in this field makes the use of optical sensors uncommon in 3D metrology. Indeed, the system selection is mostly carried out from its quality specifications. Therefore we propose a protocol to assess the quality of optical measuring systems that allows in particular quantification of acquired data quality. The results of measuring system qualification are stored in a database. Taking advantages of this database, a global multi-system 3D inspection process is set up allowing the selection of the best digitizing system (contact or contactless) in terms of quality and digitizing cost. When using optical sensors, the poor quality is mostly due to digitizing noise inherent to this kind of systems. A filter that removes noise, keeping the form deviation of the surface, is proposed in the process to make possible the specification verification for applications with small tolerance intervals using optical systems.
|
97 |
Modélisation et score de complexes protéine-ARN / Modelling and scoring of protein-RNA complexesGuilhot-Gaudeffroy, Adrien 29 September 2014 (has links)
Cette thèse présente des résultats dans le domaine de la prédiction d’interactions protéine-ARN. C’est un domaine de recherche très actif, pour lequel la communauté internationale organise régulièrement des compétitions pour évaluer différentes techniques de prédictions in silico d’interactions protéine-protéine et protéine-ARN sur des données benchmarks (CAPRI, Critical Assessment of PRedictedInteractions), par prédiction en aveugle et en temps limité. Dans ce cadre, de nombreuses approches reposant sur des techniques d’apprentissage supervisé ont récemment obtenus de très bons résultats.Nos travaux s’inscrivent dans cette démarche.Nous avons travaillé sur des jeux de données de 120 complexes protéine-ARN extraits de la PRIDB non redondante (Protein-RNA Interface DataBase, banque de données de référence pour les interactions protéine-ARN). La méthodologie de prédiction d'interactions protéine-ARN a aussi été testée sur 40 complexes issus de benchmarks de l'état de l'art et indépendants des complexes de la PRIDB non redondante. Le faible nombre de structures natives et la difficulté de générer in silico des structures identiques à la solution in vivo nous a conduit à mettre en place une stratégie de génération de candidats par perturbation de l’ARN partenaire d’un complexe protéine-ARN natif. Les candidats ainsi obtenus sont considérés comme des conformations presque-natives si elles sont suffisamment proches du natif. Les autres candidats sont des leurres. L’objectif est de pouvoir identifier les presque natifs parmi l’ensemble des candidats potentiels, par apprentissage supervisé d'une fonction de score.Nous avons conçu pour l'évaluation des fonctions de score une méthodologie de validation croisée originale appelée le leave-"one-pdb"-out, où il existe autant de strates que de complexes protéine-ARN et où chaque strate est constituée des candidats générés à partir d'un complexe. L’une des approches présentant les meilleures performances à CAPRI est l’approche RosettaDock, optimisée pour la prédiction d’interactions protéine-protéine. Nous avons étendu la fonction de score native de RosettaDock pour résoudre la problématique protéine-ARN. Pour l'apprentissage de cette fonction de score, nous avons adapté l'algorithme évolutionnaire ROGER (ROC-based Genetic LearnER) à l'apprentissage d'une fonction logistique. Le gain obtenu par rapport à la fonction native est significatif.Nous avons aussi mis au point d'autres modèles basés sur des approches de classifieurs et de métaclassifieurs, qui montrent que des améliorations sont encore possibles.Dans un second temps, nous avons introduit et mis en oeuvre une nouvelle stratégie pour l’évaluation des candidats qui repose sur la notion de prédiction multi-échelle. Un candidat est représenté à la fois au niveau atomique, c'est-à-dire le niveau de représentation le plus détaillé, et au niveau dit “gros-grain”où nous utilisons une représentation géométrique basée sur des diagrammes de Voronoï pour regrouper ensemble plusieurs composants de la protéine ou de l’ARN. L'état de l'art montre que les diagrammes de Voronoï ont déjà permis d'obtenir de bons résultats pour la prédiction d'interactions protéine-protéine. Nous en évaluons donc les performances après avoir adapté le modèle à la prédiction d'interactions protéine-ARN. L’objectif est de pouvoir rapidement identifier la zone d’interaction (épitope) entre la protéine et l’ARN avant d’utiliser l’approche atomique, plus précise,mais plus coûteuse en temps de calcul. L’une des difficultés est alors de pouvoir générer des candidats suffisamment diversifiés. Les résultats obtenus sont prometteurs et ouvrent desperspectives intéressantes. Une réduction du nombre de paramètres impliqués de même qu'une adaptation du modèle de solvant explicite pourraient en améliorer les résultats. / My thesis shows results for the prediction of protein-RNA interactions with machine learning. An international community named CAPRI (Critical Assessment of PRedicted Interactions) regularly assesses in silico methods for the prediction of the interactions between macromolecules. Using blindpredictions within time constraints, protein-protein interactions and more recently protein-RNA interaction prediction techniques are assessed.In a first stage, we worked on curated protein-RNA benchmarks, including 120 3D structures extracted from the non redundant PRIDB (Protein-RNA Interface DataBase). We also tested the protein-RNA prediction method we designed using 40 protein-RNA complexes that were extracted from state-ofthe-art benchmarks and independent from the non redundant PRIDB complexes. Generating candidates identical to the in vivo solution with only a few 3D structures is an issue we tackled by modelling a candidate generation strategy using RNA structure perturbation in the protein-RNAcomplex. Such candidates are either near-native candidates – if they are close enough to the solution– or decoys – if they are too far away. We want to discriminate the near-native candidates from thedecoys. For the evaluation, we performed an original cross-validation process we called leave-”onepdb”-out, where there is one fold per protein-RNA complex and each fold contains the candidates generated using one complex. One of the gold standard approaches participating in the CAPRI experiment as to date is RosettaDock. RosettaDock is originally optimized for protein-proteincomplexes. For the learning step of our scoring function, we adapted and used an evolutionary algorithm called ROGER (ROC-based Genetic LearnER) to learn a logistic function. The results show that our scoring function performs much better than the original RosettaDock scoring function. Thus,we extend RosettaDock to the prediction of protein-RNA interactions. We also evaluated classifier based and metaclassifier-based approaches, which can lead to new improvements with further investigation.In a second stage, we introduced a new way to evaluate candidates using a multi-scale protocol. A candidate is geometrically represented on an atomic level – the most detailed scale – as well as on a coarse-grained level. The coarse-grained level is based on the construction of a Voronoi diagram over the coarse-grained atoms of the 3D structure. Voronoi diagrams already successfully modelled coarsegrained interactions for protein-protein complexes in the past. The idea behind the multi-scale protocolis to first find the interaction patch (epitope) between the protein and the RNA before using the time consuming and yet more precise atomic level. We modelled new scoring terms, as well as new scoring functions to evaluate generated candidates. Results are promising. Reducing the number of parameters involved and optimizing the explicit solvent model may improve the coarse-grained level predictions.
|
98 |
Intégration de MEMS pour la réalisation d’ une antenne spirale à hautes performances reconfigurable / MEMS integration for the design of high performance reconfigurable spiral antennaMassiot, Jérôme 28 November 2013 (has links)
L'émergence de nouveaux systèmes de radar et de télécommunication nécessite des antennes adaptables en temps réel. Les antennes reconfigurables permettent de répondre à ce besoin par le biais d'une reconfiguration en fréquence, en polarisation ou en diagramme de rayonnement. En outre, les switchs MEMS sont des composants particulièrement attrayants pour reconfigurer une antenne car ils consomment peu et ont de faibles niveaux de pertes. La thèse porte sur l'intégration de MEMS dans une antenne spirale ultra large bande; les objectifs étant : • maitriser l'intégration de MEMS packagés dans une antenne ; • reconfigurer la spirale pour rejeter les fréquences en dehors de la bande utile ; • réaliser des prototypes et effectuer des validations expérimentales. Le mécanisme de rayonnement d'une spirale a été étudié pour identifier les possibilités de reconfiguration de l'élément rayonant. L'une d'elles a été étudiée et mise en œuvre en ajoutant des éléments au cœur de l'antenne spirale. Des antennes spirales avec et sans mécanismes de reconfiguration ont été réalisées et testées. L'antenne de base (sans résonateurs) présente des caractéristiques particulièrement intéressantes : fonctionnement sur la bande 4-20 GHz, gain relativement important de 5 à 9 dBi, et une faible épaisseur de 3.5 mm. La réjection obtenue en simulation s'est avérée difficile à prouver expérimentalement du fait des difficultés d'intégration de MEMS packagés sur l' antenne. / The evolution of radar and telecommunication systems needs antennas, which are able to adapt their performances in real time. Reconfigurable antennas can provides such characteristics through a reconfiguration of the frequency of operation, the polarisation or the radiation patterns. Besides, MEMS switches present attractive assets for reconfiguring a radiating element as they consume low power and have low losses. The thesis is about the integration of MEMS within an ultra wide band spiral antenna. The objectives of the thesis are: • To master the integration of packaged MEMS in an antenna • To reconfigure the spiral antenna for the achievement of a band rejection • To manufacture some prototypes and carry out experimental validations The radiation property of the spiral antenna has been studied. A reconfiguration of the spiral, which consists of inserting added elements within the radiating structure, has been investigated and applied. Spiral antennas with and without the reconfiguration mechanism have been manufatured and tested. The basic spiral antenna (without the reconfiguration mechanism) presents interesting properties: ultra wide band characteristics from 4 to 20 GHz, a relatively high gain of 5 to 9 dBi, and a low profile thickness of 3.5 mm. In practice, the achieved rejection has been difficult to prove due to the difficulties related to the integration of the packaged MEMS.
|
99 |
The management of multiple submissions in parallel systems: the fair scheduling approach / La gestion de plusieurs soumissions dans les systèmes parallèles: l\'approche d\'ordonnancement équitablePinheiro, Vinicius Gama 14 February 2014 (has links)
The High Performance Computing community is constantly facing new challenges due to the ever growing demand for processing power from scientific applications that represent diverse areas of human knowledge. Parallel and distributed systems are the key to speed up the execution of these applications as many jobs can be executed concurrently. These systems are shared by many users who submit their jobs over time and expect a fair treatment by the scheduler. The work done in this thesis lies in this context: to analyze and develop fair and efficient algorithms for managing computing resources shared among multiple users. We analyze scenarios with many submissions issued from multiple users over time. These submissions contain several jobs and the set of submissions are organized in successive campaigns. In what we define as the Campaign Scheduling model, the jobs of a campaign do not start until all the jobs from the previous campaign are completed. Each user is interested in minimizing the flow times of their own campaigns. This is motivated by the user submission behavior whereas the execution of a new campaign can be tuned by the results of the previous campaign. In the first part of this work, we define a theoretical model for Campaign Scheduling under restrictive assumptions and we show that, in the general case, it is NP-hard. For the single-user case, we show that an approximation scheduling algorithm for the (classic) parallel job scheduling problem also delivers the same approximation ratio for the Campaign Scheduling problem. For the general case with multiple users, we establish a fairness criteria inspired by time sharing. Then, we propose a scheduling algorithm called FairCamp which uses campaign deadlines to achieve fairness among users between consecutive campaigns. The second part of this work explores a more relaxed and realistic Campaign Scheduling model, provided with dynamic features. To handle this setting, we propose a new algorithm called OStrich whose principle is to maintain a virtual time-sharing schedule in which the same amount of processors is assigned to each user. The completion times in the virtual schedule determine the execution order on the physical processors. Then, the campaigns are interleaved in a fair way. For independent sequential jobs, we show that OStrich guarantees the stretch of a campaign to be proportional to campaigns size and to the total number of users. The stretch is used for measuring by what factor a workload is slowed down relatively to the time it takes to be executed on an unloaded system. Finally, the third part of this work extends the capabilities of OStrich to handle parallel jobs. This new version executes campaigns using a greedy approach and uses an event-based resizing mechanism to shape the virtual time-sharing schedule according to the system utilization ratio. / La communauté de Calcul Haute Performance est constamment confrontée à de nouveaux défis en raison de la demande toujours croissante de la puissance de traitement provenant dapplications scientifiques diverses. Les systèmes parallèles et distribués sont la clé pour accélérer lexécution de ces applications, et atteindre les défis associés car de nombreux processus peuvent être exécutés simultanément. Ces systèmes sont partagés par de nombreux utilisateurs qui soumettent des tâches sur de longues périodes au fil du temps et qui attendent un traitement équitable par lordonnanceur. Le travail effectué dans cette thèse se situe dans ce contexte: analyser et développer des algorithmes équitables et efficaces pour la gestion des ressources informatiques partagés entre plusieurs utilisateurs. Nous analysons les scénarios avec de nombreux soumissions issues de plusieurs utilisateurs. Ces soumissions contiennent un ou plusieurs processus et lensemble des soumissions sont organisées dans des campagnes successives. Dans ce que nous appelons le modèle dordonnancement des campagnes les processus dune campagne ne commencent pas avant que tous les processus de la campagne précédente soient terminés. Chaque utilisateur est intéressé à minimiser la somme des temps dexécution de ses campagnes. Cela est motivé par le comportement de lutilisateur tandis que lexécution dune campagne peut être réglé par les résultats de la campagne précédente. Dans la première partie de ce travail, nous définissons un modèle théorique pour lordonnancement des campagnes sous des hypothèses restrictives et nous montrons que, dans le cas général, il est NP-difficile. Pour le cas mono-utilisateur, nous montrons que lalgorithme dapproximation pour le problème (classique) dordonnancement de processus parallèles fournit également le même rapport dapproximation pour lordonnancement des campagnes. Pour le cas général avec plusieurs utilisateurs, nous établissons un critère déquité inspiré par une situation idéalisée de partage des ressources. Ensuite, nous proposons un algorithme dordonnancement appelé FairCamp qui impose des dates limite pour les campagnes pour assurer léquité entre les utilisateurs entre les campagnes successives. La deuxième partie de ce travail explore un modèle dordonnancement de campagnes plus relâché et réaliste, avec des caractéristiques dynamiques. Pour gérer ce cadre, nous proposons un nouveau algorithme appelé OStrich dont le principe est de maintenir un ordonnancement partagé virtuel dans lequel le même nombre de processeurs est assigné à chaque utilisateur. Les temps dachèvement dans lordonnancement virtuel déterminent lordre dexécution sur le processeurs physiques. Ensuite, les campagnes sont entrelacées de manière équitable. Pour des travaux indépendants séquentiels, nous montrons que OStrich garantit le stretch dune campagne en étant proportionnel à la taille de la campagne et le nombre total dutilisateurs. Le stretch est utilisé pour mesurer le ralentissement par rapport au temps quil prendrait dans un système dédié. Enfin, la troisième partie de ce travail étend les capacités dOStrich pour gérer des tâches parallèles rigides. Cette nouvelle version exécute les campagnes utilisant une approche gourmande et se sert aussi dun mécanisme de redimensionnement basé sur les événements pour mettre à jour lordonnancement virtuel selon le ratio dutilisation du système.
|
100 |
Estratégias de escalonamento de workflows com tarefas paralelas e sequenciais em grades computacionais. / Strategies for scheduling workflows composed of sequential and parallel tasks on grid environments.Stanzani, Silvio Luiz 18 October 2013 (has links)
A demanda por alto desempenho é um desafio enfrentado por diversas aplicações científicas. Nesse sentido, ambientes para processamento distribuído, tais como, clusters e grades computacionais, têm sido desenvolvidos para prover suporte ao uso de diversos recursos simultaneamente para uma mesma aplicação. Aplicações computacionalmente intensivas são organizadas em workflows e executadas com suporte de middlewares para abstrair a complexidade de uso de tais ambientes. Em ambientes de grade computacional, a execução de workflows contendo tarefas sequenciais e tarefas com paralelismo interno, obtendo bom desempenho, é um desafio, devido à heterogeneidade e comportamento dinâmico do ambiente. Nesse sentido, o escalonamento de workflows em ambientes de grade computacional é essencial. O problema de escalonamento de tarefas, em sua forma geral, é NPCompleto, dessa forma, o estudo do escalonamento de workflows em ambientes de grade computacional é fundamental para aprimorar a execução de aplicações computacionalmente intensivas. O objetivo dessa tese é propor estratégias de escalonamento de workflows, que exploram os seguintes aspectos: Avaliação da possibilidade de executar cada tarefa com paralelismo interno usando recursos de múltiplos clusters; Adaptação de planos de escalonamento no momento da submissão de novos workflows. Foram desenvolvidas duas estratégias: a primeira é uma estratégia para escalonamento estático de workflows, que considera o ambiente dedicado a execução de um workflow. A segunda foi desenvolvida para ser utilizada em conjunto com a primeira, para melhorar o tempo de resposta de múltiplos workflows que podem ser submetidos em diferentes momentos. As estratégias propostas foram avaliadas em um ambiente de simulação. / The demand for high performance is a common problem in many scientific applications. In this sense, distributed processing environments such as cluster, grid computing and multi-cluster environments have been developed to provide support for the use of several resources simultaneously for the same application. Computationally intensive applications are structured as workflows and executed with the support of middleware to abstract the complexity of using such environments. In grid computing environments the execution of workflows containing sequential and parallel tasks, with good performance is a challenge due to the heterogeneity and dynamic behavior of the environment. In this sense, the scheduling of workflows on grid computing environments is essential. The task scheduling problem in its general form is NP-Complete, in this sense, the study concerning workflow scheduling in grid computing environments is fundamental to improve the performance of computationally intensive applications. The aim of this thesis is to propose strategies for scheduling workflows that exploit the following aspects: Explore the possibility of performing single parallel tasks using multiple clusters; Adaptation plans escalation in accordance with the submission of new workflows. Two strategies were developed: the first one is a strategy for static scheduling of workflows, which considers a dedicated environment to the execution of a workflow. The second one was developed to use in conjunction with the first one, in order to improve the response time of multiple workflows that can be submitted at different times. The proposed strategies were evaluated in a simulation environment.
|
Page generated in 0.0475 seconds