Computer architects continue to push the limits of modern microprocessors. By using techniques such as out-of-order execution, branch prediction, and dynamic scheduling, designers have found ways to speed execution. However, growing architectural complexity has led to unsustained development and testing times. Shrinking feature sizes are causing increased wire resistances and signal propagation, thereby limiting a design's scalability. Indeed, the method of exploiting instruction-level parallelism (ILP) within applications is reaching a point of diminishing returns. One approach to the aforementioned challenges is the Single-Chip Message-Passing (SCMP) Parallel Computer, developed at Virginia Tech. SCMP is a unique, tiled architecture aimed at thread-level parallelism (TLP). Identical cores are replicated across the chip, and global wire traces have been eliminated. The nodes are connected via a 2-D grid network and each contains a local memory bank. This thesis presents the design and analysis of three high-performance applications for SCMP. The results show that the architecture proves itself as a formidable opponent to several current systems. / Master of Science

Several trends can be observed in modern microprocessor design. Architectures have become increasingly complex while design time continues to dwindle. As feature sizes shrink, wire resistance and delay increase, limiting architects from scaling designs centered around a single thread of execution. Where previous decades have focused on exploiting instruction-level parallelism, emerging applications such as streaming media and on-line transaction processing have shown greater thread-level parallelism. Finally, the increasing gap between processor and off-chip memory speeds has constrained performance of memory-intensive applications. The Single-Chip Message Passing (SCMP) parallel computer sits at the confluence of these trends. SCMP is a tiled architecture consisting of numerous thread-parallel processor and memory nodes connected through a structured interconnection network. Using an interconnection network removes global, ad-hoc wiring that limits scalability and introduces design complexity. However, routing data through general purpose interconnection networks can come at the cost of dedicated bandwidth, longer latency, increased area, and higher power consumption. Understanding the impact architectural decisions have on cost and performance will aid in the eventual adoption of general purpose interconnects. This thesis covers the design and analysis of the on-chip network and its integration with the SCMP system. The result of these efforts is a framework for analyzing on-chip interconnection networks that considers network performance, circuit area, and power consumption. / Master of Science

京都大学 / 新制・課程博士 / 博士(工学) / 甲第24812号 / 工博第5155号 / 新制||工||1985(附属図書館) / 京都大学大学院工学研究科マイクロエンジニアリング専攻 / (主査)教授 横川 隆司, 教授 安達 泰治, 教授 永樂 元次 / 学位規則第4条第1項該当 / Doctor of Philosophy (Engineering) / Kyoto University / DGAM

Networks-on-Chip (NoC) have been proposed to meet many challenges of modern Systems-on-Chip (SoC) design and manufacturing. At the architectural level, a clean separation of computation and communication helps integration and verification. Networking abstraction of the communication infrastructure also promotes reuse and fast development. But the benefit is most visible when it comes to circuit and physical design. Networks can be made sparse and regular and thus facilitate placement and route. It is also much easier to reach timing and power closure as NoC shield communication details away from complicating analysis. Last but not the least, networks are flexible at the design stage and adaptable post-silicon. Many techniques of tackling process variation and interconnect failure can be built upon NoC. However, when interconnects are time multiplexed in a NoC, the network’s performance will deteriorate if it is not scheduled properly. For a wide range of applications, the traffic on the network can be determined before run-time and offline scheduling offers guaranteed performance and enables simple design. We propose a synthesis flow that takes the data flow graph of the application and a network topology as inputs; and outputs an offline schedule that can be deployed directly to the NoC. We analyze the complexity of combinatorial problems that arise from this context and provide efficient heuristics when polynomial time algorithms are not available assuming P [not equal to] NP. Results on LDPC decoding and FFT designs are compared with previous ones. We further apply our findings to parallel shared memories (PSM) and formalize the PSM architecture and its scheduling problem. An efficient heuristic is derived from our algorithm for unbuffered networks. Another application exemplifies how the NoC can be reprogrammed after silicon is back from fab in order to avoid failed interconnects due to process variation. A simple statistical model is studied and the simulation result is rather interesting. We find out that high performance and yield are not always at conflict if we are able to change the network schedule based on silicon diagnosis. / text

