We consider the problem of embedding one graph in another, where the cost of an embedding is the maximum distance in the target graph separating vertices that are adjacent in the source graph. An important special case, know as the bandwidth minimization problem, is when the target graph is a path. This author has shown that for random graphs having bandwidth at most k, a well-known heuristic produces solutions having cost not more than 3k with high probability. This paper considers generalizations of this heuristic and analyzes their performance in ...Read More

Most research in algorithm design relies on worst-case analysis for performance comparisons. Unfortunately, worst-case analysis does not always provide an adequate measure of an algorithm's effectiveness. This is particularly true in the case of heuristic algorithms for hard combinatorial problems. In such cases, analysis of the probable performance can yield more meaningful results and can provide insight leading to better algorithms. The problem of minimizing the bandwidth of a sparse symmetric matrix by performing simultaneous row and column permutations, is an example of a problem for which there are well-known ...Read More

Design considerations for picture archiving and communication systems are reviewed with special emphasis on those issues that differ from conventional network architectures. Design equations for three layers of a picture network are developed and discussed in the context of preliminary estimates of the flow of digital images between a multiplicity of picture sources, picture archives and picture viewing stations. Discussions of differences from conventional networks focuses on the local nature of the net, the availability of a wide-band transmission media with low error rates, the relative costliness of network equipment ...Read More

Parallel computing structures consisting of large numbers of processors require synchronization so that data communication among processors is possible. Two basic methods of data synchronization, synchronous and asynchronous, are considered. The synchronous or clocked method uses a global clock for synchronization. Clock skew and clock line charge and discharge times both increase with system size. This decreases the data rates achievable and prevents the design of highly modular systems. The asynchronous method has no global control structure and results in a modular and expandable system with the data rate being ...Read More

For the last decade the STRIPS paradigm has had a dominant influence on research in planning systems. More recently researchers have realized that a departure from this framework is necessary if planning systems are to be able to deal with complex, real-world environments in an intelligent, flexible, and efficient manner. The present report surveys some of the problems encountered by workers in this area, and indicates what the author believes are some of the underlying causes of the difficulties. The author then proposes the notion of a "fuzzy algorithm" as ...Read More

Abstract Database System (ADS) is a data model developed for an enduring medical information system where frequent changes in the conceptual schema are anticipated and multi-level abstraction is required. The mechanism of abstraction in ADS is based on the abstraction operator of the lamba calculus. The formal semantics of a subset of the ADS model is presented using the denotational specification method.

A new approach to modelling distributed systems is presented. It uses sequential processes and event synchronization as the major building blocks and is able to capture the functionality, architecture, scheduling policies, and performance attributes of a distributed system. The approach is meant to provide the foundation for a uniform incremental strategy for verifying both logical and performance properties of distributed systems. In addition, this approach draws together work on performance evaluation, resource allocation, and verification of concurrent processes by reducing some problems from the first two areas to equivalent problems ...Read More

A preliminary design study has been carried out for a distributed picture archiving and communication system for the Mallinckrodt Institute of Radiology. The study develops design equations for three layers of a picture network and examines the estimated flow of digital images between a multiplicity of picture sources, picture archives and picture viewing stations. Application of these data to the design equations lead to some preliminary conclusions. One network architecture consistent with these conclusions is discussed.

This paper introduces a conceptual model of communicative organization as a part of the formal semantic study of distributed computation. The model includes, as communication primitives, three independent modes of communication: mailing, posting, and broadcasting. Mailing models thin-wire communication, and posting models shared memory communication. While broadcasting is not prominent in today's parallel programming languages, it has an important role to play in distributed computation. Other fundamental notions in the model are process, symbol, site, process class, symbol class and site class.

An octal tree subdivision recursively divides a bounded three-dimensional volume into octanta about an internal division point. This scheme has been used to represent cellular or enumerated voxel models of solid objects. Given one or more sets of points sampled from the surface of a solid, an octal tree may be generated in which each leaf node contains m or less points. By specifying the tree traversal rule, the points are accessed in a sorted order. By defining m=3, a divide-and-conquer surface triangulation algorithm may be developed which does not ...Read More

