The paper presents a new approach to load balancing for large distributed systems. The approach characterizes the global state uncertainty inherent in a large distributed system in terms of the fuzzy set theory and presents a fuzzy-based distributed load balancing algorithm that explicitly reflects the effect of the uncertainty in the decision making process. The notion of linguistic variables is used to model state variables that have imprecise and uncertain state values and fuzzy control to estimate the amount of consistency relaxation from the states of uncertainty sources. A fuzzy-based consistency model provides a mechanism that allows each node to make flexible scheduling and state update decisions based on the estimated degree of consistency relaxation. Simulation results show that the proposed algorithm yields a better performance, substantially reduces the number of messages required, and generally transfers fewer tasks, compared to two conventional distributed load balancing algorithms.>

The class of NP-hard problems contains many problems of considerable practical importance. The complexity of these problems is so overwhelming that exhaustive search of the solution space is not possible even using massively parallel search techniques, particularly for problems of super-exponential complexity such as flow-shop and job-shop scheduling. This two-part paper discusses a novel, inherently parallel heuristic solution technique. Part I presents this technique, known as parallel dynamic interaction (PDI), as a general solution framework that is applicable to a number of computationally intractable problems, and gives details of its general methodology. From a parallel processing standpoint, PDI is interesting because it is inherently based upon the dynamic interplay between simultaneously executing subproblems. As such, PDI has no direct serial analog, and is not directly amenable to conventional parallel processing speedup analysis. This may provide an indication that parallel processing can offer opportunities beyond simply speeding up the solution of sequentially specified algorithms. From a practical problem-solving perspective, PDI shows promise as a method capable of generating high quality solutions to exponentially and super-exponentially hard problems. For large problems, PDI is often able to find a near-optimal solution many orders of magnitude faster than the time taken for a conventional parallel branch-and-bound search to find a solution of comparable quality.>

For pt.I. see ibid., p.1006-15. This paper presents the application of parallel dynamic interaction (PDI) to three real problem domains: the flowshop scheduling problem, the job-shop scheduling problem and the vertex cover problem. Specific examples are provided as to how the general PDI framework, introduced in part I of this paper, can be applied to a particular problem. The results of an empirical study of 90 example instances of these problems indicate that PDI consistently out-performs previously published heuristics for the vertex cover problem, and can typically generate solutions within a few percent of optimal for flow-shop and job-shop problems. Out of the 76 examples for which the optimal solution could be determined, PDI was able to produce results averaging within 4% of optimal. In over 30% of the cases, PDI was able to find the optimal solution. In no case did the PDI solution deviate more than 15% from optimal. It is also seen that the time taken by PDI to arrive at these solutions is negligible compared to that taken by conventional search techniques. This provides strong empirical evidence that PDI is capable of generating high quality solutions to exponentially and super-exponentially hard problems in reasonably short periods of time.>

Performance analysis of synchronization mechanisms for simple layered task systems has recently been reported. In this paper, we develop and validate performance models for general layered task systems which are applicable to a wider range of synchronization mechanisms and parallel task systems. Synchronization mechanisms considered include both strong (barrier) synchronization and weak (partial) synchronization. The models explicitly consider overheads due to synchronization waiting time and contention for shared software and hardware resources. The models are solvable for a number of commonly used task computation time distributions and are experimentally validated on two different shared-memory multiprocessors. It is shown that the task computation behavior, the amount of intertask dependencies, synchronization overheads, and throughput of the processor-memory interconnection network interact in a multi-dimensional, but predictable, way to impact overall performance. Approximate and asymptotic models are used to demonstrate these relationships, in both qualitative and quantitative terms.

This paper considers the class of parallel computations represented by directed, acyclic task graphs. These include parallel loops, multiphase algorithms, partitioning and merging algorithms, as well as any arbitrary parallel computation that can be structured by a task graph. The paper reviews the current state of the art in stochastic bound models of parallel programs and presents new stochastic bound performance models that predict the expected execution time of parallel programs on a given shared-memory multiprocessor system; and provide qualitative and quantitative description of the relationships between the structure of parallel programs, computation and synchronization behavior of the program, and architectural features of the underlying multiprocessor system.

