# Broadcasting Algorithms of Three-Dimensional Petersen-Torus Network

Authors: Jong-Seok Kim; Hyeong-Ok Lee; Mihye Kim; Sung Won Kim
Journal: Journal of Applied Mathematics
 (2014)

---

## Abstract

The three-dimensional Petersen-torus network 3PT is based on the Petersen graph and has recently been proposed as an interconnection network. 3PT is better than the well-known 3D torus and 3D honeycomb mesh in terms of diameter and network cost. In this paper, we propose one-to-all and all-to-all broadcasting algorithms for 3PT(l;m;n) under SLA (single-link available) and MLA  (multiple-link available) models.


---

## Body

## 1. Introduction

An interconnection network of parallel computing systems consists of a set of microprocessors, local memories, and communication links for data transmission between processors. The efficiency of interprocessor communication is critical for parallel computing systems, and the diameter of an interconnection network is an important parameter describing the efficiency of communication. Consequently, routing and the diameter of the network are major primitives with scope for improving the performance of interconnection networks.An interconnection network can be modeled as an undirected graphG=(V,E), where V(G) is the set of nodes and E(G) is the set of edges of graph G. Each processor is an element of V(G) and two arbitrary processors u and v are connected by a communication link (u,v). In G, each processor is represented as a node and a communication link between two processors is represented as an edge. The distance between u and v in G is defined as the length of a shortest path connecting u and v, denoted as dist⁡(u,v). The diameter of G is defined as the maximal value of the distances between all pairs of nodes in G, denoted as diam⁡(G) (i.e., diam⁡(G)=max⁡⁡{dist⁡(u,v)∣u,v∈V(G)}).Because a delay will occur whenever a packet passes through a node, the efficiency of communication can be improved by minimizing the diameter, and by minimizing the delay in transferring a packet from a source node to a destination node under the worst-case scenario for the network. As a result, with a given fixed number of interconnection resources (i.e., nodes and edges of an interconnection network), being able to construct an interconnection network with a diameter as small as possible is a very significant factor in the design of an interconnection network [1]. Broadcasting is also one of the major parameters determining the performance of interconnection networks and is significantly influenced by the efficiency of broadcasting algorithms [2]. Broadcasting is a basic data communication method for interconnection networks, corresponding to message transmission between nodes [3]. In general, messages are disseminated between nodes in two ways: one-to-all broadcasting, whereby messages are sent from a source node to all other nodes in the network, and all-to-all broadcasting, where messages are sent from all nodes to all other nodes in the network [2–7]. Broadcasting algorithms are commonly based on two communication models: single-port or all-port communication [6, 7]. In the single-port communication model, each node transmits messages using only one link incident on it at each stage of broadcasting, whereas in all-port communication, each node transmits messages using all links incident on it at each stage of broadcasting. The former is known as the single-link-available (SLA) model, and the latter is the multiple-link-available (MLA) model [8].The three-dimensional Petersen-torus interconnection network3PT(l,m,n)  (l,m,n≥2) was proposed by Seo and is based on the Petersen graph with a fixed four-degree network [9]. The network costs are improved compared to 3D mesh variation networks that have an equivalent number of nodes as 3PT(l,m,n). In this paper, we propose and analyze algorithms for one-to-all and all-to-all broadcasting in 3PT(l,m,n) under SLA and MLA models. The results are as follows. (1) The one-to-all broadcasting time in 3PT(l,m,n) under SLA model is 2⌊l/2⌋+2⌊m/2⌋+15 when l= odd, l+2⌊m/2⌋+14 when l= even. (2) The one-to-all broadcasting time in 3PT(l,m,n) under MLA model is 2⌊l/2⌋+2⌊m/2⌋+7 when l= odd, l+2⌊m/2⌋+6 when l= even. (3) The all-to-all broadcasting time in 3PT(l,m,n) under SLA model is 3m+3n+2l+2.  (4) The all-to-all broadcasting time in 3PT(l,m,n) under SLA model is 3⌊m/2⌋+3⌊n/2⌋+2⌊l/2⌋+4 when m, n, and l are odd and is 3m/2+3n/2+l+4 when m, n, and l are even.The remainder of this paper is organized as follows. In Section2, we describe the properties of 3PT(l,m,n) In Section 3, we propose the one-to-all broadcasting in 3PT(l,m,n) under SLA and MLA models and we show the all-to-all broadcasting in 3PT(l,m,n) under SLA and MLA models. Section 5 summarizes and concludes the paper.


## 2. Preliminaries

The three-dimensional Petersen-torus interconnection network3PT(l,m,n)  (l,m,n≥2) is based on the Petersen graph [10], which is a regular node- and edge-symmetric graph with 10 nodes, a degree of 3, and a diameter of 2. 3PT(l,m,n) is also a regular graph and has 10lmn nodes, 20lmn edges, and a fixed degree of 4. 3PT(l,m,n) is defined as follows: 3PT(l,m,n)=(V3PT,E3PT), where V3PT is a set of nodes and E3PT is a set of edges. An edge that connects two arbitrary nodes A and B is denoted by (A,B). A node in 3PT(l,m,n) is represented by Definition 1 [9].Definition 1.
We have(1)V3PT={(z,x,y,p),0≤z≤l,0≤x≤m,0≤y≤n,0≤p≤9}.In3PT(l,m,n), a Petersen graph is located at the intersection of the Z-, X-, and Y-axes on a coordinate plane and is called a module. The address of a module is represented by (z,x,y) and the address of a node in a module is represented by (z,x,y,p), where z, x, and y are the Z-, X-, and Y-axes of the module and p is a node address in the module (i.e., in the Petersen graph). The edges can be divided into internal and external edges, where an internal edge connects two arbitrary nodes in a module (i.e., an internal edge is that of the Petersen graph), and an external edge connects two nodes located in different modules. Definition 2 describes the external edges of 3PT(l,m,n) [9], where the symbol % represents the modulus operator. Figure 1 shows 3PT(5,5,5) constructed using Definition 2. For neatness, in Figure 1, wraparound edges are omitted at all basic modules.Figure 1
3
PT
(
5,5
,
5
).Definition 2.
We have the following.(1)
The longitudinal edge is((z,x,y,6),(z,x,(y+1)%n,9)).(2)
The latitudinal edge is((z,x,y,1),(z,(x+1)%m,y,4)).(3)
The diagonal edge is((z,x,y,2),(z,(x+1)%m,(y+1)%n,3)).(4)
The reverse-diagonal edge is((z,x,y,7),(z,(x-1+m)%m,(y+1)%n,8)).(5)
The dimensional edge is((z,x,y,0),((z+1)%l,x,y,5)).(6)
The wraparound edge is((z,x,0,9),(z,x,n-1,6)), ((z,0,y,4),(z,m-1,y,1)), ((0,0,y,7),(0,m-1,(y+1)%n,8)), ((0,0,y,3),(0,m-1,(y-1+n)%n,2)),     ((0,x,0,8),(0,(x+1)%m,n-1,7)),  ((0,x,0,3),(0,(x-1+m)%m,n-1,7)).


