Transition machine--a general purpose computer

Abstract

A general purpose computing machine utilizing a hardware executive system controller for reducing software system overhead. The computing machine has a uniprocessor embodiment which enhances system throughput and a multiprocessor embodiment which may be tailored to achieve a high level of concurrent processor operation. The computing machine utilizes a novel programming structure tailored to the machine architecture by separating data transformation tasks from control statements and performing the data transformation task at the processor level while performing the control task in the hardware executive.

Claims

What is claimed is:

1. A hardware executive apparatus for use in a multiprocessing system for concurrent operation of a plurality of data processors for solving an algorithm by a plurality of application programs and a control program, said data processors connected for accessing application program memory storage means for storing said application programs and data memory storage means for storing data associated with said application programs, said data memory storage means including at least a common data memory area accessible by said plurality of data processors, said plurality of data processors including means for generating variable status indications determined variably upon execution of said application programs, said hardware executive apparatus connected to said plurality of data processors and executing said control program and comprising:

(a) a status storage means for storing current status indications S.sub.j corresponding to data conditions defined on elements of a data set appropriate for determining eligibility of the application programs, whereby said stored status indications correspond to data conditions which are relevant for enabling execution of application programs by said plurality of processors which are utilized in solving said algorithm;

(b) relevance storage means for storing groups, i, of relevance indications R.sub.ij each group corresponding to the relevance of said status indications to the i.sup.th one of said application programs where i is an integer designating one of said groups and corresponding one of said application programs and j is an integer designating one of said status indications;

(c) means connected to said status storage means, and connected to receive said variable status indications from said data processors for updating said current status indications stored in said status storage means at the completion of execution of said application programs, each of said variable status indications having one value corresponding to and indicating satisfaction of a given one of said data conditions, and another value corresponding to and indicating non-satisfaction of said given one of said data conditions, said given data conditions being logical relationships involving at least one element of said data set, the value of said at least one element of said data set being determined by said data processors upon execution of said application programs, said updating means including means for modifying a plurality of said current status indications in response to completion of execution of at least one of said application programs;

(d) means connected to said relevance storage means and said status storage means for determining the eligibility of said application programs for execution by said plurality of processors; and

(e) means responsive to said eligibility determining means and operatively connectable to said data processors for enabling execution of eligible application programs by said plurality of data processors whereby at least some of said application programs which are determined eligible may be executed concurrently.

2. A hardware executive apparatus as recited in claim 1, wherein said status storage means comprises a status register having bit storage positions corresponding to said current status indications.

3. A hardware executive apparatus as recited in claim 2, wherein each bit storage position of said status storage register corresponds to one current status indication.

4. A hardware executive apparatus as recited in claim 3, wherein said relevance storage means comprises a relevance matrix storage means wherein said groups form rows (columns) of said matrix storage means and individual relevance indications form columns (rows) of said matrix, each column (row) corresponding to one of said status indications on said data set.

5. A hardware executive apparatus as recited in claim 1 or 4, wherein said means for determining the eligibility of application program i comprises means for multiplying each status indications S.sub.j with each corresponding relevance indication R.sub.ij to form a logic state.

6. A hardware executive apparatus as recited in claim 5, wherein said application program eligibility determining means further comprises logic means for requiring the results of each multiplication to be a predetermined logic state whereby application program i is determined eligible if all current status indications S.sub.j corresponding to relevant indications R.sub.ij are in said predetermined logic state.

7. A hardware executive apparatus as recited in claim 6, wherein said means for updating said status indications comprises:

(a) means responsive to said data processors for sensing the completion of execution of each application program;

(b) means for storing fixed status indications (T,F) associated with each application program i, said fixed status indications determined by said algorithm independently of values associated with said data set;

(c) means for storing said variable status indications received from said data processors; and

(d) said means for modifying including logic circuit means responsive to said stored current status indications, said fixed status indications and said variable status indications for generating update current status indications, said logic circuit means connected to said status storage means for storage of said update current status indications in said status storage means.

8. A hardware executive apparatus as recited in claim 7, wherein said fixed status indications (T,F) are stored in a matrix storage means, each row (column) thereof corresponding to one of said application programs, and each column (row) thereof corresponding to one of said status indications S.sub.j, and said means for storing said variable status indications comprises a storage register V having bit positions corresponding to said current status indications of said status storage means.

9. A hardware executive apparatus as recited in claim 8, wherein said means for enabling execution of said eligible application programs comprises a plurality of entry-point address storage means for defining entry-point execution addresses for said application programs and a plurality of data access pointers corresponding to each of said application programs.

10. A hardware executive apparatus as recited in claim 9, wherein said entry-point address storage means comprises storage registers.

11. A hardware executive apparatus as recited in claim 9, wherein said apparatus further comprises an index register for storing application program identification data, said updating means responsive to said application program identification data of said index register for identifying said application program i.

12. A hardware executive apparatus as recited in claim 1, wherein said means for updating said status indications comprises:

(a) means responsive to said data processors for sensing the completion of execution of each application program;

(b) means for storing fixed status indications (T,F) associated with completion of each application program i, said fixed status indications determined by said algorithm independently of values associated with said data set;

(c) means for storing said variable status indications; and

(d) said means for modifying including logic circuit means responsive to said stored current status indications, said fixed status indications and said variable status indications for generating update current status indications, said logic circuit means connected to said status storage means for storage of said updated current status indications in said status storage means.

13. A hardware executive apparatus as recited in claim 12, wherein said fixed status indications are stored in a matrix storage means, each row (column) thereof corresponding to one of said application programs, and each column (row) thereof corresponding to one of said status indications S.sub.j, and said means for storing said variable status indications comprises a storage register V having bit positions corresponding to said status indications of said status storage means.

14. A hardware executive apparatus as recited in claim 13, wherein said means for enabling execution of said eligible application programs comprises a plurality of entry-point address storage means for defining entry-point execution addresses for said application programs and a plurality of data access pointers corresponding to each of said application programs.

15. A hardware executive apparatus as recited in claim 14, wherein said entry-point address storage means comprises storage registers.

16. A hardware executive apparatus as recited in claim 15, wherein said apparatus further comprises an index register for storing application program identification data, said updating means responsive to said application program identification data of said index register for identifying said application program i.

17. A hardware executive apparatus as recited in claim 1, wherein said means for enabling execution of said eligible application programs comprises a plurality of entry-point address storage means for defining entry-point execution addresses for said application programs and a plurality of data access pointers corresponding to each of said application programs.

18. A hardware executive apparatus as recited in claim 17, wherein said entry-point address storage means comprises storage registers.

19. A hardware executive apparatus as recited in claim 18, wherein said apparatus further comprises an index register for storing application program identification data, said updating means responsive to said application program identification data of said index register for identifying said application program i.

20. A hardware executive apparatus as recited in claim 1 wherein said status storage means stores the status of data conditions including the status of at least one of the following conditions:

(a) data available or non-available,

(b) data updatable or non-updatable, and

(c) data satisfies or does not satisfy a logical relationship.

21. A hardware executive apparatus as recited in claim 20 wherein said at least one data condition is the condition that data satisfies or does not satisfy a logical relationship.

22. A multiprocessing computing system for solving a computational problem by execution of a plurality of application programs and a control program, said system comprising:

(a) a plurality of data processors connected for accessing application program memory storage means storing said plurality of application programs and data memory storage means storing data elements, said data memory storage means having at least a data memory area commonly accessible by said plurality of data processors, at least one of said plurality of data processors including means for generating at least one variable status indication determined upon execution of at least one of said plurality of application programs; and

(b) a system controller operable for execution of said control program and including:

(1) a status register for storing status indications of a plurality of data conditions appropriate for said computational problem to be solved by said computing system;

