Different applications of communication networks have different requirements that depend on the type of application. We consider the problem of differentiating between delay-sensitive applications based on their average delay requirements, as may be of interest in signalling networks. We consider packets of different classes that are to be transmitted on the same link with different average delay requirements, to reside in separate queues with the arrival statistics for the queues being specified. This statistical multiplexer has to schedule packets from different queues in so that the average delays of the queues approach the specified target delays as quickly as possible. For simplicity, we initially consider a discrete-time model with two queues and a single work-conserving server, with independent Bernoulli packet arrivals and unit packet service times. With arrival rates specified, achieving mean queue lengths in a ratio which corresponds to the ratio of target mean delays is a means of achieving individual target mean delays. We formulate the problem in the framework of Markov decision theory. We study two scheduling policies called Queue Length Balancing and Delay Balancing respectively, and show through numerical computation that the expectation of magnitude of relative error in θ (1/m) and θ (1/√m) respectively, and that the expectation of the magnitude of relative error in weighted average delays decays as θ (1/√m) and θ (1/m) respectively, where m is the averaging interval length. We then consider the model for an arbitrary number of queues each with i.i.d. batch arrivals, and analyse the errors in the average delays of individual queues. We assume that the fifth moment of busy period is finite for this model. We show that the expectation of the absolute value of error in average queue length for at least one of the queues decays at least as slowly as θ (1/√m), and that the mean squared error in queue length for at least one of the queues decays at least as slowly as θ (1/m). We show that the expectation of the absolute value of error in approximating Little’s law for finite horizon is 0 (1/m). Hence, we show that the mean squared error in delay for at least one of the queues decays at least slowly as θ (1/m). We also show that if the variance of error in delay decays for each queue, then the expectation of the absolute value of error in delay for at least one of the queues decays at least as slowly as θ (1/√m).

Notre travail s'intègre dans les recherches actuelles sur la continuité optique du traitement et du transport de l'information. Une des techniques visant à assurer cette continuité optique consiste à réaliser une commutation de voies par déflexion holographique. Nous avons étudié théoriquement et expérimentalement la déflexion d'impulsions laser d'une durée voisine de 20 picosecondes par des réseaux photoinduits dans les semiconducteurs. Après avoir décrit et caractérisé les dispositifs expérimentaux, nous présentons les performances de deux matériaux massifs II-VI, CdZnTe (à la longueur d'onde 0,8micron) et HgCdTe (à la longueur d'onde 1,5micron). Dans le domaine spectral de la queue d'Urbach, l'efficacité de diffraction au premier ordre atteint sept pour cent pour les deux matériaux. L'ensemble des résultats expérimentaux est expliqué par un modèle basé sur l'écrantage statique des microchamps électriques locaux dus aux phonons LO. Dans un second temps, nous étudions les réseaux plasma photogénérés dans des puits quantiques InGaAs / InGaAsP inclus dans une cavité de Fabry-Pérot. Les résultats sont comparés à une modélisation prenant en compte les effets de cavité. Ceux-ci induisent une amplification du signal diffracté dont les limites sont discutées. Nous présentons enfin des résultats de modulation de transmission optique dans des puits quantiques CdTe / CdZnTe sous polarisation externe. Nous montrons que les porteurs photogénérés écrantent le champ électrique appliqué produisant ainsi une variation d'absorption par disparition de l'effet Stark dans les puits. Après avoir introduit des coefficients de mérite, nous comparons les performances des différentes structures.

The Cell processor is an example of the trade-offs made when designing a mass market power efficient multi-core machine, but the machine-exposing architecture and raw communication mechanisms of Cell are hard to manage for a programmer. Cell's design is simple and causes software complexity to go up in the areas of achieving low threading overhead, good bandwidth efficiency, and load balance. Several attempts have been made to produce efficient and effective programming systems for Cell, but the attempts have been too specialized and thus fall short. We present Jack Rabbit, an efficient thread pool work queue implementation, with load balancing mechanisms and double buffering. Our system incurs low threading overhead, gets good load balance, and achieves bandwidth efficiency. Our system represents a step towards an effective way to program Cell and any similar current or future processors. / text

Mémoire numérisé par la Division de la gestion de documents et des archives de l'Université de Montréal