This paper reports the author's experience in the use of formal specifications and presents a step by step approach to developing functional requirements for computer-based systems. A simple model of system requirements is introduced first. A systematic approach to developing requirements by starting with the general model and adapting it to the needs to the problem at hand is described and illustrated by means of the simple but realistic example. A basic knowledge of predicate calculus and set theory is assumed on the part of the reader. The presentation is ...Read More

A formal Distributed Systems Design Language (DSDL) is described. In DSDL, systems are described as nets of communicating processes. A net is defined by its processes, by the logical communications links between processes, and by the communications protocols. Each process in the net has its own local data, procedures that specify primitive operations over the data, and possesses the ability to exchange messages with other processes in the net. Some of these processes are used to model the system environment. The links identify the logical connections between processes. The way ...Read More

The paper describes a proposal for a methodology definition language and illustrates it on a variant of a well-known methodology, top-down program design. The language describes: (1) the structure of and the relations between various products of the design process (they are referred to here as configuration items and may include such things as system requirements, program specifications, module design, code, etc.); (2) changes in the state of these configuration items and consistency constraints between their states; and (3) the sequencing of design activities permitted by the methodology. A separate ...Read More

The paper reports on a technique for the formal definition of the distributed systems design methodology called the Total System Design (TSD) Methodology. Central to the formalization of the TSD Methodology is the TSD Model, which consists of several information structures and a set of consistency constraints (i.e., acceptance criteria). While the major part of this paper is taken by the model definition, the authors' intent is not simply to justify the model itself. The paper provides convincing evidence that rigorous methodology definitions are both feasible and useful. It offers ...Read More

A methodological framework is an abstraction over a class of design methodologies. The framework characteristics the problem solving approach shared by the methodologies belonging to that class: it identifies the nature of their common design concerns and the fundamental logical interdependencies between these concerns. The paper proposes a particular framework called the Total System Design (TSD) Framework. It represents a specification for a class of design methodologies which view computer-based systems as potentially distributed hardware/software aggregates. As such, the TSD Framework consolidates under a unified perspective two traditionally separate concerns: ...Read More

This paper presents an informal description of a methodology called the Total System Design (TSD) Methodology. It consists of two phases that deal with the transformation of a system requirements specification to a processing model (in the architecture design phase) and the subsequent generation of hardware and software requirements (in the binding phase). The proposed design strategy is based primarily on an extension of the concept of abstract machine hierarchies to distributed systems, while the binding strategy could be viewed as a "most constrained first" policy.

