Monitoring and checking the execution of a distributed program incur significant overhead due to the large number of states that need to be considered. This paper addresses two important aspects in tackling this problem: (a) atomization of the events that occur in a run, and (b) exploiting partial order semantics rather than interleaving semantics. Atomization is used to simplify analysis by compressing the events of an execution into a much smaller number of atoms. Partial order semantics promotes separation of concerns in modeling and checking program requirements involving (i) the necessary ordering among the atoms and (ii) the correctness of each atom. Ordering requirement is modeled by a set of recurrent sequences while computation requirement is modeled by a predicate that should be satisfied in the minimal state of each atom. A partially-ordered multi-set (pomset) model is presented to demonstrate the effectiveness of the approach. It is shown that property checking can be done without involving all the states of a run, regardless of the generality of the predicate involved.

The execution of a distributed program generates a large state space which needs to be checked in testing and debugging. This state space can be reduced by using atoms corresponding to code blocks before performing the checking of the required program properties. This paper presents our results in using atoms which are known at program design time for this purpose. We consider the impact of incomplete or incorrect knowledge of atoms on the validity of checking if a run is indeed atomic with respect to the identified atoms and if it satisfies the required program properties.

The execution of a distributed program generates a large state space which needs to be checked in testing and debugging. Atoms are useful abstractions in reducing the state lattice of a distributed computation; we refer to the reduced lattice as the atomic state lattice. However, general predicates remain difficult to check if they are asserted over all states. This paper presents a formulation to attack this problem involving separation of two different concerns: (a) order/synchronization requirement, and (b) computational dependency among atoms. Order requirement is modeled by the serialization of the global states reached by a synchronized set of atoms. Synchrony among atoms is specified by a synchronization predicate. Computational dependency among synchronized states is modeled by a general predicate. With this modeling assumption, the number of the states where a general predicate needs to be checked will be bounded by the number of atoms executed. Two efficient algorithms for checking a general predicate, in the cases where the synchronization predicate is conjunctive or disjunctive, are presented along with their proof of correctness.

A distributed application can be viewed as a collection of processes that execute a number of atomic actions. Atomicity is the basis for reasoning about the correctness of a program. Atomicity errors in a run typically indicate the presence of program errors. This paper formalizes the notion of atomicity of an action in a message passing program based on a weak-order relation among atoms. An atom can be a single statement or a sequence of statements in a program. Knowing the atoms, the atomicity of a run can be monitored and checked. Serialization of conflicting atoms is another generic correctness requirement. When atoms affect a common property, such as in sharing resources or maintaining a common constraint, they must be serialized in a run. This paper presents two efficient algorithms for dynamically detecting atomicity and serialization errors, accompanied with their proof of correctness.

This paper explores the use of locality of dependencies in large-scale distributed systems towards developing efficient checkpoint strategies. Dependencies among processes evolve into message interactions, which often spread and affect recovery dependencies and logging requirements. On the other hand, message interactions are usually localized within small sub-regions formed in space and time. Aiming at both minimizing message logging and localizing recovery effect, we propose a strategy that forms group checkpoints around such regions and meanwhile selectively logs inter-region messages. A simple and efficient atomic group checkpoint (AGC) protocol is developed based on the locality information of a distributed computation, e.g., in agent communication protocol sessions in multi-agent systems. Atomicity guarantees consistency of group checkpoint and uniformity of group logging, and hence minimizes logging overhead. The correctness of the AGC protocol is analyzed and proved through a generic checkpoint dependency graph (CDG) model, which captures the recovery dependency relations among checkpoints

This paper addresses the problems of state space decomposition and predicate detection in a distributed computation involving asynchronous messages. We introduce a natural communication dependency which leads to the definition of the communication graph. This abstraction proves to be a useful tool to decompose the state lattice of a distributed computation into simpler structures, known as concurrent intervals. Efficient algorithms have been proposed in the literature to detect special classes of predicates, such as conjunctive predicates and bounded sum predicates. We show that more general classes of predicates can be detected when proper constraints are imposed on the underlying computations. In particular, we introduce a class of predicates, defined as separable predicates, that properly includes the above-mentioned classes. We show that separable predicates can be efficiently detected on distributed computations whose communication graphs satisfy the series-parallel constraint.

This paper presents a novel approach to compute discrete sine transforms (DSTs). By using a modular mapping, DSTs are approximated by the sum of a finite sequence of discrete moments. Hence, by extending our earlier technique in computing moments with an adder network only, DSTs can also be implemented easily by a systolic array primarily involving additions. The method can be applied to multidimensional DSTs as well as their inverses.

