Search

When a program is loaded into memory for execution the relative position of its basic blocks is crucial, since loading basic blocks that are unlikely to be executed first places them high in the instruction-memory hierarchy only to be dislodged as the execution goes on. In this paper, we study the use of Bayesian networks as models of the input history of a program. The main point is the creation of a probabilistic model that persists as the program is run on different inputs and at each new input refines its own parameters in order to reflect the program's input history more accurately. As the model is thus tuned, it causes basic blocks to be reordered so that, upon arrival of the next input for execution, loading the basic blocks into memory automatically takes into account the input history of the program. We report on extensive experiments, whose results demonstrate the efficacy of the overall approach in progressively lowering the execution times of a program on identical inputs placed randomly in a sequence of varied inputs. We provide results on selected SPEC CINT2000 programs and also evaluate our approach as compared with the gcc level-3 optimization and with Pettis--Hansen reordering.

This paper presents a methodology for designing balanced VLIW architectures. Since we are interested in the architectural aspects of those processors we have developed a framework to evaluate the relationship among the main components of a VLIW machine. Our framework includes the simulator of an actual processor, software tools both to detect the instruction level parallelism of application programs and to generate the parallel object code for each specific machine configuration derived from our basic model of VLIW architecture, and an interpreter which reproduces the behavior of each member of the VLIW family. By interpreting the optimized code derived from a suite of benchmark programs, we have determined the best VLIW configuration for each test program. From these experiments we have discovered which relationship among the machine components should be observed during the specification of a VLIW machine in order to obtain a balanced processor.

This paper presents a study of the impact of conditional branch instructions on the performance of Superscalar processors. By interpreting non-optimised code of a real processor on various configurations derived from a Superscalar architecture model, we have evaluated the execution time percentages in which the associative dispatch algorithm remains idle, waiting for the completion of conditional branch instructions. In addition, we have assessed the volume of instruction level parallelism that can be extracted from application programs if the target machine is equipped with an omniscient branch predictor.

The development of a recent technological product, referred to as Array of Configurable Logic Cells, promotes many opportunities for research and implementation of digital circuits. These arrays include logic cells whose functions can be dynamically specified by the user. The paper describes the main characteristics of configurable cells, and indicates the potential use of these arrays for research and teaching. The paper also shows our experiments in this area, including the design of an alternative array of configurable cells.

The inherent low level parallelism of Super-Scalar architectures plays an important role in the processing power provided by these machines: independent functional units promote opportunities for executing several machine operations simultaneously. From the viewpoint of the hardware designer it is very important to assess the influence of each functional unit, and the way they communicate, on the overall performance of the machine. Particularly, it is highly desirable to determine an upper bound in the number of additional functional units which give significant performance improvement ratios. This work describes experiments that have been carried out to assess the effect of alternative instruction issue mechanisms, multiple functional units, instruction queues, common data bus and other hardware solutions on the performance of Super-Scalar machines. The assessment was obtained by interpreting non optimized object code fo an actual processor on some basic machine models. The paper outline the main aspects of the research, and shows that speed-up ratios of up to 3.35 times were observed during the interpretation of benchmark programs.

The development of Computer Architectures capable of executing several different instructions per clock cycle is a recent trend in processor design. These machines are called Super-Scalar architectures, and they represent an important member of parallel processors: machines incorporating several independent functional devices that can be programmed to operate in parallel. The main problem regarding this class of architectures is how the machine code should be generated in order to exploit their potential parallelism. This work describes some experiments leading to the generation of parallel code for Super-Scalar machines. The experiments have been carried out with traditional concurrency extraction techniques that have been modified in order to satisfy the requirements of some target machines with low level concurrency. The paper outlines the main details of the project, and shows that speed-up ratios ranging from 1.91 up to 2.91 have been obtained by some versions of our algorithm.

Conventional processor can be characterized by the sequential nature in which machine instructions are dispatched: only one instruction is issued each time, and the next one will be started after the conclusion of the current one. However, the machine performance can be significantly improved if the hardware is able to issue several instructions to be executed simultaneously. In this work we describe some experiments that have been carried out to assess the effect of alternative instruction dispatching algorithms on the overall performance of machines comprising several independent functional units. The paper presents the main aspects of the project, and shows that reduction ratios up to 78% in the processing time required by some benchmark programs can be obtained by issuing multiple instructions.