## 3. One-to-All Broadcasting of 3PT(l,m,n)

In this section, we analyze the one-to-all broadcasting of3PT(l,m,n) under SLA and MLA models. The broadcasting of 3PT(l,m,n) must be calculated by dividing the network into two cases: m≥n and n<m. However, we only analyze the case of m≥n, because the results of the two cases are very similar. In a previous work [8], the one-to-all broadcasting of the Petersen graph was analyzed as Lemma 3.Lemma 3.
The one-to-all broadcasting time of the Petersen graph is 4 in the SLA model and 2 in the MLA model.The following symbols are defined for broadcasting between modules.(i)
→: The message transmission via an internal edge.(ii)
⇛: The message transmission via an external edge.(iii)
wj: An internal node of a module received the message by ⇛.(iv)
LU-edge: Reverse-diagonal edge for message transmission from (zi,x,y,7) to (zi,x-1,y+1,8).(v)
RD-edge: Reverse-diagonal edge for message transmission from (zi,x,y,7) to (zi,x+1,y-1,8).(vi)
LD-edge: Diagonal edge for message transmission from (zi,x,y,7) to (zi,x-1,y-1,8).(vii)
RU-edge: Diagonal edge for message transmission from (zi,x,y,7) to (zi,x+1,y+1,8).(viii)
Source module: Module received the message by Condition 1.(ix)
Destination module: Module for Step 5.(x)
Ms: Modules that receive a message through diagonal edges and forward the message to adjacent modules via longitudinal, latitudinal, or reverse-diagonal edges or through reverse-diagonal edges and forward the message to adjacent modules via longitudinal, latitudinal, or reverse-diagonal edges.(xi)
Ifz=0, then z-1=l-1; if z=l-1, then z+1=0 where 0≤z≤l-1.(xii)
Ifx=0, then x-1=m-1, if y=0, then y-1=n-1, and if y=n-1, then y+1=0 where 0≤x≤m-1,0≤y≤n-1.The conditions for the one-to-all broadcasting of3PT(l,m,n) under SLA model are as follows.


### 3.1. Conditions for the One-to-All Broadcasting of 3 PT(l,m,n) under SLA Mode 1

Condition 1.
Perform broadcasting between modules via internal and dimensional edges as follows.(1)
(z,x,y,p0)→(z,x,y,p1)→(z,x,y,0 or 5)→(z,x,y,5 or 0).
(2)(i)
Whenl= odd,
(2)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+⌊l2⌋)%l,x,y,5)⟶((z+⌊l2⌋)%l,x,y,0);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+⌈l2⌉)%l,x,y,0)⟶((z+⌈l2⌉)%l,x,y,5).(ii)
Whenl= even,
(3)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+l2)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+l2)%l,x,y,0).
In(1), if p0=1 or 4 or 6 or 9, then remove the message transmission by (z,x,y,p0)→(z,x,y,p1), and if p1=0 or 5, then remove the message transmission by (z,x,y,p1)→(z,x,y,0 or 5).Condition 2.
All nodes located inside(z,x,y) receive a message in the following order:(1)
(z,x,y,0)→(z,x,y,4); (z,x,y,5)→(z,x,y,9),(2)
(z,x,y,0)→(z,x,y,1); (z,x,y,4)→(z,x,y,3); (z,x,y,5)→(z,x,y,6); (z,x,y,9)→(z,x,y,8),(3)
(z,x,y,6)→(z,x,y,7); (z,x,y,3)→(z,x,y,2).Condition 3.
The modules that received a message through aLU-edge transmit the message in the following order, and the modules that received a message through a RD-, LD-, or RU-edge also transmit the message in a similar way to the following orders. However, when performing (5), if the modules to receive a message (i.e., the modules to which nodes w1, w2, w3, and w4 belong) already had the message, the message is not sent to the modules:(1)
(z,x,y,8)→(z,x,y,7),(2)
(z,x,y,7)⇛w0=(z,x-1,y+1,8);  (z,x,y,8)→(z,x,y,1),(3)
(z,x,y,8)→(z,x,y,9);  (z,x,y,7)→(z,x,y,4);  (z,x,y,1)→(z,x,y,0),(4)
(z,x,y,7)→(z,x,y,6);  (z,x,y,4)→(z,x,y,3);  (z,x,y,1)→(z,x,y,2);(z,x,y,0)→(z,x,y,5),(5)
(z,x,y,4)⇛w1=(z,x-1,y,1);  (z,x,y,6)⇛w2=(z,x,y+1,9);  (z,x,y,3)⇛w3=(z,x-1,y-1,2);  (z,x,y,2)⇛w4=(z,x+1,y+1,3).
The conditions for the one-to-all broadcasting of3PT(l,m,n) under MLA model are as follows.


### 3.2. Conditions for Using the MLA Model

