Full Text:   <2610>

CLC number: TP3

On-line Access: 

Received: 2005-04-02

Revision Accepted: 2006-01-09

Crosschecked: 0000-00-00

Cited: 0

Clicked: 4394

Citations:  Bibtex RefMan EndNote GB/T7714

-   Go to

Article info.
1. Reference List
Open peer comments

Journal of Zhejiang University SCIENCE A 2006 Vol.7 No.6 P.927-936


Fork-Join program response time on multiprocessors with exchangeable join

Author(s):  WANG Yong-cai, ZHAO Qian-chuan, ZHENG Da-zhong

Affiliation(s):  Center for Intelligent and Networked Systems, Department of Automation, Tsinghua University, Beijing 100084, China

Corresponding email(s):   wangyongcai@mails.tsinghua.edu.cn

Key Words:  Exchangeable join, First come first served (FCFS), Fork-Join, Multiprocessor, Response time

Share this article to: More |Next Article >>>

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",
publisher="Zhejiang University Press & Springer",

%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

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

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%.

Darkslateblue:Affiliate; Royal Blue:Author; Turquoise:Article


[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


Please provide your name, email address and a comment

Journal of Zhejiang University-SCIENCE, 38 Zheda Road, Hangzhou 310027, China
Tel: +86-571-87952783; E-mail: cjzhang@zju.edu.cn
Copyright © 2000 - 2024 Journal of Zhejiang University-SCIENCE