Submitted by PPG Ci?ncia da Computa??o (ppgcc@pucrs.br) on 2018-07-06T13:04:33Z No. of bitstreams: 1 WILLIAM SCHNEIDER_DIS.pdf: 3430246 bytes, checksum: 5fc61ba11d1155b509058a5d6a0c34b9 (MD5) / Approved for entry into archive by Sheila Dias (sheila.dias@pucrs.br) on 2018-07-10T14:27:37Z (GMT) No. of bitstreams: 1 WILLIAM SCHNEIDER_DIS.pdf: 3430246 bytes, checksum: 5fc61ba11d1155b509058a5d6a0c34b9 (MD5) / Made available in DSpace on 2018-07-10T14:37:58Z (GMT). No. of bitstreams: 1 WILLIAM SCHNEIDER_DIS.pdf: 3430246 bytes, checksum: 5fc61ba11d1155b509058a5d6a0c34b9 (MD5) Previous issue date: 2014-03-13 / The increase in the number of cores available in Systems on a Chip has enabled the design of circuits with increasingly aggressive specifications. Efficient interconnection architectures such as intrachip networks are critical to the viability of these projects. However, measuring and comparing performanceof these networks for a given system is still a challenging task, which results from: (i) the complexity imposed by the abundance of available options in the design space of these networks; (ii) the current non-adoption of a unique evaluation platform to compare different networks proposals; (iii) the fact that the network traffic has a greater influence on the performance of such networks than any other design characteristic. This work has as main strategic goal the evaluation and comparison of different intrachip network architectures through the use of a unified evaluation platform. It adopts Nocbench, a recent platform, already validated in some contexts and proposed as a standard for the evaluation of intrachip networks. The employed evaluation method is based on the simulation of networks and uses as input traffic and computation models described in the form of traces, both extracted from real application. The main contributions of this work reside in: (i) the proposal of several enhancements to the chosen platform; (ii) the development of modules added to integrate the networks Hermes HS,Hermes OO, Hermes TB, Hermes VC, and YeaH from the author?s research group to the platform; (iii) the enhancement of the platform performance evaluation process, through the inclusion of metrics usually employed to compare intrachip networks, including: latency, throughput and jitter. A set of experiments validates the contributions and demonstrate the use the Nocbench platform as a useful tool in the comparison of intrachip networks of diverse origins. / O aumento no n?mero de n?cleos presentes em Sistemas Integrados em Chip tem proporcionado o projeto de circuitos com especifica??es cada vez mais agressivas. Arquiteturas de interconex?o eficientes tais como as redes intrachip s?o fundamentais para a viabilidade destes projetos. Entretanto, medir e comparar o desempenho destas redesainda ? uma tarefa desafiadora, resultado: (i) da complexidade imposta pela abund?ncia de op??es dispon?veis no espa?o de projeto destas redes; (ii) da atual n?o ado??o de uma mesma plataforma de avalia??o para a compara??o de diferentes propostas de redes; (iii) e do fato de o tr?fego de rede exercer uma influ?ncia muito maior do que qualquer caracter?stica de projeto no desempenho destas. Este trabalho tem como principal objetivo estrat?gico a avalia??o e compara??o de diferentes arquiteturas de redes intrachip atrav?s de uma plataforma de avalia??o unificada. Adota-se Nocbench, uma plataforma recente, j? validada em alguns contextos e proposta como um padr?o para a avalia??o de redes intrachip. O m?todo de avalia??o empregado baseia-se na simula??o de redes e utiliza como entrada modelos de tr?fego e de computa??o descritos sob a forma de traces, ambos extra?dos de aplica??es reais. As principais contribui??es do trabalho residem: (i) na proposta de diversas melhorias para a plataforma escolhida; (ii) no desenvolvimento de m?dulos para a integra??o das redes Hermes HS, Hermes OO, Hermes TB, Hermes VC e YeaHdo grupo de pesquisa do Autor ? plataforma em quest?o; (iii) no aprimoramento do processo de avalia??o de desempenho da plataforma, atrav?s da inclus?o de m?tricas comumente utilizadas para comparar redes intrachip, incluindo: lat?ncia, vaz?oe jitter. Um conjunto de experimentos valida as contribui??es e demonstra o uso da plataforma Nocbench como uma ferramenta ?til na compara??o de redes intrachip de origens diversas.