Wireless communication is facing an increasingly severe spectrum scarcity problem. Hybrid free space optical (FSO)/ millimetre wavelength (MMW) radio frequency (RF) systems and cognitive radios are two candidate solutions. Hybrid FSO/RF can achieve high data rate transmission for wireless back haul. Cognitive radio transceivers can opportunistically access the underutilized spectrum resource of existing systems for new wireless services. In this work we carry out accurate performance analysis on these two transmission techniques. In particular, we present and analyze a switching based transmission scheme for a hybrid FSO/RF system. Specifically, either the FSO or RF link will be active at a certain time instance, with the FSO link enjoying a higher priority. We consider both a single threshold case and a dual threshold case for FSO link operation. Analytical expressions are obtained for the outage probability, average bit error rate and ergodic capacity for the resulting system. We also investigate the delay performance of secondary cognitive transmission with interweave implementation. We first derive the exact statistics of the extended delivery time, that includes both transmission time and waiting time, for a fixed-size secondary packet. Both work-preserving strategy (i.e. interrupted packets will resume transmission from where interrupted) and non-work-preserving strategy (i.e. interrupted packets will be retransmitted) are considered with various sensing schemes. Finally, we consider a M/G/1 queue set-up at the secondary user and derive the closed-form expressions for the expected delay with Poisson traffic. The analytical results will greatly facilitate the design of the secondary system for particular target application. / Graduate

The BlackPearl in the Computer Engineering Department is an Automotive Demonstrator, which has a variety of sensors, and users can control these via the server. The server is responsible for the remote interaction, the Smart Queue, and the Raspberry Pi display for human interaction. The Automotive Demonstrator consists of four components, which are installed on the CE-Box: Main QML Application, Main Server, Live Stream, and Smart Queue. All of these servers are running on three single-board computers (Raspberry Pi 3B): Main, BlackPearl, and Camera servers. The Automotive Demonstrator is built with the latest version from both Qt and NodeJS, and the components can access, store and exchange the data in JSON format. The BlackPearl will be controlled via four types of interaction methods: Web server, Voice commands (Sparrow), Pi Display, and Gamepad. The outcome of this thesis is a configurable and adaptive User Interface for Automotive Demonstrator, and this can be easily updated, customized, and accessible for new applications without the need to update or rebuild the program.

