Made available in DSpace on 2015-04-14T14:50:01Z (GMT). No. of bitstreams: 1 448654.pdf: 3794673 bytes, checksum: 27e1f6f68c147a8709c4d67ce49eed05 (MD5) Previous issue date: 2013-03-11 / The growing number of manufactured transistors in embedded systems follows the trend of Moore s Law, which states that every eighteen months the number of transistors on integrated circuits doubles, while its cost remains constant. Another important issue in embedded systems is that applications with more than one processor are increasingly present in market. These devices with several processing elements are named MPSoCs (Multiprocessor System-on-Chip). MPSoCs enables the development of complex systems, together with high performance. Applications executing in MPSoC have constraints to be respected. To meet these constraints, management techniques and resources adaptability should be researched and developed. This work presents the development and evaluation of adaptive management techniques that enable applications executing in MPSoCs to meet their performance requirements. The MPSoC management uses monitoring techniques, which evaluate applications constraints, as throughput and latency. When violations are detected by the monitoring infrastructure, adaptive techniques are executed. In the scope of this work, two techniques were developed: dynamic change in the priority scheduling of tasks and task migration. The evaluation of the proposed techniques is carried out using the HeMPS MPSoC, with centralized and distributed resource management. Results show that, regardless the resource management technique adopted, the proposed adaptive techniques decrease latency and jitter, without affecting the total execution time of applications. With performed adaptive techniques the total execution time wasn t penalized, in presented experiments increased 7%. / A capacidade de integra??o em sistemas embarcados acompanha a tend?ncia da Lei de Moore, a qual prev? que a cada dezoito meses o n?mero de transistores em circuitos integrados dobra, enquanto seu custo permanece constante. Outra observa??o importante em sistemas embarcados ? que aplica??es com mais de um processador est?o cada vez mais presentes no mercado. Estes dispositivos com diversos elementos de processamento s?o denominados MPSoCs (do ingl?s, Multiprocessor Sytem-on-Chip). Os MPSoCs permitem o desenvolvimento de sistemas complexos, com alto desempenho. Para que um MPSoC atenda ?s restri??es das aplica??es nele executadas, t?cnicas de ger?ncia e adaptabilidade de recursos devem ser pesquisadas e desenvolvidas. O presente trabalho apresenta o desenvolvimento e avalia??o de t?cnicas de controle adaptativo para atendimentos a requisitos de aplica??es executando em MPSoCs. Para efetuar o controle do MPSoC utiliza-se o mecanismo de monitoramento das aplica??es. A t?cnica de monitoramento analisa os requisitos das aplica??es, em tempo de execu??o, verificando poss?veis viola??es nestes requisitos, como vaz?o e lat?ncia. O monitoramento ? o gatilho para a execu??o das t?cnicas adaptativas desenvolvidas no escopo deste trabalho: altera??o din?mica na prioridade de escalonamento de tarefas e migra??o de tarefas. Para avaliar as t?cnicas propostas, foi utilizado a plataforma HeMPS com ger?ncia de recursos centralizada e distribu?da. Os resultados mostram que, independente da ger?ncia de recursos que se utiliza, centralizada ou distribu?da, as t?cnicas de adaptabilidade proveem redu??o de lat?ncia e jitter, sem comprometimento do tempo total de execu??o das aplica??es. Com a execu??o das t?cnicas de adaptabilidade, o tempo total de execu??o da aplica??o principal n?o ? penalizado, nos casos de teste, melhorando-se em at? 7%.

