Redundancy resolution using a tractrix and its application to real-time simulations of hyper-redundant manipulators, snakes and tying of knots

To realistically simulate the motion of flexible objects such as ropes, strings, snakes, or human hair,one strategy is to discretise the object into a large number of small rigid links connected by rotary or spherical joints. The discretised system is highly redundant and the rotations at the joints (or the motion of the other links) for a desired Cartesian motion of the end of a link cannot be solved uniquely. In this paper, we propose a novel strategy to resolve the redundancy in such hyper-redundant systems.We make use of the classical tractrix curve and its attractive features. For a desired Cartesian motion of the `head'of a link, the `tail' of the link is moved according to a tractrix,and recursively all links of the discretised objects are moved along different tractrix curves. We show that the use of a tractrix curve leads to a more `natural' motion of the entire object since the motion is distributed uniformly along the entire object with the displacements tending to diminish from the `head' to the `tail'. We also show that the computation of the motion of the links can be done in real time since it involves evaluation of simple algebraic, trigonometric and hyperbolic functions. The strategy is illustrated by simulations of a snake, tying of knots with a rope and a solution of the inverse kinematics of a planar hyper-redundant manipulator.

Training-Symbol Embedded, High-Rate, Single-Symbol ML-Decodable, Distributed STBCs for Relay Networks

Distributed space-time block codes (DSTBCs) from complex orthogonal designs (CODs) (both square and nonsquare), coordinate interleaved orthogonal designs (CIODs), and Clifford unitary weight designs (CUWDs) are known to lose their single-symbol ML decodable (SSD) property when used in two-hop wireless relay networks using amplify and forward protocol. For such networks, in this paper, three new classes of high rate, training-symbol embedded (TSE) SSD DSTBCs are constructed: TSE-CODs, TSE-CIODs, and TSE-CUWDs. The proposed codes include the training symbols inside the structure of the code which is shown to be the key point to obtain the SSD property along with the channel estimation capability. TSE-CODs are shown to offer full-diversity for arbitrary complex constellations and the constellations for which TSE-CIODs and TSE-CUWDs offer full-diversity are characterized. It is shown that DSTBCs from nonsquare TSE-CODs provide better rates (in symbols per channel use) when compared to the known SSD DSTBCs for relay networks. Important from the practical point of view, the proposed DSTBCs do not contain any zeros in their codewords and as a result, antennas of the relay nodes do not undergo a sequence of switch on/off transitions within every codeword, and, thus, avoid the antenna switching problem.

Optimal Exact-Regenerating Codes for Distributed Storage at the MSR and MBR Points via a Product-Matrix Construction

Regenerating codes are a class of distributed storage codes that allow for efficient repair of failed nodes, as compared to traditional erasure codes. An [n, k, d] regenerating code permits the data to be recovered by connecting to any k of the n nodes in the network, while requiring that a failed node be repaired by connecting to any d nodes. The amount of data downloaded for repair is typically much smaller than the size of the source data. Previous constructions of exact-regenerating codes have been confined to the case n = d + 1. In this paper, we present optimal, explicit constructions of (a) Minimum Bandwidth Regenerating (MBR) codes for all values of [n, k, d] and (b) Minimum Storage Regenerating (MSR) codes for all [n, k, d >= 2k - 2], using a new product-matrix framework. The product-matrix framework is also shown to significantly simplify system operation. To the best of our knowledge, these are the first constructions of exact-regenerating codes that allow the number n of nodes in the network, to be chosen independent of the other parameters. The paper also contains a simpler description, in the product-matrix framework, of a previously constructed MSR code with [n = d + 1, k, d >= 2k - 1].

Exploiting Programmable Network Interfaces for Parallel Query Execution in Workstation Clusters

