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.

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.

A quorum-quenching approach to investigate the conservation of quorum-sensing-regulated functions within the Burkholderia cepacia complex

Taxonomic studies of the past few years have shown that the Burkholderia cepacia complex, a heterogeneous group of B. cepacia-like organisms, consists of at least nine species. B. cepacia complex strains are ubiquitously distributed in nature and have been used for biocontrol, bioremediation, and plant growth promotion purposes. At the same time, B. cepacia complex strains have emerged as important opportunistic pathogens of humans, particularly those with cystic fibrosis. All B. cepacia complex species investigated thus far use quorum-sensing (QS) systems that rely on N-acylhomoserine lactone (AHL) signal molecules to express certain functions, including the production of extracellular proteases, swarming motility, biofilm formation, and pathogenicity, in a population-density-dependent manner. In this study we constructed a broad-host-range plasmid that allowed the heterologous expression of the Bacillus sp. strain 240B1 AiiA lactonase, which hydrolyzes the lactone ring of various AHL signal molecules, in all described B. cepacia complex species. We show that expression of AiiA abolished or greatly reduced the accumulation of AHL molecules in the culture supernatants of all tested B. cepacia complex strains. Phenotypic characterization of wild-type and transgenic strains revealed that protease production, swarming motility, biofilm formation, and Caenorhabditis elegans killing efficiency was regulated by AHL in the large majority of strains investigated.

Random Regret Minimization: Exploration of a New Choice Model for Environmental and Resource Economics

This paper introduces the discrete choice model-paradigm of Random Regret Minimization (RRM) to the field of environmental and resource economics. The RRM-approach has been very recently developed in the context of travel demand modelling and presents a tractable, regret-based alternative to the dominant choice-modelling paradigm based on Random Utility Maximization-theory (RUM-theory). We highlight how RRM-based models provide closed form, logit-type formulations for choice probabilities that allow for capturing semi-compensatory behaviour and choice set-composition effects while being equally parsimonious as their utilitarian counterparts. Using data from a Stated Choice-experiment aimed at identifying valuations of characteristics of nature parks, we compare RRM-based models and RUM-based models in terms of parameter estimates, goodness of fit, elasticities and consequential policy implications.

Optimal diet choice for large herbivores: an extended contingency model

1. A more general contingency model of optimal diet choice is developed, allowing for simultaneous searching and handling, which extends the theory to include grazing and browsing by large herbivores.</p><p>2. Foraging resolves into three modes: purely encounter-limited, purely handling-limited and mixed-process, in which either a handling-limited prey type is added to an encounter-limited diet, or the diet becomes handling-limited as it expands.</p><p>3. The purely encounter-limited diet is, in general, broader than that predicted by the conventional contingency model,</p><p>4. As the degree of simultaneity of searching and handling increases, the optimal diet expands to the point where it is handling-limited, at which point all inferior prey types are rejected,</p><p>5. Inclusion of a less profitable prey species is not necessarily independent of its encounter rate and the zero-one rule does not necessarily hold: some of the less profitable prey may be included in the optimal diet. This gives an optimal foraging explanation for herbivores' mixed diets.</p><p>6. Rules are shown for calculating the boundary between encounter-limited and handling-limited diets and for predicting the proportion of inferior prey to be included in a two-species diet,</p><p>7. The digestive rate model is modified to include simultaneous searching and handling, showing that the more they overlap, the more the predicted diet-breadth is likely to be reduced.</p>

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.

Exploring Scale Effects of Best/Worst Rank Ordered Choice Data to Estimate Benefits of Tourism in Alpine Grazing Commons

In many environmental valuation applications standard sample sizes for choice modelling surveys are impractical to achieve. One can improve data quality using more in-depth surveys administered to fewer respondents. We report on a study using high quality rank-ordered data elicited with the best-worst approach. The resulting "exploded logit" choice model, estimated on 64 responses per person, was used to study the willingness to pay for external benefits by visitors for policies which maintain the cultural heritage of alpine grazing commons. We find evidence supporting this approach and reasonable estimates of mean WTP, which appear theoretically valid and policy informative. © The Author (2011).