The complex and powerful out-of-order issue logic dismisses the repetitive nature of the code, unlike what caches or branch predictors do. We show that 90% of the cycles, the group of instructions selected by the issue logic belongs to just 13% of the total different groups issued: the issue logic of an out-of-order processor is constantly re-discovering what it has already found. To benefit from the repetitive nature of instruction issue, we move the scheduling logic after the commit stage, out of the critical path of execution. The schedules created there are cached and reused to feed a simple in-order issue logic, that could result in a higher frequency design. We present the complete design of our ReLaSch processor, that achieves the same average IPC than a conventional out-of-order processor, and a 1.56 speed-up over the IPC of an in-order processor. We actually surpass the out-of-order IPC in 23 out of 40 SPEC benchmarks, mainly because the broader vision of the code after the commit stage allows creating better schedules.

Parallel in-memory 64-bit sorting is an important problem in Database Management Systems and other applications such as Internet Search Engines and Data Mining Tools.

The exploitation of data locality in parallel computers is paramount to reduce the memory traffic and communication among processing nodes. We focus on the exploitation of locality by Parallel Radix sort. The original Parallel Radix sort has several communication steps in which one sorting key may have to visit several processing nodes. In response to this, we propose a reorganization of Radix sort that leads to a highly local version of the algorithm at a very low cost. As a key feature, our algorithm performs one only communication step, forcing keys to move at most once between processing nodes. Also, our algorithm reduces the amount of data communicated. Finally, the new algorithm achieves a good load balance which makes it insensitive to skewed data distributions. We call the new version of Parallel Radix sort that combines locality and load balance, Communication and Cache Conscious Radix sort (C 3 -Radix sort). Our results on 16 processors of the SGI O2000 show that C 3 -R...

Accurate branch prediction is essential for obtaining high performance in pipelined superscalar processors that execute instructions speculatively. Some of the best current predictors combine a part of the branch address with a fixed amount of global history of branch outcomes in order to make a prediction. These predictors cannot perform uniformly well across all workloads because the best amount of history to be used depends on the code, the input data and the frequency of context switches. Consequently, all predictors that use a fixed history length are therefore unable to perform up to their maximum potential. We introduce a method-called DHLF-that dynamically determines the optimum history length during execution, adapting to the specific requirements of any code, input data and system workload. Our proposal adds an extra level of adaptivity to two-level adaptive branch predictors. The DHLF method can be applied to any one of the predictors that combine global branch history with the branch address. We apply the DHLF method to gshare (dhlf-gshare) and obtain near-optimal results for all SPECint95 benchmarks, with and without context switches. Some results are also presented for gskewed (dhlf-gskewed), confirming that other predictors can benefit from our proposal.

As the number of instructions executed in parallel increases, superscalar processors will require higher bandwidth from data caches.Because of the high cost of true multi-ported caches, alternative cache designs must be evaluated.The purpose of this study is to examine the data cache bandwidth requirements of high-degree superscalar processors, and investigate alternative solutions.The designs studied range from classic solutions like multi-banked caches to more complex solutions recently proposed in the literature.The performance tradeoffs of these different cache designs are examined in details.Then, using a chip area cost model, all solutions are compared with respect to both cost and performance.While many cache designs seem capable of achieving high cache bandwidth, the best cost/performance t,radeoff varies significantly depending on the dedicated area cost, ranging from multi-banked cache designs to hybrid multi-banked/multi-ported caches or even true multi-ported caches.For instance, we find that an 8-bank cache with minor optimizations perform 10% better than a true a-port cache at half the cost, or that a 4-bank 2 ports per bank cache performs better than a true 4-port cache and uses 45% less chip area.

Translation look-aside buffers (TLBs) are small caches to speed-up address translation in processors with virtual memory.This paper considers two issues: (1) a comparison of the power consumption of fully-associative, set-associative, and direct mapped TLBs for the same miss rate and (2) the proposal of modifications of the basic cells and of the structure of set-associative TLBs to reduce the power.The power evaluation is done using a model and the miss rates are obtained from simulations of the SPEC92 benchmark.With respect to ( 1) we conclude that for small TLBs (high miss rates) fully-associative TLBs consume less power but for larger TLBs (low miss rates) set-associative TLBs are better.Moreover, the proposed modifications produce significant reductions in power consumption.Our evaluations show a reduction of 40 to 60% compared to the best traditional TLB.The proposed TLB implementation produces an increase in delay and in area.However, these increases are tolerable because the cycle time is determined by the slower cache and because the TLB area corresponds to only a small portion of the chip area.196 __ __, ~-~-,-, 'II -F 'r-pT-yy-,~';ri '-I:.* : ,< 7,

Much effort has been directed towards obtaining near peak performance for linear algebra operations on current high performance workstations. The large amounts of data accesses however, make performance highly dependent on the behavior of the memory hierarchy. Techniques such as Multilevel Blocking (Tiling), Data Precopying, Software Pipelining and Software Prefetching have been applied in order to improve performance. Nevertheless, to our knowledge, no other work has been done considering the relation between these techniques when applied together. In this paper we analyze the behavior of matrix multiplication algorithms for large matrices on a superscalar and superpipelined processor with a multilevel memory hierarchy when these techniques are applied together. We study and model the performance and limitations of different codes. We also compare two different approaches to data prefetching, binding versus non-binding, and find the latter remarkably more effective than the former due...

