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

[img] PDF
4Mb

Abstract

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.

Item Type:Article
Keyword:grain size, scheduling, shared-memory computers, Bernstein sets
Publisher:Universiti Putra Malaysia Press
ID Code:3870
Deposited By: Nasirah Abu Samah
Deposited On:02 Dec 2009 03:02
Last Modified:27 May 2013 07:11

Repository Staff Only: item control page

Document Download Statistics

This item has been downloaded for since 02 Dec 2009 03:02.

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


Universiti Putra Malaysia Institutional Repository

Universiti Putra Malaysia Institutional Repository is an on-line digital archive that serves as a central collection and storage of scientific information and research at the Universiti Putra Malaysia.

Currently, the collections deposited in the IR consists of Master and PhD theses, Master and PhD Project Report, Journal Articles, Journal Bulletins, Conference Papers, UPM News, Newspaper Cuttings, Patents and Inaugural Lectures.

As the policy of the university does not permit users to view thesis in full text, access is only given to the first 24 pages only.