Submitted by Setor de Tratamento da Informa??o - BC/PUCRS (tede2@pucrs.br) on 2015-09-18T20:30:53Z No. of bitstreams: 1 475052 - Texto Completo.pdf: 8325686 bytes, checksum: 5d74943dc9ee311c90eb182fb022e539 (MD5) / Made available in DSpace on 2015-09-18T20:30:53Z (GMT). No. of bitstreams: 1 475052 - Texto Completo.pdf: 8325686 bytes, checksum: 5d74943dc9ee311c90eb182fb022e539 (MD5) Previous issue date: 2015-07-13 / MPSoCs with hundreds of cores are already available in the market. According to the ITRS roadmap, such systems will integrate thousands of cores by the end of the decade. The definition of where each task will execute in the system is a major issue in the MPSoC design. In the literature, this issue is defined as task mapping. The growth in the number of cores increases the complexity of the task mapping. The main concerns in task mapping in large systems include: (i) scalability; (ii) dynamic workload; and (iii) reliability. It is necessary to distribute the mapping decision across the system to ensure scalability. The workload of emerging large MPSoCs may be dynamic, i.e., new applications may start at any moment, leading to different mapping scenarios. Therefore, it is necessary to execute the mapping process at runtime to support a dynamic workload. Reliability is tightly connected to the system workload distribution. Load imbalance may generate hotspots zones and consequently thermal implications, which may result in unreliable system operation. In large scale MPSoCs, reliability issues get worse since the growing number of cores on the same die increases power densities and, consequently, the system temperature. The literature presents different task mapping techniques to improve system reliability. However, such approaches use a centralized mapping approach, which are not scalable. To address these three challenges, the main goal of this Thesis is to propose and evaluate distributed mapping heuristics, executed at runtime, ensuring scalability and a fair workload distribution. Distributing the workload and the traffic inside the NoC increases the system reliability in long-term, due to the minimization of hotspot regions. To enable the design space exploration of large MPSoCs the first contribution of the Thesis lies in a multi-level modeling framework, which supports different models and debugging capabilities that enrich and facilitate the design of MPSoCs. The simulation of lower level models (e.g. RTL) generates performance parameters used to calibrate abstract models (e.g. untimed models). The abstract models pave the way to explore mapping heuristics in large systems. Most mapping techniques focus on optimizing communication volume in the NoC, which may compromise reliability due to overload processors. On the other hand, a heuristic optimizing only the workload distribution may overload NoC links, compromising its reliability. The second significant contribution of the Thesis is the proposition of dynamic and distributed mapping heuristics, making a tradeoff between communication volume (NoC links) and workload distribution (CPU usage). Results related to execution time, communication volume, energy consumption, power traces and temperature distribution in large MPSoCs (144 processors) confirm the tradeoff hypothesis. Trading off workload and communication volume improves system reliably through the reduction of hotspots regions, without compromising system performance. / MPSoCs com centenas de processadores j? est?o dispon?veis no mercado. De acordo com o ITRS, tais sistemas integrar?o milhares de processadores at? o final da d?cada. A defini??o de onde cada tarefa ser? executada no sistema ? um desafio importante na concep??o de MPSoCs. Na literatura, tal desafio ? definido como mapeamento de tarefas. O aumento do n?mero de processadores aumenta a complexidade do mapeamento de tarefas. As principais preocupa??es em mapeamento de tarefas em grandes sistemas incluem: (i) escalabilidade; (ii) carga din?mica de trabalho; e (iii) confiabilidade. ? necess?rio distribuir a decis?o do mapeamento pelo sistema para garantir escalabilidade. A carga de trabalho em MPSoCs pode ser din?mica, ou seja, novas aplica??es podem iniciar a execu??o a qualquer momento, levando a diferentes cen?rios de mapeamento. Portanto, ? necess?rio executar o processo de mapeamento em tempo de execu??o para suportar uma carga de trabalho din?mica. Confiabilidade ? diretamente relacionada ? distribui??o da carga de trabalho no sistema. Desequil?brio de carga pode gerar zonas de hotspots e implica??es termais, que podem resultar em uma opera??o do sistema n?o confi?vel. Em MPSoCs de grande dimens?o problemas de confiabilidade se agravam, uma vez que o crescente n?mero de processadores no mesmo chip aumenta o consumo de energia e, consequentemente, a temperatura do sistema. A literatura apresenta diferentes t?cnicas de mapeamento de tarefas para melhorar a confiabilidade do sistema. No entanto, tais t?cnicas utilizam uma abordagem de mapeamento centralizado, a qual n?o ? escal?vel. Em fun??o destes tr?s desafios, o principal objetivo desta Tese ? propor e avaliar heur?sticas de mapeamento distribu?do, executadas em tempo de execu??o, garantindo escalabilidade e uma distribui??o de carga de trabalho uniforme. Distribuir a carga de trabalho e o tr?fego da NoC aumenta a confiabilidade do sistema no longo prazo, devido ? minimiza??o das regi?es de hotspot. Para permitir a explora??o do espa?o de projeto em MPSoCs, a primeira contribui??o desta Tese consiste em um ambiente de modelagem multi-n?vel, que suporta diferentes modelos e capacidades de depura??o que enriquecem e facilitam o projeto de MPSoCs. A simula??o de modelos de mais baixo n?vel (por exemplo, RTL) gera par?metros de desempenho utilizados para calibrar modelos mais abstratos. Os modelos abstratos facilitam a explora??o de heur?sticas de mapeamento em grandes sistemas. A maioria das t?cnicas de mapeamento se concentram na otimiza??o do volume comunica??o na NoC, o que pode comprometer a confiabilidade, devido ? sobrecarga de processadores. Por outro lado, uma heur?stica que visa a otimiza??o apenas da distribui??o de carga de trabalho pode sobrecarregar canais da NoC, comprometendo a sua confiabilidade. A segunda contribui??o significativa desta Tese ? a proposi??o de heur?sticas de mapeamento din?mico e distribu?dos, fazendo um compromisso entre o volume de comunica??o (canais da NoC) e distribui??o de carga de trabalho (uso da CPU). Os resultados relacionados a tempo de execu??o, volume de comunica??o, consumo de energia, distribui??o de pot?ncia e temperatura em grandes MPSoCs (256 processadores) confirmam a hip?tese deste compromisso. Fazer um compromisso entre carga de trabalho e volume de comunica??o melhora a confiabilidade do sistema atrav?s da redu??o de regi?es hotspots, sem comprometer o desempenho do sistema.

