Este trabalho descreve o projeto lógico de três meios alternativos de interconexão entre processadores e módulos de memória para um sistema multimicroprocessador: barramento multiplexado, múltiplos barramentos dedicados/memórias multiporta e matriz de barramentos cruzados. Com vistas ao projeto, são analisadas as características operacionais de multiprocessadores e identificadas algumas de suas funções de controle. O problema de interconexão em sistemas compostos de múltiplas unidades de processamento é abordado hierarquicamente. São mostradas as formas de se realizar a estrutura de interconexão, dando-se maior atenção aos barramentos digitais são apresentados os protocolos de arbitração e protocolos de comunicação mais utilizados neste tipo de estrutura. / This work describes the logical project of three alternative ways of interconnecting processors and memory modules in a multimicro processor system: multi p lexed bus, multi ple dedicated buses/multi-port memories, and cross-bar matrix. Aiming the project, the o perational features of multiprocessors are analysed and some control functions identified. The interconnection problem in multiple processing units systems is hierarchichally approached, em phasizing digital buses. The arbitration protocols and communication Protocols mostly used in this kind of structure are shown.

Dissertação (mestrado) - Universidade Federal de Santa Catarina, Centro Tecnológico. Programa de Pós-Graduação em Engenharia de Automação e Sistemas / Made available in DSpace on 2012-10-26T12:25:42Z (GMT). No. of bitstreams: 1 301047.pdf: 1285723 bytes, checksum: fcb30ba5e90539742c71505b32d65921 (MD5) / Sistemas de tempo real são sistemas onde o correto funcionamento não depende somente da resposta lógica correta, mas também do tempo no qual ela foi dada. Igualmente do ponto de vista lógico, a viabilidade temporal da aplicação deve ser determinada através de técnicas, como por exemplo análise do tempo de reposta. Este tipo de aplicação está cada vez mais presente atualmente e a demanda de processamento é tamanha que necessita-se de processadores com múltiplos núcleos complexos. É perceptível que o desenvolvimento dos multiprocessadores está muito mais avançado em relação às técnicas de análise de tais sistemas e, portanto, é evidente a necessidade de pesquisa com objetivo de promover maior confiabilidade e redução de superdimensionamentos. O objetivo deste trabalho é promover uma solução de escalonamento que considere a escalonabilidade em conjunto com a analisabilidade do código da aplicação. Atualmente, a pesquisa de sistemas de tempo real trata o problema do escalonamento isolado do problema de obtenção do parâmetro do tempo de computação da tarefas (WCET --Worst Case Execution Time). Dependendo da arquitetura do processador, as premissas adotadas no cálculo do WCET são incompatíveis com as premissas de escalonamento, o que gera uma contradição fundamental entre o cálculo do WCET e os algoritmos de escalonamento. A incompatibilidade das premissas pode ser ilustrada pela preempção em arquiteturas com memória cache, onde o cálculo de WCET assume execução contínua da tarefa, o que não é verdade em grande parte dos algoritmos de escalonamento. Este trabalho propõe o uso de uma abordagem heterogênea em multiprocessadores onde parte dos núcleos operam em regime preemptivo e parte em regime não preemptivo para tentar lidar com as diferentes considerações sobre preempção. As análises realizadas mostram que existe vantagem em usar a abordagem heterogênea. / Real-time systems are systems where the correct functioning depends not only on the logically correct response, but also the time when it was given. As the the logic functionality, the application response time could be analyzed to determine the viability of a real-time system. This type of application is increasingly present today and the processing demand is such that complex multi-core processors are needed. It is noticeable that the development of multiprocessor is a long way ahead compared with the techniques of analysis of such systems and is therefore necessary researches to promote more reliability and to reduce over-specified systems. The objective of this work is to promote a solution that considers scheduling in conjunction with the analyzability of the application code. Currently, the real-time research considers the scheduling problem isolated from the WCET (Worst Case Execution Time) problem. Depending on the processor architecture, the values obtained by computing WCET are incompatible with the scheduling model which creates a fundamental contradiction between the assumptions of calculation of WCET and scheduling algorithms. This work proposes the use of a heterogeneous approach where part of the multiprocessor cores operate under preemptive and part on a non-preemptive scheduling. The analysis shows that there are advantages using the heterogeneous approach.