(2) a relevance matrix store for storing indications of the relevance of each data condition to each of said plurality of application programs;

(3) means connected to said status register and responsive to said at least one variable status indication for updating said status indications of said status register, said at least one variable status indication indicating satisfaction of a data condition, said data condition being a logical relationship involving at least one of said data elements, said at least one data element having a value determined by said at least one data processor upon execution of said at least one application program, said updating means including means for modifying a plurality of said status indications in response to completion of execution of one of said application programs;

(4) means for storing a plurality of application program designation addresses corresponding to said plurality of application programs; and

(5) means responsive to said status indications of said status register, said corresponding relevance indications of said relevance matrix store and said application program designation addresses of said application program designation address storing means for determining the eligibility of said plurality of application programs for execution by said plurality of data processors and for generating designation address from said application program designation address storing means for application programs determined to be eligible, wherein eligible application programs are executed concurrently in said plurality of data processors; whereby said system controller forms a hardware executive apparatus for said computing system.

23. A computing system as recited in claim 22, further comprising interface means connected between said plurality of data processors and said system controller.

24. A computing system as recited in claim 23, wherein said interface means comprises an execute register connected to said application program designation address storing means for storing said application program designation addresses generated by said system controller.

25. A computing system as recited in claim 24, wherein said interface means further comprises a busy/not busy binary indicator register for indicating whether the system controller is busy/not busy upon request for access to said system controller by said data processors.

26. A computing system as recited in claim 22, wherein said application programs are event-driven programs without direct transfer of control therein or to other application programs and said status and relevance conditions solely establish the prerequisites for enabling execution of said application program.

27. A computing system as recited in claim 25, wherein said interface means comprises a binary mode indication register (X) loaded by said data processors for identifying entry and exit modes of operation and an index register for storing application program identifying data:

said system controller operable in said entry mode of operation in response to loading of said mode indication register by the k.sup.th one of said plurality of data processors for determining eligibility of the i.sup.th one of said plurality of application programs for execution by said k.sup.th data processor and for generating an application program designation address corresponding to said i.sup.th application program for storage in said execute register of said interface means for loading by said k.sup.th data processor whereby said k.sup.th data processor executes said i.sup.th application program; and

said system controller operable in said exit mode in response to loading of said mode indication register by said k.sup.th data processor for receiving said application program identifying data of said i.sup.th application program loaded by said k.sup.th data processor into said index register of said interface means for enabling said updating means of said system controller to update said status register, wherein k is an integer designating one of said data processors and i is an integer designating one of said application programs.

28. A computing system as recited in claim 27, wherein said system controller further comprises:

means for storing fixed status indications (T,F), said fixed status indications determined by said computational problem to be solved independent of data values of said data elements computed in said k.sup.th data processor; and

said interface means further comprising means for storing said variable status indications (V) associated with completion of said i.sup.th application program, said updating means receiving said fixed status indications and said variable status indications for determining updated binary status indications of said data conditions and for storing same in said status register.

29. A computing system as recited in claim 22, further comprising an interface means connected between said system controller and said plurality of data processors wherein said interface means comprises a binary mode indication register (X) loaded by said data processors for identifying entry and exit modes of operation;

said system controller operable in said entry mode of operation in response to loading of said mode indication register by the kth one of said plurality of data processors for determining eligibility of the i.sup.th one of said plurality of application programs for execution by said k.sup.th data processor and for generating an application program designation address corresponding to said i.sup.th application program for storage in said interface means for loading by said k.sup.th data processor whereby said k.sup.th data processor executes said i.sup.th application program; and

said system controller operable in said exit mode in response to loading of said mode indication register by said k.sup.th data processor for receiving application program identifying data of said i.sup.th application program for enabling said updating means of said system controller to update said status register, wherein k is an integer designating one of said data processors and i is an integer designating one of said application programs.

30. A computing system as recited in claim 29, wherein said system controller further comprises:

means for storing fixed status indications (T,F), said fixed status indications determined by said computational problem to be solved independent of data values of said data elements computed in said k.sup.th data processor; and

said interface means further comprising means for storing said variable status indications (V) associated with completion of said i.sup.th application program, said updating means receiving said fixed status indications and said variable status indications for determining updated binary status indications of said data conditions and for storing same in said status register.

31. A computing system as recited in claim 22, wherein said system controller further comprises a busy/not busy binary indicator register for indicating whether the system controller is busy/not busy upon request for access to said system controller by said data processors.

32. A computing machine operable for transitioning between different states for solving an algorithm and comprising:

(a) data processing means including means for computing data in accordance with application programs and means for generating at least one variable status signal corresponding to other than a program termination event and representing satisfaction of at least one logic condition dependent upon at least one non-predetermined value of data processed by said data processing means;

(b) memory storage means accessible by said data processing means for storing said application programs and for storing data for use with and resulting from execution of said application programs;

(c) hardware executive means operable for scheduling said application programs and comprising:

(i) status storing means for storing indications of the status of a plurality of data conditions including said at least one logic condition which collectively enable execution of said application programs;

(ii) means for storing indications of the relevance of each of said status indications corresponding to each of said application programs;

(iii) means connected to said status storing means and responsive at least to said variable status signal for updating said status indications upon execution of said application programs, said updating means including means for modifying a plurality of said status indications in response to completion of execution of at least one of said application programs; and

(iv) means for enabling execution of said application programs in response to said updated status indications and said corresponding relevance indications.

33. A computing machine as recited in claim 32 wherein said application programs are event-driven programs without direct transfer of control therein or to other application programs and said status and relevance indications solely establish the prerequisites for enabling execution of said application programs.

34. A computing machine as recited in claim 32, wherein said data processing means comprises a uniprocessor.

35. A computing machine as recited in claim 32, wherein said data processing means comprises a multiprocessor.

36. A computing machine as recited in claim 32, wherein said enabling means enables execution of said application programs which have "true" status indications of the data conditions for all relevant relevance indications corresponding to said application programs.

37. A computing machine as recited in claim 32 wherein said status storing means stores the status of data conditions pertaining to data in the data set including the status of at least one of the following conditions:

(a) data available or non-available,

(b) data updatable or non-updatable, and

(c) data satisfies or does not satisfy a logical relationship.

38. A computing machine as recited in claim 37 wherein said at least one data condition is the logical relationship constants.

39. A method of operating a data processing system for executing an algorithm comprising the steps of:

(a) performing data transformation in data processing means in accordance with data transformation programs;

(b) storing said data transformation programs and data input to and output from said data processing means;

(c) scheduling the execution of said data transformation programs in a hardware apparatus by:

(i) storing indications of the status of a plurality of data conditions which collectively enable the execution of said data transformation programs utilized in solving said algorithm;

(ii) storing indications of the relevance of each of said status indications corresponding to each of said data transformation programs;

(iii) generating at least one variable status signal corresponding to other than a program termination event in response to satisfaction of at least one logic condition dependent upon at least one non-predetermined value of data processed by said data processing means;

(iv) updating said status indications in response to said variable status signal by modifying a plurality of said status indications in response to completion of execution of one of said data transformation programs; and

(v) enabling execution of said data transformation programs in response to said status indications including said updated status indications and said corresponding relevance indications.

40. A method of computing as recited in claim 39, wherein said step of enabling execution of said data transformation programs comprises multiplying said status indications and said relevance indications such that data transformation programs are enabled if all relevant relevance indications have associated "true" status indications.

41. A general purpose multi-processing computing machine operable for transitioning between states for solving an algorithm and comprising:

(a) a plurality of data processors each including means for computing data values in accordance with application programs containing operation code designations defining data transformations and including means for generating variable status indications determined variably upon execution of said application programs, each of said variable status indications having one value corresponding to and indicating satisfaction of a data condition, and another value corresponding to and indicating non-satisfaction of said data condition, said data condition being a logical relationship involving at least one element of a data set, the value of said at least one element of said data set being determined by said data processors upon execution of said application programs;

(b) data memory storage means having at least a portion thereof shared by said plurality of data processors;

(c) application program memory storage means for storing said application programs said application programs accessible by said data processor for execution thereof; and

(d) a hardware system controller for scheduling said application programs, said system controller connected to said plurality of data processors and including a relevance matrix storage means for storing relevance indications of each of said data conditions with respect to said application programs and means for determining the eligibility of at least one of said application programs in dependence upon said relevance matrix storage means and said variable status indication corresponding to at least one data condition other than a program termination event, said controller including means for storing status indications of said plurality of data conditions including said at least one data condition, and said controller further including means for modifying a plurality of said status indications upon execution of at least one application program and for enabling operation of different ones of said data processors for concurrent execution of said eligible application programs, whereby the execution and sequence of execution of said application programs is dependent upon said at least one data condition, and thus, on at least one of said data values.

42. A general purpose computing machine as recited in claim 41 wherein said system controller is operable for determining eligibility based on a plurality of unary predicates associated with the applicability of the transitions between states of said machine for solving said algorithm.

43. A general purpose computing machine as recited in claim 42 wherein said application programs are event-driven data transformation programs without direct transfer of control therein or to other application programs.

44. A method of utilizing a hardware executive apparatus and requirements-oriented programming for solving a computational problem comprising the steps of:

(a) structuring the programming of said computational problem to be carried out by said computing system into a plurality of data transformation programs and a control program, said data transformation programs performing event-driven data computational steps and said control program scheduling execution of said data computational steps;

(b) selecting a plurality of data conditions for enabling execution of all of said data transformation programs, forming status indications;

(c) designating all of said data conditions which are relevant for enabling the execution of each of said data transformation programs, said designated data conditions forming a group of relevance indications corresponding to each data transformation program;

(d) storing said data transformation programs in memory storage devices;

(e) storing said control program in said hardware executive apparatus and scheduling said data transformation programs by:

(i) maintaining a memory store of said status indications;

(ii) maintaining a memory store of each group of relevance indications;

(iii) determining eligibility of data transformation programs in response to said status and relevance memory stores wherein a given data transformation program is determined eligible for execution if all status indications which are relevant in the group of relevance indications corresponding to said given data transformation program are in a predetermined logic state;

(iv) enabling said eligible data transformation programs for execution in data processing means;

(v) executing in said data processing means said eligible data transformation programs;

(vi) updating said memory storage of said status indications upon completion of execution of each data transformation program by modifying at least two of said status indications including modifying at least one of said two status indications variably in dependence upon the value of data transformed by said data transformation programs, whereby the execution and sequence of execution of said data transformation programs is data dependent; and

(vii) repeating at least steps (iii) through (vi) until data transformation programs are no longer determined eligible whereby said computational problem is completed.

45. A general purpose hardware executive for use in a multiprocessing computing system having a plurality of data processors operable for executing a plurality of application programs in a parallel mode of operation, said hardware executive connected to said plurality of data processors and comprising:

(a) a data construct section having means for storing:

(i) status indications corresponding to data conditions which are prerequisite to enabling execution of said application programs;

(ii) relevance indications corresponding to indications of the relevance of each of said data conditions to each of said application programs; and

(iii) application program designation addresses transferrable to said data processors and corresponding to each of said plurality application programs;

(b) a status update logic circuit means connected to said data construct section for receiving said status indications and connected to said data processors for receiving variable status indications which are variable and dependent upon data transformations executed by said application programs, said status update logic circuit means connected to said status storing means for providing updated status indications to said status storing means of said data construct section;

(c) an eligibility determination circuit means connected to said data constructs section and responsive to said status indications and said relevance indications for determining the eligibility of said application programs for execution in said data processors; and

(d) a synchronization and control logic circuit connected to said data construct section for selecting groups of said relevance indications corresponding to said application programs for feeding to said eligibility determination circuit means and for selecting application program designation addresses for eligible application programs for transfer of same to said data processors for execution of said application programs.

46. A computing system comprising:

(a) a plurality of data processors connected for accessing application program memory storage means and data memory storage means, said data memory storage means having at least a data memory area commonly accessible by said plurality of data processors;

(b) a system controller including:

(1) a status register for storing binary status indications S.sub.j of a plurality of data conditions j appropriate for determining eligibility of a computational problem to be solved by said computing system, said computing system solving said computational problem by execution of a plurality of application programs stored in said application program memory storage means;

(2) a relevance matrix store for storing binary indications R.sub.ij of the relevance of each data condition j to each application program i;

(3) means responsive to said binary status indications S.sub.j and said data processors for updating at least two of said binary status indications of said status register in response to non-predetermined, data dependent changes of the binary status of at least one of said data conditions upon execution of said application programs;

(4) means for storing a plurality of application program designation addresses corresponding to said plurality of application programs;

(5) means responsive to said binary status indications of said status register, said corresponding binary relevance indications of said relevance matrix store and said application program designation addresses of said application program designation address storing means for determining the eligibility of said plurality of application programs for execution by said plurality of data processors and for generating designation addresses from said application program designation address storage means for application programs determined to be eligible, wherein eligible programs are executed concurrently in said plurality of data processors; and

(6) synchronization and control logic means connected to said eligibility determining means, said relevance matrix store and said application program designation address storing means for synchronizing and controlling operation of said system controller;

whereby said system controller forms a hardware executive apparatus for said computing system; and

(c) interface means connected between said plurality of data processors and said system controller for interfacing operation of said data processors and system controller.

47. A computing system as recited in claim 46 wherein:

(a) said interface means comprises a type register for storing indications of the processor type requesting access to said system controller;

(b) said system controller further comprises a plurality of processor type storage means corresponding to said plurality of application programs, said processor type storage means storing indications of the type of data processor appropriate for executing said corresponding application programs; and

(c) said means for determining eligibility of said application programs comprising means for comparing indications of the data processor type stored in said interface type register with said indications of said data processor type stored in said processor type storage means;

whereby said plurality of application programs may be executed by specific types of said plurality of data processors.

48. A computing system as recited in claim 47 wherein said means for determining the eligibility of application program i comprises:

(a) means for forming the product of each binary status indication S.sub.j with each corresponding binary relevance indication R.sub.ij ; and

(b) logic means for requiring each of said products to be in a predetermined binary state such that application program i is eligible if all status indications S.sub.j corresponding to said relevant indications R.sub.ij are in said predetermined state, and said processor requesting access to said system controller is of the type appropriate for executing said application program.

49. A computing system as recited in claim 46 wherein said relevance matrix store comprises sequentially stored groups i of binary relevance indications R.sub.ij and said synchronization and control logic means sequentially selects groups of indications of said relevance matrix store for feeding same to said eligiblity determining means.

50. A computing system as recited in claim 49 wherein said synchronization and control logic means is operable for restarting said sequential selection of said stored groups i of binary relevance indications after an application program is determined eligible by said eligibility determining means,

whereby the order of said storage of said binary indications in said relevance matrix store provides a priority selection mechanism for said application programs.

51. A computing system as recited in claim 46 further comprising means for preventing execution of the same application program in more than one of said plurality of data processors at the same time.

52. A computing system as recited in claim 51 wherein said execution preventing means comprises means for providing a predetermined status indication S.sub.j in said status register corresponding to those status indications utilized in determining eligibility of an application program currently being executed, whereby other application programs utilizing said predetermined status indications are not determined eligible by said eligibility determining means.