Condition 1.
Perform broadcasting between modules via internal and dimensional edges as follows.(1)
(z,x,y,p0)→(z,x,y,p1)→(z,x,y,0); (z,x,y,p0)→(z,x,y,p2)→(z,x,y,5).
(2)(i)
Whenl= odd,
(4)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+⌊l2⌋)%l,x,y,5)⟶((z+⌊l2⌋)%l,x,y,0);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+⌈l2⌉)%l,x,y,0)⟶((z+⌈l2⌉)%l,x,y,5).(ii)
Whenl= even,
(5)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+l2)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+l2)%l,x,y,0).In (1), if p0=1 or 4 or 6 or 9, then remove the message transmission by (z,x,y,p0)→(z,x,y,p1), and if p1=0 or 5, then remove the message transmission by (z,x,y,p1)→(z,x,y,0 or 5).Condition 2.
All nodes located inside(zi,x,y) receive a message in the following order:(1)
(z,x,y,0)→(z,x,y,4); (z,x,y,0)→(z,x,y,1); (z,x,y,5)→(z,x,y,9); (z,x,y,5)→(z,x,y,6),(2)
(z,x,y,4)→(z,x,y,3); (z,x,y,4)→(z,x,y,7); (z,x,y,1)→(z,x,y,2); (z,x,y,1)→(z,x,y,8).Condition 3.
The modules that received a message through aLU-edge transmit the message in the following order, and the modules that received a message through a RD-, LD-, or RU-edge also transmit the message in a similar way to the following orders. However, when performing Condition 3, if the modules to receive a message already had the message, the message is not sent to the modules:(1)
(z,x,y,8)→(z,x,y,7);  (z,x,y,8)→(z,x,y,1);  (z,x,y,8)→(z,x,y,9),(2)
(z,x,y,7)⇛w0=(z,x-1,y+1,8);  (z,x,y,7)→(z,x,y,4);  (z,x,y,7)→(z,x,y,6);  (z,x,y,1)→(z,x,y,0);  (z,x,y,1)→(z,x,y,2);  (z,x,y,9)→(z,x,y,3);  (z,x,y,9)→(z,x,y,5),(3)
(z,x,y,4)⇛w1=(z,x-1,y,1);  (z,x,y,6)⇛w2=(z,x,y+1,9);  (z,x,y,3)⇛w3=(z,x-1,y-1,2);  (z,x,y,2)⇛w4=(z,x+1,y+1,3).Algorithm1 shows one-to-all broadcasting algorithm (OABA) of 3PT(l,m,n) under SLA and MLA models.Algorithm 1:One-to-all broadcasting algorithm of 3PT(l,m,n) under SLA and MLA models.
Step  1. Perform Condition 1 and 2.
Step  2. A message is transmitted from a source module with the message to eight modules adjacent to the source module
through an external edge.
Step  3. The modules that received a message via diagonal or reverse-diagonal edges perform Condition 3.
Step  4. Repeat Step  3 until the message is transmitted to all modules in 3PT(l,m,n).
Step  5. The node with the message transmit the message to other nodes in the same module using the broadcasting scheme in
[8] when its all eight adjacent modules (except for the modules connected via dimensional edges) already had the message.Figure2 shows an example of the one-to-all broadcasting among modules of (5,x,y) in 3PT(10,10,10) under SLA model. Numbers represent the arrival time of a message to the corresponding module, and numbers in parentheses represent the arrival time of a message to all nodes in the module. Arrows represent the processes of message transmission.Figure 2
Example of the one-to-all broadcasting among modules of(5,x,y) in 3PT(10,10,10) under SLA model.Theorem 4.
The one-to-all broadcasting time of the Petersen-torus network3PT(l,m,n) is 2⌊l/2⌋+2⌊m/2⌋+15 when l= odd and l+2⌊m/2⌋+14 when l= even under SLA model.Proof.
It is proven by dividing the broadcasting time into three cases depending on the number of edge types used for broadcasting.
Case  1. Consider the case when broadcasting is performed via internal edges, dimensional edges, and only one external edge, such as LU-, RD-, LD-, or RU-edges.
The maximum broadcasting time for Condition 1 is3+⌊l/2⌋+⌊l/2⌋ when l= odd and 3+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 3. The maximum broadcasting time via external edges except dimensional edges, such as LU-, RD-, LD-, or RU-edges, is ⌊m/2⌋. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-1. The internal broadcasting time for the destination module is 4 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+9 when l= odd and l+2⌊m/2⌋+8 when l= even.
Case  2. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of two types of external edges, for example, LU-edge and latitudinal edges, or LU-edge and RU-edges.
We assume that the two edges used areLU-edge and longitudinal edges. The maximum broadcasting time for Condition 1 is 3+⌊l/2⌋+⌊l/2⌋ when l= odd and 3+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 3. The maximum broadcasting time via LU-edge and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms is 4 because the interior of Ms, which receives a message via a LU-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-2. The internal broadcasting time for the destination module is 4 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+12 when l= odd and l+2⌊m/2⌋+11 when l= even.
Case  3. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of three types of external edges, for example, LU-edge, LD-edge, and latitudinal edges.
We assume that the two edges used areLU-edge, LD-edge, and latitudinal edges. The maximum broadcasting time for Condition 1 is 3+⌊l/2⌋+⌊l/2⌋ when l= odd and 3+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 3. The maximum broadcasting time via LU-edge, LD-edge, and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms1 is 4 because the interior of Ms1, which receives a message via a LU-edge and transmits the message to adjacent modules through a LD-edge, must meet Condition 3. The internal broadcasting time of module Ms2 is 4 because the interior of Ms2, which receives a message via a LD-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-3. The internal broadcasting time for the destination module is 4 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+15 when l= odd and l+2⌊m/2⌋+14 when l= even.Theorem 5.
The one-to-all broadcasting time of the Petersen-torus network3PT(l,m,n) is 2⌊l/2⌋+2⌊m/2⌋+7 when  l= odd and l+2⌊m/2⌋+6 when  l= even under MLA model.Proof.
It is proven by dividing the broadcasting time into three cases depending on the number of edge types used for broadcasting.
Case  1. Consider the case when broadcasting is performed via internal edges, dimensional edges, and only one external edge, such as LU-, RD-, LD-, or RU-edges.
The maximum broadcasting time for Condition 1 is2+⌊l/2⌋+⌊l/2⌋ when l= odd and 2+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 2. The maximum broadcasting time via external edges except dimensional edges, such as LU-, RD-, LD-, or RU-edges is ⌊m/2⌋. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-1. The internal broadcasting time for the destination module is 2 under MLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+5 when l= odd and l+2⌊m/2⌋+4 when l= even.
Case  2. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of two types of external edges, for example, LU-edge and latitudinal edges, or LU-edge and RU-edges.
We assume that the two edges used areLU-edge and longitudinal edges. The maximum broadcasting time for Condition 1 is 2+⌊l/2⌋+⌊l/2⌋ when l= odd and 2+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 2. The maximum broadcasting time via LU-edge and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms is 2 because the interior of Ms, which receives a message via a LU-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-2. The internal broadcasting time for the destination module is 2 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+6 when l= odd and l+2⌊m/2⌋+5 when l= even.
Case  3. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of three types of external edges, for example, LU-edge, LD-edge, and latitudinal edges.
We assume that the two edges used areLU-edge, LD-edge, and latitudinal edges. The maximum broadcasting time for Condition 1 is 2+⌊l/2⌋+⌊l/2⌋ when l= odd and 2+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 2. The maximum broadcasting time via LU-edge, LD-edge, and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms1 is 2 because the interior of Ms1, which receives a message via a LU-edge and transmits the message to adjacent modules through a LD-edge, must meet Condition 3. The internal broadcasting time of module Ms2 is 2 because the interior of Ms2, which receives a message via a LD-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-3. The internal broadcasting time for the destination module is 2 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+7 when l= odd and l+2⌊m/2⌋+6 when l= even.