Workstation clusters equipped with high performance interconnect having programmable network processors facilitate interesting opportunities to enhance the performance of parallel application run on them. In this paper, we propose schemes where certain application level processing in parallel database query execution is performed on the network processor. We evaluate the performance of TPC-H queries executing on a high end cluster where all tuple processing is done on the host processor, using a timed Petri net model, and find that tuple processing costs on the host processor dominate the execution time. These results are validated using a small cluster. We therefore propose 4 schemes where certain tuple processing activity is offloaded to the network processor. The first 2 schemes offload the tuple splitting activity - computation to identify the node on which to process the tuples, resulting in an execution time speedup of 1.09 relative to the base scheme, but with I/O bus becoming the bottleneck resource. In the 3rd scheme in addition to offloading tuple processing activity, the disk and network interface are combined to avoid the I/O bus bottleneck, which results in speedups up to 1.16, but with high host processor utilization. Our 4th scheme where the network processor also performs apart of join operation along with the host processor, gives a speedup of 1.47 along with balanced system resource utilizations. Further we observe that the proposed schemes perform equally well even in a scaled architecture i.e., when the number of processors is increased from 2 to 64

Distributed load adaptive scheduling for throughput and delay guarantees in fading wireless LANs

We consider a problem of providing mean delay and average throughput guarantees in random access fading wireless channels using CSMA/CA algorithm. This problem becomes much more challenging when the scheduling is distributed as is the case in a typical local area wireless network. We model the CSMA network using a novel queueing network based approach. The optimal throughput per device and throughput optimal policy in an M device network is obtained. We provide a simple contention control algorithm that adapts the attempt probability based on the network load and obtain bounds for the packet transmission delay. The information we make use of is the number of devices in the network and the queue length (delayed) at each device. The proposed algorithms stay within the requirements of the IEEE 802.11 standard.

The Future of Computation

The purpose of life is to obtain knowledge, use it to live with as much satisfaction as possible, and pass it on with improvements and modifications to the next generation.'' This may sound philosophical, and the interpretation of words may be subjective, yet it is fairly clear that this is what all living organisms--from bacteria to human beings--do in their life time. Indeed, this can be adopted as the information theoretic definition of life. Over billions of years, biological evolution has experimented with a wide range of physical systems for acquiring, processing and communicating information. We are now in a position to make the principles behind these systems mathematically precise, and then extend them as far as laws of physics permit. Therein lies the future of computation, of ourselves, and of life.

Computation of thermodynamic properties of liquid ferrous alloys from structural measurements

Relation between X-ray scattering intensities, mean square thermal fluctuations and thermodynamic properties. High temperature X-ray diffraction study of liquid Fe-Ni and Fe-Si alloys using reflection and transmission geometries. Calculation of the structure factor as a function of wave vector. Extrapolation to zero wave vector. Calculation of the concentration-concentration correlation function defined by A. B. Bhatia and D. E. Thorton. Computation of thermodynamic quantities of mixing A G, LlH and LlS for the binary alloys. Comparison with direct thermodynamic measurements reported in the literature.

Computation of thermodynamic properties of quaternary and higher order systems from binary data using shortest distance composition paths

Equations for the computation of integral and partial thermodynamic properties of mixing in quarternary systems are derived using data on constituent binary systems and shortest distance composition paths to the binaries. The composition path from a quarternary composition to the i-j binary is characterized by a constant value of (Xi − Xj). The merits of this composition path over others with constant values for View the MathML source or Xi are discussed. Finally the equations are generalized for higher order systems. They are exact for regular solutions, but may be used in a semiempirical mode for non-regular solutions.

Spinel deoxidation equilibria in the Fe Mn Al O system - experiments and computation