Description

TABLE OF CONTENTS

Field of the Invention

Description of Prior Art

(A) Enhanced Throughput

(B) Programmer Productivity

Summary of the Invention

Brief Description of the Drawings

Detailed Description of the Preferred Embodiments

System Overview

Definition of Transition Machine

Model of Parallel Programs

Procedure Eligibility Determination

System Status Updating

Example Program

Model of Transition Machine Architecture

Example Program Execution

General Implementation Considerations

System Controller Functional Operation-General Description

Interrupts

Detailed Implementation

Processor/System Controller Interface

System Controller Functional Operation-Detailed Description

Entry Transition

Exit Transition

Load Transition

System Controller Detailed Component Design

Data Constructs

Procedure Eligibility Determination Logic

System Controller Detailed Component Design (continued)

System Status Update Logic Circuit

Synchronization and Control Logic Circuit

System Controller Internal Operation

Single Processor Transition Machine Architecture

Entry Transition

Exit Transition

Load Transition

Selected Alternate Implementation of the System Controller

System Controller to Support a Conventional Operating System

Functional Operation

Entry Transition

Load Transition

Appendix A

Appendix B

Appendix C

BACKGROUND OF THE INVENTION

1. Field of the Invention

The invention is in the field of computer architecture and more particularly in the areas of parallel computers and multiprocessing systems. The invention enhances throughput via hardware support for parallel processing and operating system efficiency. Programmer productivity is also enhanced using a hardware supported unique software structure.

2. Description of the Prior Art

A. Enhanced Throughput

Parallel processing has been recognized as a valuable mechanism for increasing computational speeds by performing concurrent or parallel computations. Various degrees of parallelism have been achieved in computers having both single and multiple processing units. These prior art approaches to the concurrency objective may be categorized into three broad areas: (1) implementation on a multitasking basis in a sequential processor, where concurrent processing paths are assigned priorities and compete for single stream resources; (2) implementation using special purpose hardware with multiple processors based on the concurrency requirement of the problem; and (3) implementation using a general purpose multiprocessor with a multiprocessing operating system to control it.

In the single processor multitasking solution, a single processor and its associated resources are time shared by programs running "concurrently" under the control of a multitasking operating system. The processor is required to provide (over any appreciable period of time) the processing power sufficient to accommodate the requirements along all paths plus the software overhead to multiplex between paths. In addition to assuring that all paths can be accommodated over any appreciable time interval, assurance must be provided for meeting the response time of each path in a worst case concurrency situation. The problems of meeting these requirements are compounded by operating system efficiency considerations. As a consequence, the processors must be sized to the specific problem with the capability of modular extentions typically not being accommodated other than by oversizing the processor to begin with.

In the special purpose multiprocessor approach, a computer is constructed based on a specific concurrency requirement. Examples of special purpose parallel computers that have been built are array processors such as the ILLIAC IV, STARAN I, SOLOMON II. These computers require large amounts of special purpose hardware, special programming structures, and are specially suited for problems involving large amounts of homogeneous parallelism such that identical operations are to be performed on multiple data items. Array processors allow multiple identical operations to be performed in parallel, thereby supporting the concurrency requirement. However, homogeneous parallelism represents a very small part of the parallelism present in computer programs, and therefore these special purpose computers are not typically suited to support the more general heterogeneous parallelism present in typical computer programs.

The multiprocessor with a multiprocessing executive is an attempt at a general solution which accommodates heterogeneous parallelism in modular increments. These solutions, however, are fraught with increasingly diminishing returns as the number of processors is increased. The reasons for the reduction in computing gain in a multiprocessor system are two fold: first, there is a large overhead associated with the software implementation of the single unified control mechanism in the operating system, and secondly, it is difficult to effectively exploit the high level (job or task) of parallelism in application programs.

These two problems have aggravated each other since the large overhead has been taken as the justification for the high level modeling of parallelism but by exploiting parallelism at the job or task level, much of the potential gain of multiprocessing is lost since typically there is some amount of parallelism within the job or task and this internal parallelism cannot be exploited.

B. Programmer Productivity

Programmer productivity has been cited as a major cost problem on automated data processing (ADP) systems. Software development and maintenance costs have continued to climb in the same era of drastic reductions in hardware costs. Structured programming and other disciplines have been defined to reduce the problem. Unilateral agreement among proponents of these disciplines seems to exist in four areas of concern relating to the structure of programs and the computer architectures to which they apply:

(1) a requirements-oriented structure;

(2) a structure for which only the essential aspects of program control must be specified by the programmer;

(3) a structure which eliminates transfers of control (GO TO, CALL, queueing requests, etc.); and

(4) a structure which simplifies the error-prone aspects of decision logic.

The significance of each of these requirement areas is discussed below.

Requirements-oriented Programming

The specification of program requirements and the translation of these requirements into program design data is a major program development activity. One reason that these development activities require such a large percentage of the overall development process is because of the incongruities between the typical situation/response nature of program requirements and the procedural implementation of these requirements in the final design. Thus, there is a major translation from requirement to design which is a timeconsuming, error-prone process. Once the design has been established and implemented, it no longer resembles the structure of the requirements. The gulf between requirements and program design in conventional architectures hampers program understandability and therefore documentation, maintainability, etc. Thus, it is typically impossible to verify that a program of any magnitude actually implements its requirements.

Elimination of Degeneracy

In the conventional software framework the programmer typically translates the computation requirements into a somewhat arbitrary sequence of actions to be performed by the machine. In many cases, however, there is no sequence of actions implied in the requirements, so a sequence is artifically induced by the programmer. Thus, variant "correct" program versions can exist with entirely different structures. These programs are degenerate solutions to the problem described by the requirements specification. In essence the programmer has the ability to induce his own design philosophies and personal preferences into what would idealy have been an objective translation of a requirement that could have been directly compared with other versions. This design indeterminacy has the effect of making the implementations less directly relevant to the requirements such that verification must be performed only at the lowest level to determine that the final result does in fact meet the requirement.

Exploitation of the parallelism inherent in the computation is also precluded by arbitrary determination of execution sequence. This arbitrary determination reduces program effectiveness in parallel processing environments. The inherent relationships between program segments is also obscured such that later program maintenance is more likely to induce errors.

Thus, by requiring only the essential aspect of program control, the requirement translation process is simplified, many of the previously arbitrary decisions on sequence made by the programmer are eliminated, and exploitation of parallelism is supported.

Eliminating Direct Transfers of Control

The direct transfer of control is recognized as the major source of programmer coding errors. Many of the developments in software engineering have been directed to the elimination of these structures from programs. The result has enhanced software productivity, but since these structures are still supported to varying degrees in compilers, and unilaterally at the machine level, many errors can still be attributed to them. Conventional executive requests to execute a specified program are also GO TO's, the only difference being that they are implemented at a high level.

The executive request problem is an interesting one in that a program could be completely correct but not be executed under the right conditions because it was incorrectly requested. Thus, there is an intricate coupling between programs. There is also the possibility of a totally unsuspected program requesting the execution of a program for a completely inappropriate situation. Therefore, before a program can be completely verified to meet its requirements every set of conditions under which it can be requested must be known.

Simplification of Decision Logic

The elimination of GO TO's is significant from an error-proneness point of view, but decision logic structures are very major offenders also. Decision diagramming has been used to address some of the error proneness of these logic structures, but they are a monitoring and evaluation tool not implemented as a part of the program structure in the design, and thus their use constitutes a divergence (additional effort) from the central development path.