Made available in DSpace on 2013-08-07T18:42:22Z (GMT). No. of bitstreams: 1 000426062-Texto+Completo-0.pdf: 4398366 bytes, checksum: a7895c5830e8843972ffac29c4084ef7 (MD5) Previous issue date: 2010 / The constant evolution of market needs requires the availability of computing systems with ever- growing performance. Increases in operating frequencies and instruction level parallelism in microprocessors are not alone sufficient anymore to guarantee performance scaling for such systems. A way to achieve scaling performance has been the adoption of Multiprocessor Systems on a Chip (MPSoCs), which allow distributing application computation costs along a set of processing elements in the MPSoC. The increase in the number of MPSoC processing elements as technology advances into the deep submicron domain is a clear trend. To interconnect such elements it is necessary to employ more efficient communication infrastructures in what concerns electrical characteristics, facility of adoption by designers and performance. Networks on Chip (NoCs) or on chip networks are a clear trend in this sense. In the same way computation performance is expected to increase, so is the performance of communication among processing elements in future MPSoCs. Obviously, NoCs may still suffer from congestion, which degrades the communication quality due, for example, to the increase of latency while delivering messages. The use of adaptive routing algorithms in NoCs allows altogether to solve or at least to alleviate congestion scenarios, but adaptation decisions usually employ only the instantaneous state of the communication network and are based on local information. The problem with this kind of approach is the unpredictability of latency in delivering network packets since the path followed by each packet depends on the state of the network and on the rules adopted by the routing algorithm as well. Additionally, deviations from a route considered congested can take packets to regions with even higher traffic. This thesis proposes two communication infrastructures that allow an improved degree of predictability and are thus more useful to fulfill application communication requirements. Both infrastructures employ source routing strategies. The first, called Hermes-SR NoC, explores the mapping of communication routes at design time. Initial results demonstrate this infrastructure displays gains when compared to the Hermes NoC, a network without congestion solving mechanisms, which uses an XY deterministic routing algorithm. The second infrastructure, called MoNoC (Monitored NoC), explores resources that enable dynamic route adaptation to take place. These resources include special network interfaces, monitors e network probes. Experimental results achieved with MoNoC showed significant reductions for application latency. In both cases, the adoption of adaptive routing algorithms as a base to compute routes enables to turn traffic away from congestion points in the network, which naturally increases latency and packet delivery predictability. / A constante evolução das necessidades de mercado exige que sejam disponibilizados sistemas computacionais com poder de processamento cada vez maior. O aumento da frequência de operação e o paralelismo de instruções em microprocessadores não são mais suficientes para garantir a melhora do desempenho destes sistemas. Uma forma de garantir tal aumento no poder de processamento é o desenvolvimento de sistemas multiprocessados em um único chip (MPSoC), o que permite dividir os custos de computação de aplicações pelos elementos de processamento que o formam. É tendência que o número de elementos de processamento que compõe um MPSoC cresça com o avanço em direção a tecnologias submicrônicas. Para interconectar tais elementos de processamento são necessárias infraestruturas de comunicação mais eficientes do ponto de vista de características elétricas, facilidade de adoção em projetos e desempenho. Redes em chip (do inglês, Networks on Chip ou NoCs) são vistas como uma tendência neste processo. Assim como o aumento do desempenho da computação prevê-se também o aumento do desempenho da comunicação entre os elementos de processamento. Obviamente, NoCs podem sofrer com fenômenos de congestionamento, que degradam a qualidade das comunicações devido, por exemplo, ao aumento da latência de entrega de mensagens. O uso de algoritmos adaptativos em NoCs permite reduzir o congestionamento, mas decisões de adaptação são normalmente baseadas no estado instantâneo da rede e apenas no uso de informação local. O problema deste tipo de abordagem é a imprevisibilidade da latência de entrega de pacotes, visto que a rota a ser utilizada por um pacote depende do estado da rede e da regra adotada pelo algoritmo de roteamento. Adicionalmente, o desvio de uma rota considerada congestionada pode levar a outras com concentração de tráfego ainda maior.O presente trabalho propõe duas infraestruturas de comunicação que permitem maior previsibilidade, sendo assim úteis para melhor atender requisitos de comunicação de aplicações. Ambas as infraestruturas propostas empregam roteamento na origem. A primeira, denominada NoC Hermes- SR explora o mapeamento de rotas de comunicação realizado em tempo de projeto. Resultados iniciais mostram um ganho desta infraestrutura de comunicação quando comparada à NoC Hermes com roteamento determinístico XY, uma NoC sem mecanismos para reduzir congestionamentos. Na segunda infraestrutura de comunicação, chamada MoNoC (de NoC Monitorada), exploram-se recursos que contribuem para permitir adaptação de rotas, tais como interfaces de rede, monitores e sondas de rede. Resultados capturados para tal infraestrutura apresentaram reduções significativas de latência de aplicação. Em ambos os casos, a adoção de algoritmos de roteamento adaptativos quando utilizados como base para a definição de rotas permite contornar caminhos congestionados na rede aumentando a previsibilidade de latência de entrega de pacotes.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação. / Made available in DSpace on 2012-10-26T07:02:27Z (GMT). No. of bitstreams: 1 300498.pdf: 2938637 bytes, checksum: 7398afa3a077fac745bb7fa071d4f174 (MD5) / O multiprocessamento em chip (CMP) mudou o panorama arquitetural dos servidores e computadores pessoais e agora está mudando o modo como os dispositivos pessoais móveis são projetados. CMP requer acesso a variáveis compartilhadas em hierarquias multiníveis sofisticadas onde caches privadas e compartilhadas coexistem. Ele se baseia no suporte em hardware para implicitamente gerenciar o relaxamento da ordem de programa e a atomicidade de escrita de modo a fornecer, na interface software-hardware, uma semântica de memória compartilhada bem definida, que é capturada pelos axiomas de um modelo de consistência de memória (MCM). Este trabalho aborda o problema de verificar se uma representação executável do subsistema de memória implementa um MCM especificado. Técnicas convencionais de verificação codificam os axiomas como arestas de um único grafo orientado, inferem arestas extras a partir de traces de memória e indicam um erro quando um ciclo é detectado. Usando uma abordagem diferente, esta dissertação propõe uma nova técnica que decompõe o problema de verificação em múltiplas instâncias de um problema (estendido) de emparelhamento de vértices em grafos bipartidos. Como a decomposição foi judiciosamente projetada para induzir instâncias independentes, o problema-alvo pode ser resolvido por um algoritmo paralelo de verificação. Também é proposto um gerador de sequências de instruções aleatórias distribuídas em múltiplas threads para estimular o sistema de memória sob verificação. Por ser independente do MCM sob verificação, o gerador proposto pode ser utilizado pela maioria dos verificadores. A técnica proposta, que é comprovadamente completa para diversos MCMs, superou um verificador convencional para um conjunto de 2400 casos de uso gerados aleatoriamente. Em média, o verificador proposto encontrou um maior percentual de faltas (90%) comparado ao convencional (69%) e foi, em média, 272 vezes mais rápido. / Chip multiprocessing (CMP) changed the architectural landscape of servers and personal computers and is now changing the way personal mobile devices are designed. CMP requires access to shared variables in sophisticated multilevel hierarchies where private and shared caches coexist. It relies on hardware support to implicitly manage relaxed program order and write atomicity so as to provide, at the hardware-software interface, a well-defined sharedmemory semantics, which is captured by the axioms of a memory consistency model (MCM). This dissertation addresses the problem of checking if an executable representation of the memory system complies with a specified consistency model. Conventional verification techniques encode the axioms as edges of a single directed graph, infer extra edges from memory traces, and indicate an error when a cycle is detected. Unlike them, this dissertation proposes a novel technique that decomposes the verification problem into multiple instances of an extended bipartite graph matching problem. Since the decomposition was judiciously designed to induce independent instances, the target problem can be solved by a parallel verification algorithm. To stimulate the memory system under verification, the dissertation also proposes a generator of multi-threading random-instruction sequences. It complies with an arbitrary MCM and can be used by most checkers. Our technique, which is proven to be complete for several MCMs, outperformed a conventional checker for a suite of 2400 randomly-generated use cases. On average, it found a higher percentage of faults (90%) as compared to that checker (69%) and did it, on average, 272 times faster.

