On the correctness of inside-out routing algorithm

Author

Kim, M.K. ; Yoon, H. ; Maeng, S.R.

Author_Institution

Dept. of Comput. Eng., Woosuk Univ., Cheonbuk, South Korea

Volume

46

Issue

7

fYear

1997

fDate

7/1/1997 12:00:00 AM

Firstpage

820

Lastpage

823

Abstract

Recently, a new routing algorithm called inside-out routing algorithm was proposed for routing an arbitrary permutation in the omega-based 2log₂ N stage networks. This paper discusses the problems of the inside-out routing algorithm and shows that the suggested condition for proper routing in the omega-omega network is insufficient. An extended necessary and sufficient condition for proper routing in the omega-omega network is also suggested. However, it is unknown if any permutation can be successfully routed by a heuristic algorithm which follows the condition. Thus, the rearrangeability of the omega-omega network still remains an open problem

Keywords

heuristic programming; multiprocessor interconnection networks; network routing; sorting; arbitrary permutation; heuristic algorithm; inside-out routing algorithm correctness; necessary and sufficient condition; omega-based 2log₂ N stage networks; omega-omega network; routing algorithm; Computer science; Heuristic algorithms; Image converters; Mirrors; Multiprocessor interconnection networks; Routing; Sufficient conditions;

fLanguage

English

Journal_Title

Computers, IEEE Transactions on

Publisher

ieee

ISSN

0018-9340

Type

jour

DOI

10.1109/12.599903

Filename

599903