Microprogrammed digital data processing system employing multi-phase subroutine control for concurrently executing tasks

Abstract

A digital data processor operates at a microinstruction level in a multiprocessing and multiprogramming environment. The processor includes multi-phase subroutine control apparatus which provides for multiple levels of subroutine entry for a plurality of concurrently executing tasks, while also permitting the tasks to share the same subroutines. Tasks and subroutine control operations are staged to employ common hardware in a manner which provides the effect of a plurality of separate processors operating concurrently on different tasks in a multi-phased manner.

Claims

What is claimed is:

1. In a microprogrammed data processing system providing for the concurrent execution of a plurality of tasks, the combination comprising:

program control means for generating a plurality of tasks, each task being performable by the execution of one or more task microinstructions;

microinstruction storage means for storing selectably addressable task microinstructions for use in performing said tasks;

task control means coupled to said program control means for activating a plurality of different tasks and for selectively addressing said microinstruction storage means in order to provide for the concurrent execution of a plurality of different activated tasks;

microinstruction execution means operating in a multi-phased staged manner for concurrently executing a plurality of different task microinstructions selected from said microinstruction storage means and for producing microinstruction execution results for each executed microinstruction;

microinstruction sequencing control means responsive to microinstructions selected from said microinstruction storage means and to said microinstruction execution results for providing indications to said task control means for use in determining the selective addressing of said microinstruction storage means;

said microinstruction sequencing control means also being operative to provide a subroutine entry indication and a task identification indication when a task enters a subroutine and a subroutine return indication and a task identification indication when the task exits a subroutine; and

subroutine control means operating in a multi-phased staged manner in synchronism with said microinstruction execution means, said subroutine control means being responsive to said subroutine entry and return indications and to said task identification indications for determining and storing multiple levels of return addresses for subroutines entered by each task and for providing a corresponding return address to said sequencing control means when a task exits a subroutine.

2. The invention in accordance with claim 1, wherein each task microinstruction is performed by said microinstruction execution means and said subroutine control means in a plurality of stages occurring over a plurality of time periods, and wherein said microinstruction execution means and said subroutine control means operate during each time period to concurrently perform the operations required for a plurality of different stages for a plurality of different active tasks.

3. The invention in accordance with claim 2, wherein each of said microinstruction execution means and said subroutine control means provides the same number of stages and time periods for performing its operations with respect to a task microinstruction.

4. The invention in accordance with claim 1, wherein said task control means provides for addressing said microinstruction storage means in a manner so as to permit the execution of active task microinstructions in an intermixed order regardless of the particular task to which each belongs.

5. The invention in accordance with claim 1, 2, 3, or 4, wherein said microinstruction execution means provides for execution of a task microinstruction in a plurality of at least three stages including a read operation stage, a compute operation stage, and a write operation stage, each stage requiring one time period, wherein during each time period a write operation is performable with respect to a first active task microinstruction, a compute operation is performable with respect to a second active task microinstruction, and a read operation is performable with respect to a third active task microinstruction, and wherein said subroutine control means provides the same number of stages and time periods for performing its operations with respect to active task microinstructions as does said microinstruction execution means.

6. The invention in accordance with claim 5, wherein said subroutine control means comprises:

a plurality of return address storage means capable of storing multiple return addresses for each active task which includes a subroutine; and

return address control means responsive to said subroutine entry and task identification indications for determining a return address and for storing this return address in the return address storage means of the identified task; and

said return address control means being responsive to said subroutine return and task identification indications for determining the most recent return address stored in the return address storage means of the identified task and for causing it to be accessed therefrom and applied to said sequencing control means.

7. The invention in accordance with claim 6, wherein said return address control means is operable during each time period to permit a return address to be determined for a first task concurrently with the storing of a return address for a second task in its respective return address storage means.

8. The invention in accordance with claim 7, wherein said return address control means is also operable during each time period to permit a most recent return address for a third task to be accessed from its respective return address storage means for transfer to said sequencing control means concurrently with the determining of a return address for said first task and concurrently with the storing of a return address for said second task in its respective return address storage means.

9. The invention in accordance with claim 8, wherein said return address control means provides for the determining of a return address in response to a subroutine entry indication of an identified task during a first one of said stages and provides for the storing of this determined return address in the respective return address storage means of the same identified task during a second one of said stages.