This paper deals with the subject of placing a set of μ-instructions into the control store in such a way that each μ-instruction can reach its successors. A survey of classical techniques for the generation of the address of the next μ-instruction which are employed by existing μ-architectures, together with the restrictions imposed by their designs and implementations, is presented. Next, we formally describe the placement problem, presenting an algorithm that has been developed to place the μ-instructions into the control memory. The algorithm takes into account the capabilities of the hardware mechanism responsible for the generation of the address of the next μ-instruction. Finally, we present the use of the algorithm in performing the placement of a typical μ-program of an existing μ-machine.

A arquitetura WaveScalar é a primeira arquitetura dataflow a apresentar uma interface de memória que mantém a semântica de acessos requerida pelas linguagens imperativas. Um protótipo da arquitetura, em desenvolvimento, permitiria passar de experimentação por simulação para um cenário mais real, com o processador desenvolvido em FPGA. No entanto, este protótipo não é acessível (financeiramente) para qualquer instituição que também queira produzí-lo. Neste trabalho é apresentada a FlowPGA, uma versão reduzida desta arquitetura para ser utilizada com FPGAs com pequeno número de células lógicas. Uma FPGA com 1,5 milhões de gates foi utilizada para implementação. A corretude da implementação foi avaliada com a execução de um programa de multiplicação entre dois números positivos usando sucessivas somas. Os resultados mostram que a arquitetura FlowPGA tem desempenho equivalente ao WaveScalar. Ainda, para avaliar a versatilidade do projeto, a FlowPGA foi modificada para utilizar um sistema de numeração RNS, com esforço de implementação de aproximadamente 20 horas.

This paper presents the specification and implementation of a kernel supporting an environment oriented towards the development and execution of parallel programs written in PASCAL. The host machine is a multiprocessor system with a common bus interconnecting the processing boards, the global memory segment, I/O boards, and other system modules. The processing board structure of the host is similar to the IBM-PC mother board. The environment is based on the TURBO PASCAL which was extended with constructs providing facilities to express and synchronise the parallel execution of processes. The paper describes the main issues regarding the specification and implementation of the kernel, and outlines the use of the environment in the development of parallel programs.

The gap between memory and processor speeds is responsible for the substantial amount of idle time of current processors. To reduce the impact provoked by the so-called "memory gap problem," many, software techniques (e.g., the code layout reorganization) together with hardware mechanisms (cache memory, translation look-aside buffer branch prediction, speculative execution, trace cache, instruction reuse, and so on) have been successfully implemented. In this paper we present some experiments that explain why these mechanisms and techniques are so efficient. We found that only a small fraction of the object code is actually executed: our experiments disclosed that more than 50% of the instructions remain untouched during the whole execution, and the percentages of basic blocks which remain unused are slightly greater. In addition to the usage of instructions and blocks, the paper provides further insights regarding the behavior of application programs, and gives some suggestions for extra performance gains.

We present a study regarding functional unit utilization in a multiple instruction issue machine: a VLIW processor supporting the conditional execution concept. Since all the instructions are conditionally executed, then we can have several instruction scheduling alternatives to fill the fields of the very large instructions. For example, we can have instructions proceeding from different basic blocks sharing the same very large instructions. The paper shows some instruction scheduling schemes, and how they affect the degree of the occupation of the functional units of machine configurations derived from the basic model of conditional execution architecture.

A diferença de velocidade entre a CPU e o sistema de memória tem aumentado continuamente nos últimos anos provocando considerável queda no desempenho dos processadores. Uma alternativa para reduzir essa queda consiste em organizar as instruções do código binário de modo que as falhas na "cache" de instruções sejam também reduzidas. Este artigo descreve a condução de experimentos para determinar, independentemente da entrada de dados, quais foram as instruções que sempre foram executadas e quais as que permanceram intocadas durante a integral execução dos programas inteiros do conjunto SPEC95. Os resultados produzidos por nossos experimentos são valiosos pois eles permitem posicionar inicialmente as instruções de um programa que será executado segundo um esquema que realiza o posicionamento de suas instruções dinamicamente. Dessa forma, a taxa de falhas na "cache" de instruções será reduzida e conseqüentemente, o desempenho do processador será aumentado.

