Title: Database Operations on Chip Multiprocessors Speaker: John Cieslewicz, Columbia University Date/Time: Tuesday, January 8, 2008, 10:00 - 11:00 Location: International Programs Building, room 1155 Brief Abstract: The recent introduction of commodity chip multiprocessors (also known as multi-core chips) requires that the design of core database operations be carefully examined to take full advantage of on-chip parallelism. In this talk I will present some of the challenges and opportunities for databases provided by chip multiprocessors, highlighting recent research from the database community. Then I will present an in depth example: aggregation in a multi-core environment, the Sun UltraSPARC T1, a chip multiprocessor with eight cores and a shared L2 cache. Aggregation is an important aspect of query processing that is seemingly easy to understand and implement. Our research, however, demonstrates that a chip multiprocessor adds new dimensions to understanding hash-based aggregation performance---concurrent sharing of aggregation data structures and contentious accesses to frequently used values. We also identify a trade off between private data structures assigned to each thread versus shared data structures for aggregation. Depending on input characteristics, different aggregation strategies are optimal and choosing the wrong strategy can result in a performance penalty of over an order of magnitude. We provide a thorough explanation of the factors affecting aggregation performance on chip multiprocessors and use those factors to develop an adaptive aggregation operator that performs lightweight sampling of the input to choose the correct aggregation strategy with high accuracy. Our experiments verify that our adaptive algorithm chooses the highest performing aggregation strategy on a number of common input distributions.CSRI POC: Bruce Hendrickson, (505) 845-7599 |