## 3.1. Conditions for the One-to-All Broadcasting of 3 PT(l,m,n) under SLA Mode 1

Condition 1.
Perform broadcasting between modules via internal and dimensional edges as follows.(1)
(z,x,y,p0)→(z,x,y,p1)→(z,x,y,0 or 5)→(z,x,y,5 or 0).
(2)(i)
Whenl= odd,
(2)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+⌊l2⌋)%l,x,y,5)⟶((z+⌊l2⌋)%l,x,y,0);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+⌈l2⌉)%l,x,y,0)⟶((z+⌈l2⌉)%l,x,y,5).(ii)
Whenl= even,
(3)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+l2)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+l2)%l,x,y,0).
In(1), if p0=1 or 4 or 6 or 9, then remove the message transmission by (z,x,y,p0)→(z,x,y,p1), and if p1=0 or 5, then remove the message transmission by (z,x,y,p1)→(z,x,y,0 or 5).Condition 2.
All nodes located inside(z,x,y) receive a message in the following order:(1)
(z,x,y,0)→(z,x,y,4); (z,x,y,5)→(z,x,y,9),(2)
(z,x,y,0)→(z,x,y,1); (z,x,y,4)→(z,x,y,3); (z,x,y,5)→(z,x,y,6); (z,x,y,9)→(z,x,y,8),(3)
(z,x,y,6)→(z,x,y,7); (z,x,y,3)→(z,x,y,2).Condition 3.
The modules that received a message through aLU-edge transmit the message in the following order, and the modules that received a message through a RD-, LD-, or RU-edge also transmit the message in a similar way to the following orders. However, when performing (5), if the modules to receive a message (i.e., the modules to which nodes w1, w2, w3, and w4 belong) already had the message, the message is not sent to the modules:(1)
(z,x,y,8)→(z,x,y,7),(2)
(z,x,y,7)⇛w0=(z,x-1,y+1,8);  (z,x,y,8)→(z,x,y,1),(3)
(z,x,y,8)→(z,x,y,9);  (z,x,y,7)→(z,x,y,4);  (z,x,y,1)→(z,x,y,0),(4)
(z,x,y,7)→(z,x,y,6);  (z,x,y,4)→(z,x,y,3);  (z,x,y,1)→(z,x,y,2);(z,x,y,0)→(z,x,y,5),(5)
(z,x,y,4)⇛w1=(z,x-1,y,1);  (z,x,y,6)⇛w2=(z,x,y+1,9);  (z,x,y,3)⇛w3=(z,x-1,y-1,2);  (z,x,y,2)⇛w4=(z,x+1,y+1,3).
The conditions for the one-to-all broadcasting of3PT(l,m,n) under MLA model are as follows.


## 3.2. Conditions for Using the MLA Model

