Submitted by Santos Davilene (davilenes@ufba.br) on 2013-01-25T12:25:33Z No. of bitstreams: 1 TESE - Paul Regnier.pdf: 1122807 bytes, checksum: 968bc4ff6e54e1d57a2a511a607af27d (MD5) / Made available in DSpace on 2013-01-25T12:25:33Z (GMT). No. of bitstreams: 1 TESE - Paul Regnier.pdf: 1122807 bytes, checksum: 968bc4ff6e54e1d57a2a511a607af27d (MD5) / Neste trabalho de doutorado, propõe-se RUN (Redução para Uniprocessor), um novo algoritmo de escalonamento para conjunto de tarefas periódicas com deadlines implícitas em sistemas multiprocessador de tempo real, nos quais as tarefas possuem restrições tanto no domínio do tempo quanto no domínio de valores. RUN apresenta as seguintes propriedades relevantes: - RUN é ótimo no sentido que ele produz um escalonamento correto, no qual todas as restrições temporais são atendidas, de qualquer sistemas de tarefas utilizando até 100% dos processadores da plataforma de tempo real; - RUN usa o conceito-chave do escalonamento do tempo ócio, chamado de escalonamento por dualidade, segundo o qual, em algum instante t, o escalonamento de uma tarefa utiliza tanto o conhecimento de seu tempo de execução restante, bem como o seu tempo ócio restante; - RUN baseia-se na diminuição do número de tarefas a ser escalonadas pela suas agregações em supertasks, os quais chamamos de servidores, com taxa acumulada não superior a 1. Cada servidor é responsável por escalonar o seu conjunto de tarefas clientes, de acordo com alguma política de escalonamento; - RUN utiliza o princípio original de justiça global (Gfair), de acordo com o qual cada servidor de um conjunto de tarefas T é garantido de executar por um tempo proporcional à taxa acumulada das tarefas de T entre cada duas deadlines das tarefas de T; - RUN reduz o problema do escalonamento de um conjunto de tarefas em/m/ processadores no problema equivalente do escalonamento de um ou mais conjuntos de tarefas diferentes em sistemas monoprocessador; - RUN supera significativamente os algoritmos ótimos existentes em termos de preempções com um limite superior de O(log m) preempções média por jobs em/m/ processadores. / Salvador

[pt] O sistema operacional MINIX é uma nova implementação do sistema UNIX, versão 7, feito para fins didáticos. Ele está formado por uma coleção de processos, estruturados em 4 niveis: administração de processos, processos básicos do sistema, processos servidores de memória e arquivos, e processos usuários. A presente dissertação descreve o transporte do sistema MINIX, do microcomputador IBM PC XT para o computador CYGNUS do laboratório de Sistema de Computação do Departamento de Engenharia Elétrica da PUC/RJ, o qual possui uma arquitetura baseada em processadores da linha Motorola (68010 e 68020). O trabalho do transporte, constituiu em adaptar o hardware do CYGNUS para receber o sistema operacional MINIX, reprojetar o MINIX para o hardware do CYGNUS, e transportar o MINIX em forma completa, para seu novo ambiente de execução. / [en] The MINIX operating System is a new implementation of the UNIX operating system version 7, designed for didactic purposes. It is arranged as a collection of processes, structured in 4 levels: process management, system basic processes, memory and file server processes, and user processes. This work describes the transport of the MINIX system from the IBM PC XT microcomputer to te CYGNUS computer, which was developed in the Computer System Laboratory of the Electrical Engineering Department of PUC/RJ, with an architecture based on Motorola processors (68010 and 68020). The task of transporting the system, consisted in adjusting the CYCNUS hardware to accept the MINIX, redesigning the MINIX for the CYGNUS hardware, and finaly, in transporting the MINIX in its complete form to its new execution environment.

