My current research project involves implementing an amortized-time order
maintenance algorithm. The order maintenance algorithm employs a linked list of nodes with
ordered numerical keys and an implementation for insert, delete, and order functions. In some
instances where the list has no space for a new node, an insertion will require the list to be
First, I implementrf this algorithm in C, and then altered the code for
Cilk, which allows multithreading. Consequently, insertions can be
run in parallel.
In a serialized implementation, the reordering does not tax the efficiency of the overall
algorithm as the other function calls run much faster and is thus faster on average; however, when the
algorithm is written in parallel, this single function call can significantly slow down the algorithm's
performance. We aimed to reduce the time needed to reorder the list and thus speed up the algorithm in
parallel. This was achieved by implementing overlaying skip lists and by adding additional sublists.
This project is significant to research with parallelized amortized algorithms. Amortized algorithms
have proven difficult to effectively mutithread as the slower functions will delay all subsequent f
unction calls, as is the case with the order maintenance algorithm; therefore, this algorithm provides
some insight into the efficiency of amortized algorithms in parallel.
View Final Paper (PDF)