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.

A key part in the development and verification of digital systems is simulation. But hardware simulators are expensive, and software simulation is not fast enough for designs with a large number of gates. As today’s digital zesigns constantly grow in size (number of gates), and that trend shows no signs to end, faster simulators handling millions of gates are needed. We investigate how to create a software gate-level simulator able to simulate a high number of gates fast. This involves a trade-off between memory requirement and speed. A compact netlist representation can utilize cache memories more efficient but requires more work to interpret, while high memory requirements can limit the performance to the speed of main memory. We have selected the Counting Algorithm to implement the experimental simulator MICA. The main reasons for this choice is the compact way in which gates can be stored, but still be evaluated in a simple and standard way. The report describes the issues and solutions encountered and evaluate the resulting simulator. MICA simulates a SPARC architecture processor called Leon. Larger netlists are achieved by simulating several instances of this processor. Simulation of 128 instances is done at a speed of 9 million gates per second using only 3.5MB memory. In MICA this design correspond to 2.5 million gates.

Submitted by Caroline Falcao (caroline.rfalcao@ufpe.br) on 2017-06-05T16:18:45Z No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tamires Taís.pdf: 9141530 bytes, checksum: dab991dd87283a9e223705028b80d093 (MD5) / Made available in DSpace on 2017-06-05T16:18:45Z (GMT). No. of bitstreams: 2 license_rdf: 811 bytes, checksum: e39d27027a6cc9cb039ad269a5db8e34 (MD5) Tamires Taís.pdf: 9141530 bytes, checksum: dab991dd87283a9e223705028b80d093 (MD5) Previous issue date: 2013-04-04 / Esta dissertação apresenta um panorama do sistema de saúde brasileiro, com ênfase no caso do Estado de Pernambuco. A gestão de sistemas de saúde se manifesta sob a forma geral de longas filas de espera, que são analisados neste contexto, incluindo algumas abordagens que têm sido propostas e implementadas em Pernambuco, a fim de resolver o problema. Um modelo de crescimento econômico ótimo destacando o setor de saúde, e, em seguida, operando em conjunto, os setores de saúde e educação é proposto. Os resultados do princípio do máximo de Pontryagin aplicado a este modelo mostram os benefícios mútuos para ambos os setores e os seus efeitos no bem-estar da sociedade. Um estudo de caso de filas de espera no Hospital da Restauração, em Recife, Pernambuco, é apresentado. / An overview of the Brazilian health care system is presented, with an emphasis in the Pernambuco state case. One central issue concerning health systems management manifests itself under the general form of long waiting lines, which are then here analyzed in this context, including some approaches that have been proposed and implemented in Pernambuco in order to tackle the problem. An optimal economic growth model highlighting the health sector, and then, operating jointly, the health and education sectors, is proposed. The results of the Pontryagin Maximum Principle applied to this model show the mutual benefits for both sectors and their effects in the community welfare. A case study of queueing systems in Hospital da Restaura¸c˜ao (an emergency hospital) in Recife, Pernambuco, is presented.