Network on Chip (NoC) has emerged as a competitive and efficient communication infrastructure for the core based design of System on Chip. Resource (core), router and interface between router and core are the three main parts of a NoC. Each core communicates with the network through the interface, also called Resource Network Interface (RNI). One approach to speed up the design at NoC based systems is to develop standardized RNI. Design of RNI depends to some extent on the type of routing technique used in NoC. Control of route decision base the categorization of source and distributed routing algorithms. In source routing a complete path to the destination is provided in the packet header at the source, whereas in distributed routing, the path is dynamically computed in routers as the packet moves through the network. Buffering, flitization, deflitization and transfer of data from core to router and vice versa, are common responsibilities of RNI in both types of routing. In source routing, RNI has an extra functionality of storing complete paths to all destinations in tables, extracting path to reach a desired destination and adding it in the header flit. In this thesis, we have made an effort towards designing and prototyping a standardized and efficient RNI for both source and distributed routing. VHDL is used as a design language and prototyping of both types RNI has been carried out on Altera DE2 FPGA board. Testing of RNI was conducted by using Nios II soft core. Simulation results show that the best case flit latency, for both types RNI is 4 clock cycles. RNI design is also resource efficient because it consumes only 2% of the available resources on the target platform.

<p>Network on Chip (NoC) has emerged as a competitive and efficient communication infrastructure for the core based design of System on Chip. Resource (core), router and interface between router and core are the three main parts of a NoC. Each core communicates with the network through the interface, also called Resource Network Interface (RNI). One approach to speed up the design at NoC based systems is to develop standardized RNI. Design of RNI depends to some extent on the type of routing technique used in NoC. Control of route decision base the categorization of source and distributed routing algorithms. In source routing a complete path to the destination is provided in the packet header at the source, whereas in distributed routing, the path is dynamically computed in routers as the packet moves through the network. Buffering, flitization, deflitization and transfer of data from core to router and vice versa, are common responsibilities of RNI in both types of routing. In source routing, RNI has an extra functionality of storing complete paths to all destinations in tables, extracting path to reach a desired destination and adding it in the header flit. In this thesis, we have made an effort towards designing and prototyping a standardized and efficient RNI for both source and distributed routing. VHDL is used as a design language and prototyping of both types RNI has been carried out on Altera DE2 FPGA board. Testing of RNI was conducted by using Nios II soft core. Simulation results show that the best case flit latency, for both types RNI is 4 clock cycles. RNI design is also resource efficient because it consumes only 2% of the available resources on the target platform.</p>

<p>During the past years has the Nostrum Network on Chip <i>(NoC)</i> been developed to become a competitive platform for network based on-chip communication. The Nostrum NoC provides a versatile communication platform to connect a large number of intellectual properties <i>(IP) </i>on a single chip. The communication is based on a packet switched network which aims for a small physical footprint while still providing a low communication overhead. To reduce the communication network size, a queue-less network has been the research focus. This network uses de ective hot-potato routing which is implemented to perform routing decisions in a single clock cycle.</p><p>Using a platform like this results in increased design reusability, validated signal integrity, and well developed test strategies, in contrast to a fully customised designs which can have a more optimal communication structure but has a significantly longer development cycle to verify the new design accordingly.</p><p>Several factors are considered when designing a communication platform. The goal is to create a platform which provides low communication latency, high throughput, low power consumption, small footprint, and low design, verification, and test overhead. Proximity Congestion Awareness is one technique that serves to reduce</p><p>the network load. This leads to that the latency is reduced which also increases the network throughput. Another technique is to implement low latency paths called<i> Data Motorways</i> achieved through a clocking method called Globally Pseudochronous Locally Synchronous clocking. Furthermore, virtual circuits can be used to provide guarantees on latency and throughput. Such guarantees are dificult in</p><p>hot-potato networks since network access has to be ensured. A technique that implements virtual circuits use looped containers that are circulating on a predefined circuit. Several overlapping virtual circuits are possible by allocating the virtual circuits in different Temporally Disjoint Networks.</p><p>This thesis summarise the impact the presented techniques and methods have on the characteristics on the Nostrum model. It is possible to reduce the network load by a factor of 20 which reduces the communication latency. This is done by distributing load information between the Switches in the network. Data Motorways</p><p>can reduce the communication latency with up to 50% in heavily loaded networks. Such latency reduction results in freed buffer space in the Switch registers which allows the traffic rate to be increased with about 30%.</p>

