Fork-Join program response time on multiprocessors with exchangeable join  

作　　者：WANG Yong-cai ZHAO Qian-chuan ZHENG Da-zhong 

机构地区：[1]Center for Intelligent and Networked Systems, Department of Automation, Tsinghua University, Beijing 100084, China

出　　处：《Journal of Zhejiang University-Science A(Applied Physics & Engineering)》2006年第6期927-936,共10页浙江大学学报（英文版）A辑（应用物理与工程）

基　　金：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

摘　　要：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%.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 （E J）, 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 （E J） and the capacity constraint （CC）. We prove that the system response time can be effectively reduced by E J, 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%.

关 键 词：Exchangeable join First come first served （FCFS） Fork-Join MULTIPROCESSOR Response time 

分 类 号：TP3[自动化与计算机技术—计算机科学与技术]