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 reordered. 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. |