Single sided switching networks

A novel and simple architecture for realising single-sided, rearrangeably-nonblocking, N-port switching networks (N is a power of 2), that uses N/2 log (N/2) elements, together with an efficient routing algorithm with time complexity O(N log (N)) is presented. The networks also exhibit a useful measure of fault tolerance.<>     

Optimal information-dispersal for fault-tolerant communication over a burst-error channel

The (m,n) wireless information dispersal scheme (WIDS) is useful for fault-tolerant parallel wireless communications, where it can be used to tolerate up to n-m path (sub-channel) failures. This paper constructs a performance model of (m,n) WIDS used in wireless communications, and proposes an algorithm to find the optimal set of (m,n) with the highest reliability. This algorithm reduces the complexity of finding the candidate set of (m,n) from O(N/sup 2/) to O(N);N is the maximum number of available sub-channels.     

Generalised transform factorisation for massive parallelism

A formalism and an algorithm for configuring and sequencing parallel to massively parallel processors for the application of generalised spectral analysis transforms are presented. Successive partial rotations of a base-p hypercube, where p is an arbitrary integer, are shown to produce dynamic contention-free memory allocation, in a generalised parallelism processor architecture. The approach is illustrated by factorisations involving the processing of matrices of transforms which are functions of four variables. Parallel operations are implemented as matrix multiplications. Each matrix, of dimension N /spl times/ N, where N = p/sup n/, n integer, has a structure that depends on a variable parameter k. The level of parallelism, in the form of M = p/sup m/ processors, can be chosen arbitrarily by varying m between zero and its maximum value of n - 1. The result is an equation describing the generalised parallelism factorisation as a function of the four variables n, p, k and m. Applications of the approach are shown in relation to complex matrix structures of image processing generalised spectral analysis transforms. The same approach can be applied to a much larger class of parallel and multiprocessing systems for digital signal processing applications.     

Improved lightpath (wavelength) routing in large WDM networks

We address the problem of efficient circuit switching in wide area networks. The solution provided is based on finding optimal routes for lightpaths and semilightpaths. A lightpath is a fully optical transmission path, while a semilightpath is a transmission path constructed by chaining several lightpaths together, using wavelength conversion at their junctions. The problem thus is to find an optimal lightpath/semilightpath in the network in terms of the cost of wavelength conversion and the cost of using the wavelengths on links. In this paper, we first present an efficient algorithm for the problem which runs in time O(k²n+km+kn log(kn)), where n and m are the number of nodes and links in the network, and k is the number of wavelengths. We then analyze that the proposed algorithm requires O(d ²nk₀²+mk₀ log n) time for a restricted version of the problem in which the number of available wavelengths for each link is bounded by k₀ and k₀=o(n), where d is the maximum in-degree or out-degree of the network. It is surprising to have found that the time complexity for this case is independent of k. It must be mentioned that our algorithm can be implemented efficiently in the distributed computing environment. The distributed version requires O(kn) time and O(km) messages. Compared with a previous O(k²n+kn²) time algorithm, our algorithm has the following advantages. (1) We take into account the physical topology of the network which makes our algorithm outperform the previous algorithm. In particular, when k is small [e.g., k=O(log n)] and m=O(n), our algorithm runs in time O(n log² n), while the previous algorithm runs in time O(n log n). (2) Since our algorithm has high locality, it can be implemented on the network distributively     

A parallel algorithm for time-slot assignment problems in TDMhierarchical switching systems

The paper presents a parallel algorithm for time-slot assignment problems in TDM hierarchical switching systems, based on the neural network model. The TDM systems are operated in repetitive frames composed of several time-slots. A time-slot represents a switching configuration where one packet is transmitted through an I/O line. The goal of the algorithm is to find conflict-free time-slot assignments for given switching demands. The algorithm runs on a maximum of n²×m processors for m-time-slot problems in n×n TDM systems. In small problems up to a 24×24 TDM system, the algorithm can find the optimum solution in a nearly constant time, when it is performed on n²×m processors     

A new design for wide-sense nonblocking multicast switching networks