[pt] O sistema CYGNUS é um computador multiprocessador de memória compartilhada e arquitetura modular, baseado nos processadores da família Motorola MC68000, que vem sendo desenvolvido pelos Departamentos de Engenharia Elétrica e Informática da PUC/RJ. O presente trabalho consiste do projeto e implementação de dois módulos para o Sistema CYGNUS: módulo Arbitro e Módulo Supervisor. O Módulo Arbitro possibilita que o computador trabalhe em configuração multiprocessadora, já que disciplina o uso da barra de comunicação comum (VME) entre os Módulos Processadores. O módulo Supervisor foi construído para dar suporte a uma série de funções de gerenciamento e supervisão do sistema como um todo, possibilitando um melhor entendimento de seu comportamento e, conseqüentemente, um melhor aproveitamento de seus recursos. / [en] The CYGNUS System is a Motorola MC86000 based shared memory multiprocessor, with a modular architecture, that is being developd by the Engenharia Elétrica and Informática Departaments of PUC/RJ. This work is concerned with the design and implementation of two CYGNUS modules: the Arbiter Module and the Supervisor Module. The Arbiter Module allows CYGNUS to work in a multiprocessor configuration, by determining which Processor Module will access the common bus (VMF Standard), and dealing with the bus cintention. The Supervisor Module is a special Procesor Module, built to give support to a set of system management and supervision functions, which will make possible a better understanding of the system´s behavior, and a rational utilization of its resources.

[pt] Este trabalho apresenta um estudo e uma proposta de um sistema multiprocessador com organização de memórias multiportas. A memória é simulada através de técnicas de multiplexação no tempo e memórias rápidas. O trabalho inclui a avaliação do desempenho da arquitetura, assim como também, uma proposta de sua implementação utilizando microprocessadores de 16 bits. / [en] This work presents a study and a proposal of a multiprocessor system – multiport memory organization. The multiport memory is simulated through time multiplexing techniques and fast memories. The work includes an evaluation of the performance of the architecture as well as a proposal of its implementation utilizing 16 bit microprocessors.

Submitted by Kleber Silva (kleberbs@ufba.br) on 2017-05-31T19:17:00Z No. of bitstreams: 1 Ernesto Massa - Tese.pdf: 1801835 bytes, checksum: 8f11ff14bc272ec3af4ab83c894eb5db (MD5) / Approved for entry into archive by Vanessa Reis (vanessa.jamile@ufba.br) on 2017-06-06T14:41:17Z (GMT) No. of bitstreams: 1 Ernesto Massa - Tese.pdf: 1801835 bytes, checksum: 8f11ff14bc272ec3af4ab83c894eb5db (MD5) / Made available in DSpace on 2017-06-06T14:41:17Z (GMT). No. of bitstreams: 1 Ernesto Massa - Tese.pdf: 1801835 bytes, checksum: 8f11ff14bc272ec3af4ab83c894eb5db (MD5) / Sistemas de tempo real se caracterizam não somente pela necessidade do seu correto processamento lógico, mas também por terem que atender requisitos temporais, sendo a ordem escolhida para a execução das suas tarefas um aspecto particularmente relevante. Quando estes sistemas são classificados como críticos, o atendimento dos requisitos temporais é obrigatório, sob a pena de consequências catastróficas. A recente proliferação de sistemas computacionais compostos por múltiplos processadores fez com que as estratégias de escalonamento consolidadas para sistemas com uma única unidade de processamento, porém ineficientes para ambientes com múltiplos processadores, tivessem que ser substituídas por novas estratégias. As duas abordagens inicialmente adotadas, particionada e global, apresentaram problemas de eficiência ou de aplicabilidade, abrindo espaço para a abordagem semi-particionada. Esta estratégia distribui as tarefas pelos processadores, permitindo que apenas algumas tarefas específicas tenham permissão pera executar em dois ou mais processadores. Para que nenhuma destas tarefas específicas execute simultaneamente em mais de um processador, os algoritmos que seguem abordagens semi-particionadas definem reservas de tempo em que estas ocuparão os processadores, controlando a sua execução. Aproveitando-se de servidores, que garantem isolamento temporal entre tarefas que executam em um mesmo ambiente, este trabalho apresenta dois novos servidores como instrumento para implementar reservas de tempo, propondo dois novos algoritmos de escalonamento para sistemas de tempo real críticos em ambientes com múltiplos processadores que se utilizam destes servidores. Os experimentos realizados revelaram que os desempenhos destes algoritmos são comparáveis aos principais algoritmos de escalonamento relacionados, sendo que um dos algoritmos desenvolvidos foi provado ser ótimo com relação ao uso da capacidade computacional em múltiplos processadores.

