On the direct parallel solution of systems of linear equations: New algorithms and systolic structures

The paper presents two new algorithms for the direct parallel solution of systems of linear equations. The algorithms employ a novel recursive doubling technique to obtain solutions to an nth-order system in n steps with no more than 2n(n −1) processors. Comparing their performance with the Gaussian elimination algorithm (GE), we show that they are almost 100% faster than the latter. This speedup is achieved by dispensing with all the computation involved in the back-substitution phase of GE. It is also shown that the new algorithms exhibit error characteristics which are superior to GE. An n(n + 1) systolic array structure is proposed for the implementation of the new algorithms. We show that complete solutions can be obtained, through these single-phase solution methods, in 5n−log2n−4 computational steps, without the need for intermediate I/O operations.

Parallel parsing of programming languages

A new method of specifying the syntax of programming languages, known as hierarchical language specifications (HLS), is proposed. Efficient parallel algorithms for parsing languages generated by HLS are presented. These algorithms run on an exclusive-read exclusive-write parallel random-access machine. They require O(n) processors and O(log2n) time, where n is the length of the string to be parsed. The most important feature of these algorithms is that they do not use a stack.

SHAMP: An experimental shared memory multimicroprocessor system for performance evaluation of parallel algorithms

In this paper, the design and implementation of a single shared bus, shared memory multiprocessing system using Intel's single board computers is presented. The hardware configuration and the operating system developed to execute the parallel algorithms are discussed. The performance evaluation studies carried out on Image are outlined.

Structured model-following neuro-adaptive design for attitude maneuver of rigid bodies

A new structured model-following adaptive approach is presented in this paper to achieve large attitude maneuvers of rigid bodies. First, a nominal controller is designed using the dynamic inversion philosophy. Next, a neuro- adaptive design is proposed to augment the nominal design in order to assure robust performance in the presence of parameter inaccuracies as well as unknown constant external disturbances. The structured approach proposed in this paper (where kinematic and dynamic equations are handled separately), reduces the complexity of the controller structure. From simulation studies, this adaptive controller is found to be very effective in assuring robust performance.

The poly dA helix: a new structural motif for high performance DNA-based molecular switches

We report a pH-dependent conformational transition in short, defined homopolymeric deoxyadenosines (dA(15)) from a single helical structure with stacked nucleobases at neutral pH to a double-helical, parallel-stranded duplex held together by AH-HA base pairs at acidic pH. Using native PAGE, 2D NMR, circular dichroism (CD) and fluorescence spectroscopy, we have characterized the two different pH dependent forms of dA(15). The pH-triggered transition between the two defined helical forms of dA(15) is characterized by CD and fluorescence. The kinetics of this conformational switch is found to occur on a millisecond time scale. This robust, highly reversible, pH-induced transition between the two well-defined structured states of dA(15)represents a new molecular building block for the construction of quick-response, pH-switchable architectures in structural DNA nanotechnology.

A new parallel algorithm for parsing arithmetic infix expressions

A new parallel algorithm for transforming an arithmetic infix expression into a par se tree is presented. The technique is based on a result due to Fischer (1980) which enables the construction of the parse tree, by appropriately scanning the vector of precedence values associated with the elements of the expression. The algorithm presented here is suitable for execution on a shared memory model of an SIMD machine with no read/write conflicts permitted. It uses O(n) processors and has a time complexity of O(log2n) where n is the expression length. Parallel algorithms for generating code for an SIMD machine are also presented.

A new algorithm for parallel solution of linear equations

Abstract is not available.

Evolution of cooperation by reciprocation within structured demes

The iterative two-person Prisoners’ Dilemma game has been generalised to theN-person case. The evolution of cooperation is explored by matching the Tit For Tat (TFT) strategy (Axelrod and Hamilton 1981) against the selfish strategy. Extension of TFT toN-person situations yields a graded set of strategies from the softest TFT, which continues cooperation even if only one of the opponents reciprocates it, to the hardest, which would do so only when all the remaining opponents cooperate. The hardest TFT can go to fixation against the selfish strategy provided it crosses a threshold frequencypc. All the other TFT are invadable by the selfish (D) or the pure defector strategy, while none can invadeD. Yet, provided a thresholdpc is crossed, they can coexist stably withD. AsN, the size of the group increases, the threshold pc also increases, indicating that the evolution of cooperation is more difficult for larger groups. Under certain conditions, only the soft TFT can coexist stably against the selfish strategyD, while the harder ones cannot. An interesting possibility of a complete takeover of the selfish population by successive invasions by harder and harder TFT strategies is also presented.

Parallel processor scheduling for minimizing total weighted tardiness using ant colony optimization

