Private caches are critical components in high per formance multiprocessor systems. However, it has been found that, when executing a parallel program, individual processors are very difficult to attain high cache hit ratio from one program section to another; therefore sophisti cated software coherence schemes are not cost effective. In this study, trace-driven simulation has been used to evaluate various less sophisticated compiler and software techniques which can enhance this inter-section locality in parallel executions. We found that the locality can be substantially im proved through the following ways of altering the sched uling of iterations in parallel DO loops among the executing processors: i) assignment of iterations in chunks, ii) reversed execution of parallel loops, and Hi) interchange inner and outer loops. These can be done manually by a programmer or automatically by a parallelizing compiler. Moreover, we also propose a software coherence scheme which can attain the maxi mum inter-section locality for read-only shared data.

Long branch delay is a well-known problem in today's high performance superscalar and supetpipeline processor designs.A common technique used to alleviate this problem is to predict the direction of branches during the instruction fetch.Counter-based branch prediction, in particular, has been reported as an effective scheme for predicting the direction of branches.However, its accuracy is generally limited by branches whose future behavior is also dependent upon the history of other branches.To enhance branch prediction accuracy with a minimum increase in hardware COSLwe propose a correlation-based scheme and show how the prediction accuracy can be improved by incorporating information, not only from the history of a specific brsncb but also from the history of other branches.Specifically, we use the information provided by a proper subhistory of a branch to predict the outcome of that branch.The proper subhistory is selected based on the outcomes of the most recently executed M branches.The new scheme is evaluated using traces collected from running the SPEC benchmark suite on an IBM RISC System/6000 workstation.The results show that, as compared with the 2-bit counter-based prediction scheme, the correlation-based branch prediction achieves up to 11 ~0 additional accuracy at the extra hardware cost of one shift register.The results also show that the accuracy of the new scheme surpasses that of the counter-based branch predction at saturation.

An instruction-level simulator for IBM 3090 with VF (vector facility) has been developed for studying the performance of vector processors and their memory hierarchies. Results of a study of the locality of several large scientific applications are presented. The cache miss ratios of vectorized applications are found to be almost equal to those of their original scalar executions. Moreover, both the spatial and temporal locality of these applications (in scalar and vector executions) are strong enough to show a sufficiently high hit ratio on conventional cache structures.>

The performance of set associative caches is analyzed. The method used is to group the cache lines into regions according to their positions in the replacement stacks of a cache, and then to observe how the memory access of a CPU is distributed over these regions. Results from the preserved CPU traces show that the memory accesses are heavily concentrated on the most recently used (MRU) region in the cache. The concept of MRU change is introduced; the idea is to use the event that the CPU accesses a non-MRU line to approximate the time the CPU is changing its working set. The concept is shown to be useful in many aspects of cache design and performance evaluation, such as comparison of various replacement algorithms, improvement of prefetch algorithms, and speedup of cache simulation.>

An innovative cache accessing scheme based on high MRU (most recently used) hit ratio [1] is proposed for the design of a one-cycle cache in a CMOS implementation of System/370. It is shown that with this scheme the cache access time is reduced by 30 ~ 35% and the performance is within 4% of a true one-cycle cache. This cache scheme is proposed to be used in a VLSI System/370, which is organized to achieve high performance by taking advantage of the performance and integration level of an advanced CMOS technology with half-micron channel length [2]. Decisions on the system partition are based on technology limitations, performance considerations and future extendability. Design decisions on various aspects of the cache organization are based on trace simulations for both UP (uniprocessor) and MP (multiprocessor) configurations.

A parallel simulator, PSIMUL, has been used to collect information on the memory access patterns and synchronization overheads of several scientific applications. The parallel simulation method we use is very efficient and it allows us to simulate execution of an entire application program, amounting to hundreds of millions of instructions. We present our measurements on the memory access characteristics of these applications; particularly our observations on shared and private data, their frequency of access and locality. We have found that, even though the shared data comprise the largest portion of the data in the application program, on the average a small fraction of the memory references are to shared data. The low averages do not preclude bursts of traffic to shared memory nor does it rule out positive benefits from caching shared data. We also discuss issues of synchronization overheads and their effect on performance.

We study the comparison between an m-processor (multiprocessor) system and a single-processor system whose processor is m times as fast as any in the multiprocessor system. The expected superiority of the single-processor system is measured in terms of mean and maximum flow times, using both combinatorial and probabilistic models.

In this paper several results are proven showing a correspondence between problems involving task systems with single-stage processors and similar ones using pipelined processors. For example, an optimal schedule for a task system with arbitrary precedence constraints using a single pipelined processor with two stages is found by the familiar Coffman–Graham algorithm for a system with two single-stage processors. Precedence constraints in the form of inforests, out-forests, and directed acyclic graphs are examined. Task systems with release times and deadlines for each task are also considered.