The cell differentiation process is associated with activation and repression of different genes, whereby the formation of heterochromatin is mediated by spreading of repressor proteins along large chromatin domains. Some of these proteins are methyltransferases, including GLP and G9a that are implicated in the addition of mono- and dimethyl groups to lysine 9 at Histone 3. Despite extensive research the exact mechanism of binding and spreading of G9a and GLP is unclear. To better understand the molecular mechanisms through which G9a and GLP bind to chromatin we tested the in vivo binding of a mutant G9a that is unable to bind to H3K9me2 histone marks via its Ankyrin domain. Murine erythroleukemia (MEL) cell line with expression of mutant G9a was generated using recombinant DNA technologies; G9a binding targets genome-wide were detected by the analysis of ChIP-sequencing data. We validated ChIP-sequencing data providing a reliable tool to visualize G9a targets in MEL cells. We also found that G9a Ankyrin mutant bound to all tested regions suggesting that the Ankyrin domain is not the only factor that contributes to the binding of G9a on chromatin in vivo.

Le glioblastome est la tumeur cérébrale de mauvais pronostic la plus fréquente et la plus agressive. Les traitements actuels combinent la chirurgie à la radio thérapie et la chimiothérapie. Cependant ces traitements sont peu efficaces. Le taux de récidive est élevé et la survie moyenne est de 15 mois.La récidive s'explique en partie par la présence de cellules initiatrices de glioblastomes (CIG). Ces cellules possèdent des propriétés de cellules souches adultes. Elles s'auto-renouvellent en maintenant un pool de cellules tumorales et se différencient en différents types cellulaires. Elles sont aussi résistantes aux thérapies par l'activation de mécanismes d'élimination des molécules destinées à les détruire. L'engagement des CIGs vers un état tumoral différencié diminue fortement leur potentiel tumorigénique les rendant plus vulnérables.Le facteur de transcription EGR1 est impliqué dans des processus biologiques comme la prolifération et la différenciation. Dans les CIG l'expression d'EGR1 est anormalement élevée. Ce niveau diminue lorsque les cellules se différencient. L'expression d'EGR1 est donc corrélée avec un état souche suggérant sa contribution dans la régulation de la prolifération des CIG ou dans le maintien de cet état.Mon objectif est de caractériser le rôle d'EGR1 dans la régulation de l'état proliférant des CIG.Nous avons démontré l'implication d'EGR1 dans une cascade de régulation impliquant le mir18a* et les gènes SHH et GLI1. Il contribue ainsi à l'autorenouvellement, à la prolifération et au maintien de l'état souche des CiGs. De plus en régulant directement le gène PDGFa, EGR1 entretient ce système régulatoire par une deuxième boucle moléculaire. / Glioblastoma is the most commun and agressive cerebral tumor. The current treatments combine surgery with chemotherapy and radiotherapy. However these treatments are poor effective. The relapse is frequent and the rate survival is less than 18 months.The relapse is in part due to the presence of glioblastoma initiating cells (GIC). The cells have stem cell properties. They can self-renew to maintain a pool of tumor cells and they can differentiate in different kind of tumor cells. They are also able to resist to the therapies by activating mechanisms of drug efflux. The commitment of GIC toward a differentiated tumor state decreases strongly their tumorigenic potential.EGR1 transcription factor is involved in many biological processes such as proliferation and differentiation. In the GIC EGR1 expression is abnormally elevated. This level decreases when cells are differentiated. EGR1 expression is strongly correlated with stem state suggesting its contribution in the proliferation regulation of GIC or in the maintenance of this state.My aim is to characterize the role of EGR1 in the regulation of proliferating state of the GIC.We have demonstrated the involvement of EGR1 in the pathway involving the mir18a* and the genes SHH and GLI1. It contributes so to the self-renewal, to the proliferation and to the maintenance of the stem state of GIC. In addition by directly regulating the gene PDGFa EGR1 maintains this system by a second molecular loop.

