Repository logo

Infoscience

  • English
  • French
Log In
Logo EPFL, École polytechnique fédérale de Lausanne

Infoscience

  • English
  • French
Log In
  1. Home
  2. Academic and Research Output
  3. Conferences, Workshops, Symposiums, and Seminars
  4. Meet the Walkers: Accelerating Index Traversals for In-Memory Databases
 
conference paper

Meet the Walkers: Accelerating Index Traversals for In-Memory Databases

Kocberber, Onur  
•
Grot, Boris  
•
Picorel, Javier  
Show more
2013
Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture
46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'13)

The 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%.

  • Files
  • Details
  • Metrics
Type
conference paper
DOI
10.1145/2540708.2540748
Author(s)
Kocberber, Onur  
Grot, Boris  
Picorel, Javier  
Falsafi, Babak  
Lim, Kevin
Ranganathan, Parthasarathy
Date Issued

2013

Published in
Proceedings of the 46th Annual IEEE/ACM International Symposium on Microarchitecture
ISBN of the book

978-1-4503-2638

Subjects

Datacenters

•

databases

•

dark silicon

•

accelerators

•

energy efficiency

Editorial or Peer reviewed

REVIEWED

Written at

EPFL

EPFL units
PARSA  
Event nameEvent placeEvent date
46th Annual IEEE/ACM International Symposium on Microarchitecture (MICRO'13)

Davis, CA, USA

December 7-11, 2013

Available on Infoscience
November 5, 2013
Use this identifier to reference this record
https://infoscience.epfl.ch/handle/20.500.14299/96752
Logo EPFL, École polytechnique fédérale de Lausanne
  • Contact
  • infoscience@epfl.ch

  • Follow us on Facebook
  • Follow us on Instagram
  • Follow us on LinkedIn
  • Follow us on X
  • Follow us on Youtube
AccessibilityLegal noticePrivacy policyCookie settingsEnd User AgreementGet helpFeedback

Infoscience is a service managed and provided by the Library and IT Services of EPFL. © EPFL, tous droits réservés