The concentration and chemical potential of oxygen in liquid Fe--Mn alloys equilibrated with the spinel solution, (Fe, Mn)Al sub 2+2x O sub 4+3x , and alpha -Al sub 2 O sub 3 have been determined at 1873K as a function of manganese concentration. The composition of the spinel phase has been determined using electron probe microanalysis. The results are compared with data reported in the literature. The deoxidation equilibrium has been computed using data on free energy of solution of oxygen in liquid iron, free energies of formation of hercynite and galaxite, and interaction parameters reported in the literature. The activity--composition relationship in spinel solution was derived from a cation distribution model. The model is in excellent agreement with the experimental data on oxygen concentration and potential and the composition of the spinel phase. 23 ref.--AA

Collocated and Distributed STBCs with Partial Interference Cancellation Decoding, Part I: Full-Diversity Criterion

Low complexity decoders called Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC), which include the Zero Forcing (ZF) and ZF-SIC receivers as special cases, were given by Guo and Xia along with sufficient conditions for a Space-Time Block Code (STBC) to achieve full diversity with PIC/PIC-SIC decoding for point-to-point MIMO channels. In Part-I of this two part series of papers, we give new conditions for an STBC to achieve full diversity with PIC and PIC-SIC decoders, which are equivalent to Guo and Xia's conditions, but are much easier to check. We then show that PIC and PIC-SIC decoders are capable of achieving the full cooperative diversity available in wireless relay networks and give sufficient conditions for a Distributed Space-Time Block Code (DSTBC) to achieve full diversity with PIC and PIC-SIC decoders. In Part-II, we construct new low complexity full-diversity PIC/PIC-SIC decodable STBCs and DSTBCs that achieve higher rates than the known full-diversity low complexity ML decodable STBCs and DSTBCs.

Collocated and Distributed STBCs with Partial Interference Cancellation Decoding, Part II: Code Construction

In this second part of a two part series of papers, we construct a new class of Space-Time Block Codes (STBCs) for point-to-point MIMO channel and Distributed STBCs (DSTBCs) for the amplify-and-forward relay channel that give full-diversity with Partial Interference Cancellation (PIC) and PIC with Successive Interference Cancellation (PIC-SIC) decoders. The proposed class of STBCs include most of the known full-diversity low complexity PIC/PIC-SIC decodable STBCs as special cases. We also show that a number of known full-diversity PIC/PIC-SIC decodable STBCs that were constructed for the point-topoint MIMO channel can be used as full-diversity PIC/PIC-SIC decodable DSTBCs in relay networks. For the same decoding complexity, the proposed STBCs and DSTBCs achieve higher rates than the known low decoding complexity codes. Simulation results show that the new codes have a better bit error rate performance than the low ML decoding complexity codes available in the literature.

Parallel Computation of 2D Morse-Smale Complexes

The Morse-Smale complex is a useful topological data structure for the analysis and visualization of scalar data. This paper describes an algorithm that processes all mesh elements of the domain in parallel to compute the Morse-Smale complex of large two-dimensional data sets at interactive speeds. We employ a reformulation of the Morse-Smale complex using Forman's Discrete Morse Theory and achieve scalability by computing the discrete gradient using local accesses only. We also introduce a novel approach to merge gradient paths that ensures accurate geometry of the computed complex. We demonstrate that our algorithm performs well on both multicore environments and on massively parallel architectures such as the GPU.

Distributed Simulation Of Flexible Manufacturing Systems

Flexible Manufacturing Systems (FMS), widely considered as the manufacturing technology of the future, are gaining increasing importance due to the immense advantages they provide in terms of cost, quality and productivity over the conventional manufacturing. An FMS is a complex interconnection of capital intensive resources and high levels of system performance is very crucial for survival in a competing environment.Discrete event simulation is one of the most popular methods for performance evaluation of FMS during planning, design and operation phases. Indeed fast simulators are suggested for selection of optimal strategies for flow control (which part type to enter and at what instant), AGV scheduling (which vehicle to carry which part), routing (which machine to process the part) and part selection (which part for processing next). In this paper we develop a C-net based model for an FMS and use the same for distributed discrete event simulation. We illustrate using examples the efficacy of destributed discrete event simulation for the performance evaluation of FMSs.