As limitações resultantes do avanço das tecnologias de integração, como o crescente aumento da densidade de potência, levando à necessidade de redução da frequência de operação dos circuitos somados à necessidade de redução do consumo energético, sejam por motivos ecológicos ou para melhor suprir dispositivos portáteis, trazem a necessidade de maior intervenção e personalização do hardware em relação às exigências do software. Em diversos níveis estas intervenções podem ser aplicadas, onde a granularidade pode variar desde elementos de processamento sendo completamente desativados até processadores tendo apenas unidades funcionais sendo desativadas, memórias cache reconfiguradas em tamanho e associatividade, etc. Entretanto, a reconfiguração do hardware deve atingir todas as etapas destes sistemas para que seja possível atingir redução satisfatória em termos de potência e consumo de energia. Além da integração acelerada de elementos de processamento em um mesmo circuito integrado, a crescente concentração de heterogêneas tarefas em um mesmo dispositivo, leva à integração de elementos de processamento também heterogêneos, e por consequência diferentes comportamentos variando de acordo com a aplicação. Para justificar esta reconfigurabilidade e heterogeneidade dos elementos de processamento este trabalho apresenta um estudo que possibilita a observação da execução de diferentes aplicações em elementos de processamento amplamente reconfiguráveis. Para que a reconfigurabilidade e heterogeneidade possam ser aplicáveis, foi inserida uma ferramenta capaz de manter a compatibilidade entre o elemento de processamento mestre e os elementos de processamento aceleradores reconfiguráveis disponíveis. Os experimentos apresentados baseiam-se na necessidade de manter a menor quantidade de silício ativa, acelerando o código fonte enquanto reduz-se o consumo de energia. Somada a redução de energia, a compatibilidade binária é levada em consideração buscando a manutenção da produtividade quando da utilização de sistemas heterogêneos reconfiguráveis. / The limitations resulting from the advancement of integration technologies, such as the increasing power density, leading to the need to reduce the operating frequency of the circuits added to the need to reduce energy consumption, whether for environmental reasons or to better serve mobile devices, bring the need for greater intervention and hardware customization to the demands of the software. To varying degrees these interventions can be applied where the granularity can range from processing elements being completely disabled until processors having only functional units being disabled, reset cache memories in size and associativity, etc. However, the reconfiguration of hardware should reach all stages of these systems so that you can achieve satisfactory reduction in power and energy consumption. In addition to the accelerated integration of processing elements on a single integrated circuit, the increasing concentration of heterogeneous tasks in a same device, also leads to the integration of heterogeneous processing elements, and therefore different behavior varies according to the application. To justify this reconfigurability and variety of processing elements this work presents a study that allows the observation of the implementation of different applications in widely reconfigurable processing elements. For reconfigurability and heterogeneity may be applicable, a tool to maintain compatibility between the master processing element and accelerators reconfigurable processing elements available was inserted. The experiments presented are based on the need to maintain the lowest amount of active silicon, accelerating the source code while reducing power consumption. Added to energy reduction, binary compatibility is taken into consideration seeking to maintain productivity when using reconfigurable heterogeneous systems.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Ciência da Computação / Made available in DSpace on 2013-03-04T19:18:38Z (GMT). No. of bitstreams: 1 305016.pdf: 1639667 bytes, checksum: 311ae2d24eecf273bdb00a19f87e1468 (MD5) / A fim de proporcionar a alta capacidade de processamento requerida pelos dispositivos eletrônicos pessoais, sem ultrapassar os limites aceitáveis de potência e de consumo de energia, os sistemas em chip (SoCs) adotam o multiprocessamento. Para tanto, os SoCs possuem 2, 4 ou mais processadores, cada um com caches L1 privativas, conectados por meio de um barramento. Como o espaço de endereçamento visto pelos processadores é único, a programação do sistema pode assumir o modelo de memória compartilhada. A coerência entre as caches geralmente é assegurada pelo protocolo snooping. Para tirar proveito do paralelismo dos SoCs multiprocessados (MPSoCs), aplicações são desenvolvidas com uso de múltiplas threads executando concorrentemente. Neste contexto, observa-se que os dados de pilha de uma dada thread são acessados somente pelo processador no qual a thread está executando. Desta forma, a relocação da pilha para memória scratchpad (SPM) pode ser explorada para reduzir a energia do subsistema de memória. Esta redução advém não apenas da menor energia gasta em cada acesso à pilha, mas também da redução das faltas nas caches L1 de dados e da penalidade imposta pelo protocolo snooping. No presente trabalho propõe-se uma técnica para o gerenciamento dinâmico de dados de pilha em múltiplas SPMs, visando redução de energia no subsistema de memória em MPSoCs. A técnica utiliza um gerenciador totalmente em software, o qual é responsável por alocar e desalocar os dados de pilha de thread em SPM. A utilização da técnica dispensa intervenção do programador, pois as alterações necessárias no código da aplicação são realizadas por um compilador adaptado. Foram obtidos resultados experimentais através da simulação de 400 aplicações geradas aleatoriamente, assumindo-se 20 plataformas multiprocessadas, totalizando 8000 casos de uso. Os resultados mostram que, variando-se o perfil das aplicações quanto à proporção de acessos a dados de pilha, a técnica proporciona reduções de energia no subsistema de memória entre 11% e 20%, em média, para plataformas com caches L1 de 32KB, e reduções entre 14,7% e 25,9%, em média, para plataformas com caches L1 de 64KB. Para plataformas com caches L1 de menor capacidade, a redução de energia é menor pois a penalidade de faltas nas caches L1 de instruções imposta pelo gerenciador torna-se relevante.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Ciência da Computação, Florianópolis, 2012 / Made available in DSpace on 2013-06-25T18:37:00Z (GMT). No. of bitstreams: 1 312070.pdf: 869350 bytes, checksum: 7c9faae8b5533abbd9b63ba136b44e99 (MD5) / Este trabalho aborda duas classes de problemas enfrentados na verificação de projetos que exibem comportamentos fora de ordem, especificamente a verificação funcional de aceleradores em hardware e a verificação de consistência em sistemas de memória compartilhada. Comportamentos fora de ordem surgem quando relaxam-se restrições de precedência para aumentar a taxa de uso de componentes de hardware concorrentes e, portanto, aumentar o desempenho. Entretanto, o projeto de um sistema que apresenta comportamentos fora de ordem é suscetível a erros pelo fato de o relaxamento de ordem requerer controle sofisticado. Este trabalho compara as garantias de verificação de três classes de checkers dinâmicos para módulos com suporte a eventos fora de ordem. Comprovadamente, scoreboards relaxados podem ser construídos com plenas garantias de verificação contanto que utilizem regras de atualização baseadas na remoção de dominadores. Resultados experimentais mostram que um scoreboard relaxado assim projetado requer aproximadamente 1/2 do esforço exigido por um scoreboard convencional. Verificar a conformidade do hardware com um modelo de consistência é um problema relevante cuja complexidade depende da observabilidade dos eventos de memória. Este trabalho também descreve uma nova técnica de verificação de consistência de memória on-the-fly a partir de uma representação executável de um sistema multi-core. Para aumentar a eficiência sem afetar as garantias de verificação, são monitorados três pontos por núcleo, ao invés de um ou dois, como proposto em trabalhos correlatos anteriores. Os três pontos foram selecionados para serem altamente independentes da microarquitetura do core. A técnica usa scoreboards relaxados concorrentes para detectar violações em cada core. Para detectar violações globais, utiliza-se a ordem linear de eventos induzida por um caso de teste. Comprovadamente, a técnica não induz falsos positivos nem falsos negativos quando o caso de teste expõe um erro que afeta as sequências monitoradas, tornando-se o primeiro checker on-the-fly com plenas garantias de verificação. Resultados experimentais mostram que ele requer aproximadamente 1/4 a 3/4 do esforço global exigido por um checker post-mortem que monitora duas sequências por processador. A técnica é pelo menos 100 vezes mais rápida do que um checker que monitora uma única sequência por processador.<br> / Abstract : This work addresses two classes of problems faced when verifying designs exhibiting out-of-order behaviors, namely the functional verification of hardware accelerators and the verification of consistency in shared-memory systems. Out-of-order behaviors result from relaxing precedence constraints to increase the usage rate of concurrent hardware components and, therefore, lead to a performance improvement. However, the design of a system handling out-of-order behaviors is error prone, since order relaxation asks for sophisticated control. This work compares the verification guarantees of three classes of dynamic checkers for modules handling out-of-order behaviors. Provenly, relaxed scoreboards can be built with full verification guarantees, as far as they employ an update rule based on the removal of dominators. Experimental results show that such a relaxed scoreboard needs approximately 1/2 of the effort required by a conventional one. Verifying the hardware compliance with a consistency model is a relevant problem, whose complexity depends on the observability of memory events. This work also describes a novel on-the-fly technique for verifying memory consistency from an executable representation of a multi-core system. To increase efficiency without hampering verification guarantees, three points are monitored per core, instead of one or two, as proposed in previous related works. The points were selected to be largely independent from the core#s microarchitecture. The technique relies on concurrent relaxed scoreboards to check for consistency violations in each core. To check for global violations, it employs a linear order of events induced by a given test case. Provenly, the technique neither indicates false negatives nor false positives when the test case exposes an error that affects the sampled sequences, making it the first on-the-fly checker with full guarantees. Experimental results show that it needs approximately 1/4 to 3/4 of the overall verification effort required by a post-mortem checker sampling two sequences per processor. The technique is at least 100 times faster than a checker sampling a single sequence per processor.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico, Programa de Pós-Graduação em Engenharia de Automação e Sistemas, Florianópolis, 2012 / Made available in DSpace on 2013-06-25T19:20:31Z (GMT). No. of bitstreams: 1 313378.pdf: 967313 bytes, checksum: 012ab6f0cbb1ad0adcf9ee8e7b0f6036 (MD5) / Sistemas computacionais de tempo real são identificados como aqueles sistemas computacionais submetidos a requisitos de natureza temporal. Nestes sistemas, os resultados devem estar corretos não somente do ponto de vista lógico, mas também devem ser gerados no momento correto. Em tais sistemas, quando existe o compartilhamento de recursos, a sincronização de tarefas no acesso a estes é fundamental para garantir tanto a exclusão mútua, quanto a limitação no tempo de espera (evitando inversões de prioridade descontroladas), visto que isto pode induzir as tarefas a gerarem seus resultados em momentos incorretos (perda de deadlines ou não atendimento de algum requisito temporal). O não atendimento de um requisito temporal pode resultar em consequências catastróficas tanto no sentido econômico quanto em vidas humanas, dependendo do tipo de sistema. Para sincronização em multiprocessadores, alguns protocolos para escalonamento particionado foram propostos, como o Multiprocessor Priority Ceiling Protocol (MPCP), Flexible Multiprocessor Locking Protocol (FMLP) e o Multiprocessor Stack Resource Policy (MSRP). Neste contexto, esta dissertação de mestrado propõe duas variações para o protocolo MPCP, com as devidas análises de escalonabilidade e fatores de bloqueios associados. No entanto, ambas as variações podem ser encaradas também como variações do FMLP, dependendo do ponto de vista, pois abrangem características comuns a ambos os protocolos. Tais variações são o MPCP não preemptivo e MPCP com enfileiramento FIFO. Esta dissertação também apresenta comparações empíricas entre as propostas apresentadas e os protocolos existentes. Como resultados gerais, as propostas apresentadas se mostraram competitivas tanto em escalonabilidade quanto em overhead de implementação. O MPCP com enfileiramento FIFO se posicionou muito bem em sua versão baseada em suspensão. O MPCP não preemptivo, em sua versão baseada em spin obteve resultados muito próximos ao FMLP short. Do ponto de vista prático, as variações propostas facilitam a utilização em sistemas reais, quando comparadas com as propostas originais.<br> / Abstract : Real-time computational systems are identified as those systems subjected requirements of temporal nature. In these systems, the results should be correct not only from logical point of view, but also must be generated at the right time. In such systems, when there is resource sharing, tasks synchronization on access to these resources is essential to ensure both mutual exclusion and limitation of the waiting time (avoiding uncontrolled priority inversion), as this may induce the tasks to generate their results at wrong times (miss of deadlines or not meet a time requirement). A failure to meet a time requirement can result in catastrophic consequences both in the economic sense and in human lives, depending on the type of the system. For synchronization in multiprocessors, some protocols have been proposed for partitioned scheduling, as the Multiprocessor Priority Ceiling Protocol (MPCP), Flexible Multiprocessor Locking Protocol (FMLP) and Multiprocessor Stack Resource Policy (MSRP). In this context, this dissertation proposes two changes to the MPCP protocol, with appropriate schedulability analysis and blocking factors associated. However, both variants can also be viewed as variations of FMLP, depending on the point of view, because they cover features common to both protocols. Such variations are the nonpreemptive MPCP and the MPCP with FIFO queuing. This dissertation also presents empirical comparisons between the previously mentioned well-known protocols and the proposed variations. As general results, the proposals have showed to be competitive in both schedulability and implementation overhead. The MPCP with FIFO queuing was positioned very well in the suspension-based version. The nonpreemptive MPCP, in his spin-based version obtained results very close to the FMLP short. From a practical standpoint, the proposed changes facilitate the implementation in real systems, when compared to the original proposals.