Performance modeling for the class of parallel computa tions structured as simple layered task systems is consid ered. Specifically studied are the effects of using different forms of inter-layer sequencing mechanisms. The paper refines and generalizes an earlier analytical performance model and presents the results of experimental validation of the model on two different multiprocessor systems. The experimental validation results show that the model is quite accurate, with average prediction errors in the range of only a few percent. Finally, the paper uses the model to investigate performance tradeoff issues for lay ered task systems using barrier versus explicit intertask sequencing mechanisms and implemented on computing systems with differing architectural features. This study shows that the relationship between the type of sequenc ing mechanism, the nature of the computation, and the features of the underlying architecture, interact in com plex ways to impact overall performance. Several inter esting and non-intuitive results are shown.

Heterogeneous parallelism includes all forms of inter-instruction parallelism. This may include both explicitly coded and compiler generated forms. It is argued that support mechanisms are needed to efficiently manage heterogeneous subcomputations at run-time, and that the important issues in the design and implementation of these mechanisms are different from those previously studied for support of loop-level parallelism. An empirical study of an actual application is presented. The study was based on variational recursive dynamics simulation of a typical four wheel vehicle. The results of the empirical study indicate that the choice of an appropriate run-time parallel processing support mechanism can have a dramatic impact upon the ability to successfully extract heterogeneous parallelism for programs. In particular, the efficiency (lack of overhead) of the support mechanisms becomes critically important as the granularity of subcomputations becomes relatively fine. The use of simple, syntactically closed constructs is suggested.>

A modeling technique for distributed computation based on a combination of directed graphs and finite automata is described. The paradigm of distributed decision-making (DDM) is used to illustrate the technique for its two primary purposes: providing a standard specification mechanism for different algorithms for solving the same problem and providing a common mechanism for objective quantitative evaluation and comparison of alternative DDM algorithms. This is accomplished through the definition of the terms performance and efficiency as they relate to the domain of DDM. The two terms, which have precise meanings with respect to the analysis of sequential algorithms, currently lack a common interpretation in the environment of DDM. In particular, they need to be expressed in terms of the information movement necessary to share state information. The method has been used extensively to conduct analyses of several distribution scheduling algorithms. This paper focuses on the model specification properties.>

A new integrated demand-assignment multiple-access (DAMA) method for multiple-bus local networks (MBLNs) is proposed and evaluated. The performance of this method is shown to be superior to independent token-passing as well as to previously proposed integrated access schemes. V-STIA, a virtual token-passing extension of a modified explicit token-passing scheme called single-token integrated access (STIA), delivers the best overall performance at medium to heavy loads while achieving good light-load performance without collision detection. Consequently, V-STIA makes the fewest possible demands on interface capabilities for DAMA support in MBLNs. Additionally, V-STIA implementation does not require simultaneous transmit capability for correct operation and greatly reduces design complexity. Performance advantages of MBLNs over an equivalent bandwidth single-bus DAMA system are established.>

Multiple-bus local networks (MBLNs) provide an architecturally simple solution to serve high-reliability high-capacity local area networks applications. Access mechanisms for MBLNs possessing stability and favorable delay characteristics are developed. A technique is proposed that uses a single explicit token to achieve demand-assignment multiple access (DAMA) to arbitrate access on all buses in the system. The performance of this algorithm in pure DAMA form and its hybrid, carrier-sense multiple access with collision detection (CSMA-CD), version are discussed. The unique features of the hybrid algorithm are that no backoff policy is needed for colliding messages and the token-passing operation is never suspended, unlike some existing hybrid DAMA approaches.>

