Graph Architecture Information Processing System

1. Field of the Invention

This invention relates to a new concept for structuring an information processing system. In terms of terminology which has become well founded in the art (in reference, for example, the text book by C. G. Bell and A. Newell, "Computer Structures: Readings and Examples" published in 1971 by McGraw-Hill, Inc., New York, New York, and the reference work "Multiprocessors and Parallel Processing" by Phillip H. Enslow published by John Wiley and Sons, New York, 1974), this invention relates an architecture approach for implementing information processing systems. (Appendix VV is a catalogue of references cited.) Since there are many architectural approaches in existence in the art for the implementation of such systems, it is desirable to classify these systems so that the proper position of my invention may be identified with respect to the prior art approaches. Since there is a great disparity in the use of nomenclature in the information processing architecture art, it is also necessary to identify the nomenclature which shall be used to specifically define my invention and shall also permit contrasting my invention with the prior art.

Three differing parameters may be employed to characterize the architecture of information processing systems:

1. The number of processors utilized in the system in addition to the number of peripheral equipments employed. For the purpose of describing my invention, I shall call peripheral equipments by the nomenclature "external processors" since I consider such devices (which include line printers, card readers, keyboards and display devices) external to that portion of a system implemented in accordance with my invention which is new in the art.

2. The manner of interconnecting the processors of a system which is also called the topology of a system. In this regard, the taxonomical system for differentiating different interconnection schemes as defined in the paper "Computer Interconnection: Taxonomy, Characteristics and Examples" by G. A. Anderson and E. D. Jensen which appears in "Computing Surveys" Volume 7, No. 4, December 1975, published by the Association for Computing Machinery (ACM) is used in my description.

3. The functionality assigned to the processors of a system. In this regard, the external processors of a system usually have well-defined functional roles (such as listing the results of computations on a line printer). In contrast, the internal processors (those portions of the system not considered peripheral devices in the common nomenclature) may be of either a general purpose or of a dedicated function type. Such systems are also often called "homogeneous" systems if they utilize general purpose processors or "heterogeneous" if each processor is designed and built to perform only a selected set of functions. The differentiation of such systems and the advantages of each are clearly outlined in the current art in the paper "Innovations in Heterogeneous and Homogeneous Distributed Function Architectures" E. C. Joseph, published in the Institute for Electrical and Electronic Engineers (IEEE) Computer Magazine, March 1974.

With regards to the functionality of processors in a given system, four main functional areas may be identified:

1. Memory for containing the data to be manipulated as well as the programs which define the order of manipulations of the data. This will also be referred to as the data structure of the system and it should be noted that data structures may be implemented in hardware using general purpose memories (such as central random-access memory) or in a specialized functional manner (such as hardware stacks and queues as defined, for example, in the text by Robert R. Korfphage entitled "Discrete Computational Structures" published in 1974 by Academic Press, Inc., New York, and in the textbook "Computer Architecture" by Caxton Foster published in 1970 by Van Nostrand Reinhold Company, New York).

2. Mechanisms for manipulating the data in the data structures (memories) of the system. In practice, these may be of the general purpose type such as an arithmetic-logic unit or of a special purpose nature such as a string processor for manipulating character-oriented data structures.

3. Control mechanisms which effectively activate the data manipulations as a function of interpreting the commands also called instructions in the program.

4. Input/output mechanisms which allow the transmission of information to and from the external processors (peripheral equipment) and in so doing allow the information processing system to perform a useful purpose (for otherwise if there were no external processors, the system could neither obtain the data to be processed nor communicate the results of its computations).

With regards to the number of processors employed in a system, my invention along with many other approaches refers to a concept in which more than one processor is used in addition to any number (but at least one) of external processors. The principal advantage in these approaches over single processors systems being a net increase in performance as measured by how long in time it takes to execute a given program and/or how short a time the system can respond to a stimulus from an external processor.

With regards to the functionality of processors in a system built in accordance with my invention, it is a feature of my approach to allow specific dedicated special purpose functions to be assigned and built into each processor. For example, if two different data structures are needed in a system, then in my approach two different processors are designed and each placed at an appropriate point in the interconnection network of the system. Since the functions of the system are "distributed" amongst the processors in a system, then my invention appropriately falls into the category of "distributed function architecture" machines. Further, since each processor in my approach generally has a different design and different capabilities from each of the other processors in the system, my approach falls into the category of "heterogeneous distributed function architecture systems" in the nomenclature of the Joseph reference.

With regards to the topology of interconnection of processors in a system, the Anderson and Jensen paper define a taxonomy on the basis of four parameters which briefly are:

1. Whether messages between processors are communicated directly between one processor to another or possibly indirectly in which case the message must first be communicated through a third processor and with possible modification then communicated to the second intended processor. In my invention, message communication which I call "instruction transfer" in general may travel through intervening processors with modification and thus in my approach message transfer is indirect.

