Search

The work of software cost forecasting falls into two parts. First we make what we call structural forecasts, and then we calculate the absolute dollar-volume forecasts. Structural forecasts describe the technology and function of a software project, but not its size. We allocate resources (costs) over the project's life cycle from the structural forecasts. Judgment, technical knowledge, and econometric research should combine in making the structural forecasts. A methodology based on a 25 X 7 structural forecast matrix that has been used by TRW with good results over the past few years is presented in this paper. With the structural forecast in hand, we go on to calculate the absolute dollar-volume forecasts. The general logic followed in "absolute" cost estimating can be based on either a mental process or an explicit algorithm. A cost estimating algorithm is presented and five tradition methods of software cost forecasting are described: top-down estimating, similarities and differences estimating, ratio estimating, standards estimating, and bottom-up estimating. All forecasting methods suffer from the need for a valid cost data base for many estimating situations. Software information elements that experience has shown to be useful in establishing such a data base are given in the body of the paper. Major pricing pitfalls are identified. Two case studies are presented that illustrate the software cost forecasting methodology and historical results. Topics for further work and study are suggested.

Test sequences constructed by most test generation procedures often create time dependent results when applied to a circuit. These dependencies often invalidate the test. The main cause for this situation is that the test generation procedures and circuit models employed do not take into account many aspects of delay associated with a circuit. In this paper we present modeling techniques to be used by conventional test generation procedures to alleviate some of these problems. These models include the cases of equal, unequal and ambiguous delay values. Both inertial and transport delays are considered. Both static and dynamic output behavior is studied, though we restrict inputs to fundamental mode operation. Finally, a new type of fault, caUed a delay fault, is introduced, and a model developed so that a test to detect this class of fault can be generated via conventional test generation techniques. In summary, this paper attempts to outline procedures and identify problem areas so that test generation is more of a science rather than a hit and miss process, and so that the correctness of results need not always be verified via simulation or physical fault injection.

The design methodology developed in the paper is based on an APL-like definition of logical arrays and operations on such arrays. First, the notion of a logical algorithm is introduced as a finite state automaton described by transition and output matrix. The technical realizations of such algorithms is then uniformly described as time-discrete, space-discrete, and time-space-discrete systems, and the transition of an algorithm from state-to-state (or space node-to-space node) can be explicitly formulated in a very concise way. An application of this formalism to the state reduction problem is shown. Thus the paper extends the APL-based design of logical networks beyond the area of combinational networks as developed first by Iverson.

Microprogramming is a rapidly emerging technology for the implementation of the control section of modem digital processing systems. An assessment was made of this approach to control unit design three years ago in a series of papers derived from the Third Annual Workshop on Microprogramming and published as a special issue of this TRANSACTIONS. This technology has matured in the ensuing three years, and an updated assessment has been prepared again as a special issue of this TRANSACTIONS based upon the papers presented at the Sixth Annual Workshop. The extent of realization of past predictions is reviewed and current trends are discussed. Finally, an attempt is made to assess future developments that may be expected to occur in the applications of microprogramming.