The typical decision logic constructs involve a transfer of control which therefore allows circumvention of GO TO-less dogmas at the detailed implementation level. They also have the feature of treating program activation conditions as disjoint, without global awareness. A particular test for a<b, for example, may only be executed if a>c, d<e . . . . But this total situation is not readily apparent to the programmer writing/reviewing the code. Therefore, very complex meshes of logic may be implemented to provide assurance of the specific conditions of execution which, because of a decision higher in the structure, preclude a program's ever being executed.

SUMMARY OF THE INVENTION

It is an object of the invention to overcome the disadvantages of the prior art by providing a hardware executive apparatus incorporating an event-driven structure for use with a uniprocessor or a multiprocessing system.

Another object of the invention is to provide improved throughput of a computing system by eliminating software overhead functions and incorporating same into a hardware implementation. The hardware implementation incorporates the utilization of a system status vector and a relevance matrix. The status vector and relevance matrix are utilized for enabling data transformations in a multiprocessing environment resulting in a high level of concurrent operation.

In accordance with another aspect of the invention, there is disclosed a computation structure for which there is a direct traceability to requirements. As a consequence, the invention achieves a tremendous increase in programmer productivity. Requirements are typically of the form: "When a certain `situation` arises, perform an `associated function`." `Situations` are typically describable in terms of sets of conditions on parameters which are represented in the data base. The `associated functions` correspond to programs which change parameter values.

Yet another object of the invention is to provide a computing architecture having a data transformation aspect and a central control aspect thereby providing a structured computational environment for enhancing program use, development, documentation and verification. The central control aspect of the computational structure is characterized by WHEN statements involving a plurality of data conditions in the form of unary predicates on the data set. When the WHEN conditions are met, a data computation is enabled for execution in the data processor. In a multiprocessing system, a plurality of data transformations may be enabled for concurrent execution thus resulting in highly parallel system operation. The WHEN block structure is implemented in hardware which results in low overhead at the architectural level.

In accordance with the invention there is provided a hardware executive apparatus for use in a multiprocessing system for the concurrent operation of a plurality of data processors in solving an algorithm defined by a plurality of application programs and a control program. The data processors access application program memory storage means and data memory storage means and have at least a common data memory area accessible by the plurality of data processors. The hardware executive apparatus executes the control program and comprises a status storage means for storing global binary status indications S.sub.j of a data set appropriate for solving the algorithm. The stored status indications correspond to data conditions which are relevant for enabling execution of application programs by the plurality of processors which are necessary in solving the algorithm. The hardware executive apparatus additionally comprises a relevance storage means for storing groups i of binary relevance indications R.sub.ij, each group corresponding to the relevance of the status indications to the i.sup.th one of the application programs where i is an integer designating one of the groups and corresponding to one of the application programs and j is an integer designating one of the binary status indications. The hardware executive apparatus additionally comprises a means for updating the status indications stored in the status storage means at completion of execution of each application program, a means responsive to the relevance storage means and status storage means for determining the eligibility of the application programs for execution by the plurality of processors, and means for enabling execution of eligible application programs by the plurality of processors whereby application programs which are determined eligible may be executed concurrently.

The invention may also be characterized as a computing machine capable of transitioning between states for solving an algorithm and comprising a plurality of data processors each including computing means for computing data in accordance with an application program, data memory storage means having at least a portion thereof shared by the plurality of data processors, application program memory storage means for storing said application program, a hardware system controller operable for determining the eligibility of each of the application programs and for enabling operation of different ones of the data processors for concurrent execution of the eligible programs, and wherein the system controller is operable for determining eligibility based on a plurality of unary predicates associated with the applicability of the transition between states of said machine for solving said algorithm.

In accordance with another aspect of the invention, there is disclosed a method of increasing program throughput in a plurality of data processors forming a computing system comprising the steps of: (a) structuring the programming of an algorithm to be carried out by the computing system into a plurality of data transformation programs and a control program, the data transformation programs performing event-driven data computational steps without transfer of control to other transformation programs and the control program scheduling execution of the data computational steps, (b) selecting a plurality of unary predicates which collectively represent all data conditions relevant to enabling execution of all of the data transformation programs, the unary predicates forming status indications of said data conditions, (c) designating all of said unary predicates which are relevant to enabling the execution of each of the data transformation programs, the designated unary predicates forming a group of relevant indications corresponding to each data transformation program, (d) storing the data transformation programs in memory storage devices accessible by said plurality of data processors, and (e) storing the control program in a hardware executive apparatus. The hardware executive apparatus is effective for scheduling data transformation programs by including the steps of: (1) maintaining a memory store of the status indications, (2) maintaining a memory store of each group of relevance indications, (3) determining the eligibility of data transformation programs by hardware logical operations on the status and relevance memory stores wherein a data transformation program is determined eligible for execution if all status indications are true which are relevant in the group of relevance indications corresponding to the data transformation programs, (4) enabling the eligible programs wherein concurrently eligible data transformation programs are executed concurrently, (5) updating the memory store of the status indications upon completion of execution of each data transformation program, and (6) repeating steps (3)-(5) above until data transformation programs are no longer determined eligible whereby the algorithm is completed by the computing system.

BRIEF DESCRIPTION OF THE DRAWINGS

These and other objects of the invention will become clear in reference to the foregoing specification taken in conjunction with the drawings wherein:

FIG. 1 is a block diagram of the transition machine in accordance with the invention;

FIG. 2 is an illustration of the primary data constructs utilized in the system controller in accordance with the invention;

FIG. 3 illustrates an example program utilized in explaining the programming aspect of the transition machine in accordance with the invention;

FIG. 4 illustrates a conventional request driven program for solving the example problem of FIG. 3;

FIGS. 5A and 5B illustrate a request and event-driven program for solving the problem of FIG. 3;

FIG. 6 is a listing of an event-driven program for solving the problem illustrated in FIG. 3;

FIG. 7 is a program listing for an event-driven program with only assignment statements solving the program illustrated in FIG. 3;

FIG. 8 is a program listing for the transition machine program in accordance with the invention for solving the problem illustrated in FIG. 3;

FIG. 9 is an example of a partial program listing corresponding to FIG. 8 and illustrating requirements oriented programming techniques;

FIG. 10 is a table listing of control and data transformation programs corresponding to the requirements oriented programming technique of FIG. 9;

FIG. 11 is a mathematical representation of the major components and operation of the transition machine architecture in accordance with the invention;

FIG. 12 is an illustration of the R, T and F matrices corresponding to solving the example program in accordance with the invention;

FIG. 13 is a flow diagram that shows that various system states of the data constructs during execution of the example program;

FIG. 14 is a block diagram illustrating the data constructs of the transition machine together with basic elements of the interface in accordance with the teachings of the invention;

FIG. 15 illustrates a block diagram of the read, write and execute functions in accordance with the invention;

FIG. 16 shows a flow chart for the operation of a data processor and the system controller during various modes of operation of the transition machine;

FIG. 17 is a flow chart illustrating the interrupt operation in accordance with the invention;

FIG. 18 is an overall block diagram of the major components of the transition machine structure in accordance with the invention;

FIG. 19 is a block diagram of the multiport control aspect forming one embodiment of the transition machine;

FIG. 20 is a flow chart of the operation of the multiport control system of FIG. 19;

FIG. 21 is a flow chart showing the processor entry and exit operations in accordance with the invention;

FIG. 22 is a flow chart showing the processor load operations in accordance with the invention;

FIG. 23 is a flow chart showing the system controller entry, exit and load operations in accordance with the invention;

FIG. 24 is a block diagram of the data construct section of the system controller;

FIG. 25 is a schematic diagram of the procedure eligibility determination logic circuit of the system controller;

FIG. 26 is a block diagram of logic circuit nomenclature utilized in the drawings;

FIG. 27 is a schematic diagram of the system status update logic circuit of the system controller;