Made available in DSpace on 2014-12-17T15:48:02Z (GMT). No. of bitstreams: 1 TadeuFO_DISSERT.pdf: 1305505 bytes, checksum: 419b87148f7490aba343231bb89f4d72 (MD5) Previous issue date: 2010-08-09 / The increasingly request for processing power during last years has pushed integrated circuit industry to look for ways of providing even more processing power with less heat dissipation, power consumption, and chip area. This goal has been achieved increasing the circuit clock, but since there are physical limits of this approach a new solution emerged as the multiprocessor system on chip (MPSoC). This approach demands new tools and basic software infrastructure to take advantage of the inherent parallelism of these architectures. The oil exploration industry has one of its firsts activities the project decision on exploring oil fields, those decisions are aided by reservoir simulations demanding high processing power, the MPSoC may offer greater performance if its parallelism can be well used. This work presents a proposal of a micro-kernel operating system and auxiliary libraries aimed to the STORM MPSoC platform analyzing its influence on the problem of reservoir simulation / O aumento da demanda por poder de processamento nos ?ltimos anos for?ou a ind?stria de circuitos integrados a buscar formas de prover maior poder de processamento com menor dissipa??o de calor, menor consumo de pot?ncia e ?rea em chip. Isso vinha sendo feito com o aumento do clock dos circuitos. Por?m, com a proximidade dos limites f?sicos dessa abordagem, surgem como solu??o alternativa as arquiteturas com m?ltiplos processadores em um ?nico chip: os MPSoC (Multi-Processor System on a Chip). Essa abordagem exige que novas ferramentas e novos softwares sejam desenvolvidos buscando aproveitar ao m?ximo o aspecto paralelo destas arquiteturas. A ind?stria de explora??o de petr?leo tem como uma de suas atividades iniciais a decis?o de projetos de explora??o de campos de petr?leo. Essas decis?es s?o tomadas baseando-se em simula??es computacionalmente intensivas, situa??o em que os MPSoCs podem oferecer aumento de performance atrav?s de paralelismo. Este trabalho apresenta a proposta de implementa??o de um micro-kernel de sistema operacional e bibliotecas auxiliares para a plataforma MPSoC STORM analisando a influ?ncia na simula??o de reservat?rios

