Navegar por:

Técnicas de caminhos disjuntos para roteamento em systems-on-chip.

Use este link compartilhar ou citar este material: http://educapes.capes.gov.br/handle/1884/35039
Registro completo de metadados
MetadadosDescriçãoIdioma
Autor(es): dc.contributorTodt, Eduardo, 1963--
Autor(es): dc.contributorUniversidade Federal do Paraná. Setor de Ciências Exatas. Programa de Pós-Graduação em Informática-
Autor(es): dc.creatorSilva, Eduardo Sant'Ana da-
Data de aceite: dc.date.accessioned2025-09-01T12:42:41Z-
Data de disponibilização: dc.date.available2025-09-01T12:42:41Z-
Data de envio: dc.date.issued2024-11-10-
Data de envio: dc.date.issued2024-11-10-
Data de envio: dc.date.issued2013-
Fonte completa do material: dc.identifierhttps://hdl.handle.net/1884/35039-
Fonte: dc.identifier.urihttp://educapes.capes.gov.br/handle/1884/35039-
Descrição: dc.descriptionOrientador: Prof. Dr. Eduardo Todt-
Descrição: dc.descriptionTese (doutorado) - Universidade Federal do Paraná, Setor de Ciências Exatas, Programa de Pós-Graduação em Informática. Defesa: Curitiba, 03/10/2013-
Descrição: dc.descriptionInclui referências-
Descrição: dc.descriptionResumo: Systems-on-chip (SoCs) são sistemas compostos contidos em um único substrato de silício. Os SoCs foram introduzidos nas metodologias de projeto para atender 'a crescente demanda de aplicações complexas que requerem um grande poder computacional para sua execução. A utilização de SoCs contribui para uma diminuição de consumo de potência, pela ausência de um clock global, e para uma diminuição da área utilizada, visto que os componentes contidos em blocos são resultantes de projetos otimizados. As aplicações são compostas por subsistemas presentes em blocos distintos de lógica, cuja interação requer meios de comuni cação eficientes para seu adequado funcionamento. Devido 'a demanda por uma maneira eficiente de comunicação interna aos SoCs, surgiram as chamadas Networks-on-chip (NoCs). Assim como nas redes tradicionais, as NoCs possuem problemas a serem resolvidos, dentre eles, a criação de técnicas eficientes de roteamento. Apesar da maioria das NoCs implementadas comercialmente utilizarem uma técnica conhecida como wormhole, na qual um n'o (ou vértice) estabelece um caminho direto até o nó alvo, ainda faz-se necessário evitar a competição por rotas já utilizadas. Dessa forma generalizamos o problema em se obter caminhos disjuntos internos aos SoCs em um problema de grafos conhecido como árvores geradoras independentes, que pode ser descrito resumidamente como: Dado um grafo G, um conjunto de árvores geradoras enraizadas em um vértice r em G é dito vértice/aresta independente se, par a cada vértice v em G, v != r, os caminhos de r a v em qualquer par de árvores são vértice/aresta disjuntos. Se a conectividade de G 'e k, o problema resume-se 'a construção de k árvores geradoras independentes com cada vértice do grafo como raiz de tais árvores. Esse problema permanece em aberto para grafos em geral com conectividade k " 4. No entanto, foi demonstrado que, para um hipercubo de dimensão k, denotado por Qk, existem k árvores geradoras enraizadas em um vértice arbitrário de G. Neste trabalho é proposto um algoritmo para gerar k árvores geradoras independentes sobre hipercubos com o intuito de utilizá-lo na elaboração de técnicas de roteamento eficientes entre os núcleos distintos dos SoCs , assim como emprocessadores de múltiplos núcleos. Dentre as contribuições deste trabalho enfatizamos o consumo reduzido de recursos computacionais utilizados pelo algoritmo proposto, como: memória e processamento; assim como a modificação do algoritmo ECUBE para se construir rotas disjuntas sem que seja necessária a construção completa das árvores geradoras independentes. O algoritmo proposto se comporta de forma similar aos algoritmos comumente utilizados em roteamentos em NoCs, conforme mostrado pela utilização de um simulador de NoCs: Noxim. A construção de árvores geradoras disjuntas tende a seguir um dos dois objetivos: construção eficiente e altura ótima. Este trabalho tem o foco na construção eficiente, sendo que a altura ótima foi um resultado inerente ao método de construção proposto.-
Descrição: dc.descriptionAbstract: Systems-on-chip (SoCs) are compound systems contained on a single silicon substrate. The SoCs were introduced in design methodologies to meet the growing demand for complex applications that require massive computational power for their execution. The use of SoCs contributes to reduced power consumption, due to the absence of a global clock, and a decrease in the used area, since the components are contained in optimized design blocks. Such applications are composed of subsystems present in distinct logic blocks , whose interaction requires an efficient communication system for their proper functioning. Due to demand for an efficient internal communication to SoCs, the Networks-on-chip (NoCs) have emerged. Just as in traditional networks, the NoCs have problems to be solved, among them we have the creation of efficient routing techniques. Although most commercially NoCs implemented use a technique known as wormhole in which a node establishes a path straight to the target node, it is still necessary to avoid competition for routes already used. Thus, we generalize the problem of obtaining disjoint paths internal to SoCs in a problem known as independent spanning trees, that can be briefly described as: Given a graph G, a set of spanning trees rooted at a vertex r in G is said vertex/edge independent if for each vertex v in G, v != r, the paths from r to v in any pair of trees are vertex/edge disjoint. If the connectivity of G is k, the problem comes down to construct k independent spanning trees with each vertex of the graph as the root of such trees. This issue remains open for general graphs with connectivity k " 4. However, it has been shown that for a hypercube of dimension k, denoted by Qk, there are k spanning trees rooted at any arbitrary vertex of G. In this thesis we proposed an algorithm to generate k independent spanning trees on hypercubes in order to use them in developing efficient techniques for routing between distinct cores of SoCs, as well as multi-core processors. Among the contributions of this thesis, one can be emphasized, the reduced consumption of computational resources used by the proposed algorithm: memory and processing time; as well as the ECUBE modified algorithm to build disjoint routes without requiring the entire independent spanning trees construction. The proposed algorithm behaves similarly to the algorithms commonly used in routing in NoCs, as shown by the use of the NoCs simulator: Noxim. The construction of disjoint spanning trees tend to follow one of two objectives: efficient construction and optimum height. This work is focused on efficient construction, and the optimum height was an inherited result of the proposed construction method.-
Formato: dc.format140f. : il., grafs., tabs.-
Formato: dc.formatapplication/pdf-
Formato: dc.formatapplication/pdf-
Relação: dc.relationDisponível em formato digital-
Palavras-chave: dc.subjectCiência da computação-
Palavras-chave: dc.subjectÁrvores (Teoria dos grafos)-
Palavras-chave: dc.subjectRedes-em-chip-
Palavras-chave: dc.subjectSistemas embutidos de computador-
Título: dc.titleTécnicas de caminhos disjuntos para roteamento em systems-on-chip.-
Tipo de arquivo: dc.typelivro digital-
Aparece nas coleções:Repositório Institucional - Rede Paraná Acervo

Não existem arquivos associados a este item.
Mostrar registro simples do item Visualizar estatísticas

Avaliação