A heuristic approach to task assignment in distributed computing systems

• Main Author: Kafeel, Muhammad
• Format: text
• Language: English
• Published: Animo Repository 1992
• Subjects: Job descriptions; Electronic data processing > Distributed processing; Heuristic programming; Computer Sciences
• Online Access: https://animorepository.dlsu.edu.ph/etd_masteral/1397; https://animorepository.dlsu.edu.ph/cgi/viewcontent.cgi?article=8235&context=etd_masteral
• Institution: De La Salle University

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.