Multiple processor interconnection networks can be characterized as having N' inputs and N' outputs, each B' bits wide. Construction of large networks requires partitioning of the N'*N'*B' network into a collection of N*N switch modules of data size B (B

Interest in tightly coupled multiprocessor computer systems has grown as the possibilities for high performance with such systems have been recognized. Central to their design is the structure of the network over which the processors communicate. Unless properly designed, such networks can be both a cost and performance bottleneck. This paper focuses on the design of VLSI communications networks, this is, on communications network which can be placed on a single VLSI chip. Traditional SSI-based boost and complexity measures for such networks have principally involved switch aggregate counts. In a ...Read More

A data encoding scheme involving binary tree encodements is presented and analyzed. A closed-form formula for the number of n-bit legal memory configurations is developed. It is shown that the storage capacity loss due the use of this scheme is not significant for large n.

We have developed a formal model of a database system that is unusual in that it has the ability to represent information about its own structure and to insure semantic consistency. The model distinguishes general laws from instances of events and objects, but many of its mechanisms serve both categories of information. The model form a substrate upon which an information structure appropriate to neonatology is being developed. Some example queries are shown and a design study for an associative memory suggested by the model is described briefly.

The performance characteristics of banyan and crossbar communications networks are compared in a VLSI environment where it is assumed that the entire network resides on a single VLSI chip. A high level model of the space (area) and time (delay) requirements for these networks is developed and relative performance comparisons are made based on space-time product measure. The results differed significantly from those obtained with more traditional analyses which are usually based on switch aggregate comparisons. These analyses usually lead to the banyan as being the preferable network due to ...Read More

A semantic data model is introduced with the following capabilities: (1) Abstraction mechanisms for aggregation, generalization and classification, (2) Unstratified control of the database content, (3) Refined control of intentional and extensional information, and (4) Extensive semantic consistency checking. The basic features of the model are illustrated through a scenario of interactions between the user and the database system (using the proposed model) for constructing a simple database on technical publications.

VLSI technology provides and demands new ways of solving large scale computational problems. In light of this fact, a piplelined version of a real-time hidden surface elimination algorithm is proposed. The approach is tuned to the requirements of the VLSI technology: it is simple and regular, employs only local communciation, and attains a high degree of parallelism. The feasibility of the technique is demonstated for a computer graphics system where objects are defined in terms of planar triangular surface elements. A case is made in terms of the early 1980's ...Read More

The purpose of this paper is to demonstrate that in the event of degeneracy is present in an optimal basic solution to a linear programming problem, the optimal values of the dual variables doe no necessarily correspond to shadow prices. In such instances it will be shown how the actual values of the shadow prices may be determined and the nature of the relationship between shadow prices and dual variables.

This paper presents a straightforward approach to determining how best to utilize an MIMD multiprocessor in the solution of one dimensional optimization problems involving continuous unimodal functions and nongradient search techniques. A methodology is presented which allows one to consider a variety of speedup functions which may occur in parallel function and systems evaluation. It is shown how the best of two parallel optimization strategies can be determined for a given accuracy, number of processors and speedup function.

Many compilers incorporate an optimization phase during the development of the final object code. Most optimization phases utilize a flow graph and partition it into disjoint single entry regions to perform various global flow analyses. The interval is a commonly used single entry region and interval analyses have been developed for performing standard analyses such as live variable analysis, etc. This paper presents a technique for maintaining the interval structure as the underlying flow graph is dynamically modified. The techniques presented preserve the interval order required by many interval analyses ...Read More

Let Cn be the direct product of the bicyclic monoid C, taken n times, where n is a positive integer. It is shown that (1) every Petry net with n places can be represented by a finite subset of Cn represents a Petri net with n places, and (3) the firing rule of Petri net with n places, and (3) the firing rule of Petri nets can be defined as a faithful representation of Cn by the inverse hull of additive semigroup N^n is the set of natural numbers. A ...Read More

It is shown that behavioral semantics of Hoare's Parallel Commands can be formally specified by an extension of the regular expression, augmented by the shuffle operation and the inverse shuffle operation. As a corollary of the above, it is also shown that the problems of behavioral equivalence and deadlock-detection are solvable for the Parallel Commands.

It is shown that a mesh-connected n x (n+m) toroidal array of processors can perform Gauss-Jordan elimination without pivoting, on an n x (n+m) matrix, in 4n+m-1 steps, each step involving at most two artithmetic operations for every processor.

The effect of nondeterministic resolution times of flip-flops, used for synchronizing externally generated input events, on the reliability of fixed period and a newly introduced variable period clocked system is investigated. The failure probability of the simplest form of the two system types of compared. It is shown that in general, clocked system failure probability can be expressed as the product of three parameters representing, respectively, the effect of input arrival processes, system structures, and nondeterministic flip-flop resolution times.

A pipelined architecture for a locally distributed database system is proposed along with a simple concurrency coordination mechanism. The approach is based on the idea of serializing transaction processing throughout the database. The scheme is shown to require few coordination messages, to be deadlock free, to preserve database consistency, and to support recovery. Several performance related issues are also discussed.

Building on the fundamental assumption that effective methdologies are problem and environment dependent, a suggestion is made to distinguish between methodologies and the methodological frameworks they instantiate. TSD (Total System Development) is put forth as a candidate framework able to assist in the generation and evaluation of specific system development methodologies, where systems are defined as distributed hardware/software aggregates.

A software system development methodology is proposed. Its significance lies in the capacity to support a systematic and well-formalized error detection strategy extending from requirements definition through program implementation. A minimum set of checkpoints is suggested and verification procedures are detailed for each. The significant cost reducing potential of the approach and the way it was implemented in a production environment are also discussed.

Computing systems are now frequently composed of independently clocked subsystems that cooperate to perform the function desired for the whole. This type of architecture has many advantages and promises to be the standard for the foreseeable future. With the trend towards more and more gates per chip, the number of chips per subsystem gets smaller and smaller, and we can expect to soon see one or more subsystems per chip. This transition will require contributions from disciplines previously outside the field of chip design, and every issue will have to ...Read More