Made available in DSpace on 2016-05-04T12:04:26Z (GMT). No. of bitstreams: 1 000478388-Texto+Completo-0.pdf: 3535458 bytes, checksum: a287a27f46a74cc898a15dccbe61ef44 (MD5) Previous issue date: 2016 / Embedded systems adopt NoC-based MPSoCs since a large number of processing elements (PEs) enables the simultaneous execution of several applications, where some of these applications require real-time (RT) constraints. PEs communicate using messages in distributed memory MPSoCs. These messages can be classified as application messages, being the data generated by the applications, and management messages, used to ensure the correct operation of the platform. As the communication has a large impact on the application performance, an important concern in the design of MPSoCs is to improve the performance of the applications’ communication, particularly for RT applications. Two possible methods to optimize the communication performance includes: (i) prioritize the RT application messages over the messages generated by best-effort (BE) applications; (ii) isolate the application messages from the management messages, considering that complex MPSoCs require a large number of management services to meet the performance constraints. The NoC literature contains several works that differentiate traffic classes, proposing the isolation of these traffic classes by the use of multiple physical (MP) NoCs, reducing interferences among the flows belonging to different classes. The main goal of this work is to propose and to evaluate MP NoCs, with one network dedicated to the application messages and a second network for the management messages (MNoC).Based on the evaluation of the impact of the management traffic in the overall NoC communication, two different versions of M-NoCs are implemented and evaluated. Another important consideration for RT applications is to ensure that these applications meet their deadlines. The execution of these applications must have higher priority over the BE applications by dedicating more processing resources using a specialized RT scheduler. This work presents and evaluates an MPSoC platform capable of supporting both communication and computation QoS, being extensible for a large number of management services by to the use of MP NoCs. Results show that M-NoCs may be customized to have a small area overhead. The adoption of M-NoCs improves the communication performance, latency and jitter, even when the network used in the platform has QoS mechanisms (e. g. priority flows and circuit switching), by isolating the management traffic from the application traffic. / Sistemas embarcados adotam MPSoCs baseados em NoCs visto que um número grande de elementos de processamento (PEs) permitem a execução simultânea de várias aplicações, onde algumas dessas aplicações necessitam de restrições de tempo real (RT). PEs comunicam-se utilizando troca de mensagens em MPSoCs com memória distribuída. Essas mensagens podem ser classificadas como mensagens de aplicação, sendo os dados gerados pelas aplicações, e mensagens de gerência, utilizadas para garantir a operação correta da plataforma. Visto que a comunicação possui um forte impacto no desempenho da aplicação, uma preocupação importante no projeto de MPSoCs é de melhorar o desempenho da comunicação das aplicações, especialmente para aplicações RT. Dois métodos possíveis para otimizar o desempenho de comunicação incluem: (i) priorizar as mensagens das aplicações de RT sobre as mensagens geradas por aplicações de melhor esforço (do inglês, best effort, BE); (ii) isolar as mensagens de aplicações das mensagens de gerência, considerando que MPSoCs complexos necessitam de um grande número de serviços de gerência para satisfazer os requisitos de desempenho. Na literatura sobre NoCs há vários trabalhos que diferenciam classes de tráfego, propondo o isolamento dessas classes de tráfego pela utilização de múltiplas NoCs físicas (do inglês, multiple physical NoCs, MP NoCs), reduzindo interferências entre fluxos pertencentes a classes diferentes. O principal objetivo deste trabalho é propor e avaliar MP NoCs, onde uma rede é dedicada para mensagens de aplicação e uma segunda rede é utilizada para mensagens de gerência (M-NoC).Baseado na avaliação do impacto do tráfego de gerência na comunicação da NoC, duas versões da M-NoC são implementadas e avaliadas. Outra consideração importante para aplicações RT é garantir que os deadlines dessas aplicações sejam satisfeitos. A execução dessas aplicações deve ser priorizada sobre as aplicações BE através do fornecimento de mais recursos de processamento utilizando um escalonador RT especializado. Esse trabalho apresenta e avalia uma plataforma MPSoC capaz de suportar QoS de comunicação e de computação, sendo extensível para um número grande de serviços de gerência pelo uso de MP NoCs. Resultados mostram que as M-NoCs podem ser personalizadas para terem um pequeno impacto de área. A utilização de M-NoCs melhora o desempenho de comunicação, latência e jitter, mesmo considerando que a plataforma já possui mecanismos de QoS (como fluxos prioritários e chaveamento de circuitos), pelo isolamento do tráfego de gerência do tráfego de aplicação.

