A heuristic approach to task assignment in distributed computing systems
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 no...
Saved in:
| Main Author: | |
|---|---|
| Format: | text |
| Language: | English |
| Published: |
Animo Repository
1992
|
| Subjects: | |
| Online Access: | https://animorepository.dlsu.edu.ph/etd_masteral/1397 https://animorepository.dlsu.edu.ph/cgi/viewcontent.cgi?article=8235&context=etd_masteral |
| Tags: |
Add Tag
No Tags, Be the first to tag this record!
|
| Institution: | De La Salle University |
| Language: | English |
| 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. |
|---|