Project Title: Parallel Buffering Data Structures for Searching

Name: Cory Fraser

Searching has always been a prominent problem in Computer Science. Data structures to assist with searching, such as a binary search trees and B-Trees, have been created and continually improved over time. In recent years much work has been done on creating concurrent and parallel versions of these data structures that can take advantage of the multi-core nature of today's computers. One approach to speed up searching is to batch up multiple operations to perform on a data structure and perform them all at once with optimizations. A particular example of this sort of structure is described in a paper published this year, A Parallel Buffer Tree. It combines the optimizations of batching operations along with the performance increase from making use of a system's multiple cores. This project will attempt to verify the paper's claims possibly by implementing the described algorithm and testing its performance in an assortment of conditions and inputs.

Startup Paper(s):

Deliverables:

• Literature Review (PDF file created from LATEX template)
• Presentation Outline (PDF file created from LATEX template)
• Slide Presentation (PowerPoint File) incl. Question Sheet
• Final Paper (PDF file created from LATEX template)
• Code and Data (put all code, data, etc. into this directory)

Relevant References:

• L. Arge, The Buffer Tree: A New Technique for Optimal I/O Algorithms
• L. Arge, The Buffer Tree: A Technique for Designing Batched External Data Structures
• D. Hutchinson, A. Maheshwari, J. Sack, R. Velicescu, Early Experiences in Implementing the Buffer Tree
• L. Arge, M. Goodrich, M. Nelson, Fundamental Parallel Algorithms for Private-Cache Chip Multiprocessors
• L. Arge, External Memory Data Structures
• N. Shavit, Data structures in the multicore age