Condition 1.
Perform broadcasting between modules via internal and dimensional edges as follows.(1)
(z,x,y,p0)→(z,x,y,p1)→(z,x,y,0); (z,x,y,p0)→(z,x,y,p2)→(z,x,y,5).
(2)(i)
Whenl= odd,
(4)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+⌊l2⌋)%l,x,y,5)⟶((z+⌊l2⌋)%l,x,y,0);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+⌈l2⌉)%l,x,y,0)⟶((z+⌈l2⌉)%l,x,y,5).(ii)
Whenl= even,
(5)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+l2)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+l2)%l,x,y,0).In (1), if p0=1 or 4 or 6 or 9, then remove the message transmission by (z,x,y,p0)→(z,x,y,p1), and if p1=0 or 5, then remove the message transmission by (z,x,y,p1)→(z,x,y,0 or 5).Condition 2.
All nodes located inside(zi,x,y) receive a message in the following order:(1)
(z,x,y,0)→(z,x,y,4); (z,x,y,0)→(z,x,y,1); (z,x,y,5)→(z,x,y,9); (z,x,y,5)→(z,x,y,6),(2)
(z,x,y,4)→(z,x,y,3); (z,x,y,4)→(z,x,y,7); (z,x,y,1)→(z,x,y,2); (z,x,y,1)→(z,x,y,8).Condition 3.
The modules that received a message through aLU-edge transmit the message in the following order, and the modules that received a message through a RD-, LD-, or RU-edge also transmit the message in a similar way to the following orders. However, when performing Condition 3, if the modules to receive a message already had the message, the message is not sent to the modules:(1)
(z,x,y,8)→(z,x,y,7);  (z,x,y,8)→(z,x,y,1);  (z,x,y,8)→(z,x,y,9),(2)
(z,x,y,7)⇛w0=(z,x-1,y+1,8);  (z,x,y,7)→(z,x,y,4);  (z,x,y,7)→(z,x,y,6);  (z,x,y,1)→(z,x,y,0);  (z,x,y,1)→(z,x,y,2);  (z,x,y,9)→(z,x,y,3);  (z,x,y,9)→(z,x,y,5),(3)
(z,x,y,4)⇛w1=(z,x-1,y,1);  (z,x,y,6)⇛w2=(z,x,y+1,9);  (z,x,y,3)⇛w3=(z,x-1,y-1,2);  (z,x,y,2)⇛w4=(z,x+1,y+1,3).Algorithm1 shows one-to-all broadcasting algorithm (OABA) of 3PT(l,m,n) under SLA and MLA models.Algorithm 1:One-to-all broadcasting algorithm of 3PT(l,m,n) under SLA and MLA models.
Step  1. Perform Condition 1 and 2.
Step  2. A message is transmitted from a source module with the message to eight modules adjacent to the source module
through an external edge.
Step  3. The modules that received a message via diagonal or reverse-diagonal edges perform Condition 3.
Step  4. Repeat Step  3 until the message is transmitted to all modules in 3PT(l,m,n).
Step  5. The node with the message transmit the message to other nodes in the same module using the broadcasting scheme in
[8] when its all eight adjacent modules (except for the modules connected via dimensional edges) already had the message.Figure2 shows an example of the one-to-all broadcasting among modules of (5,x,y) in 3PT(10,10,10) under SLA model. Numbers represent the arrival time of a message to the corresponding module, and numbers in parentheses represent the arrival time of a message to all nodes in the module. Arrows represent the processes of message transmission.Figure 2
Example of the one-to-all broadcasting among modules of(5,x,y) in 3PT(10,10,10) under SLA model.Theorem 4.
The one-to-all broadcasting time of the Petersen-torus network3PT(l,m,n) is 2⌊l/2⌋+2⌊m/2⌋+15 when l= odd and l+2⌊m/2⌋+14 when l= even under SLA model.Proof.
It is proven by dividing the broadcasting time into three cases depending on the number of edge types used for broadcasting.
Case  1. Consider the case when broadcasting is performed via internal edges, dimensional edges, and only one external edge, such as LU-, RD-, LD-, or RU-edges.
The maximum broadcasting time for Condition 1 is3+⌊l/2⌋+⌊l/2⌋ when l= odd and 3+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 3. The maximum broadcasting time via external edges except dimensional edges, such as LU-, RD-, LD-, or RU-edges, is ⌊m/2⌋. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-1. The internal broadcasting time for the destination module is 4 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+9 when l= odd and l+2⌊m/2⌋+8 when l= even.
Case  2. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of two types of external edges, for example, LU-edge and latitudinal edges, or LU-edge and RU-edges.
We assume that the two edges used areLU-edge and longitudinal edges. The maximum broadcasting time for Condition 1 is 3+⌊l/2⌋+⌊l/2⌋ when l= odd and 3+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 3. The maximum broadcasting time via LU-edge and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms is 4 because the interior of Ms, which receives a message via a LU-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-2. The internal broadcasting time for the destination module is 4 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+12 when l= odd and l+2⌊m/2⌋+11 when l= even.
Case  3. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of three types of external edges, for example, LU-edge, LD-edge, and latitudinal edges.
We assume that the two edges used areLU-edge, LD-edge, and latitudinal edges. The maximum broadcasting time for Condition 1 is 3+⌊l/2⌋+⌊l/2⌋ when l= odd and 3+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 3. The maximum broadcasting time via LU-edge, LD-edge, and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms1 is 4 because the interior of Ms1, which receives a message via a LU-edge and transmits the message to adjacent modules through a LD-edge, must meet Condition 3. The internal broadcasting time of module Ms2 is 4 because the interior of Ms2, which receives a message via a LD-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-3. The internal broadcasting time for the destination module is 4 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+15 when l= odd and l+2⌊m/2⌋+14 when l= even.Theorem 5.
The one-to-all broadcasting time of the Petersen-torus network3PT(l,m,n) is 2⌊l/2⌋+2⌊m/2⌋+7 when  l= odd and l+2⌊m/2⌋+6 when  l= even under MLA model.Proof.
It is proven by dividing the broadcasting time into three cases depending on the number of edge types used for broadcasting.
Case  1. Consider the case when broadcasting is performed via internal edges, dimensional edges, and only one external edge, such as LU-, RD-, LD-, or RU-edges.
The maximum broadcasting time for Condition 1 is2+⌊l/2⌋+⌊l/2⌋ when l= odd and 2+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 2. The maximum broadcasting time via external edges except dimensional edges, such as LU-, RD-, LD-, or RU-edges is ⌊m/2⌋. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-1. The internal broadcasting time for the destination module is 2 under MLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+5 when l= odd and l+2⌊m/2⌋+4 when l= even.
Case  2. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of two types of external edges, for example, LU-edge and latitudinal edges, or LU-edge and RU-edges.
We assume that the two edges used areLU-edge and longitudinal edges. The maximum broadcasting time for Condition 1 is 2+⌊l/2⌋+⌊l/2⌋ when l= odd and 2+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 2. The maximum broadcasting time via LU-edge and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms is 2 because the interior of Ms, which receives a message via a LU-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-2. The internal broadcasting time for the destination module is 2 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+6 when l= odd and l+2⌊m/2⌋+5 when l= even.
Case  3. Consider the case when broadcasting is performed via internal edges, dimensional edges, and the combination of three types of external edges, for example, LU-edge, LD-edge, and latitudinal edges.
We assume that the two edges used areLU-edge, LD-edge, and latitudinal edges. The maximum broadcasting time for Condition 1 is 2+⌊l/2⌋+⌊l/2⌋ when l= odd and 2+l/2+l/2-1 when l= even. The broadcasting time for Condition 2 is 2. The maximum broadcasting time via LU-edge, LD-edge, and longitudinal edges is ⌊m/2⌋. The internal broadcasting time of module Ms1 is 2 because the interior of Ms1, which receives a message via a LU-edge and transmits the message to adjacent modules through a LD-edge, must meet Condition 3. The internal broadcasting time of module Ms2 is 2 because the interior of Ms2, which receives a message via a LD-edge and transmits the message to adjacent modules through a longitudinal edge, must meet Condition 3. The maximum total value from performing (z,x,y,8)→(z,x,y,7) in each module of (z,x,y) except for the source and destination modules is ⌊m/2⌋-3. The internal broadcasting time for the destination module is 2 under SLA model by Lemma 3. Therefore, the broadcasting time for this case is 2⌊l/2⌋+2⌊m/2⌋+7 when l= odd and l+2⌊m/2⌋+6 when l= even.


## 4. All-to-All Broadcasting of 3PT(l,m,n)

