000190306 001__ 190306
000190306 005__ 20190316235740.0
000190306 020__ $$a978-1-4503-2638
000190306 0247_ $$2doi$$a10.1145/2540708.2540748
000190306 037__ $$aCONF
000190306 245__ $$aMeet the Walkers: Accelerating Index Traversals for In-Memory Databases
000190306 269__ $$a2013
000190306 260__ $$c2013
000190306 336__ $$aConference Papers
000190306 520__ $$aThe explosive growth in digital data and its growing role in real-time decision support motivate the design of high-performance database management systems (DBMSs). Meanwhile, slowdown in supply voltage scaling has stymied improvements in core performance and ushered an era of power-limited chips. These developments motivate the design of DBMS accelerators that (a) maximize utility by accelerating the dominant operations, and (b) provide flexibility in the choice of DBMS, data layout, and data types. We study data analytics workloads on contemporary in-memory databases and find hash index lookups to be the largest single contributor to the overall execution time. The critical path in hash index lookups consists of ALU-intensive key hashing followed by pointer chasing through a node list. Based on these observations, we introduce Widx, an on-chip accelerator for database hash index lookups, which achieves both high performance and flexibility by (1) decoupling key hashing from the list traversal, and (2) processing multiple keys in parallel on a set of programmable walker units. Widx reduces design cost and complexity through its tight integration with a conventional core, thus eliminating the need for a dedicated TLB and cache. An evaluation of Widx on a set of modern data analytics workloads (TPC-H, TPC-DS) using full-system simulation shows an average speedup of 3.1x over an aggressive OoO core on bulk hash table operations, while reducing the OoO core energy by 83%.
000190306 6531_ $$aDatacenters
000190306 6531_ $$adatabases
000190306 6531_ $$adark silicon
000190306 6531_ $$aaccelerators
000190306 6531_ $$aenergy efficiency
000190306 700__ $$0243557$$g195561$$aKocberber, Onur
000190306 700__ $$0245686$$g217479$$aGrot, Boris
000190306 700__ $$0245822$$g202826$$aPicorel, Javier
000190306 700__ $$aFalsafi, Babak$$g177958$$0243553
000190306 700__ $$aLim, Kevin
000190306 700__ $$aRanganathan, Parthasarathy
000190306 7112_ $$dDecember 7-11, 2013$$cDavis, CA, USA$$a46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'13)
000190306 773__ $$tProceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture
000190306 8564_ $$uhttps://infoscience.epfl.ch/record/190306/files/walkers_micro13.pdf$$zn/a$$s1484025$$yn/a
000190306 909C0 $$xU11837$$0252231$$pPARSA
000190306 909CO $$qGLOBAL_SET$$pconf$$ooai:infoscience.tind.io:190306$$pIC
000190306 917Z8 $$x195561
000190306 917Z8 $$x195561
000190306 917Z8 $$x195561
000190306 917Z8 $$x195561
000190306 937__ $$aEPFL-CONF-190306
000190306 973__ $$rREVIEWED$$sPUBLISHED$$aEPFL
000190306 980__ $$aCONF