Browsing by Author "Liu, Victor W."

Now showing 1 - 2 of 2

Improved upper and lower bounds on the optimization of mixed chordal ring networks
(2009-06-15)
Lan, James K.
;
Liu, Victor W.
;
Chen, Chiuyuan
;
應用數學系
;
Department of Applied Mathematics
Recently, Chen, Hwang and Liu [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] introduced the mixed chordal ring network as a topology for interconnection networks. In particular, they showed that the amount of hardware and the network structure of the mixed chordal ring network are very comparable to the (directed) double-loop network, yet the mixed chordal ring network can achieve a better diameter than the double-loop network. More the mixed chordal ring network can achieve diameter about root 2N as compared precisely, to root 3N for the (directed) double-loop network, where N is the number of nodes in the network. One of the most important questions in interconnection networks is, for a given number of nodes, how to find an optimal network (a network with the smallest diameter) and give the construction of such a network. Chen et al. [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16] gave upper and lower bounds for such an optimization problem oil the mixed chordal ring network. In this paper, we improve the upper and lower bounds as 2[root N/2] +1 and [root 2N - 3/2], respectively. In addition, we correct some deficient contexts in [S.K. Chen, F.K. Hwang, Y.C. Liu, Some combinatorial properties of mixed chordal rings, J. Interconnection Networks 1 (2003) 3-16]. (C) 2009 Elsevier B.V. All rights reserved.
Optimal all-to-all personalized exchange in d-nary banyan multistage interconnection networks
(2007-10-01)
Liu, Victor W.
;
Chen, Chiuyuan
;
Chen, Richard B.
;
應用數學系
;
Department of Applied Mathematics
All-to-all personalized exchange occurs in many important applications in parallel processing. In the past two decades, algorithms for all-to-all personalized exchange were mainly proposed for hypercubes, meshes, and tori. Recently, Yang and Wang (IEEE Trans Parallel Distrib Syst 11:261-274, 2000) proposed an optimal all-to-all personalized exchange algorithm for binary (each switch is of size 2x2) banyan multistage interconnection networks. It was pointed out in Massini (Discret Appl Math 128:435-446, 2003) that the algorithm in Yang, Wang (IEEE Trans Parallel Distrib Syst 11:261-274, 2000) depends on the network topologies and requires pre-computation and memory allocation for a Latin square. Thus in (Discret Appl Math 128:435-446, 2003), Massini proposed a new optimal algorithm, which is independent of the network topologies and does not require pre-computation or memory allocation for a Latin square. Unfortunately, Massini's algorithm has a flaw and does not realize all-to-all personalized exchange. In this paper, we will correct the flaw and generalize Massini's algorithm to be applicable to d-nary (each switch is of size dxd) banyan multistage interconnection networks.