As limitações resultantes do avanço das tecnologias de integração, como o crescente aumento da densidade de potência, levando à necessidade de redução da frequência de operação dos circuitos somados à necessidade de redução do consumo energético, sejam por motivos ecológicos ou para melhor suprir dispositivos portáteis, trazem a necessidade de maior intervenção e personalização do hardware em relação às exigências do software. Em diversos níveis estas intervenções podem ser aplicadas, onde a granularidade pode variar desde elementos de processamento sendo completamente desativados até processadores tendo apenas unidades funcionais sendo desativadas, memórias cache reconfiguradas em tamanho e associatividade, etc. Entretanto, a reconfiguração do hardware deve atingir todas as etapas destes sistemas para que seja possível atingir redução satisfatória em termos de potência e consumo de energia. Além da integração acelerada de elementos de processamento em um mesmo circuito integrado, a crescente concentração de heterogêneas tarefas em um mesmo dispositivo, leva à integração de elementos de processamento também heterogêneos, e por consequência diferentes comportamentos variando de acordo com a aplicação. Para justificar esta reconfigurabilidade e heterogeneidade dos elementos de processamento este trabalho apresenta um estudo que possibilita a observação da execução de diferentes aplicações em elementos de processamento amplamente reconfiguráveis. Para que a reconfigurabilidade e heterogeneidade possam ser aplicáveis, foi inserida uma ferramenta capaz de manter a compatibilidade entre o elemento de processamento mestre e os elementos de processamento aceleradores reconfiguráveis disponíveis. Os experimentos apresentados baseiam-se na necessidade de manter a menor quantidade de silício ativa, acelerando o código fonte enquanto reduz-se o consumo de energia. Somada a redução de energia, a compatibilidade binária é levada em consideração buscando a manutenção da produtividade quando da utilização de sistemas heterogêneos reconfiguráveis. / The limitations resulting from the advancement of integration technologies, such as the increasing power density, leading to the need to reduce the operating frequency of the circuits added to the need to reduce energy consumption, whether for environmental reasons or to better serve mobile devices, bring the need for greater intervention and hardware customization to the demands of the software. To varying degrees these interventions can be applied where the granularity can range from processing elements being completely disabled until processors having only functional units being disabled, reset cache memories in size and associativity, etc. However, the reconfiguration of hardware should reach all stages of these systems so that you can achieve satisfactory reduction in power and energy consumption. In addition to the accelerated integration of processing elements on a single integrated circuit, the increasing concentration of heterogeneous tasks in a same device, also leads to the integration of heterogeneous processing elements, and therefore different behavior varies according to the application. To justify this reconfigurability and variety of processing elements this work presents a study that allows the observation of the implementation of different applications in widely reconfigurable processing elements. For reconfigurability and heterogeneity may be applicable, a tool to maintain compatibility between the master processing element and accelerators reconfigurable processing elements available was inserted. The experiments presented are based on the need to maintain the lowest amount of active silicon, accelerating the source code while reducing power consumption. Added to energy reduction, binary compatibility is taken into consideration seeking to maintain productivity when using reconfigurable heterogeneous systems.