Petri net modeling and simulation of pipelined redistributions for a deadlock-free system

Figures & data

Table 1. Pipeline-based communication models in the literature and the factors they incorporate

Paper	Model	Verification	Factors incorporated
			Scheduling	Message classification	Contentions	Blocked processes	Memory space	Load balance
Caron and Desprez (2005), Jayachandran and Abdelzaher (2007)	OOC and pipelining	Simulation	$\surd$	X	$\surd$	X	X	$\surd$
Kashif et al. (2013)	Pipelining	-Mathematics	$\surd$	X	X	X	X	$\surd$
		- Simulation
Kuntraruk et al. (2005)	Pipelining	Simulation	$\surd$	X	X	X	X	$\surd$
Liao, Choundary, Weiner, and Varshney (2004), Navarro, Asenjo, and Tabik (2009), Ties, Chandrasekhar, and Amarasinghe (2007)	-Pipelining	Simulation	$\surd$	X	X	X	$\surd$	$\surd$
	-Queues
This work	-Pipelining	Petri net, Simulation	$\surd$	$\surd$	$\surd$	$\surd$	X	$\surd$
	-Block cyclic

Table 2. Definitions of variables in this paper

Variable	Definition	Variable	Definition
$P$	Number of sending nodes	$s$	Target distribution block size
$Q$	Number of receiving nodes	$l$	Source distribution block index
$M$	Size of data array	$m$	Target distribution block index
$R$	Source distribution	$x$	Source distribution element position
$R^{\prime }$	Target distribution	$y$	Target distribution element position
$p$	Source processor index	$g$	Greatest common divisor of $Pr,Qs$
$q$	Destination processor index	$L$	Least common multiplier of $Pr,Qs$
$r$	Source distribution block size

Table 3. CPT for $P=Q=9,r=4,ands=5$

Class	Processor pairs	Communication cost
b(0)	(0,0), (8,1), (7,2), (6,3), (5,4), (4,5), (3,6), (2,7), (1,8)	4
b(1)	(7,0), (6,1), (5,2), (4,3), (3,4), (2,5), (1,6), (0,7), (8,8)	4
b(2)	(5,0), (4,1), (3,2), (2,3), (1,4), (0,5), (8,6), (7,7), (6,8)	4
b(3)	(3,0), (2,1), (1,2), (0,3), (8,4), (7,5), (6,6), (5,7), (4,8)	4
b(4)	(1,0), (0,1), (8,2), (7,3), (6,4), (5,5), (4,6), (3,7), (2,8)	4
b(6)	(6,0), (5,1), (4,2), (3,3), (2,4), (1,5), (0,6), (8,7), (7,8)	4
b(7)	(4,0), (3,1), (2,2), (1,3), (0,4), (8,5), (7,6), (6,7), (5,8)	4
b(8)	(2,0), (1,1), (0,2), (8,3), (7,4), (6,5), (5,6), (4,7), (3,8)	4

Table 4. Pipeline operations and its tasks for $P=Q=9,r=4,ands=5$

Pipeline Task	Communicating Processor Pairs (p,q)	Communication Cost
First pipeline
$T_0$	(1,0), (0,1), (8,2), (7,3), (6,4), (5,5), (4,6), (3,7), (2,8)	1
$T_1$	(3,0), (2,1), (1,2), (0,3), (8,4), (7,5), (6,6), (5,7), (4,8)	2
$T_2$	(5,0), (4,1), (3,2), (2,3), (1,4), (0,5), (8,6), (7,7), (6,8)	3
$T_3$	(7,0), (6,1), (5,2), (4,3), (3,4), (2,5), (1,6), (0,7), (8,8)	4
Second pipeline
$T_0$	(6,0), (5,1), (4,2), (3,3), (2,4), (1,5), (0,6), (8,7), (7,8)	1
$T_1$	(4,0), (3,1), (2,2), (1,3), (0,4), (8,5), (7,6), (6,7), (5,8)	2
$T_2$	(2,0), (1,1), (0,2), (8,3), (7,4), (6,5), (5,6), (4,7), (3,8)	3
$T_3$	(0,0), (8,1), (7,2), (6,3), (5,4), (4,5), (3,6), (2,7), (1,8)	4

Table 5. Solutions of Eq.1 for $P=Q=9,r=4,ands=5$

$(p,q)$	$l$	$m$	$x$	$y$	$(p,q)$	$l$	$m$	$x$	$y$	Cost
(0,0)	0	0	0	0	(7,0)	3	3	0	1	4
	0	0	1	1		3	3	1	2
	0	0	2	2		3	3	2	3
	0	0	3	3		3	3	3	4
(1,0)	0	0	0	4	(6,0)	3	3	3	0	1
(2,0)	1	1	1	0	(5,0)	2	2	0	2	3
	1	1	2	1		2	2	1	3
	1	1	3	2		2	2	2	4
(3,0)	1	1	0	3	(4,0)	2	2	2	0	2
	1	1	1	4		2	2	3	1

Figure 1. Reading from source processors’ memories and writing to target processors’ memories.

Figure 2. R/W for $P=Q=9,r=4,\mathrm{and}s=5$.

Figure 3. Memory writing over time for $P=Q=9,r=4,\mathrm{and}s=5$.

Figure 4. (a) A PN example and (b) Reachability tree

Figure 5. Pipeline generation model.

Figure 6. Pipeline execution model.

Figure 7. Pipeline execution model for $P=Q=9$, $r=4,\mathrm{and}s=5$.

Figure 8. Experiments for various parameters.

Caron, E., & Desprez, F. (2005). Out-of-core and pipeline techniques for wavefront algorithms. In Proceedings of the 19th IEEE International Parallel and Distributed Symposium (IPDPS’05). Denver, CO.

 Google Scholar

Jayachandran, P., & Abdelzaher, T. (2007). A delay composition theorem for real-time pipelines. In Proceedings of the 19th Euromicro Conference on Real-Time Systems, ECRTS ’07 (pp. 29–38). Washington, DC: IEEE Computer Society.

 Google Scholar

Kashif, H., Gholamian, S., Pelizzoni, R., Patel, H. D., & Fischmeister, S. (2013, April). ORTAP: An offset-based response time analysis for a pipelined communication resource model. In Proceedings of the 19th Real-Time and Embedded Technology and Applications Symbosium (RTAS). Philadelphia, PA.

 Google Scholar

Kuntraruk, J., Pottenger, W. M., & Ross, A. M. (2005). Application resource requirement estimation in a parallel pipeline model of execution. IEEE Transactions on Parallel and Distributed Systems, 16, 1154–1165.

 Google Scholar

Liao, W.-K., Choundary, A., Weiner, D., & Varshney, P. (2004). Performance evaluation of a parallel pipeline computational model for space-time adaptive processing. Journal of Supercomputing, 31, 137–160.

 Google Scholar

Navarro, A., Asenjo, R., & Tabik, S. (2009, September). Analytical modeling of pipeline parallelism. In Proceedings of the 18th International Conference on Parallel Architectures and Compilation Techniques. Raleigh, NC.

 Google Scholar

Ties, W., Chandrasekhar, V., & Amarasinghe, S. (2007). A practical approach to exploiting coarse-grained pipeline parallelism in C programs. In MICRO’07 (pp. 356–369). Chicago, IL.

 Google Scholar