https://scholars.lib.ntu.edu.tw/handle/123456789/488282
標題: | Optimal assignment of task modules with precedence in distributed computing systems. | 作者: | GEN-HUEY CHEN Yur, Jyh-Shiarn |
公開日期: | 1993 | 卷: | 75 | 期: | 1-2 | 起(迄)頁: | 1-34 | 來源出版物: | Inf. Sci. | 摘要: | We consider the problem of finding an optimal assignment of task modules with a precedence relationship in a distributed computing system. The objective of task assignment is to minimize the task turnaround time, i.e., the total time required to finish the execution of a task. This problem is known to be NP-complete for more than three processors. To solve the problem, a well-known state space reduction technique, branch-and-bound-with-underestimates, is applied, and two underestimate functions are defined. Through experiment, their effectiveness is shown by comparison with both Wang and Tsai's algorithm and the A* algorithm. Parameters considered in the experiment include the number of modules, the number of processors, the ratio of average intermodule communication time to average module execution time, and the shapes of task graphs. Statistical data about the number of search nodes, maximal queue length, and execution time are collected for performance evaluation. © 1993. |
URI: | https://www.scopus.com/inward/record.uri?eid=2-s2.0-0027812228&doi=10.1016%2f0020-0255%2893%2990110-8&partnerID=40&md5=25a853eccb4d2c9bc69386cf66264068 | ISSN: | 00200255 | DOI: | 10.1016/0020-0255(93)90110-8 | SDG/關鍵字: | Algorithms; Computer science; Information science; Execution time; Intermodule communication time; Maximal queue length; Optimal assignment; Task graphs; Task modules; Task turnaround time; Distributed computer systems |
顯示於: | 資訊工程學系 |
在 IR 系統中的文件,除了特別指名其著作權條款之外,均受到著作權保護,並且保留所有的權利。