Full Text:
<2612>
CLC number: TP3
On-line Access:
Received: 2005-04-02
Revision Accepted: 2006-01-09
Crosschecked: 0000-00-00
Cited: 0
Clicked: 4397
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 A, 2006, 7(6): 927-936.
@article{title="Fork-Join program response time on multiprocessors with exchangeable join",
author="WANG Yong-cai, ZHAO Qian-chuan, ZHENG Da-zhong",
journal="Journal of Zhejiang University Science A",
volume="7",
number="6",
pages="927-936",
year="2006",
publisher="Zhejiang University Press & Springer",
doi="10.1631/jzus.2006.A0927"
}
%0 Journal Article
%T Fork-Join program response time on multiprocessors with exchangeable join
%A WANG Yong-cai
%A ZHAO Qian-chuan
%A ZHENG Da-zhong
%J Journal of Zhejiang University SCIENCE A
%V 7
%N 6
%P 927-936
%@ 1673-565X
%D 2006
%I Zhejiang University Press & Springer
%DOI 10.1631/jzus.2006.A0927
TY - JOUR
T1 - Fork-Join program response time on multiprocessors with exchangeable join
A1 - WANG Yong-cai
A1 - ZHAO Qian-chuan
A1 - ZHENG Da-zhong
J0 - Journal of Zhejiang University Science A
VL - 7
IS - 6
SP - 927
EP - 936
%@ 1673-565X
Y1 - 2006
PB - Zhejiang University Press & Springer
ER -
DOI - 10.1631/jzus.2006.A0927
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%.
[1] Baccelli, F., Liu, Z., 1990. On the execution of parallel programs on multiprocessor systems—a queuing theory approach. Journal of the ACM, 37(2):373-414.
[2] Barry, W., Allen, M., 1998. Parallel Programming: Techniques and Applications Using Networked Workstations and Parallel Computers. Addison-Wesley Publisher, Boston.
[3] Flatto, L., 1985. Two parallel queues created by arrivals with two demands II. SIAM Journal on Adv. Appl. Prob., 45:845-861.
[4] Flatto, L., Hahn, S., 1984. Two parallel queues created by arrivals with two demands. SIAM Journal on Appl. Math., 44(5):1041-1053.
[5] Glasserman, P., Yao, D.D., 1992. Some guidelines and guarantees for common random numbers. Management Science, 38(6):884-908.
[6] Ko, S.S., Serfozo, R.E., 2004. Response times in M/M/s Fork-Join networks. Adv. Appl. Prob., 36(3):854-871.
[7] Medhi, J., 1990. Stochastic Models in Queueing Theory. Academic Press Inc.
[8] Nelson, R., Tantawi, A.N., 1988. Approximate analysis of Fork/Join synchronization in parallel queues. IEEE Transactions on Computers, 37(6):739-743.
[9] Taha, M.E., Stidham, S., 1999. Sample-Path Analysis of Queueing Systems. Kluwer Academic Publishers.
[10] Towsley, D., Rommel, C.G., Stankovic, J.A., 1990. Analysis of Fork-Join program response times on multiprocessors. IEEE Transctions on Parallel and Distributed Systems, 1(3):286-303.
[11] Wright, P.E., 1992. Two parallel processors with coupled inputs. Adv. Appl. Prob., 24(4):986-1007.
Open peer comments: Debate/Discuss/Question/Opinion
<1>