Date of Publication

1992

Document Type

Master's Thesis

Degree Name

Master of Science in Computer Science

Subject Categories

Computer Sciences

College

College of Computer Studies

Department/Unit

Computer Science

Thesis Adviser

En-Hsin Huang

Defense Panel Chair

Marilou Jopillo

Defense Panel Member

Mitch Andaya
Peter K. Fernandez

Abstract/Summary

A distributed Computing System (DCS) comprises a number of processing elements, connected by an interconnection network. The processor form the node of the network. A distributed Software can be partitioned into a set of tasks. These tasks of a distributed software need to be allocated to various nodes of the system, so as to optimize performance. This study is an investigation of the problem of static task assignment in a DCS i.e. given a set of m communicating tasks having precedence order for execution, to which of the n heterogeneous processors should each task be assigned. The precedence graph of tasks considered in the study is a directed acyclic graph (DAG). Since the problem of task assignment is known to be NP-complete, an approximate greedy algorithm which takes polynomial time for the assignments very near to optimal assignments is formulated. Two cost functions in terms of Interprocessor Communication (IPC) and execution cost to evaluate the effectiveness of the assignments are used. A formal proof of correctness is conducted for the proposed algorithm and the effectiveness of algorithm is shown by the results of the simulation.

Abstract Format

html

Language

English

Format

Print

Accession Number

TG02005

Shelf Location

Archives, The Learning Commons, 12F Henry Sy Sr. Hall

Physical Description

89, [36] leaves, 28 cm.

Keywords

Job descriptions; Electronic data processing--Distributed processing; Heuristic programming

Upload Full Text

wf_yes

Download

Share

COinS