Este trabalho descreve o projeto lógico de três meios alternativos de interconexão entre processadores e módulos de memória para um sistema multimicroprocessador: barramento multiplexado, múltiplos barramentos dedicados/memórias multiporta e matriz de barramentos cruzados. Com vistas ao projeto, são analisadas as características operacionais de multiprocessadores e identificadas algumas de suas funções de controle. O problema de interconexão em sistemas compostos de múltiplas unidades de processamento é abordado hierarquicamente. São mostradas as formas de se realizar a estrutura de interconexão, dando-se maior atenção aos barramentos digitais são apresentados os protocolos de arbitração e protocolos de comunicação mais utilizados neste tipo de estrutura. / This work describes the logical project of three alternative ways of interconnecting processors and memory modules in a multimicro processor system: multi p lexed bus, multi ple dedicated buses/multi-port memories, and cross-bar matrix. Aiming the project, the o perational features of multiprocessors are analysed and some control functions identified. The interconnection problem in multiple processing units systems is hierarchichally approached, em phasizing digital buses. The arbitration protocols and communication Protocols mostly used in this kind of structure are shown.

Made available in DSpace on 2015-06-17T02:04:12Z (GMT). No. of bitstreams: 1 000470587-Texto+Completo-0.pdf: 6163395 bytes, checksum: b88f0389d39c7cc7f197b32966e6fe29 (MD5) Previous issue date: 2015 / The continuous development of the transistor technology has enabled hundreds of processors to work interconnected by a NoC (network-on-chip). Nanotechnology has enabled the development of complex systems, however, fault vulnerability also increased. The literature presents partial solutions for fault tolerance issues, targeting parts of the system. An important gap in the literature is an integrated method from the router-level fault detection to the correct execution of applications in the MPSoC. The main goal of this dissertation is to present a fault-tolerant method from the physical layer to the transport layer. The MPSoC is modeled at the RTL level using VHDL. This work proposes fault tolerance techniques applied to intra-chip networks. Related work on fault tolerance at a systemic level, router level, link level and routing algorithms are studied. This work presents the research and development of two techniques: (i) protocols to enable the correct communication between task with partial degradation of the link enabling the router to operate even with faulted physical channels; (ii) test recovery method and of the router. This Dissertation considers permanent and transient faults. The HeMPS platform is the reference platform to evaluate the proposed techniques, together with a fault injection campaign where up to five random failures were injected simultaneously at each simulated scenario. Two applications were used to evaluate the proposed techniques, MPEG encoder and a synthetic application, resulting in 2,000 simulated scenarios. The results demonstrated the effectiveness of the proposal, with most scenarios running correctly with routers operating in degraded mode, with an impact on the execution time below 1%, with a router area overhead around 30%. / O contínuo desenvolvimento na tecnologia de transistores possibilitou que centenas de processadores trabalhassem interconectados por NoCs (network-on-chip). A nanotecnologia permitiu o desenvolvimento de complexos sistemas, porém a vulnerabilidade a falhas também aumentou. A literatura apresenta soluções parciais para o tema de tolerância a falhas, tendo como alvo partes do sistema. Uma importante lacuna na literatura é um método integrado para detecção de falhas do nível do roteador até a correta execução das aplicações em MPSoC reais. O objetivo principal desta dissertação é apresentar um método com tolerância a falhas da camada física até a camada de transporte. O MPSoC é modelado em nível de RTL, usando VHDL.O presente trabalho propõe técnicas de tolerância a falhas aplicadas a redes intrachip. São estudadas técnicas de tolerância a falhas em nível sistêmico, nível do roteador, nível de enlace e algoritmos de roteamento tolerante a falhas. Este trabalho apresenta a pesquisa e o desenvolvimento de duas técnicas: (i) protocolos para permitir a correta transmissão dos dados com degradação parcial do enlace, de forma a permitir que o roteador opere mesmo com canais físicos falhos; (ii) método de teste e recuperação do roteador. O modelo de falhas utilizado nesta Dissertação é de falhas permanentes e transientes. Para avaliar as técnicas propostas, foi utilizada a plataforma HeMPS, juntamente com uma campanha de injeção de falhas onde até cinco falhas aleatórias foram injetadas nos canais de comunicação entre os roteadores simultaneamente em cada cenário. Foram utilizadas duas aplicações para avaliar as técnicas: codificador MPEG e uma aplicação sintética, com um total de 2,000 cenários simulados. Os resultados demonstram a efetividade da proposta, com a maioria dos cenários executando corretamente com roteadores operando em modo degradado, com um impacto no tempo de execução abaixo de 1% e um aumente do área de 30% no roteador.

