In this paper, we study the following node-to-node and node-to-set routing problems in r-dimensional torus Trn with r 2 and n 4 nodes in each dimension: given at most 2r - 1 faulty nodes and non-faulty nodes s and t in Trn, find a fault-free path s t; and given at most 2r - k faulty nodes and non-faulty nodes s and t1,..., tk in Trn, find k fault-free node-disjoint paths s ti, 1 i k. We give an O(r2) time algorithm which finds a fault-free path s t of length at most d(Trn) + 1 for the node-to-node routing, where d(Trn) is the diameter of Trn. For node-to-set routing, we show an O(r3) time algorithm which finds k fault-free node-disjoint paths s ti, 1 i k, of length at most d(Trn) + 1. The upper bounds on the length of the found paths are optimal. From this, Rabin diameter of Trn is d(Trn) + 1.

The recent advance of semiconductor technologies enable to produce a medium size of crossbar with reasonable cost. By making the best use of the high bandwidth of such crossbars, indirect networks including the base-m n-cube and HyperCross have been proposed and researched. In these networks, a node is connected other nodes through crossbars in multiple dimensions. Although these networks are practically used in commercial machines, almost no discussion on a class of networks including them has been done. In this paper, a network class called Multi-Dimensional X'bar (MDX) which includes the above two networks is defined. Several new networks in this class are proposed, and relationship between these networks and direct networks/multistage interconnection networks is discussed. Finally, routing methods for these new networks are proposed and the average distance is evaluated. Through the discussion and evaluation, the MDX supports higher bandwidth than the corresponding multistage interconnection network with smaller hardware than the corresponding direct network.

A mesh spiral network (MSnet) and a mesh random (MRnet) are proposed. The MSnet consists of the 2-D torus and bypass links that keep the degree at six. The MRnet consists of the 2-D torus and random bypass links that keep the degree at six. The diameter and the average distance are calculated by using a computer program. The cost of the MSnet is slightly higher than that of the de Bruijn graph, and is about the same as the Star graph. The cost of the MRnet is better than that of the de Bruijn graph. The MSnet is proven to be maximally fault-tolerant. The upper bound of the MRnet size is also discussed.

This paper discusses a massively parallel interconnection scheme for multithreaded architecture and introduces a new class of direct interconnection networks called the hierarchical Multidimensional Directed Cycles Ensemble (hMDCE). Its suitability for massively parallel systems is discussed. The network is evolved from the Multidimensional Directed Cycles Ensemble (MDCE) network, where each node is substituted by lower-level sub-networks. The new network addresses some serious problems caused by the increasing scale of parallel systems, such as longer latency, limited throughput and high implementation cost. This paper first introduces the MDCE network and then presents and examines in detail the hierarchical MDCE network. Bisection bandwidth of hMDCE is considerably reduced from its ancestor MDCE and the network performs significantly higher throughput and lower latency under some practical implementation constraints. The gate count and delay time of the compiled circuit for the routing function are insignificant. These results reveal that the hMDCE network is an important candidate for massively parallel systems interconnection.

This paper proposes new algorithms for diagnosing (detection, identification and location) baseline multistage interconnection networks (MIN) as one of the basic units in a massively parallel system. This is accomplished in the presence of single and multiple faults under a new fault model. This model referred to as the geometric fault model, considers defective crossing connections which are located between adjacent stages, internally to the MIN (therefore, a fault corresponds to a physical bridge fault between two connections). It is shown that this type of fault affects the correct geometry of the network, thus requiring a different testing approach than previous methods. Initially, an algorithm which detects the presence of bridge faults (both in the single and multiple fault cases), is presented. For a single bridge fault, the proposed algorithm locates the fault except in an unique pathological case under which it is logically impossible to differentiate between two equivalent locations of the fault (however, the switching element affected by this fault is uniquely located). The proposed algorithm requires log2 N test vectors to diagnose the MIN as fault free (where N is the number of input lines to the MIN). For fully diagnosing a single bridge fault, this algorithm requires at most 2 log2 N tests and terminates when multiple bridge faults are detected. Subsequently, an algorithm which locates all bridge faults is given. The number of required test vectors is O(N). Fault location of each bridge fault is accomplished in terms of the two lines in the bridge and the numbers of the stages between which it occurs. Illustrative examples are given.

A miniature transceiver, including highly integrated MMIC front-end, for 1.9 GHz band personal handy phone system(PHS) has been developed. The terminal, adopting direct conversion transmitter and receiver technology, consists of four high-density RF circuit modules and a digital signal processing LSI with 2.7 V power supply. The four functional modules are a power amplifier, a transmitter,a receiver, and a frequency synthesizer. Each functional module includes one IC chip and passive LCR components connected with solder bumps on module substrate. The experimental miniature PHS handset has been fabricated to verify the design concepts of the miniature transceiver. The total volume of the developed PHS terminal is 60cc, including the 12cc front-end which comprises the four RF functional circuit modules. The air interface connection with the PHS base station simulator has been confirmed.