10. The invention in accordance with claim 6, wherein said return address stroage means includes a first storage means for each task for storing a plurality of return addresses for its respective task and a second significantly faster storage means for each task for storing the most recent address of its respective task, wherein said return address control means operates in response to said subroutine entry and task identification indications for causing the determined return address to be stored in both of the respective first and second storage means of the identified task, wherein said return address control means operates in response to said subroutine return and task identification indications to access the most recent return address from the second storage means of the identified task for transfer to said system, and wherein said return address control means also includes means operating in response to said subroutine return and task identification indications for determining the next most recent return address to be accessed from the respective first storage means of the identified task and for causing it to be stored in the second storage means of the identified task.

11. The invention in accordance with claim 10, wherein the first storage means of each task comprises a stack for storing a plurality of return addresses, wherein a stack level pointer register is provided for each stack for storing a stack level pointer indicative of a storage level in its respective stack, wherein the second return address storage means of each task comprises a fast access register, wherein said control means operates to store a return address in a stack at a level indicated by its respective stack level pointer, wherein said control means operates in response to said entry and return indications to maintain the stack level pointers correctly updated, and wherein said control means accesses the next most recent return address from a stack at the level indicated by the respective stack level pointer.

12. The invention in accordancwe with claim 11, wherein said return address control means includes means responsive to a task identification indication provided by said system for accessing from the respective stack level pointer register the respective stack level pointer value for the identified task for use by said return address control means in storing a return address at the appropriate level of the stack corresponding to the identified task.

13. The invention in accordance with claim 1, 2, 3 or 4, wherein said subroutine control means comprises:

a first return address storage means for each active task for storing subroutine return addresses for the respective task;

a second return address storage means for each active task capable of storing the most recent return address of the respective task when the task enters a subroutine, said second return address storage means providing for significantly faster access than said first return address means;

first control means responsive to said subroutine entry and task identification indications for determining a return address for the indicated subroutine and for storing this return address in both of the respective first and second return address registers of the task;

second control means responsive to said subroutine return and task identification indications for determining the most recent return address stored in the respective second return address storage means of the identified task and for causing it to be accessed and transferred to said sequencing control means; and

third control means also responsive to said subroutine return and task identification indications for determining the next most recent return address to be accessed from the respective first return address storage means of the identified task and for causing it to be stored in the respective second return address storage means of the identified task.

Description

CROSS-REFERENCE TO RELATED PATENT APPLICATIONS

The following commonly assigned copending applications contain subject matter related to this application:

Ser. No. 147,149 filed May 6, 1980, for Pipelined Microprogrammed Digital Data Processor Employing Micronistruction Tasking, D. R. Kim and J. H. McClintock, inventors, and Ser. No. 147,251, filed May 6, 1980, for Microprogrammed Digital Data Processing System Employing Tasking at a Microinstruction Level, D. R. Kim and J. H. McClintock, Ser. No. 173,379, filed July 29, 1980, for Microprogrammed Digital Data Processor Employing Microinstruction Tasking and Dynamic Register Allocation, Ser. No. 231,553, filed Feb. 4, 1981, for Subroutine Control Circuitry, D. R. Kim, inventor, and Ser. No. 231,554, filed Feb. 4, 1981, for Multi-Phase Subroutine Control Circuitry, D. R. Kim, inventor.

INTRODUCTION

The present invention relates to improved means and methods for performing data processing operations in a microprogrammed electronic digital computer. More particularly, the present invention relates to improved means and methods for providing subroutine control for a plurality of concurrently executing tasks.

BACKGROUND OF THE INVENTION