Apesar dos avanços tecnológicos, o número de instruções que são despachadas em paralelo pelos processadores super escalares atuais é ainda muito modesto. As técnicas de predição de desvio e a renomeação de registradores atenuam os efeitos das dependências de controle e de dados, que são os principais obstáculos para o aumento da largura de despacho. Este artigo trata da deteção automática da dependência de dados de instruções em máquinas super escalares de amplo despacho. Nós especificamos três mecanismos capazes de examinar as dependências de dados de um grande número instruções. Cada mecanismo tem uma cache especial que armazena as relações de dependência entre as instruções de um mesmo bloco básico. A suíte SPEC95 foi simulada por máquinas super escalares experimentais equipadas com esses mecanismos. Os resultados dos experimentos mostraram que nossos mecanismos de deteção são mais eficientes do que os existentes: reduzem a complexidade do hardware e tornam viável o despacho de um grande número de instruções em paralelo.

This work presents BBM - a machine oriented towards the execution of basic blocks. Instead of an instruction, the BBM standard unit of processing is the basic block. Many facts regarding the instruction usage of ordinary programs remained unknown for several decades because the traditional processing model, which treats a single instruction as the standard unit, is unable to detect what is happening whith the whole program. With a basic block machine it is possible to have a better insight about the behaviour of the programs. For example, through the experiments involving the execution of the SPECint95 suite on BBM, we found that a very large number of instructions remains unused during the whole execution: in the majority of the programs more than 50% of the instructions remained unused. Disclosed by our Basic Block Machine, this object programs characteristic has many implications on the organization and performance of future processors. Instruction caches and fill units would be much more efficient if the task of mapping instructions onto caches takes in to account the usage and frontiers of the basic blocks. The paper gives an overview of the execution model of our Basic Block Machine, describes the BBM support system, and presents the main results of our experiments.

Durante o projeto de um processador é necessário realizar inúmeras simulações para determinar as melhores opções que serão incorporadas na sua arquitetura. Trace-driven simulation é uma das técnicas mais utilizadas. O trace obtido é processado pelo simulador do modelo de arquitetura em teste e a partir daí são extraídas estatísticas de desempenho do modelo. Para cada modificação na arquitetura investigada, precisamos simular novamente o mesmo conjunto de programas de teste. Neste artigo é apresentado um método alternativo de avaliação que usa diversas amostras, igualmente espaçadas ao longo da execução do programa, para formar um trace reduzido, porém representativo, da execução completa de cada programa de teste. Este trace amostrado é utilizado como entrada pelo simulador de uma arquitetura super escalar, permitindo que as modificações sejam avaliadas em um tempo muito mais reduzido. Experimentos com programas de teste mostraram que com apenas 1% das instruções é possível reproduzir o comportamento da arquitetura super escalar com o trace completo.

Execução especulativa é um dos principais mecanismos encontrados nos atuais processadores super escalares de alto desempenho. A execução especulativa torna mais eficiente a exploração do paralelismo a nível de instrução, antecipando a execução de instruções através das fronteiras dos blocos básicos. Neste trabalho, a execução especulaliva é caracterizada através de um parâmetro arquitetural, a profundidade de especulação. É avaliado o efeito da profundidade de especulação sobre o desempenho e o balanceamento de arquiteturas super escalares. Os resultados indicam ganhos de desempenho de até 60% com profundidades de especulação elevadas. É também mostrado como os recursos da arquitetura devem ser dimensionados de forma que este ganho seja de fato concretizado.

Speculative execution is a key concept to increase the performance of superscalar processors. Given accurate branch prediction mechanisms, the efficiency of speculative execution is mainly determined by the speculation depth. In this work, we evaluate the pressure of speculative execution on the resource requirements of a typical superscalar architecture.