We have developed inlaid copper interconnects employing amorphous Ti-Si-N barrier metal. The interconnect resistivity is 1.90.1 µΩcm. Ti-Si-N films were shown to be amorphous by X-ray diffraction measurements. The amorphous structure was thermal stable, even after annealing at 600 for 30 minutes in an Ar ambient. The atomic composition of the film was identified as Ti : Si : N=1 : 0.6 : 1.6. The films were found to be under tensile stress of 0.3 Gpa. The resistivity is about 0.5 mΩcm at room temperature. The diffusion barrier characteristics were evaluated by n+/p and p+/n junction leakage measurements. No degradation of leakage characteristics was observed for these diodes, even after annealing at 600 for 30 minutes in an N2/H2 ambient. The amorphous Ti-Si-N barrier metal is a promising candidate for application in deep-submicron high-speed ULSIs.

In this paper, we give an algorithm which, given a set F of at most (n - 1) - k faulty nodes, and two sets S = {s1,..., sk} and T = {t1,..., tk}, 1 k n - 1, of nonfaulty nodes in n-dimensional star graphs Gn, finds k fault-free node disjoint paths si tji, where (j1,..., jk) is a permutation of (1,..., k), of length at most d(Gn) + 5 in O(kn) optimal time, where d(Gn) = 3(n-1)/2 is the diameter of Gn.

In this paper, we give an algorithm which, given a set F of at most n-k faulty nodes, and two sets S={s1, , sk} and T = {t1,, tk}, 1kn, of non-faulty nodes in n-dimensional hypercubes Hn, finds k fault-tree node disjoint paths sitje, where (j1, , Jk) is a permutation of (1, , k), of length at most n + k in O(kn log k) time. The result of this paper implies that n disjoint paths of length at most 2n for set-to-set node disjoint path problem in Hn can be found in O(n2 log n) time.

Network functions (NFs) such as network reflection and transmission coefficients are discussed about an interconnected network consisting of a lumped distributed N-port N non-commensurate line junction network (N-port) and a M-port. The derivation of the NFs can be done quite easily regardless of the complexity of the network by considering the flow of the traveling waves and conditions of the interconnected interface of the two multi-ports. The theory of this paper has been examined with respect to interconnected networks consisting of two 3-ports in both the time and frequency domains, and has shown good results consistent with other papers. The network functions described here can be used not only for the analysis of high-speed pulse propagation in digital systems with branches but also for the analysis of microwave distributed line networks such as hybird rings. In that sense, a new analysis method is presented in this paper.

Throughout the paper, the proper operating of the self-routing principle in 2-D shuffle multistage interconnection networks (MINs) is analysed. (The notation 1-D MIN and 2-D MIN is applied for a MIN which interconnects 1-D and 2-D data, respectively.) Two different methods for self-routing in 2-D shuffle MINs are presented: (1) The application of self-routing in 1-D MINs by a switch-pattern preserving transformation of 1-D shuffle stages into 2-D shuffle stages (and vice versa) and (2) the general concept of self-routing in 2-D shuffle MINs based on self-routing with regard to each coordinate which is the original contribution of the paper. Several examples are provided which make the various problems transparent.

Recursive Diagonal Torus (RDT) is a class of interconnection network for massively parallel computers with 216 nodes. In this paper, message transfer algorithms on the RDT are proposed and discussed. First, a simple one-to-one message routing algorithm called the vector routing is introduced and its practical extension called the floating vector routing is proposed. In the floating vector routing both the diameter and average distance are improved compared with the fixed vector routing. Next, broadcasting and hypercube emulation algorithm scheme on the RDT are shown. Finally, deadlock-free message routing algorithms on the RDT are discussed. By a simple modification of the e-cube routing and a small numbers of additional virtual channels, both one-to-one message transfer and broadcast can be achieved without deadlock.

This paper presents a generalized new approach for testing interconnects (for boundary scan architectures) as well as field programmable interconnect chips (FPICs). This approach relies on a structured walking-1 test set in the sense that a structural analysis based on the layout of the interconnect system, is carried out. The proposed structural test method differs from previous approaches as it explicitly avoids aliasing and confounding and is applicable to dense as well as sparse layouts and in the presence of faults in the programmable devices of a FPIC. The proposed method is applicable to both one-step and two-step test generation and diagnosis. Two algorithms with an execution complexity of O(n2), where n is the number of nets in the interconnect, are given. New criteria for test vector compaction are proposed; a greedy condition is exploited to compact test vectors for one-step and two-step diagnosis. For a given interconnect, the two-step diagnosis algorithm requires a number of tests as a function of the number of faults present, while the one-step algorithm requires a fixed number of tests. Simulation results for benchmark and randomly generated layouts show a substantial reduction in the number of tests using the proposed approaches compared with previous approaches. The applicability of the proposed approach to FPICs as manufactured by [1] is discussed and evaluated by simulation.

