The speculative prefetcher and evaluator processor for pipelined memory hierarchies

We consider extensible processor designs in which the number of gates and the distance that a signal traverses in one clock period are, within a given technology, independent of system size. Consequently such designs scale with system size (in particular, with memory latency) as well as with technological advancement. We assume aggressive memories that are not only hierarchical in nature, but are also heavily pipelined, accepting requests at a constant rate. In such a setting, we propose a processor organization called the Speculative Prefetcher and Evaluator (SPE), which performs memory accesses on speculated addresses and executes operations on speculated operand values. The speculation policy simply assumes the absence of dependences among suitable sets of instructions that are executed concurrently and it is not based on estimating properties of the program under execution. The SPE also supports branch target speculation; however, the performance results of this paper only assume static prediction of loop branches. In order to appraise the performance of the SPE, we evaluate the execution time on various algorithms. First we consider a class of programs, based on loops, which includes a number of interesting algorithms such as matrix addition and multiplication, FFT, bitonic merging and sorting, finite-difference solutions for some PDEs, and digital filtering simulations. Then, we consider a recursive implementation of quicksort. For all these programs, the execution time is proportional to the number of executed instructions, that is, the cycle-per-instruction metric is constant, even if memory latency is pessimistically taken to grow linearly with the physical address. The result for the loop class exploits only the pipelinability of the memory. The result for quicksort also exploits the hierarchical nature of memory.