Checkpoint
Overview of work completed
We first implemented a basic testing framework as well as a single-threaded BST. The testing framework supported the reading of text files to construct a basic BST, and perform inserts, searches and deletes on a BST. We then augmented the testing framework by adding support to generate multiple threads to work on a single BST, before working on adding fine-grained locking to our BST to enable concurrent access. As of right now, we have implemented fine-grained locking for ‘insert’ operations, as well as ‘delete’ operations. We have performed some basic tests to ensure that our ‘insert’ and ‘delete’ operations are working correctly, but more rigorous testing needs to take place before we can ascertain the correctness of our implementations. In particular, the ‘delete’ operation is tricky due to the large number of cases that can arise as a result of deleting a node from a BST, so it must be tested rigorously. The ‘search’ operation uses identical fine-grained locking semantics to the ‘insert’ operation, so implementing it should not be a challenge.
Goals and Deliverables
As stated in our proposal, we plan to implement a fine-grained-locking version of a BST as well as a lock-free version of a BST, and compare their runtime performance on a variety of traces. The deliverables include the source code for both versions of the BST, as well as the test harness code.
Given that it seems we are close to completing the fine-grained-locking version of the BST, we should be able to successfully complete both versions of the BST and perform the necessary analysis by the given project deadline. It is uncertain as to whether or not we will have time to implement another lock-free data structure, but it remains a possibility.
Parallelism competition demo
We plan to present graphs of the runtime performance of both BST versions against a variety of traces, and explain the resulting trends in the graphs. The traces that we will analyze the performance on include write-heavy workloads, read-heavy workloads and mixed-workloads. Given that this project is more analysis-inclined, it is unlikely that we could produce any sort of meaningful visual demo (if you have suggestions, please let us know!).
Issues that may pose a challenge
Time and uncertainty pose the biggest challenge as of now. Based on our upcoming schedules, it seems that we will not be able to seriously start on the lock-free BST implementation till the 30th of April or 1st of May, which gives us only 10 days or so to finish the project. However, at that point, we will be done with most of our other classes, so we will be 100% committed to the project.
Another issue that poses a challenge is the issue of testing. When performing a sequence of operations concurrently on a BST, the resulting BST will differ from one run to another, since the operations on the BST may be performed in a different order from one run to another. This makes it difficult to verify that our BST implementation is correct, particularly on larger BSTs. Thus far, we have relied on manual verification to ensure that our BST is functioning correctly, but this proves an unreasonable scheme for the workload-sizes we plan to perform runtime analysis on. We do not have a solution to this problem as of now.
Updated Schedule
It is difficult for us at this stage to exactly specify what work will be performed at what time, especially during the last week or so. So instead we specify the availability of team members during particular periods of time.
#define WORK_ON_OTHER_STUFF 404
04/21: Add timing code to the existing test-harness. Get preliminary results for fine grained locked BST. Start designing the lockfree version.
04/22: 404
04/23: Complete the lockfree design and start lockfree implementation.
04/24, 04/25, 04/26, 04/27, 04/28, 04/29: 404 / minimal work on parallel
04/30, 05/01, 05/02, 05/03: Romit goes 100% during this period.
05/04, 05/05, 05/06, 05/07: Swapnil joins in. Swapnil available for 100% of the time. Romit available for 50% of the time.
05/08, 05/09,: Romit pulls a 404 for his database exam. Swapnil finishes the remaining stuff.
05/10: Presentation preparation, etc.
05/11: Project Competition
Authors and Contributors
Swapnil Pimpale, Romit Kudtarkar