home · mobile · calendar · colloquia · 2010-2011 · 

Colloquium - Zhang

Advancement of Buffer Management Research and Development in Computer and Data Processing Systems
The Ohio State University

In any memory-capable digital systems, from small cell phones to a huge supercomputers and datacenters, the performance of data buffer management is mainly determined by a replacement algorithm that decides which data block will be evicted when a new data block needs to be allocated as the memory space is full. The replacement concept is simple but its algorithmic optimization and system implementations are challenging and difficult. Since the LRU replacement algorithm was proposed and its approximation was implemented in 1960's, computer scientists and system engineers have made continuous and tireless efforts to improve replacement algorithms analytically and systematically.

Although LRU has several critical flaws, it has been widely used in production systems due to its merits of low complexity and low overhead implementation. After our concentrated efforts for several years, the dominant LRU-like algorithms have been gradually replaced by LIRS-like algorithms in major operating and data database systems, such as BSD, Linux, MySQL, Infinispan, and others. In this talk, I will present how the LIRS algorithm and its variations lay a foundation to address the limits of LRU, and how efficient system implementations turn our research results into reality in production systems. Four connected technical components in the presentation include:

  1. the basics of LIRS,
  2. approximations and variations of LIRS in practice,
  3. lock-contention free implementations, and
  4. a LIRS-like shared cache management in multi-core processors.

Xiaodong Zhang is the Robert M. Critchfield Professor in Engineering and Chair of the Computer Science and Engineering Department at the Ohio State University. His research interests focus on data management in computer, networking and distributed systems. He has made strong efforts to transfer his academic research into advanced technology to impact production systems. He received his PhD in Computer Science from University of Colorado Boulder, where he is a recipient of the Distinguished Engineering Alumni Award in 2011. He is a Fellow of the IEEE.

Hosted by Xiao-Chuan Cai.

Department of Computer Science
University of Colorado Boulder
Boulder, CO 80309-0430 USA
May 5, 2012 (14:13)