La red en el chip (NoC) se han convertido en el elemento clave para la comunicación eficiente entre los núcleos dentro de los chip multiprocesador (CMP). Tanto el uso de aplicaciones paralelas en los CMPs como el incremento de la cantidad de memoria necesitada por las aplicaciones, ha impulsado que la red de comunicación gane una mayor importancia. La NoC es la encargada de transportar toda la información requerida por los núcleos. Además, el incremento en el número de núcleos en los CMPs impulsa las NoC a ser diseñadas de forma escalable, pero al mismo tiempo sin que esto afecte a las prestaciones de la red (latencia y productividad). Por tanto, el diseño de la red en el chip se convierte en crítico. Esta tesis presenta diferentes propuestas que atacan el problema de la mejora de las prestaciones de la red en tres escenarios distintos. Los tres escenarios en los que se centran nuestras propuestas son: 1) NoCs que implementan un algoritmo de encaminamiento adaptativo, 2) escenarios con necesidad de tiempos de acceso a memoria bajos y 3) sistemas con previsión de seguridad a nivel de aplicación. Las primeras propuestas se centran en el aumento de la productividad en la red utilizando algoritmos de encaminamiento adaptativos mediante un mejor uso de los recursos de la red, primera propuesta SUR, y evitando que se ramifique la congestión cuando existe tráfico intenso hacia un único destinatario, segunda propuesta EPC. La tercera y principal contribución de esta tesis se centra la problemática de reducir el tiempo de acceso a memoria. PROSA, mediante un diseño híbrido de conmutación de paquete y conmuntación de circuito, permite reducir la latencia de la red aprovechando la latencia de acceso a memoria para establecer circuitos. De esta forma cuando la información llega a la NoC, esta es servida sin retardos. Por último, la propuesta Token Based TDM se centra en el escenario con redes de interconexión seguras. En este tipo de NoC las aplicaciones esta divididas en dominios y la red debe garantizar que no existen interferencias entre los diferentes dominios para evitar de este modo la intrusión de posibles aplicaciones maliciosas. Token-based TDM permite el aislamiento de los dominios sin tener impacto en el diseño de los conmutados de la NoC. Los resultados obtenidos demuestran como estas propuestas han servido para mejorar las prestaciones de la red en los diferentes escenarios. La implementación y la simulación de las propuestas muestra como mediante el balanceado de la utilización de los recursos de la red, los CMPs con algoritmos de encaminamiento adaptativos son capaces de aumentar el tráfico soportado por la red. Además, el uso de un filtro para limitar el encaminamiento adaptativo en situaciones de congestión previene a los mensajes de la ramificación de la congestión a lo largo de la red. Por otra parte, los resultados demuestran que el uso combinado de la conmutación de paquete y conmutación de circuito reduce muy significativa de la latencia de red acceso a memoria, contribuyendo a una reducción significativa del tiempo de ejecución de la aplicación. Por último, Token-Based TDM incrementa las prestaciones de las redes TDM debido a su alta flexibilidad dado que no requiere ninguna modificación en la red para soportar una cantidad diferente de dominios mientras mejora la latencia de la red y mantiene un aislamiento perfecto entre los tráficos de las aplicaciones. / The Network on Chip (NoC) has become the key element for an efficient communication between cores within the multiprocessor chip (CMP). The use of parallel applications in CMPs and the increase in the amount of memory needed by applications have pushed the network communication to gain importance. The NoC is in charge of transporting all the data needed by the processors cores. Moreover, the increase in the number of cores pushes the NoCs to be designed in a scalable way, but at the same time, without affecting network performance (latency and productivity). Thus, network-on-chip design becomes critical. This thesis presents different proposals that attack the problem of improving the network performance in three different scenarios. The three scenarios in which our proposals are focused are: 1) NoCs with an adaptive routing algorithm, 2) scenarios with low memory access time needs, and 3) high-assurance NoCs. The first proposals focus on increasing network throughput with adaptive routing algorithms via the improvement of the network resources utilization, the first proposal SUR, and avoiding congestion spreading when an intense traffic to a single destination occurs, second proposal ECP. The third one and main contribution of this thesis focuses on the problem of reducing memory access latency. PROSA, through a hybrid circuit-packet switching architecture design, reduces the network latency by getting benefit of the memory access latency slack and to establishing circuits during that delay. In this way the information when arrives to the NoC is served without any delay. Finally, the proposal Token-Based TDM focuses on the scenario with high assurance networks on chips. In this type of NoCs the applications are divided into domains and the network must guarantee that there are no interferences between the different domains avoiding this way intrusion of possible malicious applications. Token-based TDM allows domain isolation with no design impact on NoC routers. The results show how these proposals improve the performance of the network in each different scenario. The implementation and simulations of the proposals show the efficient use of network resources in CMPs with adaptive routing algorithms which leads to an increasement of the injected traffic supported by the network. In addition, using a filter to limit the adaptivity of the routing algorithm under congested situations prevents messages from spreading the congestion along the network. On the other hand, the results show that the combined use of circuit and packet switching reduces the memory access latency significantly, contributing to a significant reduction in application execution time. Finally, Token-Based TDM increases network performance of TDM networks due to its high flexibility and efficient arbitration. Moreover, Token-Based TDM does not require any modification in the network to support a different number of domains while improving latency and keeping a strong traffic isolation from different domains. / La xarxa en el xip (NoC) s'ha convertit en un element clau per a una comunicació eficient entre els diferents nuclis dins d'un xip multiprocessador (CMP). Tant la utilització d'aplicacions paral·leles en el CMP com l'increment de la quantitat de memòria necessitada per les aplicacions, hi ha produït que la xarxa de comunicació tinga una major importància. La NoC és l'encarregada de transportar tota la informació necessària pels nuclis. A més, l'increment del nombre de nuclis dins del CMP fa que la NoC haja de ser dissenyada d'una forma escalable, sense que afecte les prestacions de la xarxa (latència i productivitat). Per tant, el disseny de la xarxa en el xip es converteix crític. Aquesta tesi presenta diferents propostes que ataquen el problema de la millora de les prestacions de la xarxa en tres escenaris distints. Els tres escenaris en els quals se centren les nostres propostes són: 1) NoCs que implementen un algoritme d'encaminament adaptatiu, 2) escenaris amb necessitat de temps baix d'accés a memòria i 3) sistemes amb previsió de seguretat en l'àmbit d'aplicació. Les primeres propostes se centren en l'augment de la productivitat en la xarxa utilitzant algoritmes d'encaminament adaptatiu mitjançant una millor utilització dels recursos de la xarxa, primera proposta SUR, i evitant que es ramifique la congestió quan existeix un trànsit intens cap a un únic destinatari, segona proposta EPC. La tercera i principal contribució d'aquesta tesi es basa en la problemàtica de reduir el temps d'accés a memòria. PROSA, mitjançant un disseny híbrid de commutació de paquet i commutació de circuit, redueix la latència de la xarxa aprofitant la latència d'accés a memòria i establint els circuits durant aquesta latència. D'aquesta forma la informació quan arriba a la NoC pot ser enviada sense cap retràs. Per últim, la proposta Token-based TDM se centra en l'escenari amb xarxes d'interconnexió d'alta seguretat. En aquest tipus de NoC les aplicacions estan dividides en dominis i la xarxa deu garantir que no existeixen interferències entre els diferents dominis per a evitar d'aquesta forma la intrusió de possibles aplicacions malicioses. Token-based TDM permet l'aïllament dels dominis sense tindre impacte en el disseny dels encaminadors de la NoC. Els resultats demostren com aquestes propostes han servit per a millorar les prestacions de la xarxa en els diferents escenaris. La seua implementació i simulació demostra com mitjançant el balancejat de la utilització dels recursos de la xarxa, els CMP amb algoritmes d'encaminament adaptatiu són capaços d'augmentar el trànsit suportat per la xarxa. A més, l'ús d'un filtre per a limitar l'adaptabilitat de l'encaminament adaptatiu en situacions de congestió permet prevenir els missatges de la congestió al llarg de la xarxa. Per altra banda, els resultats demostren que l'ús combinat de la commutació de paquet i commutació de circuit redueix molt significativament de la latència d'accés a memòria, contribuint en una reducció significativa del temps d'execució de l'aplicació. Per últim, Token-based TDM incrementa les prestacions de les xarxes TDM debut a la seua alta flexibilitat donat que no requereix cap modificació en la xarxa per a suportar una quantitat diferent de dominis mentre millora la latència de la xarxa i mantén un aïllament perfecte entre els trànsits de les aplicacions. / Gorgues Alonso, M. (2018). Improving Network-on-Chip Performance in Multi-Core Systems [Tesis doctoral no publicada]. Universitat Politècnica de València. https://doi.org/10.4995/Thesis/10251/107336 / TESIS