| Fork-Join program response time on multiprocessors with exchangeable join |
| |
| 作者姓名： | WANG Yong-cai ZHAO Qian-chuan ZHENG Da-zhong |
| |
| 作者单位： | Center for Intelligent and Networked Systems，Department of Automation，Tsinghua University，Beijing 100084，China |
| |
| 基金项目： | Project supported by the National Natural Science Foundation of0 China (Nos. 60274011 and 60574067), and the Program for NewCentury Excellent Talents in University (No. NCET-04-0094), China |
| |
| 摘 要： | INTRODUCTION With the prevalence of distributed computing and parallel programming languages (Barry and Allen, 1998), performance evaluation of the parallel execu-tion systems becomes important. In this work we derive bounds and an approximation of the mean response time of a particular type parallel program: program with Fork-Join tasks and executed in multi-processor with first come first served (FCFS) policy. This kind of program is general in large-scale simu-lation and numerical …
|
| 关 键 词： | FCFS 排队论 交叉连接 响应时间 多处理器 |
| 收稿时间： | 2005-04-02 |
| 修稿时间： | 9 January 2006 |
Fork-Join program response time on multiprocessors with exchangeable join |
| |
| WANG Yong-cai ZHAO Qian-chuan ZHENG Da-zhong.Fork-Join program response time on multiprocessors with exchangeable join[J].Journal of Zhejiang University Science,2006,7(6):927-936. |
| |
| Authors: | Yong-cai Wang Qian-chuan Zhao Da-zhong Zheng |
| |
| Institution: | (1) Center for Intelligent and Networked Systems, Department of Automation, Tsinghua University, Beijing, 100084, China |
| |
| Abstract: | The Fork-Join program consisting of K parallel tasks is a useful model for a large number of computing applications. When the parallel processor has multi-channels,
later tasks may finish execution earlier than their earlier tasks and may join with tasks from other programs. This phenomenon
is called exchangeable join (EJ), which introduces correlation to the task’s service time. In this work, we investigate the
response time of multiprocessor systems with EJ with a new approach. We analyze two aspects of this kind of systems: exchangeable
join (EJ) and the capacity constraint (CC). We prove that the system response time can be effectively reduced by EJ, while
the reduced amount is constrained by the capacity of the multiprocessor. An upper bound model is constructed based on this
analysis and a quick estimation algorithm is proposed. The approximation formula is verified by extensive simulation results,
which show that the relative error of approximation is less than 5%.
Project supported by the National Natural Science Foundation of China (Nos. 60274011 and 60574067), and the Program for New
Century Excellent Talents in University (No. NCET-04-0094), China |
| |
| Keywords: | Exchangeable join First come first served (FCFS) Fork-Join Multiprocessor Response time |
| 本文献已被 CNKI 维普 万方数据 SpringerLink 等数据库收录！ |