The author describes his experience with the development of large-scale, highly parallel applications hosted on a variety of parallel processing architectures. He suggests that researchers should not become so caught up in the search for general and consistent models and programming tools for parallel processing that they forsake the ability to tailor the processing resources of the system to the requirements of the problem, and vice versa. High-level abstractions that hide architectural details may obscure performance issues that are important to the algorithm design process. It is concluded that the parallel processing community does not need a single, uniform set of models, tools or paradigms to achieve success. All that is needed is the same sort of basic design and analysis tools that have served the sequential processing community for a number of years.>

The problem of achieving fault diagnosis in a network of interconnected processing elements (called nodes) is considered. It is assumes that there is no central facility to control, coordinate or mediate among the processing elements. Every node can eventually determine the status of nodes and communication paths between them. A diagnostic algorithm for homogeneous systems (systems with only testing nodes) is given. The self-fault-diagnosis of inhomogeneous systems (systems with nodes of varying degrees of testing capability) is studied and diagnostic algorithms are proposed.>

One measure of the usefulness of a general-purpose distributed computing system is the system's ability to provide a level of performance commensurate to the degree of multiplicity of resources present in the system. A taxonomy of approaches to the resource management problem is presented in an attempt to provide a common terminology and classification mechanism necessary in addressing this problem. The taxonomy, while presented and discussed in terms of distributed scheduling, is also applicable to most types of resource management.>

An examination is made of the effects of response and stability on scheduling algorithms for general-purpose distributed computing systems. Response characterizes the time required, following a perturbation in the system state, to reach a new equilibrium state. Stability is a measure of the ability of a mechanism to detect when the effects of further actions will not improve the system state as defined by a user-defined objective. These results have implications for distributed computations in general. Analysis is based on formal communicating finite automata models of two distinct approaches to the scheduling problem, each using the objective of global optimal load balancing. The results indicate that absolute stability is not always necessary in dynamic systems for the same reasons that relatively small amounts of instability are tolerated in the design of analog control systems. It is shown that response is a very important first-order metric of dynamic scheduling behavior, and that response and stability are related.>

Tree structures, as the interconnection structure in networks of many processing elements, have interesting features such as regularity ease of expansion, simple routing, simple addressing, suitability for VLSI/WSI implementation, etc. Distributed fault tolerance of these networks is considered. It is assumed that in these structures, there does not exist any central failure-free entity for providing services such as diagnosis of faulty components, system reconfiguration after failure, control, or coordination among the processing elements. Every processing element is able to diagnose the condition of every other node or internode communication paths via a truly distributed scheme.

The problem of designing distributed fault-tolerant computing systems is considered. A model in which the network nodes are assumed to possess the ability to "test" certain other network facilities for the presence of failures is employed. Using this model, a distributed algorithm is presented which allows all the network nodes to correctly reach independent diagnoses of the condition (faulty or fault-free) of all the network nodes and internode communication facilities, provided the total number of failures oes not exceed a given bound. The proposed algorithm allows for the reentry of repaired or replaced faulty facilities back into the network, and it also has provisions for adding new nodes to the system. Sufficient conditions are obtained for designing a distributed fault-tolerant system by employing the given algorithm. The algorithm has the interesting property that it lets as many as all of the nodes and internode communication facilities fail, but upon repair or replacement of faulty facilities, the system can converge to normal operation if no more than a certain number of facilities remain faulty.

Techniques for dealing with hardware failures in very large networks of distributed processing elements are presented. A concept known as distributed fault-tolerance is introduced. A model of a large multiprocessor system is developed and techniques, based on this model, are given by which each processing element can correctly diagnose failures in all other processing elements in the system. The effect of varying system interconnection structures upon the extent and efficiency of the diagnosis process is discussed, and illustrated with an example of an actual system.

A multicode single transition-time state assignment for normal mode asynchronous sequential machines is given. The proposed state assignment requires less than or equal to 2[log2 n] state variables for flow tables with n states.

Two lower bounds on the length of terminal stuck-fault tests and a technique to facilitate detection of terminal stuck-faults are given.