To analyze the all-to-all broadcasting time of3PT(l,m,n), we first examine the all-to-all broadcasting time of the Petersen graph because the basic modules consisting of 3PT(l,m,n) are the Petersen graph. Algorithms 2 and 3 describe the all-to-all broadcasting algorithms for the Petersen graph based on the SLA model and the MLA model, respectively. Let a cycle consisting of the nodes {0,1,2,3,4} of the Petersen graph be A let and a cycle consisting of the nodes {5,6,7,8,9} of the Petersen graph be B.Algorithm 2:All-to-all broadcasting algorithm of Petersen graph under SLA model.
Step  1. A message is transmitted between nodes in each cycle. Each message is transmitted as follows and each message
transmission is accomplished simultaneously.
0
⟶
1
⟶
2
⟶
3
⟶
4; 1⟶2⟶3⟶4⟶0; 2⟶3⟶4⟶0⟶1;
3
⟶
4
⟶
0
⟶
1
⟶
2; 4⟶0⟶1⟶2⟶3; 5⟶6⟶7⟶8⟶9;
6
⟶
7
⟶
8
⟶
9
⟶
5; 7⟶8⟶9⟶5⟶6; 8⟶9⟶5⟶6⟶7;
9
⟶
5
⟶
6
⟶
7
⟶
8.
Step  2. All nodes located inside cycle A transmit the message to all nodes located inside cycle B.
Step  3. All nodes located inside cycle B transmit the message to all nodes located inside cycle A.Algorithm 3:All-to-all broadcasting algorithm of Petersen graph under MLA model.
Step  1. A message is transmitted between nodes in each cycle. Each message is transmitted as follows and each message
transmission is accomplished simultaneously.
0
⟶
1
⟶
2; 0⟶4⟶3; 1⟶2⟶3; 1⟶0⟶4; 2⟶3⟶4; 2⟶1⟶0;
3
⟶
4
⟶
0; 3⟶2⟶1; 4⟶0⟶1; 4⟶3⟶2; 5⟶6⟶7; 5⟶9⟶8;
6
⟶
7
⟶
8; 6⟶5⟶9; 7⟶8⟶9; 7⟶6⟶5; 8⟶9⟶5; 8⟶7⟶6;
9
⟶
5
⟶
6; 9⟶8⟶7.
Step  2. All nodes located inside cycle A transmit their message to all nodes located inside cycle B; at the same time, all nodes
located inside cycleB transmit their message to all nodes located inside cycle A.Therefore, the all-to-all broadcasting time of the Petersen graph under SLA model is 6, which is the sum of 4 (i.e., the number of messages transmitted between nodes in the interior of each cycle at Step 1 in Algorithm2) plus 2 (i.e., the number of messages transmitted between two cycles at Step 2 and Step 3 in Algorithm 2). The all-to-all broadcasting time of the Petersen graph under MLA model is 3 from the sum of 2 (i.e., the number of messages transmitted between nodes located inside each cycle at Step 1 in Algorithm 3) and 1 (i.e., the number of messages transmitted between two cycles at Step 2 Algorithm 3). Consequently, the following lemma is proven.Lemma 6.
The all-to-all broadcasting time of the Petersen graph is 6 under SLA model and 3 under MLA model.Algorithms4 and 5 describe the all-to-all broadcasting algorithms for 3PT(l,m,n) based on the SLA model and the MLA model, respectively.Algorithm 4:All-to-all broadcasting algorithm of 3PT(l,m,n) under SLA model.
Step  1. Perform broadcasting among nodes located inside each module using the all-to-all broadcasting algorithm for the
Petersen graph with the SLA model in Algorithm2.
Step  2. Every module performs the following broadcasting via internal and latitudinal edges.
(
z
,
x
,
y
,
1
)
⇛
(
z
,
(
x
+
1
)
%
m
,
y
,
4
)
⟶
(
z
,
(
x
+
1
)
%
m
,
y
,
0
)
⟶
(
z
,
(
x
+
1
)
%
m
,
y
,
1
)
⇛
(
z
,
(
x
+
2
)
%
m
,
y
,
4
)
⟶
(
z
,
(
x
+
2
)
%
m
,
y
,
0
)
⟶
(
z
,
(
x
+
2
)
%
m
,
y
,
1
)
⇛
⋯
⇛
(
z
,
(
x
-
1
)
%
m
,
y
,
4
)
⟶
(
z
,
(
x
-
1
)
%
m
,
y
,
2
)
⟶
(
z
,
(
x
-
1
)
%
m
,
y
,
6
).
Step  3. Every module performs the following broadcasting via internal and longitudinal edges.
(
z
,
x
,
y
,
6
)
⇛
(
z
,
x
,
(
y
+
1
)
%
n
,
9
)
⟶
(
z
,
x
,
(
y
+
1
)
%
n
,
5
)
⟶
(
z
,
x
,
(
y
+
1
)
%
n
,
6
)
⇛
(
z
,
x
,
(
y
+
2
)
%
n
,
9
)
⟶
(
z
,
x
,
(
y
+
2
)
%
n
,
5
)
⟶
(
z
,
x
,
(
y
+
2
)
%
n
,
6
)
⇛
⋯
⇛
(
z
,
x
,
(
y
-
1
)
%
n
,
9
)
⟶
(
z
,
x
,
(
y
-
1
)
%
n
,
5
).
Step  4. Every module performs the following broadcasting via internal and dimentional edges.
(
z
,
x
,
y
,
5
)
⇛
(
(
z
-
1
)
%
l
,
x
,
y
,
0
)
⟶
(
(
z
-
1
)
%
l
,
x
,
y
,
5
)
⇛
(
(
z
-
2
)
%
l
,
x
,
y
,
0
)
⟶
(
(
z
-
2
)
%
l
,
x
,
y
,
5
)
⇛
⋯
⇛
(
(
z
+
1
)
%
l
,
x
,
y
,
0
).
Step  5. Perform broadcasting among nodes located inside each module using the all-to-all broadcasting algorithm for the
Petersen graph with the SLA model in Algorithm2.Algorithm 5:All-to-all broadcasting algorithm of 3PT(l,m,n) under MLA model.
Step  1. Perform broadcasting among nodes located inside each module using the all-to-all broadcasting algorithm for the
Petersen graph with the MLA model in Algorithm3.
Step  2. Perform Condition 1.
Step  3. Perform Condition 2.
Step  4. Perform Condition 3.
Step  5. Perform broadcasting among nodes located inside each module using the all-to-all broadcasting algorithm for the
Petersen graph with the MLA model in Algorithm3.The all-to-all broadcasting time of3PT(l,m,n) under SLA model is as follows. Step 1 takes 6 from Lemma 6. The broadcasting time taken at Step 2 is 3m-3 from the number of broadcasts by internal edges 2(m-1) plus those by longitudinal edges m-1. The broadcasting time taken at Step 3 is 3n-4 from the number of broadcasts by internal edges 2(n-2)+1 plus those by latitudinal edges n-1. The broadcasting time taken at Step 4 is 2l-3 from the number of broadcasts by internal edges l-2 plus those by dimensional edges l-1. The number of broadcasts at Step 5 is 6 from Lemma 6. Therefore, the all-to-all broadcasting time of 3PT(l,m,n) under SLA model is 6+(3m-3)+(3n-4)+(2l-3)+6=3m+3n+2l+2. Consequently, the following theorem is proven.Theorem 7.
The all-to-all broadcasting time of3PT(l,m,n) under SLA model is  3m+3n+2l+2.Figure3 shows an example of Steps 2 and 3 of the all-to-all broadcasting in 3PT(l,3,3) under SLA model. Here, we have not drawn the external edges of 3PT(l,3,3) because of the complexity of the graph. The arrows represent the processes of message transfer.Figure 3
Example of Steps 2 and 3 of the all-to-all broadcasting in3PT(l,3,3) under SLA model.The conditions for the all-to-all broadcasting of3PT(l,m,n) under MLA model are as follows.