This paper shows that there exists a class of functions called data manipulating functions (DMF's), in sequential as well as paralel processors. The circuits used to achieve these functions can be considered to form an independent functional block, called a data manipulator. A basic organization applicable to both sequential and parallel processors is then suggested. The main deviation of a parallel processor orgaization from the conventional Von Neumann organization is seen to be in the bit-slice (bis) manipulating functions. A comprehensive set of bis manipulating functions from the categories of permuting, replicating, spacing and masking is given. Implementation of the last category, the masking functions, is usually through a mask register by defining its content (mask pattern). It is found that for many operations the required mask patterns are periodic and/or monotonic. The upper bounds of generating these patterns are found. The techniques and designs of two data manipulators for the first three categories of DMF's (permuting, replicating, spacing) are given. Periodic and monotonic mask patterns are also used to help in implementing some of these functions. In addition, it is shown that the data manipulator designs presented in this paper are extremely flexible to suit the requirements of various parallel processors.

An "asynchronous unit delay" is an n-input n-output asynchronous sequential circuit in which the present value of the output n-tuple is equal to the value of input n-tuple prior to the last input change. In this paper it is shown that such a circuit can be used as a basic building block in the design of any asynchronous circuit. It is shown that any fundamental mode flow table is realizable by a circuit of feedback index m with one asynchronous unit delay, m inertial delays, and a combinational network, where m is the smallest integer ≥ {log2 max (Si)} and Si is the number of stable states in any input column of the table. A straightforward method of realizing "asynchronous indefinite" fundamental mode tables without critical races by circuits of feedback index 1 with k asynchronous unit delays, one inertial delay, and combinational gates is also suggested. The approach suggested in this paper avoids complicated secondary assignment problems, results in circuits with simple structure, and further, brings closer the theories of synchronous and asynchronous sequential circuits.

This paper demonstrates two improvements in coding techniques that could be used for memory word coding. First, within the fixed structure of a Hamming single-error-correcting, double-error-detecting (SEC/DED) code, an improvement can be obtained in circuit cost and operational speed over more conventional code implementations. Second, the mechanics of error correction in a fault-tolerant computer may be carried out via conventional hardware means or by use of the existing system facilities, such as the combination of the microprogram unit, local store, and the arithmetic-logic unit. These improvements may be obtained by the use of Rotational Coding schemes in conjunction with a technique calied "lookaside correction." This paper first shows a generalized algorithm for specifying the parity check matrix of Rotational Codes. The structure implemented by the parity check matrix in this paper is not merely encoding and decoding circuitry, but translates between Rotational Code forms and byte-parity encoded forms. The unique feature of these translators is that use of the Rotational Code permits the error correction to be performed on only a subset of the data word bits, and only if a single-error condition has been detected. The correction mechanism may be either a hardware logic circuit or firmware. The paper concludes with a comparison of the circuit requirements and correctional speed of the Hamming (72, 64) single-error-correcting, double-error-detecting code, as it normally would be implemented, and a Rotational Code translator also operating on 64 data bits and 8 check bits.

The progress in integrated circuits or large-scale integration (LSI) has increased the difficulty of testing and diagnosis. This paper extends the early results of using Boolean difference to generate test patterns for sequential circuits. The theory described in this paper is based on an extended Boolean difference definition, which gives a solution to the problem of automatic generation of test patterns for asynchronous sequential circuits. A complete program written in Fortran has been tested on various examples. Results are very close to the theoretical expectation.

—This paper describes the concept of a hardware sequential decision-making device consisting principally of an array or network of nodes which can support a plurality of connections among the nodes on a simultaneous basis. The connection "chains" the nodes together. The application of the device to a dynamic computer memory allocation system is described in the paper. In this use, each "node" would correspond to a word or a group of words in a storage device, the access to which is controlled by a control unit employing the node network. Thus, only one node needs to be selected to either load a record into the controlled memory unit, or to read the record from it.

In computer operating systems where background jobs must occasionally be preempted in order to run high priority jobs, it is generally the case that efficient operation and rapid response to the high priority jobs are conflicting objectives. In this short paper a preemption scheme in which a delay is introduced is shown to provide the designer with the ability to trade off these two performance measures to any desired degree. A mathematical model is developed and results are derived for the mean high priority waiting time and a measure of operating efficiency. The paper concludes with a discussion of examples designed to illustrate how the above performance measures interact as a function of system parameters.

An extension of Petri nets called evaluation nets (E-nets) has been developed for use in representation of computer systems. These lead to interpreted graphs for use in human communication and to machine-interpretable descriptions. They may be used as aids in development of simulations and planning of measurements for examining characteristics such as throughput, turnaround time, and utilization of resources. This paper reviews the five primitives used to form nets expressing logical interactions among tokens (or tasks) flowing through the net and system resources represented by the net. Inherent in the use of the primitives is the ability to express time delays associated with the flow of tokens through the network and the modification of attributes of these tokens. This paper extends previous work on evaluation nets through the use of macro nets that represent structures made up of the primitives, allowing compression of the net for easier understanding. The macro nets are ``open-ended'' in the sense that the user can develop new macros to suit the needs of a particular study. Evaluation nets can be used informally like flow charts or block diagrams, although they provide greater power of expression than either. They can also be used more formally to develop machine aids, e.g., for on-line editing of evaluation nets or for development of simulation programs. Some examples of evaluation nets are provided that model a CDC 6400 and the cooperation of n independent sequential processes.

This paper proposes that all data elements in a computer memory be made to be self-identifying by means of a tag. The paper shows that the advantages of the change from the traditional von Neumann machine to tagged architecture are seen in all software areas including programming systems, operating systems, debugging systems, and systems of software instrumentation. It discusses the advantages that accrue to the hardware designer in the implementation and gives examples for large- and small-scale systems. The economic costs of such an implementation for a minicomputer system are examined. The paper concludes that such a machine architecture may well be a suitable replacement for the traditional von Neumann architecture.

This paper treats an aspect of the learning or estimation phase of statistical pattern recognition (and adaptive statistical decision making in general). Simple mathematical expressions are derived for the improvement in supervised learning provided by additional nonsupervised learning when the number of learning samples is large so that asymptotic approximations are appropriate. The paper consists largely of the examination of a specific example, but, as is briefly discussed, the same procedure can be applied to other parametric problems and generalization to nonparametric problems seems possible. The example treated has the additional interesting aspect that the data does not have structure that would enable the machine to learn in the nonsupervised mode alone; but the additional nonsupervised learning can provide substantial improvement over the results obtainable by supervised learning alone. A second purpose of the paper is to suggest that a new fruitful area of research is the analytical study of the possible benefits of combining supervised and nonsupervised learning.

The preceding paper proposed a general-purpose digital computer structure consisting of many small iteratively connected sequential machines. A set of machine instructions was presented and a programming example of synchronous machine operation was given. This paper examines some of the problems associated with asynchronous operation of this iteratively structured digital computer. A solution is presented enabling the many small sequential machines which constitute the large iterative computer to communicate asynchronously. The instruction set outlined in the previous paper is maintained and a pictorial example of asynchronous operation is presented.

AFTER approximately 20 years of obscurity, the field of fault-tolerant computing was revived by the formation of the IEEE Technical Committee on Fault-Tolerant Computing, by a series of articles in COMPUTER for January/ February 1971, by the 1971 International Symposium on Fault-Tolerant Computing in Pasadena, Calif., and by an IEEE TRANSACTIONS ON COMPUTERS Special Issue on Fault-Tolerant Computing in November 1971. Interest and activity continued apace, and the 1972 International Symposium on Fault-Tolerant Computing was held in Newton, Mass. Most of the excellent papers in this second IEEE TRANSACTIONS Special Issue on Fault-Tolerant Computing were presented at that symposium. As an introduction to these papers, consideration of the ultimate goals of this discipline and the universe in which our work is being done is most appropriate.

The problem of designing a minimum cost network with multipoint linkages which connects several remote terminals to a data processing center is studied. The important aspects of a teleprocessing network are queue behavior at the terminals and the cost and reliability of the entire system. In this paper it is assumed that the rate and manner in which information is requested at the terminals is known and that acceptable line loadings are given. An algorithm that determines (in principle) the optimum minimum cost network subject to reliability constraints is developed. A heuristic based on Vogel's approximation method (VAM) and two other heuristics presented by Martin and Esau-Williams were compared with each other and with the optimal algorithm. The Esau-Williams heuristic seems to be the one that gives the best solution and Martin's requires the least processing time. It is shown experimentally that Martin's and Esau-Williams heuristics are, in fact, near-optimal heurstics in the sense that the solutions provided by these heuristics are generally very near the optimal solution. In this paper we make the assumption that all lines of the network have the same capacity.

This paper is a survey of the field of translator writing systems, i.e., those programs which are used to automate the construction of compilers. The paper systematically discusses both syntax and semantics of programming languages. Under syntax, the authors consider automatic construction of recognizers (e.g., precedence techniques) and formal studies of syntax (e. g., LR(k) grammars.) Under the general topic of semantics, the authors discuss syntax directed processors with the emphasis on code generation (e.g., META), compiler-compilers (e.g., FSL) and extendible compilers (e.g., ALGOL c and Cheatham's work).

Innumerable papers by Russian authors using probabilistic models for physical systems are prefaced by a comment explaining that the results obtained must follow from dialectic materialism, and therefore the same results could in principle be derived deterministically ll as statistically, save for mathematical convenience. A similarly political motivation may unconsciously underlie many papers in the computer field which explain that ever more elaborate executive programs are motivated exclusively by a desire to increase hardware efficiency and improve system economy

The purpose of this paper is to develop design equations for switched positive-resistance digital-to-analog converters. The authors state that no synthesis method heretofore has existed for the design of this type of ladder network. The problem to which the paper addresses itself is the following

These three papers, based upon the first author's Ph. D. dissertation, are concerned with the problem of assignment and sequencing of computations on multiprocessor or parallel computer systems. Although individually the papers suffer from the usual abstracting difficulties, the results are significant and warrant serious study by readers interested in computer system modeling and analysis.

Howe has included a variety of valuable information in this paper, the unifying thread being the improvement of precision in analog devices, a topic in which he has long been a leader and innovator. This paper describes 1) precise means of implementing with hardware nonlinear mathematical models involving function generation, multiplication, and division, and 2) techniques of scaling the mathematical model so as to obtain full benefit of the precision available in the analog devices. It is unfortunate that the details of this latest work are somewhat obscured by several errors in the published paper.

