7666408
Equivalent permutation capabilities between time-division optical omega networks and non-optical extra-stage omega networks
Because signals carried by two waveguides entering a common switch element would generate crosstalk, a regular <i>N</i> × <i>N</i> multistage interconnection network (MIN) cannot be directly used as an optical switch between <i>N</i> inputs and <i>N</i> outputs in an optical network. A simple solution is to use a 2<i>N</i> × 2<i>N</i> cube-type MIN to provide the <i>N</i> × <i>N</i> connections, which needs a much larger hardware cost. A recent research proposed another solution, called the time-domain approach, that divides the <i>N</i> optical inputs into several groups such that crosstalk-free connections can be provided by an <i>N</i> × <i>N</i> regular MIN in several time slots, one for each group. Researchers studied this approach on Omega networks and defined the class set θ to be the set of <i>N</i>-permutations realizable in two time slots on an Omega network. They proved that the size of θ is larger than the size of class Ω, where Ω consists of all <i>N</i>-permutations admissible to a regular <i>N</i> × <i>N</i> (nonoptical) Omega network. This paper first presents an optimal <i>O</i>(<i>N</i> log <i>N</i>) time algorithm for identifying whether a given permutation belongs to class θ or not. Using this algorithm, this paper then proves an interesting result that the class θ is identical to the class Ω + 1 which represents the set of <i>N</i>-permutations admissible to a nonoptical <i>N</i> × <i>N</i> one-extra stage Omega network.
9442074
Generalized Latin squares II
Abstract This paper is a continuation of a study on a new class of combinatorial structures called generalized Latin squares or 〈k,l〉-Latin squares. Here, we study the existence question of perfect 〈k,l〉-Latin squares. The main result is an existence theorem for the case M = 2, where M is the multiplicity of the generalized Latin squares. Specifically, we show that for given positive integers N, k = ip, l = iq, where i = gcd(k,l), there exists a perfect 〈k,l〉-Latin square of order N with M = 2 if and only if (i) N = 4k, (ii) pq(p + q)| N, and (iii) q|2.
37059740
Realization of an Arbitrary Permutation on a Hypercube
We present an explicit combinatorial algorithm for constructing a 2-realization for any given permutation on a circuit-switched d-dimensional hypercube (d-cube) such that the total number of directed edges used in the realization (counting every repetition) is bounded by d2d, the total number of directed edges in the d-cube. As a corollary, this result implies a (2d−3) step realization on a packet-switched d-cube (d⩾3).
34776029
Embedding between 2-D meshes of the same size
It is shown how to embed an x/sub 1/ /spl times/ 1/sub 1/ mesh M/sub 1/ into an s/sub 2/ /spl times/ t/sub 2/ mesh M/sub 2/, where s/sub 1/ /spl times/ t/sub 2/, s/sub 1/ < t/sub i/ (i = 1,2) such that the dilation is minimized. It is assumed that load = 1 and expansion = 1. For each case there is shown a lower bound on the dilation and a corresponding embedding method. The dilations by these embedding algorithms either match a lower bound or are very close to a lower bound.<<ETX>>
44324303
Equivalent permutation capabilities between time division optical omega network and non-optical extra stage omega network
Since optical networks must support crosstalk-free (CF) connections, regular N/spl times/N multistage interconnection networks (MINs) cannot be directly used to provide connections between N inputs and N outputs. A solution is to use a 2N/spl times/2N Cube-Type MIN to provide the N/spl times/N connections. C. Qiao (1993) proposed a time domain approach that divides the N optical inputs into several groups such that CF connections can be provided by an N/spl times/N regular MIN in several time slots, one for each group. The set of N-permutations realizable in two slots is defined as class /spl theta/. Qiao proved that the size of /spl theta/ is larger than the size of class /spl Omega/, where /spl Omega/ consists of all N-permutations passible through a regular N/spl times/N Omega network. The paper first presents an optimal O(NlgN) time algorithm for identifying whether a given permutation belongs to class /spl theta/ or not. From this algorithm, the paper proves an interesting fact that the class /spl theta/ is identical to the class /spl Omega/+1 which represents the set of N-permutations admissible by a non-optical N/spl times/N one-extra stage Omega network.
33412339
Conservative Algorithms for Parallel and Sequential Integer Sorting
We present a conservative CRCW parallel algorithm for integer sorting. This algorithm sorts n integers from {0, 1, ..., m−1} in time O(n log log min(m,n)/p + log n) using p processors. The simulation of our parallel algorithm on the sequential machine yields a sequential algorithm for integer sorting which sorts n integers from {0, 1, ..., m−1} in time O(n min(log log n, log log m/log n)).
14429022
Mining long-term search history to improve search accuracy
Long-term search history contains rich information about a user's search preferences, which can be used as search context to improve retrieval performance. In this paper, we study statistical language modeling based methods to mine contextual information from long-term search history and exploit it for a more accurate estimate of the query language model. Experiments on real web search data show that the algorithms are effective in improving search accuracy for both fresh and recurring queries. The best performance is achieved when using clickthrough data of past searches that are related to the current query.
16973693
An adaptive handoff priority scheme for wireless MC-CDMA cellular networks supporting realtime multimedia applications
An adaptive handoff priority scheme is proposed for a packet switching multicode (MC)-CDMA cellular network supporting realtime multimedia applications. The scheme jointly considers the physical, link and network layer characteristics, and gives service priority to handoff calls by exploiting the transmission rate adaptability of multimedia calls to the available radio resources. Based on the scheme, a call admission region is derived with the estimated cell capacity and the proposed packet scheduling and partial packet integration scheme and used for call admission control and handoff management with the satisfaction of quality of service requirements for all multimedia traffic, where the QoS parameters include the wireless transmission bit error rate, packet loss rate and delay requirement. Simulation results are given to demonstrate the viability of the proposed scheme.
33166016
Indirect RSVP for Virtual Cluster Cellular Mobile IP Networks
Mobile IP (MIP) could be deployed in a wireless cellular network so that the integrated Cellular Mobile IP (CMIP) network can be used to support datagram delivery to mobile users. In order to provide QoS for realtime traffic in IP network, Resource reSerVation Protocol (RSVP) is needed to reserve network resources along the route which the datagrams follow. However, current RSVP fails to operate through the MIP tunnel. Moreover, the high registration rate in a CMIP network greatly degrades RSVP performance. In this paper, an Indirect RSVP (IRSVP) over Virtual Cluster Cellular Mobile IP (VCCMIP) is proposed in which an assistant RSVP connection is introduced to assist the end-to-end major RSVP operation over the MIP tunnel. IRSVP signaling costs and packet loss rates are evaluated. Simulation results show that the proposed scheme can greatly increase RSVP performance in terms of packet loss and RSVP connection active percentage.
6253791
Array regrouping and structure splitting using whole-program reference affinity
While the memory of most machines is organized as a hierarchy, program data are laid out in a uniform address space. This paper defines a model of reference affinity, which measures how close a group of data are accessed together in a reference trace. It proves that the model gives a hierarchical partition of program data. At the top is the set of all data with the weakest affinity. At the bottom is each data element with the strongest affinity. Based on the theoretical model, the paper presents k-distance analysis, a practical test for the hierarchical affinity of source-level data. When used for array regrouping and structure splitting, k-distance analysis consistently outperforms data organizations given by the programmer, compiler analysis, frequency profiling, statistical clustering, and all other methods we have tried.
9685849
Adaptive data partition for sorting using probability distribution
Many computing problems benefit from dynamic partition of data into smaller chunks with better parallelism and locality. However, it is difficult to partition all types of inputs with the same high efficiency. This paper presents a new partition method in sorting scenario based on probability distribution, an idea first studied by Janus and Lamagna in early 1980's on a mainframe computer. The new technique makes three improvements. The first is a rigorous sampling technique that ensures accurate estimate of the probability distribution. The second is an efficient implementation on modern, cache-based machines. The last is the use of probability distribution in parallel sorting. Experiments show 10-30% improvement in partition balance and 20-70% reduction in partition overhead, compared to two commonly used techniques. The new method reduces the parallel sorting time by 33-50% and outperforms the previous fastest sequential sorting technique by up to 30%.