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 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.

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.

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.

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.