Endothelial cells, EC, are the cell type closest to the blood stream in vessel walls. These cells can affect the origin of atherosclerosis, plaques clogging the vessels. The behaviour of EC is affected by neighbouring smooth muscle cells and shear stress from the blood flow. The aim with this thesis was to fabricate a structure for an aorta-on-a-chip that can be used to study these two parameters and their influence on EC and vascular diseases. Previous research using a two-channel system resulted in leakage and low viability of the muscle cells. A three-channel system has therefore been made to include a middle channel with the muscle cells incorporated in a gel. Cell medium is flowed in the outer channels to provide the cells with nutrition. The flow in the channel with EC has been calculated to correspond to the shear stress in an aorta. Membranes of polyethylene terephthalate and polycarbonate were used to divide the channels and both were shown to be compatible with EC. Different bonding procedures were investigated to manufacture leakage-free chips. In the study, adhesive bonding clogged the channels and the parameters for thermal bonding of COC, cyclic olefin copolymer, were not fully optimised. This made chemical bonding with layers of PDMS, polydimethylsiloxane, the best alternative. APTES, (3-Aminopropyl)triethoxysilane, treatment in addition to plasma treatment on the surfaces improved the bonding strength. Polycarbonate membranes got better results in the bonding tests than polyethylene terephthalate. The resulting aorta-on-a-chip was therefore successfully fabricated in PDMS and polycarbonate membranes using plasma and APTES treatment for bonding.

A Chip Multiprocessor for a Large-scale Neural SimulatorEustace PainkrasA thesis submitted to The University of Manchesterfor the degree of Doctor of Philosophy, 17 December 2012The modelling and simulation of large-scale spiking neural networks in biologicalreal-time places very high demands on computational processing capabilities andcommunications infrastructure. These demands are difficult to satisfy even with powerfulgeneral-purpose high-performance computers. Taking advantage of the remarkableprogress in semiconductor technologies it is now possible to design and buildan application-driven platform to support large-scale spiking neural network simulations.This research investigates the design and implementation of a power-efficientchip multiprocessor (CMP) which constitutes the basic building block of a spikingneural network modelling and simulation platform. The neural modelling requirementsof many processing elements, high-fanout communications and local memoryare addressed in the design and implementation of the low-level modules in the designhierarchy as well as in the CMP. By focusing on a power-efficient design, the energyconsumption and related cost of SpiNNaker, the massively-parallel computation engine,are kept low compared with other state-of-the-art hardware neural simulators.The SpiNNaker CMP is composed of many simple power-efficient processors withsmall local memories, asynchronous networks-on-chip and numerous bespoke modulesspecifically designed to serve the demands of neural computation with a globallyasynchronous, locally synchronous (GALS) architecture.The SpiNNaker CMP, realised as part of this research, fulfills the demands of neuralsimulation in a power-efficient and scalable manner, with added fault-tolerancefeatures. The CMPs have, to date, been incorporated into three versions of SpiNNakersystem PCBs with up to 48 chips onboard. All chips on the PCBs are performing successfully, during both functional testing and their targeted role of neural simulation.

Orientador: Rodolfo Jardim de Azevedo / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Computação / Made available in DSpace on 2018-08-22T08:24:56Z (GMT). No. of bitstreams: 1 Abdnur_ThiagoBorges_M.pdf: 3580657 bytes, checksum: 2f83cda26eeb7b31a6ed647c31e27117 (MD5) Previous issue date: 2012 / Resumo: Com a mudança da maior parte das arquiteturas convencionais para multi-core a comunica _cão entre as diferentes unidades de processamento se torna um problema de destaque, principalmente no que tange _a transferência de dados entre cores. Apesar do enorme impacto no desempenho, é limitado o número de trabalhos científicos que tratam sobre novas soluções para o problema, o foco mais comum é realizar a comunicação através da memória ou endereços específicos mapeados em memória. Nesta dissertação foi definido um modelo de comunicação que acrescenta três novas instruções ao conjunto de instruções do SPARCv8, permitindo que diferentes cores transportem dados entre si diretamente, sem a latência derivada do uso de uma memória compartilhada e de Lucas, como _e o caso da atual implementação do LEON3. Avaliou-se esse modelo de comunicação através de diversos tipos de aplicações sintéticas como produtor-consumidor e pipeline. Para tornar o protótipo em FPGA mais realista, também foi construído um modelo de atraso para a memória principal do sistema, para que o desempenho relativo entre processador e memória _que mais próximo do real. Foi adicionado um suporte básico _as novas instruções no compilador para seu uso em código C através de asm-inline. De forma geral, obteve-se ganhos de 3% _a até 70 vezes, em termos de tempo de execução, em comparação ao uso de memória compartilhada e Lucas / Abstract: As processors design shift towards multicore architectures, new challenges arise to increase the core to core communication efficiency. Despite the potential huge performance impact, the number of papers focusing on this problem is limited. In this project, we define a communication model, adding three new instructions to the SPARCv8 instruction set, to allow different cores to communicate directly, without the shared memory and lock latencies. We implemented the model inside the LEON3 VHDL and evaluated it using synthetic benchmarks like producer-consumer and pipeline. To make the FPGA prototype timings more realistic, we also implemented a new memory timer so that it keeps the processor-memory speed ratio closer to real values. We also created the basic compiler support for these new instructions through intrinsic, converted to inline assembly in C code. Our overall results improve the performance from 3% to up to 70 times faster / Mestrado / Ciência da Computação / Mestre em Ciência da Computação