FIG. 28 is a block diagram of the input and output lines associated with the syncrhonization and control logic circuit of the system controller;

FIGS. 29A and 29B together form a detailed schematic diagram of the synchronization and control logic circuit of FIG. 28;

FIG. 30 is an illustration of the state diagram for use in implementing the synchronization and control logic circuitry;

FIGS. 31 and 32 are timing diagrams illustrating entry transitions in accordance with the invention;

FIG. 33 is a timing diagram illustrating an exit transition in accordance with the invention;

FIG. 34 is a timing diagram illustrating a load transition in accordance with the invention;

FIG. 35 is a block diagram illustrating the transition machine architecture for a uniprocessor in accordance with another aspect of the invention;

FIGS. 36A and 36B illustrate design language syntax listings describing the operation of the uniprocessor of FIG. 35;

FIG. 37 is a block diagram of a special system controller which supports an operating system in a uniprocessor environment;

FIG. 38 is a flow diagram of the processor logic required to activate the entry transition in the system controller of FIG. 37;

FIG. 39 is a flow diagram of the processor logic required to activate the load transition in the system controller of FIG. 37; and

FIG. 40 is a flow diagram of the system controller logic required to effect the load and entry transitions for the operating system in the processor of FIG. 37.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS

SYSTEM OVERVIEW

Definition of Transition Machines

The family of computational machine architectures described herein implements a completely general model of parallelism. An overall block diagram of a computing system or, as termed herein a transition machine has made in accordance with the invention is shown in FIG. 1. The transition machine is seen to comprise a plurality of processors 2a, 2b, 2c each connected to a common memory 4. While only three processors are shown, it is understood that a large number of processors may be used including I/O controllers and other special purpose processors. (A single processor embodiment is also disclosed herein.) Further, the common memory 4 is typically composed of a plurality of memory modules 6a, 6b, 6c, 6d of which only four are illustrated. Each memory module may provide storage means for data as well as for application programs, or additional memory modules may be provided for such purposes as desired. For the multiprocessor embodiment, however, at least some data storage areas are made commonly accessible to the plurality of data processors. It is also understood that some of the processors may in fact be I/O processors or controllers connected in conventional; and fashion to one or more I/O devices.

A System Controller 10 is shown connected to the processors 2 via a processor/system controller interface 12. The System Controller 10 forms the heart of the invention and is more fully described hereinafter. In practice, the processors 2 and common memory 4 may be of conventional hardware design. The System Controller 10 is utilized, together with interface 12, to dispatch activities to the processors 2 and to achieve concurrent operation of the processors 2, in a multiprocessor system. The System Controller 10 is thus similar in function to a multiprocessor software system executive, but has the advantage of extremely low overhead.

Model of Parallel Programs

The abstract conceptual model of parallel computation is set forth the example in a number of articles by Robert M. Keller e.g. "Formal Verification of Parallel Programs", Comm. ACM 19, 7 (July 1976) pp 371-384; "Parallel Program Schemata and Maximal Parallelism", J. ACM 20, 3 (July 1973), pp 514-537; and J. ACM 20, 4 (October 1973), pp 696-710.

The conceptual model has been termed a transition system and is accepted as the basis for the more detailed architectural model set forth herein. A transition system is a model of the run time structure for computer programs; it is a form into which any "structured" program can be converted directly by a compilation process. The transition machine provides a machine architecture in which transition systems can be executed.

The transition system model is defined as (Q, .fwdarw.), where Q is the set of possible systems states and .fwdarw. is the set of transitions between states as described by Keller. A named transition system is a triple (Q, .fwdarw.,.SIGMA.). The components correspond respectively to the set of all possible system states (q.sub.1, q.sub.2, q.sub.3. . . ), a set of all transitions between states (.fwdarw..sub.1, .fwdarw..sub.2, .fwdarw..sub.3, . . . , ), and a set of names (.sigma..sub.1, .sigma..sub.2, .sigma..sub.3, . . . ) associated with groups of individually programmed transitions between states. Since there is a one-to-one correspondence between the indices on sigma and the names themselves, the indices can be used to indicate the names: i implies.sigma..sub.i, and I.tbd.{i} implies .SIGMA.. The index i .epsilon. I is associated with a group of system transitions described by the statement:

when R.sub.i (d) do d'=.PSI..sub.i (d)

The symbols in this statement are defined as follows:

i=the index of the group of transitions whose common feature is that they all result in the data transformation indicated by the function .PSI..sub.i

d=the set of all data items in the system

R.sub.i (d)=the subset of satisfied propositions on the data set, d which are essential to defining the appropriateness of transitioning as determined by performing the data transformation .PSI..sub.i (d).

.PSI..sub.i (d)=the programmed functional data transformation (referred to as a subsystem herein) associated with the group of system transitions indicated by i which operates on the data set, d and results in a revised data set d'.

The set i represent procedures (including enabling predicate) that can be written by a programmer to effect transformations .PSI..sub.i on the data set d when the appropriate set of conditions R.sub.i is satisfied on that data set. The .PSI..sub.i are the individual program subsystems which constitute a computer program. In a parallel computation step multiple sets of conditions R.sub.i are satisfied simultaneously such that multiple subsystems can be executed in parallel. R.sub.i is an enabling predicate that indicates the requisite status of the data set which properly enables the execution of the subsystem which performs the transformation, .PSI..sub.i. Each of the enabling predicates R.sub.i is made up of a set {R.sub.ij }, j.ltoreq.J of unary predicates where J is the total number of unary predicates required by the entire algorithm or computation problem. A unary predicate may be defined as a single proposition on the data set and thus represents a single data condition whose value may be specified in or by a binary indication, e.g. true or false. Propositions which are examples of unary predicates on the data elements e.sub.j .epsilon.d are the following:

(1) the data element e.sub.j is available/not available for use in subsequent computations,

(2) the data element e.sub.j.sbsb.1 satisfies/does-not-satisfy a specified relation to some constant or other data element e.sub.j.sbsb.2 (for example, e.sub.j.sbsb.1 <e.sub.j.sbsb.2), and

(3) the data element e.sub.j can/cannot be updated.

The implementation of the conceptual model is carried out by reducing control over transitions between states to a mechanical operation. To achieve such control the set of states, Q is restricted such that only those which may imply a different set of eligible subsystems are considered to be unique. In making this restriction any particular state q can be signified by a set of binary status indications on a global set of unary predicates. The global set of unary predicates is restricted to include only those which are relevant to the eligibility of defined subsystems, i.e., the status of the data condition a>b will be a significant part of q if and only if the condition a>b is relevant to the eligibility of some subsystem, i.

Procedure Eligibility Determination

The eligibility of any particular subsystem, i can thus be determined by selecting the set of global unary predicates that are pertinent to initiating execution of the transformation d'=.PSI..sub.i (d), and by determining the status of those pertinent unary predicates. Thus the control over transitioning can be implemented by:

(1) maintaining a variable system status vector S whose components are binary status indications, one for each unary predicate in the global set, and

(2) maintaining for each subsystem, i a relevance vector, R.sub.i of fixed indications for designating which of the global set of unary predicates are relevant for enabling a particular subsystem.

Once the sense of the indications in R.sub.i and S have been defined, there exists a logical algebraic operation, ".multidot." which can be defined such that E.sub.i =R.sub.i .multidot.S, where E.sub.i is a binary status indication of the eligibility of the subsystem, i. The set of vectors, R.sub.i can be arranged as a matrix, R, the i.sup.th row of which is equivalent to R.sub.i. The vector algebraic operation, ".multidot." is then extended to include matrices such that:

E=R.multidot.S,

where