Three primary wiring capacitance components for multi-layer interconnect structure in sub-micron LSI were analyzed by using 2D/3D simulators, and an influence of neighboring wiring was investigated as a three-body problem. The investigated neighboring wiring are three kinds, and they are same-layer, upper-layer and under-layer wiring. An analytical model of each capacitance component was proposed for LPE (Layout Parameter Extraction) system, and its accuracy and application limit were discussed. This new model can estimate each capacitance component of complicated interconnect structure within 20% error.

We propose a new high-performance message router for k-ary n-cube multicomputer systems, called the Tokky router. The router utilizes a small number of queues at the outputs of its communication ports to allow fully adaptive routing, misrouting to prevent deadlocks and randomization to prevent livelock. Uncongeste network performance is improved by the inclusion of the packet expressway. Accurate models are developed to predict the switch and buffer performance of routers for varying radix and dimension and these models can be used in the design of routers for networks other than those investigated here. The simulated performance of the router exceeds that of published results for oblivious routers and is equal to or exceeds those reported for other adaptive routers. These performance predictions are especially encouraging when the simplicity of the control structures required to implement the router are taken into consideration.

In this paper, we study the following node-to-node fault tolerant routing problem: In the presence of up to n-1 faulty nodes, find a fault-free path which connects any two non-faulty nodes s and t in an n-connected graph. For node-to-node fault tolerant routing in n-dimensional hypercubes Hn, we give an algorithm which finds a fault-free path s t of length at most in O(n) time, where d(s, t) is the distance between s and t. We also show that a fault-free path s t in Hn of length at most d(s, t)2i, 1i, can be found in time. For node-to-node fault tolerant routing in n-dimensional star graphs Gn, we give an algorithm which finds a fault-free path s t of length at most min{d(Gn)3, d(s, t)6} in O(n) time, where is the diameter of Gn. It is previously known that, in Hn, a fault-free path s t of length at most d(s, t) for d(s, t)n and at most d(s, t)2 for d(s, t)n can be found in O(d(s, t)n) time, and in Gn, a fault-free path s t of length at most min{d(Gn)1, d(s, t)4}can be found in O(d(s, t)n) time. When the time efficiency of finding the routing path is more important than the length of the path, the algorithms in this paper are better than the previous ones.

A Hierarchical Cubic Network (HCN) is a hierarchical hypercube network proposed by Ghose. The HCN is topologically superior to many other similar networks, in particular, the hypercube. It has a considerably lower diameter than a comparable hypercube and is realized using almost half the number of links per node as a comparable hypercube. In this paper, we propose the shortest routing algorithm in HCN(n, n) and show that the diameter of HCN(n, n) with 22n nodes is n(n1)/31 which is about 2/3 of that of a comparable hypercube. We also propose the optimal routing algorithm in HCN(m, n) where mn and obtain that its diameter is n(m1)/31. Typical parallel algorithms run in HCN(m, n) with the same time complexity as a hypercube and the hypercube topology can be emulated with O(1) time complexity in it.

There is a wide perception of the need for conformance and interoperability testing to ensure the interoperability of open systems. In the circumstances, we have been making efforts to establish a system for interconnectability testing, which is a type of the interoperability testing. In this paper, we discuss an interconnectability testing system, named AICTS (AIC's InterConnectability Testing System) that we have designed. We also discuss a conformance testing system, named ACTS (AIC Conformance Test System), which we developed as the first step toward building an interconnectability testing system. ACTS is capable of extensions for an interconnectability testing system.

Wavelength-division multiplexing (WDM) optical switching networks are one of most attractive technologies in optical interconnections. By combining with time-division multiplexing (TDM) and space-division multiplexing (SDM) technologies, remarkably high-throughput interconnections may be accomplished. In this paper, we propose WDM switching networks with time-division multiplexed optical signals by using free-space optics. We also propose novel WDM interconnections, including multiple-wavelength light-sources, optical fibers and wavelength-selectable detectors. We successfully confirmed basic principles for the WDM interconnections.

We describe an application of InGaAs/AlGaAs VCSELs to multiple wavelength light source for optical interconnection. A flip-chip bonding technique is used to integrate the VCSELs lasing at different wavelengths. The integrated VCSELs of different wavelengths are individually grown and processed, so that one can optimize the device characteristics and the wavelength separation or distribution for multiple wavelength interconnection systems. A 9-wavelength VCSEL array with a wavelength separation of 5 nm has been successfully fabricated.