A computação reconfigurável está se fortalecendo cada vez mais devido ao grande avanço dos dispositivos reprogramáveis e ferramentas de projeto de hardware utilizadas atualmente. Isso possibilita que o desenvolvimento de hardware torne-se bem menos trabalhoso e complicado, facilitando assim a vida do desenvolvedor. A tecnologia utilizada atualmente em projetos de computação reconfigurável é denominada FPGA (Field Programmable Gate Array), que une algumas características tanto de software (flexibilidade), como de hardware (desempenho). Isso fornece um ambiente bastante propício para desenvolvimento de aplicações que precisam de um bom desempenho, sem que estas devam possuir uma configuração definitiva. O objetivo deste trabalho foi implementar um barramento eficiente para possibilitar a comunicação entre diferentes CORES de um robô reconfigurável, que podem estar dispersos em diferentes dispositivos FPGAs. Tal barramento seguirá o padrão AMBA (Advanced Microcontroller Bus Architecture), pertencente à ARM. Todo o desenvolvimento do core completo do AMBA foi realizado utilizando-se a linguagem VHDL (Very High Speed Integrated Circuit Hardware Description Language) e ferramentas EDAs (Electronic Design Automation) apropriadas. É importante notar que, embora o barramento tenha sido projetado para ser utilizado em um robô, o mesmo pode ser usado em qualquer sistema on-chip. / The reconfigurable computing is each time more fortified, what leads to a great advance of reprogrammable devices and hardware design tools. This has become hardware development less laborious and complicated, thus, facilitating the life of the designer. The technology currently used in projects of reconfigurable computing is called FPGA (Field Programmable Gate Array), which combines some characteristics of software (flexibility) and hardware (performance). This technology provides a propitious environment to the development of applications that need a good performance. Those that don’t need a definitive configuration. The purpose of this work was to implement an efficient bus to make possible the communication among different modules of a reconfigurable robot. This bus is based on a bus standard called AMBA (Advanced Microcontroller Bus Architecture), which belongs to ARM. All the development of full AMBA core was carried through using VHDL (Very High Speed Integrated Circuit the Hardware Description Language) language and appropriated EDA (Electronic Design Automation) tools. It is important to notice that, even so the bus have been projected to be used in a robot, it could be used in any system on-chip.