E is a vector indicating the eligibility status of every defined subsystem in the system. The relationship of the data constructs is shown in FIG. 2. A specific set of definitions and theorems relating the sense of the indications in R, S and E and the operations ".multidot." is included as Appendix A.

System Status Updating

There is now a prescription for determining subsystem eligibilities (E vector) based on system status (S vector) and the subsystems' conditional data requirements (R vector). There is now set forth a procedure for the computation of a new system status vector which is appropriate subsequent to the completion of a given subsystem.

There are several possible implications on the status of a data condition at the completion of a subsystem. They are as follows:

(1) The data condition remains unaffected by the subsystem running to completion;

(2) The data condition is satisfied whenever the subsystem runs to completion;

(3) The data condition is negated whenever the subsystem runs to completion; and

(4) The data condition is determined dynamically by the execution of the subsystem.

It should be noted that there are also implied modifications to system status at entry to a subsystem in the preferred embodiments to be described; these modifications prohibit the same transition from being attempted in multiple processors by denying subsequent update access to d' when the transformation d'=.PSI..sub.i (d) is initiated.

The implications to system status at completion of a subsystem is readily accommodated by three data constructs. Two of these are fixed vectors (T and F) indicating respectively the always true (2 above) and always false (3 above) situations. For example, execution of a subsystem which is responsible for computing the value of a variable A would always result in the condition "A available" being set true. A third vector, V, is set dynamically (4 above) by the subsystem based upon the relationship of data variables computed by the subsystems. For example, the subsystem responsible for computing either of the variables A or B would have to return the status of the condition "A>B" upon completion. It is clear that the updated status vector S can be computed as a function of T, F and V. The class of functions can be restricted by overlapping the defined sense of the fixed vectors T and F so as to provide a mask against unauthorized dynamic changes to S through the V vector. Appendix B provides a specific definition of the sense of T, F and V for a particular implementation.

A single vector construct A, is required to protect a procedure executing in one processor from being activated in another to perform the same data transformation in cases where this is inappropriate. A specific implementation of this construct is described in Appendix C.

Example Program

Before proceeding to describe the hardware implementation of the computational structure of the transition machine, an example program is described. This program describes how the software actually operates on a transition machine and a specific implementation of the S, R, T, F, A and V constructs (as described above and in appendices A, B, and C) for the example program. It is also shown how the requirements discussed under software productivity in the background section of the invention are supported by this computation structure.

FIG. 3 is a flow diagram of the example program to be used. For each block on this diagram, a high order language procedure is written to perform the requested function. Such a simple computation would not typically be broken into so many small subsystems, but this has been done primarily to give a clear example of how one can implement control flow with a unique computation structure. The function performed by the example set of programs simply computes the sum of the first twenty integers divided by twenty factoral. This function is not essential to the treatment and is given only to illustrate later how the conditions which effect control relate to the requirements of a computation. It is important to note the parallelism that is exploitable in this computation in that the product (block 3) can be computed in parallel with the sum (block 4).

In FIG. 4 the example program is implemented in a conventional request driven system. In this structure the flow control is completely implemented by active program requests. The control aspect of the program is interspersed with the data computation aspects. Because of this, any subsystem (program) can be activated by any other subsystem by a direct transfer of control, independent of the computational requirements it implements. Also, note that parallelism cannot be easily exploited due to the problem of trying to synchronize concurrent subsystems. The end effect is that this software structure does not support any of the identified requirements discussed above by way of background of the invention.

FIGS. 5A and 5B show the next stage in the example program evolution implemented in a system that supports both requests and events. In this system a subsystem may be activated based on a request by another subsystem or its activation may be determined based on a set of event flags being set appropriately. (It should be noted that these flags denote the status of unary predicates.) This provides a means for solving the synchronization problem that previously prevented parallelism from being exploited. Any subsystem can still request any other subsystem, and a direct transfer of control is still possible within this structure. Event based control structure allows the available parallelism to be easily exploited and therefore supports the requirement that only essential aspects of program control be specified by the programmer. A system that supports both requests and events represents the current state-of-the-art in operating systems.