In this paper, we propose a new design for a wide-sense nonblocking multicast switching network, which has many comparable properties to a strictly nonblocking Clos permutation network. For a newly designed four-stage N/spl times/N multicast network, its hardware cost, in terms of the number of crosspoints, is about 2(3+2/spl radic/2)N/sup 3/2/=11.66N/sup 3/2/, which is only a small constant factor higher than that of a three-stage nonblocking permutation network, and is lower than the O(N/sup 3/2/(logN/loglogN)) hardware cost of the well-known three-stage wide-sense nonblocking multicast network. In addition, the proposed four-stage nonblocking multicast network has a very simple routing algorithm with sublinear time complexity, and does not require multicast capability for the switch modules in the input stage.     

A time optimal wavelength rerouting algorithm for dynamic trafficin WDM networks

In this paper, we consider wavelength rerouting in wavelength routed wavelength division multiplexed (WDM) networks with circuit switching, wherein lightpaths between source-destination pairs are dynamically established and released in response to a random pattern of arriving connection requests and connection holding times. The wavelength continuity constraint imposed by WDM networks leads to poor blocking performance. Wavelength rerouting is a viable and cost effective mechanism that ran improve the blocking performance by rearranging certain existing lightpaths to accommodate a new request. Recently, a rerouting scheme called “parallel move-to-vacant wavelength retuning (MTV-WR)” with many attractive features such as shorter disruption period and simple switching control, and a polynomial time rerouting algorithm, for this scheme, to minimize the weighted number of rerouted lightpaths have been proposed. This paper presents a time optimal rerouting algorithm for wavelength-routed WDM networks with parallel MTV-WR rerouting scheme. The algorithm requires only O(N²W) time units to minimize the weighted number of existing lightpaths to be rerouted, where N is the number of nodes in the network and W is the number of wavelength channels available on a fiber link. Our algorithm is an improvement over the earlier algorithm proposed in that it requires O(N³W+N²W²) time units, which is not time optimal. The simulation results show that our algorithm improves the blocking performance considerably and only very few lightpaths are required to be rerouted per rerouting. It is also established through simulation that our algorithm is faster than the earlier rerouting algorithm by measuring the time required for processing connection requests for different networks     

Scheduling satellite-switched time-division multiple access with general switching modes

Based on network circulation formulation, the existence of feasible beam-to-beam switching modes for a satellite-switched time-division multiple access system is completely and transparently proved, where simultaneous transmissions on several carriers in each spot-beam are configured. Showing the linear independence of all but one augmented switching modes, a new bound of mn+2 is obtained on the number of switching modes, where m and n are the number of up-link and down-link beams, respectively. The time complexity for finding the whole sequence of switching modes and for finding the initial switching mode are improved to O(m/sup 2/n/sup 2/) and O(min(/spl radic/K,(m+n)/sup 2/3/)mn), respectively. Practical implementation considerations are discussed.     

A hierarchical FFT algorithm (HIL-FFT) for the fast analysis of transient electromagnetic scattering phenomena