Στην παρούσα διατριβή προτείνονται μέθοδοι διαχείρισης των κοινόχρηστων πόρων σε υπολογιστικά συστήματα όπου πολλαπλοί επεξεργαστές μοιράζονται το ίδιο ολοκληρωμένο (Chip Multiprocessors – CMPs). Ενώ μέχρι πρόσφατα ο σχεδιασμός ενός υπολογιστικού συστήματος στόχευε στην ικανοποίηση των απαιτήσεων μόνο μίας εφαρμογής ανά χρονική περίοδο, τώρα πια απαιτείται και η εξισορρόπηση των απαιτήσεων διαφορετικών εφαρμογών που ανταγωνίζονται για την κατοχή των ίδιων πόρων. Σε πολλές περιπτώσεις, όμως, αυτό δεν αρκεί από μόνο του. Ακόμη και αν επιτευχθεί κάποιος ιδανικός διαμοιρασμός του πόρου, αν δεν βελτιστοποιηθεί ο τρόπος με τον οποίο χρησιμοποιούν οι επεξεργαστές τον κοινόχρηστο πόρο, δεν θα καταφέρει να εξυπηρετήσει ικανοποιητικά το αυξημένο φορτίο. Για να αντιμετωπιστούν τα προβλήματα που πηγάζουν από τον διαμοιρασμό των κοινόχρηστων πόρων, στην παρούσα εργασία προτείνονται τρεις εναλλακτικοί μηχανισμοί διαχείρισης. Η πρώτη μεθοδολογία εισάγει μία νέα θεωρητική μοντελοποίηση του διαμοιρασμού της κρυφής μνήμης, η οποία μπορεί να χρησιμοποιηθεί παράλληλα με την εκτέλεση των προγραμμάτων που διαμοιράζονται την κρυφή μνήμη. Η μεθοδολογία αξιοποιεί στην συνέχεια αυτήν την μοντελοποίηση, για να ελέγξει τον διαμοιρασμό της κρυφής μνήμης και να επιτύχει δικαιοσύνη στο πως κατανέμεται ο χώρος της κρυφής μνήμης μεταξύ των επεξεργαστών. Η δεύτερη μεθοδολογία παρουσιάζει μία νέα τεχνική για την πρόβλεψη της τοπικότητας των προσπελάσεων της κρυφής μνήμης. Καθώς η τοπικότητα είναι η βασική παράμετρος που καθορίζει την χρησιμότητα των δεδομένων της κρυφής μνήμης, χρησιμοποιώντας αυτήν την τεχνική πρόβλεψης μπορούν να οδηγηθούν μηχανισμοί διαχείρισης που βελτιώνουν την αξιοποίηση του χώρου της κρυφής μνήμης. Στα πλαίσια της μεθοδολογίας παρουσιάζουμε έναν τέτοιο μηχανισμό, ο οποίος στοχεύει στην ελαχιστοποίηση των αστοχιών της κρυφής μνήμης μέσω μίας νέας πολιτικής αντικατάστασης. Η τελευταία μεθοδολογία που παρουσιάζεται είναι μία μεθοδολογία για την μείωση της κατανάλωσης ενέργειας της ουράς εντολών, που είναι μία από τις πιο ενεργειακά απαιτητικές δομές του επεξεργαστή. Στα πλαίσια της μεθοδολογίας, δείχνεται ότι το κλειδί για την αποδοτική μείωση της κατανάλωσης ενέργειας της ουράς εντολών βρίσκεται στην αλληλεπίδραση της με το υποσύστημα μνήμης. Με βάση αυτό το συμπέρασμα, παρουσιάζουμε έναν νέο μηχανισμό δυναμικής διαχείρισης του μεγέθους της ουράς εντολών, ο οποίος συνδυάζει επιθετική μείωση της κατανάλωσης ενέργειας του επεξεργαστή με διατήρηση της υψηλής απόδοσής του. / This dissertation proposes methodologies for the management of shared resources in chip multi-processors (CMP). Until recently, the design of a computing system had to satisfy the computational and storage needs of a single program during each time period. Now instead, the designer has to balance the, perhaps conflicting, needs of multiple programs competing for the same resources. But, in many cases, even this is not enough. Even if we could invent a perfect way to manage sharing, without optimizing the way that each processor uses the shared resource, the resource could not deal efficiently with the increased load. In order to handle the negative effects of resource sharing, this dissertation proposes three management mechanisms. The first one introduces a novel theoretical model of the sharing of the shared cache, which can be used at run-time. Furthermore, out methodology uses the model to control sharing and to achieve a sense of justice in the way the cache is shared among the processors. Our second methodology presents a new technique for predicting the locality of cache accesses. Since locality determines, almost entirely, the usefulness of cache data, our technique can be used to drive any management mechanism which strives to improve the efficiency of the cache. As part of our methodology, we present such a mechanism, a new cache replacement policy which tries to minimize cache misses by near-optimal replacement decisions. The last methodology presented in this dissertation, targets the energy consumption of the processor. To that end, our methodology shows that the key to reducing the power consumption of the Issue Queue, without disproportional performance degradation, lies at the interaction of the Issue Queue with the memory subsystem: as long as the management of the Issue Queue doesn’t reduce the utilization of the memory subsystem, the effects of the management on the processor’s performance will be minimal. Based on this conclusion, we introduce a new mechanism for dynamically resizing the Issue Queue, which achieves aggressive downsizing and energy savings with almost no performance degradation.

