Lookup operations for in-memory databases are heavily memory bound, because they often rely on pointer-chasing linked data structure traversals. They also have many branches that are hard-to-predict due to random key lookups. In this study, we show that although cache misses are the primary bottleneck for these applications, without a method for eliminating the branch mispredictions only a small fraction of the performance benefit is achieved through prefetching alone. We propose the Node Tracker (NT), a novel programmable prefetcher/pre-execution unit that is highly effective in exploiting inter key-lookup parallelism to improve single-thread performance. We extend NT with branch outcome streaming (BOS) to reduce branch mispredictions and show that this achieves an extra 3× speedup. Finally, we evaluate the NT as a pre-execution unit and demonstrate that we can further improve the performance in both single- and multi-threaded execution modes. Our results show that, on average, NT improves single-thread performance by 4.1× when used as a prefetcher; 11.9× as a prefetcher with BOS; 14.9× as a pre-execution unit and 18.8× as a pre-execution unit with BOS. Finally, with 24 cores of the latter version, we achieve a speedup of 203× and 11× over the single-core and 24-core baselines, respectively.

In this paper we investigate and contrast two techniques to maximize the performance of multi-core processors under thermal constraints. The first technique is a distributed dynamic thermal management system that maximizes the total performance without exceeding given thermal constraints. In our scheme, each core adjusts its operating parameters, i.e., frequency and voltage, according to its temperature which is measured using integrated thermal sensors. We propose a novel controller that dynamically adapts the system to simultaneously avoid timing errors and thermal violations. For comparison purposes, we implement a second technique based on a runtime centralized, optimal system that uses combinatorial optimization techniques to calculate the optimal frequencies and voltages for the different cores to maximize the total throughput under thermal constraints. To empirically validate our techniques, we put together an extensive tool chain that incorporates thermal and power consumption simulators to characterize the performance of multi-core processors for a number of configurations ranging from 2 cores at 90 nm to 16 cores at 32 nm. Our results show that both investigated techniques are capable of delivering significant improvements (about 40% for 16 cores) over standard frequency and voltage planning techniques. From the results, we outline the main advantages and disadvantages of both techniques.

High-performance multiprocessor systems built around out-of-order processors with aggressive branch predictors execute many memory references that turn out to be on a mispredicted branch path. Previous work that focused on uniprocessors showed that these wrong-path memory references may pollute the caches by bringing in data that are not needed on the correct execution path and by evicting useful data or instructions. Additionally, they may also increase the amount of cache and memory traffic. On the positive side, however, they may have a prefetching effect for memory references on the correct path. While computer architects have thoroughly studied the impact of wrong-path effects in uniprocessor systems, there is no previous work on its effects in multiprocessor systems. In this paper, we explore the effects of wrong-path memory references on the memory system behavior of shared-memory multiprocessor (SMP) systems for both broadcast and directory-based cache coherence. Our results show that these wrong-path memory references can increase the amount of cache-to-cache transfers by 32%, invalidations by 8% and 20% for broadcast and directory-based SMPs, respectively, and the number of writebacks by up to 67% for both systems. In addition to the extra coherence traffic, wrong-path memory references also increase the number of cache line state transitions by 21% and 32 % for broadcast and directory-based SMPs, respectively. In order to reduce the performance impact of these wrong-path memory references, we introduce two simple mechanisms - filtering wrong-path blocks that are not likely-to-be-used and wrong-path aware cache replacement - that yield speedups of up to 37%.

Uniprocessor designs have always assumed worst-case operating conditions to set the operating clock frequency and, hence, performance. However, much more performance can be obtained under typical operating conditions through experimentation, but such increased frequency operation is subject to the possibility of system failure and, hence, data loss/corruption. Further, mobile CPUs such as those in cell phones/Internet browsers do not adapt to their current surroundings (varying temperature conditions, etc.) so as to increase or decrease operating frequency to maximize performance and/or allow operation under extreme conditions. We present a digital hardware design technique realizing adaptive clock-frequency performance-enhancing digital hardware; the technique can be tuned to approximate performance maximization. The cost is low and the design is straightforward. Experiments are presented evaluating such a design in a pipelined uniprocessor realized in a field programmable gate array (FPGA).