A fast algorithm for accelerating the time-marching solution of time-domain integral equations pertinent to the analysis of free-space electromagnetic scattering from perfectly conducting, platelike and uniformly meshed structures is presented. The matrix-vector multiplications required by the time-marching scheme are accelerated by use of the fast Fourier transform (FFT). This acceleration is achieved in a multilevel fashion by hierarchically grouping sparse interactions to extract denser pieces that are efficiently evaluated by the FFT. The total computational cost and storage requirements of this algorithm scale as O(N/sub t/N/sub s/log/sup 2/ N/sub s/) and O(N/sup 1.5/), respectively, as opposed to O(N/sub t/N/sub s//sup 2/) and O(N/sub s//sup 2/) for classical time-marching methods (N/sub s/ and N/sub t/ denote the total number of spatial unknowns and time steps, respectively). Simulation results demonstrate the accuracy and efficiency of the algorithm.     

超立方体多计算机系统的一个高效故障诊断算法

超立方体是一类广泛应用的互连拓扑结构,具有可并行处理的某些性质.在MM*模型下,针对于超立方体多计算机系统的诊断问题,提出了一个快速诊断算法,可以正确诊断出系统中所有的故障结点,其时间复杂度为O(Nlog22N),N是处理器总数.     

Time domain adaptive integral method for surface integral equations

An efficient marching-on-in-time (MOT) scheme is presented for solving electric, magnetic, and combined field integral equations pertinent to the analysis of transient electromagnetic scattering from perfectly conducting surfaces residing in an unbounded homogenous medium. The proposed scheme is the extension of the frequency-domain adaptive integral/pre-corrected fast-Fourier transform (FFT) method to the time domain. Fields on the scatterer that are produced by space-time sources residing on its surface are computed: 1) by locally projecting, for each time step, all sources onto a uniform auxiliary grid that encases the scatterer; 2) by computing everywhere on this grid the transient fields produced by the resulting auxiliary sources via global, multilevel/blocked, space-time FFTs; 3) by locally interpolating these fields back onto the scatterer surface. As this procedure is inaccurate when source and observer points reside close to each other; and 4) near fields are computed classically, albeit (pre-)corrected, for errors introduced through the use of global FFTs. The proposed scheme has a computational complexity and memory requirement of O(N/sub t/N/sub s/log/sup 2/N/sub s/) and O(N/sub s//sup 3/2/) when applied to quasiplanar structures, and of O(N/sub t/N/sub s//sup 3/2/log/sup 2/N/sub s/) and O(N/sub s//sup 2/) when used to analyze scattering from general surfaces. Here, N/sub s/ and N/sub t/ denote the number of spatial and temporal degrees of freedom of the surface current density. These computational cost and memory requirements are contrasted to those of classical MOT solvers, which scale as O(N/sub t/N/sub s//sup 2/) and O(N/sub s//sup 2/), respectively. A parallel implementation of the scheme on a distributed-memory computer cluster that uses the message-passing interface is described. Simulation results demonstrate the accuracy, efficiency, and the parallel performance of the implementation.     

Fast solution of mixed-potential time-domain integral equations for half-space environments

A fast Fourier transform-accelerated integral-equation based algorithm to efficiently analyze transient scattering from planar perfect electrically conducting objects residing above or inside a potentially lossy dielectric half-space is presented. The algorithm requires O(N/sub t/N/sub s/(logN/sub s/+log/sup 2/N/sub t/)) CPU and O(N/sub t/N/sub s/) memory resources when analyzing electromagnetic wave interactions with uniformly meshed planar structures. Here, N/sub t/ and N/sub s/ are the numbers of simulation time steps and spatial unknowns, respectively. The proposed scheme is therefore far more efficient than classical time-marching solvers, the CPU and memory requirements of which scale as O(N/sub t//sup 2/N/sub s//sup 2/) and O(N/sub t/N/sub s//sup 2/). In the proposed scheme, all pertinent time-domain half-space Green functions are (pre) computed from their frequency-domain counterparts via inverse discrete Fourier transformation. In this process, in-band aliasing is avoided through the application of a smooth and interpolatory window. Numerical results demonstrate the accuracy and efficiency of the proposed algorithm.     

一种高效的基于局部扭曲立方体的悲观诊断算法

悲观诊断与精确诊断相比,可以提高系统的自诊断能力。局部扭曲立方体是超立方体的一种变体,具有可并行处理的某些性质。在PMC模型下,研究了局部扭曲立方体的诊断问题,提出了一个O(Nlog_2N)的悲观诊断算法,N是处理器总数。经典的YML算法所需时间为O(N~(2.5)),因此,该算法在时间复杂度方面是高效的。     

Self-routing space switch network comprising fast and uniform switch elements

The authors present a method by which to construct a fast N*N self-routing space switch network with identical 2*2 switch elements. This network is nonblocking and employs O(N log/sup 3/ N) switch elements; each element uses just two bits of the output port address for switching control.<>     

Efficient time slot assignment algorithms for TDM hierarchical andnonhierarchical switching systems

Two efficient time slot assignment algorithms, called the two-phase algorithm for the nonhierarchical and the three-phase algorithm for the hierarchical time-division multiplex (TDM) switching systems, are proposed. The simple idea behind these two algorithms is to schedule the traffic on the critical lines/trunks of a traffic matrix first. The time complexities of these two algorithms are found to be O(LN²) and O(LM²), where L is the frame length, N is the switch size, and M is the number of input/output users connected to a hierarchical TDM switch. Unlike conventional algorithms, they are fast, iterative and simple for hardware implementation. Since no backtracking is used, pipelined packet transmission and packet scheduling can be performed for reducing the scheduling complexity of a transmission matrix to O(N²) and O(M²), respectively. Extensive simulations reveal that the two proposed algorithms give close-to-optimal performance under various traffic conditions     

Efficient network folding techniques for routing permutations inVLSI

Network folding is a technique for realizing permutations on N elements using interconnection networks with M input (and output) terminals, where M相似文献   

The smallest grammar problem

This paper addresses the smallest grammar problem: What is the smallest context-free grammar that generates exactly one given string /spl sigma/? This is a natural question about a fundamental object connected to many fields such as data compression, Kolmogorov complexity, pattern identification, and addition chains. Due to the problem's inherent complexity, our objective is to find an approximation algorithm which finds a small grammar for the input string. We focus attention on the approximation ratio of the algorithm (and implicitly, the worst case behavior) to establish provable performance guarantees and to address shortcomings in the classical measure of redundancy in the literature. Our first results are concern the hardness of approximating the smallest grammar problem. Most notably, we show that every efficient algorithm for the smallest grammar problem has approximation ratio at least 8569/8568 unless P=NP. We then bound approximation ratios for several of the best known grammar-based compression algorithms, including LZ78, B ISECTION, SEQUENTIAL, LONGEST MATCH, GREEDY, and RE-PAIR. Among these, the best upper bound we show is O(n/sup 1/2/). We finish by presenting two novel algorithms with exponentially better ratios of O(log/sup 3/n) and O(log(n/m/sup */)), where m/sup */ is the size of the smallest grammar for that input. The latter algorithm highlights a connection between grammar-based compression and LZ77.     

Fast algorithm for finding primitive polynomials over GF(q)

An efficient algorithm for the construction of primitive polynomials of degree m over GF(q) is proposed. The algorithm runs in time O(km/sup 2/), where k is an integer such that gcd (k,q/sup m-1/)=1.<>     

A m log m algorithm to compute the most probable configurations of a system with multi-mode independent components

In this note, we propose a m log m algorithm to find the k most probable configurations of a system of n multi-mode independent components, with at most d modes each. m denotes the size of the problem, i.e. max (nd, k). This problem originates in network performance analyzes, in which focusing on the most probable configurations is a means to reduce computational costs. Up to this note, the best known algorithm to extract the most probable configurations was in O(n/sup 2/d/sup 2/ + k log k). Our algorithm achieves thus a substantial improvement.     

Sequential diagnosis of processor array systems

We examine the diagnosis of processor array systems formed as two-dimensional arrays, with boundaries, and either four or eight neighbors for each interior processor. We employ a parallel test schedule. Neighboring processors test each other, and report the results. Our diagnostic objective is to find a fault-free processor or set of processors. The system may then be sequentially diagnosed by repairing those processors tested faulty according to the identified fault-free set, or a job may be run on the identified fault-free processors. We establish an upper bound on the maximum number of faults which can be sustained without invalidating the test results under worst case conditions. We give test schedules and diagnostic algorithms which meet the upper bound as far as the highest order term. We compare these near optimal diagnostic algorithms to alternative algorithms, both new and already in the literature, and against an upper bound ideal case algorithm, which is not necessarily practically realizable. For eight-way array systems with N processors, an ideal algorithm has diagnosability 3N/sup 2/3/-2N/sup 1/2/ plus lower-order terms. No algorithm exists which can exceed this. We give an algorithm which starts with tests on diagonally connected processors, and which achieves approximately this diagnosability. So the given algorithm is optimal to within the two most significant terms of the maximum diagnosability. Similarly, for four-way array systems with N processors, no algorithm can have diagnosability exceeding 3N/sup 2/3//2/sup 1/3/-2N/sup 1/2/ plus lower-order terms. And we give an algorithm which begins with tests arranged in a zigzag pattern, one consisting of pairing nodes for tests in two different directions in two consecutive test stages; this algorithm achieves diagnosability (3/2)(5/2)/sup 1/3/N/sup 2/3/-(5/4)N/sup 1/2/ plus lower-order terms, which is about 0.85 of the upper bound due to an ideal algorithm.