language: en

EXPLOITING COMMUTING OPERATIONS IN PARALLELIZING SERIAL PROGRAMS

PEDRO DINIZ AND MARTIN RINARD
DEPARTMENT OF COMPUTER SCIENCE UNIVERSITY OF CALIFORNIA, SANTA BARBARA
SANTA BARBARA, CA 93106

Abstract. Two operations commute if the result of their execution is independent of the order in which they execute. Commuting operations can be executed concurrently provided they execute atomically on the objects they access. Statically recognizing commuting operations is of great interest because they increase the amount of concurrency a compiler can exploit. In this document we introduce commutativity analysis anew technique for automatically parallelizing serial programs. We then conduct a feasibility study of existing scientific applications as to the existence and exploitability of commuting operations. We study the commuting operations present in one such application the Barnes-Hut hierarchical N-body algorithm. We then parallelize this application using knowledge of commuting operations and present performance results of the parallel code for a shared-memory multiprocessor.

1. Introduction.