Slides available here!


Prof. Babak Falsafi, EPFL, Switzerland


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


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


Babak joined the School of Computer and Communication Sciences at EPFL in 2008. Prior to that, he was a full Professor of Electrical & Computer Engineering and Computer Science at Carnegie Mellon. He is the founding director of the EcoCloud research center pioneering future energy-efficient and environmentally-friendly cloud technologies at EPFL. He has made numerous contributions to computer system design and evaluation including a scalable multiprocessor architecture which laid the foundation for Sun Microsystems family of WildFire and WildCat servers, energy-efficient memory technologies that are cited by an Intel patent and incorporated into IBM BlueGene/P, and computer system simulation sampling methodologies that are in use by AMD and HP for research and product development. His most notable contribution has been to be first to show that contrary to conventional wisdom, multiprocessor memory programming models -- known as memory consistency models -- prevalent in all modern systems since the inception of microprocessors are neither necessary (shown in ISCA'99) nor sufficient (shown in ISCA'07) to achieve high performance. He is a recipient of an NSF CAREER award in 2000, IBM Faculty Partnership Awards in 2001, 2003 and 2004, and an Alfred P. Sloan Research Fellowship in 2004. He is a fellow of IEEE.

* If you wish to modify any information or update your photo, please contact the web