In the last fifteen years many researchers working in such diverse areas as pattern recognition, parallel computation, self-reproducing automata, pattern recognition, evolution theory, information retrieval, and integrated circuit technology have found it convenient to use an array of identical intercommunicating finite-state machines as their underlying model. This naturally suggests that it would be worthwhile to develop a comprehensive theory of such arrays which would then provide a common framework for all these areas. Yamada and Amoroso have taken up this suggestion, and this paper is the first in a proposed series of papers reporting their results. However, as they readily admit, they have not attempted to produce a truly comprehensive model (an ill-defined, if not impossible, task), but rather they have been concerned with a "fairly general" model based largely on the earlier work of Moore.

In the November 1968 issue of this TRANSACTIONS, the author's paper "Automatic packaging of computer circuitry,"1was referenced in the short note, "Comments on 'An Algorithm for Synthesis of Multiple-Output Combination Logic'," by E. S. Davidson and G. Metze.2This reference might give the impression that the paper gives a procedure for packaging logic on functionally packaged circuits. This is not the case.

This paper concerning two IBM programs was written by two IBMers for an IBM publication. This might given reason to question the objectivity of the paper and its value to the general community. In actuality, though, the two programs discussed are of sufficient general interest, if for no other reason than the popularity of the machines for which they have been implemented, and the authors have maintained sufficient perspective to warrant reading of the paper by all persons interested in continuous system stimulation

