On generating set index functions for randomized caches

Caches hide the growing latency of accesses to the main memory from the processor by storing the most recently used data on-chip. To limit the search time through the caches, they are organized in a direct mapped or set-associative way. Such an organization introduces many conflict misses that hamper performance. This paper studies randomizing set index functions, a technique to place the data in the cache in such a way that conflict misses are avoided. The performance of such a randomized cache strongly depends on the randomization function. This paper discusses a methodology to generate randomization functions that perform well over a broad range of benchmarks. The methodology uses profiling information to predict the conflict miss rate of randomization functions. Then, using this information, a search algorithm finds the best randomization function. Due to implementation issues, it is preferable to use a randomization function that is extremely simple and can be evaluated in little time. For these reasons, we use randomization functions where each randomized address bit is computed as the XOR of a subset of the original address bits. These functions are chosen such that they operate on as few address bits as possible and have few inputs to each XOR. This paper shows that to index a 2(m)-set cache, it suffices to randomize m+2 or m+3 address bits and to limit the number of inputs to each XOR to 2 bits to obtain the full potential of randomization. Furthermore, it is shown that the randomization function that we generate for one set of benchmarks also works well for an entirely different set of benchmarks. Using the described methodology, it is possible to reduce the implementation cost of randomization functions with only an insignificant loss in conflict reduction.

Highly accurate and efficient evaluation of randomising set index functions

Randomising set index functions can reduce the number of conflict misses in data caches by spreading the cache blocks uniformly over all sets. Typically, the randomisation functions compute the exclusive ors of several address bits. Not all randomising set index functions perform equally well, which calls for the evaluation of many set index functions. This paper discusses and improves a technique that tackles this problem by predicting the miss rate incurred by a randomisation function, based on profiling information. A new way of looking at randomisation functions is used, namely the null space of the randomisation function. The members of the null space describe pairs of cache blocks that are mapped to the same set. This paper presents an analytical model of the error made by the technique and uses this to propose several optimisations to the technique. The technique is then applied to generate a conflict-free randomisation function for the SPEC benchmarks. (C) 2003 Elsevier Science B.V. All rights reserved.

Application-Specific Instruction Set Processor for SoC implementation of Modern Signal Processing Algorithms

A novel application-specific instruction set processor (ASIP) for use in the construction of modern signal processing systems is presented. This is a flexible device that can be used in the construction of array processor systems for the real-time implementation of functions such as singular-value decomposition (SVD) and QR decomposition (QRD), as well as other important matrix computations. It uses a coordinate rotation digital computer (CORDIC) module to perform arithmetic operations and several approaches are adopted to achieve high performance including pipelining of the micro-rotations, the use of parallel instructions and a dual-bus architecture. In addition, a novel method for scale factor correction is presented which only needs to be applied once at the end of the computation. This also reduces computation time and enhances performance. Methods are described which allow this processor to be used in reduced dimension (i.e., folded) array processor structures that allow tradeoffs between hardware and performance. The net result is a flexible matrix computational processing element (PE) whose functionality can be changed under program control for use in a wider range of scenarios than previous work. Details are presented of the results of a design study, which considers the application of this decomposition PE architecture in a combined SVD/QRD system and demonstrates that a combination of high performance and efficient silicon implementation are achievable. © 2005 IEEE.

On effective linearly ordered sets of comparison functions

Both the existence and the non-existence of a linearly ordered (by certain natural order relations) effective set of comparison functions (=dense comparison classes) are compatible with the ZFC axioms of set theory.

On the set of hypercyclic vectors for the differentiation

Let D be the differentiation operator Df = f' acting on the Fréchet space H of all entire functions in one variable with the standard (compact-open) topology. It is known since the 1950’s that the set H(D) of hypercyclic vectors for the operator D is non-empty. We treat two questions raised by Aron, Conejero, Peris and Seoane-Sepúlveda whether the set H(D) contains (up to the zero function) a non-trivial subalgebra of H or an infinite-dimensional closed linear subspace of H. In the present article both questions are answered affirmatively.

XOR-based hash functions