Microprogramming may be broadly viewed as a technique for designing and implementing the control function of a digital computer system as sequences of control signals that are organized on a word basis and stored in a fixed or dynamically changeable control memory. Detailed examples of some known approaches to the design of microprogrammed digital computers can be found in U.S. Pat. No. 3,886,523, Ferguson et. al., issued May 27, 1975, U.S. Pat. No. 4,155,120, Keefer and Kim, issued May 15, 1979, U.S. Pat. No. 4,181,935, Feeser and Gerhold, issued Jan. 1, 1980 and U.S. Pat. No. 4,038,643, Kim, issued July 26, 1977; in the book by S. S. Husson, "Microprogramming; Principles and Practices", Prentice-Hall, Inc. (1970); in the book "Foundations of Microprogramming", Argrausala, et al., Academic Press, Inc., 1976; in the article "Microprogramming-Another Look at Internal Computer Control", M. J. Flynn, I.E.E.E. Proc., Vol. 63, No. 11, Nov. 1975, pp. 1554-1567; and in the article "Microprogramming: a Tutorial and Survey of Recent Developments" , I.E.E.E.E. Transaction on Computers, Vol. C-29, No. 1, Jan. 1980.

In recent years the concept of microprogramming has been extended for use in conjuction with pipelined architectures as described, for example, in the article "The Microprogramming of Pipelined Processors, P. M. Kogge, 4th Annual Symposium on Computer Architecture", Mar. 1977, pp. 63-69; and also in the article "A Pipeline Architecture Oriented Towards Efficient Multitasking", F. Romani, Euromicro, Oct. 1976, Vol. 2, No. 4, North-Holland Publishing Co., Amsterdam.

The contents and teachings of the above references are to be regarded as incorporated herein.

SUMMARY OF THE PRESENT INVENTION

An important feature of the present invention is to futher extend the advantages of microprogramming by providing for multi-phased tasking and subroutine control at a microinstruction level in a microprogrammed data processing system.

Another feature of the present invention is to provide a microprogrammed data processing system employing microinstruction tasking and multi-phased subroutine control in a manner which permits advantage to be taken of both multiprocessing and multiprogramming at a microinstruction level.

A further feature of the present invention is to provide a microprogrammed data processing system which provides for multi-phase subroutine control in conjunction with microinstruction tasking so as to further enhance the capability and advantages derivable from microinstruction tasking.

In a preferred embodiment of the invention, a microprogrammed data processor is provided with a three-stage pipelined architecture having the capability of managing and dynamically allocating resources for up to sixteen activated tasks while concurrently providing for the execution of three dynamically selectable task microinstructions, each task being executed as a result of the performance of one or more task microinstructions. In the preferred embodiment, the three-stage pipelined architecture is implemented so as to in effect provide three separate processors operating 120.degree. out of phase with one another and sharing the same physical hardware. Each processor is capable of executing task microinstructions in and desired intermixed order regardless of the particular task to which they belong, thereby providing a multiprogramming capability for each processor. In addition, multi-phase subroutine control circuitry is provided which permits multiple levels of subroutine entry to be provided for each of a plurality of concurrently executing tasks, while also permitting the tasks to share the same subroutines.

The specific nature of the invention as well as other objects, features, advantages and uses thereof will become evident from the following detailed description taken in conjunction with the accompanying drawings.

BRIEF DESCRIPTION OF THE DRAWINGS

FIG. 1 is a block diagram of an overall computer system in which the present invention may be incorporated.

FIG. 2 is a block diagram of the MLP Processor illustrated in FIG. 1.

FIG. 3 is a block diagram of the Processing Element PE in FIG. 2.

FIG. 4 diagrammatically illustrates the basic manner in which tasks are managed in a preferred embodiment.

FIG. 5 illustrates an example of how the preferred embodiment dynamically allocates resources for activated tasks in performing the calculation (A+B)-(1+C).

FIG. 6 illustrates an example of how task microprogramming may be provided in the preferred embodiment.

FIG. 7 illustrates how tasks are performed using the three-stage pipeline architecture provided for the preferred embodiment.

FIG. 8 illustrates an example of how the preferred embodiment employs tasking microprogramming, and multiprocessing for concurrently performing the three calculations (A+B)+(C+D)=H; (A+B)-E=I; and (C+D)-E=J.

FIG. 9 is a block diagram illustrating a preferred embodiment of the Program Controller PE of FIG. 3.

FIG. 10 is a block diagram illustrating a preferred embodiment of the Task Controller TC of FIG. 3.

FIG. 11 is a block diagram illustrating a preferred embodiment of the Stored Logic Controller SLC in FIG. 3.

FIG. 12 is a block diagram illustrating a preferred embodiment of the Auxiliary Control Memory ACM in FIG. 11.

