An environment to support designers in the modeling, analysis, and simulation of concurrent systems is described. It is shown how a fully nested structure model supports multilevel design and focuses attention on the interfaces between the modules which serve to encapsulate behavior. Using simple examples, it is shown how a formal graph model can be used to model behavior in three domains: control flow, data flow, and interpretation. The effectiveness of the explicit environment model in SARA is discussed and the capability to analyze correctness and evaluate performance of a system model is demonstrated. A description of the integral help designed into SARA shows how the designer can be offered consistent use of any new tool introduced to support the design process.

Some designers of software systems have recognized the need for providing interactive assistance to the users of their systems. A variety of ad hoc approaches have been used to associate assistance with various aspects of these systems. Common problems with such approaches are inconsistent availability of assistance and inaccurate assistance. A technique is presented for integrating assistance information into the design and implementation of a software system. This technique guarantees consistency and accuracy of syntactic assistance and provides a framework for integral semantic assistance information. The technique for developing self-describing systems centers around a specification of the language with which a user interacts with the system. The language is processed to produce a parser as well as on-line assistance information, error messages, and hard copy user manuals. A method for presenting this user assistance is discussed, and examples of an implemented system are provided.

This paper models the CCITT X.21 interface specification using a graph model and verifies the behavior of the interface using analysis tools accessible through UCLA's SARA (System Architects' Apprentice) design aid system. Behavior of the interface is modeled in three domains: control flow, data flow, and interpretation. Explicit models of assumed behavior for the environment and for the system under study are incorporated in a SARA world view such that systematic analysis and simulation can be applied.

Directed graphs having logical control associated with each vertex have been introduced as models of computational tasks for automatic assignment and sequencing on parallel processor systems. A brief review of their properties is given. A procedure to test the “legality” of graphs in this class is described, and leads to algorithms for counting the number of all possible executions (AND-type subgraphs), and for evaluating the probability of ever reaching a given vertex in the graph. Numerical results are given for some example graphs.

A dynamic memory allocation algorithm is presented making use of a priori information about a computer program. A two- level storage system is assumed, and a replacement algorithm is developed based upon a priori knowledge of interaction factors between any two space-taking entities associated with a computation.

An algorithm for allocation of memory resources is presented making use of a priori information about a computer program. This static allocation algorithm is based on a directed graph model of computations with particular attention to the memory allocation of programs assigned for execution on multiprocessor systems.

Given an acyclic directed graph where vertices represent computational tasks, arcs represent transfer of control, and two labels—called input and output logics—associated with each vertex show either the concurrency or the mutual exclusiveness of tasks, procedures are given to determine a lower and an upper bound on the number of processors required for maximum parallelism. The lower bound is obtained via a mean path length approach, while the upper bound is based on the structure of the graph. A detailed algorithm is given for the latter. First, some reduction rules are applied yielding a subset of the vertices which can be performed in parallel. Then the maximum cut in the graph is determined taking into account mutually exclusive vertices. Results are given for example graphs.

This paper discusses essential difficulties in calculating mean path lengths on a directed graph model of computations. This study was part of a larger study of a priori scheduling of computer programs in a parallel processing environment. Efficient approximations to mean processing time (mean path length) of programs in such an environment are given.

This paper concerns itself with the modeling of computations and systems and the generation of a priori estimates of expected computation time for given problems on given processing systems. In particular, methods are discussed for determining the probabilities of reaching vertices in a graph model of computations.

This paper reports results of experiments on models of computational sequences and models of computer systems. The validity of these models is a step in the evolution of methods for prediction of complex computer system performance. A graph model representing computational sequences was implemented and mapped onto a model of computer systems using programmable assignment and sequencing strategies. An approximate procedure for a priori estimation of path length (computation time) through an assigned graph was checked against more conventional simulation. The graph model was also perturbed to probe sensitivity of estimates of operation times, cycle factors, and branching probabilities. Problems arising in numerical weather prediction, X-ray analysis, nuclear modeling, and graph computations were transformed into acyclic directed graphs and have undergone computer analysis. Effectiveness of parallel processing, convergence properties of the successive approximation assignment and sequencing procedure, sensitivity to input parameter variation, the cost in computer time of the graph analysis, and comparison with more conventional SIMSCRIPT simulation are presented. The reduction in time required to obtain an estimate of path length compared to conventional simulation is found to range from a little less than 102to more than 104. Computational tests indicate that additional factors may be gained without severe loss in validity of the approximation.

This paper discusses cyclic to acyclic transformations performed on graphs representing computational sequences. Such transformations are critical to the development of models of computations and computer systems for performance prediction. The nature of cycles in computer programs for parallel processors is discussed. Transformations are then developed which replace cyclic graph structures by mean-value equivalent acyclic structures. The acyclic equivalents retain the noncyclic part of the structure in the original graph by evaluating a multiplicative factor associated with the mean time required for each vertex execution in the original graph. Bias introduced in the acyclic approximation is explored.

In the field of design automation, in general and in the automatic design of digital computers in particular, it is frequently necessary to translate machine descriptions and designer requests from the input language to the language of the design automation system. This process is very similar to the translation of artificial computer programming languages into machine language. Hence, it is reasonable to attempt to apply the techniques developed for writing compilers to the task of translation required within a design automation system. In this paper we will describe the use of one such tool, the meta-compiler or syntax directed compiler.[1]