Este trabalho descreve o projeto lógico de três meios alternativos de interconexão entre processadores e módulos de memória para um sistema multimicroprocessador: barramento multiplexado, múltiplos barramentos dedicados/memórias multiporta e matriz de barramentos cruzados. Com vistas ao projeto, são analisadas as características operacionais de multiprocessadores e identificadas algumas de suas funções de controle. O problema de interconexão em sistemas compostos de múltiplas unidades de processamento é abordado hierarquicamente. São mostradas as formas de se realizar a estrutura de interconexão, dando-se maior atenção aos barramentos digitais são apresentados os protocolos de arbitração e protocolos de comunicação mais utilizados neste tipo de estrutura. / This work describes the logical project of three alternative ways of interconnecting processors and memory modules in a multimicro processor system: multi p lexed bus, multi ple dedicated buses/multi-port memories, and cross-bar matrix. Aiming the project, the o perational features of multiprocessors are analysed and some control functions identified. The interconnection problem in multiple processing units systems is hierarchichally approached, em phasizing digital buses. The arbitration protocols and communication Protocols mostly used in this kind of structure are shown.

Orientador : João Bosco Ribeiro do Val / Dissertação (mestrado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica / Made available in DSpace on 2018-07-14T21:30:56Z (GMT). No. of bitstreams: 1 Maia_JoseEverardoBessa_M.pdf: 14536546 bytes, checksum: bebfc1c1e2475f5f58c910c2c71d81f7 (MD5) Previous issue date: 1989 / Resumo: É presentado um modelo de Cadeia de Markov a Tempo Contínuo (CMTC) para avaliação de desempenho de sistemas multiprocessadores na execução de sistemas de tarefas com estrutura hierárquica. O trabalho desenvolve a concentuação necessária à apresentação do problema e apresenta solução computacional para o modelo. São estudadas duas arquiteturas: arquitetura radial e arquitetura por barramento compartilhado. Um índice de desempenho é estabelecido que permite comparar as arquiteturas. Os resultados são aplicados na execução de algoritmos de otimização hierárquicos. Os casos nio-Markovianos são tratados através de técnicas de simulação de eventos discretos / Abstract: Not informed. / Mestrado / Mestre em Ciências

Orientador: Vinicius Amaral Armentano / Tese (doutorado) - Universidade Estadual de Campinas, Faculdade de Engenharia Eletrica e de Computação / Made available in DSpace on 2018-07-24T07:54:32Z (GMT). No. of bitstreams: 1 Mazzini_Renata_D.pdf: 12936662 bytes, checksum: 581f180b73d247423b83bd197041667d (MD5) Previous issue date: 1998 / Resumo: Neste trabalho estuda-se a aplicação de meta-heurísticas populacionais em problemas de programação da produção. O problema abordado consiste da minimização do atraso total na programação de tarefas em máquinas paralelas idênticas onde se consideram tempos de preparação de máquina dependentes da seqüência de processamento e datas de entregas distintas. São apresentadas duas implementações de Algoritmos Genéticos e quatro implementações de Busca por Espalhamento. Testes computacionais extensos foram realizados com essas implementações sobre um conjunto de problemas gerados aleatoriamente. Os resultados obtidos possibilitaram a realização de análises comparativas do desempenho e do comportamento das versões implementadas dessas duas meta-heurísticas quando aplicadas ao problema de programação da produção estudado / Abstract: The application of population-based meta-heuristics on scheduling problems is studied in this work. The problem which is addressed is the minimization of total tardiness when jobs are scheduled on identical parallel machines with sequence dependent set-up times and distinct due dates. Two implementations of Genetic Algorithms and four implementations of Scatter Search are presented. These implementations were extensively tested over a set of randomly generated problems. The obtained results were used to compare the performance and the behavior of the implemented versions of these two meta-heuristics when applied to the scheduling problem studied. / Doutorado / Doutor em Engenharia Elétrica

Orientador: Rogerio Drummond / Dissertação (mestrado) - Universidade Estadual de Campinas, Instituto de Matematica, Estatistica e Ciencia da Computação / Made available in DSpace on 2018-07-17T23:29:28Z (GMT). No. of bitstreams: 1 Hexsel_RobertoAndre_M.pdf: 2603589 bytes, checksum: 63a5073b316e9b7dd4121ccfbde1245d (MD5) Previous issue date: 1988 / Resumo: Esta Dissertação descreve o núcleo de tempo-real do Multiprocessador para Sistemas de Controle (MSC). O MSC foi desenvolvido no Instituto de Automação do Centro Tecnológico para Informática e possui características que o tornam adequado a aplicações em controle de processos e automação industrial. Estas aplicações exigem respostas rápidas a eventos externos e grande capacidade de processamento. O MSC pode ser configurado para satisfazer as mais diversas aplicações e diferentes níveis de desempenho, desde controladores de robô até gerenciadores de sistemas integrados de manufatura. O MSC é baseado no barramento VME e pode conter um ou mais processadores MC 68000 e zero ou mais processadores Z80. O barramento VME suporta a comunicação de baixo nível entre os programas executados em paralelo pelos processadores. Cada processador (MC 68000) executa o código (aplicativos e NÚCLEO) armazenado em sua memória local, à qual é conectado por um barramento privativo (padrão VMX). A sincronização e comunicação de alto nível entre os programas ocorre através da memória global, a que os processadores tem acesso pelo barramento VME. Os processadores de Entrada/Saída (PE/S) são escravos dos demais processadores. Os PE/S são interligados ao VME por memória dual-port: uma das portas é mapeada como memória global (no VME) e a outra é ligada ao barramento interno do PE/S. O NÚCLEO do MSC é estruturado segundo o modelo estratificado. A unidade lógica de computação é o processo. O mecanismo de sincronização interprocessos é uma extensão de semáforos para uso no ambiente multiprocessado do MSC. O mecanismo de comunicação interprocessos é a troca de mensagens através de caixas postais. A localização (em memória global ou local) dos objetos suportados pelo NÚCLEO é especificada somente na sua criação. Todas as outras operações referenciam apenas aos identificadores dos objetos (números inteiros). Chamamos esta caraçterística de Transparência de Multiprocessamento. Graças a ela, a programação do MSC, um multiprocessador, oferece um grau de dificuldade não maior que aquele apresentado por sistemas multitarefa convencionais. Além disso, se todos os objetos necessários à execução de um programa forem criados num mesmo processo, um aplicativo pode ser transportado para uma máquina com um número diferente de processadores sem alterações no seu código (exceto nos locais onde os objetos/recursos são criados). O NÚCLEO oferece primitivas para a criação e destruição de processos (locais e remotos), operações P e V sobre semáforos, operações sobre conjuntos de armazenadores e troca de mensagens através de caixas postais. Os semáforos possibilitam soluções simples e eficientes para problemas de exclusão mútua e sincronização condicional. As caixas postais permitem a implementação de vários paradigmas de comunicação interprocessos, tais como comunicação síncrona ou assíncrona, "pipes" e "rendezvous". / Abstract: This dissertation describes the real-time kernel for a Multiprocessor aimed at Control Systems Applications (MSC for short). The MSC multiprocessor was developed at Instituto de Automação, Centro Tecnológico para Informática. It has features that make it suitable for applications in industrial process control. These applications demand high throughput and prompt response to external events. The MSC can be configured to solve a wide variety of problems in control and automation, from robot controllers up to supervising chores in flexible manufacturing systems. The MSC is built around a VME bus and may have one or more MC 68000 based processors and zero or more Z80 based I/O processors. The VME bus supports the low leveI communication between the processors. Each processor (MC 68000) executes the code (application and KERNEL) stored in its local memory, to which it is connected, by a private bus (VMX bus). The high leveI synchronization and communication between the programs occurs through the global memory, which is accessed by the processors via the VME bus. The I/O processors interface to the VME bus is a dual ported memory: one port is connected to the global bus (mapped as global memory) and the other is connected to the I/O processor's internal bus. The MSC's KERNEL was designed as a layered structure. The logical unit of computation is the process. The interprocess syhchronization mecanism is an extension to semaphores so they can be used in the distribuited MSC's environrnent. The interprocess communication mecanism is message exchange through mailboxes. The loci (in either global or local memory) of the objects supported by the KERNEL is specified only at its creation. All the other operations upon them refer just to their identifiers (which are integers). We call this feature Multiprocessing Transparency. Thanks to it, the MSC's (a multiprocessor) programming presents no more difficulty than that of conventional multitasking systems. Furthermore, if alI the objects needed to a program's execution are created on one process, this program may be ported to a machine with a different number of processors without any changes to its code (except, of course, to the places where the objects are created). The KERNEL supports primitives for the creation and killing of processes (local and remote ones), P and V operations on semaphores, operations on buffer pools (get, release) and message exchange through mailboxes. The semaphores provide simple and effident solutions to mutual exclusion and condition synchronization problems. The mailboxes allow the implementation of many interprocess communication paradigms, such as synchronous and assynchronous communication, pipes and rendezvous. / Mestrado / Mestre em Ciência da Computação

O uso de técnicas de processamento paralelo tem se tornado bastante comum na implementação de sistemas computacionais de alto desempenho. Uma destas técnicas, o uso de múltiplos processadores independentes ligados a um sistema de memória compartilhado(normalmente denominada paralelismo MIMD fortemente acoplado), tem sido pesquisado de maneira especial, devido a sua flexibilidade e facilidade de programação. No entanto, a implementação de sistemas de memória compartilhada apresenta diversos desafios, porque um único sistema deve atender a acessos de diversos processadores rapidamente, e ainda assim apresentar um custo aceitável. Diversas propostas para estes sistemas são apresentadas neste trabalho, com atenção especial para cachês locais com mecanismos dinâmicos de garantia de consistência. Entre os mecanismos de consistência, são abordados os protocolos de posse de blocos(adequados a cachês copy-back), protocolos write-through e protocolos orientados por software (adequado a caches write-through)Este trabalho envolve simulações de algumas arquiteturas básicas, através de um simulador de multiprocessadores alimentado com programas de álgebra linear. Da-se especial atenção a comparação entre sistemas baseados em cachês copy-back e nos baseados em cachês write-through, considerando mecanismos de consistência baseados em hardware. Mostra-se que, apesar de exigirem uma largura de faixamaior para a memória principal, sistemas de cachês write-through são menos sensíveis a codificação dos programas do que os sistemas com cachês copy-back, apresentando desempenho melhor quando ha muito compartilhamento de dados.

Made available in DSpace on 2015-04-14T14:50:00Z (GMT). No. of bitstreams: 1 448655.pdf: 3228559 bytes, checksum: af4e73cef74eca9bd8a7fea60aae927f (MD5) Previous issue date: 2013-03-22 / Several new applications are composed by heterogeneity of tasks implying high complexity degree, and requiring high processing and communicating rate. Multiprocessor System-on-Chip (MPSoC) based on Network-on-Chip (NoC) is a promising targeting architecture to fulfill these requirements, due to its high computation and communication parallelism that enables several tasks executed at the same time. Furthermore, these applications requirements are better fulfilled by MPSoC composed by different types of processors heterogeneous MPSoC. One challenge in current heterogeneous MPSoC design is partitioning of application tasks, aiming energy consumption minimization and fair load balance. This work contribution is twofold: (i) analysis and comparison of partitioning algorithms; and (ii) the evaluation of partitioning as a pre-mapping task. This work analyzes and compares stochastic and new heuristic partitioning algorithms for obtaining low energy consumption and efficient load balance when applied to tasks partitioning onto heterogeneous MPSoC. In addition, performance results obtained from simulations indicate that the static partitioning technique can be used on application tasks before mapping activities to improve the quality on the static or dynamic mapping and also for minimizing processing time. / V?rias aplica??es novas s?o compostas por uma heterogeneidade de tarefas implicando alto grau de complexidade, e requerendo grande capacidade de processamento e comunica??o eficiente. Multiprocessor System-on-Chip (MPSoC) baseado em Network-on-Chip (NoC) ? uma arquitetura alvo promissora com capacidade de atender diversos requisitos de uma aplica??o alvo, devido ? alta capacidade de computa??o e grande paralelismo de comunica??o que possibilitam a execu??o de diversas tarefas simultaneamente. Al?m disso, requisitos de diversas aplica??es embarcadas s?o melhores atendidos por um MPSoC composto por v?rios tipos de processadores MPSoC heterog?neo. Um desafio atual no projeto de MPSoC heterog?neo ? particionar tarefas, almejando minimizar consumo de energia e ter balanceamento de carga apropriado. Este trabalho contribui duplamente em: (i) an?lise e compara??o de algoritmos de particionamento; e (ii) avalia??o do particionamento como uma atividade pr?-mapeamento. Este trabalho analisa e compara algoritmos de particionamentos estoc?sticos e heur?sticos, elaborados para obter baixo consumo de energia e balanceamento de carga eficiente quando aplicados a particionamento de tarefas em um MPSoC heterog?neo. Al?m disto, resultados de desempenho, obtidos atrav?s de simula??es, indicam que a t?cnica de particionamento est?tico de tarefas pode ser previamente aplicada ? atividade de mapeamento de grupos de tarefas em processadores da arquitetura alvo, aprimorando a qualidade do mapeamento est?tico ou din?mico, e ainda, minimizando o tempo de processamento.