FIG. 13 is a block diagram illustrating a preferred embodiment of the Sequence Control Memory SCM in FIG. 11.

FIG. 14 is a block diagram illustrating a preferred embodiment of the main Data Path DP in FIG. 3.

FIG. 15 is a block diagram illustrating a preferred embodiment of the Address and State Unit ASU in FIG. 3.

FIG. 16 is a flow chart illustrating the operation of the ASU Change Queue ASU-CQ in FIG. 15.

FIG. 17 is a block diagram illustrating a preferred embodiment of the Memory System MS in FIG. 2.

FIG. 18 is a preferred implementation of multi-level subroutine control circuitry in accordance with the invention.

FIG. 19 illustrates an example of a typical task listing containing a plurality of subroutine calls.

FIG. 20 illustrates basic operations of the FIG. 18 implementation during performance of the task of FIG. 19.

FIG. 21 illustrates time relationships between the performance of the stages of the subroutine control circuitry of FIG. 18 and the stages of the processor system.

GENERAL DESCRIPTION

Overview (FIG. 1)

In a preferred embodiment, the present invention may be incorporated in an overall system comprised of one or more a simplex systems, such as illustrated in FIG. 1. Each simplex system typically comprises a multiple logical processor (which will herein after be referred to as an MLP processor), a Maintenance Processor, and an I/O Subsystem with its associated peripherals P. These simplex systems are interconnected by an Exchange EX and a Global Memory GM which allows the system software to determine the degree of coupling between the simplex systems.

The I/O subsystem in FIG. 1 contains the user input/output devices and storage for complete sets of program and data segments. The Global Memory GM permits processor interconnection and contains program and data segments shared by the multiple processors. Each MLP processor has a local memory subsystem containing those program and data segments being processed on the MLP processor.

In the preferred embodiment, the MLP processor is an integrated hardware and firmware system which implements a high-level virtual instruction set. The instructions of this set are individually programmed by a set of firmware instructions which execute on lower-level MLP hardware. The MLP processor uses multiprogramming and multiprocessing techniques at the hardware (microinstruction) level to achieve a high degree of parallelism between the execution of the firmware instructions corresponding to multiple high-level instructions. The MLP processor considers a sequence of the applied high-level virtual instructions as a set of tasks to be performed, each of these tasks being performed by executing one or more microinstructions on a low-level processor. Some of these tasks may need to use data which is prepared by preceding tasks. However, for typical data processing applications, a substantial number of the tasks do not have such dependencies. Thus, some or all of the performance of the tasks can be overlapped. This capability is enhanced by the multi-phase subroutine circuitry provided in accordance with the present invention which permits many levels of subroutine entry to be provided for each of a plurality of concurrently executing tasks.

MLP Processor Organization (FIG. 2)

In the preferred embodiment being considered herein, the MLP processor is partitioned into hardware modules as shown in FIG. 2. The Processing Element PE contains both the basic data path and the storage for the processor microcode. The Memory Subsystem MS contains both the local memory of the processor and the processor's interface to the Global Memory GM (FIG. 1). MS also preferably contains a cache module to improve the average access time and the bandpass of the local memory. The Host Dependent Port HDP provides the processor's interface to the I/O (FIG. 1). HDP is controlled by a task initiated by microinstructions from PE as well as a request from HDP. In the preferred embodiment, this HDP task is one of the multiple tasks that may be executed concurrently with other processor tasks. The Host Console Port HCP is the processor's interface with the system port of the Maintenance Processor MP (FIG. 1) through which the maintenance and control of the processor is performed. HCP has read-write access to all components of the processor state for initialization and maintenance.

Processing Element PE (FIG. 3)

As illustrated in FIG. 3, a preferred implementation of the Processing Element PE comprises five major components:

1. A Program Controller PC which parses program code words into operators and parameters and, in response to each operator, determines one or more tasks to be performed along with the resource requirements for each task.

2. A Task Controller TC which manages the tasks and controls the sequence in which tasks are performed.

3. A main Data Path DP which stores the primary data items for the tasks along with manipulation facilities for performing logical and arithmetic operations on these data items.

4. An Address and State Unit ASU which contains the storage for memory addresses along with facilities for their manipulation. ASU also stores most of the state of the high-level architecture.