FIG. 6 shows the next step which is a totally event-driven (data condition-driven) version of the program where the activation of every subsystem is based on the status of a set of required event flags. The overall system flowchart is this and subsequent examples is the same as that of FIG. 5B. This approach is not typically incorporated in current systems due to the high overhead involved in processing the large number of event flags in software. The advantage of this structure is that subsystem requests (inter-program direct transfer of control statements) can be eliminated. Control in this system is implemented by setting the appropriate event flags on completion of each computation. The result is a more requirements-oriented control structure in that the data conditions required to enable each subsystem are specified as an inherent part of the subsystem. Although "FLAG0", "FLAG1", etc., are not requirements-oriented, this is seen to be primarily a mneumonic problem where identifiers directly associated with specific requirements could have been assigned to the event flags. For example, Table I shows a possible assignment of mneumonic specifiers to the event flags which results in a very readable requirements-oriented structure.

                  TABLE I
    ______________________________________
    REQUIRED CONDITION MNEMONICS DEFINITIONS
    MNEMONIC           ASSIGNMENT
    ______________________________________
    INITIALLY          FLAG0
    FACTORIAL.READY    FLAG1
    SUM.READY          FLAG2
    CONTINUE.FACTORIAL FLAG3
    CONTINUE.SUM       FLAG4
    COMPUTE.RATIO      FLAG5
    ______________________________________

                  TABLE II
    ______________________________________
    Descriptor
               Definition
    ______________________________________
    P/P
    a binary semaphore used to prevent
              multiple processors from accessing the
              processor/system controller interface
              registers simultaneously. The P/P sema-
              phore is set (using a traditional test
              and set capability) when a processor
              is accessing the processor/system control-
              ler interface registers and it is cleared
              when no processor is currently accessing
              the interface registers.
    a binary status indicator used to pre-
              vent the processors from accessing
              the system controller interface regis-
              ters while a system transition is in
              progress. When a processor initiates
              a system transition, it loads the
              appropriate data values in the X,
              INDEX, TYPE, and V registers (to be
              described) and sets the L discrete
              true. This requests execution of the
              System Controller which resets the L
              discrete false when the required tran-
              sition is completed.
    X
    a binary status indication used to
              notify the System Controller of the
              type of system transition to effect.
              The X flag is set true by the processor
              when the system transition required is
              the result of a subsystem exiting, and
              X is set false by the processor for a
              subsystem entry transition.
    TYPE
    a register used to contain the pro-
              cessor type indentification. The System
              Controller uses this register to deter-
              mine the next eligible subsystem whose
              identification is to be loaded into
              INDEX. TYPE is loaded by a processor
              with its processor category when it re-
              quests the next subsystem eligible for
              execution. The System Controller then
              returns the EXECUTE, READ, WRITE, and
              INDEX values associated with the next
              eligible subsystem, whose type is of
              the same category as the value con-
              tained in the TYPE register. (This con-
              struct is required if a processor is to
              be able to request a specific type of
              subsystem.)
    INDEX
    a register used to contain the iden-
              tification of either the next eligible
              subsystem or the subsystem currently
              being exited. At the completion of
              each system entry transition, the System
              Controller loads INDEX with the index of
              (the number of the row in the matrices
              associated with) the next eliglible sub-
              system whose type is of the same cate-
              gory as the value contained in the
              TYPE register. INDEX is loaded by the
              System Controller with a special indi-
              cator if no subsystems for the current
              processor type are eligible. When a
              subsystem exits, INDEX contains the
              associated subsystem identification,
              i.e. the number of the row in the con-
              trol matrices associated with the
              subsystem.
    EXECUTE
    provides the entry point of the sub-
              system whose identification is in INDEX.
              This register is loaded only by the
              System Controller and is read by the
              processors.
    V
    provides the variable update vector
              loaded by the processors upon comple-
              tion of a subsystem. This vector
              allows a subsystem to return variable
              data conditions to the system status
              vector.
    READ
    provides the pointer(s) to the global
              data item(s) accessible to the asso-
              ciated subsystem in a read capacity.
              READ is loaded by the System Controller
              during an entry transition and is un-
              used during an exit transition.
    WRITE
    provides the pointer(s) to the global
              data item(s) accessible to the associated
              subsystem in a write capacity. WRITE
              is loaded by the System Controller dur-
              ing an entry transition and is unused
              during an exit transition.
    ______________________________________

                  TABLE III
    ______________________________________
    Descriptor
             Definition
    ______________________________________
    STATUS
    a 4-bit read/write register whose bits are labeled
             L, I, X and O, and which contain the following
             synchronization, protocol and mode request
             information:
    a binary status indicator used to prevent the
             processors from accessing the System Controller
             interface registers while a subsystem transition is in
             progress. When a processor requests a system
             transition, it loads the appropriate data
             values in the X, INDEX, TYPE and V registers
             and sets the L discrete true. This requests
             execution of the System Controller
             which resets the L discrete (sets it false) when
             the required transition is completed.
    I
    a binary status indicator used to indicate to the
             System Controller whether a normal or load
             transition is being requested. The I flag is set true
             by the processor when the system transition
             required is a load transition. The I bit remains true
             until the processor resets it upon load completion.
    X
    a binary status indicator used to indicate to the
             System Controller whether an entry or exit system
             transition is requested. The X flag is set true by
             the processor when the system transition required
             is the result of a subsystem exiting, and X is set
             false by the processor for a subsystem entry
             transition. During a load transition X is ignored.
    O
    a binary status indicator set by the System
             Controller to notify the processor that no subsystem
             is currently eligible. The O bit is set true by the
             System Controller when an entry transition results
             in no eligible subsystem. The O bit is set false by the System
             Controller when an entry transition
             results in an eligible subsystem. The O bit is ignored
             on exit and load transitions.
    TYPE
    a register used to contain the processor type
             identification. The System Controller uses this
             register to select the next eligible subsystem
             appropriate to the requesting processors. TYPE
             is fixed for a given processor with its processor
             category. During entry transitions the
             System Controller returns the EXECUTE,
             READ, WRITE, and INDEX values associated
             with an eligible subsystem, whose type is of the
             same category as the value contained in
             the TYPE register. TYPE is ignored during a
             subsystem exit transition. During a load transition
             TYPE is loaded by the processor with the
             processor category required by the subsystem
             whose row of data constructs is being loaded
             into the System Controller.
    INDEX
    a register used to contain the identification of
             either the next eligible subsystem, the row currently
             being loaded, or the subsystem currently being
             exited depending upon the type of transition being
             requested. At the completion of each subsystem
             entry transition, the System Controller loads
             INDEX with the index of the next eligible
             subsystem whose type is of the same category as the
             value contained in the TYPE register for the
             processor. During a load transition,
             INDEX is loaded by the processor with the System
             Controller row number for the row of constructs
             currently being loaded. When a subsystem exit
             transition is requested, INDEX will contain the
             subsystem identification provided to it by the
             System Controller at completion of the entry
             transition. Processor interrupts are forwarded to the
             System Controller by an exit transition using
             an INDEX value dedicated in the System
             Controller for that purpose.
    EXECUTE
    a register used to provide the entry point of the
             subsystem whose identification is in INDEX. This
             register is loaded by the System Controller and is
             read by the processors during subsystem
             entry transitions. EXECUTE is loaded by the
             processor and read by the System Controller
             during a load transition. During
             exit transitions EXECUTE is unused.
    READ
    a register used to provide the pointer(s) to the
             global data item(s) accessible to the associated
             subsystem in a read capacity. READ is loaded by
             the System Controller during an entry transition
             and is loaded by the processor during a load tran-
             sition. READ is unused during an exit transition.
    WRITE
    a register which provides the pointer(s) to the
             global data item(s) accessible to the associated
             subsystem in a write capacity. WRITE is loaded
             by the System Controller during an
             entry transition and is loaded by the processor
             during a load transition. WRITE is
             unused during an exit transition.
    V
    a register used to provide the variable update
             vector loaded by the processors upon completion
             of a subsystem. This vector allows a subsystem to
             return variable data conditions to the system status
             vector. (For the specific implementation described
             in the appendices, this allows the subsystem
             to modify only selected data elements of the S
             vector since any attempt to modify unauthorized
             elements will be masked out by the T and F
             vectors, stored internally to the System
             Controller.) During a load transition V is
             loaded by the processor with the new S vector
             to be loaded in the S register. V is
             unused during an entry transition.
    R
    a register which provides a method for the
             processor to load the R matrix of the System
             Controller. During load transitions the R
             register contains the vector to be loaded in
             the row of the System Controller's R matrix
             specified by INDEX. The R register is unused
             during entry and exit transitions.
    A
    a register which provides a method for the
             processor to load the System Controller A
             matrix. During load transition the A register
             contains the vector to be loaded in the row of
             the System Controller's A matrix specified by
             INDEX. The A register is unused during
             entry and exit transitions.
    T
    a register used to provide a method for the
             processor to load the System Controller T
             matrix. During load transitions the T register
             contains the vector to be loaded in the
             row of the System Controller's T matrix specified
             by INDEX. The T register is unused
             during entry and exit transitions.
    F
    a register which provides a method for the
             processor to load the System Controller's F
             matrix. During load transitions the F register
             contains the vector to be loaded in the
             row of the System Controller's F matrix
             specified by INDEX. The F register is unused
             during entry and exit transitions.
    ______________________________________

                                      TABLE IV
    __________________________________________________________________________
             Definition
    __________________________________________________________________________
    ADDRESS
    a multiple bit address bus that is capable of addressing each
             element of the R, A, T, F, TYPE, READ, WRITE, and EXECUTE
             arrays. The arrays are addressed concurrently, e.g., if ADDRESS
             =
             2 then the second element of each array is addressed.
    CE
    a one bit signal that enables the eight memory modules to be read
             or written. When CE is true (i.e., logical 1) the contents of
             each
             array element indicated by ADDRESS is read (R/--W = "1") or
             written
             (R/--W ="0") to or from the associated data bus. When CE is
             false
             (i.e., logical "0") no array can be read or written.
    R/--W
    a one bit signal input to each of the eight memory modules that
             specify a read or write action. When R/--W is true (i.e.,
             logical "1")
             and CE is true (i.e., logical "1") the contents of the array
             element
             indicated by ADDRESS is output on the corresponding data bus.
             When R/--W is false (i.e., logical "0") and CE is true (i.e,
             logical "1")
             the contents of each data bus is written into the associated
             array
             element specified by ADDRESS.
    S.sub.NEW
    a multibit data input to the read/write S register. S.sub.NEW contains
             the updated status vector returned by the system status update
             logic as the result of an entry, exit or load transition.
    S.sub.LATCH
    a control signal which, when enabled (transitions from logical "0"
             to logical "1"), causes the contents of S.sub.NEW data input to
             be
             latched into the S register. When S.sub.LATCH is disabled
             (logical "0")
             the contents of the S register remain unchanged independent of
             changes in S.sub.NEW.
    R.sub.i
    T.sub.i
    F.sub.i
    multiple bit, bidirectional data buses. Data from each of the
    A.sub.i  eight memory modules are output to (or input from) the
             associated
    EXECUTE.sub.i
             data buses.
    READ.sub.i
    WRITE.sub.i
    TYPE.sub.i
    a multiple bit data bus on which the content of the S register is
             output.
    __________________________________________________________________________