Bank conflicts can severely reduce the bandwidth of an interleaved multibank memory and conflict misses increase the miss rate of a cache or a predictor. Both occurrences are manifestations of the same problem: Objects which should be mapped to different indices are accidentally mapped to the same index. Suitable chosen hash functions can avoid conflicts in each of these situations by mapping the most frequently occurring patterns conflict-free. A particularly interesting class of hash functions are the XOR-based hash functions, which compute each set index bit as the exclusive-or of a subset of the address bits. When implementing an XOR-based hash function, it is extremely important to understand what patterns are mapped conflict-free and how a hash function can be constructed to map the most frequently occurring patterns without conflicts. Hereto, this paper presents two ways to reason about hash functions: by their null space and by their column space. The null space helps to quickly determine whether a pattern is mapped conflict-free. The column space is more useful for other purposes, e. g., to reduce the fan-in of the XOR-gates without introducing conflicts or to evaluate interbank dispersion in skewed-associative caches. Examples illustrate how these ideas can be applied to construct conflict-free hash functions.

Polynomial Functions and the Riesz Interpolation Property

Building on a proof by D. Handelman of a generalisation of an example due to L. Fuchs, we show that the space of real-valued polynomials on a non-empty set X of reals has the Riesz Interpolation Property if and only if X is bounded.

Modulational instability in asymmetric coupled wave functions

The evolution of the amplitude of two nonlinearly interacting waves is considered, via a set of coupled nonlinear Schrödinger-type equations. The dynamical profile is determined by the wave dispersion laws (i.e. the group velocities and the group velocity dispersion terms) and the nonlinearity and coupling coefficients, on which no assumption is made. A generalized dispersion relation is obtained, relating the frequency and wave-number of a small perturbation around a coupled monochromatic (Stokes') wave solution. Explicitly stability criteria are obtained. The analysis reveals a number of possibilities. Two (individually) stable systems may be destabilized due to coupling. Unstable systems may, when coupled, present an enhanced instability growth rate, for an extended wave number range of values. Distinct unstable wavenumber windows may arise simultaneously.

Improving multi-site benefit functions via Bayesian model averaging: A new approach to benefit transfer

A benefit function transfer obtains estimates of willingness-to-pay (WTP) for the evaluation of a given policy at a site by combining existing information from different study sites. This has the advantage that more efficient estimates are obtained, but it relies on the assumption that the heterogeneity between sites is appropriately captured in the benefit transfer model. A more expensive alternative to estimate WTP is to analyze only data from the policy site in question while ignoring information from other sites. We make use of the fact that these two choices can be viewed as a model selection problem and extend the set of models to allow for the hypothesis that the benefit function is only applicable to a subset of sites. We show how Bayesian model averaging (BMA) techniques can be used to optimally combine information from all models. The Bayesian algorithm searches for the set of sites that can form the basis for estimating a benefit function and reveals whether such information can be transferred to new sites for which only a small data set is available. We illustrate the method with a sample of 42 forests from U.K. and Ireland. We find that BMA benefit function transfer produces reliable estimates and can increase about 8 times the information content of a small sample when the forest is 'poolable'. © 2008 Elsevier Inc. All rights reserved.

MAPPING SYSTEM LEVEL FUNCTIONS ON TO BIT LEVEL SYSTOLIC ARRAYS.

Bit-level systolic-array structures for computing sums of products are studied in detail. It is shown that these can be subdivided into two classes and that within each class architectures can be described in terms of a set of constraint equations. It is further demonstrated that high-performance system-level functions with attractive VLSI properties can be constructed by matching data-flow geometries in bit-level and word-level architectures.

STO and GTO field-induced polarization functions for H to Kr

Field-induced polarization (FIP) functions were proposed over two decades ago to improve the accuracy of calculated response properties, and the FIP functions in GTO form for H and C to F were tested on small molecules, with encouraging results. The concept of FIP,is now extended to all atoms up to Kr. New simplifying approximations for the description of asymptotic highest occupied atomic orbitals. (HOAOs) are introduced in this study. They provide the basis for STO and GTO exponents of a complete set of FIP functions from H to Kr, which are both listed for the convenience of the users. Tests on the polarizabilities of a series of atoms and molecules demonstrate that addition of the FIP basis functions to a series' of standard basis sets drastically improves the performance of all these basis sets compared to converged results. Moreover, the byproduct of this study (approximate asymptotic HOAOs) provides information for the construction of accurate basis sets for long-range ground state properties. (C) 2003 Wiley Periodicals, Inc.