Les Réseaux de Capteurs Sans Fil (RCSF) sont de plus en plus exploités par des applications diverses grâce à leur facilité de déploiement et d’auto-configuration. Les applications de collecte de données qui utilisent les RCSF ont souvent un profil convergecast : l’ensemble des données récoltées par tous les capteurs du réseau sont acheminées vers un puits de collecte, grâce à une communication multi-saut. Pendant l’acheminement des données des nœuds de collecte vers le puits, des goulots d’étranglement sont fréquemment observés, principalement au voisinage du puits. Cela est du à la congestion et au phénomène d’entonnoir couramment observé sur le trafic de données ayant un profile convergecast. Outre un risque accru de collision, cela entraîne le débordement des files d’attente des nœuds concernés conduisant à des pertes de données. Cette perte réduit le taux de livraison au puits entraînant une baisse du débit du réseau. Afin de réduire ces pertes et de permettre un meilleur taux de livraison au puits, le trafic doit être équitablement réparti au niveau de chaque saut pendant l’acheminement. Dans cette thèse, nous avons d’une part proposé S-CoLBA (Single channel Collaborative Load Balancing Algorithm), un protocole mono-canal de routage dynamique avec équilibrage de la charge. Sa métrique de routage est basée sur le délais moyen d’accès au medium radio par nœud. Chaque nœud choisit comme prochain saut à destination du puits, un de ses voisins ayant le délais d’accès le plus court. S-CoLBA intègre également une surveillance permanente des files d’attente des nœuds afin de prévenir la congestion et d’éviter le débordement de ces files. D’autre part, nous avons adapté S-CoLBA pour le rendre utilisable dans un réseau multicanal. Cette version du protocole s’appelle M-CoLBA (pour Mulitchannel CoLBA). M-CoLBA évite la congestion en équilibrant la charge grâce à une répartition du trafic au niveau de chaque saut du réseau. Dans un réseau multicanal, le problème de support de diffusion se pose. M-CoLBA introduit des périodes de synchronisations où tous les nœuds utilisent le même canal pour échanger les informations de routage. Ces périodes de synchronisation contribuent à allonger les délais de bout en bout des paquets. Nous avons ainsi optimisé M-CoLBA en "surchargeant" les acquittements des trames avec les informations de routage ( piggybacking) et les états des files d’attente. Cela évite de passer par des périodes de synchronisation pour diffuser ces informations. Cette version optimisée s’appelle ABORt ( Acknowledgement-Based opportunistic Routing protocol). Dans un cas de trafic de type convergecast, ABORt induit une diversité des routes prises par les données collectées, ce qui est bénéfique à la quantité de données transportées et à la robustesse de la solution. Les contributions ont été évaluées par simulation et expérimentation dans un réseau monocanal et multicanal. Les résultats montrent que nos contributions améliorent le taux de livraison des données au puits, optimisent le délais de bout en bout et réduisent la quantité de trafic de contrôle comparé à des solutions déjà existantes. / The popularity of wireless sensor networks (WSNs) is increasing due to their ease ofdeployment and auto-configuration capabilities. They are used in different applica-tion domains including data collection with convergecast scenarios. In convergecast,all data collected in the network is destined to one common node usually called thesink. In case of high carried traffic load and depending on the used routing policy,this many-to-one data collection leads to congestion and queue overflow mainly innodes located near the sink. Congestion and queue overflow reduce delivery ratiothat negatively affects the network efficiency.Wireless sensor nodes are resource constrained devices with limited buffers sizeto store and forward data to the sink. Introducing multichannel communication inWSNs helps to increase the carried traffic load thanks to allowing parallel data trans-mission and reduction of contention and interference. With high traffic load, thenumber of data packets travelling from leaf nodes towards the sink becomes higher.In case the routing scheme does not balance the traffic load, it will be unfairly dis-tributed between forwarding nodes. Thus, nodes that are in part of the routing will beoverloaded while others are less used. Overloaded nodes increase the risk of conges-tion and queue overflow leading to data loss that reduces the throughput. Therefore,we need to couple the routing protocols with traffic load balancing scheme in hightraffic load network scenarios.The goal of this thesis is to propose an efficient routing solution to prevent con-gestion and queue overflow in high data rate convergecast WSNs, in such a way, tooptimize data delivery ratio at the sink node.On the one hand, we proposed a single channel traffic load balancing routingprotocol, named S-CoLBA (Single channel Collaborative Load balancing routing).It relies on data queueing delay metric and best score (according to the value of themetric) next hop neighbors to fairly distribute traffic load in per hop basis in the net-work. Since the carried traffic load increases in multichannel communication, onthe other hand, we adapted our contribution to cope with multichannel WSNs andwe named it as Multichannel CoLBA (M-CoLBA). As broadcasting information isnot straightforward in multichannel, we optimize M-CoLBA to use piggybackingscheme for routing information sharing in the network. This enhanced version iscalled ABORt for Acknowledgement-Based opportunistic Routing protocol and re-lies on ACK frames to share routing information. Doing so helps to optimize dataframe end-to-end delay and to reduce the transmitted beacons in the network. ABORtfairly distributes traffic load in the network and avoids congestion and queue over-flow.We evaluated the performance of our contributions in both simulation using Con-tiki OS Cooja simulator and experiment (only for S-CoLBA) on TelosB motes. Ob-tained results in both simulation and experiment confirm the efficiency of our routingprotocols in term of packet delivery ratio and queue overflow compared to some ex-isting routing protocols in the literature.