Control/observation points have been used to detect undetectable faults in delay-insensitive/speed-independent circuits but no techniques exist so far for its use in reducing the test length. The major difficulty is in deriving a safe hazard-free test. A theory for control point insertion is presented for the purpose of test length reduction of transition signaling circuits. It is based on extraction of safe behaviors from the original usage protocol via gap detection (identification of unnecessary behavior) and gap matching (jumping from one partial state to another). The area overhead is low, requires only a single input pad, and can give significant reductions in test length.

This paper presents six properties, each of which, if satisfied by all the basic circuit elements used in synthesis, will also be satisfied by any delay-insensitive (DI) behavior realized by those circuit elements. Six relevant theorems are proved. The DI behaviors of classical circuit elements (e.g., AND, OR, inverter, merge, etc.) are then examined. It is found that they all satisfy the so called unique successor set (USS) property. As a result, it is proved that any DI behavior realized by a network of classical circuit elements necessarily exhibits the USS property. Some new circuit elements are needed to realize arbitrary DI behaviors (e.g., those that do not exhibit the USS property). A set of circuit elements is proposed. It is shown that these circuit elements are sufficient to implement any determinate finite state DI system.>

This paper presents a necessary and sufficient condition for realizability from signal transition graphs to circuits that use the complex gate implementation method. A polynomial time algorithm is developed for checking the condition. The advantages of performing checking in signal transition graphs lie in its avoiding state space enumeration and searching, which incur exponential complexity due to concurrency.>

Delay-insensitive (DI) circuits are a class of asynchronous circuit whose functional correctness is unaffected by component delays or wire delays. DI circuits can be considered as distributed circuits in which the system is protocol based and no global information is available. Existing truly DI implementations of state machines have so far required area which is linearly proportional to the number of states in the machine and have not yet applied the technique of state encoding which exists in synchronous design. We introduce an optimization/synthesis technique for DI sequence generators which uses implicit state encoding. An interesting result is proved: modulo-N counters using O(log N) area require only an average case time complexity of O(1).>

A syntax-directed translation procedure for the synthesis of delay-insensitive circuits from graph-theoretic specifications is presented. No isochronic fork assumption is required for the correct operation of the synthesized circuits. The synthesized circuits are different from those obtained from Ebergen's synthesis method. In Ebergen's circuits, the voltage levels of a set of wires are used to encode which input events are most recently received. Special circuit elements (the N-element or the RCEL element) and two-phase to four-phase converters are needed to change the voltage levels of the encoding wires when input events are received. In the circuits obtained from the method in this paper, the wires encoding which input events are most recently received are the outputs of the toggles. When input events are received, they are sent directly or via demultiplexers to the toggles to change the voltage levels at their outputs. Two-phase to four-phase converters are not needed. The synthesis method is compared with Ebergen's synthesis method.>

A shape matching technique based on the straight line Hough transform (SLHT) is presented. In the theta - rho space, the transform can be expressed as the sum of the translation term and the intrinsic term. This formulation allows the translation, rotation, and intrinsic parameters of the curve to be easily decoupled. A shape signature, called the scalable translation invariant rotation-to-shifting (STIRS) signature, is obtained from the theta - rho space by computing the distances between pairs of points having the same theta value. This signature is invariant to translation and can be easily normalized, and rotation in the image space corresponds to circular shifting of the signature. Matching two signatures only amounts to computing a 1D correlation. The height and location of a peak (if it exists) indicate the similarity and orientation of the test object with respect to the reference object. The location of the test object is obtained, once the orientation is known, by an inverse transform (voting) from the theta - rho space to the x-y plane.>

An optimization strategy based on time-sharing was previously proposed by the authors (1991). A process is decomposed into threads and the technique of time-sharing is applied in the synthesis of each thread and the synchronization requirements among threads. This study presents an extension of the methodology to nondeterminate processes. The synchronization requirements among threads include the passing of choice information as well as the causal relations between events from different threads. Substantial reduction in circuitry for realizing the synchronization requirements is observed if the choice states of threads are atomic (necessarily reached) and all the occurrences of an action belong to a thread. A theory on extracting threads that have the above properties and on synthesizing the synchronization requirements among threads is outlined.>

A novel approach for the detection of parametric curves using the straight-line Hough transform is presented. The transform function of a curve can be expressed as the sum of two terms, namely, the intrinsic term and the translation term. This representation allows a natural decomposition of the high-dimensional parameter space into three subspaces: the intrinsic curve parameters, translation, and rotation. By eliminating either the translation term or the intrinsic term, one can easily determine the parameters of the remaining term. The complexity of this method depends mainly on the angular resolution, which is relatively independent of the arc length of the curve. The computational complexity of this approach compares favorably with that of other approaches based on the Hough transform.>