Chez les eucaryotes, l’ADN est empaqueté dans des complexes protéiques d’histones nommés nucléosomes qui assurent sa conformation. Cet arrangement est hétérogène à travers le génome et peut être dynamiquement modifié. La régulation de l’architecture chromatinienne joue un rôle essentiel dans la stabilité des génomes ainsi que la dynamique transcriptionnelle. Certaines régions qualifiées d’ ‘’heterochromatine constitutive’’ sont toutefois connues pour être maintenues à l’état condensé. Régionalisées aux extrémités et centres des chromosomes, l’hétérochromatine constitutive participe des fonctions télomériques et centromériques.Spodoptera frugiperda (S.fru, Lépidoptère, Noctuelle) est un ravageur de culture endémique du continent américain, récemment invasif dans le continent africain. Comme tous les Lépidoptères, S.fru est une espèce holocentrique dont le centromère est réparti le long des chromosomes et non restreint en un point unique. Cette disposition interroge sur l’établissement, la distribution ainsi que la fonction conservée de l’HC puisque cette dernière est principalement décrite pour être majoritairement localisée dans de larges régions péricentriques. Comprendre l’architecture chromatinienne chez S.fru peut avoir un intérêt en lutte biologique mais également permettre d’approfondir les connaissances en épigénétique chez un organisme non-modèle.Dans le cadre de la thèse, nous nous sommes demandés si la diméthylation de la lysine 9 de l’histone 3 (H3K9me2), marqueur de l’hétérochromatine constitutive, possédait un rôle conservé chez S.fru. Pour ce faire, nous avons comparé des données de ChIP-seq d’H3K9me2 sur cellules et larves entières après avoir annoté les gènes et l’ensemble des éléments répétés du génome, susceptibles d’être enrichis par cette marque. Parallèlement, des échantillons d’ARN-seq ont été étudiés afin de questionner le statut répressif de l’hétérochromatine constitutive. Nos résultats suggèrent un invariable maintien d’H3K9me2 dans les régions (sub)télomériques transcriptionnellement inactives ainsi qu’une forte association aux locus répétés d'ADN ribosomal (rDNA). Ces séquences ne constituent toutefois qu’une minorité des régions enrichies, le reste étant retrouvé dans des séquences répétées ainsi que dans le corps des gènes, indifféremment de leur état transcriptionnel. La persistante association d’H3K9me2 aux télomères et rDNA présagerait d’un maintien de la marque à proximité des centromères dont nous proposons un modèle d’établissement.La disposition de l’hétérochromatine constitutive questionne celle des régions euchromatiniennes, pauvres en nucléosomes, transcriptionnellement active et dynamiquement modifiées au cours du développement, du cycle cellulaire et des conditions environnementales. Afin de tester l’antagonisme de ces conformations, nous avons respectivement étudié la répartition des zones ouvertes et fermées du génome de la larve au stade L4 par approches de FAIRE-seq et de MAINE-seq. Ces structures ont été décrites dans la littérature pour être enrichies par de spécifiques modifications d’histones. Ainsi nous avons mis au point le protocole de native ChIP-seq d’H3K4me3 (marque active) et H3K9me2, H3K9me3, H3K27me3 (marques répressives). L’analyse en cours de l’ensemble de ces données de séquençages permettra d’avoir une vue intégrée de l’architecture chromatinienne au stade ravageur. / In eukaryotes, DNA is arranged in histones proteins complexes called nucleosomes that shape its conformation. This arrangement is heterogeneous across genomes and can be dynamically modified. Regulation of chromatin architecture plays an essential role in genome stability and transcription dynamics. Some regions named ‘’constitutive heterochromatin’’ are nonetheless known to remain highly condensed, regardless of conditions. Regionalized at extremities and chromosomes centers, constitutive heterochromatin contributes to telomeric and centromeric functions.Spodoptera frugiperda (S.fru, Lepidoptera, Noctuidae) is major crop pest in the Americas that recently invaded Africa. Like all Lepidopteran, S.fru is holocentric which means that its centromere is spread along chromosome and not restricted to a uniq point. This disposition question about establishment, distribution but also conserved function of constitutive heterochromatin since its usually and mainly localized in large pericentric regions.Deciphering chromatinian architecture in S.fru can be of interest in biological control but also allow to deepen epigenetic knowledge in a non-model organism.During my phD, we questionned the role of histone 3 lysine 9 demethylated (H3K9me2) in S.fru, a histone modification known in other yet described organisms to be a constitutive constitutive heterochromatinian hallmark.We compared H3K9me2 ChIP-seq data on cells and larvae after overall genomic functional annotation, potentially enriched for this mark. In parallel, RNA-seq samples were analyzed to question the putative repressive status of constitutive heterochromatin.Our results suggest an invariant retention of H3K9me2 in (sub)telomeric regions transcriptionally inactive but also a strong association of this mark in repeated ribosomal DNA locus (rDNA).These sequences constitutes nonetheless a minority of enriched regions since most of them regionalize in repeated sequences like transposons and tandem array but also gene bodies, independently of their transcriptional states.Persistent H3K9me2 association to telomeres and rDNA could predict of the conserved expression of this mark near centromeres. Based on literature and bioinformatics analysis, we proposed a model for S.fru holocentromeres.Constitutive heterochromatin questions euchromatin arrangement, described to be nucleosome poor, transcriptionally active and dynamically modified across development, cell cycle and environmental conditions. In order to test these structural antagonisms, we respectively studied open and closed genome conformations by FAIRE-seq and MAINE in larvae. These structures are reported to be associated to specific histones marks. We developed a native ChIP-seq protocol on H3K4me3 (active mark) and H3K9me2, H3K9me3, H3K27me3 (repressives marks). Overall analysis of these NGS data would help to picture an integrative view of chromatin architecture during larval pest stage.