In this paper we analyze the use of Blocklng (tiling), Data Precopying and Software Pipelining to improve the performance of sparse matrix computations on superscalar workstations.In particular, we analyze the case of the Sparse Matrix by dense Matrix operation.The analysis focusses on the practical aspects that can be observed when programming such problem on present workstations with several memory levels.The problem is studied on the Alpha 21064 based workstation DEC 3000/800.Simulations of the memory hierarchyare also used to understand the behaviour of the algorithms.The results obtained show that there is a clear difference between the dense case and the sparse case in terms of the compromises to be adopted to optimize the algorithms.The analysis can be of interest to numerical library and compiler designers.1

The difference-bit cache is a two-way set-associative cache with an access time that is smaller than that of a conventional one and close or equal to that of a direct-mapped cache. This is achieved by noticing that the two tags for a set have to differ at least by one bit and by using this bit to select the way. In contrast with previous approaches that predict the way and have two types of hits (primary of one cycle and secondary of two to four cycles), all hits of the difference-bit cache are of one cycle. The evaluation of the access time of our cache organization has been performed using a recently proposed on-chip cache access model.

In this paper, a review of methods for the solution of general bidiagonal systems of equations is done. Gaussian Elimination, the r-Cyclic Reduction family of algorithms and the Divide and Conquer algorithm are analyzed. A unified view of the three types of methods is proposed. The work is focussed on two basic aspects of the methods: parallelism and grain. The influence of the architecture of the target computer on the parallelism and grain of the methods is evaluated. In particular, vector processors are analyzed as target architecture and one vector processor of the Convex C-3480 is taken as a case study. For the special case of Divide and Conquer, a model is made in order to tune parallelism and grain for its optimal execution. Two conclusions can be outlined from the analysis of the methods. First, the execution time of the r-Cyclic Reduction family of algorithms is lower as r grows reaching a lower significative bound in r=9. This means that the classic use of Cyclic Reduction on vector computers is outdated from now on. Second, the higher rank versions of the r-Cyclic Reduction family of algorithms and the optimized version of Divide and Conquer behave similarly on vector computers.

Multilevel block algorithms exploit the data locality in linear algebra operations when executed in machines with several levels in the memory hierarchy. It is shown that the family we call Multilevel Orthogonal Block (MOB) algorithms is optimal and easy to design and that using the multilevel approach produces significant performance improvements. The effect of interference in the cache, of the TLB misses, and of page faults are also considered. The multilevel block algorithms are evaluated analytically for an ideal memory system with M cache levels without interferences. Moreover, experimental results of the MOB forms in some present high performance workstations are presented.

Address transformation schemes, such as skewing and linear transformations, have been proposed to achieve conflict-free vector access for some strides in vector processors with multi-module memories. In this paper, we extend these schemes to achieve this conflict-free access for a larger number of strides. The basic idea is to perform an out-of-order access to vectors of fixed length, equal to that of the vector registers of the processor. Both matched and unmatched memories are considered: we show that the number of strides is even larger for the latter case. The hardware for address calculations and access control is described and shown to be of similar complexity as that required for access in order.

A systematic method to map systolic problems onto multicomputers is presented. A systolic problem is a problem for which it is possible to design a systolic algorithm. This method selects and transforms the systolic algorithm into a parallel algorithm with high granularity. The communications requirements are reduced and the performance can be increased. The proposed scheme requires a classification of dependences and it is based on the interleaved execution of several partitions of the systolic algorithm. The code to be executed in a processing element of the multicomputer system is obtained through application of the proposed systematic transformations to the original sequential code. By applying this method to algebraic path problem (APP), the authors illustrate the main features, and several performance measures for a torus of transputers system are presented, considering the various algorithms which are unified by the APP.>

The authors present a method to implement systolic algorithms (SAs) using pipelined functional units (PFUs). This kind of unit makes it possible to improve the throughput of a processor because of the possibility of initiating a new operation before the previous one has been completed. The method permits transformation of a SA so that it can be efficiently executed using PFUs. The method is based on two temporal transformations (slowdown and retiming) and one spatial transformation (coalescing). The temporal transformations permit the modification of the SA in such a way that dependences established by the PFU are preserved. The spatial transformation improves the hardware utilization. The method was applied to 1-D SAs with data contraflow. To demonstrate the effectiveness of the method, the authors describe an efficient implementation of a non-time-homogeneous SA with data contraflow for QR decomposition.>

In this paper we propose a methodology to adapt Systolic Algorithms to the hardware selected for their implementation. Systolic Algorithms obtained can be efficiently implemented using Pipelined Functional Units. The methodology is based on two transformation rules. These rules are applied to an initial Systolic Algorithm, possibly obtained through one of the design methodologies proposed by other authors. Parameters for these transformations are obtained from the specification of the hardware to be used. The methodology has been particularized in the case of one-dimensional Systolic Algorithms with data contraflow.

A methodology to transform dense to band matrices is presented in this paper. This transformation, is accomplished by triangular blocks partitioning, and allows the implementation of solutions to problems with any given size, by means of contraflow systolic arrays, originally proposed by H.T. Kung. Matrix-vector and matrix-matrix multiplications are the operations considered here. The proposed transformations allow the optimal utilization of processing elements (PEs) of the systolic array when dense matrix are operated. Every computation is made inside the array by using adequate feedback. The feedback delay time depends only on the systolic array size.