1994 International Conference on Parallel Processing A NE W TAG SCHEM E AN D ITS TRE E REPRESENTATIO N FO R A SHUFFLE-EXCHANG E NETWOR K 1
Tse-Yun Feng, Yanggon Kim · 1994
This paper introduces a new tag scheme having a flexibility and a bidirectionality for an N × N k-stage shuffle-exchange network where k > log2TV. Based on the interstage correlations for a path, the EB-tag generating rules are presented. In addition, an elegant and simple graphical representation called a N- leaf Dual Complete Binary tree (N-leaf DCB-tree) for a given permutation is proposed and its characteristics are discussed. Then the universal necessary condition for a conflict-free connection pattern is given. Due to this condition, the conflict-free routing problem can be transformed to the perfect assignment problem.