[pt] O sistema Cygnus é um computador multiprocessador de memória compartilhada e estrutura modular desenvolvido pelos departamentos de Energia Elétrica e Informática da PUC/RJ. Este trabalho tem como objetivo a introdução de um novo controlador de acesso a discos e impressora. Este controlador é baseado no microprocessador 68010 e utiliza técnicas de implementação de memórias cachê de disco em um ambiente de multiprogramação onde processos, através de troca de mensagens, cooperam para aceitar várias solicitações simultâneas provenientes dos diversos processadores que compõem o sistema. / [en] The Cygnus system is a multiprocessor computere based on a modular structure with shared memory, which was developed at the Department of Electrical Engineering and Computer Science of PUC/RJ. The goal of this work is the introduction of a new controller to access disks and printer. This controller is based on the 68010 microprocessor unit and employs implementation techniques of disk caching in a multitask environment. In this environment, processes cooperate via message passing to serve simultaneous requests issued by other processors in the system.

[pt] Neste trabalho é abordado o problema da análise de desempenho de aplicações paralelas, especificamente de programas científicos. Apresentamos uma metodologia para a construção de modelos analíticos de desempenho para aplicações paralelas, executando em multiprocessadores de memória compartilhada. A metodologia é baseada na construção e integração de dois submodelos. O primeiro submodelo representa as características do código e do fluxo de execução de um programa paralelo, incluindo seu mapeamento na topologia do multiprocessador. O segundo submodelo é basicamente um modelo de interferência por memória, que representa a competição dos processadores pelos recursos de memória compartilhada. Um modelo de desempenho de baixo custo computacional é construído para exemplificar a metodologia, sendo validado através de simulações. / [en] In the present work we adress the issue of preformance analysis of parallel scientifc applications. We propose a methodology for building analytic models for parallel programs executing on a shared memory multiprocessor system. The methodology is based on the building and integration of two submodels. The first submodel represents the program code and its execution flow, including distribution of tasks among the processor elements. The second is basically a memory interference model that represents the contention for shared memory resources. A low cost performance model is built to illustrate the use of the methodology, which is validated by simulations.

