UPM Institutional Repository

Top-down Heuristic for Finding Optimal Grain Size of Parallel Tasks


Mohd Saman, Md. Yazid and D. J., Evans (1995) Top-down Heuristic for Finding Optimal Grain Size of Parallel Tasks. Pertanika Journal of Science & Technology, 3 (2). pp. 241-259. ISSN 0128-7680


In order to have an optimal execution time of a program running on a multiprocessor system, the program has to be partitioned into concurrent tasks. Partitioning of programs to grain size suitable for parallel execution is an NP complete problem but near-optimal time can be derived. This paper discusses a heuristic to determine the near-optimal grain size of parallel tasks that will give the best execution time. The effects of communication overheads between the different processors are examined. The heuristic developed is capable of balancing between maximizing parallelism and minimizing overheads.

Download File


Download (4MB)

Additional Metadata

Item Type: Article
Publisher: Universiti Putra Malaysia Press
Keywords: grain size, scheduling, shared-memory computers, Bernstein sets
Depositing User: Nasirah Abu Samah
Date Deposited: 02 Dec 2009 03:02
Last Modified: 27 May 2013 07:11
URI: http://psasir.upm.edu.my/id/eprint/3870
Statistic Details: View Download Statistic

Actions (login required)

View Item View Item