In this correspondence we present and prove the correctness of an algorithm for reducing the number of synchronized memory references to shared data elements in multiprocessed loops. Optimizing compilers for shared memory multiprocessors can use this algorithm to reduce synchronization overhead. The algorithm has been implemented as a new module in the multiprocessors version of Parafrase, the restructuring system of the University of Illinois. We present a brief discussion of experiments we performed to asses the effectiveness of this algorithm in reducing the synchronization overhead for the 61 subroutines of EISPACK, a package for computing matrix eigenvectors and eigenvalues.

Previous models of program speedup on parallel architectures tend to ignore I/O activity and other important issues. In this paper we derive analytic speedup models including I/O activities. We show that ignoring I/O yields conservative speedup results. We explore the effectiveness of using hardware format conversion units in multiprocessors [33]. We prove that hardware parallel format conversion loses its edge over software parallel format conversion if the ratio of the number of processors to I/O bandwidth increases. For a given number of processors, program speedup is more sensitive to the available I/O bandwidth rather than the format conversion speed. Ninety-one Fortran programs are used in various experiments to verify our models and conclusions. Most of the programs are I/O bound. Our empirical results show that including I/O activity improves the speedup factor for 78 percent of the programs, and 18 percent of the programs are sped up only due to faster I/O activities. For a serial machine, using hardware format conversion units designed in [13] reduces program execution time by an average factor of three. The software format conversion speed used is obtained from direct measurements on an IBM 4341 running CMS and a CDC Cyber 175 running NOS. For multiprocessor systems a factor of eight increase in the processors to I/O bandwidth ratio reduces the effectiveness of hardware format conversion to an average factor of 1.36.

The development of performance prediction tools for highspeed machine organizations has been recognized as a key problem facing the research community in parallel computing [BrAI84].This paper presents a survey of the tools which has been developed for performance prediction of the Cedar multiproce~or supercomputer of the University of Illinois.The system is deterministic, modular, and automatic.The hierarchical organization of the system provides the user with the ability to choose from a set of alternatives for predicting the performance with different levels of accuracy and cost.Using 22 programs, we measure the performance degradation due to conflicts in the shared memory, delay in the Cedar interconnection network, and synchronization overhead.The results confirm that the architecture of Cedar as detailed in [GLYZ84] is balanced.The performance of the Cedar interconnectiou network is very close to a crossbar.Synchronization overhead and shared memory conflicts could degrade performance for some programs considerably.

The effectiveness of multiprocessing a single subroutine in a tightly coupled muir!processor system is highly dependent (among other factors) on the amount of overhead incurred due to synchronized references to shared data items by active processes.In this paper we present a technique to reduce this overhead.This is achieved by reducing the number of synchronized references issued by different processes.We describe the criteria used to identify the variables whose synchronized accesses will eliminate the need to synchronize references to other variables.Our technique can be implemented in optimizing compilers for mnltiprocessor machines.It can also be used when designing parallel algorithms for multiproeessors.We implemented the technique as a pass in the Parafrase system of the University of Illinois.Relevant measurements on all the subroutines of the EISPACK package are reported (61 subroutines).The results show that our technique is quite effective.For subroutines with interprocess communication, it reduced the number of memory references requiring synchronization by 10% in two thirds of these subroutines and by more than 30% for one third of the subroutines.

This paper shows that the working set parameter-real memory and real memory-fault rate anomalies mentioned by Franklin, Graham, and Gupta in [13] do occur in traces generated by real programs. The results of the detailed investigation of this anomalous behavior in four Fortran programs are presented. In some cases a drop of a factor of two in the average real-time memory allotment is observed when the window size is increased. In some instances a bigger real-time memory allotment means an order of magnitude increase in page faults.

It is possible to improve the paging performance of a program by applying transformations to the source program that improve data access locality. We discuss this subject in general terms, including automation of these transformations, and present a number of such transforms. This is followed by experimental results which indicate that these transformations are indeed effective. Use of practical, simple memory management policies like the fixed allocation local lru replacement algorithm leads to average improvements over untransformed programs of a factor of 10 in space-time cost, and a factor of 5 in memory size. Multiprogramming questions are also discussed.