This paper is a brief discussion of the preliminary specifications design automation system (DAS) for digital devices. The goal of the proposed system is to allow a systems designer to describe his initial requirements to evaluate and modify his design as it passes through the various stages automatic implementation. The development of this system is motivated by need for eneration of an extensive library of designs for use in the UCLA Variable Structure Computer System1 and by the need for a framework in which optimization research studies may be carried out. It is hoped that this system may also provide information and tools for the many industrial organizations who cannot Justify investment in a design automation system.

Pragmatic problem studies predict gains in computation speeds in a variety of computational tasks when executed on appropriate problem-oriented configurations of the variable structure computer. The economic feasibility of the system is based on utilization of essentially the same hardware in a variety of special purpose structures. This capability is achieved by programmed or physical restructuring of a part of the hardware. Existence of important classes of problems which the variable structure computer system promises to render practically computable, as well as use of the system for experiments in computer organization and for evaluation of new circuits and devices warrant construction of a variable structure computer. This paper describes the organization, programming, and hardware of a variable structure computer system presently under construction at UCLA.

The problem of optimal assignment of subcomputations of a computational task to autonomous computing structures of a variable structure computing system is investigated. In particular, it is desired to determine which computing structures should be constructed from the hardware inventory of the variable structure computing system and which subcomputations should be executed on which computing structures, and in what sequence, so as to minimize the total cost of computation (cost of restructuring of the system and the cost of the actual execution time). A successive approximation assigmnent procedure is formulated. The procedure requires representation of the computational task by a directed graph and an estimate of the number of traversals of each computational loop, as well as the branching probabilities of each conditional branching operation. Computer programs for automatic execution of the assignment procedure have been written. A numerical experiment on a problem from the area of the x-ray diffraction analysis of crystal structures indicates that the procedure is computationally practical, and also demonstrates that execution of the problem in a variable structure system leads to a considerable gain over a system of three modern high-speed general purpose computers.

Abslract.The design of a special purpose computer to operate in parallel with a general purpose computer to accelerate the diagonalization of real symmetric matrices is described.The entire system operates in a configuration described as the "Fixed-Plus-Variable" Structure Computer [1] such that the same elements used for the special computer may be reorganized for other problem applications.As a vehicle for this study it is assumed that problem properties dictated the choice of Jacobi's method.The Jaeobi method of diagonalization ~md an available program utilizing an improved technique for its execution on existing computers are described.The bases of decisions leading to design of the special purpose computer are explained.The nature of the supervisory control, which coordinates the activities of the general and speeiM purpose computers is detailed.The predicted in~ creases in speed due to the organization and parallelism and then with the superimposed effect of higher speed circuitry are evaluated.(~2 G. ESTRIN AND C. R, VISWANATHANst, raing of the awfilable inventory, the variable-stlructurc~ par~, of the system is used to shorten the overall computation time associated with any given problem.The eigenvalue problem, which arises in a variety of fields, viz.theory of vibrations, atomic and molecular spectroscopy, crystalline physics, nuclear physics, etc., [3] may be formulated as follows.Let H be an % X n matrix whose elements are real and symmetric.The problem is (o find a mmaber X and arl n-dimensional vector M such that

No abstract available.

Sequential table look-up algorithms are proposed for the evaluation of ln x and exp x. Tables of pre-computed constants are utilized in transforming the argument into a range where the function may be approximated by a simpler polynomial. In the case of ln x, x is transformed so that it falls into a close neighborhood of 1; in the case of exp x, x is transformed to a close neighborhood of 0. These algorithms are particularly effective when mechanized so as to carry out the predetermined sequence of operations without waste manipulation. Such special purpose organization is reasonable within the variable structure part of UCLA's proposed Fixed-Plus-Variable structure computer, as the same equipment may be reorganized for use in other special purpose configurations at other times. In this paper the sequential table look-up algorithms and their speed advantages over existing subroutine approximation procedures are described. The design of special purpose configurations which leads to another factor of speed increase as compared to a stored program implementation of the algorithms is presented. The properties of the supervisory control which integrate the operation of the ``fixed structure'' general purpose computer and the ``variable structure'' special purpose configurations are specified and the over-all computational gains evaluated. An order-of-magnitude increase in speed compared to existing subroutines is predicted in both cases.

Magnetic-core memory elements characteristically require bipolar applied fields. The vanishing inner diameter of toroids and the loss of the third dimension entirely in deposited thin films demands minimization of the number of wires. A configuration which has been investigated and applied in a word organized memory at the University of California at Los Angeles is illustrated in Fig. 2. It consists of a pair of mutually inverted and parallel connected transistors. The transistors are not in general symmetrical. This paper discusses some of the system considerations which determine the important design parameters. Methods for location of regions of satisfactory operation in the many-variable space of the inverted transistor pair are described. Although a particular design problem is discussed, attention is focused on the question, ``What classical and new procedures can we use to reduce the number of dimensions in such design problems?'' The power of the computer as a design tool is crucially dependent upon such processes.