Architectural and software support for executing numerical applications on high performance computers

iii Numerical applications require large amounts of computing power. Although shared memory multiprocessors provide a cost-e ective platform for parallel execution of numer-ical programs, parallel processing has not delivered the expected performance on these machines. There are two crucial steps in parallel execution of numerical applications: (1) e ective parallelization of an application and (2) e cient execution of the parallel program on a multiprocessor. This thesis addresses the second step within the scope of automatically parallelized FORTRAN programs. In this thesis, the mismatch between the needs of parallelized FORTRAN programs and the support for parallel execution in shared memory multiprocessors is identi ed as a cause of poor performance. The thesis addresses this problem from two angles, architec-tural and software support for parallel execution and compiler transformation to enhance program characteristics. Architectural features and synchronization and scheduling al-gorithms are studied to increase the e ciency of support for parallel execution. It is shown that architectures supporting atomic fetch&add primitives and synchronization busses can execute parallel programs more e ectively. New algorithms for lock access and parallel task scheduling are proposed. iv The thesis also explores compiler transformations which can modify parallel program characteristics to increase the parallel execution e ciency of less sophisticated archi-tectures. It is shown that by using blocking transformations on nested parallel loops, program characteristics can be modi ed to decrease the need for scheduling and synchro-nization operations. This results in an increase in the e ciency of parallel execution, especially for multiprocessors with simplistic support for interprocessor synchronization.