El rendimiento de los actuales sistemas multiprocesador de memoria compartida depende tanto de la utilización eficiente de todos los componentes del sistema (procesadores, memoria, etc), como de las características del conjunto de aplicaciones a ejecutar. Esta Tesis tiene como principal objetivo mejorar la ejecución de conjuntos de aplicaciones paralelas en sistemas multiprocesador de memoria compartida mediante la utilización de información sobre el rendimiento de las aplicaciones para la planificación de los procesadores.Es una práctica común de los usuarios de un sistema multiprocesador reservar muchos procesadores para ejecutar sus aplicaciones asumiendo que cuantos más procesadores utilicen mejor rendimiento sacarán sus aplicaciones. Sin embargo, normalmente esto no es cierto. Las aplicaciones paralelas tienen diferentes características respecto a su escalabilidad. Su rendimiento depende además de parámetros que sólo son conocidos en tiempo de ejecución, como por ejemplo el conjunto de datos de entrada o la influencia que pueden ejercer determinadas aplicaciones que se ejecutan de forma concurrente.En esta tesis proponemos que el sistema no base sus decisiones solamente en las peticiones de recursos de los usuarios sino que él, dinámicamente, mida el rendimiento que están consiguiendo las aplicaciones y base, o ajuste, sus decisiones teniendo en cuenta esa información.El rendimiento de las aplicaciones paralelas puede ser medido por el sistema de forma dinámica y automática sin introducir una sobrecarga significativa en la ejecución de las aplicaciones. Utilizando esta información, la planificación de procesadores puede ser decidida, o ajustada, siendo mucho más robusta a requerimientos incorrectos por parte de los usuarios, que otras políticas que no consideran este tipo de información. Además de considerar el rendimiento, proponemos imponer una eficiencia objetivo a las aplicaciones paralelas. Esta eficiencia objetivo determinará si la aplicación está consiguiendo un rendimiento aceptable o no, y será usada para ajustar la asignación de procesadores. La eficiencia objetivo de un sistema podrá ser un parámetro ajustable dinámicamente en función del estado del sistema: número de aplicaciones ejecutándose, aplicaciones encoladas, etc.También proponemos coordinar los diferentes niveles de planificación que intervienen en la planificación de procesadores: Nivel librería de usuario, planificador de procesadores (en el S.O), y gestión del sistema de colas. La idea es establecer una interficie entre niveles para enviar y recibir información entre niveles, así como considerar esta información para tomar las decisiones propias de cada nivel.La evaluación de esta Tesis ha sido realizada utilizando un enfoque práctico. Hemos diseñado e implementado un entorno de ejecución completo para ejecutar aplicaciones paralelas que siguen el modelo de programación OpenMP. Hemos introducido nuestras propuestas modificando los tres niveles de planificación mencionados. Los resultados muestran que las ideas propuestas en esta tesis mejoran significativamente el rendimiento del sistema. En aquellos casos en que tanto las aplicaciones como los parámetros del sistema han sido previamente optimizados, las propuestas realizadas introducen una penalización del 5% en el peor de los casos, comparado con el mejor de los resultados obtenidos por otras políticas evaluadas. Sin embargo, en otros casos evaluados, las propuestas realizadas en esta tesis han mejorado el rendimiento del sistema hasta un 400% también comparado con el mejor resultado obtenido por otras políticas evaluadas.Las principales conclusiones que podemos obtener de esta Tesis son las siguientes: - El rendimiento de las aplicaciones paralelas puede ser medido en tiempo de ejecución. Los requisitos para aplicar el mecanismo de medida propuesto en esta Tesis son que las aplicaciones sean maleables y estar en un entorno de ejecución multiprocesador de memoria compartida. - El rendimiento de las aplicaciones paralelas debe ser considerado para decidir la asignación de procesadores a aplicaciones. El sistema debe utilizar la información del rendimiento para auto-ajustar sus decisiones. Además, el sistema debe imponer una eficiencia objetivo para asegurar el uso eficiente de procesadores.- Los diferentes niveles de planificación deben estar coordinados para evitar interferencias entre ellos / The performance of current shared-memory multiprocessor systems depends on both the efficient utilization of all the architectural elements in the system (processors, memory, etc), and the workload characteristics.This Thesis has the main goal of improving the execution of workloads of parallel applications in shared-memory multiprocessor systems by using real performance information in the processor scheduling.It is a typical practice of users in multiprocessor systems to request for a high number of processors assuming that the higher the processor request, the higher the number of processors allocated, and the higher the speedup achieved by their applications. However, this is not true. Parallel applications have different characteristics with respect to their scalability. Their speedup also depends on run-time parameters such as the influence of the rest of running applications.This Thesis proposes that the system should not base its decisions on the users requests only, but the system must decide, or adjust, its decisions based on real performance information calculated at run-time. The performance of parallel applications is information that the system can dynamically measure without introducing a significant penalty in the application execution time. Using this information, the processor allocation can be decided, or modified, being robust to incorrect processor requests given by users. We also propose that the system use a target efficiency to ensure the efficient use of processors. This target efficiency is a system parameter and can be dynamically decided as a function of the characteristics of running applications or the number of queued applications.We also propose to coordinate the different scheduling levels that operate in the processor scheduling: the run-time scheduler, the processor scheduler, and the queueing system. We propose to establish an interface between levels to send and receive information, and to take scheduling decisions considering the information provided by the rest of levels.The evaluation of this Thesis has been done using a practical approach. We have designed and implemented a complete execution environment to execute OpenMP parallel applications. We have introduced our proposals, modifying the three scheduling levels (run-time library, processor scheduler, and queueing system).Results show that the ideas proposed in this Thesis significantly improve the system performance. If the evaluated workload has been previously tuned, in the worst case, we have introduced a slowdown around 5% in the workload execution time compared with the best execution time achieved. However, in some extreme cases, with a workload and a system configuration not previously tuned, we have improved the system performance in a 400%, also compared with the next best time.The main results achieved in this Thesis can be summarized as follows:- The performance of parallel applications can be measured at run-time. The requirements to apply the mechanism proposed in this Thesis are to have malleable applications and shared-memory multiprocessor architectures.- The performance of parallel applications 1must be considered to decide the processor allocation. The system must use this information to self-adjust its decisions based on the achieved performance. Moreover, the system must impose a target efficiency to ensure the efficient use of processors.- The different scheduling levels must be coordinated to avoid interferences between levels.