Several designs are presented for VLSI dictionary machines that combine both a linear (modify) network and a logarithmic (query) network with a novel idea for separation of concerns. The initial design objectives included: (1) single-cycle operability of host-issued modify and query commands (no compress instructions), (2) complete processor utilization (no waste processors), and (3) optimal 2 log n response times, where n is the current population of the machine. The authors sought simple ideas that, for the first time, would allow all three objectives to be achieved simultaneously. They were forced to abandon objective (3), instead achieving a slightly weaker objective, namely, near-optimal (2 log n+R) response times, where R is the time for a round trip through the particular prenetwork used to connect the host to the roots of the query trees in the logarithmic network. Both sorted and unsorted versions of dictionary machines are presented. Those with orthogonal command networks achieve all objectives; those without orthogonal networks achieve only the first and third.>

Presents a critical study of two approaches, the classical RC-cut approach and H.T. Kung and M.S. Lam's (Proc. 1984 MIT Conf. Advanced Res. VLSI p.74-83, 1984) RCS-cut approach, for reconfiguring faulty systolic arrays. The amount of cell (processing element) redundancy needed to ensure successful reconfiguration into an n*n array is considered. It is shown that no polynomial bounded redundancy is sufficient for the classical approach, whereas O(n/sup 2/log n) redundancy is sufficient for the Kung and Lams approach. The number of faulty cells that can be tolerated in a given array regardless of their locations is characterized and derived. It is shown that, for both approaches, in almost all cases a square array has better fault tolerance than a rectangular array having the same number of cells. A minimal fault pattern in a 2n*2n array with 3n+1 faults that is not reconfigurable into an n*n array using either of the two approaches is established.>

The problem of restructuring systolic arrays with faulty cells is considered. An approach to derive the required data-flow paths and computational sites is proposed. The data skewing requirement, which must be satisfied to find an input schedule, is also discussed. Algorithms to restructure systolic arrays for three different architectures of processing elements are presented. A systematic method to retime the restructured array using additional programmable delays so that the retimed array satisfies the data skewing requirements is developed.>

The authors consider B/sub c/-trees in a centralized system with large main memory, and show that in some cases the join operation using B/sub c/-trees out performs other join techniques. The results can be used for estimating the cost of join using B/sub c/-trees and then making a decision regarding the most efficient join technique to be used.>

A combined methodology is presented for specifying abstract synchronous data types and proving the correctness of systolic network implementations. It is shown that an extension of the Parnas trace method of specifying software modules containing distinct access programs yields a natural method of specifying abstract synchronous data types that possess distinct access operators and are intended for implementation in VLSI. Associated systematic proof techniques are presented, and the correctness of several novel systolic network implementations of familiar data types is established. The methodology appears to be naturally suited to systolic network implementations with their associated rippling of control flow and data flow. The important distinction between systolic control-flow networks and systolic data-flow networks is presented.>

Software metrics are computed for the purpose of evaluating certain characteristics of the software developed. A Fortran static source code analyzer, FORTRANAL, was developed to study 31 metrics, including a new hybrid metric introduced in this paper, and applied to a database of 255 programs, all of which were student assignments. Comparisons among these metrics are performed. Their cross-correlation confirms the internal consistency of some of these metrics which belong to the same class. To remedy the incompleteness of most of these metrics, the proposed metric incorporates context sensitivity to structural attributes extracted from a flow graph. It is also concluded that many volume metrics have similar performance while some control metrics surprisingly correlate well with typical volume metrics in the test samples used. A flexible class of hybrid metric can incorporate both volume and control attributes in assessing software complexity.

A distributed multiprocessor traffic control system is explained. In the distributed hierarchy, the decomposition of physical modules as well as task modules forms the center of investigation. By using the inexpensive microprocessors to form the lower level modules, and using them to monitor and compute the real time parameters, a satisfactory and self-optimizing system is available. It is anticipated that the system can handle up to 100 traffic junctions in a network.

Scheduling task trees to be executed in parallel and/or pipelined processing systems are examined under individual situations. Processor structural requirements at task nodes are also included in the model of consideration. While simple techniques can serve as heuristics, counterexamples are constructed in some crucial cases. Simple optimal algorithms are presented in two important cases: 1) unistructure, multipipe, uniform latency, and flush time; and 2) vector loops. Finally, the complexity of the remaining cases is scrutinized with different structural parameter combinations.

Recent advances in multiprogramming have been concentrated on multiprocessor systems. But overlap in operations is also permissible in uniprocessor systems in which the processor instruction execution and input–output operations are handled by separate units. By maximizing the processor and input–output overlap, a program can be executed faster while the system utilization is highly improved.

With the developments of parallel computer systems, the techniques for the recognition and representation of parallel task streams in a job (program) have become important to enhance the system performance.