Data structures for parallel resource management

The problem of resource management for many processor architectures can be viewed as the problem of simultaneously updating data structures that hold system state. An approach in which the possibility of using structures with weakened specifications is examined, is presented. Specifically, data structures that weaken the specification of a priority queue, permitting it to be updated simultaneously by multiple processes are introduced. Two structures, the concurrent heap and the software banyan are proposed, along with their associated algorithms for update. The algorithms are shown to possess attractive properties of simultaneous update and throughput. The results of simulation and actual implementations show that such data structures can improve the execution times of parallel algorithms quite significantly. These structures are proposed as possible basic building blocks for implementation of resource allocation in operating systems     

Data placement in shared-nothing parallel database systems

Data placement in shared-nothing database systems has been studied extensively in the past and various placement algorithms have been proposed. However, there is no consensus on the most efficient data placement algorithm and placement is still performed manually by a database administrator with periodic reorganization to correct mistakes. This paper presents the first comprehensive simulation study of data placement issues in a shared-nothing system. The results show that current hardware technology trends have significantly changed the performance tradeoffs considered in past studies. A simplistic data placement strategy based on the new results is developed and shown to perform well for a variety of workloads. Edited by M. Adiba. Received May 11, 1993 / Accepted April 24, 1996 November 1, 1995     

Control of nondeterministic discrete-event systems for bisimulation equivalence

Most prior work on supervisory control of discrete event systems is for achieving deterministic specifications, expressed as formal languages. In this paper we study supervisory control for achieving nondeterministic specifications. Such specifications are useful when designing a system at a higher level of abstraction so that lower level details of system and its specification are omitted to obtain higher level models that may be nondeterministic. Nondeterministic specifications are also meaningful when the system to be controlled has a nondeterministic model due to the lack of information (caused for example by partial observation or unmodeled dynamics). Language equivalence is not an adequate notion of behavioral equivalence for nondeterministic systems, and instead we use the finest known notion of equivalence, namely the bisimulation equivalence. Choice of bisimulation equivalence is also supported by the fact that bisimulation equivalence specification is equivalent to a specification in the temporal logic of /spl mu/-calculus that subsumes the complete branching-time logic CTL*. Given nondeterministic models of system and its specification, we study the design of a supervisor (possibly nondeterministic) such that the controlled system is bisimilar to the specification. We obtain a small model theorem showing that a supervisor exists if and only if it exists over a certain finite state space, namely the power set of Cartesian product of system and specification state spaces. Also, the notion of state-controllability is introduced as part of a necessary and sufficient condition for the existence of a supervisor. In the special case of deterministic systems, we provide an existence condition that can be verified polynomially in both system and specification states, when the existence condition holds.     

Data structures and DBMS for computer-aided design systems

The structures for the storage of data in CAD systems influence to a large extent the effectiveness of the system. This paper reviews the wide range of data structures and database management systems (DBMS) available for structuring CAD data. Examples of basic data types are drawn from the MODULA-2 language. The relationship between these basic data types, their composite structures and the classical data models (on which many DBMS are based) is discussed, and the limitations of existing DBMS in modelling CAD data highlighted. A set of requirements for CAD database management systems is drawn up and the emerging role of product models (which seek to encapsulate the totality of data elements required to define fully an engineering artefact) is explored.     

Multilevel decomposition based nondeterministic design optimization for structural systems

The paper presents a methodology for nondeterministic design optimization of hierarchically coupled structural systems. Deterministic multilevel decomposition-based design formulations for such systems have been modified to incorporate the presence of uncertainty in both the problem parameters, and in design variables at various levels of a multilevel hierarchical system. These formulations not only allow for robust design solution strategies, but also provide a mechanism for tracking the propagation of uncertainty in such hierarchical systems. For uncertain design variables distributed across several subsystems, an iterative problem formulation is proposed. A widely used numerical example based on the design of a portal frame is used to illustrate the problem complexities in this class of design problems, and to demonstrate the effectiveness of the proposed solution techniques.     

User defined topological predicates in database systems