2. Whether the switching of messages from one processor to another is accomplished by a centralized mechanism (such as a so-called "cross-bar" network which is described in Anderson's paper) or on a decentralized basis wherein each processor may control the switching of messages between itself and other processors in the system with which messages can be communicated. In this respect, my invention utilizes decentralized switching using a technique and structure to which I refer as "control arcs" and defined more fully in the following portions of the specification.

3. Whether the physical paths for message (instruction) communication are shared amongst more than two processors or dedicated for communication between a first and second processor. In my invention, message paths are dedicated and the physical hardware required to form each instruction communication path is called a "control arc."

4. Whether the network of communication paths and placement of processors within this network is arranged on the basis of a regular pattern or alternately on the basis of an irregular pattern. In my invention, each practical implementation generally results in an irregular pattern.

In summary then, under the structural taxonomy convention defined by Anderson and Jensen, my invention reconstitutes a multiple processor information processing system utilizing indirect message (instruction) transmissions (communication) which are decentrally switched over dedicated message (instruction) paths resulting in a generally irregular arrangement of processors, and referred to as an IDDI category from the first letters of the words "indirect," "decentrally," "dedicated," and "irregular."

2. Description of the Prior Art

In contrast, the approach of Frank J. Perpiglia as defined in U.S. Pat. No. 3,905,023, Sept. 9, 1975, entitled "Large Scale Multi-Level Information Processing System Employing Improved Failsaft [Sic] Techniques," also refers to a system having more than one processor in addition to external processors. In the Perpiglia approach, each processor may communicate directly to any other second processor by way of a centralized non-dedicated switching network. In addition, the arrangement of processors when viewed from the block diagram level looks the same for any machine implemented in accordance with the Perpiglia concept independent of the number of processors employed and thus a machine under this concept has a regular interconnection topology. Thus, although my invention is similar to the Perpiglia approach in the sense of utilizing multiple processors, my structure varies from the Perpiglia architecture on the basis of all four major structural taxonomy parameters. In this regard, the disclosures of L. D. Amdahl et al in U.S. Pat. No. 3,226,689, Dec. 28, 1965, entitled "Modular Computer System Master Disconnect Capability"; Frederich V. Rehhauser et al in U.S. Pat. No. 3,665,421, May 23, 1972, entitled "Information Processing System Implementing Program Structures Common to Higher Level Program Languages"; and R. C. Richmond et al in U.S. Pat. No. 3,374,465, Mar. 15, 1968, entitled "Multiprocessor System Having Floating Executive Control" all describe computer architectures or means for controlling the interaction amongst the processors of systems having structural topology similar to the Perpiglia architecture and thus vary significantly in the manner of implementation and intended application from my invention.

Another prior art approach for implementing systems utilizing multiple processors is the "Electronically Controlled Microelectronic Cellular Logic Array" as disclosed by S. E. Wahlstrom in U.S. Pat. No. 3,473,160, issued Oct. 14, 1969. In this approach, direct message transmission is accomplished over dedicated decentrally switched paths. However, all processors according to Wahlstrom are required to be identical in design and each processor is required to have a fixed set of connections with an identical number of other processors so that the network is always regular and thus varies from my approach on the basis of regularity or irregularity of interconnection. The Wahlstrom approach also differs from my approach on the basis of functionality of usage of each processor. In the Wahlstrom arrangement, as well as in similar cellular array concepts such as the ILLIAC-4 computer (described in the previously cited Enslow reference ) and the theoretical Solomon approach (described in the Bell reference), each processor is capable of performing the functions of any other processor in the system and thus each processor is a general purpose processor which is, therefore, burdened with the overhead of hardware normally associated with general purpose processors. In architecture according to my invention, each processor is designed for each intended application to perform only a subset of the necessary system functions and thus my graph architecture system can be built at lower cost as less hardware is involved, or conversely, the processor may be of higher performance since specialized circuitry such as custom large-scale integrated circuits may be employed in a single specific processor without having to supply the same circuitry in all other processors in the system.

As further background to my invention, it is pointed out that a significant problem of multiple processor systems is a problem called "deadlock" and otherwise called "deadly embrace." This problem results from the possibility, as a function of how a given information processing system is programmed, that a situation may arise such that several processors request the services of other processors in the system in such a way that none of the processors can continue its activities causing the system to be deadlocked and precluding further work. The theoretical solution of this problem, as it applies to software management, is described in the article by E. G. Coffman, Jr., et al entitled "System Deadlocks" published in the ACM Computing Surveys Journal, Vol. 3, No. 2, June 1971.

Although solutions exist to this problem (as well as associated problems such as data contention) the programmer is burdened with ensuring that deadlock can never occur and this is very difficult in large systems in which many programmers are involved. A better solution is to have an architecture design of a multiple-processor system which automatically (and without programmer knowledge) inhibits the system's operation in such a way as to eliminate any possible deadlock (and since the solution is in hardware, the programmer can not do anything to make the system deadlock). The extensions necessary to the theoretical art of computer science required for such a hardware solution have been accomplished by me and reported in my doctoral thesis (Ph.D., University of Massachusetts, 1976) entitled "A Class of Multiple Processor Computers with Grammar Directed Control" published in 1976 by University Microfilms, Ann Arbor, Mich. This work in abbreviated form appears in my article "Grammar Based Multiple Processor Design," 1977 IEEE Micro-Computer Conference Record and also my chapter entitled "A Design Approach for Multiple Processor Computers" which appears as Chapter 2 in the book "Micro-computer Design and Applications" edited by Samuel C. Lee and published in 1977 by Academic Press, Inc., New York. In the thesis, I show from a theoretical point of view that a multiple processor system can be designed with no inherent deadlock problems by allowing a high-level definition of the information processing system to be specified using a notation which I call "control grammars." Well defined operations on such a control grammer (which is based upon the theory of formal languages as described in the paper "Syntax Directed Transduction" by P. M. Lewis, 2nd, and R. E. Stearns appearing in the ACM Journal, Volume 15, No. 3, July 1968, and further expanded in the textbook entitled "Compiler Design Theory" by P. M. Lewis, J. Rosenkrantz and R. E. Stearns published by Addison-Wesley Co., Reading, Mass., 1976) are used to generate the definition of interconnection of processors in the system. The relationship between the architecture of a system and its definition by control grammars is based upon a mathematics common to both the system and the grammar which is known as "graph-theory" and is discussed in the previously mentioned text by Korfphage. The main theoretical concept here is that both the interconnection of processors in an information processing system and the relationship of elements in a grammar may be depicted as "graphs" in the previously mentioned mathematical theory. It is a purpose of my invention to disclose the concept of and the means of implementing such systems without burdening the user to understanding the aforementioned mathematical theory. Since the theoretical basis of my invention is the mathematics of graphs, I have chosen to call my invention the "Graph Architecture Information Processing System."

Reference to prior art work must include the disclosure of Saul B. Dinman of "Direct Function Processor" in U.S. Pat. No. 3,631,401 issued Dec. 28, 1971. In this approach, the structural taxonomy of the system is similar to that in my system except that the interconnection of processors in limited to two levels of control wherein one level is a master processor for controlling a plurality of subprocessors. In the Dinman architecture approach, no deadlock can occur because the subprocessors are not allowed to communicate with each other, thus avoiding the deadlock issue altogether.

Another system which avoids the deadlock issue is the "Data Processing System Having Pyramidal Hierarchy Control Flow" defined in U.S. Pat. No. 3,962,685 issued June 8, 1976, to Albert P. Belle Isle and assigned to the same assignee as is my invention. In the Belle Isle architecture, any number of levels of control may be employed potentially achieving a much more powerful system than the Dinman architecture, but one single processor is still required to be the master driver of the system in such a way that full utility of the processors is limited. In my approach, there is no requirement for a first high-level master processor since deadlock is resolved on the basis of the architecture topology in conjunction with the aforementioned theory. Thus, my invention allows nearly the full performance capabilities of systems such as that defined by Perpiglia but without the burdening of software to resolve deadlock and associated problems. As in-depth discussion of the relationship of these inventions is given in the following detailed portions of my specification.

My invention also includes and implements a new concept for directly executing high level languages. High level languages differ from what is commonly referred to as machine language. In machine language, the programmer is given a set of instructions, each having a different numerically-coded operation code (which will be abbreviated as "opcode") and data parameters (which will be called simply "data"). A program is constructed by defining a specific order of these instructions. In a program, the same instruction may appear many times. When executed by a computer, the instructions are read out and the operation defined by the opcode is executed in the order of the instructions in the program. The main feature of machine language instructions is that an instruction having a specific opcode is always executed in the same way independently of instructions previously executed.

In contrast, in a high level language program, a relatively free form of data is used and programs consist of ordered sequences of alpha-numeric characters instead of the numeric data which forms the basis of machine language. It is a specific objective of a high level language to represent a form which is readily indentified by the user and relates to the type of problems being solved.

For example, in the high level language BASIC described in the previously-cited Lewis (1976) reference, the programmer is allowed to write algebraic equations as opposed to listing a sequence of memory reads, accumulator additions and the like which typify machine language programming. A peculiarity of high level languages is that a single character sequence can have entirely different meanings under different circumstances. For example, the characters "SIN" could mean a variable name or mean the sine trigonometric function. This is in sharp contrast to machine language in which a specific operation code number (opcode) always has a specific meaning.

In prior art systems, high level language capabilities are implemented by use of a program, written in machine language, which is capable of converting a high level language character sequence to the ordered instruction sequence of a machine language which is subsequently executed. This process of converting a high level language program to a machine level language program is usually called "compilation" and the mathematical process of deciphering the intended meaning of the high level language program is called "parsing." A discussion of these terms may be found in the textbook, "The theory of Parsing, Translation and Compiling" by A. V. Aho and J. D. Ullman published by Prentice-Hall, Inc., Englewood Cliffs, N.J., 1972.

In my invention, a specific processor called a METAPROCESSOR is used to interpret a high level language and generate the appropriate machine level instructions to be executed by other processors. The advantages of this approach over prior art systems include:

1. Memory requirements are reduced since only sufficient memory to contain the high level language is necessary (the additional memory required to save the machine language program in prior art devices is not needed).

2. The overall implementation of programs is simpler since only one step is necessary to run a program.

In my invention, the METAPROCESSOR may be reprogrammed to allow changes in the high level language or allow execution of programs in different high level languages. To maintain maximum speed, the programming of the METAPROCESSOR is accomplished in a machine level language. Since the language of the METAPROCESSOR allows the definition of a high level language, the METAPROCESSOR instruction set effectively defines a "meta-language". . . that is a language for defining a language (in reference see the previously-cited Aho and Ullman text). Since the METAPROCESSOR of my invention allows the direct programming of operations required for parsing and metalanguage operations, I have chosen to call this particular portion of my invention by the name METAPROCESSOR.

Prior art systems for directly executing high level languages are typified, for example, by the "Information Processing System Implementing Program Structures Common to High Level Program Languages" as defined in the above-cited U.S. Pat. No. 3,665,421 to Rehhauser et al. In the Rehhauser arrangement, hardware is added to a multi-processor system of the Perpiglia architecture to allow direct execution of high level languages.

In contrast, the concept in my METAPROCESSOR is to supply a dedicated function processor for use in systems which support the use of such processors as, for example, my own graph architecture. In addition, within the architecture of a given system, more than one METAPROCESSOR may be employed to speed up the execution of programs by assigning specific METAPROCESSORS to interpret (parse) different portions of a high level language. It is also a feature of my invention to use "classifier" and "push-down" stack mechanisms to allow the direct implementation of the language types called LL(1) as defined in the previously-mentioned Lewis text, these circuits being new and novel in the art of directly executed high level languages.

My invention also includes and implements a novel concept for performing string computations. By a "string" is meant a data structure formed by an ordered sequence of data characters. By a "character" is meant a data word of fixed size (usually 8 binary digits). This is in contrast to prior art computing systems which:

1. Use numbers as the basis for computations.

2. Perform operations on these numbers such as add and subtract to produce other numbers.

In string computing:

1. The elements (data) to be manipulated are strings.

2. Operations over the strings include the mathematical operations "alternation" and "concatenation."

String computations are useful in systems in which the problems to be solved are inherently non-numeric in nature, for example, the analysis of inputs from a student in a computer-aided instruction system to determine if the student has correctly answered a question.

In prior art systems, string computations are performed by using softward algorithms on arrays of numbers which represent strings. Typical languages which support such computation are the LISP language (as defined in reference "LISP 1.5 Primer" by Clark Weissman and published by Dickenson Publishing Co., Inc., Belmont, California, 1967) and the SNOBOL language (as described in the text "A SNOBOL 4 Primer" by R. E. Griswold and M. T. Griswold published by Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973).

As opposed to prior art systems, in my invention hardware "stacks" are used to allow a significant speed-up of string computation operations for a modest system cost. The stack approach also allows a significant reduction in program size for specific problems when compared to solutions of these problems in prior art systems. My invention takes advantage of current art high speed semiconductor memory technology to implement the hardware stacks. No predecessor hardware string processor devices appear in the prior art.

My invention also relates to an approach for storing graphic information in a reduced form and for generating complex visual presentations on a variety of different types of display devices using the same hardware processor. For example, the same processor is used to generate images for a raster scan cathode ray tube (CRT) display device and also drives a flat panel dot-addressable plasma panel type display. Prior art systems are typified by the "Method and Apparatus for Point Plotting of Graphical Data From a Coded Source Into a Buffer and For Rearranging That Data for Supply to a Raster Responsive Device" as defined in U.S. Pat. No. 3,973,245, Aug. 3, 1976, to Karl A. Belser. In contrast, in my invention, the same hardware is utilized to drive dissimilar display devices.

It is an object of the present invention to provide an information processing system having the ability to directly execute high level user languages.

It is a further object to provide a system of modular design where a plurality of processing elements may be utilized each performing different functions within the system.

It is a further object to provide a system in which similar processing elements are utilized to direct the activities of dissimilar external processors.

It is a further object to provide a system of processing elements having the capability of constructing and displaying images of arbitrary complexity from a specified set of primitive images.

It is a further object to provide a system of processing elements having the ability to develop a tree-structured organization of display image definitions.

It is a further object to provide a system including processing elements having the capability of converting information produced by a first external processor to information in a form characteristically produced by a dissimilar second external processor. The interpretation of information produced by the first processor is re-definable.

It is a further object to provide a system including processing elements having the capability of interpreting high level user languages and directing activities of the system in accordance with such interpretations.

It is a further object to provide a system including processing elements having the capability of interpreting high level user languages and directing activities of the system in accordance with such interpretations.

It is a further object to provide a system including processing elements having the ability to manipulate strings of data to effect reduction of language based data (non-numeric computations), parsing of high level algorithm programming language and editing of data files.

These and further objects of the invention will become apparent by referring to the following detailed description and accompanying drawings.

An information processing system according to my invention for a heterogeneous distributive function processing system having indirect message communication, decentralized switching, dedicated message paths and an irregular arrangement of processors (IDDI) is constructed from a plurality of processing elements integrated into a novel heterodox or heterohierarchical (i.e., non-hierarchical or other than hierarchical arrangemet which is different from those previously known) architecture defined by control grammars where both the architecture and the control grammar are based on the mathematical concept known as graph theory. The processing elements are functionally classified according to their role in the overall system as control processors, data processors and external processors. Integration is accomplished by means of dedicated communication lines providing message paths interconnecting control logic circuitry in processing elements for transmitting and receiving control signals. Data processors are processors which primarily perform data manipulation functions and are integrated into the system by their included control logic circuitry which has a capability to receive but not send control signals. Control processors are processors which, whether or not having data manipulation capabilities, primarily perform control functions, are distinguished by the fact that they include control logic circuitry having a capability of transmitting control signals and may contain additional control logic circuitry for transmitting and receiving control signals. Each dedicated communication line between two processors along with the control logic circuitry within the processor to which the line is connected is designated a "control arc." External processors are processors which communicate with control processors or data processors, perform functions comparable to peripheral devices in other systems and are "external" to the control system as they do not have control arc connections. Data lines interconnecting processors provide for data flow among processors as required.

The processors in the network are interconnected in a non-hierarchical (or heterodox or heterohierachical) structure in which control of processing elements is selective between control processors and several control processors can simultaneously exercise control over other processing elements. As an example, a training system (the implementation constituting the inventor's first reduction to practice) constructed from the above-described processing elements in the described non-hierarchical structure includes processors to perform display processing operations, input processing operations, program execution operations and mass data transfer operations.

Display processing is accomplished by an arrangement of processors for effecting construction of images on disparate display screens from similar dot-pattern information originated by one of the processors. An example includes a prior art cathode-ray-tube type display device and a cathode ray tube processor which is unique to my invention for receiving the dot-pattern information and controlling the electron beam in the cathode ray tube device to effect display of images defined by the information at sections of the device screen located by the information. The arrangement also includes a plasma panel display device and a unique plasma panel processor for controlling row and column grid lines of the plasma panel to effect display of images defined by the information at sections of the plasma panel screen located by the information. Additionally, the arrangement includes a novel display processor for generating the information defining the images and locating the sections. A novel symbols processor is also included in the arrangement for storing definitions of primitive images and definitions of images of arbitrary complexity constructed from these primitive images and which sequentially transmits information defining adjacently located primitive images to the display processor to facilitate display of complex images on the screens of the prior art display devices. A multileveled, tree-structured organization of stored information is employed, with the lowest level of information defining primitive images and the highest level defining the most complex image to be constructed from the primitive images.

Input processing is accomplished by an arrangement of processors for converting information produced by a first prior art input device (such as a sound driven pen device) to information characteristically produced by a dissimilar prior art input device (such as a typewriter-like keyboard). An example includes an input device for producing electrical signals representing locations on a plasma panel, a keyboard device for producing codes representing specific key depressions, a graph-pen processor and an operator input unit or OIU processor for receiving inputs from the graph-pen processor and codes from the keyboard device. The graph-pen processor converts the electrical signals to X and Y co-ordinate information. The input processor holds definitions of predetermined locations on the plasma panel. These locations are each defined as representing specific inputs produced by depression of keys on the keyboard device. The input processor converts co-ordinate information from the graph-pen processor to the specific keyboard inputs defined for the locations corresponding to the co-ordinates.

Program execution operations are accomplished by an arrangement of processors for interpreting high level user type languages and effecting performance of operations dictated by information from an operator and stored program material. This arrangement comprises a string processor for manipulating and comparing serial strings of data words by transferring the words among a plurality of memory stacks. The arrangement also includes a novel METAPROCESSOR comprising a memory containing rules for interpreting the high level language, state determination elements for determining states defining the order of use of said rules and selection elements for selecting rules on the basis of data comparisons or classification of program inputs.

Mass data transfer is accomplished by an arrangement of prior art processors for transferring data between processing elements.

FIG. 1 illustrates a hypothetical interconnection of a plurality of processing elements to form an information processing system in accordance with the graph architecture concept and illustrates a typical arrangement of interconnected control processing elements (CP), data processing elements (DP) and external processing elements (EP).

FIG. 2 is a diagram showing the interface signals to a typical control processor (CP.sub.i) constituting an essential element of a system as illustrated in FIG. 1 including the definition of the signal content of control arc information communication paths, a plurality of said control arc inputs to the control processor (CP) from a plurality of other control processors (CP's) and a plurality of control arc outputs from the control processor (CP) to other control (CP's) or data processors (DP's) as well as the means for a uniquely designed control processor to interface to external processors (EP's) over prior art communication means.

FIG. 3 illustrates the interface block diagram of a typical data processor (DP.sub.j) constituting a data processor of the system of FIG. 1 including multiple control arc input paths and the capability of a uniquely designed data processor to interface with external information processing elements over prior art communication means.

FIG. 4A illustrates the interconnection network of a plurality of processing elements for the training system built in accordance with the graph information processing concept referred to in the specification as representing the reduction to practice of my invention.

FIG. 4B illustrates the block diagram of the same training system depicted in FIG. 4A illustrating the data and control flow amongst the plurality of processing elements and illustrating that the data flow amongst processors need not be identical to the control arc interchange amongst the processors.

FIG. 4C illustrates an operating panel as used in the training system built in accordance with the graph architecture concept as depicted in FIGS. 4A and 4B and includes the definition of two operator input devices for allowing an operator to make inputs to the systems and a display device for giving information to the operator of the system.

FIG. 4D illustrates a program in the high level language used in the training system of FIGS. 4A, 4B and 4C for implementing a question query response scenario with the operator of the training system, said program including the coding which results in the message displayed as seen in FIG. 4C.

FIG. 4E illustrates the portion of the programming of a control processor (CP) known as METAPROCESSOR in the training system of FIG. 4A where it is identified as META and illustrates the programming necessary for the interpretation of the high level language for the example question query program illustrated in FIG. 4D.

FIG. 4F illustrates the programming of a control processor (CP) known as a Semantics Processor (SEM) in the training system of FIG. 4A (which is controlled by the METAPROCESSOR as shown in FIG. 4B) for carrying out a subset of instructions initiated by the METAPROCESSOR as determined by the execution of the sequence shown in FIG. 4E.

FIG. 4G illustrates the programmed contents of the micro-code generator read only memory for the String Processor (STG) in the system of FIG. 4A (which is controlled by the SEM processor as shown in FIG. 4B) and illustrates the step of translating instructions to micro-level register and flip-flop operations for the instructions initiated by the SEM processor as shown in FIG. 4F.

FIG. 5A illustrates in block diagram a typical implementation of a processing element in a system according to the invention and shows logic which is common amongst all processing elements and illustrates the interface of that common logic to circuitry which is unique for each type of processing element in a graph architecture machine.

FIG. 5B illustrates the detailed implementation of the Operation Input Register (501) or opcode register portion of a processor as shown in FIG. 5A for use in a processing element in a graph architecture machine, said opcode register used to hold the definition of the instruction currently being executed in a processor.

FIG. 5C illustrates the interfaces to the micro-code read only memory device in the Micro-Code Generator (503) of FIG. 5A for use in a processing element in an exemplary graph architecture machine, said read only memory device used for activating specific register level operation as a function of the opcode of the current instruction.

FIG. 5D illustrates the detailed implementation of the control logic circuit portion of the processing element of FIG. 5A for use in processing elements built in accordance to the graph architecture principle, said control logic circuit performing the functions of responding to requests for instruction execution, supplying timing signals at specific times during instruction execution and determining when the instruction has completed execution.

FIG. 5E illustrates the interconnection of two processing elements by way of the control arc concept having a control arc transmit logic in one processing element for communication to the control arc receive logic in a second processing element, with connections between these logic circuits in accordance with FIG. 2.

FIG. 5F is a block diagram on one arrangement to permit a control processor to communicate with a plurality of processing elements over multiple control arc outputs, each control arc output being in accordance with FIG. 2.

FIG. 5G is a block diagram of one arrangement to permit a single processing element to receive control signals from one or more control processors in a graph architecture machine, each control arc input being in accordance with FIGS. 2 and 3.

FIG. 5H illustrates an implementation of the control arc receive logic portion (CAR) of FIG. 5E of a processing element such as that shown in FIG. 5A.

FIG. 5J illustrates an implementation of the control arc transmit logic circuit portion of FIG. 5E for a processing element in a graph architecture machine such as that shown in FIG. 5A.

FIG. 5K illustrates an implementation of the multiple transmit expansion circuit portion of the multiple control arc tramsmit logic circuit of FIG. 5F for use in a control processor element such as that illustrated in FIG. 5A in a graph architecture system, where said control processor is required to have more than one output control arc.

FIG. 5L illustrates an implementation using standard logic for the multiple receive expansion circuit portion of FIG. 5G for a processing element required to have more than one input control arc.

FIG. 5M is a timing diagram for the circuits shown in FIGS. 5H and 5J for the case in which the receiving processing element is not active at the time the request signal is received.

FIG. 5N is a timing diagram for the circuits shown in FIGS. 5H and 5J for the case in which the receiving processing element is active at the time that a new instruction is requested.

FIG. 5P illustrates a typical interconnection of three processors using the control arc implementations of FIG. 5A and also illustrates the state control logic in two processing elements, and further illustrates that a processor may generate an instruction to a third processor as determined by a combination of an instruction from a first processor in conjunction with a current state value.

FIG. 5Q illustrates the simple case of a processing element not having means of the state control concept shown in FIG. 5P.

FIG. 5R illustrates an implementation of the state defined control logic portion (SCL) of FIG. 5P for a processing element in which the state may change only once during the execution of a given instruction input.

FIG. 5S illustrates an implementation of hardware for the state controlled logic portion (SCL) of FIG. 5P for a processing element in which the state may change several times during the execution of a single instruction input and intermediate states may be recorded on a control stack.

FIG. 5T illustrates the detailed implementation of the maintenance multiplexer concept in a processing element in a graph architecture system.

FIG. 5U illustrates an advance disable circuit of a control processor necessary for use in conjunction with the maintenance multiplexer concept for allowing access to the values of data registers and memories within an information processing system built in accordance with the graph architecture principle.

FIG. 5V illustrates the interconnection of processing elements in prior art general purpose computers having a uniprocessor capability, and showing that such a system may have any number of external processors connected to the uni-processor.

FIG. 5W illustrates the interconnection of processing elements in prior art systems built in accordance with the direct function processor concept, in which there may be a plurality of processors in addition to external processors but in which only two levels of processors are allowed.

FIG. 5X illustrates the possible interconnection of processing elements in prior art information processing systems built in accordance with the pyramidal hierarchy control flow concept, in which there may be a plurality of control levels of processors in addition to external processors.

FIG. 5Y illustrates the minimum connection of processing elements for any system built in accordance with the graph architecture principle, showing that a plurality of processors is used in addition to external processors and that no single processor is required to be a dedicated highest level control processor, and also showing the interconnection of processors in accordance with the control arc concept implementations shown in FIGS. 2, 5E, 5F, etc., and the connection to external processors over prior art communication paths.

FIG. 5Z illustrates an information processing system built in accordance with the graph architecture principle having a plurality of processing element interconnections, including multiple input arcs and multiple control loops and also showing that prior art hierarchial structures may be included as a part of an overall interconnection work.

FIG. 6A illustrates the block diagram of circuits necessary for interfacing processors of a graph architecture system with a prior art CRT type display external processing element, said circuits for use in integrating such a CRT device into a system such as depicted in FIG. 4B.

FIG. 6B illustrates the drive circuitry portion of FIG. 6A necessary for interfacing with a prior art CRT display device.

FIG. 6C illustrates an exemplary case of the refresh timing circuitry portion of FIG. 6A necessary for interfacing with a prior art CRT display device.

FIG. 6D illustrates the refresh memory circuitry portions of FIG. 6A necessary for constructing graphic information for a prior art CRT information display device.

FIG. 6E illustrates the interface timing for FIG. 6A for entering data into the refresh memory of FIG. 6D.

FIG. 6F illustrates the detailed refresh memory timing for the circuit of FIG. 6D for interfacing with a prior art CRT external processing element.

FIG. 7A illustrates interface circuitry which may be used to interface a graph architecture processing element with a prior art plasma type display external processor device, as may be used in a system as illustrated in FIG. 4B.

FIG. 7B illustrates the interface timing for the circuit of FIG. 7A for interfacing with a prior art plasma display external processing element.

FIG. 8 is a block diagram of the PROJ data processing element shown in FIGS. 4A and 4B, the purpose of which is to allow communication with a slide projector external processor.

FIG. 9 illustrates the block diagram of the PRNT data processing element shown in FIGS. 4A and 4B for interfacing with a line printer external processor.

FIG. 10 illustrates the row and column breakdown of display information on a CRT or plasma type display external processing element.

FIG. 11 illustrates the dot patterns for display of character information on a display device, so that each dot pattern may be written into any of the row and column positions of the devices of FIG. 10.

FIG. 12A illustrates the tree structure concept for constructing complex symbols from primitive symbols.

FIG. 12B illustrates the steps of generating a complex symbol in accordance with the definition of FIG. 12A in which the primitive symbols A, B, C, D and E are used to construct more complex symbols F, G and H which are in turn used to construct complex symbol I which is part of the example illustrated in FIG. 4C.

FIG. 13 is a block diagram of the symbol processing element SYM of FIGS. 4A and 4B, the purpose of which is to process the data for structures illustrated in FIG. 12A.

FIG. 14 is a block diagram of the DSPL control processor of FIGS. 4A and 4B, and the purpose of DSPL being to control the DIU, PROJ, PRNT and SYM processors.

FIG. 15 is a block diagram of the OIU control processor of FIGS. 4A and 4B, the purpose of OIU being to accept instructions from multiple sources KYBD and GRAF and control the processors META and INPT.

FIG. 16A is a block diagram of an implementation of an INPT processing element of FIGS. 4A and 4B, the purpose of which is to process operator input data.

FIG. 16B illustrates the timing for the interface between the OIU and INPUT information processing elements of FIGS. 4A, 4B, 15 and 16A.

FIG. 17A illustrates an implementation of the boot-strap control processor circuit (BOOT CIRCUIT 1502) of FIG. 15, the purpose of which is to initiate initial program loading in the system.

FIG. 17B illustrates an implementation of the repeat control processor circuit (1503) of FIG. 15, said circuit allowing multiple entry of operator entries under operator control.

FIG. 17C illustrates a detailed implementation of a keyboard control processor of FIGS. 4A and 4B which is also depicted as the KYBD in FIG. 15, said circuit allowing communication with a keyboard external processor.

FIG. 18 illustrates a detailed implementation of a GRAF control processor of FIGS. 4A and 4B which is also depicted as the GRAF PEN INTERFACE 1501 in FIG. 15, the purpose of which is to allow communication to a sound driven operator interaction device.

FIG. 19 illustrates the format of instructions and data for the OIU processor illustrated in FIG. 15, said formats specifying the meaning of instruction signals in control arcs to and from the OIU.

FIG. 20 is a block diagram of an implementation of the NUM data processing element of FIGS. 4A and 4B, the purpose of said NUM processor being to perform numeric computations.

FIG. 21 is a block diagram of an implementation of the STG data processing element of FIGS. 4A and 4B, the purpose of said STG processor being to perform computations on string data structures in a new and novel way.

FIG. 22 is a block diagram of an implementation of the SEM control processor of FIGS. 4A and 4B, the purpose of which is to control the NUM and STG processors and translate higher level instructions from the META processor into sequences of lower level NUM and STG instructions.

FIG. 23 is a block diagram of an implementation of the PMEM data processor of FIGS. 4A and 4B, the purpose of which is to store and perform operations on the program data structure in the system.

FIG. 24 is a block diagram of an implementation of the META control processor of FIGS. 4A and 4B, said META (also called METAPROCESSOR) itself constituting a new concept in interpreting high level language programs.

FIG. 25 is a block diagram of an implementation of the FD data processor of FIGS. 4A and 4B for communicating with a floppy disk external processing element.

FIG. 26 is a block diagram of an implementation of the MS control processor of FIGS. 4A and 4B for controlling the sequence of operations of the FD processor to effect communication with a mass storage.

FIG. 27 is a block diagram of an implementation of the DL data processor of FIGS. 4A and 4B, the purpose of which is to facilitate communication of data to and from the mass data transfer portion of the system.

FIG. 28 is a block diagram of an implementation of the WFB data processor of FIGS. 4A and 4B, the purpose of which is to store and allow operations on a working file data structure during program editing.

FIG. 29 is a block diagram of an implementation of the FORM control processor of FIGS. 4A and 4B, the purpose of which is to format the data for disk storage and to control the WFB, MS, DL, DSPL and OIU processors.

FIG. 30 illustrates the interface signals between the STG and SEM processors of FIGS. 4A and 4B as more fully illustrated in FIGS. 21 and 22.

FIG. 31A illustrates the input instruction format to the STG processor of FIGS. 21 and 30, said instruction consisting of the opcode and data portions of the interface.

FIG. 31B illustrates the data format for data within the STG processor illustrated in FIGS. 21 and 30.

FIG. 31C illustrates the stack address word format for the STG processor of FIGS. 21 and 30, said stack address word being used to access specific words in a stack and define status of a stack.

FIG. 32 is an implementation of the control logic portion 2104 of the STG processor of FIG. 21 in accordance with the general definition of implementation of control logic for processors as shown in FIG. 5D.

FIG. 33 illustrates the opcode and data register logic of FIG. 21 for an STG processor in accordance with the general definition of FIG. 5B.

FIG. 34 illustrates the micro-code generator logic of FIG. 21 for an STG processor in accordance with the general definition of FIG. 5C.

FIG. 35 illustrates the stack memory logic of FIG. 21 for an STG processor, the purpose of which is to store the data of stack structures.

FIG. 36 illustrates the address stack computing circuit portion of FIG. 21 for an STG processor, the purpose of which is to allow manipulations of the stack data in the stack memory of FIG. 35.

FIG. 37 illustrates the full and empty condition circuitry portion of FIG. 21 for an STG processor, the purpose of which is to determine the full and empty status of the computing stacks.

FIG. 38 illustrates the data comparison circuit portion of FIG. 21 for an STG processor, the purpose of which is to compare individual words to determine the equality of strings of data.

FIG. 39A illustrates the NOP ("no operation") instruction timing for the STG processor shown in FIG. 21, the purpose of said NOP instruction being to verify that the STG may accept instructions.

FIG. 39B illustrates the stack CLEAR instructiong timing for an STG processor of FIG. 21, the purpose of said CLEAR instruction being to initialize a data stack.

FIG. 39C illustrates the timing for the FIFO instruction in an STG processor for selecting the first-in--first-out mode of operation of a stack.

FIG. 39D illustrates the timing for the PUSH instruction in an STG for pushing data into a stack.

FIG. 39E illustrates the timing for the POP instruction in an STG for popping data from a stack.

FIG. 39F illustrates the timing for the LEN (length) instruction in an STG for determining the number of characters currently in a stack.

FIG. 39G illustrates the timing for a SAVE instruction in an STG for saving the current stack address for a stack.

FIG. 39H illustrates the timing for a COMPARE instruction in an STG for comparing a first given character to a second character in a stack.

FIG. 40 illustrates the block diagram of the interconnection of the METAPROCESSOR or META processor with other processors in the exemplary training system, and represents a portion of FIG. 4B.

FIG. 41A illustrates the format of the instruction input to a METAPROCESSOR from the OIU processor over lines illustrated in FIG. 40 comprising opcode and data information.

FIG. 41B illustrates the format of the instruction output from a METAPROCESSOR to one of the processors FORM, PMEM or SEM, each instruction comprising the META-OPCODE and META-DATA signals of FIG. 40.

FIG. 41C illustrates the format of the self-instructions in a METAPROCESSOR for controlling operations internal to the METAPROCESSOR.

FIG. 41D illustrates the format of the data used internal to a METAPROCESSOR.

FIG. 42 is a detailed implementation of the control logic 2401 of FIG. 24 for a METAPROCESSOR, the purpose of which is to generate timing signals for carrying out of operations within a METAPROCESSOR.

FIG. 43 illustrates the detailed data flow portion of FIG. 24 to the data register in a METAPROCESSOR.

FIG. 44 is a detailed implementation of the control arc transmit logic of FIG. 24 in a METAPROCESSOR in accordance with the general scheme of FIG. 5J.

FIG. 45 is a detailed implementation of the state defined control logic of FIG. 24 for a METAPROCESSOR in accordance with the general scheme of FIG. 5S.

FIG. 46 illustrates the detailed implementation of the address stack portion of FIG. 24 for a METAPROCESSOR in accordance with the general scheme of FIG. 5S.

FIG. 47 illustrates the detailed implementation of the micro-code ROM portion of FIG. 24 for a METAPROCESSOR in accordance with the general scheme of FIG. 5C.

FIG. 48 illustrates the detailed implementation of the data compare and classify circuit portion of FIG. 24 for a METAPROCESSOR for allowing the generation of condition signals which allow conditional control of the METAPROCESSOR sequences.

FIG. 49 illustrates the detailed implementation of the condition circuit portion of FIG. 24 for a METAPROCESSOR to allow conditional control.

FIG. 50 illustrates the detailed implementation of the octal conversion circuit 2412 of FIG. 24 for a METAPROCESSOR to allow the conversion of numbers from serial to word formats.

FIG. 51A illustrates the timing of operations for DIRECT instruction in a METAPROCESSOR for parsing input instructions directly to the output of a METAPROCESSOR.

FIG. 51B illustrates the timing of operations for the LOAD-LOW instruction in a METAPROCESSOR for use in loading the sequence memory.

FIG. 51C illustrates the timing of operations for the RUN-META instruction in a METAPROCESSOR for initiating the execution of a sequence of operations within a METAPROCESSOR.

FIG. 51D illustrates the timing of operations for a JUMP instruction in a METAPROCESSOR for allowing access to a sequence of instructions other than that containing the JUMP instruction.

FIG. 51E illustrates the timing of operations for a PASS instruction in a METAPROCESSOR for requesting the execution of an instruction in the PMEM, FORM or SEM processors.

FIG. 52 is a detailed implementation of the system clock and master reset circuit 1510 of FIG. 15 in an OIU processor.

FIG. 53A is a detailed implementation of the control circuit portion of FIG. 15 including both the control circuitry 1507 and a multiple control arc receiver (FORM interface circuit 1505) for an OIU processing element in accordance with the general scheme of FIGS. 5D and 5L.

FIG. 53B illustrates the detailed implementation of the data bus control circuitry portion of FIG. 15 for an OIL processor for allowing the connection to several data sources.

FIG. 54 is a detailed implementation of the control arc transmit logic of the output instruction circuit 1508 of FIG. 15 for an OIU processor in accordance with the general scheme of FIGS. 5J and 5K.

FIG. 55 is a detailed implementation of an INPT interface circuit 1506 of FIG. 15.

FIG. 56A illustrates the system clock timing in the OIU processor of FIG. 16A.

FIG. 56B illustrates the timing for the GRAF processor of FIG. 18.

FIG. 56C illustrates the timing of the BOOT control processor of FIG. 17A.

FIG. 56D illustrates the detailed timing of the repeat circuit of an OIU processor illustrated in FIG. 17B.

FIG. 56E illustrates the detailed timing of the interaction of the OIU with a KYBD control processor illustrated in FIG. 17C.

FIG. 56F illustrates the detailed timing of reception of instructions from a FORM processor to an OIU processor illustrated in FIG. 53A.

FIG. 56G illustrates the interface timing of an OIU processor with an INPT processor for the circuit illustrated in FIG. 54.

FIG. 56H illustrates the instruction interface timing of operations for an OIU processor passing out an instruction for the circuit of FIG. 54.

FIG. 56I illustrates the detailed timing for an OIU control arc transmit logic for the circuit of FIG. 54.

FIG. 57 is a block diagram of the interconnection of processing elements DSPL, SYM and DIU in the display subsystem with control processor FORM in the system of FIGS. 4A and 4B.

FIG. 58 is a block diagram of the DIU processing element 5801 of FIG. 57.

FIG. 59 illustrates the instruction and data formats for the DIU processing element of FIG. 58.

FIG. 60 is a detailed implementation of the control logic portion of FIG. 58 in a DIU processing element in accordance with the general scheme of FIG. 5D.

FIG. 61 illustrates the instruction data and microcode circuitry including 5817 of FIG. 58 for a DIU processing element in accordance with the general scheme of FIGS. 5B and 5C.

FIG. 62 illustrates the detailed implementation of the options and mode circuitry including 5805 of FIG. 58 for a DIU processing element for selectively controlling the manner in which characters are written.

FIG. 63 illustrates the detailed implementation of the DIU cursor circuitry including 5804 of FIG. 58 for a DIU processing element.

FIG. 64 illustrates the detailed implementation of the DIU processor character generation circuitry portion of FIG. 58.

FIG. 65 illustrates the timing of operations for a typical DIU processor instruction execution.

FIG. 66A illustrates the instruction (comprising opcode and data signals) input format to an SYM processor for communication over the lines illustrated in FIG. 57.

FIG. 66B illustrates the data, the row and column address word format for the SYM processor portion of FIG. 57, being the same design as for the PMEM processor of FIG. 23.

FIGS. 67A and 67B illustrate the detailed implementation of the control circuit 2301 of FIG. 23 for a SYM or PMEM processing element in accordance with the general scheme of FIG. 5D. FIG. 67A details request receipt and internal timing circuitry. FIG. 67B is a schematic of the arrangement of memories.

FIGS. 68A and 68B illustrate the detailed implementation of the instruction input register and micro-code generator portions of FIG. 23 for the SYM and PMEM processing elements in accordance with the general schemes of FIGS. 5B and 5C.

FIG. 69 illustrates the detailed implementation of the data memory portion of FIG. 23 for a SYM or PMEM processing element.

FIG. 70 illustrates the detailed implementation of the address generation circuitry portion of FIG. 23 of a SYM or PMEM processing element.

FIG. 71 illustrates the detailed timing of operations for instructions within a SYM or PMEM processing element.

The following description relates to a graph architecture concept according to my invention for structuring information processing systems. I have adopted the term "graph architecture" as descriptive of my system because, according to this concept, a network of processing elements are interconnected in a manner dictated by the intended application to any specific purpose or system using, as noted in the background discussion above, principles of graph theory. A hypothetical exemplary graph acrhitecture for such a network is illustrated in FIG. 1. In that FIGURE graphically illustrating the novel architecture, each of the circles represents a processing element (PE) of one of three types designated by me as a control processor (CP), a data processor (DP) and an external processor (EP), respectively according to its nature or function. A control processor (CP) is defined as a processing element which directs the actions of other processing elements. A data processor (DP) is a processing element which performs an information or data transformation. An external processor (EP) is a processing element which does not communicate with other processors in the system over the peculiar interfacing connections referred to as control arcs which constitute a characteristic of my invention and is, therefore, "external" to the control system defined by control arc connections. An external processor may be connected to either a CP or a DP, but is connected by lines and circuitry in accordance with prior art for communication with the other processing elements rather than by means of lines and circuitry within the control arc definition. The solid lines in FIG. 1 represent control arc communication lines over which control flows from a control processor to another processing element, with the arrowheads indicating direction of control flow. Each control arc communication line interconnects control logic circuitry in two processors (CP's or one CP and one DP) and with that circuitry is, for convenience of description, referred to as a control arc. When a CP and a DP are connected, the arrow which indicates direction of control flow always points to the DP as control flows from CP's to DP's. In the case of two CP's having control arc connection, the arrow shows the control flow for each control arc and the particular combination of two CP's may have two control arcs--one for each direction of control flow. The dashed lines indicate information flow over conventional (prior art) communication links between control or data processors on one hand and external processors on the other, with the arrowheads indicating direction of information flow. In accordance with the graph architecture concept of the present invention for structuring an information processing system which at the time of my invention was heterodoxial, no single processing element is given overall control of the network as is done in prior art hierarchical systems using distributed processing as noted above with respect to the prior art. Rather, several control processors assume only temporary control over other processing elements in the network and over each other when required to effect performance of a specific operation. Control of processing elements in the network may alternate among various control processors, and several control processors may exercise controls over other processing elements simultaneously. A data processor may be located at any point in the defining graph of the network without modification. An external processor may be connection to any control processor or data processor which is uniquely designed to interface with the particular external processor. This system is not hierarchical or is nonhierarchical in the sense that there is no established unchanging control hierarchy among the processing units as exists in the prior art systems referred to. This is true even though there can be a certain amount of established unchanging hierarchy of control by CP's over certain DP's in branches of the graph. Similarly, this system is heterodoxial in that previous systems regarded an unchanging hierarchy of control as orthodox.

A typical control processor designated control processor i (CP.sub.i) is illustrated in FIG. 2. The primary functions of a control processor is that of issuing instructions (commands to initiate operations) to other processing elements. The control processor may receive instructions from several other control processors designated CP.sub.1, CP.sub.2, . . . , CP.sub.n and as a result of an instruction input may issue instructions to one or more processing elements of either type, control processor or data processor, and as denoted PE.sub.1, PE.sub.2, . . . , PE.sub.m. In FIG. 2, the lines with arrows represent the communication of signals, designated as, for example, CP.sub.1 -RQ-CP.sub.i according to the nature of the signal. The double lines indicate a multiple line or wire signal as opposed to the single wire (or line) signals represented by the single lines. Specifically in the convention commonly used in mathematics where CP.sub.i and CP.sub.j represent any two CP's in a system having n CP's, issuance of one instruction input to a selected CP.sub.i from another selected control processor CP.sub.j which is also one of the control processors CP.sub.1, CP.sub.2, . . . , CP.sub.n of the system includes the following set (sequence) of signals:

This is a single wire signal, the purpose of which is to notify CP.sub.i that CP.sub.j requests CP.sub.i to execute an instruction.

This is a single wire signal indicating to CP.sub.j that CP.sub.i has accepted the instruction from CP.sub.j and is currently active executing the instruction.

This is a single wire signal indicating the current condition or status of CP.sub.i and monitored by CP.sub.j to determine its course of action as a function of CP.sub.i operations.

This is a multiple line signal containing the instruction given CP.sub.i by CP.sub.j. The same lines utilized to transmit instructions are also utilized to transmit data.

The above-described set of signals taken together is referred to as a control arc input from CP.sub.j to CP.sub.i. The "direction" of the control arc input is in the control sense even though a control arc input includes a two-way communication (or conversation) including responses (receipts, busy signals, etc.). As a general rule, the "direction" of the control arc input is determined by the direction of the "instruction" communication or signal. A control processor may receive any number of control arc inputs or no control arc inputs. In a similar manner, a control processor may generate a plurality of control arc outputs to other processing elements, but by definition must have at least one control arc output. The set of signals included in a control arc output are the same as those in a control arc input and for CP.sub.i are designated:

wherein PE.sub.k designates a processing element numbered k, which is any selected one of the set of processing elements PE.sub.1, PE.sub.2, . . . , PE.sub.m which is a system having m processing elements. As in the case of control arc inputs, control arc outputs involve both conversations and single and multiple line or wire signals. Direction generally is that of the "instruction."

In addition to the required signal inputs, a control processor may also have the following signal inputs if needed for a particular design:

This is a periodic signal used by the control processor to sequentially perform its operations. A particular control processor may generate its own CLOCK signal internally.

A control processor may receive one or more DATA signals from other processing elements. The time of reading of these signals is determined by the control processor.

These are signals utilized to communicate directly with external processors.

These are multiple-line signals which allow readout of the register and memory values within a processor for maintenance or performance evaluation purposes.

Allows the readout of maintenance data selected by the maintenance address.

This signal causes each PE to stop after executing each instruction so that maintenance data may be read out between successive instruction executions.

A typical data processor designated data processor j (DP.sub.j) is illustrated in FIG. 3. The data processor inputs and outputs are the same as those of a control processor with the following exceptions:

1. A data processor does not generate a control arc output.

2. A data processor generates a multiline signal called DATA which is nominally a meaningful result of an operation performed by the data processor as directed by instructions given it by a control processor and using DATA provided by other data processors.

In general a graph architecture network according to my invention operates as follows. In response to an external signal, a control processor initiates the execution of a sequence of operations including the issuance of instructions to other processing elements. Each instruction issuance is typified by the following steps:

1. The originating control processor places the instruction information (CP-INST-PE) on its output lines.

2. The originating control processor places a signal on the request line (CP-RQ-PE) to the destination processing element which the control processor wants to perform the operations specified by the instruction information.

3. If the destination processing element is currently active performing a prior instruction, the control processor keeps the request signal on the line.

4. When a processor active aignal (PE-ACT-CP) is raised by the destination processing element, the originating control processor may assume that the instruction has been taken and drops the request signal.

The following paragraphs describe details of the preferred manner of interconnection of a plurality of processor elements in accordance with the graph architecture concept. In addition, this preferred manner of interconnection is described in the context of the prior art and the preferred manner of interconnection in prior art architecture concepts.

FIG. 5B illustrates the typical interconnection of prior art processors in what is commonly referred to as "general purpose computer" or alternately referred to as a one-processor or uni-processor system. Shown are four circles using the notation (DP, EP) discussed previously to illustrate features of existing general purpose computers. Illustrated in a single uni-processor DP 5V01 (as made and sold by many manufacturers as, for example, a PDP 1103 computer by Digital Equipment Corporation, Maynard, Mass.) which has a capability of communicating by use of nonstandard interface schemes with different kinds of external processing elements, e.g., tape drives, disk file devices, card reader devices, display devices and other devices necessary to allow a system to perform its intended purpose. The prior art system illustrated in FIG. 5V is an example of the minimal information processing system. That is a single data processor which can communicate with a plurality of processors and does communicate with at least one external processor, where said external processor is necessary to allow the practical use of the information processing capability of the data processor based on external information from a human operator or other parts of a realistic system.

FIG. 5W illustrates another prior art information processing system built in accordance with the "direct function processor" concept referenced in U.S. Pat. No. 3,631,401, Dec. 28, 1971, "Direct Function Processor," to Saul B. Dinman. FIG. 5W is a plurality of processing elements interconnected in accordance with the concept of the Dinman invention into a processing system consisting of one processing element which performs functions similar to a control processor in my invention and which has communication links to a plurality of data processing elements which in Dinman are referred to as "direct function processors" where in turn those processing elements may have further communication ties to external processing equipments such as the standard line printers, card input readers, etc., referred to previously. Since in the architecture approach of Dinman, the communication ties between the processing elements which perform the control processing function and those processing elements which perform the data processing function are not over lines which meet control arc definition described in and constituting a characteristic of my invention, the communication lines are illustrated in FIG. 5W by the dashed lines. In summary, the Dinman invention, as noted above in the discussion of the prior art, refers to the implementation of a distributed processing information processing system in which there are two levels of control: (1) a main control which is similar to the uni-processor control as illustrated in FIG. 5V, and (2) a second level of control consisting of one or more processing elements for performing specific functions in the information processing system.

A further prior art evolution of the distributed processing architectural art is that described in U.S. Pat. No. 3,962,685, "Data Processing System Having Pyramidal Hierarchy Control Fow, "Albert P. Belle Isle, as described above in the analysis of the prior art. An illustrative machine built in accordance with the Belle Isle concept as depicted in FIG. 5X shows a machine having a plurality of processors in several levels arranged in a pyramidal or tree-structured manner wherein there is one processor 5X01 at the top of the pyramid. Processor 5X01 as the main processor is designated CP.sub.1 (control processor) and has responsibility for directing the activities in its subprocessors wuch as CP.sub.2 5X02 and CP.sub.3 5X03 which in turn may direct the activities of subordinate processors such as CP.sub.4 5X04 and data processor DP.sub.11 5X13.

In this scheme of Belle Isle, as in other prior art arrangements, there are communication ties between processors, but the communication ties are orthodox hierarchical ties which do not purport to meet the novel control arc interconnection described and claimed in this application. In summary, an information processing system of the pyramidal hierarchical control flow concept may have multiple levels of control, having at least three levels according to Belle Isle, and must have a top-most level processor as the overall controlling element and the only processing element in the system which may have the state defined control concept used in the control processors of my invention. In addition, the ends of the tentacle-like depending processors of Belle Isle forming the base of the pyramid remote from the top-most processor must be data processors or external processors but never control processors.

In contrast to these prior art information processing system architecture concepts, FIG. 5Y illustrates a minimal information processing according to my novel graph architecture concept. FIG. 5Y shows a system consisting of four processing elements, of which one, 5Y03, is an external processor EP.sub.3 which as in the other systems illustrated conforms to a principal requirement of any information processing system, a combination of two interconnected control processors, CP.sub.1 5Y01 and CP.sub.2 5Y02, and a data processor DP.sub.4 5Y04. One principal difference between this graph implemented information processing system and each of those described previously is that as illustrated in FIG. 5Y, "control loops" may exist in the interconnection of processing elements. For example, CP.sub.1 5Y01 has a control arc output to CP.sub.2 5Y02 and, in addition, control processor CP.sub.2 5Y02 has a control arc output to CP.sub.1 5Y01. In this interconnection, the control processors CP.sub.1 and CP.sub.2 are said to be in a control loop or cycle. Also, in the graph architecture concept, each of the processors may utilize the state defined control concept and in the general case at least two of the processors must have state defined control. In this manner, neither control processor CP.sub.1 nor control processor CP.sub.2 is required to be the principal control processor in the system at all times. That is, at one time, control processor CP.sub.1 may be the principal control activator in the system whereas at other times, as a function of the state defined control, control processor CP.sub.2 may be the principal control processor and data processor DP.sub.4 is utilized for performing the actual information transformations required to result in a useful and meaningful transformation of data for computations. For semantic purposes and to distinguish my system from the prior art, I use and define the term non-hierarchical as meaning a system that does not have an established structural hierarchy of processors as do Dinman and Belle Isle.

As a way of determine whether a given information processing system is of the type found in prior art or in a machine in accordance with my graph architecture concept, the number of processing elements in the system may be compared to the number of control arcs defined in this sense solely as the number of interconnections useable for control purposes among processing elements. In a graph architecture machine having a number N of processing elements of type CP or DP (excluding EP's), the number of control arcs interconnecting said processing elements is N or more. By contrast, in an information processing system along the lines of Dinman or Belle Isle, the number of interconnections among N processors of type CP or DP is N-1. This is illustrated by FIG. 5X wherein there are N=13 processing elements of type CP or DP with 12 or N-1 interconnections; by FIG. 1 wherein there are N-20 CP's plus DP's interconnected by 24 or N+4 control arcs. In the minimal system of FIG. 5Y, there are N=3 CP's and DP's and 3 or N interconnecting control arcs. The Dinman system of FIG. 5W has N=4 CP's plus DP's and 3 or N-1 interconnections.

FIG. 5Z illustrates an arbitrary hypothetical interconnection of a plurality of processing elements into a system in accordance with the concept of my graph architecture. The FIGURE shows the various ways in which processing elements can be interconnected including:

1. A control processor to control processor loop as illustrated by the two control arc lines connecting CP.sub.1 to control processor CP2.

2. There may be more than two control processors in a loop as illustrated by the loop formed by control arc lines running from CP.sub.1 to CP.sub.5 to CP.sub.2 which in turn has connection back to CP.sub.1.

3. In the general case, an information processing system built in accordance with the graph architecture concept may have control loops amongst a set of control processors in which there may be two processors in that loop or three processors in that loop or a multiplicity of processors in that loop.

4. In addition, as illustrated in FIG. 5Z, there may be more than one control arc loop in the information processing system network as described in 1 and 2 above.

5. In addition, an information processing system built in accordance with the graph architecture principle may have multiple control arc inputs to individual processing elements and those multiple control arc inputs may be generated into processing elements either of type control processor, e.g., CP.sub.2, or of type data processor, e.g., DP.sub.13.

6. Also illustrated in FIG. 5Z is the fact that a control processor may not have a control arc input as illustrated in the case of CP.sub.14 in which case the control input originates as a result of an input from external processor EP.sub.13 and as a result, CP.sub.14 generates a control for controlling the activities of CP.sub.1.

7. In addition, an information processing system built in accordance with the concept of the graph architecture principle may include, as subparts, tree-structured networks as illustrated in the connection of CP.sub.3 to data processor DP.sub.10 and also data processor DP.sub.12.

8. One aspect of my concept of my graph architecture is the denial of a requirement for any one single control processor to be the principal control agent of the network for all time. In the network illustrated in FIG. 5Z, any of the control processors CP.sub.1, CP.sub.5 or CP.sub.2 may be the principal control processor at a particular time. The passing of the principal control function from one processor to another processor is made possible by facts that (1) there is a cycle otherwise called a loop in the control arc network and (2) there are more than one processing element in the system that have state defined control.

These eight features of the graph architecture information processing system concept may now be related to the interconnection network of the training system noted in the foregoing "Summary of Invention" as constituting the reduction to practice of my invention as illustrated in FIGS. 4A and 4B. As shown, the training system exhibits the principle of having control arc loops as illustrated by the cyclic connection of the OIU processor to the METAPROCESSOR to the FORM processor. In addition, the training system exhibits the principle of having two or more processing elements having state defined control in that the METAPROCESSOR and the FORM processor each have state defined control ability. As a result of the combination of these two facts, no single processor in the system need be the principal control processor at all times. Thus, at certain times and as actually occurs in operation of my training system, the METAPROCESSOR is the principal control agent for program execution. At other times, the FORM processor is the principal control agent which issues instructions through the OIU to the METAPROCESSOR, for example, to load the definition of a particular high level language in the METAPROCESSOR, or to load a specific user level lesson program in the program memory processor, or to distribute data to the INPT processor for definition of the hit points associated with the student pen entries. In addition, as illustrated in FIG. 4A, the training system built in accordance with the graph information system processing concept uses multiple control arc input to more than one processing element. For example, the OIU processor receives control arc inputs from the GRAF, KYBD, INPT, and FORM processors. In addition, the FORM processor receives control arc inputs from both the META and OIU processing elements.

FIG. 4A, as noted previously, is an illustration of an information processing system built in accordance with the graph architecture concept discussed above. This system is useable for a wide range of processing tasks but in the implementation used for reduction to practice and testing of my invention is particularly suitable for use as a training device and it will hereinafter be referred to as a training system and discussed with this particular application in mind.

The training system is illustrated in more detail in block diagram form in FIG. 4B. That portion of FIG. 4B enclosed within the large dashed line box corresponds to the network of processing elements interconnected by the control arcs in FIG. 4A. Each block within the dashed line box corresponds to one of the processing elements in FIG. 4A--and also the system generally corresponds to the network of control processors (CP's) and data processors (DP's) of FIG. 1 (except for a rearrangement in the Display Processor). The solid lines interconnecting the blocks are data lines with arrowheads indicating direction of information flow. Each of various types of broken lines interconnecting the blocks represents a control arc corresponding to one of the control arcs (solid lines with arrow) illustrated in FIG. 4A. All system elements external to the control arc network (i.e., external processors, EP's) are located outside the dashed line box and arrowheads on lines of interconnecting these elements with processing elements within the network indicate direction of information flow.

The purpose of the training system constituting the reduction to practice and the basis for explanation of the invention is to provide an automatic training device which has the capability of communicating with a trainee and evaluating the trainee's response to sensuous presentations provided by the system in accordance with a preprogrammed lesson plan or program. The training system also has the capability of communicating with an instructor and cooperating with the instructor in preparation of lesson plans. Additionally, the training system has the capability of communicating with other information processing systems thus allowing the training system to be integrated into a central general purpose computer controlled training complex, if desired.

To facilitate the above-mentioned communication between the system network and the trainee, the following external processing elements (exemplary vendor types are given in Appendix A) are provided in the particular model of system used in the example.

1. Switch Panel--This panel includes switches utilized to select one of three modes of system operation, i.e., bootstrap, normal lesson run and maintenance.

2. Keyboard--A standard ASCII (American Standard Code for Information Interchange) keyboard having the capability of generating 128 separate codes is provided. Ninety-six of these codes represent characters and thirty-two represent control functions.

3. Graph-Pen Electronics--The graph-pen electronics locates a hit point of a sonic pen touched to a surface in a grid area bounded by two microphones positioned to form an L or the adjacent sides of a rectangle. The times required for an ultrasonic sound generated by the pen to travel from the hit point to the two microphones defines X and Y coordinates of the hit point. These times are measured by the graph-pen electronics and signals designated X-on and Y-on are produced for time periods representative of the X and Y coordinates of the hit point.

4. Plasma Panel--A flat matrix plasma panel is utilized as the primary display device of the training system. Complex graphics, pictorial representations and characters may be displayed by illuminating patterns of dots within the matrix of the panel. The plasma panel is located within the grid defined by the microphones of the graph-pen device and an operator may indicate selected areas on the panel by utilizing the pen to cause generation of X and Y coordinate signals. Thus, a device enabling two-way communication between operator and training system has been established. For example, a dot-formed image of a hand-held calculator can be displayed on the panel and the operator will actually have the ability to operate the calculator by touching the pen to the displayed calculator keys indicating what operations he desires the calculator to perform. This information will be communicated to the network of processors in the training system which will actually perform the desired calculations and cause the calculated answers to appear in the numeric display portion of the image of the hand-held calculator.

5. l Slide Projector--A slide projector is provided to enable rear projection of images on the plasma panel for more realistic pictorial representations than are possible by use of the plasma panel display alone. For example, a pictorial representation of a hand-held calculator might be projected onto the panel with only the numeric display being presented in dot form. A projector having a multiple slide cartridge is utilized in conjunction with a stepping motor and a digital counter to enable selection of any one of a plurality of slides by the network.

6. TV--A three beam cathode-ray-tube device is provided to enable multi-color presentations.

7. Line Printer--A device is utilized to provide a record of operations performed by the training system and/or the operator. This printer forms characters on a paper surface by spraying a beam of ionized ink spurts in a continually changing direction required to write the character. The direction of the beam is controlled by X and Y deflection grids. The required deflections are controlled by electronics within the line printer and information defining characters to be printed is transmitted to the control electronics in the form of a 7-bit data code and a request signal.

8. Mass Storage--A magnetic disc system is utilized to provide storage of lesson plans. In this particular system, a floppy disc device utilizing flexible diskettes for the storage medium is utilized.

Before describing the functions of the processing elements enclosed within the large dashed line box, it is advantageous to note some terms that will be used similar to their uses elsewhere in the art to describe the network:

1. String--An ordered sequence of characters which may represent a statement in a programming language, computation sequence, or data element to be processed.

2. Metalanguage--A language used to describe a programming language.

3. Grammar--The set of rules for the high level language defined by metalanguage notation.

4. Language Level--The degree of complexity of operations described by a single communication in a language.

5. Instruction--A data word defining a specific operation or sequence of operations to be performed.

6. Data--Any information other than operations commanded by control processors.

7. Delimiter--A character indicating the beginning or end of a string or group of strings.

The network has been designed to take advantage of its metamorphic control scheme wherein control processing elements have the ability of issuing commands to each other directly in a high level language beginning at different points in the structure so that no permanent hierarchy is established by the structure. As noted above, this is denoted by a non-hierarchical structure. The various broken lines representing control arcs in FIG. 4B are formed from symbols representing the various language levels used for communicating between processing elements. These levels are defined in Table I. Note that the processing elements often have the capability of communicating at more than one language level and this capability is evidenced by the use of more than one type of symbol to form the broken lines representing a specific control arc connecting two processing elements.

The system network for the example training system includes the following processing elements:

Keyboard Processor (KYBD)--This control processor conveys keyboard generated codes to other processing elements and initiates a mode of operation selected by the operation actuation of one of the switches on the switch panel.

Graph-Pen Processor (GRAF)--This control processor retrieves information from internal hit-point memory locations corresponding to plasma panel hit point locations and transmits this information over control arc means to other processing elements.

Inputs Processor (INPT)--This control processor performs input pre-processing operations prior to generating a RUN command, and initiates operations for system initialization.

Operator Inputs Unit (OIU)--This control processor generates instructions for INPT or META based upon inputs from KYBD, INPT and GRAF.

Program Memory Processor (PMEM)--This data processor provides random access memory or RAM storage for that portion of a lesson plan currently in use. This processor also scans the stored information for delimiters and performs program addressing functions.

Meta-Processor (META)--This novel control processor stores the grammar of the programming language used with the system and performs the basic translation of program interpretation level information received from other processing elements.

Semantics Processor (SEM)--This control processor generates sequences of instructions commanding NUM and STG to perform complex numeric and character string computations, respectively.

Numerics Processor (NUM)--This data processor performs numeric operations, logical operations and code conversion.

String Processor (STG)--This novel data processor performs complex string operations under the direction of the semantics processor.

Format Processor (FORM)--This control processor controls the distribution of large blocks of information between the processing elements.

Mass Storage Processor (MS)--This control processor generates sequences of instruction for controlling the floppy disk device.

Floppy Disk Processor (FD)--This data processor directs the floppy disk mass storage unit to store and to read information.

Working File Buffer Processor (WFB)--This data processor provides temporary information storage when the training system is used to prepare lesson plans.

Display Processor (DSPL)--This control processor interprets information provided by other processing elements and directs the activities of PLAS, PROJ, CRT, PRNT, and SYM.

Symbols Processor (SYM)--This data processor stores information needed to construct graphic and pictorial displays on the plasma panel and the TV.

Projection Processor (PROJ)--This external processor interfaces between DSPL and the slide projector.

Display Interface Unit (DIU)--This novel data processor interprets character codes and generates the proper dot patterns for a plasma display device (PLAS) or a cathode ray tube device (CRT) or both.

Print Processor (PRNT)--This external processor interfaces between DSPL and the line printer.

Data Link Processor (DL)--This data processor provides an information distribution path between processing elements connected to FORM and other processing elements in the network. DL also provides temporary storage for information passing between the network and the mass storage equipment.

Before giving a detailed description of the processing elements, a typical operation of the system as built will be described including operations performed by the individual system elements and information flow between these elements.

The most common usage of the system will be that of communicating with a trainee where display information will be presented to the trainee on the plasma panel, and the trainee will respond to information presented by touching one or more hit points on the plasma panel with the sonic pen. The system reacts to the trainee's response by performing an operation consistent with the particular hit point(s) touched, as discussed with respect to the hit point memory in explanation of the INPT processor. Examples of system reactions include comparing the response of the trainee to a specific response required by the lesson plan, performing operations specified by the trainee and calling up sub-routines or new lesson plans requested by the trainee.

To initiate operation, the trainee actuates the bootstrap switch causing a bootstrap signal to be transmitted to the OIU. OIU transmits a code sequence level instruction to INPT which then initiates the sequence of operations defined for this instruction. These operations include issuing instructions to KYBD, GRAF and META commanding these processors to assume predetermined initial states. INPT will then transmit a code sequence level instruction through META to FORM. In compliance with this instruction, FORM issues instructions to MS and to META (through OIU) causing the first block of information in the mass storage to be transferred through MS, DL and OIU to a meta-memory located in META. On completion of the transfer of this block of information, FORM transmits a code execution level RUN instruction through OIU to META.

META next begins execution of the block of instructions in its meta-memory. Normally, one of these instructions causes META to command FORM to load the second block of information stored in mass storage into PMEM. This second block of information is transferred from mass storage to PMEM under the direction of FORM. Upon completion of this transfer, FORM again issues a RUN instruction through OIU to META.

META now begins interpreting the information in PMEM. Typically, this second block of information located in PMEM will include program statements causing META to command FORM to load other memories in the system with blocks of information in mass storage. Upon completion of loading these memories, META normally issues a command to DSPL causing information to be displayed on the plasma panel. The trainee's response to this information by touching the sonic pen to a particular section of the image on the plasma display will be interpreted by META and control of the system will shift from one control processor to another as dictated by subsequent responses of the trainee to display images.

A detailed example is now given illustrating the several levels of language in the exemplary graph architecture machine including those parts of programming performed by a person who is generating the lesson programs for the system, the functions performed by the trainee to operate that lesson program, and in addition the discrete functions performed in the system in response to the inputs of the trainee. As an example, a program called the multiple choice question program or MCP for short will be used throughput the specification to illustrate the various features of the processors and the interconnection of processors in the graph architecture training system machine used as an example. In this respect, examples of the design at all levels for the MCP program are given. On the one extreme in the example, the trainee performs operations using the keyboard and the pen selection device in response to displays given him on the display device in the system. In the other extreme, the system must take the inputs given it by the trainee and execute a sequence of micro-level operations, i.e., individual register loads, memory write and flip-flop set and reset functions. Between these two extremes, the different levels of language implementation allow a straightforward manner for interpreting the student's desires and generating new display information for the student as a function of those desires.

FIG. 4C illustrates one implementation of an operating panel which is the visual part of the system seen by the operator or trainee of the exemplary training system. Shown here is the operating panel 4CO1 which contains a display device 4CO2 which is shown to the student and to the side of the display device a predefined hit point selection area 4CO3. In addition is shown the hit point selection device or sonic pen 4CO4 and the alternate keyboard input device 4CO6. During execution of the lesson program, statements in the language of the system when programmed properly by the user of the system allows the generation of various display sentences and graphics as illustrated in FIG. 4C as 4CO5. The illustration shows a multiple choice question consisting of the stem part which reads "the symbol" followed by a typical symbol which is being used to query the student and it is asked if that symbol "is given which of the following names." There follows two alternatives from which the student must choose. Alternative "A" is selected by the student if the student believes that the symbol shown is a "NAND" symbol. Alternative "B" is selected if the student believes that the symbol shown is a "process" symbol. The student may reply to the question by one of two means. The student may use the pointer selection device 4CO4 to touch the point or line representing alternative "A" or alternative " B". Alternately, the student may select to choose one of the standard control options for the student entry such as the "NEXT" control or "BACK" control in the off-screen hit area 4CO3. Alternately, the student may choose to make any of these entries by way of the keyboard 4CO6. The operation of the program in either case is the same.

The MCP program in this example is expected to allow the question display information to be shown on the display device 4CO2 and then halt its operation and wait for input from the trainee. In response to input from the student, the program causes the system either (1) to display additional information such as the fact the student answered the question correctly or incorrectly or, in response to, for example, a "BACK" input from the student which requires backing up in the lesson program or in the case of the "NEXT" input from the student, (2) to back up or go forward to another part of the lesson program. In the present case, the correct answer to the question is line B, i.e., the symbol is a PROCESS symbol. If the student selects this alternative, then the program will display the message CORRECT and then halt again allowing the student to make a second entry. At this second entry point, the student selects the NEXT entry and the next question in the sequence will be displayed to the student. In this manner, not only can several questions be illustrated to the student, but information of background nature may be displayed to the student explaining what the difference in symbols is or another suitable subject material which can be programmed using the capabilities of the system can be displayed. In particular, this training system has specific utility in the simulation of operation panels such as computer maintenance panels and allows a student to self-test his understanding of the operation sequences for using such a panel. With this equipment, a plurality of different training situations can be presented to a student so that he might learn many different subject materials using this same training device.

The programmer of this system must generate a program for executing the above sequence of operations for the student using the high level language of this system which I have designated the string problem oriented machine language or SPOML.

In FIG. 4D is illustrated a sample portion of a lesson program written in the SPOML language to show a sequence of statements in this high level language, the purpose of which when executed in the system is to generate display information for the sample question, to allow the inputs from the student and to permit subsequent processing of the inputs from the student. A summary definition of the SPOML language is given in Appendix C. The meaning of the various statements used in the execution of the MCP program as set out in FIG. 4D will now be described. On line 4D01 is illustrated a left bracket character which executed by the system means "beginning a new control point." The meaning of a control point is that conditional operations within the language must flow from one control point to another or back to a previous control point. The use of a control point at the beginning of a question allows the question to be repeated later or bypassed by choice of the student. On line 4D02 is illustrated the sensitized hit point type statement. In this case, the parameters following the "s" which stands for sensitize statement are the "nul" characters from the ASCII (American Standard Code for Information Interchange) character set. These are written by the word "nul" surrounded by the periods. This allows the differentiation between the single data words which has name "nul" from a sequence of word characters. The ".s.nul..nul." statement desensitizes all the current hit points on the screen. Line 4D03 starts the display message to be displayed. The initiation of the display operation is by way of the "d" character which means "start display statement sequence." The "0" character after the "d" is used by the DCU processor to determine in what state to start. The "0" state means "display with normal cursor controls the following information." The display sequence now contains a string of characters surrounded by the quote characters. This has the meaning "display all the information within the quotes" so that, for example, the "dle" control item is used to clear the display. This is then followed by displaying the message "THE SYMBOL." This is followed by a carriage return of the cursor ":.cr." and a tab function of the cursor ".tab." and this is followed by the displaying of the symbol referenced by name "I". This is followed then by a second carriage return, followed by the message "IS GIVEN WHICH OF THE FOLLOWING NAMES." The operation of the display functions is described in detail in the display processing subsystem of the specification. On line 4D07 is illustrated a second sensitize statement which in this case will sensitize the area then under the cursor of the display to be of name "A" and of size ten characters by two characters. At this point on the screen, by way of the display statement on line 4D08, is now written the message "A.NAND." This is now followed by a carriage return at which time a third sensitize statement is used to sensitize an area called "B" on the screen. At this point on the screen the message "B.NOR" is written. In this manner, if a student uses the hit point selection device and points to a point inside the area defined as A or points to a point inside the area defined as B, the system will accept that input as the character A or B. Alternately, the student may enter the characters A or B on the keyboard with the same effect. The program now starts a new control point having not forgotten the previous control point on line 4D01 and starts this new control point at line 4D11. The program now at line 4D12 performs the halt operation statement which is represented in the high level language by the period character. The halt operation allows the system to stop and await an input from the student. Upon an input from the student, the execution of the program is now continued. The statement sequence on line 4D13 allows the checking of the student's input to see if it corresponds to the BACK operation. If the student has selected the BACK operation, then the sequence of the three colons followed by "r" allows the repetition of a control point before that defined at point 4D01, e.g., the backing up to a previous question in the lesson program sequence. Alternately, if the student's input is not a BACK function, then on line 4D14 a numeric variable called "Q" is incremented. This "Q" variable may be used to keep track of how many times a student has answered a question. At line 4D15 a test is made to see if the student entered the "A" alternative for the question. In this case, the message "INCORRECT" is displayed and the operation is exited by the colon followed by the "e" statement in such a manner that the operation will now continue at line 4D18. Alternately, if the student entered the "B" alternative, then the message "CORRECT" would be displayed and a second numeric variable would be incremented which in this case might be used to denote the number of correct responses made by the student. Again, in this case, the continued operation of the program by way of the colon followed by the "e" statement causes execution to be continued at line 4D18. If the student entered none of the BACK, A or B inputs, then the message "INVALID ENTRY" is given and the control halt at point 4D12 is executed. This requires the student to reanswer the question for he may not have selected a point within a hit point area or he may have attempted to make an entry which is not allowed by the program at this time. The student would then respond again until he has gotten the correct answer or incorrect answer or entered a BACK operation. At line 4D18, the program again halts and requires a student entry. In this example, if the student enters BACK, the question starting at line 4D01 is again repeated so that, for example, if the student answered a question incorrectly he might be given another opportunity to answer that question. Alternately, the lesson program would now continue with its next part which is not shown, but which might be another question or a sequence of descriptive material or a sequence of exercises for execution by the student, all of which are programmed in this high level language in a manner similar to what has been described.

The interpretation of SPOML program such as that illustrated in FIG. 4D is carried out principally by the METAPROCESSOR. As a function of interpreting the character string output of the program memory in which the program is stored, the METAPROCESSOR will direct the activities of other processors in the system and for this purpose function as the principal control processor.

FIG. 4E now illustrates the next level of complexity in the system which is the program interpretation level. FIG. 4E shows the detailed coding of the METAPROCESSOR state sequences for interpreting a program. The META sequences consist of a plurality of sequence parts, each part of which is used for interpreting different statements in the SPOML language. The common return point for all parts of interpreting a program is the state called PROG on line 4E01 in FIG. 4E. The PROG point allows the reception from the program memory of the next sequence of character(s) in the program and determines which of a plurality of different statement types are to be executed. Lines 4E06 through 4E13 illustrate a portion of the state transition table which is used to determine which parts in the META sequences are to be executed for each statement type. For example, in line 4E07 is illustrated the period state which allows the jumping to the halt sequence part of the META sequences to perform those functions required for the halt statement. In a similar manner, on line 4E10 is illustrated the "d" state which allows access to that sequence in the METAPROCESSOR for executing the display sequence statement part. A detailed explanation of the operation of the METAPROCESSOR in carrying out this interpretation process using the instruction illustrated in FIG. 4E is given in the detailed description of the METAPROCESSOR.

The next level of operation in this system is the execution of those instructions commanded from the METAPROCESSOR. For example, in the case of the alternative statement sequence illustrated in lines 4E39 through 4E51 in FIG. 4E there is the occurrence of the instruction ONECP at line 4E42. This is a command from the METAPROCESSOR to the SEM processor to execute the instruction called "ONECP." FIG. 4F illustrates the state transition table part and exemplary parts of the operation sequences within the SEM processor. For example, the "ONECP" instruction state allows access to the "ONECP" sequence at line 4F03. This sequence now executed within the SEM processor executes a series of instructions, some of which such as the microinstruction at line 4F03 are executed completely with the SEM processor, and other instructions of which such as the "SEULD" at line 4F04 is executed by the STG instruction processor. Differentiation upon which the processor determines whether the instruction is to be executed by the SEM itself or by yet another processor is made on the basis of the SELF OPCODE. In the case that the SELF OPCODE is a " PASS" or a "PASW" instruction for 4F04 or 4f05, then the OPERAND portion of the self instruction in a sequence is the OPCODE instruction to be executed by yet another processor.

The next level of execution of operation within this system is now at the instruction level. For example, the "SEULD" instruction required from the SEM processor at line 4F04 is executed by the STG processor.

FIG. 4G illustrates the micro-operations performed by the STG processor for each instruction input type. In this table is given in the columns the thirty-two possible instructions executed by the STG processor and horizontally the micro-operations within the STG processor which may be performed for each instruction. Then, for example, the "SEULD" instruction which has micro-code generator address 20 requires only the operation called LOAD-DIN within the STG. A detailed explanation of these operations is contained in the SEM/STG processor descriptions below.

Overall as can be seen from this example, the approach of taking a program in a high level language and breaking it down into further detailed parts can be seen to be very useful in allowing a programmer, by using the high level language and a very simple statement of desired actions, to develop a program which when executed by the system as used as an example is then expanded into a sequence of very detailed operations representing several times the number of operations originally defined by the programmer in the program. In this manner, the programming of this system is simplified and the amount of storage is simplified considerably. The system operation cost is greatly reduced as well as the cost of the design of this system which is greatly reduced.

In each of the control and data processors of a system built in accordance with graph architecture concept, there exists a collection of hardware components common to all processors except CP's not having an input control arc.

FIG. 5A illustrates the general structure of a typical processor. The processor includes the common hardware components, hereinafter termed common logic, and unique circuitry, the details of which are unique to the purpose of a specific processor for an intended specific application.

The purpose of the circuits of the common logic is as follows:

1. OPERATION INPUT REGISTER 501--holds the operation code, hereafter called OPCODE, portion of the instruction during the time that the instruction is being executed.

2. DATA INPUT REGISTER 502--holds the DATA portion of the input instruction during execution of a given instruction and supplies this data to the processing element unique circuitry 506 where it may be combined with other data or otherwise manipulated to obtain results data corresponding to the intended purpose of the processor.

3. MICRO-CODE GENERATOR 503--takes the OPCODE from the operation input register 501 and generates individual signals called enables to the other components of the processor commanding specific operations to be performed. For example, if a given instruction needs data register to be loaded the LOAD-ENABLE signal must be active for that instruction, whereas for another instruction which does not require that register to be loaded then that same LOAD-ENABLE signal must be inactive. The micro-code generator also supplies signals to control logic 504 to allow selection of conditions and determine the number of clock pulses which are to be generated.

4. CONTROL LOGIC 504--performs the overall control activities of the processor including receiving the request signal, generating the active signal, generating the condition signal and generating the timing pulses needed by the other components of the processor to perform the functions needed for a specific instruction. Upon receipt of a CP-RQ-PE signal, if the PE-ACT-CP signal is not currently enabled, the control logic causes a LOAD-INSTRUCTION signal to be generated which effects loading of the OPCODE and data portions of the instruction into the operation input and data input registers. The control logic then generates a series of timing pulses and commands, the number and type of which are defined for each different instruction by the micro-code generator 503. After the proper number of timing pulses have been generated or upon reception of a certain condition (the particular case being determined by the micro-code generator) then the control logic drops the PE-ACT-CP signal and may thereafter accept another instruction and repeat the above actions in a similar manner. At the appropriate time and by enable from the micro-code generator, the control logic may set or reset the PE-COND-CP signal and/or load a data output register 505 with data.

5. THE DATA OUTPUT REGISTER 505--may be loaded with data during the execution of an instruction. This data may then be used by other processors for their own operations. By convention this data may only be used when the processor is not active and it is the responsibility of the processors using the data to ensure this situation by monitoring the PE-ACT-CP and PE-COND-CP signals.

6. PROCESSING ELEMENT UNIQUE CIRCUITRY 506--includes those components such as registers, memory and arithmetic networks which are necessary to allow a specific processor to perform processor unique functions in the system. Later paragraphs describe exemplary processors detailing the various types of components and interconnections which make up the unique circuitry.

The ensuing paragraphs detail the composition of the various circuits which make up the common portion of a DP or CP.

The operation input register as shown in FIG. 5B comprises a set of flip-flop components, which are well known devices in the art or alternately a collection of integrated circuits containing flip-flops, also well known in the art. Each flip-flop holds the value of a single bit of the input OPCODE. The OPCODE value is caused to be stored upon the occurrence of the LOAD-INSTRUCTION pulse which is generated by the control logic and the data so stored is kept until a subsequent LOAD-INSTRUCTION pulse is received. The data input register 502, data output register 505 and other registers in the system have an identical construction with differing signal names.

The micro-code generator circuit as illustrated in FIG. 5C comprises one or more read only memory devices, such devices being well known in the art. The input address of these read only memories in the OPCODE of a given instruction. For a particular processor, the contents of the read only memory are permanently defined in such a manner that the outputs of the memories, called micro-codes or enables, uniquely define a set of primitive operations (such as memory write, multiplexer address, etc.) which are to be accomplished for each instruction.

In the general case, the control logic as shown in FIG. 5D includes flip-flops, logic gates, multiplexers, counters and decoders, all such devices being well known in the art. The operation of the control logic in receiving and generating various signals is as follows:

Upon the receipt of the CP-RQ-PE signal and if an ACTIVE flip-flop 511 is reset, meaning that the processor is not currently active, then AND-gate 510 generates a signal to the J input of a J-K flip-flop 512 designated the ACCEPT FF. Upon receipt of a next CLOCK-PE pulse, which is part of a continuous train of clock pulses generated by another processor or generated within the subject processor, the ACCEPT FF 512 is set. Upon the reception of the next CLOCK-PE pulse, the LOAD-INSTRUCTION signal is generated from AND-gate 513 and the ACTIVE FF is set. Now the ACTIVE FF transmits the PE-ACTIVE-CP signal and the AND-gate 510 is disabled, thus preventing reception of further instructions. Also, since the ACCEPT FF was set, the K input causes the ACCEPT FF to become reset, thus preventing the generation of further LOAD-INSTRUCTION pulses. If at any time, and particularly when power is first applied to a given machine, the RESET-PE signal is received, then both the ACCEPT FF and ACTIVE FF are reset establishing a state in which the processor may receive instructions. While the ACTIVE FF is set, AND-gate 514 generates a stream of pulses which allow operation of the other components of the processor. In particular, an instruction length counter 515, having been loaded with a number signifying the number of pulses to be generated, now is incremented by the pulses from gate 514 and as a result of each count a clock phase is generated from a decoder device 516. For a given instruction, the clock phases are used to order the sequence of various commands as, for example, the combination of a phase and an enable from the micro-code generator through AND-gate 517 causes a clock pulse to be issued effecting performance of some predetermined elementary operation.

One such clock phase may be gated through an END multiplexer switch 518 which then supplies the END signal to the K input of the ACTIVE FF resulting in that flip-flop being reset, thus causing the processor to become inactive and allowing subsequent requests to be honored. During execution of the instruction, one of a multiplicity of conditions may be monitored by a condition multiplexer 519, a selection address of which is supplied by the micro-code generator. The output of the condition multiplexer is recorded into a condition FF 520, the output of which constitutes the PE-COND-CP signal for use by the processor which originated the instruction.

As stated previously, all of the previous circuits are common to all processors. For this reason, a detailed description of the circuits is not repeated. Also, since the micro-code generator and control logic circuits generate signals to all other components in a given processor, and since this is generally a large number of lines to be shown on a diagram, such lines will be left off of subsequent diagrams for clarity, but it is to be understood that such lines do exist. The design of a specific PE need not include all of the components of the common logic. For example, (1) a CP not having an input control arc does not have the common logic, (2) a particular PE need not store both the DATA and OPCODE portions of the input instruction, (3) the ACCEPT flip-flop may not be used, (4) the same register may be used for data input and output, and (5) the micro-code enables may be taken directly from the OPCODE so that the micro-code generator is not necessary.

FIG. 5E illustrates a typical block diagram of the connection of a control processor 5E01 to a processing element 5E04 by way of a control arc 5E03. In this diagram is illustrated that the control arc itself physically consists of a circuit in the control processor element 5E01 which is called a control arc transmit logic 5E02 or CAT for short. In conjunction with this, the processing element receiving the control arc must have a control arc receive logic element 5E05 or CAR for short. In other words, a control arc consists of the combination of a control arc transmit logic in one processor and a control arc receive logic in another processor. Between these two logic blocks, the control arc signal set as described previously are connected. The processing element illustrated in FIG. 5E may be either of type data processor or of type control processor. If that processing element is of type control processor, then the processing element 5E04 will in addition have control arc transmit logic of its own for communicating to other processors in the network. The control processor 5E01 illustrated in FIG. 5E may also contain a control arc receive logic for receiving instructions from other processors. These extra elements are not shown.

As illustrated in FIG. 5F, a particular control processor 5F01 in an exemplary machine may require connection to several processing elements by way of output control arcs. In this case, the control processor may in the first case have multiple control arc transmittal logics or in the case illustrated have a multiple transmit expansion circuit 5F03 which is driven by a single control arc transmit logic element 5F02 in that control processor 5F01. This multiple transmit expansion circuit 5F03 has inputs both from the single control arc transmit logic 5F02 and a destination address which is used to select which of the processing elements PE1, PE2 and generally up to PEN the particular instruction is to flow over the control arc. In this diagram, these processing elements PE1, PE2 and so forth contain their own control arc receive logic to receive this instruction over the control arc signal set. In a similar manner, a particular processing element may be needed for use by several control processors.

This situation is illustrated in FIG. 5G. In this example, several control processors labeled CP1, CP2, etc., have control arc outputs to the single processing element which may receive these multiple control arc inputs in one of two ways. In the first way, this processing element may contain several control arc receive logics or alternately in the case illustrated, this processing element 5G07 may contain a multiple receive expansion circuit 5G08. These cases may be combined so that a particular processing element in an exemplary graph architecture machine may have multiple control arc inputs using a multiple receive expansion circuit in conjunction with a control arc receive logic and, in addition, multiple control arc outputs using a single control arc transmit logic and multiple transmit expansion circuit. The details of exemplary control arc transmit logic, control arc receive logic, and multiple expansion circuits are not described.

FIG. 5H illustrates an exemplary control arc receive logic circuit. This consists, as illustrated, of logic devices which have previously been described in the area of the control logic portion of the processing element, i.e., a control arc receive element may consist of two flip-flops, one called the ACCEPT flip-flop 5H03 and an ACTIVE flip-flop 5H04. In addition, the control arc logic may contain an OPCODE input register 5H06 and a data input register 5H07. The circuit, as described previously, works as follows: Upon the reception of a CP-RQ-PE signal, the ACCEPT flip-flop becomes set on the next clock signal, this allows the LOAD-INSTRUCTION signal to be generated which loads the CP OPCODE and CP-DATA portions of the input instructions from the control arc into the OPCODE INPUT REGISTER and DATA INPUT REGISTER 5H07. After the instruction is loaded, then the ACTIVE flip-flop 5H04 is set generating the PE-ACTIVE-CP signal back to the requesting control processor. This initially requesting control processor must now drop the CP-RQ-PE signal. The control processor may now on its own go about the generation of more instructions to flow over a control arc to this particular processing element or another processing element which is connected to that control processor.

FIG. 5J illustrates an exemplary design of a control arc transmit logic function. The control arc transmit logic function 5J06 consists of three flip-flops with supporting gate logic. Of these three flip-flops, the ENABLE-CAT flip-flop 5J02 is used to control the overall operation of the CAT logic. The ACTIVE-UP flip-flop 5J03 when set denotes the fact that the processor to which the instruction has been requested for execution has accepted that instruction and is now active. The ACTIVE-DOWN flip-flop on the other hand when set denotes that the instruction execution by the processor for which the request was generated has been completed. In this manner, the control processor can determine when to continue its own operation on the basis of either the acceptance of the instruction or on the basis of the instruction having been completed. The general operation of the CAT logic is as follows: Firstly, the control processor generates the RESET-CAT signal which clears the flip-flops to put them in the initial state. The control processor now generates the START-CAT pulse which sets the ENABLE-CAT flip-flop 5J02. Since now the ACTIVE-UP flip-flop which was reset on the occurrence of the RESET-CAT signal now enables gate 5J01 and thusly allows the generation of the signal CP-RQ-PE. In response to this signal, the processing element will at some point in future time generate the PE-ACTIVE-CP signal which now on the low to high transmission sets the ACTIVE-UP flip-flop 5J03. Since now the ACTIVE-UP flip-flop is set, the gate 5J01 is disabled, thus dropping the CP-RQ-PE signal. When the processing element to which the instruction was sent has completed the execution of that instruction, the PE-ACTIVE-CP signal goes low and on this transition the ACTIVE-DOWN flip-flop 5J04 is set. The control process in which the CAT logic is resident may choose on its own to continue operation either on the state that the ACTIVE-UP flip-flop is set or on the state that the ACTIVE-DOWN flip-flop is set. In the case that an instruction completion is not needed for the continued operation of the control processor, that control processor will generally proceed with its operations when the ACTIVE-UP flip-flop is set. On the other hand, if the instruction to be executed is such that data is needed back or where the condition is needed back to the control processor, then that control processor may elect to wait for continuation of its operations until the ACTIVE-DOWN flip-flop is set.

FIG. 5K illustrates an exemplary multiple transmit arc expansion circuit which is used in conjunction with a single control arc transmit logic element 5K01. The multiple transmit expansion circuit 5K02 consists of two elements: firstly, a destination decoder and secondly, an ACTIVE multiplexer 5K04. The destination decoder takes the destination address which is generated elsewhere within the control processor and generates an ACTIVE signal on one of the lines CP-RQ-PE1 or CP-RQ-PE2, etc., as a function of the address lines of the destination address. The signal outputs from the destination decoder are enabled to a high state only at the presence of the CP-RQ-PE signal which is generated by the control arc transmit logic 5K01. In response to the REQUEST signal, the processing element will at some time generate an ACTIVE signal. This may be PE1-ACTIVE-CP signal, PE2-ACTIVE-CP signal, etc., the one used in correspondence with the original request signal sent out. The destination address is also given to the active multiplexer 5K04 which allows selection of the appropriate active line which is then sent to the single control arc transmit logic 5K01 for use as described before. In this manner, a multiplicity of processing elements may be communicated to by a single control processor over multiple control arcs. The instruction content of the control arc sent out by the control processor consisting of the OPCODE and DATA PORTIONS is from a common source in the CP not illustrated in the diagram.

FIG. 5L illustrates an exemplary multiple receive circuit expansion. This circuit 5L01 works in conjunction with a single control arc receive logic block 5L02, the details of which have been described previously. The purpose of the multiple receive logic is to accept request signals from a multiplicity of control processors and encode these on a priority basis into a single control arc set of signals for use by the CAR logic 5L02. The multiple receive expansion circuit consists of the following elements: a request encode element 5L03 which has as inputs each of the request signals from the control processors in mention. From this set of request signals, the request encode circuit generates the addresss of the highest priority currently HI request signal and the signal CP-RQ-PE which is used to denote that at least one request signal from the lowest numbered control processor in the case that there are two or more request signals present at any given point in time. The source register 5L04 is loaded by the LOAD-INSTRUCTION pulse from the CAR logic 5L02 so that the number of the control processor requesting instruction execution may be saved. This is necessary since the control processor will drop the request signal as soon as the processing element is activated. In contrast, the active signal going back to that requesting control processor must remain steady for that control processor throughout the execution of the instruction. To generate this active signal back to the originating control processor, the active decoder circuit 5L04 is used. This takes the address which is now stored in the source register 5L04 and decodes it to one of a multiplicity of signals which constitute the processor active signal back to the control processor and this signal is present when the processor active signal is generated by the CAR logic 5L02. The multiple receive expansion circuit also includes the OPCODE-INPUT multiplexer 5L06 and the DATA-INPUT-MULTIPLEXER 5L07. The address of these multiplexers is also driven by the address generated by the request encode circuit 5L03. In this manner, the operation code and data portions of the instruction associated with request signal of the requesting control processor is switched onto the lines CP-OP and CP-DATA for use by the control receive logic 5L02 which then stores those quantities into the OPCODE register and INPUT-DATA register also on the occurrence of the LOAD INSTRUCTION pulse.

FIGS. 5M and 5N illustrate exemplary timing sequences for the operation of the combination of a control arc transmit logic and a control arc receive logic. This timing is the same whether there are multiple arcs involved or not. There are two cases to be described. In the first case, the request is given to the processing element during a time period in which that processing element is not currently active. In the second case, the processing element may be currently active executing an instruction when the request signal is received. The case of the processing element firstly being not active is described.

FIG. 5M illustrates the timing of the various pulses involved in the CAT-CAR logic for this case. Also shown is the CP-CLOCK signal which is the assumed pulse train used internal to the control processor and a separate pulse train PE-CLOCK signal which is used internal to the processing element. These pulse trains may be the actual same clock trains or dissimilar pulse trains as illustrated in the FIGURE, i.e., each processing element may contain its own clock generation circuitry and the overall instruction acceptance over the control arc will operate the same. The sequence of events for accepting instruction is as follows: Firstly, in the control processor the reset CAT signal is generated which resets the ENABLE-CAT, ACTIVE-UP and ACTIVE-DOWN flip-flops as illustrated in the diagram. The second event is the generation of the START-CAT pulse on the next clock pulse in this control processor. This sets the ENABLE-CAT flip-flop which allows the generation of the CP-RQ-PE signal. In the processing element receiver, the reception of the control processor request PE signal allows the setting of the ACCEPT flip-flop which in turn on the next clock pulse allows the generation of the load instruction pulse so that the instruction may be loaded into the OPCODE and DATA registers. On the trailing edge of this same clock pulse, the ACTIVE flip-flop is set. When received by the control processor, the ACTIVE-UP flip-flop is immediately set which in turn disables the CP-RQ-PE signal. The operation now continues with the control processor performing other tasks if it has been programmed in a manner to do that but at some point in time the END signal is generated within the control arc receive logic which on the next PE-CLOCK signal allows the ACTIVE flip-flop to be reset which in turn causes the ACTIVE-DOWN flip-flop to be set. If in the case the originating control processor sought to wait until the completion of the execution of the instruction, said control processor would now continue its operation.

The exemplary case of a processing element already in the active state at the reception of a request signal is illustrated in FIG. 5N. In this FIGURE, the control arc transmit logic not knowing initially that the processing element for which it is going to request instruction execution is active proceeds with the generation of the reset CAT and START-CAT clock pulses and thus enabling the generation of CP-REQUEST-PE signal as described before. The processing element now, however, being active, the operation of the control processor waits. The action in the processing element continues with the completion of this instruction until the generation of the END signal which allows the resetting of the ACTIVE flip-flop on the next clock PE clock signal. After this occurrence, the request signal is now accepted by the receiving processing element which allows the setting of the ACCEPT flip-flop and on the next clock pulse the load instruction pulse is generated and the processor's ACTIVE-CP signal is generated as before. The remainder of the operation in this case is as described previously.

In concept, this particular interchange of signals allows maximum utilization of each processing element and is accomplished because the control processor may be actively generating the next instruction to be executed by processing elements while that original processing element is currently executing an instruction. It should be noted, however, that only a single request signal can be active at one point in time over one of the control arcs out of the control processor and that only one instruction input over a control arc can be honored by a processing element at one point in time. In a particular exemplary implementation of a graph architecture machine, a single request signal may be used by several processing elements. In this manner, a single control arc can thus be used to broadcast an instruction to several processing elements simultaneously. This is particularly useful in the implementation of machines which have highly parallel operation of instruction in several different processing elements. In no case, however, can a single processing element receive instructions from more than one control processor at the same time.

The state defined control concept is now described in detail. The basic idea of the state defined control concept is that a particular processing element may execute its sequence of operations as a function both of a current state value within the PE which was set by previous instructions or previous execution by the processing element in conjunction with the new instruction received by the processing element. In this manner, the requesting processing element does not need to keep track of the complete sequence of operations within the processing element in which an instruction is to be executed. The idea of a processing element operating in such a state defined control manner is not new. What is new and novel for application in a graph architecture information processing system is that at least two processing elements shall have such a state defined control mechanism. In this manner, the complete operation of the system is defined by states in a multiplicity of processors and not by any one single processing element. This situation is illustrated in FIG. 5P which illustrates three processing elements labeled 5P01, 5P03 and 5P07. In the situation illustrated, processor 5P01 by way of its control arc to 5P02 can request execution of an instruction in processor 5P03 which receives such instruction in its control arc receiver logic 5P04. This instruction now is used by the state control logic 5P05 or SCL for short to determine the sequence of actions by processor 5P03. As a function of the operation code and data portions of this new instruction received in processing element 5P03, that processor may elect to perform operations completely within itself or execute a sequence of instructions to yet another processing element 5P07 by way of sending instructions over the control arc from the control arc transmit logic 5P06 to CAR logic 5P08 in said second processor. This second processor now may also have its own state control logic 5PO9 for determining its sequence of operations as a function of its new instruction input. In the general case, processor 5P03 will initiate the state in processor 5PO7 by way of an instruction. After this, subsequent instructions received by 5P07 from processor 5P03 will be interpreted by said second processor and its actions performed as a function of that previously defined state and the new instruction input. In this manner, processor 5P03 does not have to record in its own memories or in its own operations what state 5P07 may be in. As an example, consider the case of PE 5P03 having two possible state values, one called STATE1 and the other called STATE2. In the first case, assume PE 5PO3 has state value STATE1. Upon reception of an instruction called EXECUTE from PE 5P01, PE 5P03 in this case generates an instruction to PE 5P07. In a second case, assume PE 5P03 has state value STATE2. In this case, PE 5P03 will generate no instructions to PE 5P07 even though the same EXECUTE instruction is received. These state defined actions on the part of PE 5P03 are performed on the basis of the state sequence programming of the state control logic in PE 5P03, said programming being performed during the design of the system. Also, the state sequences may be redefined during the operation of the system by reloading the memories contained in said processor. An example of such redefinable state sequence state defined control processing element is the METAPROCESSOR described in later paragraphs. Not all processing elements in exemplary graph architecture machine need be implemented using the state control logic block.

FIG. 5Q illustrates an example showing a processor 5Q01 which does not have state defined control and which has an instruction input into the CAR logic 5Q02. The individual operations now executed by this processing element as defined by the micro-code generator ROM 5Q03 which has been described previously is now completely defined by the instruction input and the OPCODE in CAR registers.

Processing elements in an exemplary graph architecture machine may implement the state control logic SCL in one of two principal ways as illustrated in FIGS. 5R and 5S. The simpler case of the processing element determining its operations as a function of state and new instruction input but being allowed only to change its state value once per instruction execution is illustrated in FIG. 5R. What is shown is the control arc receive logic 5R02 which has outputs which feed the microcode generator as described previously in FIG. 5Q but in addition go to a multiplexer 5R03 which then gates these signals to state register 5R04. For a specific instruction as commanded by the OPCODE portion of the instruction, the micro-code generator 5R05 wil require the loading of the state register by enabling the load state signal which then allows the value of the OPCODE or DATA PORTIONS from the input instruction to be loaded into the state register 5R04. The determination of whether the OPCODE or the INPUT DATA PORTION of the instruction is loaded into the STATE REGISTER is determined by the SELECT-MPXR signal into the multiplexer 5R03. On subsequent instructions, the OPCODE or DATA PORTIONS are now used in conjunction with the output value of the STATE REGISTER to determine which of the multiplicity of the microcode enables are to be executed. The STG, DLU, FDIU and DIU processors in the exemplary training system are examples of state defined control processing elements using the scheme illustrated in FIG. 5R.

The more complex case is illustrated in FIG. 5S wherein is illustrated a processing element 5S01 which has a state control logic which allows the changing of states a multiplicity of times during the execution of a single instruction. In this case, the processor has logic similar to that illustrated in FIG. 5R but, in addition, has a STATE SEQUENCE MEMORY 5S05. The STATE REGISTER in this case 5S04 is also a counter so that a sequence of states can be executed and by way of an output from the state sequence memory 5S05 through the multiplexer 5S03 a new state value may be loaded into the state counter register 5S04 as determined by the current value outputs of the micro-code generator 5S08. The determination of whether the next state or a different state is to be executed in the exemplary processor is made by the micro-code generator which determines as a function at a portion of the STATE SEQUENCE MEMORY 5S05 output called the SELF-CODE in conjunction with conditions generated within the processing element as well as conditions which may be generated externally to the processing element. In a particular example, while the processing element is executing a state sequence the state sequence memory SELF-CODE may require the execution of an instruction in another processing element. This requires the initiation of operation of the control arc transit logic element which must be part of the processing element 5S01 if such an external instruction is to be executed. It is not necessary, however, that a processing element be a control processor to have state defined control. In this case, the execution of such an instruction by a second processor may now result in data being generated which is used through the instruction input lines in the control arc receive logic to be compared with data in the compare circuit 5S07 with data in the state sequence memory 5S05. As a function of this data comparison, the micro-code generator may the require a new state to be entered in the state counter register 5S04. This then allows a conditional execution of states within the processing element and this is what is meant by a state defined control processing element. In the exemplary training system, the META, FORM, INPT and DCU processors have this type of state defined control capability. In particular, the METAPROCESSOR operates in conjunction with the DSPL processor in such a manner that the combination of the state in the METAPROCESSOR and a separate state in the DSPL processor allow the generation of complex graphic sequences seen on the display element and such complex graphics are generated under the direction of the DSPL with only the data generated by the METAPROCESSOR. For example, in the MCP program example described previously, the "0" portion of the display statement at line 4D03 requires the selection of the zero state in the DSPL processor. This then will require the DSPL processor to use the data given in the quoted string of characters in lines 4D03 through 4D06 to generate the display illustrated in FIG. 4C. Alternately, a display statement may be used in an SPOML program which sets a separate state in the DSPL. As a function of setting this separate state, the use of the data from a quoted string such as 4D03 to 4D06 will have a completely different effect on the operation of the DSPL. For example, the DSPL as a function of the initial state to which it was set may generate the information on a CRT display device as opposed to a plasma display type of device or, alternately, print the information on a printer device of system. The determination of what action is taken using the data from the DSPL input instruction is made independently of actions in the METAPROCESSOR and this is what is meant by the processing system having processing elements at least two of which have separate state defined control elements and can work in conjunction to perform more complex operations than either processing element operating alone.

The instruction sequence level of operation in this system may now be further explained. Referring to FIG. 4E again, execution lines 4E19 through 4E31 constitutes the sequence for interpreting the characters in the display statement of an SPOML program. At line 4E20 is shown an instruction out of the state sequence memory for the METAPROCESSOR which is called a SCAN-WAIT or SCANW instruction. This instruction has the effect of causing the execution of the ADVANCE instruction in the program memory processor. At the completion of the execution of this instruction in PMEM, the METAPROCESSOR automatically loads the data from the program memory processor output into the register for its own use. The instruction called CHAR at line 4E21 with operand quote (") now compares the input data from the PMEM with the quote character. If the two characters are the same, then a jump is executed, i.e., a redefinition of the current METAPROCESSOR state to the state called DQUOTE. Alternately, in lines 4E23 and 4E24 is a check to see if the character input from the program memory processor is of the type DIGIT. If the character is a digit, then a new state called DNUM is entered at line 4E25 which consists singly of execution of the instruction DCUSET which is an instruction executed in the DSPL processor and since in this case the data is a digit the DSPL is set in that state. This is an example of the mechanism for setting a state in one processor as a function of the execution of a sequence in a sequence processor. Within the DQUOTE state at line 4E27 in the METAPROCESSOR sequence is now the sequence of steps which allows the generation of data from the program memory which is then sent to the DSPL processor for execution. For example, the SCAN instruction is issued again at line 4E27 to pick up the next character from the SPOML program and assuming that this character is not the quote character which would mean the end of the string of data then that data is sent out with the DCUEXC instruction which allows the DSPL to execute its current state with the new data. In this manner, the DSPL will use this data to generate the several display lines and symbols as illustrated in FIG. 4C. At the completion of the sequence of data from the DSPL from the METAPROCESSOR, the quote character is detected at line 4E28. At this point, the new state in the METAPROCESSOR called state D is entered and the operation continues by intepreting the characters from the program memory processor for the currently running program.

At a given point in time, the period character may be detected from the program memory which is the SPOML program statement to require the system to stop. The halt sequence, lines 4E14 through 4E18, is now executed. Initially, the instruction CLEARM is executed which clears the match stack in the STG processor. Now the instruction ENABLE is executed within the OIU processor which allows input from the student and now the HALT self instruction at line 4E16 is executed by the METAPROCESSOR. This stops the operation of interpretation processes by the METAPROCESSOR. However, the METAPROCESSOR keeps its state which is called HALT2 at line 4E17 so that subsequent instruction initiation from the OIU to the METAPROCESSOR will allow the continued execution of operation at this state. For example, once the student has entered his choice, say for the question in the MCP program, then continued operation in the METAPROCESSOR at line 4E17 will require the data which it receives with the instruction which is the character entered by the student either from the keyboard or by the pen selection device to be passed out with the PUSHM instuction which allows the storing of that data within the match stack within the STG processor. The METAPROCESSOR now at line 4E18 executes the instruction called JUMP PROG which allows the redefinition of meta state register to be at the PROG point 4E01. This then allows subsequent interpretation of later statements in the SPOML program following the halt statement. These later statements as described previously then will monitor and evaluate the student's inputs to determine what actions the machine is to take as a function of the student's inputs.

As illustrated in FIG. 5S, an exemplary state control logic portion of a processing element may also contain a state stack element 5S06. This state stack allows several states to be pushed into a memory by using a self instruction called PUSH. The purpose of saving such states is to determine the future operation of this processing element as a function of later inputs. In particular, at specific points in the execution of the sequences from the state sequence memory 5S05, the operation called STACK POP is executed which allows now the previous value of state which has been loaded into the state stack to be reloaded into the state counter register 5S04. This state stack control mechanism allows complex sequences of operation to be performed and in the case of the METAPROCESSOR is the principal which allows the implementation of a high level language. This combination allows the implementation of what is called language grammars directly in the state sequence memory of the METAPROCESSOR. The detailed operation examples of usage of this state defined control mechanism is described in detail in later paragraphs.

A detailed description of the maintenance multiplexer concept which may be used in conjunction with an exemplary graph architecture system is now given. The purpose of the maintenance multiplexer concept is to allow the inspection of the contents of any register or the output of any memory device is a graph architecture system. This concept allows access to these parameters independently of the size and number of processors used in a system. This is a new and novel concept and unique with the possibility for implementation in a graph architecture machine. The basis of the use of the maintenance multiplexer concept is that the processing elements in the graph architecture system already have the ability of switching data from within individual processors and giving that data to separate processors. For implementation of the maintenance multiplexer concept, two elements must be added to the processing elements in the graph machine.

In the first case as illustrated in FIG. 5T, a maintenance multiplexer 5T02 must be added. The maintenance multiplexer allows the direction of the address input to the data multiplexer 5T01 which is already a part of the processing element to be directed as a function of a MAINTENANCE ADDRESS input. The operation is as follows. During normal operation, the maintenance enable signal MAINT-ENBL points the maintenance multiplexer 5T02 to allow the use of the multiplexer address generated within the processing element. In this manner, the processing elements operates as described before. Alternately, if the maintenance enable signal MAINT-ENBL is activated, then the maintenance multiplexer 5T02 causes the maintenance address to be used as the address for the dta multiplexer 5T01. In this manner, the contents internal to the processing elements or the value of signals input to the processing element may be read as the output from the processing element. By having such a mechanism in each processing element in an exemplary graph graph machine, then any particular data register or memory output may be accessed or viewed for maintenance purposes by defining the value for maintenance address which allows the switching of all multiplexers in the system to come to a common point. To illustrate, referring again to FIG. 5P, which shows three processors, separate maintenance address lines would be given to each processing element 5P01, 5P03 or 5P07 and since there is a control arc from 5P01 to 5P03 a data register in 5P01 can be read into processing element 5P03. In a similar manner, by directing the multiplexer within processor 5P03, the data can be put on the output lines to processing element 5P07. In this manner, the data output from processor 5P07 can reflect a value of a register in processing element 5P01 or alternately the value of a register in processing element 5P03 using a different maintenance address or alternately the value of a register in processing element 5P07 using still yet a separate maintenance address number. In the exemplary graph architecture training system as illustrated in FIG. 4A, the data output from the METAPROCESSOR is used as the common point for maintenance data addressing. In this manner, the high level addresses for the maintenance address refer to registers within the METAPROCESSOR. The next address bits in a maintenance address refer to processors immediately surrounding the METAPROCESSOR, these being the INPT, the OIU, the FORM, the PMEM and the SEM. In a similar manner, the second level of processors may access data in a third level of processors, such as DSPL, WFB, etc. In this manner, in the exemplary system a tenbit maintenance address can access any of approximately fifty registers and memory outputs in this system. Appendix B contains a listing of maintenance addresses and the corresponding registers which may be monitored in this manner. This data value is valid for the maintenance address only in the contect that the MAINT-ENBL signal is active. Otherwise, the system operates normally. It is possible since the processing system may actively be performing functions that the switching of the maintenance multiplexer may cause improper operation. Because for maintenance purposes, it is desirable to monitor the value of specific registers at different points in the operation of the system a mechanism must be provided to allow the periodic stoppage of operation in the system. This is accomplished by adding an ADVANCE-DISABLE flip-flop to each control processor in the graph architecture machine as illustrated in FIG. 5U. What is shown here is the ADVANCE-DISABLE flip-flop 5U02 and a gate 5U01 which allows the use of the ADVANCE-DISABLE flip-flop. When the ADVANCE-DISABLE flip-flop 5U02 is set, the ADVANCE signal which is used by the control processor to determine when it can proceed with the separate operations after generating an instruction to another processor is disabled. In this manner by controlling the action of this ADVANCE-DISABLE flip-flop, the system can be caused to stop after execution of each instruction in a sequence of instructions and thus data may be monitored at the points in between the execution of each instruction. This is independent of length of the sequence of instructions which in many cases may be several hundred thousand instructions long. The process operates as follows: The STEP-MODE signal into gate 5U01 is activated for the maintenance operation. Since this is now active, the NEXT INSTRUCTION pulse into gate 5U01 allows the setting of the ADVANCE-DISABLE flip-flop 5U02 which then causes the control processor in which the flip-flop is contained to halt after each instruction issuance. The system now will not proceed until the reception of the STEP signal which allows the ADVANCE-DISABLE flip-flop 5U02 to be reset. This then allows the control processor to issue the next instruction for execution and again wait until another STEP signal is received. The STEP-MODE and the STEP signals may variously be generated by switches on a maintenance control panel of the exemplary graph architecture machine or may be generated by a separate processing element whose function it is to evaluate the performance or monitor the operation or determine failures within the exemplary graph architecture system. Because the ADVANCE-DISABLE flip-flop is set in all control processors at the same time, the use of the maintenance address concept does not destroy the operation sequence of any processor in the system. In this manner, data can be reached and monitored in between the execution of each and every instruction in a sequence of instructions in the graph machine. In summary, by adding the maintenance multiplexer to each and every processing element in a graph architecture machine and by adding an ADVANCE-DISABLE flip-flop to each control processor in an exemplary graph architecture machine, it is allowed to monitor the value of any register or memory content in the system and it is clear that the number of processors in the system may be arbitrarily large for this operation to take place. In that the maintenance multiplexer concept is not a necessary part of every exemplary graph architecture machine, the portions of the maintenance multiplexer and the ADVANCE-DISABLE flip-flop circuits are not described in each of the ensuing processing element descriptions.

In the example training system, the function of the program execution subsystem is to take data from the inputs processing subsystem and determine what operations are to be performed using the current portion of a lesson program. The processors in FIG. 4A which make up the program execution subsystem include the: (1) METAPROCESSOR (META), (2) Program Memory Processor (PMEM), (3) Semantics Processor (SEM), (4) Numerics Processor (NUM), and (5) String Processor (STG) hereinafter described in detail. Of the foregoing, the METAPROCESSOR is the principal control processor for initiating sequences of operations in the other processors which make up the program execution circuitry as well as selectively initiating operations in other portions of the overall system. The NUM processor is a data processor which performs all program commanded numeric computations such as add and multiply and in addition performs the functions of converting numbers from one base number system to a different number base (such as decimal to binary), incorporates a real time clock and, as an example, allows storage for up to 64 numeric variables.

The string processor is a data processor which performs functions on strings of data. The term string means an ordered sequence of data words. The number of words in the string is called the string length. The functions performed by the string processor, or STG, on strings include (1) string concatenation in which two strings of the same or different lengths are strung (concatenated) together to form a single third string which has a length equal to the sum of the lengths of the original string, (2) string alteration in which case a string is broken up into two strings, the dividing point being determined by yet a third string called the match string which must correspond to a substring of the original string, and (3) string comparison in which a match string is compared word by word with a portion or all of the words of a second string to give a determination as to existence of that string at the beginning of the second string. The usefulness of these operations to problems in text editing. Student answer response processing, and grammar processing is well known in the art as described in, for example, any standard text for the SNOBOL programming language. The current mechanization of these functions using the concept of stacks is new in the art.

The SEM is a control processor which directs the activities of the STG and NUM processors either separately or in combination. In particular, a concatenate operation directed by command of the META to SEM causes SEM to issue a sequence of instructions to the STG, each instruction of which manipulates a single word of a string and only upon completion of the entire sequence of operation are all words of the first string concatenated with all the words of the second string. As a further illustration, a numeric variable within the NUM may be converted to a string of decimal characters representing that number and conversely a string of characters may be converted into a binary number by taking a string from STG and transferring each word of such string to NUM which comprises a single binary number.

The PMEM processor holds in a memory at any given time the portion of the overall lesson which is being used to direct the actions of the machine. This lesson program which is coded in the SPOML language, the elementary parts of which are alphabetic characters, is stored as a continuous string of 8 bit words called characters. The PMEM supplies the next logical character in the sequence to the META for interpreting the actions which are to be performed by other processors. As each sequence of characters is exhausted, a further program string segment is loaded into the PMEM.

The overall operation of the program execution circuitry may be likened to a software interpreter which is well known in the art, but which is embodied in a novel manner in the current invention and consists of the following sequence of operations: (1) source program is given a part at a time to the (2) lexical analyzer which composes the data such as for taking a string representing the name of a prior storage filed picture and converting said string to a single word address for locating said file in the mass storage device by way of supplying information to the (3) syntax analyzer which determines that the name so defined relates to a picture stored in mass storage as opposed to the name of a new program string portion and supplies this fact to a (4) code generator which provides an ordered sequence of instructions to one or more (5) instruction execution devices which carry out those primitive operations necessary to cause the mass storage data referred to originally by a name to be shown on a display device. In the current invention, the correspondence is that the object program is stored in the PMEM which supplies the character data to the META which performs the lexical and syntax operations itself or causes the FORMAT, DSPL or INPT processors or perform the lexical and syntax anaylsis depending upon whether the operation currently desired by the program is for string, numeric, mass data transfer, display or input processing. In the case that the META performs the lexical and syntax operations, the further operations are initiated in the control processors SEM, FORMAT, DSPL or INPT which perform the code generation functions to one or more of the data processors in the combination or ensemble of processors. Alternatively, the META may cause instructions to be sent out which directly cause data processor actions effectively bypassing the code generation function of the control processors although such instructions do flow through said control processors.

In the following, the detailed construction and operation of each processor which makes up the program execution subsystem is described.

The numerics processor performs the commonly known functions of arithmetic manipulation of data such as add, subtract, multiply and divide and further allows numbers to be inputted in various number bases and converts such numbers as is necessary to carry out the arithmetic computations as well as converting numbers stored in the binary form used internal to the processor for output in any number base. Further, the NUM contains storage for variables which may be referred to by the program and a real time clock useful in timing the difference between various events in the execution of a lesson such as the time required for the operator to make a response to a displayed question. The NUM processor may be implemented by a special design or using any number of vendor numeric processing devices and for this reason the function is not new in the art and since it is not new only a general description will be given.

The NUM processor is illustrated in block diagram form in FIG. 20. A signal, SEM-INST-NUM, is applied at terminal 20A and then to an operation input register 2001 which holds the numeric code representing the current instruction which is then being executed in a manner similar to that described previously. The data part of the SEM-INST-NUM is also applied to the data input register 2002 which may optionally as determined by the OPCODE hold the data supplied with the instruction for execution. The operation input register 2001 is connected to a micro-code generator 2003 which is a read only memory, and which decodes the encoded operation code into individual elementary register and data movement operations which are necessary to carry out the intent of the instruction during the execution of the instruction, and provides at its output enable signals as well as signals to a control logic circuit 2004 which is identical in function to the control logic previously described in that it supplies an ACTIVE signal in response to a REQUEST signal and during the ensuing time period generates one or more timing pulses (the number being defined by the micro-code generator) and upon having generated the proper number of timing pulses drops the ACTIVE signal and awaits the occurrence of yet another REQUEST signal. The control logic also generates the condition signal COND over a line NUM-COND-SEM to the originating control processor, the meaning of said COND signal being appropriate for the instruction being executed as, for example, an overflow condition which results when two numbers are added and the result is too large in value to be held in the result register 2005 which holds one of the two parameters in, for example, an add operation and receives the result of such an operation.

A Q-register 2006 which may supply the second parameter in an operation such as addition having been loaded previously with a number originating elsewhere in NUM is connected at its input to a numerics variables memory 2008 and at its output to an arithmetic logic unit 2007 which is a well known circuit in the art for performing addition and subtraction.

The numerics variable memory which is a random access memory may hold, for example, up to 64 numbers, any location thereof which may be used as a parameter for arithmetic operation by transfer through the multiplexer switch 2009 to the arithmetic logic unit 2007.

A variables address register 2010 holds a number, usually representing a character of the English alphabet, said number allowing the selection of one of the variables in the numeric variables memory 2008. A real time clock 2011 which is a continuously clocked counter allows readout and may be used as a parameter in an arithmetic operation by means of its value being transferred through the data multiplexer 2009.

A conversion register 2012 which is a shift register wired to allow conversion from one number base to another as for binary to decimal conversion receives input signals from the numeric variables memory and provides an output of the data output register 2013 which holds a part of a result number for use by the SEM and for subsequent distribution elsewhere.

A data multiplexer 2009 is a switch guided by the micro-code generator for a particular instruction to gate data from the input register 2002, real time clock 2011, numeric variables memory 2008, conversion register 2012, or results register 2005 to be used by the conversion register 2012, result register 2005, arithmetic logic unit 2007, Q-register 2006, or stored in the variables memory 2008.

The instructions executable by the NUM processor may be broken down into the following categories:

(1) Control setup as for defining the mode of number base conversion to be used.

(2) Data input and output.

(3) Arithmetic instructions such as add and subtract.

(4) Data transfer such as duplicating the result register data into a particular variables memory location or, as a further example, reading the current value of the real time clock for use as a parameter.

The sequence of operation of typical instructions carried out by NUM is hereinafter described. To set a mode for subsequent number base conversion, the SEM issues the appropriate instruction along with the SEM-RQ-NUM signal to control logic 2004. If, at this time, the NUM is not active, the control logic generates a timing pulse which latches the OPCODE portion of the instruction into the OPCODE input register 2001 and at the same time loads the SEM-DATA into the data input register 2002, and at the same time raises the NUM-ACTIVE-SEM signal which notifies the SEM that the instruction has been taken and the SEM may perform other operations. The micro-code generator switches the data multiplexer 2009 so that it may read the data input register, enables the conversion register to accept the parameter and enables the control logic to generate one timing pulse. The result of this timing pulse is to cause the parameter which defines the conversion mode to be stored into the conversion register 2012. Having issued the required number of timing pulses, the control logic drops the NUM-ACT-SEM signal and awaits a subsequent request signal. No condition signal is generated for this instruction.

Data input is accomplished by the execution of a series of DATA-IN instructions. Each instruction supplies a portion of the data needed by the conversion register to form a complete number. Each instruction works as follows. The instruction is accepted as previously described, the data input is selected to the conversion register 2012 through the data multiplexer 2009 and a timing pulse from control 2004 causes the conversion register to assemble the new data along with the old. As before, control 2004 drops the active signal.

As an example of data transfer, consider an instruction for moving data from the conversion register to the Q-register 2006. The instruction is accepted as before and the data multiplexer 2009 is switched to accept data from the conversion register 2012 and gate said data to the Q-register 2006. The control logic 2004 generates timing signals allowing the Q-register 2006 to load and then drops the active signal.

As an example of an arithmetic instruction, consider the addition of a number in the Q-register 2006 to a number in the result register 2005 with the sum placed into the result register 2005. The instruction (which has no associated SEM-DATA) is accepted as before and the micro-code generator 2003 enables the arithmetic logic unit 2007 to perform the add operation, enables the multiplexer 2009 to read the current result register 2005 data and enables the result register 2005 to be loaded. The control logic 2004 generates the required number of timing pulses to load the result register 2005 with the sum.

Other instructions may be used to store result data 2005 into the variables memory 2008, read the variables memory into the Q-register 2006, load the variables address register 2010 and transfer result data to the conversion register 2012 where said data may be converted to the appropriate data base and read out by a series of instructions through the data output register 2013 which forms the NUM-DATA.

The STG is an autonomous processor for manipulating data strings (an ordered sequence of data words) that may be used as a peripheral processor to an existing computer system or as a functional processor in a graph architecture processing system such as the example training system. FIG. 30 illustrates the typical interconnection of STG in such systems. The processor called SEM (for semantics processors) may be a computer or control processor and supplies the data and sequences of instructions necessary for performing the string computations. FIG. 30 also lists the signals which exist between STG and the rest of the system for operation and said signals include a:

SYSTEM CLOCK signal which is used by STG to synchronize its operation with the SEM and generate internal timing control signals.

MASTER RESET signal which is used to initialize the control logic within the STG.

SEM-RQ-STG signal which is active when the SEM processor desires the STG to execute an instruction.

STG-ACTIVE signal which is generated by STG and when active indicates that STG is executing the instruction requested by SEM.

FULL-COND signal which indicates that a data string is of maximum size.

EMPTY-COND signal which indicates that a data string has no data content.

STG-DATA word output of STG supplies the results of computations by STG.

SEM-OPCODE word input to STG defines which of the 32 instructions is to be executed for a given instruction request.

SEM-DATA word which supplies the data for use in executing an instruction.

An instruction is defined as the combination of the SEM-OPCODE and SEM-DATA words and an instruction execution is defined as one sequence of SEM-RQ-STG and STG-ACTIVE signal activations.

External inputs to SEM consist of user data (from the META) to be manipulated and external outputs are results of computations needed by the user (the METAPROCESSOR).

The sequence of instructions supplied to the STG from the SEM is defined by the user as a set of programs for accomplishing the computations desired by the user.

The STG processor performs those functions on data strings that are useful in performing text editing and grammar equation solution. These functions include, but are not limited to, string concatenation, string alternation and substring comparison and the approach taken in implementing these functions in the STG processor is a new and novel approach and is an essential part of the invention.

The method of string processing employed in STG is based upon generalizations of elementary pushdown (also called LIFO or Last-In-First-Out) stacks and elementary queueing (also called FIFO or First-In-First-Out) stacks, the principle of operation for which, taken individually, is well known in the art. Basically, a stack is a data storage structure which stores a string of data in which only the end data items of the string may be manipulated. For example, in the LIFO case, data is written on one end of the stack and taken back (with loss of that data to the stack) from the same end. For a FIFO stack, data is written in one end and taken from the other.

A string normally has two ends called a left and a right end respectively, or those ends which would appear to one if the data string is laid out horizontally.

There are basically four elementary pushdown stack operations: (1) write, (2) push, (3) pop, and (4) read. These are illustrated in the table below for the left end along with symbology useful in describing the operations and examples of their application to exemplary data strings.

In the immediate above table, x and y represent singular data words, the elipses " . . . " imply any other data which may be in the stack and the arrow .fwdarw. means the data is manipulated from the left end of the data string.

As in the immediately previous table, the four operations may similarly be defined in the right end of a data string as in the following table:

It is to be noted that the data in the left end operation case is reversed with respect to the data appearance for the right end operation case and this is a useful feature of the string processor. Also, note that depending upon the current data contents of a stack, the push operation can not be accomplished if the amount of data already in the stack has used all the available storage locations in which case the stack is said to be "full." Also, the pop, write and read operations can not be accomplished if the stack has no data contained therein in which case the stack is said to be "empty." The first generalization of these elementary operations is for several character words manipulated at one time. There are again four operations each similar to those described, but more complex, and given the names replace, place-on, withdraw and read. These are illustrated immediately below for the case of left end manipulation of data.

In these cases, sine there are multiple data words represented, for example, by the letters A and B, these data words are enclosed in quotations so that no confusion can be made with the characters of normal words. In the case of replace and withdraw, the operations are performed only if the character string given in the instruction, such string normally referred to as a "match" string, is found on the top of the stack. If the match string is not found, then the operation is said to "fail." As before, these operations may also be accomplished on the right end of stack data.

The second principal generalization of these operations are for a multiplicity of stacks, some of which are manipulated on the left end and some on the right end. Consider the exemplary case of two stacks, one of which is called the LEFT stack and the second the RIGHT stack with connections such that data is manipulated on the right end of the LEFT stack and similarly data is manipulated on the left end of the RIGHT stack and data is allowed to flow between these ends. Pushing a string of characters into the left stack causes data movement in the left direction and similarly for the right stack. Moving characters from one stack to the other keeps the proper ordering of the strings overall. There are two operations called move and restore, illustrated by examples in the following table, for data movement in both the left direction and the right direction.

The move operation moves all data preceding the matching string (does not operate exclusively on the top of the stack). Also, the restore operation is used after the move operation to either duplicate data (direction of restore operation is opposite to direction of move) or to eliminate a substring of data (direction of restore is the same as the direction of the move).

This set of generalized operations clearly can be accomplished by using the primitive stack operations wherein the stacks are arranged such that data may flow properly. Also, a multiplicity of stacks may be used to allow string computation on several data strings of different content.

The principles here described are embodied in an exemplary fashion in the string processor (STG), the components and interconnect of components for said processor as illustrated in FIG. 21. The purpose of the illustrated components is firstly discussed.

The STG OPCODE register 2101 performs the function of holding the OPCODE part of the instruction. The input data register 2102 stores the DATA part of an instruction. The micro-code generator 2103 supplies the appropriate elementary enables and data switching as required for the current instruction.

The control logic 2104 communicates with the SEM processor using REQUEST, ACTIVE, and CONDITION signals as well as generates the required number of timing pulses for carrying out the execution of the instruction.

The source/destination register 2105 determines which stack data is taken from and/or which stack data is given to other parts of the STG. The output data multiplexer 2106 allows connection of data paths amongst the various data for use by the SEM as well as an OPERAND for comparison with data in one of the stacks.

The match counter 2108 (MCTR) and match stack memory 2109 taken together form the match stack, the purpose of which is to hold the definition of a match string during one of the generalized stack operations. The left counter 2110 and left stack memory 2111 together form the LEFT stack which performs the functions previously described. The right counter (RCRT) 2112 and right stack memory 2113 together form the RIGHT stack for STG.

The label counter (LABCTR) 2114 and label stack memory 2115 together form the LABEL stack which is one example of the multiplicity of additional stacks which may be used to allow computation on different strings in which computation is performed using a set of three of the stacks at one time. In a particular application, the LABEL stack holds the names for mass storage files which may be needed for display and program loading purposes.

The full/empty logic 2116 monitors the counts of the various stack counters and provides appropriate signals to the control logic 2104 when a stack becomes empty or is full.

The compare circuit 2117, which compares two words for correspondence, is used to determine if the data in the match string corresponds to the data in the required LEFT, LABEL or RIGHT stack.

The operations of the STG processor correspond to the primitive stack operations previously defined and may be broken down into the following categories: stack clear; read stack; write stack; pop stack; push stack; move stack; compare stack; read length; restore stack; and save stack contents.

By convention, a stack is empty if the count in the counter for that stack is of value zero. By convention, a stack is full if the counter has its maximum possible count which in the current machine is 255. The full/empty logic 2116 continuously monitors these conditions and enables the condition line through the control logic 2104 for any instruction for which these conditions are important. Examples of instruction execution follow.

The push stack instruction for the match stack is accepted and loaded into the OPCODE register 2101 and data input register 2102 after the occurrence of a SEM-RQ-STG signal through the control logic 2106. The MCTR 2108 is incremented by a pulse from control logic 2106 and the data having been gated through the output data MPXR 2106 to the match stack memory 2109, the data is recorded therein by a pulse from the control logic 2104.

The pop instruction to the LEFT stack, for example, causes the then current data at the location indicated by the LCTR 2110 to be gated through the data output MPXR 2106 and loaded into the output data register 2107. This is followed by decreasing the count in the LCTR 2110 by one count, effectively losing the data at the original location.

The move stack operation, as for moving data from the LEFT stack to the RIGHT stack, causes one character to be read from the LEFT stack, pushed into the RIGHT stack in the sequence previously defined and that character popped from the LEFT stack. During the operation, the data is compared with data in the data output register 2107, and the condition is set as a function of whether the data compare or not.

The save stack instruction causes the current count of, for example, the label counter 2114 to be duplicated in another register internal to this counter and described in more detail later. A subsequent restore instruction causes this saved count to be reloaded into the counter effectively restoring the size and content of the string value at the time of the save.

The read length instructions allow the size of any string stored in a stack to be read and used for computation and is accomplished by loading the counter contents for the appropriate stack into the output data register.

The generalized stack operations are accomplished by a sequence of the above instructions as commanded by the SEM processor.

FIG. 31A illustrates the format of the instructions given to STG. An instruction consists of an eight-bit OPCODE of which only the lower five bits are used and a SEM-DATA part of eight bits. The OPCODE part dictates which of the 32 possible instructions are to be executed for a given instruction acceptance and the DATA part supplies the data to be used for the execution of that instruction. FIG. 31B illustrates the format of the data used internally to the STG and is representative of the data content at each location in a stack. FIG. 31C illustrates the format of a stack pointer word which is used to define the left or right end of a stack. Note that the FULL and EMPTY status conditions are stored as part of the stack pointer word.

The complete set of 32 exemplary instructions for an STG are defined in summary in Appendix CC. Appendix CC also contains example specific OPCODE numbers which would be supplied from the SEM.

In this section, the operation of each of the STG circuits is described and the operation of each of the STG instructions is explained in terms of the detailed functional block diagrams FIGS. 32-38 and timing diagrams FIGS. 39-39H.

FIG. 32 illustrates the detailed breakdown of the control logic 2104 which is used to interchange control signals with the SEM for accepting instructions and generating the timing pulses necessary to accomplish the execution of the instruction. An instruction is accepted by the STG at a time instant when the SEM-RQ-STG signal is present and the NOT-STG-ACTIVE signal is present. In the case that the STG is already executing an instruction, that instruction will be completed before the new instruction is accepted. At the time that gate 3201 becomes active, the STG-ACTIVE flip-flop 3202 becomes set on the next SYSTEM-CLOCK signal generating the STG-ACTIVE signal. This signal notifies the SEM that the new instruction has been received and the SEM now drops the SEM-RQ-STG signal. Once the STG-ACTIVE signal is enabled, the STG phase counter 3206 is allowed to count up on each occurrence of system clock pulse. As the STG phase counter 3206 counts, the phase decoder 3207 generates the eight pulses P0, P1, P2, P3, P4, P5, P6 and P7, in that order, and in step with the system clock pulses. Upon the occurrence of the P7 pulse, the STG-ACTIVE flip-flop is reset, completing the execution of the instruction. The P0, P1, . . . , P7 pulses are used to execute the micro-operations defined by the micro-code generator 2103 for the OPCODE of the current instruction. The master reset signal is used to reset the STG-ACTIVE flip-flop and thus initialize the STG for acceptance of a new instruction. The master reset is normally used after applying power to the STG or to abort the execution of an instruction. STG Instruction and Data Flow

FIG. 33 illustrates the OPCODE and data (input/output) registers and the STG multiplexer 3303. The data register has two inputs and is used both for holding the SEM-DATA part of the input instruction and for holding data for output from the STG.

The STG OPCODE register 3301 is loaded on the same clock pulse which sets the ACTIVE flip-flop each time a new instruction is received. The STG-OPCODE signals are used by the micro-code generator shown in FIG. 34 to define the individual micro-operations to be performed for an instruction. For particular instructions, the LOAD-DIN signal is active from the micro-code generator allowing the data MPXR register 3302 to be loaded with the SEM-DATA part of the instruction. The data register 3302 is loaded at the P7 pulse time from STG-MPXR for more instructions have the LOAD-DOUT signal enabled. The MUX-ADD from the micro-code generator which is unique for each instruction is used to identify the source of data through the STG-MPXR 3303. In this manner, the data register 3302 may be loaded with the counter value of a particular stack or the MEM signals which are the content of a particular location in a stack.

FIG. 34 is the micro-code generator for the STG and consists of four read only memory (ROM) devices, labelled STG ROM 1, 2, 3 and 4. The address for ROM's 1, 2 and 3 are defined by the OPCODE portion of the instruction which forms a five-bit address. At each of the 32 locations in the ROM's is stored a pattern of bits to enable the several micro-functions for a given instruction OPCODE. In the general case, these micro-code enables such as the PUSH and POP signals from STG-ROM 2, 3402 are gated with timing pulses to accomplish a low level register load or counter operation. STG-ROM 4 3404 is used to enable the selection of stacks and counter actions as a function of its address inputs which are enables from ROM's 340l, 3402 and 3403 as well as the current full and empty conditions. For example, the contents of the ROM will disable the counter from decrementing (will not generate the EN (NTR-DOWN signal) if the stack referenced is currently empty even though a pop instruction is being executed which would normally cause the counter to decrement. The coding for these micro-code generator ROM's is given in Appendixes DD-GG.

The computations for the several STG stacks are accomplished using a random access memory (RAM) in conjunction with address counters. In the exemplary STG, data is stored in the stack memory 3501 illustrated in FIG. 35. Data input to the stack memory is taken from the data register. Data output called MEM is used as an input to the STG-MPXR 3303.

At a given instant of time, the address for the stack memory 3501 is formed by a combination of the current counter value and a selection of which of the four stack memory areas are to be used. The stack area selection such as SELECT-MATCH is derived from the address signals A8 and A9 which are generated by micro-code generator ROM's 3403 and 3404.

FIG. 36 illustrates the parts of the stack pointer addressing circuitry which includes the counters for the match, left, right and label stacks. Actually, only one stack address counter 3602 is used in conjunction with a RAM stack pointer memory 3601 in the exemplary STG. This arrangement allows by expansion of the stack pointer memory 3601 the addition of a multiplicity of stacks while having only one stack address counter 3602. The stack pointer memory contains two locations for each stack and the contents of these locations has the format depicted in FIG. 31C and has already been described. Of these two locations, one is called the PTR and indicates the address in the stack memory which currently points to the left or right end of stack data. The other location in the stack pointer memory 3601 for each stack is used for the save value of a pointer for that stack. The LOAD-COUNTER, DOWN-COUNTER and RESET-COUNTER micro-operations are performed for any instruction for which the micro-code generator dictates that these operations are to be executed. The address input to the stack pointer memory 3601 is formed by a combination of the selection of one of the four stacks LEFT, RIGHT, MATCH or LABEL and the selection of PTR or SAVE. This selection is accomplished by the micro-code generator.

FIG. 36 also illustrates FIFO flip-flop 3604 which is used to denote whether the MATCH stack is in LIFO or FIFO mode. The FIFO flip-flop output goes to the micro-code generator and is used to determine the direction of counting for the MATCH stack. For example, if the MATCH stack is in FIFO mode (FIFO flip-flop 3604 is set) then the counter will decrement for a push instruction. This effectively causes reading and writing of the MATCH stack to be accomplished on the same end (memory location) for LIFO mode and opposite ends (different locations) for the FIFO mode.

FIG. 36 also illustrates the LABEL flip-flop 3603 which constitutes a one-bit stack select register. This flip-flop when reset allows selection of the RIGHT stack and allows selection of the LABEL stack when set. This flip-flop may be replaced with a multistage register to allow selection of a multiplicity of stacks.

FIG. 37 illustrates the circuitry which determines the full and empty stack conditions. The FULL-COND flip-flop 3704 is reset using pulse P2 for every instruction. The flip-flop may then be set at pulse P6 if the combinationally defined FULL-DATA signal is active which results from the conditions defined in the illustrated Boolean equations. The EMPTY-COND flip-flop 3705 works in a similar manner. The save register 3701, MPXR 3702 and full/empty comparator 3703 operate together to determine if the present count in the stack address counter 3602 constitutes a full or empty condition. The several cases of this operation are as follows.

Case 1: LEFT, RIGHT or LABEL stack selected and a push instruction is being executed.

In this case, the COMP-WORD signals represent a count of 255 and the comparator 3703 compares this word through the MPXR 3702 with the present counter full. If the two words are equal, then the flip-flop 3703 is set, otherwise the full flip-flop is left reset. In either case, the empty flip-flop is left reset since after a push the stack can not be empty.

Case 2: LEFT, RIGHT or LABEL stack pop instruction.

The COMP-WORD represents a count of 0 in this case and is compared to the current count. If the comparator 3703 finds its inputs are equal, then the empty flip-flop is set, otherwise the empty flip-flop is left reset. The full flip-flop is left reset since a stack can not be full after a pop instruction.

Case 3: MATCH stack with a push instruction.

Operates the same as Case 1.

Case 4: MATCH stack is LIFO mode with a pop instruction.

Operates the same as Case 2.

Case 5: MATCH stack in FIFO mode with a pop instruction.

In this case, the save register is loaded with the right end of stack pointer using a save instruction, and the match pointer is cleared to zero. On subsequent pop instructions, the current save register contents are compared to the current counter and if they are equal, the empty flip-flop is set. This allows the data first into the match stack to be read out first.

For the generalized stack operations which require data in the MATCH stack to be compared to data on the top of another stack, the DATA-COMPARE circuit as illustrated in FIG. 38 is used. This comparator 3801 compares the current output of the stack memory 3501 with the current contents of the data register 3302 and if they are equal, the COMP-COND signal is generated.

The following paragraphs describe each STG instruction in detail.

The STG NOP instruction performs no operation on the data within the STG and consists only of going through the instruction execution cycle. Timing for this instruction is illustrated in FIG. 39A. The basic sequence of operation is as follows: (1) SEM-RQ-STG signal is received, (2) STG-ACTIVE signal is generated, (3) operation code is loaded into the OPCODE register, (4) the eight clock pulses P0, P1, . . . , P7 are generated, and (5) the STG-ACTIVE signal is dropped at the time in which the P7 signal is generated. The NOP instruction is used to verify that the STG can accept and execute instructions for maintenance purposes.

A clear instruction is provided for each stack. The clear instruction resets the pointer value for the stack referenced, resets the FIFO flip-flop, sets the empty condition for that stack and resets the full flip-flop for that stack. Timing for the clear instruction is illustrated in FIG. 39B.

A save instruction is provided for each of the stacks. The action of the save instruction is to (1) load the stack address counter 3602 with the current stack pointer from the stack pointer memory 3601, and (2) store the contents of the stack address counter into the save value part of the stack pointer memory.

In the case that the FIFO flip-flop is set and the MATCH save instruction is executed, the save register 3701 is loaded from the counter. Having saved the current address of the top of a stack, the address may later be restored using the restore instruction effectively returning the stack to the state at the time of the save independent of push and pop instructions which may have been executed in between the save and restore instruction.

A restore pointer instruction is provided for each stack. The restore instructions perform the reverse operation of the save instructions. That is, the save value in the stack pointer memory 3601 is read out and stored back into the stack pointer memory at the PTR value location for the referenced stack. After a restore instruction, operations on a stack will proceed in the same manner as if no instructions had been executed since the last save instruction.

A push data instruction is provided for each of the stacks. The purpose of the push instruction is to add the SEM-DATA word portion of the input instruction to the current string of data in the stack, effectively increasing the length of string by one word. As described previously, the push instruction will perform a NOP if the stack is already full. Timing for a push instruction is illustrated in FIG. 39D. The sequence of micro-operations is as follows: (1) the instruction is accepted and the OPCODE loaded into the OPCODE register 3301, (2) on clock pulse PO, the SEM-DATA portion of the input instruction is loaded into the data register 3302, (3) the full and empty flip-flops 3704 and 3705 are reset by pulse P2, (4) the stack address counter 3602 is loaded with the current stack pointer value using clock pulse P3, (5) the address counter 3602 is incremented using timing pulse P4 and the full condition set if the stack is now full, (6) if the FULL-COND signal is not active, then the data from the data register 3302 is written into the stack memory 3501 at the memory address defined by the stack address counter 3602, and (7) the new stack pointer is written into the stack pointer memory 3601 at the pointer value location associated with the reference stack from the stack address counter 3602 and the STG-ACTIVE flip-flop is reset ending the instruction. For the case of push MATCH instruction is FIFO mode, the operation is similar excepting the counter is decremented instead of being incremented.

A pop instruction is provided for each stack in the STG. The purpose of the pop instruction is to delete a word from the top (current pointer position) of the stack. Timing for the pop instruction is illustrated in FIG. 39B. The sequence of actions is as follows: (1) the instruction is accepted, (2) the full 3704 and empty 3705 flip-flops are reset by pulse P2, (3) the stack address counter 3602 is loaded with the current pointer value from the stack pointer memory 3601 at the time of pulse P3, (4) the stack address counter is decremented using pulse P5, (5) if the stack has now become empty, the empty flip-flop 3705 is set using pulse P6, (6) the new pointer value is written into the stack pointer memory 3601 using time pulse P7. The operation for the case of MATCH stack in FIFO mode is similar with the exception that the counter is incremented.

A pop instruction is provided for each stack in the STG. The purpose of the pop instruction is to delete a word from the top (current pointer position) of the stack. Timing for the pop instruction is illustrated in FIG. 39E. The sequence of actions is as follows: (1) the instruction is accepted, (2) the full 3704 and empty 3705 flip-flops are reset by pulse P2, (3) the stack address counter 3602 is loaded with the current pointer value from the stack pointer memory 3601 at the time of pulse P3, (4) the stack address counter is decremented using pulse P5, (5) if the stack has now become empty, the empty flip-flop 3705 is set using pulse P6, (6) the new pointer value is written into the stack pointer memory 3601 using timing pulse P7. The operation for the case of MATCH stack in FIFO mode is similar with the exception that the counter is incremented.

A length instruction is provided for each stack and allows a one word data output which defines the number of words currently in that stack. The timing is illustrated in FIG. 39F and the sequence of actions is as follows: (1) the instruction is accepted, (2) the stack address counter 3602 is loaded from the stack pointer memory 3601, (3) the stack address counter 3602 content is loaded into the data register 3302.

The reset instruction resets the FIFO 3602 and LABEL 3604 flip-flops as values. The micro-code generator 3403 for this instruction activates the USE-LABEL and FIFO-LIFO signals. Upon the occurrence of pulse P2, the D-type flip-flops are loaded with the logic "0" VALUE signal effecting the reset of the flip-flops.

The load instruction is used to load the SEM-DATA part of the instruction into the data register 3302. This allows an external data word to be compared to the last word read from a stack, the value of which is represented by the MEM signal input to the data comparator 3801.

The FIFO and LIFO instructions are used to set and reset the MFO 3604 flip-flop. Compare Data Instruction

The compare instruction allows the SEM-DATA portion of the instruction to be compared with the top word in the MATCH stack. The timing is illustrated in FIG. 39H. The instruction has the following sequence of operations: (1) the instruction is accepted, (2) the data register 3302 is loaded with the SEM-DATA word part of the input instruction, (3) the MATCH pointer value is loaded into the stack address counter 3602 allowing the top MATCH stack word to be read out of the stack memory 3501, and (4) allowing that word to be compared to the input word through the data comparator 3801.

The use instructions allow the selection of the RIGHT or LABEL stacks for manipulation. For the case of two stacks, two instructions are provided: the USE-RIGHT instruction and the USE-LABEL instruction. The action of these instructions is to reset and set the LABEL 3603 flip-flop respectively.

For a particular implementation, an extra data bit may be provided for the MATCH stack memory. This bit may be written into by the any instruction in a manner similar to the push instruction. On a later compare instruction, the COMP-COND signal will be true independently of the data values if this bit is set. This capability allows masked string comparison.

The push immediate instructions perform the same function as a push instruction with the exception that the current data register 3302 contents are used instead of the SEM-DATA part of the instruction. The push immediate instructions allow a one-word move operation from one stack to another to be accomplished by using a two-instruction sequence consisting of a pop instruction followed by a push immediate instruction.

A read instruction is provided for each stack. The read instruction takes the current top word of a stack from the stack memory 3501 and loads that word into the data register 3302. The full 3704 and empty 3705 flip-flops are set or reset in correspondence with the current status of the stack so that the read instruction may be used as a test for these conditions.

An explanation of the implementation of the generalized (multistack, multicharacter) operation is given in the description of the SEM processor. Devices used to construct the example STG are listed in Appendix HH.

The SEM processor is a control processor which takes instructions from the META and issues a sequence of instructions to the NUM or to the STG or to both. In this manner, a desired operation which is of great complexity is broken down into individual steps which are executable as instructions in the STG or NUM or both. The construction of the SEM as shown in FIG. 29 is similar to the METAPROCESSOR except that a fewer number of self instructions are implemented and there is no compare and classify circuitry. For this reason, only a general description of the SEM is given here.

FIG. 22 is a block diagram of the processor. The elements have the following functions. The data input multiplexer 2201 provides the data movement capability from the various external and internal sources onto a central bus for redistribution. This central bus forms the data portion of the SEM instruction. The data input register 2202 receives the data portion of the META instruction and receives and holds data received from and passed out to other processors. The operation input register 2203 holds the OPCODE received from the META for decoding by the source/destination logic 2204. The source/destination logic 2204 determines if the received code is to be passed directly out as a part of a FORM instruction, or if the code is to initiate a translation sequence. The control logic 2213 and active/request logic 2215 are informed accordingly. The sequence address multiplexer 2205 provides a means for the sequence address counter 2206 to be loaded from the data bus during jumps and subroutine returns; and from the operation input register 2203 during translation sequence preset. The sequence address counter 2206 drives the sequence memory 2207 and may be loaded or counter up. The sequence memory 2207 is used to program translation sequences. Its outputs are divided into two fields, control and data. The control field contains a self-code which, through the control logic 2213 and the micro-code generator 2214, controls all the other components in the processor. The data field contains OPCODES to be passed out as well as sequence addresses for jumps and subroutine calls. The operation out multiplexer 2208 allows loading of the operation out register 2209 from the operation input register 2203 for direct passed codes or from sequence memory 2207 for translation sequence codes. The operation out register 2209 holds the OPCODE portion of SEM instructions. The stack counter 2210 and the stack memory 2211 are used to implement the subroutine function. When a sub-routine is called, the stack counter 2210 is incremented and the stack memory 2211 is loaded from the sequence address counter 2206. On the return, the sequence address counter 2206 is loaded from stack memory 2211 and the stack counter 2210 is decremented. The condition logic 2212 allows the processor to execute conditional sequences based on the condition indicator of other processors. The micro-code generator 2214 decodes the sequence memory self-codes into the necessary signals and timing terms to control the other components in the processor. It also receives inputs from the control logic 2213 and condition logic 2213 which are necessary to complete generation of the component control signals. The control logic 2213 provides overall control of the actions taking place in the processor. When a META request is received, the control logic loads the operation code and data registers and raises the SEM active signal to the META. With the aid of the source/destination logic, the control logic starts a direct pass or a translation sequence depending on the code received. The active/request logic 2215 may be directed by the micro-code generator 2214 or by the source/destination logic 2204. When the SEM passes out an instruction, this logic raises a request to the appropriate processor and holds the request until the processor raises an active signal.

As an example of typical operation of SEM, consider the MOVE operation described in the preceding paragraphs. In particular, take the case of a move from LEFT STACK MEMORY to RIGHT STACK MEMORY of FIG. 21. Previous instructions must have already loaded up the match stack with the match string as shown in FIG. 21. Upon reception of the move-right instruction which is accepted by SEM in the manner already described, instructions are issued from the sequence memory to the STG, causing the values of the LEFT and RIGHT stacks to be saved. Now a move one character left-to-right sequence is issued to the STG. This sequence consists of three instructions: (1) READL, (2) PUSHRI, and (3) POPL, which are sent to STG. During this sequence, the character is compared to the first character in the match stack. If these characters compare as determined by the SEM monitoring the condition line from STG (signal STG-COND) the operation proceeds as described under Step 2 below. Otherwise the operation proceeds as described under Step 1 below.

Step 1: Another move one character sequence is executed by STG by command of the SEM. If the match stack character compares operation continues as under Step 2. If at any point the LEFT stack becomes empty as indicated by the empty condition, then instructions are issued to restore the original stack contents, the SEM-COND signal is generated notifying the META that the operation failed and the SEM-ACTIVE-META signal is dropped.

Step 2: Another move one character sequence is executed and the next match stack character is compared to it. If this comparison is valid, Step 2 is repeated, otherwise Step 1 above is executed. During this step, which uses several instructions for its completion, if the match stack becomes empty, then the proper string has been found. The SEM drops the SEM-ACTIVE-META signal completing the instruction execution in the SEM. The other instructions executable by the SEM proceed in a manner similar to the above discussion. A complete listing of SEM self-instructions is given in Appendix II and the PROM's used to implement the instruction sequences are defined in detail in Appendixes JJ, KK and LL.

The Program Memory Processor (PMEM) is a data processor which provides RAM (Random Access Memory) storage for a program currently being executed and additional RAM storage for a table of specific addressable points in this executing program. This processor also performs addressing functions for both memory arrays. PMEM interfaces with the METAPROCESSOR in that PMEM makes availale the next character to be interpreted when the META indicates that another character is needed.

The Program Memory Processor (PMEM), shown in FIG. 23, comprises an instruction register which is in the nature of an operation input register 2302 and a data input register 2304. The operation code is decoded by a micro-code generator 2303 to determine if the operation code is intended for execution by PMEM and, if this is the case, generates the appropriate "enables" signal to other subunits of PMEM which are required for the execution of that instruction. The control logic circuit 2301 recognizes the META-PROCESSOR's request of PMEM, checks that the operation code sent is valid and provides feedback via the program memory active signal (PMEM-ACT-META) and the condition line (PMEM-CONT-META). In addition, the control logic 2301 provides the sequence of timing control signals to the other subunits of the program memory processor.

The program memory counter 2305 provides the address of the location where the instruction to be executed can be found in the PMEM memory array 2306. If the program memory counter 2305 at any time generates a count greater than the size of the memory array (indicating that the processor is trying to locate instructions that do not exist), PMEN notifies the META of this condition via the program memory error (PMEM ERROR) line. If a specific program memory address is to be stored for later reference, then it is stored in the PMEM stack memory 2308. The stack memory 2308 is employed as a first-in, first-out (or a "push-down") memory device where the address of the next possible storage location (for the stack memory) is kept in the stack counter 2307. Thus, if a program memory address is to be saved, it is stored in the stack memory at the current address value found in the stack counter. The stack counter contents are incremented so that the stack will hold the address of the location when the next program memory address is to be stored. Only the last saved program memory address or the "top of the stack" is in the stack memory, that is, the "last-one" stored, can be referenced. In this case, the contents of the stack counter are decremented and the program memory address which is stored at the location referenced by the contents of the stack counter is placed in the program counter. The decrementing of the stack counter uncovers a new "top of the stack" or "last-one" stored program memory address. If PMEM attempts to save more program memory addresses in the PMEM stack memory than there is available area, the stack counter notifies META via the program memory overflow (PMEM OVERFLOW) line. Likewise, if the processor attempts the recall more program memory addresses than were stored in PMEM stack memory, META is signaled of this condition via the program memory end line (PMEM-END).

The data input register 2304 contains any data that may be required for a specific operation code. There are two types of information which the data input register would contain: (1) addresses to be loaded into either the program memory 2305 or the stack counter 2307 and (2) data to be stored in the PMEM memory array, that is loading PMEM memory array with a set of instructions of a lesson plan which will shortly be executed. The data output multiplexer 2309 provides a means of accessing the outputs of several subunits of the processor. In typical operation, the data output multiplexer gates the output of the PMEM memory array 2306 (which is the next instruction to be executed) and places this information of the program memory data output line (PMEM-DATA) so that the information is available to other processors. However, for maintenance work, the content value of the stack counter 2307, the program memory address stored at the specific location in PMEM stack memory 2308 or the current value of the program memory counter 2305 can be switched onto the program memory data lines.

The PMEM operations are straight forward. Instructions such as load program memory counter, save program memory counter or read program memory are typical. The normal sequence for loading in the next lesson portion to be executed is to initialize the program memory counter 2305, then load into the program memory array 2306 data in the data input register 2304, increment the program memory counter 2305, and do another load into program memory 2306. This sequence continues until the PMEM-ERROR lines are activated, at which time the program memory counter is again initialized. Now PMEM is requested to read the program memory array, so that execution of this new lesson can begin.

For sequencing through a set of characters a number of times, first a designated program memory counter value is stored, in the stack memory 2308 and then recalled later. A typical sequence of instructions for this looping would be first to load to stack memory 2308 with the value from the program memory counter 2305, and then increment the stack counter 2307. The program memory counter 2305 is incremented and execution then continues until the end of the set of instructions in the lesson has been reached. If that sequence is to be repeated, then the stack counter is decremented and the value found in stack memory 2308 at that location is pushed into the program memory counter 2305, and the stack counter 2308 is again incremented. The character located in PMEM memory array 2306 addressed by the new value of the program counter is the next character of the lesson to be executed. If that sequence of instructions is not to be executed again, then the stack counter 2307 is decremented. The implementation of PMEM is identical to the SYM processor described later in greater detail and this detailed description is not repeated here.

The METAPROCESSOR (META) shown in FIG. 24 is a control processor (CP) which stores the grammar of the programming language used with the training system and performs the interpretation of the lesson program stored in the program memory processor (PMEM). As the principal control processor of the program execution subsystem, the META receives control arc inputs from the inputs processing subsystem and sends control arcs to the mass data transfer subsystem, the PMEM, and SEM.

The META receives a control arc from the OIU processor and sends control arcs to the PMEM, semantics processor (SEM), and the format processor (FORM). The META receives data from the OIU, PMEM, SEM, and FORM processors and sends data to the FORM, PMEM, and SEM.

FIG. 24 further shows the control logic 2401 which directs all of the activity of the META. The control logic operates the control interface with the OIU processor, controls the request/active logic 2406 and generates timing for other logic in the META, based on input signals from the source/destination detector 2403, the condition logic 2415 and the micro-code generator 2405.

The operation code register 2402 is used to hold the OPCODE portion of the INPT instruction when the META goes active, and is also used to hold the OPCODE portion of the META instruction sent to the FORM, SEM and PMEM. The operation code register 2402 is loaded through the META multiplexer 2404 from either the INPT instruction or the sequence random access memory (sequence RAM) 2408. The contents of the operation code register 2402 are decoded by the source/destination detector 2403, which for input OPCODES (OIU) classifies them into direct and sequence OPCODE classes, and for both input and output OPCODES (from sequence RAM 2408) determines the proper destination of the OPCODE, whether PMEM, SEM, FORM or self (META). Input OPCODES in the direct class are those which are to be passed directly through the META to the PMEM, SEM or FORM processor. Input OPCODES in the sequence class are those which are executed by the META. All output OPCODES are in the direct class. The source/destination ROM 2403 provides direct/sequence class information to the control logic 2401, and provides destination information to the request/active logic 2406.

The request/active logic 2406 controls the control interface request and active lines to the PMEM, SEM and FORM under the direction of the control logic 2401 and the source/destination ROM 2403.

The META multiplexer 2404 selects the data source for the META data bus. The multiplexer inputs include the OIU instruction, PMEM data, SEM data, FORM data, the stack memory 2410, the sequence counter 2407, the octal converter 2412, and the META data register 2411. The META data bus in turn supplies data to the operation input register 2402, the stack memory 2410, the sequence counter 2407, the octal converter 2412, the META data register 2411, the sequence RAM 2408, the class memory 2413, the comparator 2414, and four other processors as explained above. Mutiplexer 2404 selection is provided by the control logic 2401.

The sequence counter 2407 provides an address for the sequence RAM 2408. The sequence counter 2407 can be loaded through the META multiplexer 2404 from the sequence RAM 2408 for implementing jump or all self-codes (see below) and from the stack memory 2410 for implementing return self-codes. The counter 2407 is normally incremented when the META is running through a sequence from sequence RAM 2408.

The sequence RAM 2408 is used to store self-code sequences which define the grammar used to interpret lesson programs in PMEM. The sequence RAM 2408 is addressed by the sequence counter 2407, can be loaded from a data source through the META multiplexer 2404, and supplies self-codes to the micro-code generator 2405 and sequence data to the META multiplexer 2404, the class memory 2413 and the condition logic 2415. The self-codes define the operations that are performed at each step in a sequence in the memory 2408.

The sequence data is used as a data source or as a self-code modification field.

The micro-code generator 2405 decodes the self-code from the sequence RAM 2408 into enable signals for the control logic 2401. These enable signals direct the action of the timing signals provided by the control logic 2401.

The META data register 2411 is used to store input data from the META multiplexer 2404. A common usage is that of holding PMEM-DATA characters for processing.

The stack counter 2409 and the stack memory 2410 form an address stack for use with the call, push and return self-codes (explained below). The stack memory 2410 is a random access memory (RAM) addressed by the stack counter 2409, and which can be written into from the sequence counter 2407 for call self-codes, and from the sequence RAM for push self-codes. The stack memory 2410 output can be loaded into the sequence counter 2407 for return self-codes. The stack counter 2407 can be incremented and decremented to provide the push and pop stack operations.

The octal converter 2412 can convert three ASCII octal characters into one 8-bit data word, and can reverse the process, using the META multiplexer 2404 to select both the source and the destination of the conversion.

The class memory 2413 is used to classify characters on the META-DATA but into different classes, such as a digit or a capital letter, with the class specified by the sequence data from sequence RAM 2408. This class memory 2413 is a read only memory (ROM) which is addressed by the META-DATA bus and sequence data from the sequence RAM 2408. The ROM 2413 contains the character class definitions. An output of the class memory 2413 called class goes to the condition logic 2415.

The comparator 2414 is a combinatorial logic circuit which makes a numerical equal comparison between the META data register 2411 contents and a data source selected by the META multiplexer 2404. The result of this comparison is sent to the condition logic 2415.

The condition logic 2415 selects a particular condition from the set of external conditions, SEM-COND, FORM-COND and PMEM-COND, and internal conditions, class memory 2413, comparator 2414, and settable flags within the condition logic 2415, to send a net condition true signal to the control logic 2401. The condition selected is specified by the sequence data from the sequence RAM 2408. The control logic 2401 uses the condition signal input to determine the resulting actions for conditional skip self-codes, and to set the META-COND-INPT line.

The general operation of the METAPROCESSOR is as follows. Starting from the quiescent state in which the META is not active, the presence of INPT-RQ-META causes the control logic 2401 to emit timing signals which load the operation code register 2402 with the INPT instruction, load the META data register 2411 with DL-1-DATA, and subsequently to raise the META-ACT-INPT signal. The OPCODE is then divided into the direct or sequence class by the source/destination logic 2403. For direct OPCODES, the OPCODE is passed out to either the PMEM, SEM or FORM processor depending on the destination code, by the request/active logic 2406, and then the META active line is lowered and the META returns to the quiescent state. For sequence OPCODES, the source/destination logic 2403 further divides the input OPCODE into run, or load OPCODES. The lead OPCODE causes the writing of the sequence RAM 2408 from the just loaded contents of the META data register 2411. This OPCODE is used to store a new lesson grammar sequence into the sequence RAM 2408 and is used for initial system bootstrap. The run OPCODE is issued from the INPT processor with operator input data, and causes the initiation of self-code execution from the sequence RAM 2408 without modifying the sequence counter 2407 value.

Self-codes are decoded by the micro-code generator 2405 which feeds enable signals to the control logic 2401 which in turn directs the self-code execution. Execution of self-codes continues until the half self-code is executed, which causes the META active to lower and returns the META to the quiescent state.

There are ten classes of META self-codes: pass, load, jump, call, return, push, skip, set flag, convert and halt. Except for jump, call and return, each self-code causes the sequence counter to increment by one so that self-codes are executed sequentially. The pass self-code causes the sequence data from the sequence RAM 2408 to be loaded into the operation code register 2402, and that OPCODE to be passed out to the PMEM, SEM or FORM by the request/active logic 2406. The load self-code causes the META data register 2411 to be loaded from a data source specified by the sequence data which in this case selects the META multiplexer 2404 directly. The jump self-code causes the sequence data to be loaded into the sequence counter 2407 and the next self-code will be read from the sequence RAM 2408 at that location.

The call self-code causes the stack counter 2409 to be incremented, the sequence counter 2407 contents plus one to be stored in the stack memory 2410, and then the sequence data is loaded into the sequence counter 2407. The old sequence counter 2407 value is saved in the stack memory 2410. The return self-code causes the stack memory 2410 contents to be loaded back into the sequence counter 2407, returning the counter to its saved value, and then decrements the stack counter 2409. The push self-code causes the stack counter 2409 to be incremented and the sequence data to be stored in the stack memory 2410. The skip self-code causes the next self-code in sequence RAM 2408 to be skipped over if a condition specified by the sequence data is satisfied. The skip action is achieved by double incrementing the sequence counter 2407. The convert self-codes cause the octal converter 2412 to perform the desired conversion operation. Finally, the halt self-code causes the META active to lower and returns the META to the quiescent state.

These self-codes combined with appropriate sequence data make up the "program" which runs in the META upon its receipt of a run OPCODE. This sequence RAM 2408 "program" defines the lesson grammar used for interpreting PMEM lesson programs and INPT inputs. The following paragraphs describe the detailed implementation of an exemplary METAPROCESSOR.

FIG. 40 illustrates the interfaces between a METAPROCESSOR 4002 with other elements in a typical system such as in the exemplary training system and output interface units 4001 and subordinate processing elements such as the FORM processor 4003, program memory processor 4004 and semantics processor 4005. The signal interfaces between these processing elements as shown on the FIGURE are basically a set of signals defined previously as control arc between the processing element in a network. For example, the connection between the OIU 4001 and METAPROCESSOR 4002 constitute a control arc input to the METAPROCESSOR. In a similar manner, the signals interchanged between the METAPROCESSOR and the FORM processor 4003 constitute a control arc output from META to FORM. Similarly, the signals to the PMEM constitute a control arc output from META, and similarly the signals between the META and the SEM 4005 constitute a control arc from META to SEM. These are the signals required in an exemplary system using the METAPROCESSOR for communication. In a different application, the METAPROCESSOR may have control arc outputs to more than the three processors illustrated in FIG. 40 or may have control arc outputs to only one processing element besides the META but in any case requires the control arc output to at least one other processing element to a system and a control arc input from at least one other control processor in the system for a useful application of the METAPROCESSOR.

FIG. 41A illustrates the format of instruction accepted by a METAPROCESSOR from the OIU. The instruction input which flows over the control arc input lines is a 16-bit word consisting of two parts. In the first part, the bits labeled 8, 9, etc., through 15 constitute the 8-bit OPCODE from the OIU. In the second case, the bits labeled 0, 1 through 7 constitute the data portion of the OIU input instruction. This 16-bit word is received and loaded into the OPCODE and DATA input registers in the METAPROCESSOR during the instruction acceptance cycle that has been described previously. To initiate the actions of operations in subordinate processing elements, the METAPROCESSOR generates output instructions over an output control arc. The format of an output instruction is similar to the input instruction format and is illustrated in FIG. 41B. The output instruction consists of two fields, the upper 8-bits of which are the META-OP-CODE output and the lower 8-bits of which are the META-DATA output. Internal to the METAPROCESSOR, the control logic and the sequence logic within a METAPROCESSOR operate by way of executing a sequence of instructions which are called self instructions. To implement a particular grammar and thus to be able to interpret a high level language, a programmer develops such a sequence of self instructions which in the exemplary METAPROCESSOR case has 16 major instruction types. The format of these self instructions is illustrated in FIG. 41C. In this case, a 16-bit word is used and stored in a sequence memory for read out and subsequent execution internally to the METAPROCESSOR. The self instruction, however, uses only 14 bits of the 16-bit word. Of these 14 bits, the lower 8 bits are referred to as the OPERAND portion of the instruction. The next 2 bits are called the TAG portion of the instruction and finally the upper 4 bits are referred to as the SELF-OPCODE. The SELF-OPCODE selects one of the sixteen major instruction types, each of these instruction types may be modified for execution by the two-bit TAG portion and finally the OPERAND portion of the instruction supplies meaningful information used for particular SELF-OPCODES. For example, in different SELF-OPCODE cases, the OPERAND is used as data to be sent out as a data portion of an instruction or as an operation code to be sent out as a META-OPCODE of an instruction or as a multiplexer address to be used when reading data into the METAPROCESSOR and several other applications to be illustrated in the following paragraphs. Within the METAPROCESSOR, data is transferred between several logic devices in the form of 8-bit data words as illustrated in FIG. 41D. In the following paragraphs, the detailed implementation of each of the circuit blocks illustrated previously on the METAPROCESSOR block diagram is described in detail. Devices used to implement an example META are listed in Appendix BB.

FIG. 42 illustrates an exemplary implementation of the control logic portion of the METAPROCESSOR. The control logic as described previously consists of the preset and active flip-flops which are necessary in the sequence of events in accepting instructions and also of the flip-flops called STATE1 4219 and STATE2 4220 which are used for generating the clock pulses necessary for the execution of self instructions. The two flip-flops STATE1 and STATE2 in fact constitute a two-bit counter which drives the phase decode element 4221. In combination with a certain setting of the STATE1 and STATE2 flip-flops and the occurrence of a META clock pulse, this causes the generation of four clock pulses called P1, P2, P3 and P4 which occur in that order. For a complete operation of the METAPROCESSOR, each execution of a self instruction requires the sequence P1, P2, P3 and P4 and then on the next instruction read out of the sequence memory that sequence of signals is generated again. Thus, the METAPROCESSOR sequentially generates these clock pulses in a cyclic manner until such time as the HALT self instruction is executed which generates the end of sequence signal and thus causes the ACTIVE flip-flop 4204 to be reset. The master reset signal causes inverter element 4207 to be activated which resets the PRESET and ACTIVE flip-flops 4203, 4204 and thus puts the METAPROCESSOR in a state in which it can accept instructions. This master reset function is performed by external push button on other device to allow use of the METAPROCESSOR for useful processing of data. Normally, the master reset signal is generated during the sequence of operations for turning on the power to an equipment using a METAPROCESSOR. When the META-ACTIVE signal is low, that is the META-ACTIVE flip-flop is reset, this signal causes the STATE1 and STATE2 flip-flops to be in a set state and remain in that set state so that only the pulse P1 is generated. This keeps the self instructions from being executed when the METAPROCESSOR is not active. After the METAPROCESSOR becomes active upon the reception of instruction, the STATE1 and STATE2 flip-flops are allowed to set and reset as a function of its input signals and thus generate the clock phases so its self instructions can be executed.

FIG. 43 illustrates an exemplary implementation of the multiplexer B and data register within the METAPROCESSOR. The circuit consists of a read-only memory device 4301 (defined in detail in Appendix R), a multiplexer device 4302 and a data register 4303. The address read-only memory 4301 has inputs from STATE flip-flops, the TAG portion of the instruction, the SELF-OP portion of instruction currently being executed so that it can define the appropriate address for the B multiplexer as a function of the position and time of execution of an instruction and the data requirements for that instruction. The B multiplexer 4302 has inputs from external data, from the program memory processor, the FORM processor, the SEM processor, and the OIU processor. In addition, the B multiplexer has inputs from internal data registers within the METAPROCESSOR constituting of the link register, an input from the C multiplexer portion of the METAPROCESSOR and an input from the stack memory. The B multiplexer output is used as the META-DATA which is used internal to the METAPROCESSOR and also is used as the META-DATA portion of instruction being sent out of the METAPROCESSOR. When loaded into the data register 4303, the data may be read back to the B multiplexer 4302. When the METAPROCESSOR is not active, the read-only memory 4301 which has STATE inputs STATE1 and STATE2 causes the B multiplexer to have on its output lines the current value in the data register. In this manner, with the METAPROCESSOR inactive, the current data in the data register is accessible by other processors in the system.

FIG. 44 illustrates an exemplary implementation of the control arc output generation logic. This logic consists of the destination decode element 4402 and flip-flops 4404 active now, the active up flip-flop 4405 and the active flip-flop 4406. In addition, the circuit uses the active multiplexer 4403 to allow the reception of the proper active signal from a processing element for which the METAPROCESSOR requires data instruction execution. The address for the decoder which selects the proper request line and the active multiplexer address input is supplied by the destination read-out memory 4401 (defined in Appendix U). The destination read-only memory has as its address input the METAOPCODE signals which are to be sent out as part of the instruction. The destination read-only memory is programmed in such a manner than an instruction intended for a particular processing element external to the METAPROCESSOR is denoted by a special code of the address lines. Thus, for example, the OPCODES sent out by the METAPROCESSOR are unique for each of the processing elements to receive those instructions. In this manner, a simple mapping by way of the destination read-only memory allows selection of the proper output processing element without the self instruction having to define completely which processing element the instruction is to be sent. The programming of the destination read-only memory 4401 in the exemplary implementation of the METAPROCESSOR is given in Appendix U. The detailed description of the operation of this circuit for generating and controlling the sending out of instructions to a processing element over a control arc has already been described.

FIG. 45 illustrates a sequence random access memory in which the sequences of self instructions are stored in the METAPROCESSOR as well as the address generation circuitry for that sequence address memory. The elements of this circuit consists of multiplexer C4502 which is used to determine the proper addresses for the sequence counter 4505 for subsequent use in defining the location for the use of the self instruction in the sequence random access memory 4506. The read-only memory 4501 (defined in Appendix S) is used in a manner similar to that described in the B multiplexer for defining the address input the STATE1 and STATE2 flip-flop signals as well as the TAG and SELF-OPCODE signals. This circuit includes the META-OPCODE register. This register is common for use both as the receiver of data of the OPCODE portion of input instruction as well as being used for generating the OPCODE output/part of instruction to a processing element to receive an instruction. During the execution of the self instructions within the METAPROCESSOR, the two portions of a self instruction consisting of the SELF/OPCODE and the OPERAND and TAG portions are loaded respectively into the SELF-OPCODE register 4507 and the OPERAND register 4508. The SELF-OPCODE register 4507 in addition may be loaded by the source code read-only memory 4504 (defined in Appendix T). This source code read-only memory upon the initial acceptance of instruction by the METAPROCESSOR performs a mapping from the OPCODE portion of the instruction accepted to a SELF-OPCODE to be executed by the METAPROCESSOR. Thus, an external instruction may cause the METAPROCESSOR to execute any one of the sixteen possible self instructions. In typical cases, the source code read-only memory may require the SELF-OPCODE to be a direct instruction. In this case, the input instruction is sent out to some other processing element in the network in a manner described previously and upon the completion of sending out that instruction, the METAPROCESSOR becomes inactive. In a second case, the multiplexer register, the SELF-OPCODE register 4507 may be loaded with a JUMP instruction from the source code read-only memory as a function of the OPCODE input now stored in register 4503. In this case, the JUMP address as defined by the actual OPCODE value will be put into the sequence counter and thus define the initial position in the sequence random access memory 4506 for initial execution of that instruction. In this manner, a multiplicity of instructions can be accepted by the METAPROCESSOR, each of which accesses a different portion of a sequence address, sequence random access memory and thus allows selection of different sequences for execution by the METAPROCESSOR. In a third case, the sequence counter 4504 is allowed to retain its current value when the METAPROCESSOR becomes inactive. If now an input instruction is received by the METAPROCESSOR, such that the source code read-only memory 4504 calls for a no operation within the multiplexer register 4507 or SELF-OPCODE register, then the current value of the sequence counter is used causing the continuation of operation within the METAPROCESSOR from the position where it left off when it became inactive from a previous operation. In this manner, the METAPROCESSOR may perform the STATE defined control operations, i.e., the METAPROCESSOR executes a sequence of self instructions as defined in the sequence random access memory as a function of the state that it was in when the instruction was first received and the data which was received with that instruction. The determination of what further actions are to be taken is determined by the sequence of self-instructions in the sequence random access memory 4506 and the data value received with the input instructions.

FIG. 46 illustrates an exemplary implementation of the address stack for the METAPROCESSOR. The address stack is used for storing address return values as well as the execution of primitive operations in the high level grammar that require the pushing of addresses on a stack until such time as POP (or RETURN) operations are performed at which time those addresses are loaded into the sequence counter and subsequently the sequence is executed. The address stack for the METAPROCESSOR is composed of two components, the stack counter 4601 and the stack random access memory 4602. The stack random access memory allows the storage of a multiplicity of addresses. The stack counter 4601 allows the selection of the proper address within the stack random access memory at a given point in time. Two basic operations are defined for the stack address operations. These are the PUSH operation and the POP operation. The PUSH operation works as follows: the current META-DATA value is written into the location of the STACK RANDOM ACCESS MEMORY 4602 at the location currently defined by the value in the STACK COUNTER. The STACK COUNTER is now incremented. The POP operation works in the reverse. The stack is first decremented, by a count of one allowing access to an address previously written into the STACK RANDOM ACCESS MEMORY. The execution of several POP operations would be the subsequent use of those addresses for executing a sequence of operations within the METAPROCESSOR involved in the execution of a sequence of overall operation, each operation of which consists of a sequence of self instructions as defined by the addresses in the STACK RANDOM ACCESS MEMORY.

FIG. 47 illustrates an exemplary implementation of the micro-code generation logic of a METAPROCESSOR. In this example, five read only memories labeled METAROM-1, METAROM-2, etc., are used to decode the SELF-OPCODE portions of the SELF instruction. The programming of these ROM's are defined in Appendixes V, W, X, Y and Z. In addition, METAROM-5 4701 which is called the microinstruction generation ROM receives its inputs from the operand portion of a self instruction and is enabled by the MICRO signal from METAROM-4, 4704. In this manner, the SELF-OPCODE is translated by the contents of these read only memories into a set of functions out of the total possible set of functions illustrated by the outputs of the METAROMS. For each SELF instruction, only a subset of all these functions are performed. In this manner, a SELF instruction allows the execution of individual micro operations such as loading registers and controlling the position of multiplexers. The METAROM-5 because it has address input from the OPERAND portion of the SELF instruction allows expansion of the repertoire of the SELF instructions of the METAPROCESSOR, that is the single SELF-OPCODE if it selects the micro option will use the OPERAND portion of that instruction as a further operation code to define individual discrete operations to be performed within the METAPROCESSOR. The various enable signals from the METAROM's are used in conjunction with the P1, P2, P3 and P4 clock pulses to execute individual micro operations for a self instruction.

FIG. 48 illustrates an exemplary implementation of the classify and compare circuitry of the METAPROCESSOR. This circuitry performs the operations within certain self instructions for comparing data and comparing data to a subset called a class of data. These instructions allow conditional operation of sequences of instructions within the METAPROCESSOR. The circuit consists of three elements respectively a DATA COMPARATOR 4101 whose output signal data compare is a high value only when the OPERAND portion of a self instruction is equal to the contents of the METADATA register. The element CLASS ROM 4802 (defined in Appendix AA) has input from the METADATA register. This read only memory is programmed in such a manner that the output of the read only memory discretely defines on a true and false logic level basis whether the data input to the read only memory is one of the multiplicity of sets called classes. The CLASS MULTIPLEXER 4803 which has address inputs from the OPERAND portion of the instruction is then allowed to select one of the line outputs of the CLASS READ ONLY MEMORY. In this manner, the output of the CLASS MULTIPLEXER called the CLASS COMPARE SIGNAL is a high value only if the data input to the CLASS READ ONLY MEMORY 4802 is in a set of words selected by the OPERAND portion of the self instruction.

FIG. 49 illustrates exemplary implementation of the condition logic of the METAPROCESSOR. The logic consists of a CONDITION MULTIPLEXER 4901 whose address input is in the OPERAND portion of a self instruction and the METACONDITION flip-flop 4902. The METACONDITION flip-flop is a data-one-bit data word which can be set or reset by self instructions in the METAPROCESSOR when monitored sometime later by a self instruction. This allows the METAPROCESSOR to determine the order of sequence of execution of instructions in the sequence memory. The CONDITION MULTIPLEXER has inputs both from internal to the METAPROCESSOR, such as the METACONDITION signal and conditions external to the METAPROCESSOR, such as the condition line inputs from the subprocessors SEM, FORM, and PMEM. By monitoring these conditions, the METAPROCESSOR can determine a reordering of the sequence of execution of instructions in the sequence memory.

FIG. 50 illustrates an exemplary implementation of the link register in the METAPROCESSOR. The link register is configured in such a manner that three consecutive data word inputs can be used to convert to a single byte word, that is the lower three bits three consecutive words are stripped off and compacted into one single eight-bit word. This is called a conversion of a character string to an octal number. In a similar manner, a single eight-bit word can be converted to three consecutive characters, each of which represents one digit of a three-character octal number. For this reason, the circuit is called on octal conversion circuit. The circuit itself consists of three registers called LINK0 5001, LINK1 5002 and LINK2 5003. Each of these registers is responsible to each point in time for holding three bits worth of information corresponding to three bits of an eight-bit word or three bits of the input character string. The operation of this circuit is as follows: the LOAD-LINK signal occurs in conjunction with a SELECT NUM signal in such a manner that the lower three bits of the character are loaded into the LINK0 register. Upon the next LOAD-LINK signal the contents currently in the LINK0 register 5001 are loaded into the LINK1 register 5002. On this same pulse, the lower three bits of the new data word are loaded into LINK0 register. On the next LOAD-LINK pulse the contents of LINK1 are put into the LINK2 register 5003. The contents of LINK0 are put into LINK1 register and the data input lower three bits are put into the LINK0 register. In this manner, the lower three bits of three consecutive data words are loaded as one eight-bit quantity in the LINK register. In a similar manner, the LOAD-LINK signal can allow the loading of all eight bits of the META-DATA information. Now subsequent LOAD-LINK signals with the SELECT-NUM signal in the opposite position allows the readout of consecutive three-bit quantities from the LINK register. The following is now a detailed description of the execution of each of the self instructions in the METAPROCESSOR.

The self instructions of the METAPROCESSOR (which are summarized in Appendix L) are now described in detail. Two cases must be discussed. In the first case, the operation of the METAPROCESSOR for instructions accepted from the OIU and in the second case, the execution instructions in the METAPROCESSOR during the execution of a sequence from the RANDOM ACCESS MEMORY. Instructions executed by the METAPROCESSOR are the same in two cases; however, the timing is slightly different.

Instructions executed by the METAPROCESSOR from the OIU fall into three categories. In the first category are the instructions load sequence high and load sequence low which are used to load the SEQUENCE RANDOM ACCESS MEMORY. In the second case are direct instructions for which the METAPROCESSOR simply takes the input instruction and then generates the same instruction on the output arc for a subordinate processor. In the third case are run instructions for the METAPROCESSOR which initiate the execution of a sequence in the SEQUENCE RANDOM ACCESS MEMORY, either from a new state point as defined in the sequence counter 4505 or from the current state. The LOAD-LO instruction is executed by the METAPROCESSOR upon the reception of instruction from the OIU with operation code 372. The purpose of this instruction is to take the data portion of the output instruction loaded into the lower eight bits of the current location in the SEQUENCE RANDOM ACCESS MEMORY defined by the sequence counter 4505. After completion of the instruction, the METAPROCESSOR becomes inactive and awaits the reception of a new instruction. The sequence of operations in the METAPROCESSOR for the load sequence low instruction is illustrated in FIG. 51B which shows the request signal from the OIU to the METAPROCESSOR and the response to that request signal by the METAPROCESSOR by way of the METAPRESET signal and then subsequently the generation of the active signal. During the preset time, the META-OPCODE register 4503 is loaded and the DATA REGISTER 4303 is loaded with the data input part of the instruction. The data flow to the data register 4303 is as follows: the B multiplexer 4302 is steered to the OIU data location by the multiplexer address ROM 4301 because the METAPROCESSOR is currently in STATE1 and STATE2. The SELF-OP register 4507 is loaded from the source code read only memory 4504 with the load sequence low SELF-OPCODE as a translation of the OPCODE in the META-OPCODE register 4503. That is the source code ROM 4304 is programmed to generate the load-sequence-low SELF-OPCODE with the OPCODE received from the OIU as the 372 OPCODE.

After the METAPROCESSOR becomes active, the P1, P2, P3 and P4 pulses are generated as illustrated in FIG. 51B. The generation of these pulses as described before is accomplished by the STATE1 and STATE2 flip-flops in combination with the phase decode device 4221. During the time that the STATE2 flip-flop is set, the load sequence low signal as shown in FIG. 51B is generated which allows the loading of the SEQUENCE RANDOM ACCESS MEMORy from the data through the C multiplexer 4502 which is steered to read the META-DATA register by the C multiplexer read only memory 4501. This accomplishes the loading of the lower eight bits of the word location in the SEQUENCE RANDOM ACCESS MEMORY 4506 at the current location defined by the sequence counter 4505. After leading the SEQUENCE RANDOM ACCESS MEMORY with the input data, the META-ACTIVE flip-flop 4204 is reset because the end of sequence signal 4214 is generated as a result of the halt enable signal from META ROM 4701 being active for this particular SELF-OPCODE. The METAPROCESSOR now waits in a quiescent state for the arrival of a new instruction from the OIU. This new instruction from the OIU may in the current case be a load-sequence-high instruction OPCODE 373. The operation for this instruction is similar to the load sequence low instruction except that in addition on pulse P3 the sequence counter 4505 is incremented by the UP-SEQUENCE COUNTER signal which is generated because of the LDSEQCTR signal from METAROM-2 4702 which is enabled for this particular SELF-OPCODE. By performing a sequence alternately of load sequence low and low sequence high instructions, the OIU is allowed to load up completely the contents of the SEQUENCE RANDOM ACCESS MEMORY.

The second case for the METAPROCESSOR executing instructions from the OIU is the case of what is called passing direct instructions. For example, the OIU can load the program memory by way of sending a load PMEM instruction to the METAPROCESSOR along with data to be loaded into the program memory. In this case, the instruction is accepted as described before by loading the META-OPCODE register 4503 and the METADATA register 4303 during the preset flip-flop time. The timing for this operation is illustrated in FIG. 51A. As shown, the instruction is accepted and then the META-ACTIVE signal is generated. The input OPCODE which is now loaded in the META-OPCODE register 4503 is now presented to the source code ROM 4504 which allows the SELF-OPCODE register 4507 to be loaded up with the direct SELF-OPCODE which is SELF-OPCODE No. 01. Since the SELF-OPCODE is a direct OPCODE and the preset flip-flop is still set, the instruction is sent out to the program memory through the control arc transmit logic as described in previous cases. Upon reception of the active signal from the program memory, the METAPROCESSOR is now allowed to become inactive by resetting the active flip-flop. By generating a sequence of these instructions to the METAPROCESSOR from the OIU processor, the PMEM processor now can be loaded with a program to be executed by the METAPROCESSOR. In this case, the METAPROCESSOR acts simply as a data path for the instructions meant for the program memory. This device is very useful to allow the generation of instructions to processing elements which have no direct control arc connection to an originating control processor. For example, in this case, the OIU could have a control arc directly to the program memory but since the OIU already has a control arc connection to the METAPROCESSOR, the overall network design is simplified by sending instructions first to the METAPROCESSOR and then having the METAPROCESSOR send those instructions onto a program memory processor. The METAPROCESSOR itself does not change the value of its internal state or the value of any data in its registers and SEQUENCE RANDOM ACCESS MEMORY as a result of executing such direct instructions.

The third case of instructions executed by the METAPROCESSOR from the OIU processor is the case of the RUN instruction OPCODE 370. This instruction is accepted as described previously but results in a NOP SELF-CODE No. 00 being loaded in the SELF-OPCODE register 4507 as determined by the output of the source code ROM 4504 which monitors the value of the OPCODES in the META-OPCODE REGISTER 4503. Since the SELF-OPCODE is a NOP, no operation is performed for the initial instruction; however, the META-ACTIVE flip-flop is not reset at the end of this instruction. As a result, the next instruction in the SEQUENCE RANDOM ACCESS MEMORY 4506 at the location defined by the current value of the sequence counter 4505 is executed. This new self instruction now allows the METAPROCESSOR to execute a sequence of operations defined by sequentially accessing self instructions from the SEQUENCE RANDOM ACCESS MEMORY as a function of differing address generated from the sequence counter. In this manner, the METAPROCESSOR is allowed to execute sequences as a function of its current state saved in the sequence counter 4505 and the new instruction data inputs. This then is an exemplary illustration of the use of the state defined control concept described previously. Timing for the ROM META-OPERATION is illustrated in FIGURE 51C which shows the reception of the request signal from the OIU processor, the generation of the META-PRESET time, the generation of the META-ACTIVE signal after loading the instruction to the OPCODE and data registers and then the issuance of the pulses P1, P2, P3 and P4 which perform no operation for this initial cycle. However, after the issuance of pulse P4, operation of the METAPROCESSOR continues by again generating pulse P1 and on this new self instruction SEQUENCE RANDOM ACCESS MEMORY will perform yet another self instruction and this self instruction may be followed by again another self instruction as defined by varying locations defined in the sequence counter 4505. The cases of the METAPROCESSOR executing self instructions after having been initiated for running a sequence is now described. In the first case, the self instruction may have the SELF-OPCODE 00 which requires the METAPROCESSOR to execute a NOP instruction. This instruction performs no useful function during the execution of a sequence within the METAPROCESSOR and is used principally for initiating the running of the METAPROCESSOR by instruction from the OIU processor.

The METAPROCESSOR may execute a direct instruction OPCODE 01 if the self code register 4507 is loaded in the SELF-OPCODE for doing the direct function. In this case, the least significant tag bit is used to define whether the METAPROCESSOR will wait for the completion of the execution of the direct instruction or will continue the sequence of operation at the reception of the active signal from the processor to which the instruction is being sent. The instruction sent out by the METAPROCESSOR consists of the current contents of the META-OPCODE register and the current contents of the META-DATA register. Timing for this self instruction is to allow the program being read from the program memory processor to define operation codes and instructions to be sent out to other processors in the system. This is done by the METAPROCESSOR reading data from the program memory and then loading that data into the META-OPCODE register by the load P instruction which will be described in subsequent paragraphs.

The METAPROCESSOR will execute the PASS self instruction if the OPCODE loaded into the SELF-OPCODE register 4507 is the OPCODE 02. This case is similar to the direct instruction PASS operation except that the META-OPCODE register 4503 is loaded with the OPERAND portion of the self instruction from the SEQUENCE RANDOM ACCESS MEMORY 4506. The data flow in this case is to take the OPERAND from the OPERAND register 4508 which is loaded on pulse P1 and take the output of that OPERAND register through the C multiplexer which is steered by the C multiplexer ROM and then load the META-OPCODE register on pulse P2 as illustrated in the equations in FIG. 45. In this case, the instruction executed by an external processor to the METAPROCESSOR is composed of an OPCODE from the self instruction being executed and the current value of the data in the META-DATA register. The METAPROCESSOR will continue its execution of self instructions after receipt of the ACTIVE signal from the processor which is to execute the instruction as defined in the control arc transmit logic or in the case that the tag bit being set in the METAPROCESSOR will wait for the completion of that instruction before continuing.

The METAPROCESSOR will execute the scan self instruction if the SELF-OPCODE is 03. The scan instruction is similar to the pass instruction with the addition that the META-DATA register is loaded with the data from the program memory processor. In the case of the scan instruction, the instruction consisting of the OPCODE from the OPERAND portion of the self instruction and the current value of the META-DATA register is sent out to the processing unit defined by the destination read only memory in the control arc transmit logic 4401. As soon as the instruction is generated by the METAPROCESSOR, the contents of the program memory processor output is loaded into the METAPROCESSOR data register 4303 from the B multiplexer 4302 whose address is enabled by the B multiplexer address ROM 4301 to look at the PMEM data input which is the output of the program memory processor.

The SCANW (scan and wait) instruction is executed for the SELF-OPCODE 02 if the tag bit 0 is a logic 1 signal. In this case, the operation is the same as for SCAN except that the METAPROCESSOR will wait for the completion of instruction execution (usually in the program memory processor) before loading the META-DATA register from the output of the program memory. The SCANW instruction is used to access and load the META-DATA register with the next character data from the program in the program memory processor. Usually the operation code for the scan weight is the advance instruction in the program memory which allows accessing the next location in the program memory.

The load instruction is used to load the META-DATA register from any location accessible from the B multiplexer 4302. The operation is as follows: the SELF-OPCODE register is loaded with OPCODE 04 and the tag quantity of the self instruction is 0. In this case, the B multiplexer address ROM is steered to the location which is defined by the OPERAND portion of the self instruction. In this manner, any of the quantities, LINK, STACK, PMEM data processor output, FORM processor output, SEM processor output or OIU data output can be loaded into the META-DATA register. This instruction allows the METAPROCESSOR to access the results of computations performed in other processing elements of the exemplary graph architecture machine. Once the data is loaded into the DATA REGISTER, then that data may be used as a part of an instruction passed out by the METAPROCESSOR to another processing element or used internally in the METAPROCESSOR to determine on a conditional basis its sequence of operations.

The DATA self instruction is executed if the SELF-OPCODE 04 and the tag is value 1. In this case, the META-DATA register is loaded with the OPERAND portion of the self instruction by way of taking the OPERAND output of the register 4508 through the C multiplexer 4502 further through the B multiplexer 4302 and finally into the META-DATA register 4303. This instruction is used in the METAPROCESSOR sequences to load data which is initially defined in the SEQUENCE RANDOM ACCESS MEMORY. In this manner, the META-PROCESSOR using this instruction in combination with a PASS instruction may completely define an instruction to be passed out to other processors accessible from the METAPROCESSOR.

The load P instruction is executed if the SELF-OPCODE is 05 and tag is 0. In this case, the META-OPCODE register 4503 is loaded with the current value in the DATA register, or as defined by the OPERAND portion of the self instruction which allows loading the OPCODE register from any of the locations accessible by the C and B multiplexers.

The EXEC instruction is executed if the SELF-OPCODE is 05. In this case, the new state of the sequence counter 4505 is located by the contents of the META-DATA register. In this manner, a new state may be defined in the METAPROCESSOR using data loaded previously from an external processor or by the DATA instruction from the SEQUENCE RANDOM ACCESS MEMORY. This instruction is used to allow the access to differing sequences in the METAPROCESSOR by external data input.

The LOAD RAM HI and LOAD RAM LO Self instructions are executed for SELF-OPCODES 06 and 07 and are used to load the SEQUENCE RANDOM ACCESS MEMORY 4506. The operation of these instructions has been described previously.

The JUMP self instruction is executed if the SELF-OPCODE is 10. The JUMP instruction allows the current state value in the sequence counter 4505 to be loaded from the OPERAND and tag portions of the self instruction. This allows access to a different sequence in the SEQUENCE RANDOM ACCESS MEMORY from a currently executing sequence.

The CALL self instruction is executed if the SELF-OPCODE is 11. The operation is similar to the JUMP self instruction except that in addition the current value of the sequence counter 4505 is recorded in the sequence stack illustrated in FIG. 46. The sequence of operation is as follows: the stack counter 4601 is incremented using timing pulse P2. Pulse P4 stores the current value of the sequence counter in the STACK RANDOM ACCESS MEMORY 4602. The data is gated to the sequence counter 4505 through the C multiplexer 4502 which in turn is gated through the B multiplexer 4302 and subsequently presented to the data inputs to the STACK RANDOM ACCESS MEMORY 4602. This instruction is used to record the present value of the sequence while allowing the execution of a separate sequence in the SEQUENCE RANDOM ACCESS MEMORY. During the execution of the new sequence, a RETURN self instruction may be executed which allows the location of the call point stored to be reloaded into sequence counter 4505.

The RETURN self instruction is executed if the SELF-OPCODE is 12. The RETURN self instruction allows the current address value in the STACK RANDOM ACCESS MEMORY 4602 to be loaded into the sequence counter 4505. Subsequently, the sequence counter is incremented during the execution of the RETURN self instruction and in this manner the location of a sequence point previously used by a CALL instruction may be reloaded and the next sequence step in the calling sequence may be executed. A combination of the RETURN and CALL instructions allows the access and execution of subsequences in the SEQUENCE RANDOM ACCESS MEMORY which may be used by several other sequences in that SEQUENCE RANDOM ACCESS MEMORY. In addition, because the stack allows the storage of several addresses, a particular subsequence may in itself call that same subsequence and in that manner operate in a recursive manner, which is a principle well known in the art of computer science.

A PUSH self instruction is executed if the SELF-OPCODE is 13. In this case, the OPERAND and tag portions of the self instructions are stored in the STACK RANDOM ACCESS MEMORY 4602 in the manner described previously for the CALL instruction. In this case, however, the current sequence counter value is incremented. The PUSH instruction allows a future return instruction to access a sequence address defined by the PUSH instruction. The PUSH instruction is very useful in allowing the programming of the grammars necessary for defining the interpretation of the high level language.

The SKIP self instruction is executed if the SELF-OPCODE is 14 and the tag is 0. The SKIP instruction allows a conditional bypassing of the next instruction in the META-SEQUENCE and operates as follows: the OPERAND portion of the SKIP instruction is an address for selecting a condition in the condition circuit FIG. 49. If the condition selected by the OPERAND is true, then the sequence counter 4505 is incremented twice. In this manner, the next step in the sequence is bypassed. Normally, this next self instruction in the sequence is a JUMP instruction. In this manner, if the SKIP is performed, then the JUMP is not executed and the sequence proceeds to the next self instruction. If the SKIP is not performed, then the next instruction is executed which, for example, would be the JUMP instruction and this would allow the access to a different point in the SEQUENCE RANDOM ACCESS MEMORY. This allows the conditional operation of the METAPROCESSOR as a function of conditions both within the METAPROCESSOR and the condition lines from other processing elements in an exemplary graph architecture machine.

The CHAR instruction is executed if the SELF-OPCODE is 15. The operation of this instruction is similar to the SKIP instruction except that in this case the OPERAND is used as a data word for direct comparison to the current contents of the data register. That is, for example, if the current value of the data register is equal to the OPERAND portion of the CHAR self instruction, then a SKIP operation if performed. Otherwise, the next instruction in the sequence is executed which is normally a JUMP instruction to allow the access to a different sequence.

The NCHAR instruction is executed if the SELF-OPCODE is 15 and the tag is 2. The operaion is similar to the CHAR instruction except that the SKIP is performed if the OPERAND portion of the self instruction is not equal to the current value of the META-DATA register. The CHAR and NCHAR instructions are used in the interpretation process to determine what operations or sequences are to be performed by the METAPROCESSOR in response to the sequence of characters in the high-level language program. The CHAREX instruction operates similarly to the CHAR instruction except that the data for comparison is defined by an input to the B multiplexer as selected by the OPERAND part of the self instruction. In this manner, the conditional operation of the METAPROCESSOR can be determined by the comparison of data in the META-DATA register to any value accessible from the B multiplexer.

The class self instruction is executed if the SELF-OPCODE is 15 and the tag value is 1. The operation is similar to SKIP and CHAR instructions except that the condition is based upon whether the current value of data in the META-DATA register is in a class or set defined in the CLASSIFIER READ ONLY MEMORY illustrated in 4802. For example, one class is defined as capital letters. If the value in the META-DATA register is a capital D letter, then this data is in the class accessed by the class name which is selected by the OPERAND portion of the CLASS self instruction. In this case, the SKIP operation is performed and this allows again conditional operation of the METAPROCESSOR as a function of the classification of data in the META-DATA register. If, on the other hand, the data in the META-DATA register, say for example, is the small letter "a" character, then that letter is not in the class defined and in this case the SKIP is not performed.

The NCLASS self instruction is executed if the SELF-OPCODE is 15 and the tag value is 0. The OPERAND portion of this instruction is a class name for use in the classify circuit illustrated in FIG. 48. The NCLASS instruction is the same as the CLASS instruction except that the SKIP is performed if the data value in the META-DATA register is not in the class defined by the OPERAND portion of the self instruction.

The MICRO self instruction is executed if the SELF-OPCODE is 17. The MICRO self instruction allows the manipulation of individual discrete micro operations within the METAPROCESSOR. The selection of the individual micro operation which must be one of the operation outputs from the micro code generator is based upon the value of the OPERAND portion of the self instruction. The possible micro operations are as follows: if the OPERAND has value 0 a NOP is performed. If the OPERAND portion of this micro self instruction has value 01, the POP operation is performed which decrements the stack counter 4601. The META-CONDITION flip-flop 4902 is reset if the micro OPERAND portion has value 06 and similarly the flip-flop is set if the micro OPERAND portion has value 07. The link converter register is loaded if the micro OPERAND portion has value 10 and is loaded with an alpha-numeric character for octal-to-number conversion if the micro OPERAND portion has value 11. The stack counter 4601 is reset if the micro OPERAND has value 14. The stack counter 4601 is incremented if the self micro self instruction OPERAND has value 15. The METAPROCESSOR HALT operation is executed if the micro self instruction OPERAND has value 16. The micro halt self instruction is used to reset the METAPROCESSOR ACTIVE flip-flop and discontinue the execution of the current sequence. At the completion of this operation, the sequence counter 4505 retains the current state and upon the reception of a new RUN METAPROCESSOR instruction from the OIU will continue the execution of self instructions from the sequence RANDOM ACCESS MEMORY as defined by the previous value in the sequence counter 4505.

A detailed description is now given concerning the programming of self instruction sequences in the METAPROCESSOR to allow the interpretation of high level languages. A high level language is normally defined in terms of mathematical structure called a transduction grammar. The transduction grammar specifies the allowed sequences of characters in a high level language program and identifies what actions are to be taken by the machine in response to the character sequences in a high level language program. The METAPROCESSOR is eminently suited for this task since it can take data from the program memory processor which can be loaded with the high level language program being executed and its set of conditional instructions allows interpretation of those characters and the generation of instructions to other processors in the system to allow execution of numeric computations, display operations, etc., as a function of those statement sequences in the high level language program. The transduction grammar is written using a special notation illustrated in the following table:

< > Enclose the name of a state.

. Enclose the name of an input symbol part of the high level language program.

() Enclose the name of actions or instructions to be executed by the METAPROCESSOR or other PE's.

.fwdarw. Delimits the left hand side (LHS) and right hand side (RHS) of grammar rule equations.

.epsilon. Means any input symbol or character.

* Execute state without getting a new input character.

A transduction grammar consists of a listing of grammar rules similar to those defining the legal sentences in the English language and have the general form

For the types of grammars used in a high level language interpretation process, the LHS quantity is a single state name corresponding to an address value for loading into the sequence counter 4505 and the RHS part consists of a string of characters which denote actions and states to be executed by the METAPROCESSOR by way of passing out instructions to other processing elements in the system and in addition specifies new states to be executed if that particular grammar rule is to be executed. The RHS also contains a reference to specific character data or character classes to be used for determining whether that specific grammar rule is to be executed. In summary then, a list of grammar rules is given for a high level language and the operation of that grammar is determined by a combination of a current state value in combination with a new character input in the high level language program. This uniquely selects one of the grammar rules in the overall list of grammar rules and allows the conditional operation of the METAPROCESSOR in that manner. To illustrate this action, the following table illustrates a simple transduction grammar definition of a very simple case.

1. <A>.fwdarw..1.<B>

2. .fwdarw..epsilon.<B>

3. <B>.fwdarw..a.<B><A>

4. .fwdarw..epsilon.

Assume that the system is started in the state referenced by the state name "A" and that the input sequence of the characters is "1a23." By the rule selection process, since the system is now in STATE A and the first input symbol is 1, this causes RULE 1 to be executed. The execution of this rule causes the next state to be STATE B. Now the next input character is read and since it has value "a", this allows RULE NO. 3 to be executed. The execution of RULE 3 requires that the STATE A be remembered as a pending state, that is pushed on the address stack, and the next state to be executed is STATE B. The next input is the letter "2" and RULE 4 is executed. Since no new state is denoted in this case, then the last pending state value pushed on the address stack is used. In this case, that last address stack value denoted STATE A so that now the machine enters STATE A and must execute either RULE 1 or RULE 2. Since the next input symbol is the character 3, then RULE 2 is executed, which causes the STATE A to be again executed. A practical high level language may require the use of several hundred of these grammar rules for its definition, and require in correspondence several hundred self instruction sequences to be programmed into the SEQUENCE RANDOM ACCESS MEMORY.

The following conventions are followed when using this notation in the following discussions:

1. If a given state has more than one rule associated with it, these rules are listed without the current state name on the left of the arrow.

2. In a given state, the first arrow symbol means get or read a new input character. In the case of the METAPROCESSOR, this means execute the SCAN instruction with an OPCODE for accessing new data in the PMEM processor. Subsequent rules for that state in the list of grammar rules for that state do not get a new input character.

3. The input is not advanced for a current state if it was reached by a state reference having the star symbol "*" after it.

4. For a rule of the form .fwdarw..epsilon.*, the latest pending state on the address stack is executed without getting into input character.

5. For a rule of form .fwdarw..epsilon., the next pending state is executed on the address stack.

6. The rules for a current state are assumed to be executed in the order given.

In the case of interpreting a high level language, the input symbols for determining which one of the grammar rules in the overall list of rules is to be executed is normally a character such as found in APPENDIX B. A combination of a sequence of these characters constitutes the high level language program. Examples are now given for the relationship of the grammar rule notation to self instructions for programming in the METAPROCESSOR. These examples are illustrated in the following table:

To illustrate the programming of the METAPROCESSOR for implementation of the SPONL language, refer again to the MCP multiple choice program example. FIG. 4D illustrates a sequence of characters which constitutes the high level language program for this example. METAPROCESSOR programming for executing a portion of the sequences necessary for interpreting this program is illustrated in FIG. 4E. The PROG state is that state which is initially entered by the METAPROCESSOR when it begins interpretation of a program. This state is returned to subsequently between the execution interpretation of each statement in the program. Starting at the PROG state, the self instruction PASW ADVANCE causes the next character in the program to be accessed from the PMEM processor. The next self instruction at line 4E02 causes that data value accessed within the PMEM processor to be loaded into the META-DATA register. The class is now checked of that data to see if it is the beginning character of a statement. This is performed by the NCLASS self instruction on line 4E03, which determines if the data character which is now on the META-DATA register is in the class of characters called BEGIN class. The BEGIN class is illustrated in detail in APPENDIX Q. If the character read from the program memory processor and stored into the META-DATA register is in the BEGIN class, then the self instruction line 4E04 is executed. In this case, the self instruction is the EXEC self instruction which causes the new state of the METAPROCESSOR to correspond to the character value in the META-DATA register. That is, the data value is used in the state transition table part of the META sequences illustrated in lines 4E06 to lines 4E03 to determine which of the sequences in the METAPROCESSOR are to be executed. For example, if the character read from the PMEM processor is the period character, then the state on line 4E07 is entered which causes the JUMP to the sequence called HALT on line 4E14. During this sequence, a sequence of instructions is passed out including the clearing of the matched stack in the STG processor by way of the pass CLEARM instruction on line 4E14 and this is followed by the issuance of the ENABLE instruction for the OIU processor on line 4E15. This allows the input of data from the operator of the system. The HALT self instruction is now executed at line 4E16. This causes the METAPROCESSOR to discontinue its operation and await a new run command. Once the OIU processor has received new data from the operator, it will generate the run command to the METAPROCESSOR with the data entered from the operator. In this case then, the METAPROCESSOR will continue its operation from the state HALT 2 at 4E17. The self instruction at this location in the sequence causes the PUSHM instruction to be executed in the STG processor which allows the storing of the input data from the operator in the match stack. At line 4E18 now the JUMP to state PROG self instruction is executed and now the operation of the METAPROCESSOR continues as before from the state PROG on line 4E01. Now a new statement type is detected and the corresponding sequence for interpreting that new statement is entered. For example, in the case of the display sequence, the DISPLAY state at line 4E19 if the PROG state determines that the statement to be executed was begun with the little letter "d". DISPLAY sequence now performs additional states to generate instructions for the display portion of the system to generate information on the display device. Additional operations in the program in the high level language are accomplished by a combination of program control point sequences and conditional checking of the operator input data. For example, the alternate sequence line 4E39 is executed if character from the program memory is the vertical slash character (1). The ALT sequence allows the comparison of the next character in the program memory with the current character value in the match stack. If these compare, then the current control sequence in the program is skipped. The complete definition of the grammars implemented in the METAPROCESSOR for the exemplary training system are given in APPENDIXES M, N, O and P. APPENDIX M and APPENDIX N contain the special grammar called the META-INTERPRETER COMMUNICATION GRAMMAR. This particular grammar allows interpretation of inputs directly from the operator as opposed to interpretation of the program in the program memory processor. If the METAPROCESSOR is put into the state of using the interpreter communication grammar, the operator of the system is allowed direct control over the operation of the METAPROCESSOR and subsequently the operation of the other processing elements in the system.

This interpretation communication grammar is used mostly for maintenance of the system and access to specific programs to be executed. The self instruction sequence coding for the example SPOML grammar is illustrated in APPENDIX Q. The self instructions listed there include the binary and octal values of the SELF-OPCODES, OPERAND values and sequence address locations needed by the METAPROCESSOR for the actual execution of the sequences of interpreting high level SPOML language.

The METAPROCESSOR may be used for several applications by way of defining a new language or using the definition of an existing transduction grammar definition of a high level language. In particular, languages such as the BASIC and ALGOL which are commonly in use may be implemented in the METAPROCESSOR. In conjunction with new or the same processors illustrated in the exemplary training system, programs written in those languages may be executed using the METAPROCESSOR for interpreting the high level language and translating high level language statements to lower level sequences of primitive operations which can be executed by the METAPROCESSOR and other processing elements in the exemplary system.

The processors performing input processing are illustrated in FIG. 4A and include GRAF, KYBD, INPT and OIU. In the example training system, the GRAF and KYBD processors are physically part of the OIU processor hardware but operate as separate processors under the definitions of my invention. INPT is a general purpose control processor based on a microprocessor which is programmed to preprocess inputs from KYBD, GRAF, INPT and FORM and sends outputs to the META to allow program processing of operator inputs. In typical system operation, the KYBD or GRAF originates an instruction input to OIU following an operator action such as striking a key on the keyboard, then OIU receives the instruction and passes that instruction to the INPT for preprocessing. For example, GRAF instructions containing Graf pen coordinate data are converted to symbolic names based on tables loaded into the INPT processor. The INPT then sends the symbolic name with the META "RUN" OPCODE to the OIU, and then the OIU passes this instruction to the META. After processing the symbolic name data, the META sends an "ENABLE INPUTS" instruction to the FORM. The FORM passes this instruction to the OIU and the OIU in turn passes the instruction to INPT, where a flip-flop is set enabling further input processing. The cycle repeats itself during normal training system operation.

KYBD and GRAF, while not physically distinct processors in the example training system, are logically distinct in that they provide output instructions to the OIU and interface independently with external equipments. KYBD interfaces with an ASCII (American Standard Code for Information Interchange) Keyboard which allows the operator input of alpha-numeric data to the system. In addition, KYBD can originate special instructions such as "BOOTSTRAP" and "REPEAT" in response to operator depression of actuator/indicator keys which are labeled with the names "BOOTSTRAP" and "REPEAT". Further, KYBD allows the operator (or the INPT processor) to load an instruction into a register within KYBD for subsequent passing to the IOU and then to the rest of the system. This instruction generation feature allows an operator to specifically command other processors in the system to effect manual system testing.

The GRAF processor interfaces with the Graf pen external electronics package. When the operator makes a pen entry, GRAF "calculates" the absolute X and Y rectangular coordinates of the pen hit position over the system display area, and generates an instruction called "PROCESS PEN ENTRY" to the OIU.

The OIU is a special control processor which can be described as a multiple control arc input/multiple control arc output CP. No instruction processing takes place inside the OIU: every instruction it receives from KYBD, GRAF, INPT or FORM is passed out without modification to INPT or META. The OIU is specialized in that the KYBD and GRAF are incorporated within it, and it has a special interface with the INPT unit. In addition, the OIU provides the system CLOCK and MASTER RESET signals used by the other processing elements in the system.

The INPT processor is a microprocessor based CP which makes use of special interface circuits in the OIU to function as a control processor. The INPT is programmed to preprocess KYBD and GRAF instructions via the OIU. INPT contains tables to aid in the processing of GRAF instructions, and these tables can be loaded under the direction of system programs by instructions from FORM. The detailed description of the INPT processor is brief because it differs little from similar processors common in the art.

In summary, in the inputs processing subsection, the KYBD and GRAF processors generate instructions from operator entries, the INPT processor does the data processing on these inputs, and the OIU processor allows instructions over control arcs from four sources to be channelled to any of four processors depending upon the OPCODE of a specific instruction and this is an example of a processor with multiple input arcs under the definition of my invention.

The Operator Interface Unit (OIU) is a control processor which allows instructions from GRAF, KYBD, FORM or INPT to be passed on to META or INPT. From FIG. 15, the OIU block diagram, it can be seen that actually the OIU has eight instruction sources, represented by request signals to the CAR circuit 1507, and four instruction sinks or destinations, represented by request signals out of the CAT circuit 1508. One request signal comes from the GRAF processor 1501, three requests come from the KYBD processor circuit 1504, repeat circuit 1503 and bootstrap circuit 1502, one request comes from the FORM interface circuit 1505, two requests come from the INPT interface circuit 1506, and the remaining request signal is a spare input not used. The output request signals go to the INPT and META processors (two are spare). In operation, the OIU control circuitry 1507 receives a request and instruction from one of the interface circuits, and directs the CAT circuit 1508 to send the request and instruction to the appropriate destination processor.

OIU-OPCODE is a time shared bus which is used to transfer input instructions, OPCODE and data, from the input interface circuits to the destination processors (INPT and META). In operation, the instruction data is first placed on the OIU-OPCODE bus and loaded into the data register 1509, and second, the instruction OPCODE is placed on the same bus. At this point in time, the instruction is ready to be passed from the OIU to the INPT or META processor. FIG. 19 shows the OIU instruction OPCODE and data format.

The OIU provides the training system with several system CLOCK signals and a system MASTER RESET signal as shown as outputs from circuit 1510 in FIG. 15.

Each of the blocks of FIG. 15 are now examined in greater detail. Typical electronic components for constructing an OIU processor are listed in APPENDIX J.

The GRAF processor circuit 1501 is shown in greater detail in FIG. 18, and the circuit timing is shown in FIG. 56B. The Graf Pen Electronics 1807 is an external processor (as identified in APPENDIX A) which produces three pulse signals whenever the electronics is activated by an operator pen entry. The PEN-START signal is a long pulse which overlaps the other two signals and causes the request signal PEN-RQ to be generated. The start detector circuit 1801 generates PEN-ACTIVE-1 to the pen request generator circuit 1802 when

and is synchronized with the trailing edge (logic 1 to 0 transition) of the PEN-CLK signal. The PEN-ACTIVE signal is reset (set to logic 0) when

or when

and the trailing edge of the PEN-CLK signal occurs. The request generator circuit 1802 generates the PEN-RQ=1 signal to the OIU CAR circuit 1507 in FIG. 15 when

and the trailing edge of the PEN-CLK signal occurs. Once the request is activated (logic 1 value), it remains so until

The signal RES-PEN also serves to reset (set to 0) the pen X and Y counter circuits 1804 and 1805. The OIU CAR circuit responds to the PEN-RQ signal by generating a "PROCESS PEN ENTRY" instruction to the INPT processor. After INPT has completed its processing, it causes PEN-RQ to be reset via the OIU INPT interface circuit 1506. This circuit generates the INPT-SEL-RES and INPT-WR signals to the pen request generator circuit 1802 and this allows another operator pen entry to be processed.

The pen clock generator circuit 1803 generates a 0.816 MHZ clock signal called PEN-CLK from a 1.667 MHZ input clock signal called INPT-P2 from the INPT processor. The pen clock generator contains toggle switches which allow a binary number N to be adjusted from 128 to 255 affecting a change in the frequency of PEN-CLK generated, given by the equation: ##EQU1## The circuit is essentially a count by (256-N) counter which removes one pulse of the input clock signal every time the counter overflows to zero. An additional counter stage is used to effect the final frequency divide by two. N is normally set to 207 in this circuit. The PEN-CLK frequence is chosen to allow a convenient linear scale factor between the PEN-X and PEN-Y pen counter outputs and the distance covered by the pen sound wave across the display surface. This allows the pen coordinates to be proportional to the display address.

The PEN-X counter 1804 and the PEN-Y counter 1805 are binary counters which count up from zero at the rate set by PEN-CLK, and count only when enabled by the equations:

and

respectively. The Graf Pen Electronics generates PEN-X-ENB and PEN-Y-ENB pulse signals so that the pulse length (time active) of each is exactly the time required for the pen sonic impulse to travel to the X and Y linear microphones connected to the electronics package. The resulting counter values, PEN-X and PEN-Y, are proportional to the pen distances from the X and Y linear microphones, and thus can be considered to be the X and Y coordinates of the pen position over the display.

The ten bit PEN-X and PEN-Y signals are transferred to the INPT processor by the pen multiplexer circuit 1806 which puts the counter values on the INPT-DBUS data bus when enabled to do so by instructions from the INPT processor. In addition, six bits of fine adjustment information (toggle switches) can also be selected for output on the INPT-DBUS lines. Two INPT-ADR signals from the INPT interface circuit 1506 serve to select which of PEN-X, PEN-Y or the fine adjustment information is desired, and INPT-SEL-PEN=0 enables or causes the selected information to be placed on INPT-DBUS. In processing the "PROCESS PEN ENTRY" instruction, the INPT processor reads the PEN-X, PEN-Y and fine adjustment values by acting through the INPT interface circuit to effect the enabling and control of the pen multiplexer as described.

The boot circuit 1502 which is normally considered part of the KYBD processor is shown in FIG. 17A, and FIG. 56C shows the boot circuit timing. When the operator depresses the BOOT A/I switch 1705, the PNL-BOOT signal is driven low (logic 0). The high to low transition of PNL-BOOT causes the request BOOT-RQ=0 signal to be generated to the OIU CAR circuit 1507. The CAR responds to this request by generating a "BOOTSTRAP" instruction to the INPT processor and sending the ACTIVE acknowledge signal ACK-BOOT=0 to the BOOT flip-flop 1706. This signal resets the request to BOOT-RQ=1. BOOT is a very simple example of a control processor under the definitions of my invention.

The repeat circuit 1503 which also is normally considered part of the KYBD processor is shown in greater detail in FIG. 56D. The oscillator 1707 is a RC (Resistor-Capacitor) timing circuit based on the Signetics 555 timer as listed in APPENDIX J which generates a low frequency square wave signal called TIME. This signal is combined with the PNL-RPT signal from the repeat A/I switch 1708 so that when

the repeat request flip-flop 1709 generates the request signal RPT-RQ=0 to the OIU CAR circuit 1507. The CAR responds to this request by generating a "REPEAT" instruction for the INPT processor and sending an ACTIVE acknowledge signal ACK-RPT=0 to the repeat request flip-flop. This signal resets the request to RPT-RQ=1. REPEAT is a second example of a very simple control processor.

The keyboard processor circuit 1504 in FIG. 15 is shown in greater detail in FIG. 17C, and the circuit timing is shown in FIG. 56E. The KYBD processor generates instructions to the OIU processor from operator inputs on a typewriter-like keyboard external processor. This circuit interfaces with a standard ASCII keyboard 1711 and two A/I's (actuator/indicators) 1710 and 1712. The two A/I's are non-latching push button switches which change "state" with every actuation as indicated by lamps within the switches. The keyboard OPCODE mode flip-flop 1701 and the DATA-7 flip-flop 1713 each alternate state with each leading edge transition of the A/I signals PNL-OP-MOD=0 and PNL-DAT-7=0 respectively. KBD-RES=0 resets the state of these flip-flops so that KBD-OP-MOD=1 and KBD-DAT-7=1.

The ASCII Keyboard 1711 generates 7-bits of KBD-DATA and a pulse KBD-STB-IN whenever a key is depressed. The data is is combined with the KBD-DAT-7 signal to meet the standard 8-bit word (character) system format, and is buffered by keyboard data buffer register 1703 before being placed on the OIU-OP signal lines. When the buffer is enabled by the SEL-KBD=0 signal, the keyboard data is used to load either the keyboard OPCODE register 1704 and the OIU data register 1509 or just the keyboard OPCODE register.

The keyboard request generator flip-flops 1715, 1716, 1717 and 1702 generate the timing and control signals shown, following a strobe signal input from the keyboard. If

then the SEL-KBD=0 signal is not generated following the keyboard strobe. This prevents possible usage conflicts over the OIU-OP bus. The OIU signal OIU-CLK is used to synchronize the signals generated by this circuit. The OIU-MR=1 signal serves to reset the circuit and also generates the KBD-RES=0 signal. Following a keyboard strobe input, the SEL-KBD=0 signal is generated for one clock period as shown in FIG. 56B. This signal causes the keyboard data to be placed on the OIU-OP bus. KBD-STB=1 is then generated and is used to effect the loading of the keyboard OPCODE register and the OIU data register. If KBD-OP-MOD=0, then both registers are loaded; otherwise, only the OIU data register is loaded with keyboard data. Following KBD-STB=1, the request KBD-RQ=0 is generated, but only if KBD-OP-MOD=1; otherwise, no further action takes place. Thus, if the keyboard interface circuit is in the OPCODE mode (KBD-OP-MOD=0), then keyboard data is loaded into the keyboard OPCODE and OIU data registers, and no request is generated. If the circuit is not in this mode (KBD-OP-MOD=1), then keyboard data is loaded into the OIU data register and a request is generated to the OIU control circuitry.

When the OIU control circuitry receives the keyboard request, the circuitry sets ACK-KBD=0 which resets the request and causes the keyboard OPCODE register contents to be placed on the OIU-OP bus. The keyboard output instruction (now OIU instruction) is then passed to the INPT or META processor. Normally, the instruction is a "PROCESS KEYBOARD ENTRY" instruction for INPT, although the capability exists for the operator to enter any instruction into the system with the keyboard by using the OPCODE A/I switch.

The keyboard OPCODE register 1704 is loaded from the OIU-OP bus with either KBD-STB=1 or under INPT control with

from the INPT interface circuit. When the keyboard OPCODE register is loaded under INPT control, the OIU-OP bus contains INPT-DBUS data. During the time periods of system initialization and bootstrap, the INPT processor uses this capability to load the "process keyboard entry" OPCODE into the keyboard OPCODE register so that manual entry of this OPCODE is not required.

The INPT processor has the capability of generating a pseudo keyboard request via the INPT interface circuit by setting SET-KB-RQ=0. Once this occurs, the OIU control circuitry processes the request in the same manner as any other keyboard request.

The FORM interface circuit 1505 is shown in more detail in FIGS. 53A and 53B. FIG. 53A shows the FORM-RQ-OIU signal input request to the OIU input request encoder 5301. In responding to this request, the OIU control circuitry generates the active signal OIU-ACT-FORM as shown. The OIU CAR control circuitry is described in later paragraphs.

FIG. 53B shows the FORM data buffer 5306 and FORM OPCODE register 5307. In processing a FORM request, the FORM data buffer is enabled with the EN-FORM-DAT=0 signal, placing FORM-DATA on the OIU-OP bus. This data is loaded into the OIU data register 5309 with WR-FORM=1. At the same time, the FORM OPCODE register is loaded with FORM OPCODE. Subsequently, the OPCODE register contents are enabled onto the OIU-OP bus with EN-FORM-OP=0, and the FORM instruction, now OIU instruction, is passed to the INPT or META processor. FIG. 56F shows the FORM interface timing.

The INPT interface circuit 1506 is shown in greater detail in FIG. 55, and the circuit timing is shown in FIG. 56G. The INPT interface circuit can do seven different functions corresponding to the seven different output signals of the INPT select decoder 5502. When INPT-ENB-SEL=0, the address bus INPT-ADR is checked for valid values by the enable PROM 5501. If the address is valid, then the INPT ENABLE PROM 5501 (as defined in detail in APPENDIX H) generates INPT-ENB=0 which enables the address decoder. The functions performed or started by the decoder outputs are listed below:

(1) INPT-SEL-INPT: pass INPT instruction.

(2) INPT-SEL-INPW: pass-wait INPT instruction.

(3) INPT-SEL-INPK: pass keyboard instruction.

(4) INPT-SEL-PEN: enable pen multiplexer 1806 onto INPT-DBUS.

(5) INPT-SEL-INPD: load OIU data register from INPT-DBUS data.

(6) INPT-SEL-KBD: load keyboard OPCODE register from INPT-DBUS data.

(7) INPT-SEL-RES: reset pen request and counters.

When enabled the decoder sets one of these outputs low (=0) and the rest high (=1).

Any of the first three outputs cause the flip-flop 5504 to be set with the strobe signal INPT-STS. This flip-flop generates INPX-RQ=1 and RDY-INPT=0. The latter signal causes the INPT processor to suspend its operation until the OIU has finished passing the INPT or keyboard OPCODE and OIU-END=0 resets the flip-flop. Either of two requests can be generated by gates 5505 and 5506

or

In processing these requests, the OIU enables the INPT-DBUS onto the OIU-OP bus with EN-INPT=0 (see FIG. 53B, INPT data buffer 5305). The OIU data register must be loaded previously, with INPT-SEL-INPD=0, to provide data to be passed out with the OIU-OP OPCODE. After the instruction has been passed (to the META), the OIU control circuitry generates OIU-END=0 which resets the INPT request flip-flop 5504.

The OIU CAR control circuitry 1507 is shown in greater detail in FIGS. 53A and 53B, and the circuit timing is shown in FIGS. 56F and 56H. Eight request signals are prioritized and encoded by the input request encoder 5301 which forms the basis of multiple control arc input. The output ANY=1 indicates the presence of any request input to the encoder, and CODE is the 3-bit priority number of the highest priority request present. The CODE any ANY signals are loaded into the request register 5302 repeatedly with the OIU-CLK signal until 1=ANY=XXX-RQ-OIU. Also the request register is inhibited from being loaded if

This prevents any requests other than those initiated by the INPT interface circuit from getting recognized when INPT is active. When a request is recognized, XXX-RQ-OIU=1, and the request register is not reloaded until it is reset by

the CODE signal becomes SEL-ADR after being loaded into the request register 5302, and is used to address the ACTIVE acknowledge generator PROM 5303. This PROM is programmed (as defined in detail in APPENDIX E) to emulate a decoder circuit with the difference that when OIU-MR=1, the ROM output acknowledges are all activated. The ROM outputs are enabled when

and the result is a low output acknowledge corresponding to the SEL-ADR code held in the request register.

The signal XXX-RQ-OIU=1 initiates a timing chain of flip-flops 5311, 5312 and 5304 which control the sequencing of OIU activities. The flip-flop signals control the flow of information on the OIU-OP bus in preparation for passing out an OIU instruction when OIU-BUSY=1. After the instruction has been passed out, the output instruction circuit sets DONE=1, which causes flip-flop 5310 to generate OIU-END=0. This last serves to reset the control circuitry and prepare the circuit to respond to another request.

The first four request sources, SPARE, BOOT, REPEAT and PEN, do not generate their own instructions. Instead, the fixed OPCODE ROM 5308 (as defined in detail in APPENDIX F) is used to supply OPCODES for these request sources. The remaining four request sources generate their own instruction OPCODES as has been described.

The OIU CAT output instruction circuit 1508 is shown in greater detail in FIG. 54, and the circuit timing is shown in FIGS. 56H and 56I. The OPCODE on the OIU-OP bus addresses the active/request selector PROM 5401 (defined in detail in APPENDIX G), which generates the RQ-ADR request address. Different OPCODES generate request addresses for their corresponding destination processors. When

the request generator (decoder) 5404 generates an OIU request to the destination processor specified by the request address.

The same request address is used to switch the active multiplexer 5402 so that the active signal from the processor requested is monitored by the active edge detector circuit 5403. When the selected active goes from low (=0) to high (=1), the ACT-UP=1 signal is generated. When ACT-UP=1 and the selected active goes from high to low, ACT-OOWN=1 is generated. When the circuit is in pass-wait mode, ACT-INPW=0, and ACT-DOWN is switched by the up-down multiplexer 5405 to supply the DONE signal. Otherwise, ACT-INPW=1, and ACT-UP is switched to supply the DONE signal to the OIU control circuitry.

The system CLOCK and MASTER RESET generation circuit 1510 is shown in greater detail in FIG. 52, and the clock circuit timing in FIG. 56A. The system clock source can be selected between an internal oscillator 5201 and an external or manual clock by the clock multiplexer 5202. The external clock source is used only for maintenance purposes. Slower clock frequencies for different speed processors in the system are generated by the clock counter 5203. System MASTER RESET is generated by the MR actuator/indicator, and buffered in the OIU. The MASTER RESET signal is used by most processors in the example system to initialize control circuitry prior to program execution.

INPT or Input Processor is a general purpose microprocessor based processor which makes use of special interface circuits in the OIU to function as a control processor in the system. FIG. 16A is the INPT block diagram and FIG. 16B shows the INPT interface timing. The other circuits in INPT are controlled by the microprocessor and support logic. The address bus INPT-ADR from the microprocessor is used by the bus control logic 1604 to select data sources and destinations for data on the INPT-DBUS microprocessor data bus. The INPT-DBUS bus is a bidirectional data path linking the microprocessor with registers and memory within INPT, and also is used to transfer information to and from the OIU. Components for constructing an INPT processor are lists in APPENDIX K.

The support logic 1602 provides clock and reset signals for the microprocessor. The clock is derived from a crystal controlled oscillator circuit, and one of this clock's derivatives is the 1.667 MHZ square wave signal INPT-P2 which is sent to the OIU sonic pen circuit. At the beginning of each microprocessor memory read or write cycle, a strobe INPT-STS is generated. When OIU-RQ-INPT=1, the support logic generates an interrupt to the microprocessor, which starts executing its program stored in the PROM 1605, which is defined in detail in APPENDIX I. The RDY-INPT signal is used for suspending the microprocessor operation in the middle of a memory read or write cycle (if RDY-INPT=0).

The bus control logic decodes the address bus and microprocessor status to generate enables to the data sources on the data bus, write strobes to the data destinations, and an external enable INPT-ENB-SEL for the OIU. The microprocessor status information determines whether a read or write cycle will occur.

The multiplexer 1603 is used to get OIU-OPCODE, OIU-DATA and condition input signals onto the microprocessor data bus.

The RAM and ROM memory 1605 is used for table and variable storage, and program storage respectively.

The flag register 1606 is used to generate the INPT-ACT-OIU active and condition output signals.

The data register 1607 is used to generate latched data output, INPT-DATA, which is not used in the present system.

The Mass Data Transfer Subsystem (MDTS) portion of the example training system consists of the: Format Processor (FORM), Working File Buffer Processor (WFB), Data Link Processor (DL), Mass Storage Processor (MSC), Floppy Disk Processor (FDIU), and Mass Storage Device external processor as shown in FIG. 5. This section describes the purpose and operation of this subsystem and the processors in it.

The MDTS's primary purpose is to manage block data transfers between the Mass Storage Device and the other portions of the system. Secondly, it is used by the Program Execution and Inputs Processing sections of the system to build, form, and/or manipulate data into data blocks (defined to be 256 eight-bit data characters) for use by the Program, Display, or Mass Transfer portions of the system. Additionally, it may be directed to perform operations on data strings of the type defined previously. The strings may originate from sources including the Mass Storage Device and the Input and Program Execution portions of the system. These operations are of an interpretive nature using the state defined control concept and allow strings to be broken down into control and data substrings for distribution to other processors. Finally, it provides instruction and data paths for interaction with the other subsystems.

The Format Processor (FORM) is a control processor which directs other processors in the MDTS and serves as the MDTS node for interaction with other portions of the system. It implements the state defined control operations. The Working File Buffer Processor (WFB) is a data processor which is used to implement the data forming function and is similar in design with the previously described PMEM processor. The Data Link processor (DL) is a data processor which is used to buffer blocks in a memory called a Mass Storage Buffer (MSB) to and from the mass storage device and to multiplex data betweem processors and other parts of the system. Additionally, it contains a comparison function to test the equality of two data words. Taken together, the FORM and DL perform similar types of operations performed by the METAPROCESSOR except that the Mass Storage Buffer (MSB) is added and not all the METAPROCESSOR self-instructions are implemented in the FORM. The Mass Storage (MS) Processor is a control processor which, together with the Floppy Disk Processor, implements mass storage access and data transfer operations. The Floppy Disk Processor (FD) is a data processor which interfaces with the Mass Storage External Device. It performs control and data transfer motions between the Mass Storage Device and the Mass Storage Processor. Additionally, the Floppy Disk Processor provides arithmetic and temporary register storage functions for use by the MS. The Mass Storage Device is an external processor which is used to store blocks of data in a non-volital fashion for use by the other portions of the system. In this application, the device is a Floppy Disk Drive of the type defined in APPENDIX A.

The MDTS can perform three classes of operation: (1) mass transfer, (2) control interpretation, and (3) data block manipulation. A typical operation of the first class is a transfer of display information otherwise called a display file from the Disk to the Display Processing portion of the system. Such an operation would typically be requested by the Program Execution portion of the system. First, the MS is given the Disk address associated with the display. Next, the FORM is given a command to perform the transfer. The FORM begins the transfer by initializing the DL for the receipt of a block of data from the MS, and then directs the MS to begin the transfer. The MS, in conjunction with the FD, accesses the block of data and starts reading words from the disk. The FORM takes these words one at a time and puts them in the DL mass storage buffer. When the transfer from the disk is complete, the MS indicates to the FORM the occurrence or non-occurrence of an error in the data. This allows a retry before the data leaves the subsystem. From the mass storage buffer, the data is transferred to the Display Subsystem. The operations are similar for other types of mass transfers.

A typical operation in the control interpretation class is the interpretation of a display string from the Program Execution portion of the system. First, the Program Execution portion of the system directs FORM to get ready for a display string. As the Program Execution portion of the system passes characters of the string to the FORM, the FORM uses the DL compare function to see if the character matches certain control characters. If they do, the FORM directs the Display Processing portion of the system to change its display mode. This might be a change from displaying the characters in a standard format to displaying them in a complemented format.

A typical operation in the third class of operations is character insertion into the WFB. Assume the WFB has a program in its memory which is being constructed, and the program author wishes to insert some new statements into the middle of the program at location "X". To insert the characters, the WFB is first commanded to set its memory address to X. Next, the FORM is given the first character, with the instruction to INSERT. The WFB is directed to save its current address (X), and present the character at that address to the FORM. The FORM takes the character from the WFB, and then directs the WFB to write its present memory location with the character the FORM received with the INSERT instruction. The WFB memory is incremented and the exchanging of characters between it and the FORM continues down through the memory until the end is reached. At this point, the FORM directs the WFB to return its memory address to X. It is then ready to receive the next character for insertion.

The Floppy Disk (D) Processor performs data and control transformations between the Disk Drive of the Mass Storage and the MS. Additionally, it provides arithmetic and temporary register storage functions for the MS. Each of the FD operations consists of a few elementary steps which perform such operations as read/write head movement and parallel/serial/parallel data conversation.

FIG. 25 is a block diagram of the FD processor. The operation input register 2501 receives the OPCODE portion of the MS generated instruction. The Data Input Register 2502 receives the data portion of the MS instruction. From here, the data can be routed to the Disk Drive via the Shift Register 2505 or to the ALU (Arithmetic Logic Unit) 2504 for an arithmetic or logical operation. The Temporary Storage Registers 2503 are used for storage of control parameters, disk addresses, and intermediate arithmetic and logical results. The ALU 2504 is used to perform arithmetic and logical operations. The Shift Register 2505 is used to perform serial/parallel/serial conversions between the FD processor and the Disk Drive of the Mass Storage Device. The Output Data Multiplexer 2506 is used by the FD to output either disk or ALU data. The Disk Control Logic 2507 under the control of the MICRO-CODE GENERATOR 2508 produces the control signals which are sent to the Disk Drive. The MICRO-CODE GENERATOR 2508 decodes the OPCODE portion of the MS instruction. Depending on the OPCODE, ALU conditions and Drive conditions, enables are generated to control all the other components in the processor. The CONTROL LOGIC 2509 performs the FD/MS interface control functions and generates timing pulses and clocks which are gated with the enables from the MICRO-CODE GENERATOR 2508 to perform operations in the Processor components. Additionally, the control logic 2509 can be directed by the MICRO-CODE GENERATOR to raise or lower the Condition Flag.

The Processor performs two basic classes of operations: (1) ALU and (2) Disk Interface. A typical example of the first class is the addition of two numbers A and B. First, A is given to the Processor with a load register instruction. The data passes through the DATA INPUT REGISTER and the ALU for storage in one of the TEMPORARY REGISTERS. Next, the value of B is given to the Processor with an ADD instruction. B is added to A and the result passes out the OUTPUT DATA MULTIPLEXER 2506.

A typical example of the second class operation is read/write head movement. The MS passes a head move IN or OUT instruction to the FD. There is no data associated with the code. The MICRO-CODE GENERATOR 2508 decodes the instruction as a head move instruction and enables the DISK CONTROL INTERFACE 2507 to generate the appropriate command signals to the Disk Drive of the Mass Storage Device. Since the FD processor performs operations and is implemented in a manner well known in the art, no detailed description is given.

The Mass Storage Processor controls the FD Processor and is controlled by the FORM. Along with the FD, the MS implements the Mass Storage Functions. These functions are: (1) disk track a and sector access, (2) data reading (word by word at the MS/FORM interface), (3) data writing, and (4) data word error checking. The specific purpose of the MS in the implementation is to translate high level instruction OPCODES and data for the FD. The Mass Storage Processor contains a programmed memory and other supporting functions which allow it to implement translation sequences containing conditional branches and procedure calls. The MS is of the same design as the SEM, FORM, and DSPL processing elements and is essentially a METAPROCESSOR element with reduced number of self instruction types.

FIG. 26 is a block diagram of the MS Processor. The elements have the following functions. The DATA INPUT MULTIPLEXER 2601 provides data movement capability from the various external and internal sources onto a central bus for redistribution. This central bus forms the Data portion of the MS instruction. The DATA REGISTER 2602 receives the data portion of the FORM instruction and receives and holds data received from and passed out to other processors. The OPERATION INPUT REGISTER 2603 holds the OPCODE received from the FORM for decoding by the PRESET/DESTINATION LOGIC 2604. The SOURCE/DESTINATION LOGIC 2604 determines if the received instruction is to be passed directly out as part of an MS instruction, or if the instruction is to initiate a translation sequence. The CONTROL LOGIC 2613 and ACTIVE/REQUEST LOGIC 2615 are informed accordingly. The SEQUENCE ADDRESS MULTIPLEXER 2605 provides a means for the SEQUENCE ADDRESS COUNTER 2606 to be loaded from the Data Bus during JUMP and subroutine RETURNS self instructions and from the OPCODE INPUT REGISTER during translation sequence instructions. The SEQUENCE ADDRESS COUNTER 2606 provides states and addresses for the SEQUENCE MEMORY 2607 and may be loaded or counted up. The SEQUENCE MEMORY 2607 is used to program translation sequences, and its outputs are divided into two fields, SELF-OPCODE and OPERAND. The SELF-OPCODE through the CONTROL LOGIC 2613 and the MICRO-CODE GENERATOR 2614 controls all the other components in the processor. The OPERAND field contains OPCODES to be passed out as well as sequence addresses for JUMPS and subroutine CALLS. The OPCODE OUT MULTIPLEXER 2608 allows loading of the OPCODE OUT REGISTER 2609 from the OPCODE INPUT REGISTER 2603 for direct passed codes or from SEQUENCE MEMORY 2607 for translation sequence instructions. The OPCODE OUT REGISTER 2606 holds the OPCODE portion of the MS instructions. The STACK COUNTER 2610 and the STACK MEMORY 2611 are used to implement the subsequence functions. When a subsequence is called, the STACK COUNTER 2610 is incremented and the STACK MEMORY 2611 is loaded from the SEQUENCE ADDRESS COUNTER 2606. On the RETURN self instruction, the SEQUENCE ADDRESS COUNTER 2606 is loaded from STACK MEMORY 2611 and the STACK COUNTER 2610 is decremented. The CONDITION LOGIC 2612 allows the processor to execute conditional sequences based on the Condition Indicator at the FD. The MICRO-CODE GENERATOR 2614 decodes the SEQUENCE MEMORY 2607 SELF-CODES into the necessary signals and timing terms to control the other components in the processor. The MICRO-CODE GENERATOR also receives inputs from the control logic 2613 and condition logic 2612 which are necessary for complete generation of the component control signals. The CONTROL LOGIC 2613 provides overall control of the actions taking place in the processor.

When a FORM request is received, the logic loads the OPCODE and DATA REGISTERS and raises the MS ACTIVE signal to the FORM. With the aid of the Source/Destination logic 2604, the Control Logic 2613 starts a direct pass or a translation sequence depending on the instruction received. The ACTIVE/REQUEST Logic 2613 may be directed by the MICRO-CODE GENERATOR 2614 or by the SOURCE/DESTINATION LOGIC 2604. When the MS passes out an instruction, this logic raises a Request to the FD processor and holds the Request until the processor raises an Active signal.

The processor performs two basic types of operations corresponding to the two types of instructions it may receive from the FORM: direct and sequence. When an instruction is received, it is first examined to determine if it is direct or sequence. If it is a direct instruction, the OPCODE is loaded into the OPCODE OUT REGISTER 2609 and the DATA INPUT MULTIPLEXER 2601 is switched to look at the DATA REGISTER 2602. The FORM instruction is then passed out as an MS instruction to the FD Processor. The ACTIVE/REQUEST Logic 2615 performs the necessary handshaking as directed by the Source/Destination logic 2604. If the FORM input instruction is a sequence instruction, the OPCODE is used as an address to preset the SEQUENCE ADDRESS COUNTER to the sequence location associated with that OPCODE. The translation sequence which is subsequently executed may take many forms, for it may cause a series of instructions to be passed out of memory unconditionally, or it may cause a series of instructions to be passed out repetitively until some condition is met. Consider the Access Track/Sector instruction as an example. First, FORM, using Direct Instructions, loads the desired disk track and sector into two temporary storage registers in the FD. The FORM then issues an access instruction to the MS. First, the MS gives an instruction to the FD to subtract the current track address from the desired track address. Depending on the outcome of the operation (indicated by the FD condition flag), the MS gives the FD a move read/write head instruction and a change current address instruction. This process continues until the head is positioned over the desired track. At this point, a similar operation is used to find the desired sector. When the sector is found, the MS goes not active. At this point, the FORM would direct the MS to perform an initiate Read or Write operation.

The Data Link Processor (DL) shown in FIG. 27 is a data processor (DP) which is primarily used to provide an information distribution path between processors within the Mass Data Transfer portions of the system and the other portions of the system, and to provide a buffer memory for blocks of data to and from the mass storage device. As an information distribution device, DL provides data transfers between the Format Processor (FORM), the METAPROCESSOR (META), the Working File Buffer Processor (WFB), the Mass Storage Processor (MS), the Display Processor (DSPL) and the Operator Inputs Unit (OIU). As a buffer memory device, DL provides data block storage for information going to and from the MS Processor and the above-mentioned processors. DL also provides a character "equal" comparison feature which is used for decoding character strings being processed by the FORM.

DL receives its control instruction and requests from the FORM processor and sends back the DL ACTIVE and CONDITION signals. DL-2 receives data from FORM, META, WFB, MS and DSPL and sends data for FORM, META, WFB, MS, DSPL and OIU.

FIG. 27 includes the control logic circuitry 2701 which interfaces with the control arc signals, DL-COND-FORM, DL-ACT-FORM and FORM-RQ-DL, the Comparator Circuit 2704 COMPARE signal, the DL COUNTER CIRCUIT 2707 COUNTER ZERO signal, and the MICRO-CODE GENERATOR 2703 output micro-code signals. The Control Logic 2701 contains combinational and sequential logic circuitry which controls and directs the control arc interface and all the other logic circuit sections 2702-2708 in DL based on its inputs from the MICRO-CODE GENERATOR 2703 COMPARATOR 2704 and DL Counter 2707. Specifically, the CONTROL LOGIC 2701 generates timing signals which direct activity in the other circuitry of DL, these timing signals being dependent on enable signals from the MICRO-CODE GENERATOR 2703, which enables are in turn dependent on the contents of the OPERATION CODE INPUT register 2702.

The OPERATION CODE INPUT REGISTER 2702 is a register which contains the OPCODE portion of the FORM which is being executed by DL while DL is active. The OPERATION CODE INPUT REGISTER 2702 contents are decoded combinationally by the MCIRO-CODE GENERATOR 2703, which generates enable signals for the control logic circuit 2701.

The multiplexer 2705 is an 8 to 1 data path switch controlled by the control logic 2701 section of DL. The multiplexer 2705 can select three internal sources, the DL BUFFER MEMORY 2708, the DL COUNTER 2707 and the DL DATA REGISTER 2706, and five external (to DL) sources, the data portion of FORM, META DATA, WFB DATA, MS DATA AND DSPL DATA, any one of these eight to be placed on the DL-DATA OUTPUT data path. The DL-DATA path goes to the comparator 2704, the DL DATA REGISTER 2706, the DL COUNTER 2707, the DL BUFFER MEMORY 2708 and six other processors in the training system as was outlined before.

The COMPARATOR 2704 is a combinational logic circuit which makes a numerical equal comparison between the DL DATA from the Multiplexer 2705 and the data portion of the FORM. The result of this comparison, equal or not equal, is provided to the control logic 2701 by a COMPARE signal, which in turn is used by the control logic 2701 to generate the DL-COND-FORM signal.

The DL DATA REGISTER 2706 is a register which can be loaded with DL-DATA from the multiplexer 2705 and which can be selected as a data source by that multiplexer. The DL DATA REGISTER is used for temporary data storage as, for example, a source for a subsequent comparison using the COMPARATOR 2704.

The DL Counter 2707 is a register which can be loaded the DL DATA from the Multiplexer 2705, which can be incremented or decremented by one, which has circuitry for determining when the counter contents is zero resulting in a COUNTER ZERO SIGNAL to the control logic 2701, and which provides the address for the DL BUFFER MEMORY 2708. The DL COUNTER 2707 can be selected as a data source by Multiplexer 2705.

The DL Buffer Memory 2708 is a random access memory (RAM) which can save DL DATA from the Multiplexer 2705 by being written into at a location in the memory selected by the address from the DL COUNTER 2707. The DL BUFFER MEMORY 2708 output can be selected as a data source by the Multiplexer 2705.

The general operation of the DL Processor is as follows. Starting from quiescent state in which DL is not active, the presence of FORM-RQ-DL causes the control logic 2701 to emit timing signals which load the operation code input register from the FORM INSTRUCTION and subsequently raise the DL-ACT-FORM signal. The OPCODE in the OPERATION INPUT REGISTER 2702 is then decoded into enable signals by the MICRO-CODE GENERATOR 2703, which enables are used by the CONTROL LOGIC 2701 to provide timing and control to direct the OPCODE's execution. After the OPCODE execution phase is complete, the LD-ACT-FORM signal is lowered and the DL Processor returns to the quiescent state.

There are three classes of DL operation codes: LINK OPCODES, Buffer OPCODES and Data Register OPOCDES. The LINK OPCODES cause the selection of a specified data source for the Multiplexer 2705 so that the data source is placed on the DL DATA OUTPUT for subsequent use within DL and/or by other processors in the training system. The Buffer OPCODES provide for writing into and reading from the DL BUFFER MEMORY 2708, and for loading, incrementing and decrementing the DL COUNTER 2707 which addresses the memory. The DATA REGISTER OPCODE loads the DL DATA REGISTER 2706.

The Working File Buffer (WFB) Processor is used for program, symbol, and display construction under the control of the FORM. The WFB contains a main RAM storage for the data being constructed. It contains an additional auxiliary RAM for tables of specific addressable points in the main memory. The processor also performs addressing functions on both memory arrays.

The WFB Processor is diagrammed in FIG. 28. Its instruction register is composed of an OPERATION INPUT REGISTER 2802 and a DATA INPUT REGISTER 2804. The operation code is decoded by the MICRO-CODE GENERATOR 2803 into the appropriate enables to the other components for the execution of that instruction. The CONTROL LOGIC 2801 recognizes the FORM request to WFB and provides feedback via the WFB active and CONDITION lines. In addition, the control logic provides the sequence of timing control signals for the processor. The WFB COUNTER 2805 drives the WFB MEMORY ARRAY 2806. This memory is used for the data module constructions and may be loaded from the DATA INPUT REGISTER. The WFB COUNTER may be loaded, or incremented up or down, for movement throughout the memory. If the counter at anytime generates a count greater than the size of the memory array, the WFB notifies the FORM via the WFB CONDITION line. If a specific address of the memory array is to be remembered for later reference, then it is stored in the WFB STACK MEMORY 2803. The STACK MEMORY is employed as a last-in, first-out memory device where the address of the next possible storage location (for the stack memory) is kept in the STACK COUNTER 2807. Thus, if an address is to be saved, it is stored in the STACK MEMORY at the current address value found in the STACK COUNTER; then the STACK COUNTER contents are incremented so that it will hold the address of the location where the next address may be stored. A memory address may be restored by decrementing the stack and loading the WFB counter. If the WFB attempts to save or restore addresses off either end of the stack (no more storage room or no more addresses to restore), the WFB notifies the FORM via the WFB CONDITION line. The data input register 2804 contains any data that may be associated with an instruction. There are two types of input data: (1) addresses to be loaded in either the WFB counter or the stack counter or (2) data to be stored in the WFB MEMORY ARRAY. The output Data Multiplexer 2809 provides a means of accessing the outputs of the various WFB components.

The WFB operations are the same as those previously described for the PMEM processor.

The FORMAT (FORM) Processor controls the other processors in the MDTS and serves as the subsystem node for interactions with other subsystems. It controls and implements, in conjunction with the other processors in the subsystem, the functions of the subsystem. The specific purpose of the FORM in the implementation is to translate high level instructions and data into low level OPCODES and data for the processors under its control. It contains a programmed memory and other supporting functions which allow it to implement translation sequences containing conditional branches and procedure calls.

FIG. 29 is a block diagram of the processor and illustrates that FORM has the same design as the previously described MS and SEM processing elements.

The processor performs two basic types of operations corresponding to the two types of instructions it may receive from the META: direct and sequence. When an instruction is received, it is first examined to determine if it is a direct or sequence instruction. If it is a direct, the code is loaded into the OPERATION OUT REGISTER 2909 and the DATA INPUT MULTIPLEXER 2901 is switched to look at the DATA REGISTER 2902. The META instruction is then passed out as a FORM instruction. The ACTIVE/REQUEST LOGIC 2915 performs the necessary handshaking as directed by the Source/Destination Logic 2904. If the META instruction is a sequence code, the code is used as an address to preset the Sequence Address Counter 2906 to the sequence location associated with the code. A translation sequence may take many forms. It may cause a series of codes to be passed out of memory unconditionally, or it may cause a series of codes to be passed out repetitively until some condition is met.

Consider the Insert instruction as a sequence example. When the instruction is received, the character is loaded into the DATA REGISTER, the OPCODE presets the Sequence Address Counter 2905 to the proper location. First, FORM passes instructions to the WFB to direct it to save the memory counter address in the WFB stack memory and to switch its output data multiplexer to the memory data. The DL is then sent an instruction to load its DATA REGISTER from the WFB. Next, the WFB is passed a WRITE MEMORY instruction, the DATA being the character to be inserted from the FORM Data Register. The FORM Data Register is now loaded from the DL DATA REGISTER to prepare for the next insertion. The WFB is passed a code to increment its counter and raise its condition line if the memory has reached its end. The FORM does a conditional jump and repeats the sequence of steps above unitl the WFB Condition line is raised. The FORM then directs the WFB to restore its counter from its stack, and then goes not active having completed the translation of the INSERT instruction. APPENDIX MM defines the complete ROM sequences for the FORM as used in the example training system.

The display processing subsystem is an autonomous processor for displaying data strings and building and interpreting symbol structures. The display processing subsystem may be used as a peripheral processor to an existing computer system or as a functional processor in a graph architecture processing system such as the exemplary training system. FIG. 57 illustrates the typical interconnection of the display processing subsystem controller or DSPL in such systems. The processor called FORM (for formatting processor) may be a computer, or a control processor, and supplies the data in sequences of instructions necessary for performing display and symbol construction. FIG. 57 also lists the signals which exist between DSPL and the rest of the system. The functions of these signals are as follows:

FORM-RQ-DSPL signal which is active when the FORM processor desires the DSPL to execute an instruction.

DSPL-ACT-FORM signal which is generated by DSPL and when active indicates that DSPL is executing the instruction requested by FORM.

DSPL-COND signal which indicates the variety of conditions depending on the syntax of the sequence of the display instructions.

SYM-DATA word output of SYM supplies the readout of constructed symbols.

DIU-DATA word output of DIU supplies the readout of the cursor for providing sensitized displays.

DSPL-RQ-SYM signal which is active when the DSPL processor desires the SYM to execute an instruction.

SYM-ACT-DSPL signal which is generated by SYM and when active indicates that SYM is executing the instruction requested by DSPL.

SYM-COND signal which indicates a variety of conditions depending on the syntax of the sequence of instructions from DSPL.

DSPL-RQ-DIU signal which is generated by DIU and when active indicates that DIU is executing the instruction requested by DSPL.

DIU-COND signal which indicates when the cursor has passed beyond the lower right-hand corner of the screen. The DSPL control processor directs the activities of the SYM data processor, DIU data processor, PROJ data processor, and PRNT data processor. The SYM data processor provides the capability to construct, store and interpret symbol structures. The DIU data processor provides the interface necessary for the driving of a variety of display devices. This capability includes the plasma panel and raster scan CRT, both as indicated in APPENDIX A. The PROJ data processor provides the driving interface to a random access slide projector as specified in APPENDIX A. The PRNT data processor provides the driving interface to a hard copy printer specified in APPENDIX A.

The display processor subsystem is designed to provide the direct processing of a grammar. This grammar defines the display syntax. As a part of the semantics of this grammar, the ability to drive a variety of display devices without regard to their various differences is a major concept implemented in the display processor subsystem. This concept may be best described by the example system where switching between the plasma panel display and the raster scan CRT display is made without regard to the structure of the display strings in the grammar describing the interface. In other words, a given display instruction string consisting of graphics, symbols, and sensitized areas may be displayed on either display device without modification of the instruction string. An additional concept is embodied in the grammar semantics provision for construction of symbols in a hierarchical tree structure. These symbols provide the ability to reference complex patterns of an image with minimal direction external to the display processor subsystem. Furthermore, the hierarchical structure of the symbol storage provides flexibility in selection for display of a symbol at any of the nodes of the "tree". The symbol concept provides a "building block" capability for construction of complex displays. In other words, an arbitrarily complex image may be decomposed into a collection of more simple portions which are duplications of some common subset of images. Hence, after construction of each of these "building blocks" as symbols, the desired complete image may be produced from references to the individual members of this collection.

In the display processing subsystem of the example training system, the SYM data processor implements the hierarchical symbol concept. The concept of transparency of type of display device is implemented in this display processor subsystem by the DIU data processor.

The plasma panel interface consists of control and address signal lines to the panel of a type identified in APPENDIX A and status signal lines from the panel. The set of control instructions consist of no-operation, write, erase, and bulk-erase. The interface circuitry of FIG. 7A, Plasma Interface Circuitry, shows the two flip-flops 7A01 and 7A02 used to hold the instruction until acknowledged by the DIG-BUSY signal, received from the plasma panel. The CELL-DOT signal comes from the character generation circuitry when a TRUE condition indicates a lighted dot in the character definition. The COMPL signal when TRUE indicates that the character to be displayed is to be complemented (i.e., unlighted character on a lighted background). The DOT signal is supplied by the micro-enable memory and is TRUE when individual "dot-write" instructions are issued. The ERASE signal when TRUE indicates that the individual dots of a character are to be erased rather than written. The REPL signal when TRUE indicates that each of the dots making up a character are either to be written or erased. Whenever the REPL signal is FALSE, a dot representing the character will be written or erased only if CELL-DOT EXCLUSIVE-ORed with COMPL is TRUE. The BULK-ER signal when TRUE indicates a command to bulk-erase the plasma panel. The DIG-BUSY signal when TRUE indicates that the plasma panel has accepted the instruction. The instruction is immediately replaced by a NO-OPERATION instruction. FIG. 7B, Plasma Interface Timing, shows the timing sequence necessary for interface with the plasma panel. First, the CELL-DOT signal and DOT-ADR signal must be TRUE. Second, the DIG-CMD is presented to the plasma panel. Third, the plasma panel indicates acceptance of the command by the DIG-BUSY signal and the DIG-CMD is immediately set to a no-operation instruction. Finally, the plasma panel indicates completion of the instruction by the DIG-BUSY signal, at which time the DOT-ADR need no longer be held stable.

From the table of FIG. 7A, it can be seen that when the DIG-C.phi. and DIG-C1 signals both TRUE, a NOP instruction is indicated to the plasma panel. This is the normal state of the instruction latch while the plasma panel interface is idling. During this state, the address signals to the plasma panel are not required to be stable.

As indicated in FIG. 7A, when the signals DIG-C.phi. and DIG-C1 are both FALSE (logic 0), a BULK ERASE instruction is indicated to the plasma panel. This command when executed by the plasma panel causes the entire panel to be erased. During this state, the address signals to the plasma panel are not required to be stable.

When signal DIG-C.phi. is FALSE and signal DIG-C1 is TRUE (as indicated in FIG. 7A), a WRITE-DOT instruction is indicated to the plasma panel. This instruction will cause one dot at the coordinates of DIG-X-ADR and DIG-Y-ADR to be lighted. Prior to the issue of this instruction and throughout the plasma panel busy cycle, the address signal, DIG-X-ADR and DIG-Y-ADR, to the plasma panel must remain stable.

When signal DIG-C.phi. is TRUE and signal DIG-C1 is FALSE (as indicated in FIG. 7A) an ERASE-DOT instruction is indicated to the plasma panel. This instruction will cause one dot at the coordinates of DIG-X-ADR and DIG-Y-ADR to be extinguished. Prior to the issue of this instruction and throughout the plasma panel busy cycle, the address signals, DIG-X-ADR and DIG-Y-ADR, to the plasma panel must remain stable.

The CRT interface circuits for an example CRT of type identified in APPENDIX A consist of a series of functional units as shown in FIG. 6A, CRT Interface Block Diagram. The different CRT options (e.g., color complemented, blink) are retained by the CRT OPS latch 6A01. The refresh timing generation and attribute memory is performed by the circuitry indicated by CRT REF MEM 6A02. The standard character cell generation is performed by the circuitry indicated by C-CELL CHAR-GEN 6A03. The extended redefinable graphic character cell generation is performed by the circuitry indicated by G-CELL CHAR-GEN 6A04. The electrical interface to the CRT is performed by the circuitry indicated by CRT INTERFACE 6A05. The CRT that will accept RGB encoded signals with external SYNC is indicated by the CRT symbol 6A06. The CRT INTERFACE is further described by FIG. 6B, CRT Drive Circuitry. The horizontal and vertical synchronization is provided by the SYNC signal which feeds the SWEEP CONTROL 6B01 which in turn drives the deflection circuitry of the CRT 6B02. The individual dots of which a character or graphic cell consists are serially presented as the signals C-CELL-DOT and G-CELL-DOT, respectively. These signals are combined with the complement signal, COMPL, which when TRUE indicates the display of a dark character or graphic on a lighted background. The resulting signal is then used to control the color attribute signals, RED, GREEN and BLUE. Each of these signals when TRUE indicates the corresponding electron gun of the CRT to be turned on. Finally, these signals are further gated by the BLINK signal. This signal when TRUE allows the character to be displayed and when FALSE prevents the display of the character. If selected, the BLINK signal alternates between TRUE and FALSE approximately twice per second. The resulting signals are then presented to the ELECTRON GUN CONTROL circuit 6B02 which in turn drives the electron guns of the CRT 6B02.

The iterative refresh of the CRT display requires a refresh timing circuit for the SYNC signal generation and the address generation for the attribute, standard character, and graphic memories as well as the address generation for the character cell generation and graphic cell generation. A block diagram of this circuitry is represented by FIG. 6C, Refresh Timing Circuitry. The REF-CLK signal provides the FALSE to TRUE transition used to cause each of the counters of the refresh circuitry to advance or reset. The CELL COL generator 6CO1 provides for the CELL-COL signal which provides for the individual dot column address of the character and graphic cell generators. This signal is a modulo eight count. The END-CELL-COL signal becomes TRUE each time the CELL-COL signal reaches a count of seven. This signal causes the MEM COL generator 6C02 to advance to the next count. The refresh memory column address generator provides the MEM-COL signal as a modulo 64 count for the attribute, character, and graphic refresh memories. The END-MEM-COL signal becomes TRUE each time the MEM-COL signal reaches a count of 63. This signal enables the HORIZ SYNC generator 6C03 which generates the H-SYNC signal to the horizontal synchronization circuit of the CRT. In addition, the END-ROW signal is generated which resets the CELL COL generator and MEM COL generator and holds them at the reset condition until the next horizontal line is ready to be generated. The END-ROW signal causes the CELL-ROW generator 6C04 to be advanced to the next count, modulo 16. The CELL-ROW signal, which is generated as a result of this action, is provided to the character and graphic cell generators as the individual dot row address. In addition, the END-CELL-ROW signal is generated each time the CELL-ROW count reaches 15. This signal is used to advance the MEM ROW generator 6C05. This generator produces the MEM-ROW signal, modulo 32, to be used for addressing the attribute, character, and graphic refresh memories. Upon reaching a count of 31, the END-MEM-ROW signal becomes TRUE. This signal enables the VERT SYNC generator 6C06 which in turn provides the V-SYNC signal to the vertical synchronization circuit of the CRT. In addition, the END-FRAME signal is generated which resets the CELL ROW and MEM ROW generators and holds them at the reset condition until the next frame is ready to be generated. The H-SYNC and V-SYNC signals are combined to form the overall SYNC signal.

The usage of the memory and cell address generation can be seen from FIG. 6D, Refresh Memory Circuitry. The CRT display options (e.g., color, complement, blink) are loaded into the CRT OPTNS latch 6DO1 from the DATA signal which is common throughout the DIU. This action is performed when the WR-OPTNS signal becomes TRUE. The cursor is similarly saves in the CRT CURSOR latch 6D02 each time the cursor is updated by the DIU. During refresh, the INT-REF signal is FALSE which allows the MEM COL and MEM-ROW signals to flow through the MUX 6D03 to form the address for the A-MEM 6D04, C-MEM 6D05, and G-MEM 6D06. The output of the attribute memory, A-MEM, provides the signals BLINK, COMPL, RED, GREEN and BLUE for the CRT Drive Circuitry previously shown in FIG. 6B. The output of the character and graphic refresh memories flows through the MUX 6D07 and 6D08 (due to INT-REF being FALSE) to provide the character address to the character cell) generator C-CELL 6D09 and the graphic cell generator G-CELL (6D10, respectively. In addition, the signals CELL-COL and CELL-ROW, through MUX 6D07 and 6D08, to provide the remainder of the address to the cell generators, C-CELL and G-CELL.

The timing relationship of the addressing signals during refresh can be seen from FIG. 6F, CRT Refresh Memory Timing. The refresh clock, signal REF-CLK, provides the update rate for the CELL-COL signal (modulo eight address). At the end of one character cell column cycle, the END-CELL-COL signal becomes TRUE for one REF-CLK cycle. The END-CELL-COL signal provides the clocking signal for the generation of the MEM-COL signal (modulo 64 address). At the end of one refresh memory column cycle, the END-MEM-COL signal becomes TRUE for one END-CELL-COL cycle. The END-CELL-COL signal provides the clocking signal for the generation of the H-SYNC signal (horizontal synchronization) and the END-ROW signal. The END-ROW signal provides the clocking signal for the generation of the CELL-ROW signal (modulo 16 address). At the end of one character cell row cycle, the END-CELL-ROW signal becomes TRUE for one END-CELL-ROW cycle. The END-CELL-ROW signal provides the clocking signal for the generation of the MEM-ROW signal (modulo 32 address). At the end of one refresh memory row cycle, the END-MEM-ROW signal becomes TRUE for one END-CELL-ROW cycle. The END-MEM-ROW signal provides the clocking signal for the generation of the V-SYNC signal (vertical synchronization) and the END-FRAME signal. The END-FRAME signal is used to resynchronize the entire cycle.

In order to load the refresh memory with data to be displayed, the addressing of the A-MEM, C-MEM and G-MEM must be switched from that of the cyclical refresh timing circuitry to that of the cursor latch. This is accomplished by setting the INT-REF signal TRUE. FIG. 6E, CRT Interface Timing/Refresh, shows the timing relationship of the signals necessary to allow the loading of the refresh memory. The CUR-COL address signal and the CUR-ROW address signal must be latched stable when the INT-REF signal becomes TRUE to switch the addressing. After stability has been achieved, the WR-REF-MEM signal becomes TRUE allowing the character indicated by the DATA signal to be written into the refresh memory at the address specified by the CUR-ROW and CUR-COL signals. Similarly, the contents of the display option latch is written into the A-MEM at the same address, specified by CUR-ROW and CUR-COL. The contents of the options latch is loaded by the DATA signal becoming stable following which the WR-OPTNS signal becomes TRUE.

The DIU receives an instruction from the DSPL control processor. As shown in FIG. 59, DIU Instruction and Data Formats, this instruction is made up of a DIU OPCODE and DIU DATA parts. Internal to the DIU, the cursor is stored as a collection of COURSE-Y, FINE-Y, COARSE-X and FINE-X. The total cursor is used to address the CRT or plasma panel to the individual dot location. FIG. 10 and FIG. 11 show the individual dot addressing of the CRT or plasma panel. In addition, a representative character set is shown in the dot matrix format.

A block diagram of the DIU is shown as FIG. 58, DIU Block Diagram. A list of devices needed to implement an example DIU is given in APPENDIX TT. The control logic, CNTRL LOGIC 5801, receives a request from the display control via the signal DSPL-RQ-DIU and acknowledges receipt of the instruction by setting the DIU ACT-DSPL signal TRUE. Along with the request from the DSPL processor, the instruction, DSPL-INST-DIU, is presented to the DIU data processor. The instruction is latched into the OPCODE REG 5802 and the DATA REG 5803 as previously indicated in the instruction format description. The OPCODE is used to generate the micro-enables via the MICRO CODE GEN 5817, (defined in detail in APPENDIX RR). The CURSOR REG 5804, MODE REG 5805, and OPTION REG 5806 are loaded with the data from the data register under control of the micro-enable ROM. The cursor register provides an output condition to the DSPL control processor via the DIU-COND signal. In addition, the cursor register provides addressing to the C-CELL 5813 and G-CELL 5814 via the multiplexers, MPXR 5810 and MPXR 5811. The alternate source for addressing is derived from the CRT C-MEM 5808 and the CRT G-MEM 5809 whose addressing, in turn, is normally derived from the CRT REF TIMING 5807 circuit. This circuit also provides addressing to the CRT A-MEM 5812. The CRT attribute memory, character cell generator, and graphic cell generator provide overall display information to the CRT INTERFACE 5815. In addition, the character cell and graphic cell generators along with the display option register provide the necessary information to the PLASMA INTERFACE 5816.

A closer inspection of the control logic is presented as FIG. 60, DIU Control Logic. The external signal DSPL-RQ-DIU is combined with the internal signal DIU-BUSY to produce the DIU-LD signal which is used to load the OPCODE and data into their respective latches. In addition, this signal causes the preset flip-flop 6001 to be set at the next active edge of the CLOCK signal. This in turn generates the DIU-PRESET signal which is presented to the busy flip-flop 6002. The busy flip-flop is set on the next active edge of the CLOCK signal and generates the DIU-BUSY and DIU-ACT-DSPL signals. This signal causes the preset flip-flop to be reset on the next active edge of the CLOCK signal and prevents the generation of any further DIU-LD signals until the DIU-END signal becomes TRUE. The master reset signal, MR, provides for an overriding reset of the preset and busy flip-flops. The CLOCK, DIU-BUSY, and DIU-PRESET are combined to form the signals DIU-CLK and DIU-PRE-CLK.

The more detailed diagram of the OPCODE, data and microenable circuits are presented as FIG. 61, DIU Instruction and Data Registers and Micro-code Generator. The DIU-LD signal is used to activate the loading of the DIU-OP portion of the DSPL-INST-DIU into the latch 6101. Similarly, the DIU-DATA portion of the DSPL-INST-DIU is loaded by the DIU-LD signal into the latch 6102. The OPCODE portion of the instruction is further decoded by the ROM 6103 which generates the micro-enable signals RD-CUR, WR-CELL, UP-CELL, TI-CUR, TI-CHAR, ON-DOT, LD-CHAR, NO-TI-CUR, LD-MODE, RES-MODE, LD-CUR, LD-CUR-OP, LD-CRT-OP, EN-CUR-OP, CUR-OP-.phi., CUR-OP-1, CUR-OP-2, CUR-OP-3, ROM-CUR-ADR-.phi., ROM-CUR-ADR-1, INT-REF, DIG-EN and BULK-ER.

The display options and cursor modes circuitry are diagrammed in more detail as FIG. 62, Options and Modes Circuitry. The addressable latch 6201 allows the micro-enable ROM to select one of four options, XTEND, COMPL, REPL, or ERASE, which affect the display option used subsequently during the display of a character on the plasma panel or the CRT. The CL-DIG-OP signal provides for the simultaneous clearing of all display option exceptions currently in effect. The cursor mode latch 6202 is loaded with the four least significant bits of the DATA signal. The contents of this latch are used subsequently as a portion of the address of the cursor direction ROM. The value of the contents of the cursor mode latch allows the redefinable spacing modes of the cursor following the display of a character (e.g., right, left, up, down, tabulate, no-space). The selection of the control of the cursor by the cursor mode latch is made by the EN-CUR-OP signal from the micro-enable ROM. The current display in use, plasma panel or CRT, is determined by the output signal CRT from the flip-flop 6203. This flip-flop is loaded with the state of the least significant bit of the DIU-DATA signal when the active edge of the LD-CRT-ON/OFF signal is generated. The blinking character option is selected by the BLINK signal from the flip-flop 6204. This flip-flop is loaded with the state of the least significant bit of the DIU-DATA signal when the active edge of the LD-BLINK-CP is generated. The color option latch 6206 which generates the RED, GREEN, and BLUE signals to control the color of the character to be written into the CRT refresh memory is loaded from the decoded output of the ROM 6205 (illustrated in APPENDIX UU) whose address is determined by the least significant five bits of the DATA signal. The color option latch is loaded when the active edge of the LD-COLOR-OP signal is generated. Each of the outputs of the previous latches and flip-flop (except the CRT flip-flop) are cleared to a FALSE state when the CL-DIG-OP signal is generated.

The cursor circuitry is shown in greater detail as FIG. 63, DIU Cursor Circuitry. The counter 6301 is responsible for generating the addresses of the four portions of the cursor, FINE-X, COARSE-X, FINE-Y, and COURSE-Y. The counter is loaded with the micro-enable ROM signals TI-CUR and NO-TI-CUR during the period the LD-CUR-TI signal is TRUE. The TI-CUR signal provides either one clock period for cursor update or four clock periods. However, the NO-TI-CUR signal is used to prevent any cursor clock periods from being generated whenever the microenables so direct. The multiplexer 6302 is directed by the signal LD-CUR from the micro-enable ROM to provide either the sequential addresses from the cursor address generator or the preset address from the micro-enable ROM. The preset address is used whenever the instruction directs that only one portion of the four-part cursor value is to be modified. The signals FINE-COARSE and COL-ROW provide the address to the register file 6303 containing the current cursor value. During a cursor update which uses the modified value of the old cursor, each of the portions of the cursor are sequentially addressed in the same order as mentioned above. For each value presented to the ADDER 6305, the old cursor value is modified by the contents of the ROM 6304 (illustrated in APPENDIX SS) whose address is specified by a collection of signals indicating the type of spacing to be performed. The CUR-CRY signal is the overflow or borrow condition from the previous operation on the previously addressed portion of the cursor. This feature allows the cursor to drop down one character row whenever the cursor reaches the right-hand side of the display. The FINE-COARSE and COL-ROW signals provide the addressing necessary to treat the individual portions of the cursor differently. The CUR-OP signal is provided from cursor spacing mode latch or the micro-enable ROM. The micro-enable ROM determines which data dominates the signal. Finally, the DIG-EN signal indicates the address for cursor modification depending on whether or not the operation called for by the micro-enable ROM is composed of both a character display operation and a cursor operation or only a cursor operation.

The dot matrix character generation circuit for display is shown as FIG. 64, DIU Character Generation Circuitry. The ROM 6401 is addressed by the DATA signal which is specified by the ASCII value of the character to be displayed in addition to the ROW signal produced by the row address generator. The output of the ROM (the character is a seven dot by nine dot matrix defined within an eight by sixteen dot matrix) is then fed to a multiplexer 6402 which selects one of the eight inputs as indicated by the COL signal produced by the column address generator. Similarly, the RAM 6403 is addressed by the ASCII value of the character plus the ROW signal to produce an eight-dot signal fed to the multiplexer 6404. Again, one dot is selected by the COL signal. Finally, the XTEND signal is used to select between the C-CELL-DOT and G-CELL-DOT signals to produce the CELL-DOT signal used by the plasma panel interface circuit.

The timing relationship of the various signals used to initiate an instruction, modify the cursor, and terminate an instruction are shown as FIG. 65, DIU Timing Diagrams. The CLOCK signal provides the active edge for the actions occurring. Whenever a request is raised by the DSPL control processor, if the DIU is currently idle, then the DIU-PRESET signal will become TRUE at the next active edge. On the immediately subsequent active edge, the DIU-BUSY signal will become TRUE. The DIU-PRE-CLK signal is generated during the previous cycle. The next active edge causes the DIU-PRESET signal to become FALSE. The DIU-CLK signal now begins tracking the CLOCK signal. If the cursor address generator is selected to run by the micro-enable ROM, then four cursor clocks, DIU-CUR-CLK signal, are generated. During the period of cursor modification, the FINE-COARSE and COL-ROW signals produce the desired addresses for the cursor memory. Finally, after the termination conditions are met (as determined by the output state of the micro-enable ROM), the DIU-END signal is generated and the DIU-BUSY signal becomes FALSE on the next active edge.

The DIU raises its DIU-BUSY or DIU-ACT-DSPL signal to a TRUE condition in response to the DSPL-RQ-DIU signal. Otherwise, no cursor or display operation is performed. The DIU immediately returns to the "not-active" state.

The DIU raises the DIU-ACT-DSPL signal in response to the DSPL-RQ-DIU signal. Four cursor cycles are produced during which each of the four portions of the cursor are modified to zero. This operation insures that the next cursor position will be the upper left-hand corner of the display.

The DIU acknowledges the DSPL request. The ASCII character presented in the DATA portion of the instruction is displayed on the plasma panel or written into the CRT refresh memory at the address specified by the current position of the cursor. The sequence of actions also results in the generation of four cursor clock cycles during which the cursor is updated to the new cursor position. The direction and magnitude of the cursor update depend on the current contents of the cursor mode latch.

The DIU acknowleges the DSPL request. THe ASCII character represented by the DATA portion of the instruction is used to set the address into the G-CELL memory for subsequence loading of the dot definition to the redefinable character set.

The DIU acknowledges the DSPL request. The eight-bit DATA portion of the instruction is used to load the redefinable graphic cell generator memory, G-CELL. The address is then incremented by one in order that the next load-cell-row instruction will be performed at the next address. Sixteen of these instructions are required to define an entire graphic cell.

The DIU acknowledges the DSPL request. The six least significant bits of the DATA portion of the instruction are used to load the COARSE-X portion of the cursor. Only one cursor clock cycle is required while the address is provided by the micro-enable ROM.

The DIU acknowledges the DSPL request. The state of the ERASE signal from the display options mode addressable latch is set to FALSE. The address into the latch is provided by the micro-enable ROM. Only one DIU-CLK is required to accomplish this operation. This instruction provides the ability to disable the ERASE condition without affecting the other display options.

The DIU acknowledges the DSPL request. The six least significant bits of the DATA portion of the instruction is used to load the COARSE-Y portion of the cursor. Only one cursor clock cycle is required while the address into the cursor memory is provided by the micro-enable ROM.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor one character width (eight dots) to the left. The direction and magnitude of the cursor update is provided by the CUR-OP signal from the micro-enable ROM. This instruction provides the ability to backspace the cursor during character displays.

The DIU acknowleges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor to the next "tab" position. This is acomplished by incrementing the cursor COARSE-X portion by eight and setting to zero the less significant bits of the COARSE-X portion and clearing the FINE-X portion. This direction and magnitude of the cursor update is provided by the CUR-OP signal from the micro-enable ROM. This instruction provides the ability to "tab" the cursor to the next fixed "tab" position.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor to the next half-line down the display from the current position. This is accomplished by incrementing the cursor COARSE-Y portion by one. The direction and magnitude of this cursor update is provided by the CUR-OP signal from the micro-enable ROM. The "line-feed" instruction provides the ability to display subscripts.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor to the next half-line up the display from the current position. This is accomplished by decrementing the cursor COARSE-Y portion by one. The direction and magnitude of this cursor update is provided by the CUR-OP signal from the micro-enable ROM. The "vertical-tab" instruction provides the ability to display superscripts.

The DIU acknowledges the DSPL request. The BULK-ERASE signal is set TRUE in order for the plasma interface to generate a BULK-ERASE command to the plasma panel. If the CRT state is set, then the CRT refresh circuit is set to write the most significant bit of each location in the refresh memory to a TRUE state. In addition, four cursor clock cycles are generated during which each of the four portions of the cursor are modified to zero. The signals necessary for this cursor update are provided by the CUR-OP signal from the micro-enable ROM. The "form-feed" instruction provides the ability to clear the display without disturbing the display options currently in effect.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor to the beginning of the next full character line below the current line. This is accomplished by clearing the FINE-X and COARSE-X portion of the cursor and incrementing the COARSE-Y portion of the cursor by two. The direction and magnitude of this cursor update is provided by the CUR-OP signal from the micro-enable ROM. The "carriage-return" instruction provides the ability to attain the next display line for common textual displays.

The DIU acknowledges the DSPL request. The three least significant bits of the DATA portion of the instruction are used to load the FINE-X portion of the cursor. Only one cursor clock cycle is required while the cursor address (i.e., FINE-X) is provided by the micro-enable ROM.

The DIU acknowledges the DSPL request. The three least significant bits of the DATA portion of the instruction are used to load the FINE-Y portion of the cursor. Only one cursor clock cycle is required while the cursor address (i.e., FINE-Y) is provided by the micro-enable ROM.

The DIU acknowledges the DSPL request. The BULK-ERASE signal is set TRUE in order for the plasma interface to generate a BULK-ERASE command to the plasma panel. If the CRT state is set, then the CRT refresh circuit is set to write the most significant bit of each location in the refresh memory to a TRUE state. In addition, four cursor clock cycles are generated during which each of the four portions of the cursor are cleared. The signals necessary for this cursor update are provided by the CUR-OP signal from the micro-enable ROM. Finally, the CL-DIG-OP signal (clear display options and cursor options) is generated. The "reset" instruction provides the ability to completely reset the unit to a pristine state.

The DIU acknowledges the DSPL request. Before the DIU-ACT-DSPL signal returns to a FALSE state, the contents of the COARSE-Y portion of the cursor memory are presented on the output of the DIU data processor. The specified cursor address is provided by the micro-enable ROM. Only one cursor clock cycle is required to complete this instruction.

The DIU acknowledges the DSPL request. Before the DIU-ACT-DSPL signal returns to a FALSE state, the contents of the COARSE-X portion of the cursor memory are presented on the output of the DIU data processor. The specified cursor address is provided by the micro-enable ROM. Only one cursor clock cycle is required to complete this instruction.

The DIU acknowledges the DSPL request. Before the DIU-ACT-DSPL signal returns to a FASLE state, the contents of the FINE-Y portion of the cursor memory are presented on the output of the DIU data processor. The specified cursor address is provided by the micro-enable ROM. Only one cursor clock cycle is required to complete this instruction.

The DIU acknowledges the DSPL request. Before the DIU-ACT-DSPL signal returns to a FALSE state, the contents of the FINE-X portion of the cursory memory are presented on the output of the DIU data processor. The specified cursor address is provided by the micro-enable ROM. Only one cursor clock cycle is required to complete this instruction.

The DIU acknowledges the DSPL request. The upper bits (bits five and six, numbering the least significant bit as zero) of the DATA portion of the instruction are examined to determine which of three actions will occur. (1) The CRT state flip-flop will be loaded from the state of the least significant bit of the DATA portion of the instruction. (2) The BLINK state flip-flop will be loaded from the state of the least significant bit of the DATA portion of the instruction. (3) The color option latch will be loaded with the output of the color decode ROM whose address is specified by the five least most significant bits of the DATA portion of the instruction. This instruction allows the selection of the different CRT display options that are not a subset of the plasma panel display options.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor in the direction specified by the four least significant bits of the DATA portion of the instruction. This instruction provides the ability to move the cursor in any of sixteen different manners as controlled by the input data.

The DIU acknowledges the DSPL request. Only one DIU clock cycle is generated. The state of the ERASE signal from the display options mode addressable latch is set to TRUE. The address into the latch is provided by the micro-enable ROM. This instruction provides the ability to enable the ERASE condition without affecting the state of the other display options.

The DIU acknowledges the DSPL request. Only one DIU clock cycle is generated. The CL-DIG-OP signal is generated which clears the cursor option mode latch, the display option mode latch, the BLINK flip-flop and the CRT color option mode latch. This instruction provides the ability to reset only the display and cursor options without affecting other portions of the unit.

The DIU acknowledges the DSPL request. Only one DIU clock cycle is generated. The least significant four bits of the DATA portion of the instruction are loaded into the cursor option mode latch. This instruction provides the ability to preset the method of cursor update that will be applied after the display of any subsequent characters.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the portion of the cursor in the direction specified by the four least significant bits of the DATA portion of the instruction. In addition, a single dot is written at the previous location of the cursor during plasma panel operations. This instruction allows the ability to perform incremental dot graphic display operations.

The DIU acknowledges the DSPL request. The ASCII character presented in the DATA portion of the instruction is displayed on the plasma panel or written into the CRT refresh memory at the address specified by the current position of the cursor. However, the cursor is not modified from its current position. This instruction allows the ability to implement a software visible cursor with a minimal number of instructions.

The DIU acknowledges the DSPL request. Four cursor clock cycles are generated in order to update the position of the cursor to the next character space to the right of the current position on the display. This is accomplished by incrementing the COARSE-X portion of the cursor by one. The direction and magnitude of this cursor update is provided by the CUR-OP signal from the micro-enable ROM. The "forward-space" instruction provides the ability to space the cursor without affecting the display.

The DIU acknowledges the DSPL request. Only one DIU clock cycle is generated. The state of the REPL signal from the display options mode addressable latch is set to TRUE. The address into the latch is provided by the micro-enable ROM. This instruction provides the ability to enable the replace condition without affecting the state of the other display options.

The DIU acknowledges the DSPL request. Only one DIU clock cycle is generated. The state of the COMPL signal from the display options mode addressable latch is set to TRUE. The address into the latch is provided by the micro-enable ROM. This instruction provides the ability to enable the "reverse-writing" condition (dark character on lighted background) without affecting the state of the other display options.

The DIU acknowledges the DSPL request. Only one DIU clock cycle is generated. The state of the XTEND signal from the display options mode addressable latch is set to TRUE. The address into the latch is provided by the micro-enable ROM. This instruction provides the ability to select the redefinable graphic cell generator as the character source for the plasma panel. If the CRT state is TRUE, then the extended character set refresh memory, G-MEM, is selected to be written into.

Referring to FIG. 8, the control of the slide projector to PROJ to rear project an image on the plasma panel will be explained. A particular projector used in the exemplary system is a Kodak RA-960 as identified in APPENDIX A which has the capability of storing 80 slides and accessing any one of these slides on demand. PROJ exercises control over the projector by performing any one of four operations commanded by DSPL:

PROJECTOR ON

PROJECTOR OFF

LOAD ADDRESS

ACCESS SLIDE

Each of the commands from DSPL is transmitted in the form of an instruction DSPL-INST-PROJ which may include an operation code portion and a data portion. Simultaneous with transmission of an instruction to an instruction input register in PROJ, DSPL transmits a request signal DSPL-RQ-PROJ to control logic in PROJ. The control logic effects latching of the instruction in the instruction input register and then transmits an active signal PROJ-ACT-DSPL to DSPL. Transmission of this active signal is maintained until the operation commanded by DSPL has been completed. The data portion of the instruction flows to an operation interpretation ROM and to a units address register. The ROM interprets data and transmits a signal designating the operation to be performed to the control logic. The control logic then effects completion of the designated operation and drops the active signal informing DSPL that PROJ is ready to perform another operation.

If a PROJECTOR ON signal is interpreted by the ROM, the control logic raises a signal on a line connected to the projector informing the projector to turn power on. If a PROJECTOR OFF signal is interpreted by the ROM, the control logic is caused to drop the signal directing the projector to turn power off.

The LOAD ADDRESS operation is commanded if the ROM detects numeric data input. The data is interpreted by the ROM causing the control logic to effect the gating of the data portion into a units address register. If it is desired to display a slide located at storage locations 0 through 9, the data in the units address register will be utilized to designate this location to the projector. If it is desired to display a slide located at a two-digit address, however, the DSPL will transmit two successive instructions with the data portion containing the lower order digit. The higher order digit will be loaded into the unit's address register during the first of these operations and during the second operation the higher order digit will be transferred to a ten's address register and the lower order digit will be loaded into the unit's address register.

The ACCESS SLIDE operation is commanded by an instruction havving an operation code portion only. After interpretation by the ROM, the control logic transmits an ACCESS SLIDE signal directing the projector to display the slide located at the address represented by the data in the ten's and unit's address registers.

Referring to FIG. 9, the control of the line printer by PRNT to print a designated character will be explained. The Cassio Jet printer as identified in APPENDIX A requires only data giving a seven digit code designating a character to be printed and a request signal indicating that this data is being transmitted. The data designating a desired character is first transmitted from DSPL to a data input register DATA IN in the print processor, simultaneous with transmission of a request signal DSPL-RQ-PRNT to control logic. The control logic effects latching of the data into the data input register and transmits an active signal PRNT-ACT-DSPL to DSPL. The control logic then transmits a request signal to the printer indicating that data designating a character to be printed is being transmitted from the data input register to the printer. The printer writes the character designated and then transmits a READY signal to the control logic in PRNT. The READY signal causes the control logic to drop the active signal informing DSPL that the designated character has been printed.

Information defining graphic and pictorial images to be presented on the plasma panel and/or the TV display device is stored in SYM before transmission to DIU by DSPL. Each image to be presented is structured from a plurality of symbols and each of these symbols is designated by a unique character assigned by the operator or by the lesson plan. Each of these symbols is in turn structured from a plurality of smaller symbols also designated by unique characters. This process of constructing larger symbols from smaller symbols and designating each by a unique character can be continued down to a primitive symbol which is formed by a single display cell. Thus, a multi-level, tree-structured definition of symbols of arbitrary complexity may be established. A very simple example of such a tree-structured definition is illustrated in FIG. 12A. The symbols defined by the characters of FIG. 12A are illustrated in FIG. 12B.

As illustrated in FIG. 13, SYM 1301 includes an OPERATION INPUT REGISTER 1302 and a DATA INPUT REGISTER 1303 for receiving OPCODE and data portions of instructions from DSPL. An OUTPUT DATA REGISTER 1304 is provided for holding data to be transmitted to DSPL. SYM also includes CONTROL LOGIC CIRCUITRY 1305 controlling performance of operations specified by received instructions, and two random access memories designated the SYMBOLS MEMORY 1306 and the SYMBOLS STACK 1307. The SYMBOLS MEMORY 1306 stores symbol definitions and the SYMBOLS STACK 1307 operates as a look-up table for translating each character into the beginning address in the symbols memory for the definition of the symbol designated by the character. The SYMBOLS STACK 1307 is also used for short term storage of addresses in the SYMBOLS MEMORY 1306 which must be reentered during readout of symbols. A complete list of devices needed to construct an example SYM processor is given in APPENDIX QQ.

Storage of a symbol definition requires that DSPL transmit the starting address and the character designating this symbol to the DATA INPUT REGISTER 1302. The starting address is then gated to a SYMBOLS COUNTER 1308 and also through a STACK COUNTER 1309 to a memory location in the SYMBOLS STACK 1307 at an address designated by the transmitted character. Upon completion of these operations, DSPL transmits the symbol definition which is stored in successive memory addresses in the SYMBOLS MEMORY 1306 under the control of the SYMBOLS COUNTER 1308. The last portion of the definition is a special code indicating "end of symbol". Storage of the definition of the symbol designated by the character I in FIG. 12 requires a starting address for each of the nine definitions required to construct the nine possible symbols. These definitions are:

Reading of a symbol definition from the symbols memory is initiated by an instruction from DSPL commanding that the definition designated by a character transmitted to the data input register be transmitted to DSPL. In the case of a symbol not formed from other symbols, the data defining this symbol is read from the symbols memory address designated by the SYMBOLS STACK 1307 for the transmitted character. This data is then transmitted by the DATA OUTPUT REGISTER 1304 to DSPL.

In the case of a symbol formed from other symbols, the first character designating this symbol is transmitted to DSPL and the address of the location in the symbols memory following the last location accessed is stored in an auxiliary address location in the SYMBOLS STACK 1307. If the original symbol requested by DSPL is F, for example, the character read would be A and the location in the symbols memory following the last one accessed would contain the character B. DSPL next commands SYM to read the contents of the symbols memory location designated by A and the data defining the symbol designated by A is transmitted to DSPL. Following this transmission, the CONTROL LOGIC 1305 causes a count in the STACK COUNTER 1309 to be referenced. This count indicates the number of auxiliary addresses that have been stored in the SYMBOLS STACK 1307 during readout of information. The count following readout of F is incremented to 1. This is now decremented to 0 and the data defining B is read from the symbols memory location designated by the auxiliary address in the SYMBOLS STACK 1307. The STACK COUNTER 1309 will then transmit a SYMBOL END signal to the CONTROL LOGIC 1307 which indicates to DSPL by transmission of the condition signal SYM-COND-DSPL the end of symbol. Two other conditions may also be transmitted to DSPL in this manner. The first condition is STACK OVERFLOW indicating that the number of auxiliary addresses in the symbols stack is insufficient for storing the number of addresses attempted. The second condition is SYMBOLS ERROR indicating that the last symbol information stored in the symbols memory exceeded the available memory locations.

A detailed description of the implementation of an exemplary SYM is now given.

The SYM accepts 16-bit instructions from the DSPL with bit format illustrated in FIG. 66. The OPCODE portion of the instruction defines what type of operation is to be performed whereas the DATA portion of the instruction provides data which may be used with that operation.

In the application as a symbol processor, the PMEM provides three fundamental data structures for the symbol readout process:

(1) a linear array of character data representing the definition of a multiplicity of symbols,

(2) an address stack which is used for saving subsymbol return points, and

(3) a symbol name lookup table memory which holds the starting address for each symbol.

The combination of these data structures allows all the addressing for a symbol set to be performed entirely within the SYM and thus DSPL is not required to supply the address of any specific data items. Instead, DSPL uses the instruction ADVANCE in SYM to access the next character from the symbol definition string, a combination of the RDROW, STROW, PUSPS instructions to save an address on the address stack and a combination of the instructions REPROW, REPCOL POPS to cause the symbol return address or initial symbol address to be restored to a value previously stored on the address stack.

In this section, the circuit level operation of the SYM is described using detailed block diagrams of FIGS. 67-71.

The instruction interface control circuitry is illustrated in FIG. 67. Operation of the SYM begins when the DSPL-RQ-SYM signal becomes active. If SYM is currently active, operation waits until it becomes inactive from the previous instruction. Once SYM becomes inactive, gate 6701 is enabled and on the next CLOCK the SYM-ACTIVE flip-flop 6704 is set. SYM-ACTIVE allows the PHASE COUNTER 6705 to count on each CLOCK PULSE. As the PHASE COUNTER counts, the PHASE-DECODE devices generate the four pulses P1, P2, P3 and P4, in that order. On the occurrence of pulse P4, the K input to the ACTIVE flip-flop is enabled and the flip-flop is reset, completing the instruction execution. The pulses P1, P2, P3 and P4 are used to control the operations unique to each instruction. The relative timing of these operations are illustrated in FIG. 71 as the COMMON TIMING for all instructions executed for SYM.

Each SYM instruction is executed by performing a set of micro-instructions which are determined by the OPCODE of the instruction. FIG. 68 illustrates the circuitry for the OPCODE register and the MICRO-CODE GENERATOR. The OPCODE REGISTER 6801 is loaded by the same clock pulse which sets the ACTIVE flip-flop as illustrated by the LOAD-OPCODE line in timing diagram FIG. 71. SYM ROM's 1 and 2, 6802, 6804 (defined in detail in APPENDIXES OO and PP), generate the enable signals defining what micro-operations are to be performed. The BUS-ADD signals constitute a three-bit word which selects which of the registers and memories in the SYM is to be used for data on the SYM-DATA 6805 bus. The BUS ADDRESS DECODER 6803 insures that only one data source is on the bus at a time. The other ROM enables are used in conjunction with the P1, P2, P3 and P4 pulses to load registers, write memories, count counters and so forth for the different input instructions. The definition of enables for the different OPCODES are defined in APPENDIXES OO and PP.

Data flow within the SYM is accomplished by a tri-state bus. The DATA REGISTER 6806 on FIG. 68 may be loaded with the DSPL-DATA portion of the input instruction if the enable LOAD-DREG and SELECT-INPUT signals are generated by the MICRO-CODE GENERATOR 6802, 6803 for a given instruction. The DATA REGISTER may also be loaded from any other source on the DATA-BUS 6805. The SYM-DATA signals out of the processor reflect the current contents of the DATA-REGISTER when the SYM is not active (between instructions).

The principal part of the SYM in the DATA MEMORY 6901 illustrated in FIG. 69. This memory allows storage of 2048 eight-bit words. Each location in this memory may be written or read by different input instructions. The 11-bit address for this memory is generated by the MEMORY ADDRESS COUNTER 7001 illustrated in FIG. 70. The memory address word is broken up into two fields as follows:

Bits 0-5 COLUMN ADDRESS

Bits 6-11 ROW ADDRESS

The MEMORY ADDRESS COUNTER 7001 allows the COLUMN and ROW address parts to be loaded separately and allows the current COLUMN COUNT (PCOL) and ROW COUNT (PROW) to be separately read onto the DATA-BUS through the bus drivers 7002 and 7003. The parts of the MEMORY ADDRESS COUNTER count up and count down as a single counter.

The location of different data items in the DATA MEMORY may be saved for subsequent relocation of the MEMORY ADDRESS COUNTER by the ADDRESS STACK illustrated in FIG. 70. The ADDRESS STACK may be used either as an address return stack or as an address lookup table or both concurrently. The ADDRESS STACK consists of an up/down counter 7004 and an ADDRESS STACK MEMORY 7005. Each value of the STACK POINTER COUNTER 7004 may access either a stack row address or column address in the ADDRESS STACK MEMORY depending upon whether the SELECT-MROW or SELECT-MCOL micro-code enables are present.

For use as a return stack, the operation is as follows. To save an address, the STACK POINTER COUNTER is incremented by a PUSHS instruction and the row and column data written into the current address indicated by STACK POINTER COUNTER by the STROW and STCOL instructions. To return the stack address, the MEMORY ADDRESS COUNTER is loaded by the REPROW and REPCOL instructions after which the STACK POINTER COUNTER is decremented by a POPS instruction.

For use as a lookup table, the stack pointer is loaded into the STACK POINTER COUNTER by a SETS instruction after which the REPROW and REPCOL instructions are used to take the address from ADDRESS STACK MEMORY and put that address into the MEMORY ADDRESS COUNTER.

When the ADDRESS STACK is used for both a lookup table and a return address stack, the STACK POINTER COUNTER may be read and restored at the times which the dual usage might invalidate the current contents of the STACK POINTER COUNTER.

As shown in FIG. 67, the SYM generates three conditions which may be monitored by the DSPL to allow looping of operation. The STACK-OVER signal is generated when the STACK POINTER COUNTER issues the MAX-COUNT signal which sets F-F 6707. This condition denotes that there is no more room in the stack memory for addresses. This condition remains set until the stack pointer is decremented or the PRESET instruction is executed.

The STACK-END signal denotes that the stack is empty and is generated when the STACK POINTER COUNTER issues the MIN-COUNT signal and sets F-F 6708. STACK-END is inhibited if the counter is incremented.

The SYM-OUT signal denotes that the MEMORY ADDRESS COUNTER has overflowed and is set when the PCTR-MAX signal is generated which sets F-F 6709 and is reset when the MEMORY ADDRESS COUNTER is reset.

The SYM NOP instruction is executed when the DSPL OP-CODE sent to the SYM has value 340 (octal). This instruction does not manipulate any data in the processor, as implied by the name "NO-OPERATION", but is useful for maintenance purposes to verify that the processor can accept and execute instructions. Timing for the NOP instruction consists of the common timing signals illustrated in FIG. 71. The sequence of signals is as follows. To initiate the instruction execution, the DSPL-RQ-SYM signal activates gate 6701 and upon the next clock pulse the ACTIVE flip-flop 6704 is set which generates the SYM-ACTIVE signal. The ACTIVE signal allows the PHASE COUNTER 6705 to count and generate in order the four clock phase signals P1, P2, P3 and P4 from the PHASE DECODER 6706. Upon the occurrence of the P4 signal, the ACTIVE flip-flop 6704 is reset. Subsequent instructions may be executed by the processor when the DSPL-RQ-SYM signal is again received.

The PRESET instruction is used to initialize the conditions and memory address counter in the SYM. The time sequence for the PRESET instruction is the same as for the NOP instruction. The STACK-OVER 6707, STACK-END 6708 and SYM-OUT 6709 flip-flops are reset by the PRESET signal output from SYM ROM 6802 which is active for OPCODE 341 (octal). This signal also resets MEMORY ADDRESS COUNTER 7001. The timing for this signal is illustrated by the RESET-PCNTR signal in FIG. 71.

The RESET instruction performs the same functions as the PRESET instruction and, in addition, clears the STACK POINTER COUNTER 7004 by use of the RESET signal from the MICRO-CODE ROM 6804 which is active for OPCODE=342.

The load memory address counter row instruction (LDROW) is used to set the value of the ROW portion of the memory address counter. Timing for this instruction is the same as for the NOP instruction. The value for loading is taken from the DATA REGISTER by enabling that register's data onto the bus by way of the signal SELECT-DATA which is active for this instruction by way of the BUS ADDRESS DECODER 6803 which in turn is given the bus address from the MICRO-CODE GENERATOR 6802. The data is loaded into the ROW portion of the MEMORY ADDRESS COUNTER 7001 by the LOAD-PROW signal which is activated by the combination of the EN-LOAD-PROW from the MICRO-CODE GENERATOR 6804 and clock pulse P4.

The load memory address column instruction operates the same as the LDROW instruction except that the LOAD-PCOL signal is generated instead of the LOAD-PROW signal. This causes the column portion of the MEMORY ADDRESS COUNTER 7001 to be loaded instead of the row portion.

The LOADPM instruction is used to load data into the DATA REGISTER 6806 from the META-DATA input value. Timing for this instruction is the same as the NOP instruction except that the LOAD-D signal is generated as a result of the LOAD-DREG signal being activated by the MICRO-CODE GENERATOR 6802. This signal loads the DATA REGISTER 6806 with the value from the INPUT BUS DRIVER 6804 which is enabled by the SELECT-INPUT signal supplied by the BUS ADDRESS DECODER 6803.

The WRITE instruction is used to load one word (eight bits) of data into the DATA MEMORY 6901 at the current address location defined by the MEMORY ADDRESS COUNTER 7001. The data originates in the DATA REGISTER 6806. For this instruction, the MICRO-CODE GENERATOR 6802 enables the DATA REGISTER 6806 contents onto the DATA-BUS 6805 and activates the EN-WRT-MEM signal to load data into the DATA MEMORY 6901. The WRITE-DATA-MEMORY signal timing is illustrated in FIG. 71.

The READ instruction is used to read the contents of the DATA MEMORY 6901 at the location currently defined by the MEMORY ADDRESS COUNTER 7001 and load that data into the DATA REGISTER 6806. AFter the completion of the instruction, the DATA REGISTER contents are enabled onto the DATA-BUS 6805 so that they can be used by other processors as the SYM-DATA. cl SYM POPP Instruction (OPCODE=350)

The POPP instruction performs the same functions as the READ instruction and, in addition, decreases the address count in the MEMORY ADDRESS COUNTER 7001 by a count of one.

The PUSHP instruction performs the same functions as the WRITE instruction and, in addition, increments the MEMORY ADDRESS COUNTER 7001 by enabling the PCTR-UP signal from the MICRO-CODE GENERATOR 6804.

The ADVANCE instruction is used to read out the next logical word in the DATA MEMORY 6901. The instruction performs the same functions as the READ instruction and, in addition, increments the MEMORY ADDRESS REGISTER 7001 by a count of one.

The repeat row or REPROW instruction is used to load the row portion of the MEMORY ADDRESS COUNTER 7001 from the current row value output of the ADDRESS STACK MEMORY 7005. The instruction performs the same micro-functions as the LDROW instruction except that the data originates in the ADDRESS STACK MEMORY 7005 instead of the DATA REGISTER 6806.

The REPCOL instruction is similar to the REPROW instruction escept that the column portion of the MEMORY ADDRESS COUNTER 7001 is loaded from the column portion of the ADDRESS STACK MEMORY 7005.

The read row (RDROW) instruction is used to load the DATA REGISTER 6806 with the current MEMORY ADDRESS COUNTER 7001 row part. After completion of the instruction, this data may be read by any processor connected to the SYM which may need this information.

This instruction is similar to the RDROW instruction with the exception that the column part of the MEMORY ADDRESS COUNTER 7001 is loaded into the DATA REGISTER 6896.

The store row (STROW) instruction is used to store the current row value from the MEMORY ADDRESS COUNTER 7001 into the row part of the ADDRESS STACK MEMORY 7005 at the location defined by the STACK POINTER COUNTER 7004.

The STCOL instruction stores the current column value from the MEMORY ADDRESS COUNTER 7001 into the column part of the ADDRESS STACK MEMORY 7005 in a manner similar to the STROW instruction.

The PUSHS instruction increments the STACK POINTER COUNTER 7004 allowing the use of different locations in the ADDRESS STACK MEMORY.

Decrements the STACK POINTER COUNTER 7004 allowing accessing to stack address loaded by previous instructions.

The read address stack memory row (RDMSROW) instruction is used to load the DATA REGISTER 6806 with the current row value from the ADDRESS STACK MEMORY 7005.

Performs the same function as the RDMSROW instruction except on the column part of the ADDRESS STACK MEMORY 7005.

The set stack pointer counter (SETSCTR) instruction loads the STACK POINTER COUNTER 7004 from the current contents of the DATA REGISTER 6806. This allows selection of any of the locations in the ADDRESS STACK MEMORY 7005.

The DSPL control processor self-instruction set is similar to that of the SEM control processor. This instruction set is illustrated in APPENDIX II. Additionally, the destination ROM of the DSPL control processor is similar to the distination ROM of the SEM control processor, illustrated in APPENDIX KK.

The display processor DSPL illustrated in FIG. 14 controls SYM, DIU, PROJ and PRNT by issuing code execution level instructions to these processors to carry out code execution, code sequence and program interpretation commands received from FORM. DSPL also acts as a data path between the processors it controls and the FORM and DL processors.

Commands from FORM are in the form of instructions, each having an operation code portion and a data portion. As illustrated in FIG. 14, these portions are latched into an OPERATION INPUT REGISTER 1404 and a DATA REGISTER 1410. The data portion must pass through a DATA INPUT MULTIPLEXER 1409 which is controlled by SOURCE/DESTINATION LOGIC 1405 to selectively pass data from FORM, DL, SYM, DIU and elements internal to DSPL. The instructions to FORM are of two general types--set state and execute state. A set state instruction initializes a SEQUENCE ADDRESS COUNTER 1407 with the starting address in a SEQUENCE MEMORY 1408 of a grammar defining strings of data to be subsequently transmitted to DSPL. An execute state instruction causes DSPL to interpret the subsequently transmitted strings of data by utilizing this grammar. The strings of data may be transmitted by either FORM or DL. The DSPL also has the capability of setting the SEQUENCE COUNTER 1407 to the starting address of a different grammar stored within the SEQUENCE MEMORY 1408 if interpretation of data establishes a need for use of one of the other grammars.

All data and instructions received by and transmitted from DSPL are passed through MULTIPLEXERS 1406, 1409, 1413 and REGISTERS 1404, 1410, 1414, under the control of a MICRO-CODE GENERATOR 1402 which in turn is controlled by clock pulses from the CONTROL LOGIC 1401 and information from the SEQUENCE MEMORY 1408 defining a sequence of operations to be performed. Data defining a starting address in the SEQUENCE MEMORY 1408 can be obtained either from the data transmitted to DSPL or from a location in a STACK MEMORY 1412 at an address specified by the transmitted data. The STACK MEMORY 1412 includes auxiliary addresses and operates with a STACK COUNTER 1411 in a manner similar to operation of the symbols stack and its associated stack counter so that tree-structured addressing of the SEQUENCE MEMORY 1408 is possible.

CONDITION LOGIC 1415 is provided to monitor condition signals transmitted by DIU, PROJ, SYM, and PRNT. This logic also monitors a STACK-END signal from the STACK MEMORY 1412 indicating that the full memory capacity has been utilized.

ACTIVE/REQUEST LOGIC 1403 is provided to transmit request signals to the processors commanded by the DSPL and to monitor active signals from these processors indicating that instructions have been accepted.

Typical operations of the DSPL after interpreting data by use of the grammar specified by the current set state include transmission of an instruction to DIU directing that a particular symbol or character be displayed directing DIU to display a cursor mark. The SYM is referenced by DSPL whenever symbol definitions must be transmitted to DIU. Transmission of codes and addresses to PRNT and PROJ is accomplished by simply passing code and address information received from DL along with an appropriate instruction as described in the descriptions of PRNT and PROJ.

The DSPL control processor is designed to directly process a set of grammars. These grammars describe the sequence of instructions received by the DSPL control processor in order to produce the desired display. These grammars are similar to the META grammar described previously.

An exemplary contrast between two of the several grammars implemented in the DSPL control processor is illustrated below. The initial state is set by instructions from the FORM.

The complete listing of ROM sequences for the DSPL is given in APPENDIX NN.

While the invention has been described with respect to one embodiment thereof, it will be understood by those skilled in the art that changes in form and detail may be made from the described invention without departing from the spirit and scope of the invention.

A. Devices Used To Implement Exemplary External Processors

B. ASCII Character Set

C. SPOML Language Definition

D. GETS Instruction Set Definition

E. OIU Acknowledge Generator ROM 5303

F. OIU Fixed Op-Code ROM 5308

G. OIU Active Request Selector ROM 5401

H. OIU Input Enable ROM 5501

I. INPT ROM Table 1605

J. Devices Used To Implement Exemplary OIU

K. Devices Used To Implement Exemplary INPT

L. META Self Instruction Set

M. META Interpreter Communication Grammar

N. Communication Grammar States and Actions

O. SPOML METAPROCESSOR Grammar

P. SPOML Grammar States and Actions

Q. Self Instruction Sequence Coding for An Exemplary METAPROCESSOR

R. META Multiplexer Select ROM 4301

S. META Multiplexer Select ROM 4501

T. META Source Code ROM 4504

U. META Destination ROM 4401

V. META Micro-Code Generator ROM 4701

W. META Micro-Code Generator ROM 4702

X. META Micro-Code Generator ROM 4703

Y. META Micro-Code Generator ROM 4704

Z. META Micro-Code Generator ROM 4705

AA. META Classifier ROM 4802

BB. Devices Used To Implement An Exemplary METAPROCESSOR

CC. STG Instruction Set Definition

DD. STG Micro-Code Generator ROM 3401

EE. STG Micro-Code Generator ROM 3402

FF. STG Micro-Code Generator ROM 3403

GG. STG Micro-Code Generator ROM 3404

HH. Devices Used To Implement An Exemplary STG

II. SEM Processor Self Instruction Set

JJ. SEM Self Code ROM

KK. SEM Destination ROM

LL. SEM Self Sequence ROM

MM. FORM Self Sequence ROM

NN. DSPL Self Sequence ROM

OO. SYM Micro-Code Generator ROM 6802

PP. SYM Micro-Code Generator ROM 6804

QQ. Devices Used to Implement An Exemplary SYM

RR. DIU Micro-Code Generator ROM 5817

SS. DIU Cursor ROM 6304

TT. Devices Used to Implement An Exemplary DIU

UU. CRT Color Generator ROM

VV. References and Patent References ##SPC1## ##SPC2## ##SPC3## ##SPC4## ##SPC5## ##SPC6## ##SPC7## ##SPC8## ##SPC9## ##SPC10## ##SPC11## ##SPC12## ##SPC13## ##SPC14##

Aho, A. V., and Ullman, J. D., "The Theory of Parsing, Translation, and Compiling", Prentice-Hall, Inc., Englewood Cliffs, N.J., 1972

Anderson, G. A., and Jensen, E. D., "Computer Interconnection: Taxonomy, Characteristics, and Examples", ACM Computing Surveys, Vol. 7, No. 4, December 1975

Bell, C. G., and Newell, A., "Computer Structures: Readings and Examples", McGraw-Hill, New York, 1971

Coffman, E. G., Jr., Elphick, M. J., and Shoshani, A., "System Deadlocks", ACM Computing Surveys, Vol. 3, No. 2, June 1971

Enslow, P. H., Jr., Ed., "Multiprocessors and Parallel Processing", John Wiley and Sons, New York, 1974

Foster, Caxton C., "Computer Architecture", Van Nostrand Rheinhold Co., New York, New York, 1970

Griswold, R. E., and Griswold, M. T., "A SNOBOL 4 Primer", Prentice-Hall, Inc., Englewood Cliffs, N.J., 1973

Hopcroft, J. E., and Ullman, J. D., "Formal Languages and their Relation to Automata", Addison-Wesley Co., Reading, Mass., 1969

Joseph, E. C., "Innovations in Heterogeneous and Homogeneous Distributed Function Architectures", IEEE Computer Magazine, March 1974

Korfphage, R. R., "Discrete Computation Structures", Academic Press, Inc., New York, 1974

Lewis, P. M., II, Rosenkrantz, D. J., and Stearns, R. E., "Compiler Design Theory", Addision-Wesley Co., Reading, Mass., 1976

Lewis, P. M., II, and Stearns, R. E., "Syntax Directed Transduction", JACM, Vol. 15, No. 3, July 1968, pp. 465-488

Rupp, Charle R., "A Class of Multiple Processor Computers with Grammar Directed Control", copyright 1976 by Author, published by University Microfilms, Ann Arbor, Mich.

Rupp, Charle R., "A Stand-alone CAI System Based on Procedural Grammars", IEEE EASCON, Fall 1976

Rupp, Charle R., and Glorioso, R. M., "A Design Approach for Multiple Processor Computers", Chapter 2 in the book "Microcomputer Design and Applications", Samuel C. Lee, Editor, c. 1977, Academic Press, Inc., New York, N.Y.

Rupp, Charle R., and Glorioso, R. M., "Grammar Based Multiple Processor Design", IEEE Micro-Computer Conference Record, c. 1977, IEEE Publication 77CH1185-8, Long Beach, Calif.

Weissman, Clark, "LISP 1.5 PRIMER", Dickenson Publishing Company, Belmont, Calif. 1967

Amdahl, L. D., et al, "Modular Computer System Disconnect Capability", U.S. Pat. No. 3,226,689, issued Dec. 28, 1965

Belle Isle, Albert P., "Data Processing System Having Pyramidal Hierarchy Control Flow", U.S. Pat. No. 3,962,685, issued June 8, 1976

Belser, Karl A., "Method and Apparatus for Point Plotting of Graphical Data from a Coded Source into a Buffer and for Rearranging that Data for Supply to a Raster Responsive Device", U.S. Pat. No. 3,973,245, issued Aug. 3, 1976

Christensen, Carl, "Computer Graphics System", U.S. Pat. No. 3,534,338, issued Oct. 13, 1970

Dinman, Saul B., "Direct Function Processor", U.S. Pat. No. 3,631,401, issued Dec. 28, 1971

Mellen, Gregory E., et al, "Task Control", U.s. Pat. No. 3,530,438, issued Sept. 22, 1970

Perpiglia, Frank J., "Large Scale Multi-Level Information Processing System Employing Improved Failsafe (sic) Techniques", U.S. Pat. No. 3,905,023, issued Sept. 9, 1975

Rehhauser, Frederick V., et al, "Information Processing System Implementing Program Structures Common to Higher Level Program Languages", U.s. Pat. No. 3,665,421, issued May 23, 1972

Wahlstrom, Sven E., "Electronically Controlled Microelectronic Cellular Logic Array", U.S. Pat. No. 3,473,160, issued Oct. 14, 1969