Das als Trace bezeichnete nicht-invasive Aufzeichnen von Systemzuständen, während ein eingebettetes System unter realen Einsatzbedingungen in Echtzeit läuft und mit der Systemumgebung interagiert, ist ein wichtiger Teil von Softwaretests. Die Notwendigkeit für den On-Chip-Trace resultiert aus der rückläufigen Einsetzbarkeit etablierter Werkzeuge für den Off-Chip-Trace. Ein wesentlicher Bestandteil von On-Chip-Trace-Architekturen ist die Volumenreduktion der Tracedaten in deren Entstehungsgeschwindigkeit direkt auf dem Chip. Der Schwerpunkt liegt auf dem Trace des Instruktionsflusses von Prozessoren. Der aktuelle Stand der Forschung zeigt zwei Ausprägungen. Bei einfachen Lösungen ist der Kompressionsfaktor zu klein. Aufwendigere Lösungen liefern einen unvollständigen Instruktionstrace, wenn auch sequentielle Befehle bedingt ausgeführt werden. Bisher existieren keine Lösungen, die einen vollständigen Instruktionstrace mit hoher Kompression realisieren. Diese Lücke wird in der vorliegenden Arbeit geschlossen. Der systematische Entwurf der neuen On-Chip-Trace-Architektur beginnt mit der umfassenden Analyse typischer Benchmarkprogramme. Aus den Ergebnissen werden grundlegende Entwurfsentscheidungen abgeleitet. Diese Bitsequenzen von Ausführungsbits, die bei der bedingten Befehlsausführung entstehen, und die Zieladressen ausgeführter indirekter Sprünge werden in unabhängigen Kompressoren verarbeitet. Ein nachgeschalteter Kompressor für die Messages der anderen beiden Kompressoren ist optional und kann die Kompression weiter steigern. Diese Aufteilung stellt ein architektonisches Novum dar. Die Kompression von Bitsequenzen ist bisher ein weitestgehend unbehandeltes Feld. Implementiert worden ist hierfür ein gleitendes Wörterbuch mit der Granularität von Einzelbits. Die Vergleiche mit den untersuchten existierenden Architekturen zeigen die Überlegenheit der neuen Architektur bei der Kompression. Ein vollständiger Instruktionstrace ist für Prozessoren mit und ohne bedingt ausführbaren sequentiellen Befehlen realisiert worden.

Sub-ambient direct-on-chip liquid cooling is an emerging technology in the data center industry. The risk of an electrically conductive liquid leaking out to the electrical components and damaging the servers has been the major factor in holding back the use of liquid cooling historically. This technology effectively removes that risk. A direct-on-chip liquid cooling system, where average system pressure and average CPU temperatures can be fixed for a range of server computing loads and coolant supply temperatures for data center servers has been designed and constructed. This has been used to determine what impact pressure has on a small-scale liquid cooled server system in terms of CPU power consumption and CPU temperatures. The cooling system was only able to work with one server connected. Experiments with different values for the CPU temperature setpoint, coolant supply temperature setpoint, server computational load, and server pressure were executed to verify that the system works as intended. Applying a range of CPU computing loads works well, maintaining fixed average CPU temperatures works, with differences between the CPUs at higher temperatures and failure to reach average CPU temperatures when the difference between these and the coolant supply temperature is small. Maintaining fixed average pressure before the server works well, while pressure after the server is heavily affected by coolant flow. However, this effect is not seen as important for the experimental goals of the thesis. Maintaining a fixed coolant supply temperature works well with some slow fluctuations around the setpoint. No noticeable effects from pressure on CPU power consumption and CPU temperatures were seen. However, lower flow resistance was seen by the circulating pump when negative system pressure was lower which implies that less pump energy is needed to pump at lower negative pressure. The pressure was not in the region where the coolant could phase change during the experiments.