Current database systems cannot only store standard data like integer\underline{integer}, string\underline{string}, and real\underline{real} values, but also spatial data like points\underline{points}, lines\underline{lines}, and regions\underline{regions}. The importance of topological relationships between spatial objects has been recognized a long time ago. Using the well known 9-intersection model for describing such relationships, a lot of different topological relationships can be distinguished. For the query language of a database system it is not desirable to have such a large number of topological predicates. Particularly the query language should not be extended by a lot of predicate names. It is desirable to build new relationships from existing ones, for example to coarse the granularity. This paper describes how a database system user can define and use her own topological predicates. We show algorithms for computing such predicates in an efficient way. Last, we compare these general versions with specialized implementations of topological predicates.     

Complete open-state testing of limitedly nondeterministic systems

An approach to the problem of complete testing is proposed. Testing is interpreted as the check of an implementation’s conformance to the given requirements described by a specification. The completeness means that a test suite finds all the possible implementation errors. In practice, testing must end in a finite amount of time. In the general case, the requirements of completeness and finiteness contradict each other. However, finite complete test suites can be constructed for certain classes of implementations and specifications provided that there are specific test capabilities. Test algorithms are proposed for finite specifications and finite implementations with limited nondeterminism for the case of open-state testing. The complexity of those algorithms is estimated.     

Absolute controllability of predicates in discrete event systems

The absolute controllability of predicates in discrete event systems is studied in this paper. A predicate is absolutely controllable if it is control-invariant and the states specified by it are mutually reachable via legal states. It is shown that there is a global state feedback such that the resultant closed-loop system is strongly connected if and only if the predicate is absolutely controllable. The weakest absolutely controllable predicate stronger than the given predicate is shown to exist with respect to the given initial state. Based on the notion of the dual automaton a graph-theoretic algorithm is given to compute the set of weakest absolutely controllable predicates stronger than the given predicate. Application of the concept of absolutely controllable predicate to a class of optimal control problem is discussed. Examples are given to illustrate the results     

Exploiting symmetry of state tree structures for discrete-event systems with parallel components

We consider discrete-event systems consisting of parallel arrays of machines and buffers. The machines are divided into groups in each of which the members have identical structure, i.e. same state set and isomorphic transitions. This feature allows event relabelling of the machines in a given group to a standard prototype machine. In these systems, to avoid the underflow or overflow of the buffers, the controller needs only the information of the total numbers of components at each state and the numbers of workpieces in the buffers. By exploiting the identical structure of each group, we extract such control information from the control functions computed by the state tree structures to generate abstract control functions. Thanks to the symmetry of the system, we show that all controllable events relabelled to the same symbol share an invariant abstract control function, which is independent of the total number of machines, as long as the buffer sizes are fixed. The approach is illustrated by two examples.     

Perfect difference networks and related interconnection structures for parallel and distributed systems

In view of their applicability to parallel and distributed computer systems, interconnection networks have been studied intensively by mathematicians, computer scientists, and computer designers. In this paper, we propose an asymptotically optimal method for connecting a set of nodes into a perfect difference network (PDN) with diameter 2, so that any node is reachable from any other node in one or two hops. The PDN interconnection scheme, which is based on the mathematical notion of perfect difference sets, is optimal in the sense that it can accommodate an asymptotically maximal number of nodes with smallest possible node degree under the constraint of the network diameter being 2. We present the network architecture in its basic and bipartite forms and show how the related multidimensional PDNs can be derived. We derive the exact average internode distance and tight upper and lower bounds for the bisection width of a PDN. We conclude that PDNs and their derivatives constitute worthy additions to the repertoire of network designers and may offer additional design points that can be exploited by current and emerging technologies, including wireless and optical interconnects. Performance, algorithmic, and robustness attributes of PDNs are analyzed in a companion paper.     

Detecting global predicates in distributed systems with clocks

Summary. This paper proposes a framework for detecting global state predicates in systems of processes with approximately-synchronized real-time clocks. Timestamps from these clocks are used to define two orderings on events: “definitely occurred before” and “possibly occurred before”. These orderings lead naturally to definitions of 3 distinct detection modalities, i.e., 3 meanings of “predicate held during a computation”, namely: (“ possibly held”), (“ definitely held”), and (“ definitely held in a specific global state”). This paper defines these modalities and gives efficient algorithms for detecting them. The algorithms are based on algorithms of Garg and Waldecker, Alagar and Venkatesan, Cooper and Marzullo, and Fromentin and Raynal. Complexity analysis shows that under reasonable assumptions, these real-time-clock-based detection algorithms are less expensive than detection algorithms based on Lamport's happened-before ordering. Sample applications are given to illustrate the benefits of this approach. Received: January 1999 / Accepted: November 1999     