Readers of this paper are likely to come away with too narrow a view of the little-known and little-appreciated art of assumed mode methods for solving distributed parameter system problems. The fact that only three references to these methods are cited is evidence of the wide scattering of the many papers which have appeared concerning these methods. The papers cited at the end of this review have been carefully selected to enable the reader to enter the most recent literature on a broader front. There the reader will find many more assumed mode methods than just the Galerkin method (which is the only one mentioned by Newman and Strauss). The reader will also find, contrary to an assertion by the authors, that assumed mode methods do not offer equal accuracy with fewer equations, as compared with nodal methods [1], although this possibility exists when a problem involves only a restricted class of system behaviors [2]. The literature also contains examples of nonlinear problems which have been solved on analog computers by assumed mode methods, e.g., [2], which the authors apparently had not encountered.

This paper is written by automata theorists for automata theorists. In numerous definitions of automata, there is an "input head" which is expected to be positioned at one square of an "input tape" at all times. There is often the possibility that the automaton might cause the input head to move right, say, from the rightmost input square, before theautomaton has had a chance to do all the computation it wanted to do. Thus, "endmarkers"—special symbols that appear on the leftmost and rightmost input squares but are not otherwise considered part of the input-are often part of the automaton definition. This paper demonstrates that in several cases the endmarkers are unnecessary in that a class of automata with end markers recognizes only languages that are recognizable by the analogous classes of automata without one or both of the endmarkers.