Cette thèse présente de nouveaux modèles et de nouveaux résultats en théorie de la ruine, lorsque les distributions des montants de sinistres sont à queue épaisse. Les hypothèses classiques d’indépendance et de stationnarité, ainsi que l’analyse univariée sont parfois jugées trop restrictives pour décrire l’évolution complexe des réserves d’une compagnie d’assurance. Dans un contexte de dépendance entre les montants de sinistres, des équivalents de la probabilité deruine univariée en temps fini sont obtenus. Cette dépendance, ainsi que les autres paramètres du modèle sont modulés par un processus Markovien d’environnement pour prendre en compte des possibles crises de corrélation. Nous introduisons ensuite des modèles de dépendance entre les montants de sinistres et les temps inter-sinistres pour des risques de type tremblements de terre et inondations. Dans un cadre multivarié, nous présentons divers critères de risques tels que la probabilité de ruine multivariée ou l’espérance de l’intégrale temporelle de la partie négative du processus de risque. Nous résolvons des problèmes d’allocation optimale pour ces différentes mesures de risque. Nous étudions alors l’impact de la dangerosité des risques et de la dépendance entre les branches sur cette allocation optimale / This PhD thesis presents new models and new results in ruin theory, in the case where claim amounts are heavy-tailed distributed. Classical assumptions like independence and stationarity and univariate analysis are sometimes too restrictive to describe the complex evolution of the reserves of an insurance company. In a dependence context, asymptotics of univariate finite-time ruin probability are computed. This dependence, and the other model parameters are modulated by a Markovian environment process to take into account possible correlation crisis. Then, we introduce some models which describe dependence between claim amounts and claim interarrival times we can find in earthquake or flooding risks. In multivariate framework, we present some risk criteria like multivariate ruin probability or the expectation of the timeintegrated negative part of the risk process. We solve some problems of optimal allocation for these risk measures. Then, we study the impact of the risk dangerousness and of the dependence between lines on this optimal allocation.

Submitted by Daniele Amaral (daniee_ni@hotmail.com) on 2016-09-13T20:06:59Z No. of bitstreams: 1 DissGSSS.pdf: 12761989 bytes, checksum: 9e4c2b4e76a2502af072064ed081eec1 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-15T13:34:53Z (GMT) No. of bitstreams: 1 DissGSSS.pdf: 12761989 bytes, checksum: 9e4c2b4e76a2502af072064ed081eec1 (MD5) / Approved for entry into archive by Marina Freitas (marinapf@ufscar.br) on 2016-09-15T13:35:23Z (GMT) No. of bitstreams: 1 DissGSSS.pdf: 12761989 bytes, checksum: 9e4c2b4e76a2502af072064ed081eec1 (MD5) / Made available in DSpace on 2016-09-15T13:35:30Z (GMT). No. of bitstreams: 1 DissGSSS.pdf: 12761989 bytes, checksum: 9e4c2b4e76a2502af072064ed081eec1 (MD5) Previous issue date: 2014-11-19 / Não recebi financiamento / Loop pipelining is a technique that may offer significant performance improvements, being employed not only in conventional compilation targeting microprocessors, but also by High Level Synthesis (HLS) tools, targeting heterogeneous architectures and hardware accelerators. This work presents a specialized hardware support aiming at facilitate compilation tasks for HLS tools, along with potential advantages in execution performance and total silicon area employed. Two specialized hardware modules are presented: a queue register file and an instruction predication control module. / O desempenho na execução de programas, que é cada vez mais uma prioridade, pode ter uma melhora significativa por meio do uso de paralelismo em nível de instrução (ILP). Uma técnica que utiliza o ILP e propicia ganhos de desempenho significativos é o loop pipelining, sendo usado não apenas por compiladores para microprocessadores, mas também por ferramentas de Síntese de Alto Nível (HLS), visando arquiteturas heterogêneas e aceleradores de hardware. Neste trabalho é apresentado o projeto e implementação de estruturas de hardware especializadas, objetivando-se em solucionar o problema de sobreposição de valores que ocorre no loop pipelining, facilitar tarefas de compilaçãoo em ferramentas HLS e diminuir a repetição de código. Além disso, ganhos potenciais de desempenho e área de silício total podem ser alcançados como resultado do uso das estruturas propostas. Serão apresentados: um arquivo de registradores baseado em filas e um módulo de controle para a execução de instruções predicadas.