Instruction Level Parallelism (ILP) speedups of an order-of-magnitude or greater may be possible using the techniques described herein. Traditional speculative code execution is the execution of code down one path of a branch (branch prediction) or both paths of a branch (eager execution), before the condition of the branch has been evaluated, thereby executing code ahead of time, and improving performance. A third, optimal, method of speculative execution, Disjoint Eager Execution (DEE), is described herein. A restricted form of DEE, easier to implement than pure DEE, is developed and evaluated. An implementation of both DEE and minimal control dependencies is described. DEE is shown both theoretically and experimentally to yield more parallelism than both branch prediction and eager execution when the same, finite, execution resources are assumed. ILP speedups of factors in the ten's are demonstrated with constrained resources.

It is desirable to achieve high read bandwidths for the processing elements of highly concurrent SISD computers, both while keeping the register and memory write bandwidths low, and while keeping the interconnection networks simple. Solutions to these problems are proposed, simulated, verified, and measured. New techniques called write elimination and write liberation are presented that also greatly reduce the complexity of the data cache. The elimination of addressable hardware registers is also achieved.

Hardware solutions to low-level (semantic) concurrency extraction are presented, focusing on the reduction of both control-flow and dataflow inhibitors of concurrency in general-purpose and scientific instruction streams. In the first model, CONDEL-1, an input code control flow model based on the code's branch domains is used in the algorithm to detect the reduced procedural dependencies in the input code. This model allows branches to execute concurrently. The cost and delay of the model's concurrency hardware are demonstrated to be relatively low, especially for the detection of concurrency beyond branches. The reduced procedural dependence techniques of CONDEL-1 are combined with high-speed reduced data dependency techniques to yield a machine model, CONDEL-2, executing standard sequential code in a manner beyond data-flow. Simulation results are presented and analyzed, showing the model's functionality and performance improvement. The beneficial effects of limited software optimizations are also reviewed.>

Both the efficient execution of branch intensive code and knowing the bounds on the same are important issues in computing in general and supercomputing in particular. In prior work, it has been suggested that the hardware needed to execute code with branches optimally is exponentially dependent on the total number of dynamic branches executed, this number of branches being proportional at least to the number of iterations of the loop. For classes of code taking at least one cycle per iteration to execute, this is not the case. For loops containing one test (normally in the form of a Boolean recurrence of order one), it is shown that the hardware necessary varies from exponential to polynomial in the length of the dependence cycle L, while execution time varies from one time cycle per iteration to less than L time cycles per iteration; the variation depends on specific code dependences. These results bring the eager evaluation of imperative code closer to fruition.>

A reduced set of procedural dependencies is presented which is necessary and sufficient to describe all procedural dependencies in standard imperative codes. Hence, the set is minimal. In conjunction with reduced data dependencies, this set forms a set of minimal semantic dependencies for all traditional code. It is also shown that all forward branches in structured code are procedurally independent. The effects of limited hardware are also addressed. A possible implementation of a machine enforcing just the minimal procedural dependencies is described.>

Both the efficient execution of branch intensive code and knowing the bounds on same are important issues in computing in general and supercomputing in particular. In prior work, it has been suggested, implied, or left as a possible maximum, that the hardware needed to execute code with branches optimally, i.e., oracular performance, is exponentially dependent on the total number of dynamic branches to be executed, this number of branches being proportional at least to the number of iterations of the loop. For classes of code taking at least one cycle per iteration to execute, this is not the case. For loops containing one test (normally in the form of a Boolean recurrence of order 1), it is shown that the hardware necessary varies from exponential to polynomial in the length of the dependency cycle L, while execution time varies from one time cycle per iteration to less than L time cycles per iteration; the variation depends on specific code dependencies.