Masters Theses

Keywords and Phrases

Submesh allocation algorithm; Reservation factor

Abstract

"A Partitionable Mesh Connected System (PMCS) is a system of mesh-connected processors which can be partitioned into many rectangular sub meshes and may execute jobs in parallel. Efficient processor allocation is crucial for achieving high-performance in PMCS. A good processor allocation algorithm should be able to detect and locate the presence of a free sub mesh for the incoming task, if one such sub mesh exists. Only then can the strategy be called recognition complete. This thesis proposes a sub mesh allocation algorithm that has complete sub mesh recognition capability. It uses a n ovel function, called the reservation factor to evaluate possible candidate free sub meshes. By using reservation factor as the best-fit criteria to determine the best possible candidate for an incoming request, the algorithm achieves better results than all the previously proposed algorithms. The proposed algorithm gives better results than several of the previously proposed algorithms in terms of mean search time (MST) i.e. average CPU time elapsed on sub mesh allocations per job for jobs with smaller execution times. Two different job scheduling policies are followed, namely First-Come-First-Served (FCFS) and modified FCFS (M-FCFS). In FCFS scheduling policy, jobs are serviced in the order they arrive. If the job at the head of the request queue is not allocatable, it waits until a sub mesh is released and is tried again. This blocks the jobs after the head of the queue to be serviced. In M-FCFS scheduling, when the job at the head of the request queue is not allocatable it is queued, and subsequent jobs are tried. M-FCFS scheduling policy shows better performance results than the FCFS scheduling"-- Abstract, p. iii

Advisor(s)

Erçal, Fikret

Committee Member(s)

Subramanya, S. R.
Enke, David Lee, 1965-

Department(s)

Computer Science

Degree Name

M.S. in Computer Science

Publisher

University of Missouri--Rolla

Publication Date

Summer 2003

Pagination

ix, 58 pages

Note about bibliography

Includes bibliographical references (pages 53-57)

Rights

© 2003 Pramodh Narayanan, All rights reserved.

Document Type

Thesis - Restricted Access

File Type

text

Language

English

Subject Headings

MultiprocessorsParallel processing (Electronic computers)

Thesis Number

T 8335

Print OCLC #

54885692

Download
Off-campus S&T users

Share My Thesis If you are the author of this work and would like to grant permission to make it openly accessible to all, please click the button above.

Share

 
COinS