5. A Stored Logic Controller SLC which stores the microcode and provides control circuitry responsive thereto for executing tasks. This control circuitry provided for SLC includes the multi-phase subroutine control circuitry of the present invention. In response to TC, DP and ASU, SLC issues microinstructions to the various components of PE in the proper sequences to perfrom the tasks applied thereto by TC. A task may require one or more microinstructions for its performance and may also incorporate a plurality of nested subroutines.

It will thus be understood that operator-level data, memory addresses and state are stored in DP and ASU, and that SLC issues microinstructions which causes these units to select the operations and data required in order to perform each task. During task execution, selected conditions are provided which flow to SLC and affect microinstruction sequencing, thereby completing the basic feedback loop in PE.

In order to achieve high performance, the preferred embodiment employs several levels of concurrency in the performance of PE operations as follows:

1. PC and TC operations (fetching, converting of operators into tasks by PC and managing and activating of tasks by TC) are concurrent with the performance of microinstructions by SLC, DP, and ASU.

2. SLC, DP and ASU operate concurrently with each other, so that during each clock cycle a microinstruction is executed by DP and ASU while a new microinstruction and state is generated by SLC.

3. SLC, DP and ASU are implemented with a multiplestage pipeline architecture which permits multiple tasks to be concurrently performed in a manner which takes advantage of both multiprogramming and multiprocessing techniques. As is well known, multiprogramming is a technique in which the execution of multiple programs is interleaved on a single processor, whereby time intervals during which one program is waiting (i.e., not ready to execute) are used to execute portions of other programs. As is also well known, multiprocessing is a technique in which multiple processors are used to execute one or more programs.

Basic Operation of the Processor Element PE (FIG. 3)

Before considering specific implementations of the MLP Processor, some basic operating features will first be presented.

Generation of tasks

The generation of tasks in the Processor Element PE is performed by the Program Controller PC and the Task Controller TC. PC examines the sequence of raw words of code derived from applied high-level instructions, determines the sequence of high-level operators to be performed, and, for each of these operators, determines one or more tasks to be performed. Each task, along with its resource requirements, is fowarded to TC. PC also decodes any parameters which may be provided for each operator, and forwards these to the main Data Path DP.

TC either inserts the task into the active mix or enters a holding state if sufficient resources are not available for its insertion. The reasons why TC may not be able to insert the task include the following:

1. The mix may be full (that is, the hardware limit on the number of active tasks has been reached), in which case PC must wait for the termination of the Oldest Active Task (OAT);

2. Sufficient free registers may not exist to satisfy the task's requirements in which case PC must wait for other tasks to free enough registers;

3. One or more of the change queues required by the task (to be described later) may be locked, in which case PC must wait for them to become unlocked.

PC may also be used for the detection of external interrupt conditions and, with the aid of the Maintenance Processor MP (FIG. 1), also detects alarm interrupt conditions. Typically, these conditions may be handled by special tasks which PC inserts into the mix.

Management of waiting tasks and wait conditions

During processor operation, every active task is in one of four states: (1) Executing (task is presently being executed), (2) Waiting (task is not ready for execution until some condition has been satisfied), (3) Ready (task is ready to be executed--that is, the task is not waiting on any condition), or (4) End of Task (EOT) (task waiting to be terminated). The Task Controller TC keeps track of the state of each task. At the completion of each task microinstruction, TC is presented with an appropriate task status condition for use in determining whether the Executing state of the task should be continued, or the task put in another state (e.g., Waiting or (EOT)). FIG. 4 diagrammatically illustrates the manner in which the task states are managed in the preferred embodiment in which, for example, there may be a maximum of 16 active tasks and a maximum of three tasks being executed at any one time.

Selection of Ready tasks

On each clock cycle, the Task Controller TC selects one task microinstruction to be executed from among the Ready tasks. This selected task microinstruction may be the first microinstruction of a newly activated task or a second, third, etc. microinstruction of a previously activated task which was previously put in a Waiting state (e.g., becuase all the data required for the next task microinstruction was not available at that time). TC marks the selected task as "in execution" so that it will not select it again on the next clock cycle. This is done because, in the preferred embodiment, execution of each task microinstruction is performed in three stages requiring three clock cycles.

