TY - JOUR

T1 - Path establishment of permutations in a rearrangeable interconnection network

AU - Hsu, Chiun Chieh

AU - Lin Shun-Shi, Shun-Shi

PY - 1999/12/1

Y1 - 1999/12/1

N2 - One of the most widely used parallel systems is the one which uses a multistage interconnection network to connect processors and memory modules, such as Omega and inverse Omega (denoted as Omega-1) networks. Appending an Omega network to an Omega-1 network becomes an Omega-1.Omega network. This paper aims at establishing paths for routing an arbitrary permutation in a (2log2 N-1) stage Omega-1.Omega network. First, we present the set of permutations which can be realized in an Omega network. The path establishment for such an Omega-passable permutation can be easily achieved by using top or bottom control. Secondly, an approach is developed to rearrange an arbitrary input permutation in an Omega-1 network such that the output permutation turns out to be an Omega-passable permutation. It is also shown that removing the last stage in Omega-1 network has no influence on this rearrangement result. Henceforth, an arbitrary permutation can be realized in the reduced (2log2 N-1) stage Omega-1.Omega network. Based on the results presented in this paper, it will be shown that several networks are also rearrangeable by using the lemmas and theorems presented by Abdennadher and Feng1.

AB - One of the most widely used parallel systems is the one which uses a multistage interconnection network to connect processors and memory modules, such as Omega and inverse Omega (denoted as Omega-1) networks. Appending an Omega network to an Omega-1 network becomes an Omega-1.Omega network. This paper aims at establishing paths for routing an arbitrary permutation in a (2log2 N-1) stage Omega-1.Omega network. First, we present the set of permutations which can be realized in an Omega network. The path establishment for such an Omega-passable permutation can be easily achieved by using top or bottom control. Secondly, an approach is developed to rearrange an arbitrary input permutation in an Omega-1 network such that the output permutation turns out to be an Omega-passable permutation. It is also shown that removing the last stage in Omega-1 network has no influence on this rearrangement result. Henceforth, an arbitrary permutation can be realized in the reduced (2log2 N-1) stage Omega-1.Omega network. Based on the results presented in this paper, it will be shown that several networks are also rearrangeable by using the lemmas and theorems presented by Abdennadher and Feng1.

KW - Inverse Omega network

KW - Omega network

KW - Permutation

KW - Rearrangeability

UR - http://www.scopus.com/inward/record.url?scp=0033185107&partnerID=8YFLogxK

UR - http://www.scopus.com/inward/citedby.url?scp=0033185107&partnerID=8YFLogxK

M3 - Article

AN - SCOPUS:0033185107

VL - 14

SP - 267

EP - 274

JO - Computer Systems Science and Engineering

JF - Computer Systems Science and Engineering

SN - 0267-6192

IS - 5

ER -