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.

Implementation of CSP-S for description of distributed algorithms

The implementation of CSP-S (a subset of CSP)—a high level language for distributed programming—is presented in this paper. The language CSP-S features a parallel command, communication by message passing and the use of guarded command. The implementation consists of a compiler translating the CSP-S constructs into intermediate language. The execution is carried out by a scheduler which creates an illusion of concurrency. Using the CSP-S language constructs, distributed algorithms are written, executed and tested with the compiler designed.

2 Algorithms For 3-Layer Channel Routing

A channel router is an important design aid in the design automation of VLSI circuit layout. Many algorithms have been developed based on various wiring models with routing done on two layers. With the recent advances in VLSI process technology, it is possible to have three independent layers for interconnection. In this paper two algorithms are presented for three-layer channel routing. The first assumes a very simple wiring model. This enables the routing problem to be solved optimally in a time of O(n log n). The second algorithm is for a different wiring model and has an upper bound of O(n2) for its execution time. It uses fewer horizontal tracks than the first algorithm. For the second model the channel width is not bounded by the channel density.

A Huge Effect of Weak dc Electrical Fields on Grain Growth in Zirconia

We show that the application of a modest dc electrical field, about 4 V/cm, can significantly reduce grain growth in yttria-stabilized polycrystalline zirconia. These measurements were made by annealing samples, for 10 h at 1300°C, with and without an electrical field. The finding adds a new dimension to the role of applied electrical fields in sintering and superplasticity, phenomena that are critical to the net-shape processing of ceramics. Grain-growth retardation will considerably enhance the rates of sintering and superplasticity, leading to significant energy efficiencies in the processing of ceramics.

Weak discontinuities in relativisitic MHD

By using singular surface theory and ray theory the speeds of propagation of fast and slow waves, propagating into a medium in arbitrary motion, have been obtained in relativistic magnetohydrodynamics. The differential equation governing the growth of these waves along the rays has been derived and the solution has been presented in integral form.

Relaxation Labeling with Learning Automata

Relaxation labeling processes are a class of mechanisms that solve the problem of assigning labels to objects in a manner that is consistent with respect to some domain-specific constraints. We reformulate this using the model of a team of learning automata interacting with an environment or a high-level critic that gives noisy responses as to the consistency of a tentative labeling selected by the automata. This results in an iterative linear algorithm that is itself probabilistic. Using an explicit definition of consistency we give a complete analysis of this probabilistic relaxation process using weak convergence results for stochastic algorithms. Our model can accommodate a range of uncertainties in the compatibility functions. We prove a local convergence result and show that the point of convergence depends both on the initial labeling and the constraints. The algorithm is implementable in a highly parallel fashion.

On the propagation of a weak shock front: Theory and application

In this paper the kinematics of a weak shock front governed by a hyperbolic system of conservation laws is studied. This is used to develop a method for solving problems, involving the propagation of nonlinear unimodal waves. It consists of first solving the nonlinear wave problem by moving along the bicharacteristics of the system and then fitting the shock into this solution field, so that it satisfies the necessary jump conditions. The kinematics of the shock leads in a natural way to the definition of ldquoshock-raysrdquo, which play the same role as the ldquoraysrdquo in a continuous flow. A special case of a circular cylinder introduced suddenly in a constant streaming flow is studied in detail. The shock fitted in the upstream region propagates with a velocity which is the mean of the velocities of the linear and the nonlinear wave fronts. In the downstream the solution is given by an expansion wave.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Algorithms for Constructing Hierarchical Graphs

An algorithm is described for developing a hierarchy among a set of elements having certain precedence relations. This algorithm, which is based on tracing a path through the graph, is easily implemented by a computer.

Arithmetic Algorithms in a Negative Base

Algorithms are described for the basic arithmetic operations and square rooting in a negative base. A new operation called polarization that reverses the sign of a number facilitates subtraction, using addition. Some special features of the negative-base arithmetic are also mentioned.

Implementation of placement and routing algorithms for computer aided design of printed circuit boards