This paper deals with the distribution of functionality among the functional units of a superscalar processor. Starting with configurations including identical functional units capable of executing any instruction, we have assessed the effect provoked by replacing these complex units with specialized units to execute memory access and branch instructions. Our experiments show that the maximum speedup ratios obtained by configurations equipped with eight complex units can also be achieved by machines with the same number of simpler units.

O artigo apresenta o modelo CONDEX: uma arquitetura do tipo VLIW com capacidade de execução condicional. A arquitetura básica é formada por múltiplas unidades funcionais independentes que podem operar concorrentemente, processando diversas instruções procedendo do mesmo programa de aplicação. Além da especificação do modelo de arquitetura, o artigo descreve algumas técnicas para geração de código paralelo para configurações derivadas do modelo CONDEX e os experimentos para avaliar a qualidade desse código.

This paper describes the design and implementation of a virtual machine oriented towards the execution of concurrent programs written in the high level language EDISON defined by P. Brinch Hansen in [1] and [2]. The target machine specification includes primitives reflecting typical constructs of source programs. For instance, there are primitives realizing directly those source operations involving array type and set type variables; instructions to create, synchronize, and to kill processes etc. As required by the source language, the virtual machine implements the concept of Conditional Critical Regions [3]. EDISON programs are translated to target code before their actual interpretation. Some virtual machine interpreters were implemented: first we developed two interpreters in high level language; next an interpreter in ASSEMBLY language; and finally we implemented a μ-programmed version of the virtual machine. Some performance figures of the interpretation are included in the appendix.

In an earlier work we have introduced an Architecture Description Language (ADL for short) and its support system implemented in a machine-independent fashion [5]. This system provides facilities for teaching and research in computer architecture: target machines described in ADL are fed into the support system, and the corresponding interpreter programs are automatically generated. These programs reproduced the run-time environment of the target, as specified by the ADL description, including the interpretation of the target code. This paper presents a brief review of the language and the implementation of its support system. Next, the new constructs that have been incorporated into ADL to give an extended version (ADL-X) are described. Through these mechanisms, designers can specify and synchronize target machine activities occuring in parallel. Finally, we show how the new support system is being implemented, and give a description of a pipeline machine, using the new language features.

This paper presents the specification and implementation of a kernel supporting an environment oriented towards the development and execution of concurrent programs written in an extension of PASCAL. The environment is based on the TURBO PASCAL which was extended with constructs providing mechanisms to express and synchronize the concurrent execution of processes. In addition to the specification and implementation details of the kernel, the paper also outlines the use of the environment in the development of parallel programs, and describes the current stage of the work which should lead to the migration of the environment to a parallel host machine.

The specification and implementation of a machine oriented to the execution of programs written in applicative languages is presented. Source programs are translated into a intermediate form which is interpreted by the target architecture: a normal graph reduction machine based on combinators. Some interpreters for this reduction machine were implemented. In this way, we developed interpreters in the C language, in ASSEMBLY language, and finally a microprogrammed version of the target architecture. The paper shows the relevant aspects of the reduction machine design and the current stage of the project.

This paper describes the design and realization of MPH, a Hybrid Parallel Machine, which is intended to be used as a tool for research in parallel computing. MPH is a multiprocessor system whose processors are arranged according to a hypercubic topology but with interprocessor communication being realized through memory segments which are shared by each pair of processors. The resulting machine incorporates the characteristics of both loosely and tightly coupled architectures, hence its hybrid nature. In addition to the design and implementation issues, the paper also describes the research potential of MPH, and the current stage of the work.

Este trabalho contém a apresentação de um projeto cujo objetivo primário é a investigação da compilação e uso de Prolog Concorrente. O projeto apresenta problemas em diversas disciplinas, incluindo Programação Lógica e Processamento Distribuído. A intenção é que seja utilizada uma arquitetura em hipercubo baseada no microprocessador Transputer e na linguagem OCCAM. Problemas a serem investigados incluem a compilação eficiente de programas em Prolog Concorrente e o balanceamento de carga em sistemas distribuídos.