Award Abstract #0534389
Cache-Aware Database Systems on Modern Multithreading Processors

NSF Org:	IIS Division of Information & Intelligent Systems
Initial Amendment Date:	December 9, 2005
Latest Amendment Date:	November 6, 2007
Award Number:	0534389
Award Instrument:	Continuing grant
Program Manager:	Frank Olken IIS Division of Information & Intelligent Systems CSE Directorate for Computer & Information Science & Engineering
Start Date:	January 1, 2006
Expires:	December 31, 2010 (Estimated)
Awarded Amount to Date:	$380000
Investigator(s):	Kenneth Ross kar@cs.columbia.edu (Principal Investigator)
Sponsor:	Columbia University 2960 Broadway NEW YORK, NY 10027 212/854-6851
NSF Program(s):	DATA MANAGEMENT SYSTEMS, INFO INTEGRATION & INFORMATICS
Field Application(s):	0104000 Information Systems
Program Reference Code(s):	HPCC, 9218
Program Element Code(s):	7485, 7364

ABSTRACT

IIS-0534389

Kenneth A. Ross <kar@cs.columbia.edu>

Columbia University

Cache-Aware Database Systems on Modern Multithreading Processors

This project studies how to best utilize the resources available in

modern processors in the development of database system software. A

primary objective is avoiding cache interference between threads in

multithreaded and multi-core processors, so that performance scales

well as the number of cores/threads increases. A variety of

techniques are considered, including multi-threaded algorithm design,

threads explicitly devoted to resource management, and scheduling

algorithms that are aware of thread interference patterns.

Simulations and implementations on real hardware are used to measure

the effectiveness of each approach.

The project will result in the development of algorithms designed for

the global management (and minimization) of processor- and

memory-related delays in database systems. Based on preliminary

experiments, overall improvements in throughput of thirty to fifty

percent are expected. A database prototype will be developed, and

made available for download over the web.

This project has relevance to commercial and public-domain database

systems. Performance improvements would enhance the experience of

database system users, and reduce hardware requirements for a given

level of performance. This project makes significant contributions to

education through reseach projects, a new advanced course, and by

providing a prototype system for use by others.

Project-related information can be found at

http://www.cs.columbia.edu/~kar/fastqueryproj.html

PUBLICATIONS PRODUCED AS A RESULT OF THIS RESEARCH

Cieslewicz, John; Ross, Kenneth. "Data Partitioning on Chip Multiprocessors," DaMoN Workshop, 2008, p. 25.

Cieslewicz, John; Ross, Kenneth. "Database Optimizations for Modern Hardware," Proceedings of the IEEE, v.96(5), 2008, p. 863.

J. Cieslewicz, J. Berry, B. Hendrickson, K.A. Ross. "Realizing Parallelism in Database Operations: Insights from a Massively Multithreaded Architecture," Proceedings of the 2006 Workshop on Data Management on New Hardware (DaMoN), 2006, p. 4.

J. Cieslewicz, K. A. Ross. "Adaptive Aggregation on Chip Multiprocessors," International Conference on Very Large Databases, 2007, p. 339.

J. Cieslewicz, K. A. Ross, I. Giannakakis. "Parallel Buffers for Chip Multiprocessors," SIGMOD Workshop on Data Management on New Hardware, 2007.

K. A. Ross. "On the Adequacy of Partial Orders for Preference Composition," ICDE Workshop on Ranking in Databases, 2007.

K. A. Ross, P. J. Stuckey, A. Marian. "Practical Preference Relations for Large Data Sets," ICDE Workshop on Ranking in Databases, 2007.

Ross, Kenneth A; Stoyanovich, J. "Schema Polynomials and Applications," EDBT Conference, 2008, p. 404.

Please report errors in award information by writing to: awardsearch@nsf.gov.