The Printed Circuit Board (PCB) layout design is one of the most important and time consuming phases during equipment design process in all electronic industries. This paper is concerned with the development and implementation of a computer aided PCB design package. A set of programs which operate on a description of the circuit supplied by the user in the form of a data file and subsequently design the layout of a double-sided PCB has been developed. The algorithms used for the design of the PCB optimise the board area and the length of copper tracks used for the interconnections. The output of the package is the layout drawing of the PCB, drawn on a CALCOMP hard copy plotter and a Tektronix 4012 storage graphics display terminal. The routing density (the board area required for one component) achieved by this package is typically 0.8 sq. inch per IC. The package is implemented on a DEC 1090 system in Pascal and FORTRAN and SIGN(1) graphics package is used for display generation.

Estimation of Execution Times of Process Control Algorithms on Microcomputers

An important question which has to be answered in evaluting the suitability of a microcomputer for a control application is the time it would take to execute the specified control algorithm. In this paper, we present a method of obtaining closed-form formulas to estimate this time. These formulas are applicable to control algorithms in which arithmetic operations and matrix manipulations dominate. The method does not require writing detailed programs for implementing the control algorithm. Using this method, the execution times of a variety of control algorithms on a range of 16-bit mini- and recently announced microcomputers are calculated. The formulas have been verified independently by an analysis program, which computes the execution time bounds of control algorithms coded in Pascal when they are run on a specified micro- or minicomputer.

Intersoliton forces in weak-coupling quantum field theories

We offer a procedure for evaluating the forces exerted by solitons of weak-coupling field theories on one another. We illustrate the procedure for the kink and the antikink of the two-dimensional φ4 theory. To do this, we construct analytically a static solution of the theory which can be interpreted as a kink and an antikink held a distance R apart. This leads to a definition of the potential energy U(R) for the pair, which is seen to have all the expected features. A corresponding evaluation is also done for U(R) between a soliton and an antisoliton of the sine-Gordon theory. When this U(R) is inserted into a nonrelativistic two-body problem for the pair, it yields a set of bound states and phase shifts. These are found to agree with exact results known for the sine-Gordon field theory in those regions where U(R) is expected to be significant, i.e., when R is large compared to the soliton size. We take this agreement as support that our procedure for defining U(R) yields the correct description of the dynamics of well-separated soliton pairs. An important feature of U(R) is that it seems to give strong intersoliton forces when the coupling constant is small, as distinct from the forces between the ordinary quanta of the theory. We suggest that this is a general feature of a class of theories, and emphasize the possible relevance of this feature to real strongly interacting hadrons.

Synthesis, characterization, thermal degradation, and comparative chain dynamics studies of weak-link polysulfide polymers

Synthesis, spectroscopic and thermal characterization of two new classes of polysulfide polymers: poly[1(phenoxymethyl) ethylene polysulfide] (PPMEP), and poly [1-(phenoxy) ethylene polysulfide] (PPEP) is presented. The direct pyrolysis mass spectrometry (DP-MS) technique, used to study the thermal degradation behavior of these polysulfide polymers, indicated that the polymers underwent degradation through the weak-links scission. The thermal stability of the polysulfide polymers decreased as the ``rank'' (number of sulfur atoms in the polysulfide linkage; n=1, 2, 4) increased. The main-chain flexibility of these polysulfide polymers in terms of their C-13 NMR spinlattice relaxation time (T-1) measurements on the backbone methine (-CH-) and methylene (-CH2-) carbons are reported here for the first time. A comparative study of the solution chain dynamics indicated that it increased as ``rank'' of the polysulfide linkages decreased as well as by introducing side chain spacers such as, ether (-O-) or methyleneoxy (-CH2O-) groups.

A Proof of Convergence of the B-RED and P-RED Algorithms for Random Early Detection

In [8], we recently presented two computationally efficient algorithms named B-RED and P-RED for random early detection. In this letter, we present the mathematical proof of convergence of these algorithms under general conditions to local minima.