Although considerable progress has been made in the understanding of the more "algebraic" properties of context-free languages, the quantitative aspects of the recognition and parsing of context- free languages are still far from well understood. It was shown by Kasami and Younger that for every context-free language there exists a multitape Turing machine which recognizes this language and uses no more than n3operations to process input words of length n. For one-tape Turing machines Hartmanis showed, using the Younger algorithm, that every context-free language can be recognized in n5operations. This result has now been improved in the paper under review. It is shown, by a careful implementation of the Torii–Kasami–Ozaki algorithm on a one-tape Turing machine, that every context-free language can be recognized in n4operations. Again, just like for the n3operation multitape result, it is not known how good this time bound is. On the other hand, the authors have been able to show in this paper that for linear context-free languages n2is the least-upper time bound for their recognition on one-tape Turing machines. This is done by showing that every linear language is n2-recognizable, and by recalling that there are linear languages whose recognition requires n2 operations on a one-tape machine.

The authors of the above-mentioned paper have been informed by H. Haskal that the technique for the analysis of waveform propagation used in this paper had been previously used by Haskal and Rabinovici2 as early as 1965. This fact was unknown to the authors at the time of the publication of their paper.

This paper is little more than a rehash of well-known results, mostly from the paper of Bartee and Schneider (Information and Control, vol. 6, pp. 79-98, 1963) and from Elspas (IRE Trans. Circuit Theory, vol. CT-6, pp. 45-60, 1959). The former is not even referenced. Standard algebraic theorems, notably the Cayley-Hamilton theorem, and well-known results on companion matrices are (unnecessarily) demonstrated when a reference to, e. g., Birkhoff-Mac-Lane would have sufficed. Fig. 2 of this paper is identical to a figure on page 117 of W. W. Peterson, Error Correcting Codes (Cambridge, Mass.: M.I.T. Press, and New York: Wiley, 1961). One wonders why this paper was written at all, and what kind of review procedure it did (or did not) receive.

This is a somewhat discursive but informative article on the hybrid Apollo docking simulation. The authors do not identify their objective in writing the paper until the very last sentence of the concluding section, where they state: "It is hoped that some part of the description of the problems, solutions, and experiences will be useful to others who are now involved, or who may become involved, in simulations similar to the one described." With that as an objective,much of the detailed material on problem characteristics and specifications of the docking test device could have been condensed into an introductory or parenthetical paragraph. The discussion of why a hybrid computer was selected in preference to an all-analog or all-digital system, and of the way the problem was distributed between the analog and digital portions of the hybrid system, also adds little to the paper or to previously published material on these subjects.

This paper is an introduction which presents only the first layer of the makeup of graphics. While this layer is explained sufficiently and clearly, as in many tutorial papers, value judgements are studiously avoided. The primary purpose, therefore, of this review will be to place in perspective some of the alternatives presented.

This paper discusses the use of a hybrid simulation in the investigation of a specific synthesis procedure. Its content is divided between two subjects: a time domain synthesis procedure based on Gaussian wave functions and a hybrid computer realization of the required operations. These topics are discussed adequately enough to serve as an introduction to the material; but insufficient data are presented to determine how the procedure will compare with other analysis-synthesis systems, such as the vocoder. To determine the practicality of an approach, both a synthesis and an analysis procedure must be described, realized, and used to process significant amounts of speech. This paper discusses in detail only the realization of the synthesis procedure and thus an evaluation of the approach cannot be made at present.

