Improved preprocessing methods for modulo scheduling algorithms

Instruction scheduling with an automaton-based resource conflict model is well-established for normal scheduling. Such models have been generalized to software pipelining in the modulo-scheduling framework. One weakness with existing methods is that a distinct automaton must be constructed for each combination of a reservation table and initiation interval. In this work, we present a different approach to model conflicts. We construct one automaton for each reservation table which acts as a compact encoding of all the conflict automata for this table, which can be recovered for use in modulo-scheduling. The basic premise of the construction is to move away from the Proebsting-Fraser model of conflict automaton to the Muller model of automaton modelling issue sequences. The latter turns out to be useful and efficient in this situation. Having constructed this automaton, we show how to improve the estimate of resource constrained initiation interval. Such a bound is always better than the average-use estimate. We show that our bound is safe: it is always lower than the true initiation interval. This use of the automaton is orthogonal to its use in modulo-scheduling. Once we generate the required information during pre-processing, we can compute the lower bound for a program without any further reference to the automaton.

Simple Coding Scheme For Modular Arithmetic

A dual representation scheme for performing arithmetic modulo an arbitrary integer M is presented. The coding scheme maps each integer N in the range 0 <= N < M into one of two representations, each being identified by its most significant bit. The encoding of numbers is straightforward and the problem of checking for unused combinations is eliminated.

Error correction in nonbinary words

A simple error detecting and correcting procedure is described for nonbinary symbol words; here, the error position is located using the Hamming method and the correct symbol is substituted using a modulo-check procedure.

Cup products for groups and commutators

We give it description, modulo torsion, of the cup product on the first cohomology group in terms of the descriptions of the second homology group due to Hopf and Miller.

Svetlichny's inequality and genuine tripartite nonlocality in three-qubit pure states

The violation of the Svetlichny's inequality (SI) [Phys. Rev. D 35, 3066 (1987)] is sufficient but not necessary for genuine tripartite nonlocal correlations. Here we quantify the relationship between tripartite entanglement and the maximum expectation value of the Svetlichny operator (which is bounded from above by the inequality) for the two inequivalent subclasses of pure three-qubit states: the Greenberger-Horne-Zeilinger (GHZ) class and the W class. We show that the maximum for the GHZ-class states reduces to Mermin's inequality [Phys. Rev. Lett. 65, 1838 (1990)] modulo a constant factor, and although it is a function of the three tangle and the residual concurrence, large numbers of states do not violate the inequality. We further show that by design SI is more suitable as a measure of genuine tripartite nonlocality between the three qubits in the W-class states,and the maximum is a certain function of the bipartite entanglement (the concurrence) of the three reduced states, and only when their sum attains a certain threshold value do they violate the inequality.

Behaviour of autonomous mobile agents using linear cyclic pursuit laws

In this paper, the behaviour of a group of autonomous mobile agents under cyclic pursuit is studied. Cyclic pursuit is a simple distributed control law, in which the agent i pursues agent i + 1 modulo n.. The equations of motion are linear, with no kinematic constraints on motion. Behaviourally, the agents are identical, but may have different controller gains. We generalize existing results in the literature and show that by selecting these gains, the behavior of the agents can be controlled. They can be made to converge at a point or be directed to move in a straight line. The invariance of the point of convergence with the sequence of pursuit is also shown.

Low-Delay, High-Rate Nonsquare Complex Orthogonal Designs

The maximal rate of a nonsquare complex orthogonal design for transmit antennas is 1/2 + 1/n if is even and 1/2 + 1/n+1 if is odd and the codes have been constructed for all by Liang (2003) and Lu et al. (2005) to achieve this rate. A lower bound on the decoding delay of maximal-rate complex orthogonal designs has been obtained by Adams et al. (2007) and it is observed that Liang's construction achieves the bound on delay for equal to 1 and 3 modulo 4 while Lu et al.'s construction achieves the bound for n = 0, 1, 3 mod 4. For n = 2 mod 4, Adams et al. (2010) have shown that the minimal decoding delay is twice the lower bound, in which case, both Liang's and Lu et al.'s construction achieve the minimum decoding delay. For large value of, it is observed that the rate is close to half and the decoding delay is very large. A class of rate-1/2 codes with low decoding delay for all has been constructed by Tarokh et al. (1999). In this paper, another class of rate-1/2 codes is constructed for all in which case the decoding delay is half the decoding delay of the rate-1/2 codes given by Tarokh et al. This is achieved by giving first a general construction of square real orthogonal designs which includes as special cases the well-known constructions of Adams, Lax, and Phillips and the construction of Geramita and Pullman, and then making use of it to obtain the desired rate-1/2 codes. For the case of nine transmit antennas, the proposed rate-1/2 code is shown to be of minimal delay. The proposed construction results in designs with zero entries which may have high peak-to-average power ratio and it is shown that by appropriate postmultiplication, a design with no zero entry can be obtained with no change in the code parameters.

Resolution of Singularities for a Class of Hilbert Modules

Let M be the completion of the polynomial ring C(z) under bar] with respect to some inner product, and for any ideal I subset of C (z) under bar], let I] be the closure of I in M. For a homogeneous ideal I, the joint kernel of the submodule I] subset of M is shown, after imposing some mild conditions on M, to be the linear span of the set of vectors {p(i)(partial derivative/partial derivative(w) over bar (1),...,partial derivative/partial derivative(w) over bar (m)) K-I] (., w)vertical bar(w=0), 1 <= i <= t}, where K-I] is the reproducing kernel for the submodule 2] and p(1),..., p(t) is some minimal ``canonical set of generators'' for the ideal I. The proof includes an algorithm for constructing this canonical set of generators, which is determined uniquely modulo linear relations, for homogeneous ideals. A short proof of the ``Rigidity Theorem'' using the sheaf model for Hilbert modules over polynomial rings is given. We describe, via the monoidal transformation, the construction of a Hermitian holomorphic line bundle for a large class of Hilbert modules of the form I]. We show that the curvature, or even its restriction to the exceptional set, of this line bundle is an invariant for the unitary equivalence class of I]. Several examples are given to illustrate the explicit computation of these invariants.

On Additive Combinatorics of Permutations of Z(n)

Let Z(n) denote the ring of integers modulo n. A permutation of Z(n) is a sequence of n distinct elements of Z(n). Addition and subtraction of two permutations is defined element-wise. In this paper we consider two extremal problems on permutations of Z(n), namely, the maximum size of a collection of permutations such that the sum of any two distinct permutations in the collection is again a permutation, and the maximum size of a collection of permutations such that no sum of two distinct permutations in the collection is a permutation. Let the sizes be denoted by s (n) and t (n) respectively. The case when n is even is trivial in both the cases, with s (n) = 1 and t (n) = n!. For n odd, we prove (n phi(n))/2(k) <= s(n) <= n!.2(-)(n-1)/2/((n-1)/2)! and 2 (n-1)/2 . (n-1/2)! <= t (n) <= 2(k) . (n-1)!/phi(n), where k is the number of distinct prime divisors of n and phi is the Euler's totient function.

Beyond Schur's Conjecture

Schur 4] conjectured that the maximum length N of consecutive quadratic nonresidues modulo a prime p is less than root p if p is large enough. This was proved by Hummel in 2003. In this note, we outline a clear improvement over Hummel's bound for p > 23.

Beyond Schur's Conjecture

Schur 4] conjectured that the maximum length N of consecutive quadratic nonresidues modulo a prime p is less than root p if p is large enough. This was proved by Hummel in 2003. In this note, we outline a clear improvement over Hummel's bound for p > 23.