Controllability of predicates and languages in discrete-event systems

In discrete-event systems, two control techniques, called supervisory control and state feedback logic, are applicable if control specifications are given in terms of predicates on the set of states. The concepts of controllability for both techniques has been proposed for the analysis and design of these techniques. First it is shown that controllability of the legal language for a given predicate is equivalent to that for the corresponding reachability set. Next we deal with the relationship between the supremal controllable subpredicate of the predicate and the supremal controllable sublanguage of the corresponding legal language     

Computed torque control of fully-actuated nondeterministic multibody systems

In this paper we are interested in the dynamic behavior of a slider-crank mechanism with single and two revolute clearance joints. Due to the clearance existence in the revolute joints, it is important to choose an appropriate contact force model in analyzing the dynamic response of a slider-crank mechanism with clearances. The dynamic equations are established by combining the Newton–Euler equations with modified contact force model and improved Coulomb friction force model, and the Baumgarte stabilization approach is used to improve the numerical stability. According to numerical and experimental results, the method of continuous contact can be verified to be reasonable. Comparing dynamic the response between one clearance joint and two clearance joints in a crank-slider mechanism, it is easy to find a significant mutual coupling region due to the presence of two clearance joints by simply contact figures. The dynamic response in a mechanism with two clearance joints is not a simple superposition of that in mechanism with one clearance joint. Therefore, all the joints in a multibody system should be modeled as clearance joints.     

Complexity of verification of nondeterministic probabilistic multiagent systems

Probabilistic systems of interacting nondeterministic intelligent agents are considered. The states of agents in such systems are probabilistic databases (of facts), and their actions are controlled by probabilistic logical programs. Besides, communication channels between agents are also probabilistic. It is shown how such systems can be transformed in poynomial time to equivalent finite Markov decision processes. This makes it possible to translate the known results on the verification of the dynamic properties of the finite Markov processes to the probabilistic multiagent systems of the considered type.     

Nonblocking supervisory control of nondeterministic systems viaprioritized synchronization

Shayman and Kumar (1995) showed that supervisory control of nondeterministic discrete-event systems, in the presence of driven events, can be achieved using prioritized synchronous composition as a mechanism of control, and trajectory models as a modeling formalism, first introduced by Heymann (1990). The specifications considered in this earlier work were given by prefix-closed languages. In this paper, we extend this work to include markings so that nonclosed specifications and issues such as blocking can be addressed. It is shown that the usual notion of nonblocking, called language model nonblocking, may not be adequate in the setting of nondeterministic systems, and a stronger notion, called trajectory model nonblocking, is introduced. Necessary and sufficient conditions for the existence of language model nonblocking as well as trajectory model nonblocking supervisors are obtained for nondeterministic systems in the presence of driven events in terms of extended controllability and relative-closure conditions and a new condition called the trajectory-closure condition     

Decentralized structures for parallel Kalman filtering

Various multisensor network scenarios with signal processing tasks that are amenable to multiprocessor implementation are described. The natural origins of such multitasking are emphasized, and novel parallel structures for state estimation using the Kalman filter are proposed that extend existing results in several directions. In particular, hierarchical network structures are developed that have the property that the optimal global estimate based on all the available information can be reconstructed from estimates computed by local processor nodes solely on the basis of their own local information and transmitted to a central processor. The algorithms potentially yield an approximately linear speedup rate, are reasonably failure-resistant, and are optimized with respect to communication bandwidth and memory requirements at the various processors     

Communication styles for parallel systems

Distributed-memory parallel systems rely on explicit message exchange for communication, but the communication operations they support can differ in many aspects. One key difference is the way messages are generated or consumed. With systolic communication, a message is transmitted as it is generated. For example, the result computed by the multiplier is sent directly to the communication subsystem for transmission to another node. With memory communication, the complete message is generated and stored in memory, and then transmitted to its destination. Since sender and receiver nodes are individually controlled, they can use different communication styles. One example of memory communication is message passing: both the sender and receiver buffer the message in memory. These two communication styles place different demands on processor design. This article illustrates each style's effect on processor resources for some key application kernels. We are targeting the iWarp system because it supports both communication styles. Two parallel-program generators, one for each communication style, automatically map the sample programs