The book consists of selected papers presented at the Second International Conference on Computing Methods in Optimization Problems held in San Remo, Italy, September 9–13, 1968. The purpose of the conference was to review recent advances in computational techniques of optimization problems, applied in a variety of technical areas. Thirty-one papers presented at the conference were selected to be included in this publication. These papers can be subdivided into eight basic categories. This classification and the contents of the papers will be discussed next.

This paper discusses the problems of simulating systems in which some random behavior exists. The title refers to "discrete-event simulation," but this remains undefined and unemphasized throughout most of the paper. (The expression refers to svstems in which events, such as customer arrivals, occur at a countable set of points on the continuous time axis–this as opposed to a continuous-event simulation in which important properties of the system must be accounted for over a continuum in a given time interval.) The authors trace the elements of a typical experiment and identify the statistical problems along with a discussion of their possible solutions. They isolate a number of frequently overlooked considerations in the random input process, particularly the independence of adjacent samples. Similarly, in estimating system performance, the problem of correlated outputs must be solved. In short, in any simulation, the input data and the system structure must be understood and examined carefully.

This paper presents a carefully described method for answering restricted natural language questions about elementary drawings. The algorithm produces as output a flow chart for a computer program which could then be used to infer the answer from a list structure representing the picture. The work described was performed while the author worked with Saul Amarel at the RCA Laboratories in Princeton, N.J. during the summer of 1965. The paper is well written, and its only major deficiency is that, in this rapidly moving field, a period of three and one-half years elapsed before it was published in the open literature.1

This paper should cheer both system programmers and application programmers. The authors describe the methods used to measure the performance of both the GE-625/ 635 GECOS II operating system nd the user programs running under the operating system. Anyone who works on computer operating systems or who is involved in computer system measurement and improvement would probably find this paper interesting.

One problem associated with test generation algorithms for sequential circuits is that they often produce tests which, when applied to the circuit under test, create static and/or dynamic hazards which may invalidate the test. Usually, for static hazards, but not dynamic hazards, these situations can be predicted using a logic simulator. In this paper we present procedures which can be added to path sensitization test generation algorithms so that the resulting procedure will not produce tests which will be invalidated due to hazards. Incidental to this work is a new simulation technique for handling both static and dynamic hazards. The principal concepts behind this work deal with detecting when hazards are created in a circuit; propagating hazard status information related to a signal line through a circuit; detecting those conditions at flip-flop inputs which necessitate hazard free conditions; and finally, selecting test inputs so that all hazard free conditions are satisfied.

This paper examines the dynamic fault behavior of asynchronous sequential machines, specifically identifying the faults which cause critical races and hazards, and presents a state assignment technique leading to a machine that enters one of a small set of error states whenever a fault occurs. Entry into an error state can be checked by very simple check circuits; a self-testing check circuit and one requiring only two tests for fault detection are discussed. An extension of the state assignment technique to produce a machine that is fail-safe is also presented. The fail-safe design has the property that once a fault has caused the machine to malfunction and enter an error state, the machine never leaves the error state and therefore does not produce erroneous outputs. This machine detects all but a small class of multiple faults.

This paper provides a summary of the design features of a microprogram controlled high speed signal processor referred to as an analyzer unit (AU). It provides an overview of the interrelationship between processing requirements, a language structure in which these requirements can be efficiently programmed, and an AU design that can efficiently execute the processing requirements. Particular emphasis is placed on the microprogram structure of the system computational unit, the Arithmetic Processor.

Most of the work done so far on recognition of handwritten script uses curve tracing techniques. The present paper describes a recognition scheme which is independent of the dynamics of writing and is suitable both for on-line and off-line systems. New recognition criteria, namely, the distribution of intensity of marking along and perpendicular to the direction of writing are used. Methods for correcting the inclination of script, determination of zonal limits and segmentation of the continuous script into a set of curve elements have been developed. The method of correlation is used for classification of the curve-elements. A simple grammer for the reconstruction of letters from classified segments is presented. A significant recognition has been found.