### 4.1. Conditions for Using the MLA Model

Condition 1.
Every module performs the following broadcasting via internal and latitudinal edges.(1)(i)
Whenm= odd,
(6)(z,x,y,1)⇛(z,(x+1)%m,y,4)⟶(z,(x+1)%m,y,0)⟶(z,(x+1)%m,y,1)⇛(z,(x+2)%m,y,4)⟶(z,(x+2)%m,y,0)⟶(z,(x+2)%m,y,1)⇛⋯⇛(z,(x+⌊m2⌋)%m,y,4)⟶(z,(x+⌊m2⌋)%m,y,7)⟶(z,(x+⌊m2⌋)%m,y,6);(z,x,y,4)⇛(z,(x-1)%m,y,1)⟶(z,(x-1)%m,y,0)⟶(z,(x-1)%m,y,4)⇛(z,(x-2)%m,y,1)⟶(z,(x-2)%m,y,0)⟶(z,(x-2)%m,y,4)⇛⋯⇛(z,(x+⌈m2⌉)%m,y,1)⟶(z,(x+⌈m2⌉)%m,y,8)⟶(z,(x+⌈m2⌉)%m,y,9).(ii)
Whenm= even,
(7)(z,x,y,1)⇛(z,(x+1)%m,y,4)⟶(z,(x+1)%m,y,0)⟶(z,(x+1)%m,y,1)⇛(z,(x+2)%m,y,4)⟶(z,(x+2)%m,y,0)⟶(z,(x+2)%m,y,1)⇛⋯⇛(z,(x+m2)%m,y,1)⟶(z,(x+m2)%m,y,7)⟶(z,(x+m2)%m,y,6);(z,x,y,4)⇛(z,(x-1)%m,y,1)⟶(z,(x-1)%m,y,0)⟶(z,(x-1)%m,y,4)⇛(z,(x-2)%m,y,1)⟶(z,(x-2)%m,y,0)⟶(z,(x-2)%m,y,4)⇛⋯⇛(z,(x+m2)%m,y,1)⟶(z,(x+m2)%m,y,8)⟶(z,(x+m2)%m,y,9).Condition 2.
Every module performs the following broadcasting via internal and longitudinal edges.(2)(i)
Whenn= odd,
(8)(z,x,y,6)⇛(z,x,(y+1)%n,9)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,6)⇛(z,x,(y+2)%n,9)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,6)⇛⋯⇛(z,x,(y+⌊n2⌋)%n,9)⟶(z,x,(y+⌊n2⌋)%n,5);(z,x,y,9)⇛(z,x,(y+1)%n,6)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,9)⇛(z,x,(y+2)%n,6)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,9)⇛⋯⇛(z,x,(y+⌈n2⌉)%n,6)⟶(z,x,(y+⌈n2⌉)%n,5).(ii)
Whenn= even,
(9)(z,x,y,6)⇛(z,x,(y+1)%n,9)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,6)⇛(z,x,(y+2)%n,9)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,6)⇛⋯⇛(z,x,(y+n2)%n,9)⟶(z,x,(y+n2)%n,5);(z,x,y,9)⇛(z,x,(y+1)%n,6)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,9)⇛(z,x,(y+2)%n,6)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,9)⇛⋯⇛(z,x,(y+n2)%n,6)⟶(z,x,(y+n2)%n,5).Condition 3.
Every module performs the following broadcasting via internal and dimensional edges.(3)(i)
Whenl= odd,
(10)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+⌊l2⌋)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+⌈l2⌉)%l,x,y,0).(3)(ii)
Whenl= even,
(11)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+l2)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+l2)%l,x,y,0).The all-to-all broadcasting time of3PT(l,m,n) under MLA model is as follows. Step 1 takes 3 from Lemma 6. The broadcasting time taken at Step 2 is 3⌊m/2⌋ when m is odd from the number of broadcasts by internal edges 2⌊m/2⌋ plus the number of broadcasts by longitudinal edges ⌊m/2⌋ and is 3m/2 when m is even from the number of broadcasts by internal edges m plus the number of broadcasts by longitudinal edges m/2. The broadcasting time taken at Step 3 is 3⌊n/2⌋-1 when n is odd from the number of broadcasts by internal edges 2⌊n/2⌋-1 plus the number of broadcasts by latitudinal edges ⌊n/2⌋ and is 3n/2-1 when n is even from the number of broadcasts by internal edges n plus the number of broadcasts by longitudinal edges n/2. The broadcasting time taken at Step 4 is 2⌊l/2⌋-1 when l is odd from the number of broadcasts by internal edges ⌊l/2⌋-1 plus the number of broadcasts by dimensional edges ⌊l/2⌋ and is l-1 when l is even from the number of broadcasts by internal edges l/2-1 plus the number of broadcasts by longitudinal edges l/2. The number of broadcasts at Step 5 is 3 from Lemma 6. Therefore, the all-to-all broadcasting time of 3PT(l,m,n) under MLA model is 3⌊m/2⌋+3⌊n/2⌋+2⌊l/2⌋+4 when m, n, and l are odd and is 3m/2+3n/2+l+4 when m, n, and l are even. Consequently, Theorem 8 is proven for the all-to-all broadcasting algorithms of 3PT(l,m,n) under MLA model.Theorem 8.
The all-to-all broadcasting time of3PT(l,m,n) under SLA model is 3⌊m/2⌋+3⌊n/2⌋+2⌊l/2⌋+4 when m, n, and  l are odd and is  3m/2+3n/2+l+4 when m, n, and  l are even.


## 4.1. Conditions for Using the MLA Model

