Exploiting Commuting Operations in Parallelizing Serial Programs

Two operations commute if the result of their execution is independent of theorder in which they execute. Commuting operations can be executed concurrentlyprovided they execute atomically on the objects they access. Staticallyrecognizing commuting operations is of great interest because they increase theamount of concurrency a compiler can exploit. In this document we introducecommutativity analysis - a new technique for automatically parallelizing serialprograms. We then conduct a feasibility study of existing scientificapplications as to the existence and exploitability of commuting operations.We study the commuting operations present in one such application - theBarnes-Hut hierarchical N-body algorithm. We then parallelize this applicationusing knowledge of commuting operations and present performance results of theparallel code for a shared-memory multiprocessor.