This paper investigates a potential application of microprogrammable memories to the problem of sequential network synthesis and computer design. It is shown that by allowing a controllable amount of memory redundance, a microprogrammed emulation of a state table can be organized such that decision branches in the microprogram are achieved in an immediate multiport manner, without the need of additional branch steps in the microprogram, thus increasing operational speed. A design technique is developed which, for a given state table, allows a minimum number of memory address variables to be used while minimizing the dependence of the variables on both the input and current state information. This technique has immediate practical application in the design of sequential networks, and is shown to be feasible in the controller design of a general purpost computer.

This paper describes an algorithm that is suitable for fast implementations of nonrecursive and recursive digital filters. High speed is realized at the expense of memory; however, the memory-speed tradeoff is flexible so that many hardware and software implementations are practical. When memory is not limited, the time required to compute a filter output value is independent of the order of the filter.

This paper introduces a class of programmable cellular arrays, called control arrays, and presents a technique for programming these arrays to realize asynchronous control systems. Control arrays are two-dimensional uniform networks composed of a collection of identical cells that can be independently programmed to one of two internal states. A control system is a device that controls one or more operations by means of initiation and termination signals that are transmitted through bidirectional control links. A control system model is developed by augmenting the marked graph model in order to represent constraints on the generation of these control signals. Finally, an array synthesis procedure for realizing control systems with control arrays is presented.

This paper investigates some of the problems that arise when several microprocessors share a common control memory and a common main memory. The performance with respect to both control and main memory accessing conflicts is measured for several system configurations by means of a simulation program. The program tests a set of Digital Scientific Meta 4's operating in IBM 1130 emulation mode.

This paper illustrates an algorithm for finding a read-only memory (ROM) specification, optimal in the sense that it results in a minimum ROM bit dimension, starting with an instruction set description which employs acyclic directed graphs. The algorithm selects (by a tabular technique) a descriptive graph subset, shown to be sufficient; then it performs a heuristically guided search among possible solutions generated by the graphs in the subset. The algorithm works for instructions which are such that a microevent occurs at most once in a single instruction; some results apply to the general case as well.

This paper is concerned with the problem of realizing an arbitrary syndconous or asynchronous sequential machine using only monotone AMR (or decreasing) switching functions. It has been found that h ion always exist, that in the asynchronous case only nomal fundamental mode flow tables are considered. Univesl state assignmments resulting in monotone inceasing (or next-state funtions are characterized using the concept of an (i,j) completely separating system.

This paper considers a solution to the multiprocessor scheduling problem for the case where the ordering relation between tasks can be represented as a tree. Assume that we have n identical processors, and a number of tasks to perform. Each task T i requires an amount of time μ i to complete, 0 i ≤ k, so that k is an upper bound on task time. Tasks are indivisible, so that a processor once assigned must remain assigned until the task completes (no preemption). Then the "longest path" scheduling method is almost-optimal in the following sense.

In this paper, we are concerned with the problem of generating minimal fault-detection experiments for fanout-free combinational logic networks. We establish the greatest lower bound on the necessary number of fault-detecting tests and show in a systematic way how such experiments can be obtained.

This paper describes an algorithm for the synthesis of applications-oriented microcode for a dynamically microprogrammable computer. The synthesis algorithm provides an iterative method for generating specialized architectures. Current attempts at generating specialized architectures can be considered as manual tuning due to human generation of specialized microcode. Heuristic instruction synthesis is described as one phase of a heuristic tuning process which attempts to automate the manual tuning process.

Each discrete transform has its advantages over other transforms. Fourier domain filters are easier to design than Walsh domain filters. But Walsh transforms can be computed much faster than Fourier transforms. This paper considers the problem of designing a Walsh domain filter, given a Fourier domain filter. Same procedure can be applied to other transforms. Given a Slant filter its equivalent Fourier filter or Walsh ifiter can be found.