Condition 1.
Every module performs the following broadcasting via internal and latitudinal edges.(1)(i)
Whenm= odd,
(6)(z,x,y,1)⇛(z,(x+1)%m,y,4)⟶(z,(x+1)%m,y,0)⟶(z,(x+1)%m,y,1)⇛(z,(x+2)%m,y,4)⟶(z,(x+2)%m,y,0)⟶(z,(x+2)%m,y,1)⇛⋯⇛(z,(x+⌊m2⌋)%m,y,4)⟶(z,(x+⌊m2⌋)%m,y,7)⟶(z,(x+⌊m2⌋)%m,y,6);(z,x,y,4)⇛(z,(x-1)%m,y,1)⟶(z,(x-1)%m,y,0)⟶(z,(x-1)%m,y,4)⇛(z,(x-2)%m,y,1)⟶(z,(x-2)%m,y,0)⟶(z,(x-2)%m,y,4)⇛⋯⇛(z,(x+⌈m2⌉)%m,y,1)⟶(z,(x+⌈m2⌉)%m,y,8)⟶(z,(x+⌈m2⌉)%m,y,9).(ii)
Whenm= even,
(7)(z,x,y,1)⇛(z,(x+1)%m,y,4)⟶(z,(x+1)%m,y,0)⟶(z,(x+1)%m,y,1)⇛(z,(x+2)%m,y,4)⟶(z,(x+2)%m,y,0)⟶(z,(x+2)%m,y,1)⇛⋯⇛(z,(x+m2)%m,y,1)⟶(z,(x+m2)%m,y,7)⟶(z,(x+m2)%m,y,6);(z,x,y,4)⇛(z,(x-1)%m,y,1)⟶(z,(x-1)%m,y,0)⟶(z,(x-1)%m,y,4)⇛(z,(x-2)%m,y,1)⟶(z,(x-2)%m,y,0)⟶(z,(x-2)%m,y,4)⇛⋯⇛(z,(x+m2)%m,y,1)⟶(z,(x+m2)%m,y,8)⟶(z,(x+m2)%m,y,9).Condition 2.
Every module performs the following broadcasting via internal and longitudinal edges.(2)(i)
Whenn= odd,
(8)(z,x,y,6)⇛(z,x,(y+1)%n,9)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,6)⇛(z,x,(y+2)%n,9)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,6)⇛⋯⇛(z,x,(y+⌊n2⌋)%n,9)⟶(z,x,(y+⌊n2⌋)%n,5);(z,x,y,9)⇛(z,x,(y+1)%n,6)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,9)⇛(z,x,(y+2)%n,6)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,9)⇛⋯⇛(z,x,(y+⌈n2⌉)%n,6)⟶(z,x,(y+⌈n2⌉)%n,5).(ii)
Whenn= even,
(9)(z,x,y,6)⇛(z,x,(y+1)%n,9)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,6)⇛(z,x,(y+2)%n,9)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,6)⇛⋯⇛(z,x,(y+n2)%n,9)⟶(z,x,(y+n2)%n,5);(z,x,y,9)⇛(z,x,(y+1)%n,6)⟶(z,x,(y+1)%n,5)⟶(z,x,(y+1)%n,9)⇛(z,x,(y+2)%n,6)⟶(z,x,(y+2)%n,5)⟶(z,x,(y+2)%n,9)⇛⋯⇛(z,x,(y+n2)%n,6)⟶(z,x,(y+n2)%n,5).Condition 3.
Every module performs the following broadcasting via internal and dimensional edges.(3)(i)
Whenl= odd,
(10)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+⌊l2⌋)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+⌈l2⌉)%l,x,y,0).(3)(ii)
Whenl= even,
(11)(z,x,y,0)⇛((z+1)%l,x,y,5)⟶((z+1)%l,x,y,0)⇛((z+2)%l,x,y,5)⟶((z+2)%l,x,y,0)⇛⋯⇛((z+l2)%l,x,y,5);(z,x,y,5)⇛((z-1)%l,x,y,0)⟶((z-1)%l,x,y,5)⇛((z-2)%l,x,y,0)⟶((z-2)%l,x,y,5)⇛⋯⇛((z+l2)%l,x,y,0).The all-to-all broadcasting time of3PT(l,m,n) under MLA model is as follows. Step 1 takes 3 from Lemma 6. The broadcasting time taken at Step 2 is 3⌊m/2⌋ when m is odd from the number of broadcasts by internal edges 2⌊m/2⌋ plus the number of broadcasts by longitudinal edges ⌊m/2⌋ and is 3m/2 when m is even from the number of broadcasts by internal edges m plus the number of broadcasts by longitudinal edges m/2. The broadcasting time taken at Step 3 is 3⌊n/2⌋-1 when n is odd from the number of broadcasts by internal edges 2⌊n/2⌋-1 plus the number of broadcasts by latitudinal edges ⌊n/2⌋ and is 3n/2-1 when n is even from the number of broadcasts by internal edges n plus the number of broadcasts by longitudinal edges n/2. The broadcasting time taken at Step 4 is 2⌊l/2⌋-1 when l is odd from the number of broadcasts by internal edges ⌊l/2⌋-1 plus the number of broadcasts by dimensional edges ⌊l/2⌋ and is l-1 when l is even from the number of broadcasts by internal edges l/2-1 plus the number of broadcasts by longitudinal edges l/2. The number of broadcasts at Step 5 is 3 from Lemma 6. Therefore, the all-to-all broadcasting time of 3PT(l,m,n) under MLA model is 3⌊m/2⌋+3⌊n/2⌋+2⌊l/2⌋+4 when m, n, and l are odd and is 3m/2+3n/2+l+4 when m, n, and l are even. Consequently, Theorem 8 is proven for the all-to-all broadcasting algorithms of 3PT(l,m,n) under MLA model.Theorem 8.
The all-to-all broadcasting time of3PT(l,m,n) under SLA model is 3⌊m/2⌋+3⌊n/2⌋+2⌊l/2⌋+4 when m, n, and  l are odd and is  3m/2+3n/2+l+4 when m, n, and  l are even.


## 5. Conclusion

Broadcasting is one of the major primitives with the scope for improving the performance of interconnection networks and is significantly influenced by broadcasting algorithms. In this paper, we proposed and analyzed algorithms for one-to-all and all-to-all broadcasting in3PT(l,m,n) under SLA and MLA models. The results are as follows. (1) The one-to-all broadcasting time in 3PT(l,m,n) under SLA model can be accomplished in 2⌊l/2⌋+2⌊m/2⌋+15 when l= odd and l+2⌊m/2⌋+14 when l= even. (2) The one-to-all broadcasting time in 3PT(l,m,n) under MLA model can be accomplished in 2⌊l/2⌋+2⌊m/2⌋+7 when l= odd and l+2⌊m/2⌋+6 when l= even. (3) The all-to-all broadcasting time in 3PT(l,m,n) under SLA model can be accomplished in 3m+3n+2l+2.  (4) The all-to-all broadcasting time in 3PT(l,m,n) under SLA model can be accomplished in 3⌊m/2⌋+3⌊n/2⌋+2⌊l/2⌋+4 when m, n, and l are odd and is 3m/2+3n/2+l+4 when m, n, and l are even. Therefore, the broadcasting methods reported here are expected to be extremely useful for the analysis of the properties of 3PT(l,m,n), including wormhole-routing and wormhole-broadcasting.



---

*Source: 935737-2014-04-10.xml*