Submitted by Fabio Sobreira Campos da Costa (fabio.sobreira@ufpe.br) on 2016-03-15T13:58:26Z No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) UFPE-MEI 2015-078 - Maria Cireno Ribeiro Silveira.pdf: 4578273 bytes, checksum: 1c434494e0c03cb02156a37ebfd1c7da (MD5) / Made available in DSpace on 2016-03-15T13:58:26Z (GMT). No. of bitstreams: 2 license_rdf: 1232 bytes, checksum: 66e71c371cc565284e70f40736c94386 (MD5) UFPE-MEI 2015-078 - Maria Cireno Ribeiro Silveira.pdf: 4578273 bytes, checksum: 1c434494e0c03cb02156a37ebfd1c7da (MD5) Previous issue date: 2015-03-09 / O prefetching é uma técnica considerada e ciente para mitigar um problema já conhecido em sistemas computacionais: a diferença entre o desempenho do processador e do acesso à memória. O objetivo do prefetching é aproximar o dado do processador retirando-o da memória e carregando na cache local. Uma vez que o dado seja requisitado pelo processador, ele já estará disponível na cache, reduzindo a taxa de perdas e a penalidade do sistema. Para sistemas multiprocessadores baseados em NoCs a e ciência do prefetching é ainda mais crítica em relação ao desempenho, uma vez que o tempo de acesso ao dado varia dependendo da distância entre processador e memória e do tráfego da rede. Este trabalho propõe um algoritmo de prefetching de dados temporizado, que tem como objetivo minimizar a penalidade dos núcleos através uma solução de prefetching baseada em predição de tempo para sistemas multiprocessadores baseados em NoC. O algoritmo utiliza um processo pró-ativo iniciado pelo servidor para realizar requisições de prefetching baseado no histórico de perdas de cache e informações da NoC. Nos experimentos realizados para 16 núcleos, o algoritmo proposto reduziu a penalidade dos processadores em 53,6% em comparação com o prefetching baseado em eventos (faltas na cache), sendo a maior redução de 29% da penalidade. / The prefetching technique is an e ective approach to mitigate a well-known problem in multi-core processors: the gap between computing and data access performance. The goal of prefetching is to approximate data to the CPU by retrieving the data from the memory and loading it in the cache. When the data is requested by the CPU, it is already available in the cache, reducing the miss rate and penalty. In multiprocessor NoC-based systems the prefetching e ciency is even more critical to system performance, since the access time depends of the distance between the requesting processor and the memory and also of the network tra c. This work proposes a temporized data prefetching algorithm that aims to minimize the penalty of the cores through one prefetching solution based on time prediction for multiprocessor NoC-based systems. The algorithm utilizes a proactive process initiated by the server to request prefetching data based on cache miss history and NoC's information. In the experiments for 16 cores, the proposed algorithm has successfully reduced the processors penalty in 53,6% compared to the event-based prefetching and the best case was a penalty reduction of 29%.

[pt] A interligação de computadores se torna cada vez mais importante, pois possibilita a transferência de dados, assim como o partilhamento de recursos entre eles. O processador de Comunicação, descrito neste trabalho, permite a conexão do sistema multiprocessador Cygnus a uma rede local, que utiliza uma topologia em barra comum, par trançado e um protocolo de acesso ao meio que evita colisões. / [en] Computer interconnections are becoming very important because they allow data exchanging and resources sharing. The Cygnus multiprocessador system to be connected to a local network that utilizes a bus topology, twisted pair and a medium access protocol that avoids collisions.