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

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.

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.