A co-processor approach for accelerating data-structure intensive algorithms

Many important software applications are dominated by non-trivial serial components: Amdahl´s Law places a hard upper bound on possible speedup that can be achieved for these applications. In this paper, we propose an integrated software/hardware approach for accelerating hard serial bottlenecks in data structure heavy algorithms. The key idea is to overlap the processing of the main algorithmic functions and the data structure related operations. We describe the language, compiler, ISA and architectural support for such data structure co-processing (DSCP), and define a clean interface between the software and the hardware. We perform extensive simulations using the popular C++ STL container classes, as well as a detailed implementation of our approach for Dijkstra´s single-source shortest path algorithm. We find potential for improvements that are well beyond what can be achieved with more conventional parallel computation methods.