[Previous [1] [2] [3] [4] [5] [6] [7] [8]

Journal of Inforamtion Science and Engineering, Vol. 16, No. 2, pp. 169-200 (March 2000)

An Intelligent Parallel Loop Scheduling for
Parallelizing Compilers*

Yun-Woei Fann, Chao-Tung Yang+
Shian-Shyong Tseng and Chang-Jiun Tsai

Department of Computer and Information Science
National Chiao Tung University
Hsinchu, Taiwan 300, R.O.C.
+ROCSAT Ground System Section
National Space Program Office
Hsinchu, Taiwan 300, R.O.C.

In this paper we propose a knowledge-based approach to solving loop-scheduling problems. A rule-based system, called IPLS, is developed by combining a repertory grid and an attribute ordering table to construct a knowledge base. IPLS chooses an appropriate scheduling algorithm by inferring some features of loops and assigning parallel loops to multiprocessors to achieve significant speedup. Because more attributes are proposed, the accuracy of selection of an appropriate scheduling method is improved. In addition, the refined IPLS system can automatically adjust the attributes in the knowledge base according to profile information; therefore, IPLS has the capability of feedback learning. The experimental results show that our approach can achieve greater speedup on multiprocessor systems than can others.

Keywords: parallelizing compiler, parallel loop scheduling, knowledge-based system, multi-processor systems, speedup

Full Text () Retrieve PDF document (200003_02.pdf : 3,563,874 bytes)

Received March 31, 1999; revised June 16 & July 27, 1999; accepted September 20, 1999.
Communicated by Shang-Rong Tsai.
*This work was supported in part by the NSC of the ROC under Grant No. NSC87-2213-E-009-023. A preliminary version of this paper, entitled IPLS: An Intelligent Parallel Loop Scheduling for Multiprocessor Systems, appeared in Proceedings of the 1998 International Conference on Parallel and Distributed Systems (ICPADS '98), Taiwan, pp. 775-782, 1998.