The main function of parallelizing compilers is to analyze sequential progr
ams, in particular the loop structure, to detect hidden parallelism and aut
omatically restructure sequential programs into parallel subtasks that are
executed on a multiprocessor. This article describes the design and impleme
ntation of an efficient parallelizing compiler to parallelize loops and ach
ieve high speedup rates on multiprocessor systems. It is well known that th
e execution efficiency of a loop can be enhanced if the loop is executed in
parallel or partially parallel, such as in a DOALL or DOACROSS loop. This
article also reviews a practical parallel loop detector (PPD) that is imple
mented in our PFPC on finding the parallelism in loops. The PPD can extract
the potential DOALL and DOACROSS loops in a program by verifying array sub
scripts. In addition, a new model by using knowledge-based approach is prop
osed to exploit more loop parallelisms in this paper. The knowledge-based a
pproach integrates existing loop transformations and loop scheduling algori
thms to make good use of their ability to extract loop parallelisms. Two ru
le-based systems, called the KPLT and IPLS, are then developed using repert
ory grid analysis and attribute-ordering tables respectively, to construct
the knowledge bases. These systems can choose an appropriate transform and
loop schedule, and then apply the resulting methods to perform loop paralle
lization and obtain a high speedup rate. For example, the IPLS system can c
hoose an appropriate loop schedule for running on multiprocessor systems. F
inally, a runtime technique based on the inspector/executor scheme is propo
sed in this article for finding available parallelism on loops. Our inspect
or can determine the wavefronts of a loop with any complex indirected array
-indexing pattern by building a DEF-USE table. The inspector is fully paral
lel without any synchronization. Experimental results show that the new met
hod can resolve any complex data dependence patterns where no previous rese
arch can. One of the ultimate goals is to construct a high-performance and
portable FORTRAN parallelizing compiler on shared-memory multiprocessors. W
e believe that our research may provide more insight into the development o
f a highperformance parallelizing compiler Copyright (C) 2001 John Wiley &
Sons, Ltd.