If there are no Ready tasks (i.e., all active tasks are either Waiting, Executing, or at (EOT)), then TC selects a special null task microinstruction which is always Ready. The null task microinstruction is never marked "in execution", so that it may be selected on the next clock cycle, if necessary. The null task microinstruction may, for example, simply be a loop of "null" operations.

If there is more than one Ready task, TC may, for example, make its selection according to a simple, static, two-level priority system. The distinction between high priority and low priority tasks may be indicated by the programmer of the instruction flow. Among tasks of the same priority, the selection by TC is arbitrary.

Synchronization of tasks and dynamic register assignment

For the preferred embodiment being considered, a conventional stack-oriented operator set may be assumed. A basic understanding of how one or more stacks may be employed in a data processing system can be obtained, for example, by reference to the article E. A. Hauck and B. A. Dent, "Burroughs B 6500/7500 Stack mechanism", AFIPS Conference Proceedings, 1968 SJCC, p. 245; and also to the series of articles in Computer, May 1977 pp. 14-52, particularly the articles entitled: "Stack Computers: An Introduction", D. M. Bulman, pp. 18-28 and "Exploring a Stack Architecture", R. P. Blake, pp. 30-39. The contents and teachings of these articles are to be considered as incorporated herein.

The Burroughs 6800 computer system is an example of the use of a stack-oriented operator set. As is conventional in such a system, at least one stack is provided for operation in a manner such that communication between microinstructions normally occurs via the top of the stack. In order to further enhance this important communication mechanism, the present invention additionally provides a substantial number of "floating" top-of-stack register pairs. Operation is then caused to be such that the stack items which an operator takes as its input and the stack items which a task produces as its outputs are stored in register pairs which are assigned dynamically to the task when it is initiated into the mix of tasks. Each register pair has an associated validity bit, which indicates whether the corresponding stack item has been "produced". If a task microinstruction requires it to "consume" one of its input stack items which has not yet been produced, the task is put into a Waiting state by the hardware. It is put back into the Ready state when the stack item is produced.

The Task Controller TC keeps track of a virtual "top-of-stack image", which is a list of register pairs. This list indicates the top-of-stack configuration. TC also keeps a list of "free" (unassigned) register pairs. These lists are updated whenever a task is initiated or terminated.

As an example of the above, assume that the calculation (A+B)-(1+C) is to be performed using tasks T1, T2, T3, T4, T5, T6 and T7 assigned as follows:

    ______________________________________
    Tasks           Operators
    ______________________________________
    T1              VALC A
    T2              VALC B
    T3              ADD: (A + B) = S1
    T4              ONE
    T5              VALC C
    T6              ADD: (1 + C) = S2
    T7              SUBTRACT: (S1 - S2)
    ______________________________________

    ______________________________________
    Tasks             Operators
    ______________________________________
    T.sub.A = T.sub.A m.sub.1 w T.sub.A m.sub.2
                      VALC A
    T.sub.B = T.sub.B m.sub.1 w T.sub.B m.sub.2
                      VALC B
    T.sub.C = T.sub.C m.sub.1 w T.sub.C m.sub.2
                      VALC C
    T.sub.D = T.sub.D m.sub.1 w T.sub.D m.sub.2
                      VALC D
    T.sub.E = T.sub.E m.sub.1 w T.sub.E m.sub.2
                      VALC E
    T.sub.F = T.sub.F m
                      ADD (A + B) = F
    T.sub.G = T.sub.G m
                      ADD (C + D) = G
    T.sub.H = T.sub.H m
                      SUBTRACT F - G = H
    T.sub.I = T.sub.I m
                      SUBTRACT F - E = I
    T.sub.J = T.sub.J m
                      SUBTRACT G - E = J
    ______________________________________

• Inventors
  Kim, Dongsung R.;
• Assignee
  Burroughs Corporation (Detroit, MI)
• Published
  Feb-7-1984
• Current US Classes:
  718/100
• Application #
  240714
• International Classes
  G06F 009/38; G06F 009/42; G06F 009/46
• Field of Search
  364/200
• Examiner
  Smith; Jerry
• Agent
  Cass; Nathan, Peterson; Kevin R., Rasmussen; David G.
• US Patent References:
  4041462
  4073005
  4124890
  4126893
  4156925
  4210960
  4229790