On the automatic parallelization of sparse and irregular Fortran programs[1]This work is supported in part by Army contract DABT63‐95‐C‐0097; Army contract N66001‐97‐C‐8532; NSF contract MIP‐9619351; and a Partnership Award from IBM. This work is not necessarily representative of the positions or policies of the Army or Government.

Article type: Research Article

Authors: Lin, Yuan^; | Padua, David

Affiliations: Department of Computer Science, University of Illinois at Urbana‐Champaign, Urbana, IL 61801, USA E‐mail: {yuanlin,padua}@uiuc.edu

Note: [] Corresponding author.

Abstract: Automatic parallelization is usually believed to be less effective at exploiting implicit parallelism in sparse/irregular programs than in their dense/regular counterparts. However, not much is really known because there have been few research reports on this topic. In this work, we have studied the possibility of using an automatic parallelizing compiler to detect the parallelism in sparse/irregular programs. The study with a collection of sparse/irregular programs led us to some common loop patterns. Based on these patterns new techniques were derived that produced good speedups when manually applied to our benchmark codes. More importantly, these parallelization methods can be implemented in a parallelizing compiler and can be applied automatically.

Journal: Scientific Programming, vol. 7, no. 3‐4, pp. 231-246, 1999