In the modern business environment, meeting due dates and avoiding delay penalties are very important goals that can be accomplished by minimizing total weighted tardiness. We consider a scheduling problem in a system of parallel processors with the objective of minimizing total weighted tardiness. Our aim in the present work is to develop an efficient algorithm for solving the parallel processor problem as compared to the available heuristics in the literature and we propose the ant colony optimization approach for this problem. An extensive experimentation is conducted to evaluate the performance of the ACO approach on different problem sizes with the varied tardiness factors. Our experimentation shows that the proposed ant colony optimization algorithm is giving promising results compared to the best of the available heuristics.

Note On The Stability Of Parallel Magnetic-Fields - Comment

It is shown that the conclusions arrived at regarding the instability of an incompressible fluid cylinder in the presence of the magnetic field and the streaming velocity in a recent communication easily follow from the study of propagation characteristics of Alfvén surface waves along cylindrical plasma columns made earlier.

Topochemical dimerization of non-parallel double bonds: 7-methoxycoumarin

X-ray crystal structure analysis of 7-methoxycoumarin reveals that the reactive double bonds are rotated by about 65° with respect to each other, the centre-to-centre distance between the double bonds being 3.83 Å. In spite of this unfavourable arrangement, photodimerization occurs in the crystalline state yielding the syn-head-tail dimer as the only product. Lattice energy calculations on ground-state molecules in crystals throw light on the mechanism of the reaction.

Finite volume TVD formulation of lattice Boltzmann simulation on unstructured mesh

A numerical scheme is presented for accurate simulation of fluid flow using the lattice Boltzmann equation (LBE) on unstructured mesh. A finite volume approach is adopted to discretize the LBE on a cell-centered, arbitrary shaped, triangular tessellation. The formulation includes a formal, second order discretization using a Total Variation Diminishing (TVD) scheme for the terms representing advection of the distribution function in physical space, due to microscopic particle motion. The advantage of the LBE approach is exploited by implementing the scheme in a new computer code to run on a parallel computing system. Performance of the new formulation is systematically investigated by simulating four benchmark flows of increasing complexity, namely (1) flow in a plane channel, (2) unsteady Couette flow, (3) flow caused by a moving lid over a 2D square cavity and (4) flow over a circular cylinder. For each of these flows, the present scheme is validated with the results from Navier-Stokes computations as well as lattice Boltzmann simulations on regular mesh. It is shown that the scheme is robust and accurate for the different test problems studied.

Parallel polygon scan conversion algorithms: Performance evaluation on a shared bus architecture

In this paper, three parallel polygon scan conversion algorithms have been proposed, and their performance when executed on a shared bus architecture has been compared. It has been shown that the parallel algorithm that does not use edge coherence performs better than those that use edge coherence. Further, a multiprocessing architecture has been proposed to execute the parallel polygon scan conversion algorithms more efficiently than a single shared bus architecture.

A parallel-serial binary arbitration scheme for collision-free multi-access techniques

Multi-access techniques are widely used in computer networking and distributed multiprocessor systems. On-the-fly arbitration schemes permit one of the many contenders to access the medium without collisions. Serial arbitration is cost effective but is slow and hence unsuitable for high-speed multiprocessor environments supporting very high data transfer rates. A fully parallel arbitration scheme takes less time but is not practically realisable for large numbers of contenders. In this paper, a generalised parallel-serial scheme is proposed which significantly reduces the arbitration time and is practically realisable.

On the Kelvin-Helmholtz instability of structured plasma layers in the magnetosphere

The hydromagnetic Kelvin-Helmholtz (K-H) instability problem is studied for a three-layered system analytically by arriving at the marginal instability condition. As the magnetic field directions are taken to vary in the three regions, both the angle and finite thickness effects are seen on the instability criterion. When the relative flow speed of the plasmas on the two sides of the interfaces separating the inner and the surrounding layers is U < Uc, where Uc is the critical speed, the system is stable both for symmetric and asymmetric perturbations. However, unlike the case of the interface bounded by two semiinfinite media, Uc is no longer the minimum critical speed above which the system will be unstable for all wavenumbers; another critical speed U* > Uc is introduced due to the finiteness of the system. When Uc < U < U*, the instability can set in either through the symmetric or asymmetric mode, depending on the ratio of the plasma parameters and angle between the magnetic field directions across the boundaries. The instability arises for a finite range of wavenumbers, thus giving rise to the upper and lower cut-off frequencies for the spectra of hydromagnetic surface waves generated by the K-H instability mechanism. When U > U*, both the modes are unstable for short wavelengths. The results are finally used to explain some observational features of the dependence of hydromagnetic energy spectra in the magnetosphere on the interplanetary parameters.