Analysis of parallelism in nested DO loops

The execution time of FORTRAN programs can be decreased by putting solutions to problems in their maximally parallel forms. The most important issue is the DO-loop. In this study nested DO-loops were considered and analysis of parallellism was performed on matrix multiplication using a PROLOG program. When processed by the AIDS system, the maximally parallel graph was produced. This indicates the number of processors that could be used in parallel to execute the FORTRAN program. The study shows that the maximally parallel program can run in considerably less time than that needed to run the original sequential FORTRAN program. N×N matrix multiplication programs are speeded up by a time-saving ratio that is always greater then (1:N²), but it cannot exceed (1:N³), since N³ is the maximum number of processors used in parallel at any time. These time-saving ratio evaluations assume that all operations have equal execution time and initialization overhead is ignored. © 1985.