As semiconductor technologies develop, a System-on-Chip (SoC) that integrates all semiconductor intellectual property (IP) cores is suggested and widely used for various applications. A traditional bus interconnection does not support transmitting data between IP cores for high performance. Because of this reason, a Network-on-Chip (NoC) has been suggested to provide an efficient and scalable solution to interconnect among all IP cores. High throughput and low latency have recently become the main important factors of NoC for achieving hard guaranteed real-time systems. In order to guarantee these factors and provide real-time service (i.e., Guaranteed Service, GS), the circuit switching (CS) approach has been widely utilized. The CS approach allocates mutually exclusive paths to transmitting data between different sources and destinations using dedicated NoC resources. However, the exclusive occupancy of the allocated path reduces the efficiency of the overall use of NoC resources. In order to solve this problem, Space-Division-Multiplexing (SDM) and Time-Division-Multiplexing (TDM) techniques have been suggested. SDM implements a circuit switching technique by assigning physically different NoC-links between different connections. Path connections of the SDM technique based on spatial resources assignment do not provide high scalability. In contrast to this, using virtual time slots for a path connection, the TDM technique can share physical links between exclusively established connections, thereby improving NoC path diversity. For all of these mentioned techniques, the factor that significantly impacts the system efficiency or performance scaling is how the path is allocated. In recent years, a dynamic connection allocation approach that can cope with highly dynamic workloads has been gaining attention due to the sudden and diverse demands of applications in real-time systems. There are two groups in the dynamic connection allocation approach. One is a distributed allocation technique, and the other is a centralized allocation technique. While distributed allocation exploits additional logic integrated into the NoC-routers for path search and allocation, the centralized approach makes use of a central unit to manage the path allocation problem. There are several algorithms for the centralized allocation technique. Trellis search-based allocation approach shows the best performance among them. Many algorithms related to centralized connection allocators have been studied extensively during the past decade. However, relatively little attention was paid to methodology in analyzing and evaluating the centralized connection allocation algorithms. In order to further develop the algorithms, it is necessary to understand and evaluate the centralized connection allocator by establishing a new analysis methodology. Thus, this thesis presents a performance analysis methodology for the trellis search-based allocation approach. Firstly, this thesis proposes a system model for analysis. Secondly, performance metrics are defined. Finally, the analysis results of each performance metric related to the trellis search-based allocation approach are presented. Through this analysis, the performance of the trellis search-based allocation approach can be accurately analyzed. Although a simulation is not performed, the upper limit of performance of the trellis search-based allocation approach can also be predicted through the analysis metrics. Additionally, we introduce the general formulation of the trellis search-based path allocation algorithm. The weight values among available paths through the branch metric and path metric are proposed to enable higher performance path connection. Furthermore, according to network size, topology, TDM, interface load delivery, and router internal storage, the performance of trellis search-based path allocation algorithms is also described. In the end, the Application Specific Instruction Processor (ASIP) hardware platform customized for the trellis search-based path allocation algorithm is presented. The shortest available and lowest-cost (SALC) path search algorithm is proposed to improve the success rate of path connection in the ASIP hardware platform. We evaluate the algorithm performance and implementation synthesis results. In order to realize the dynamic connection approach, a short execution cycle of ASIP time is essential. We develop several algorithms to achieve this short execution cycle. The first one is a rectangular region of search algorithm that allows adapting the size and form of path search region according to the particular source-destination positions and considers actual operational constraints. The average execution cycles for searching an optimum path are decreased because the unnecessary region for path-search is excluded. The second one is a path-spreading search algorithm that separates between involved routers and uninvolved routers in path search. The involved routers are selected and spread out from source to destination at each intermediate trellis-search process. The path-search overhead is considerably reduced due to the router involvements. The third one is a three-directional path-spreading search algorithm that eliminates one direction movement among four spreading movements. Because of this reason, the trellis search-based path connection algorithm, which omits the back-tracing process, can be implemented in the ASIP platform. Thus, the whole algorithm execution time can be halved. The last one is a moving regional path search algorithm that significantly reduces computation complexity by selecting a constant dimensional path-search region that affects performance and moving the region from source to destination. The moving regional path search algorithm achieves a considerable decrement of computational complexity.:1 Introduction 1 1.1 NoC-interconnect . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 1 1.2 Thesis outline . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 4 2 Connection allocation in a Network-on-Chip 7 2.1 Circuit Switching NoCs . . . . . . . . . . . . . . . . . . . . . . . . . . 7 2.1.1 Guaranteed Service in NoCs . . . . . . . . . . . . . . . . . . . 7 2.1.2 Spatial-Division-Multiplexing technique . . . . . . . . . . . . 8 2.1.3 Time-Division-Multiplexing technique . . . . . . . . . . . . . 10 2.2 System architectures employing circuit switching NoCs . . . . . . . . 11 2.2.1 Static and dynamic connection allocation . . . . . . . . . . . 12 2.2.2 Distributed connection allocation technique . . . . . . . . . . 14 2.2.3 Centralized connection allocation technique . . . . . . . . . . 16 2.2.4 Algorithms for centralized connection allocation . . . . . . . . 17 2.2.4.1 Software based run-time path allocation approach . 18 2.2.4.2 Trellis search-based allocation approach . . . . . . . 19 3 Performance analysis methodology for a centralized connection allocator 23 3.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 23 3.2 Performance metrics and analysis methodology . . . . . . . . . . . . 25 3.3 System simulation . . . . . . . . . . . . . . . . . . . . . . . . . . . . 33 4 Trellis search-based path allocation algorithm 45 4.1 General formulation . . . . . . . . . . . . . . . . . . . . . . . . . . . 45 4.1.1 Trellis graph structure . . . . . . . . . . . . . . . . . . . . . . 45 4.1.2 Survivor path selection criterion . . . . . . . . . . . . . . . . . 52 ix 4.1.2.1 Branch metric and path metric . . . . . . . . . . . . 52 4.1.2.2 The shortest-available and lowest-cost path selection criterion . . . . . . . . . . . . . . . . . . . . . . . . . 53 4.2 Algorithm Properties . . . . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.1 Network topology . . . . . . . . . . . . . . . . . . . . . . . . 55 4.2.2 Network size . . . . . . . . . . . . . . . . . . . . . . . . . . . 58 4.2.3 Time-Division-Multiplexing . . . . . . . . . . . . . . . . . . . 61 4.2.4 NoC interface load diversity . . . . . . . . . . . . . . . . . . . 63 4.2.5 The internal storage of the router . . . . . . . . . . . . . . . . 66 5 ASIP approach for Trellis search-based connection allocation 73 5.1 System model . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 73 5.1.1 Trellis search-based ASIP platform architecture . . . . . . . . 74 5.2 Algorithm for improving success rates of path connection . . . . . . . 81 5.2.1 SALC algorithm for Trellis search-based ASIP platform . . . . 81 5.2.2 Performance evaluation of the SALC algorithm . . . . . . . . 88 5.2.2.1 Simulation results . . . . . . . . . . . . . . . . . . . 88 5.2.2.2 Synthesis results . . . . . . . . . . . . . . . . . . . . 91 5.3 Algorithm for reducing path-search time . . . . . . . . . . . . . . . . 93 5.3.1 Rectangular regional path search algorithm . . . . . . . . . . 93 5.3.2 Path-spreading search algorithm . . . . . . . . . . . . . . . . 99 5.3.3 Three directional path-spreading search algorithm . . . . . . 108 5.3.4 Moving regional path search algorithm . . . . . . . . . . . . . 114 5.3.5 Performance evaluation . . . . . . . . . . . . . . . . . . . . . 123 5.3.5.1 Simulation results . . . . . . . . . . . . . . . . . . . 123 5.3.5.2 Synthesis results . . . . . . . . . . . . . . . . . . . . 126 6 Conclusion and Future work 131 6.1 Conclusion . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 131 6.2 Future work . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . . 132 Bibliography 135