To take full advantage of the parallelism offered by a multicore machine, one must write parallel code. Writing parallel code is difficult. Even when one writes correct code, there are numerous performance pitfalls. For example, an unrecognized data hotspot could mean that all threads effectively serialize their access to the hotspot, and throughput is dramatically reduced.
This project aims to provide a generic framework for performing certain kinds of concurrent operations in parallel. Infrastructure is provided to perform those operations in a scalable way over the available threads in a multicore machine, automatically responding to hotspots and other performance hazards. The goal is not to squeeze the last drop of performance out of a particular platform. Rather, with the planned system a programmer can, without detailed knowledge of concurrent and parallel programming, develop code that efficiently utilizes a multicore machine.
The project involves the development of algorithms and data structures designed for the efficient parallel execution of generic code fragments. The primary focus is on data intensive operations as would typically be found in an in-memory database engine. Critical research questions include how to design generic multi-threaded operators that can be applied to a range of computations, how to avoid cache thrashing, and how to implement the framework in a way that works on a variety of hardware platforms. Performance improvements in throughput of an order of magnitude are expected relative to naive solutions that suffer from contention. The project aims to achieve performance close to that of hand-tailored expert-written parallel code, with far less coding effort.
Participants
Publications
Energy Analysis of Hardware and Software Range Partitioning, L. Wu, O. Polychroniou, R. J. Barker, M. A. Kim, K. A. Ross,ACM Transactions on Computer Systems, September 2014. link.
Vectorized Bloom Filters for Advanced SIMD Processors, O. Polychroniou, K. A. Ross, Proceedings of the 2014 Workshop on Data Management on New Hardware, June 2014. link.
A Comprehensive Study of Main-memory Partitioning and its Application to Large-scale Comparison- and Radix-sort, O. Polychroniou, K. A. Ross, Proceedings of the 2014 SIGMOD Conference, June 2014. link.
Track Join: Distributed Joins with Minimal Network Traffic, O. Polychroniou, R. Sen, K. A. Ross, Proceedings of the 2014 SIGMOD Conference, June 2014. link.
Navigating Big Data with High-Throughput, Energy-Efficient Data Partitioning, L. Wu, R. J. Barker, M. A. Kim, K. A. Ross. International Symposium on Computer Architecture (ISCA), June 2013. pdf. A version of this article appears in IEEE Micro, Vol. 34(3), 2014, as one of the "Top Picks" from 2013.
High Throughput Heavy Hitter Aggregation for Modern SIMD Processors, O. Polychroniou, K. A. Ross, Proceedings of the 2013 Workshop on Data Management on New Hardware, June 2013. link.
Ameliorating Memory Contention of OLAP Operators on GPU Processors, E. Sitaridi, K. A. Ross, Proceedings of the 2012 Workshop on Data Management on New Hardware, May 2012. (Best Paper Award winner.) link.
Partitioned Blockmap Indexes for Multidimensional Data Access, K. A. Ross, E. Sitaridi, Columbia University Technical Report CUCS-006-12 , April 2012. link.
Scalable Aggregation on Multicore Processors, Y. Ye, K. A. Ross, N. Vesdapunt, Proceedings of the 2011 Workshop on Data Management on New Hardware, June 2011. link.
Thread-Level Parallel Indexing of Update Intensive Moving-Object Workloads, D. Sidlauskas, K. A. Ross, C. S. Jensen, S. Saltenis, 12th International Symposium on Advances in Spatial and Temporal Databases, August 2011. link.
Optimizing Read Convoys in Main-Memory Query Processing. K. A. Ross, Proceedings of the 2010 Workshop on Data Management on New Hardware, June 2010. pdf.
Automatic Contention Detection and Amelioration for Data Intensive Operations. J. Cieslewicz, K. A. Ross, K. Satsumi, and Y. Ye, Proceedings of the 2010 SIGMOD Conference, June 2010. pdf.
Software
Related Projects
This material is based in part upon work supported by the National
Science
Foundation under grant IIS-0915956.
Any opinions, findings, and conclusions or recommendations expressed
in this material are those of the author(s) and do not necessarily
reflect
the views of the National Science Foundation.