Apparatus and method for controlling digital data processing system employing multiple processors

• US 4,543,626 A
• Filed: 12/06/1982
• Issued: 09/24/1985
• Est. Priority Date: 12/06/1982
• Status: Expired due to Term

• Current Assignee: Compaq Computer Corporation (HP Inc.)
• Original Assignee: Digital Equipment Corporation (HP Inc.)
• Inventors: Blackledge, Robert, Gardner, Edward A., Bean, Robert, Lary, Richard F., Rubinson, Barry L., Chow, Michael
• Primary Examiner(s): Thomas, James D.
• Assistant Examiner(s): Eng, David Y.
• Application Number:
  US06/447,228
• Time in Patent Office: 1,023 Days
• Field of Search: 364/200 MS File, 364/900 MS File
• US Class Current: 709/201
• CPC Class Codes: G06F 15/161 Computing infrastructure, e.g. computer clusters, blade chassis or hardware partitioning casings, cabinets, racks or drawers for data centers H05K5/00
• CPC Class Codes: G06F 9/4881 Scheduling strategies for dispatcher, e.g. round robin, multi-level priority queues

Abstract

A control arrangement for coordinating operations of multiple processors in a multiprocessor system in response to a command. Each command is associated with a route comprising a sequence of route vectors, each identifying an operation to be performed to execute the command, as well as the process, or station, to execute the route vector. In response to the receipt of a command, a control block is generated identifying the first route vector in the route associated with the command. Each station has a work queue containing control blocks, which the station retrieves and processes sequentially. The control block is first sent to the work queue of the station to perform the first operation. When the station gets to the control block, it performs the operation required by the route vector, modifies the control block to identify the next route vector in the sequence, and transfers the control block to the work queue of the station to perform the operation required by the next route vector in the route.

Claims

1. A data processing system for executing commands, each command requiring a plurality of sequentially-performed operations, comprising memory means, source processor means and a plurality of stations;

A. said memory means for storing a route for each command, each route comprising a sequence of route vectors each including an operation specifying portion identifying an operation to be performed in partial execution of the command and a station specifying portion identifying a station for performing the identified operation;

B. source processor means comprising

(1) means connected to said memory means for generating, in response to a command, a control block containing a pointer identifying the first route vector in the route associated with the command; and

(2) control block transmitting means connected to said generating means and to all of said stations for coupling the generated control block to the station to process the first route in the route vector;

C. each station comprising;

(1) work queue means connected to said control block transmitting means and to said other stations for receiving and storing control blocks in a queue;

(2) means connected to said work queue means for sequentially retrieving the control blocks from said work queue means;

(3) processing means connected to said retrieving means and to said memory means for retrieving the route vector from said memory means identified by the pointer in the retrieved control block and for performing the operation specified by the vector; and

(4) transfer means connected to said processing means and to the k queue means of the other stations for advancing the route vector pointer in the control block to identify the next route vector in the route and for transferring the control block to the work queue means of the station that is to execute the route vector identified by the route vector pointer.

2. A data processing system as defined in claim 1 wherein each transfer means includes:

A. means connected to said memory means for retrieving from said memory means a station specifying portion of the route vector identified by the advanced route vector pointer in the control block; and

B. means for coupling the control block identifying the route vector to the work queue means of the identified station.

3. A data processing system as defined in claim 2 wherein one of said stations is a diagnostic station which includes diagnostic means for executing diagnostic programs and wherein each route vector further includes a diagnostic station specifying portion for identifying said diagnostic station, said transfer means further including means connected to said memory means for retrieving said diagnostic work queue identifying portion when said station is unable to perform operation specified in the route vector and for transferring the control block to the work queue of said diagnostic station.

4. A data processing system as defined in claim 2 wherein each work queue means is identified by a work queue pointer means for identifying the control blocks in the work queue, said transfer means including means for altering the work queue pointer means to couple a new control block to the work queue means.

5. A data processing system as defined in claim 4 wherein said work queue pointer means includes a tail pointer means for identifying the last control block in the work queue means, said coupling means including tail coupling means for altering the tail pointer means when coupling a new control block to the work queue means.

6. A data processing system as defined in claim 5 wherein said work queue pointer means also includes a head pointer means for identifying the first control block in the work queue means, said coupling means including head coupling means for altering the head pointer means when coupling a new control block to the work queue means.

7. A data processing system as defined in claim 6 wherein said route vector further includes flag means having a first condition for indicating that the control block is to be transferred to the head of the work queue means and a second condition for indicating that the control block is to be transferred to the tail of the work queue means, said coupling means including means for determining the condition of said flag means to enable either said head coupling means or said tail coupling means when coupling a control block to the work queue means.

8. A data processing system as defined in claim 7 wherein each control block further includes a queue link pointer means for identifying the next control block in each work queue means, the queue link pointer means of the last control block identifying the tail pointer means of the work queue means, said tail coupling means further including:

A. means for modifying the queue link pointer means of the last control block in the recipient work queue means to identify the control block being transferred to the work queue means, and

B. means for modifying the queue link pointer means of the control block being transferred to the work queue means to identify the tail pointer means of the work queue means.

9. A data processing system as defined in claim 7 wherein a station includes a plurality of work queue means, the station further including a service queue means having a series of entries each of which identifies those work queue means of the station which have gone from an empty condition to a non-empty condition, each entry in the series including a link identifying the next entry in the series, the service queue means comprising a head pointer means and a tail pointer means, the work queue means further including a service queue pointer means which identifies the service queue, the transfer means further comprising:

A. condition detecting means for determining whether the receiving work queue means is empty,

B. means connected to said condition detecting means for generating a new entry for the service queue means to identify the receiving work queue means,

C. means for altering the link in the last entry of the service queue means to identify the new entry, and

D. means for altering the tail pointer means of said service queue means to identify the new entry in the service queue means.

10. A data processing system as defined in claim 9 in which said retrieving means comprises service queue retrieval means for retrieving an entry from said service queue means comprising:

A. means for retrieving the head pointer means of said service queue means to determine the identity of the first entry in the service queue means;

B. entry retrieving means connected to said service queue head pointer retrieving means for using the retrieved head pointer means of said service queue means to retrieve the first entry from said service queue means,

C. means connected to said entry retrieving means for replacing the head pointer means of the service queue means with the link from the first entry in said service queue means in response to the retrieval of an entry from said service queue means, the link constituting the new head pointer means for the service queue means.

11. A data processing system as defined in claim 6 wherein each control block includes a queue link pointer means for identifying the next control block in each work queue means, said retrieval means comprising:

A. identification means for using the head pointer means to identify the first control block in the sequence of control blocks in the work queue means,

B. means connected to said identification means for retrieving the identified control block from the work queue means, and

C. means connected to said control block retrieving means for using the queue link pointer of the retrieved control block to alter the head pointer means to identify the next control block in said work queue means.

12. A data processing system as defined in claim 1 wherein said generating means generates a plurality of control blocks in response to a command, the control blocks generated by the generating means each containing a pointer identifying the first route vector in the route, with the operations identified in all of the routes being required to execute the command, said memory means further including a counter means that is associated with the command and set by said generating means to identify the number of control blocks generated by said generating means in response to the command, said control blocks associated with the command including counter identification means for identifying the location in said memory means of said counter means, said transfer means further including:

A. means for determining that the station is executing the last route vector in the route,

B. means connected to said determining means and to said memory means for decrementing said counter means when said processing means has completed performing the operation specified by the route vector.

13. A data processing system as defined in claim 12 wherein the last route vector in each route includes a last route vector flag which indicates that it is the last route vector, said determining means including means for testing said last route vector flag.

14. A data processing system as defined in claim 13 wherein said source processor means includes means for generating an indication that the command has been completed when said counter has been decremented to a selected value.

15. A station for connection in a data processing system that executes commands requiring a plurality of operations, the data processing system including a plurality of stations and a memory means for storing in predetermined locations a route for each command, each route comprising a plurality of route vectors each including an operation specifying portion identifying an operation to be performed by a station in partial execution of the command, said data processing means further comprising source processing means for generating, in response to a command, a control block containing a pointer identifying the first route vector in the route associated with the command and for transmitting the control block to a station, the station comprising:

(1) work queue means connected to said source processor means and to said other stations for receiving and storing control blocks in a queue;

(2) means connected to said work queue means for sequentially retrieving the control blocks from said work queue means;

(3) processing means connected to said retrieving means and to said memory means for retrieving the route vector from said memory means identified by the pointer in the retrieved control block and for performing the operation specified by the route vector; and

(4) transfer means connected to said processing means and to the work queue means of the other stations for advancing the route vector pointer in the control block to identify the next route vector and for transferring the control block to the work queue means of the station that is to execute the route vector identified by the route vector pointer.

16. A station as defined in claim 15 wherein said transfer means includes:

A. means for connection to the memory means for retrieving the station specifying portion of the route vector identified by the advanced route vector pointer in the control block, and

B. means for coupling the control block identifying the route vector to the work queue means of the identified station.

17. A station as defined in claim 16 wherein the work queue means is identified by a work queue pointer means for identifying the control blocks in the work queue, said transfer means including means for altering the work queue pointer means when coupling a new control block to the work queue means.

18. A station as defined in claim 17 wherein said work queue pointer means includes a tail pointer means for identifying the last control block in the work queue means, said coupling means including tail coupling means for altering the tail pointer means when coupling a new control block to the work queue means.

19. A station as defined in claim 18 wherein said work queue pointer means also includes a head pointer means for identifying the first control block in the work queue means, said coupling means including head coupling means for altering the head pointer means when coupling a new control block to the work queue means.

20. A station as defined in claim 19 wherein said route vector further includes flag means having a first condition for indicating that the control block is to be transferred to the head of the work queue means and a second condition for indicating that the control block is to be transferred to the tail of the work queue means, said coupling means including means for determining the condition of said flag means to enable either said head coupling means or said tail coupling means to couple a control block to the work queue means.

21. A station as defined in claim 20 wherein each control block further includes a queue link pointer means for identifying the next control block in each work queue means, the queue link pointer means of the last control block identifying the tail pointer means of the work queue means, all of the coupling means further including:

A. means for modifying the queue link pointer means of the last control block in the recipient work queue means to identify the control block being transferred to the work queue means, and

B. means for modifying the queue link pointer means of the control block being transferred to the work queue means to identify the tail pointer means of the work queue means.

22. A station as defined in claim 20 wherein a station includes a plurality of work queue means, the station further including a service queue means having a series of entries each of which identifies those work queue means which have gone from an empty condition to a non-empty condition, each entry in the series including a link to the next entry, the service queue means comprising a head pointer means and a tail pointer means, the work queue means further including a service queue pointer means which identifies the service queue, the transfer means further comprising:

A. condition detecting means for determining whether the receiving work queue means is empty,

B. means connected to said condition detecting means for generating a new entry for the service queue means to identify the receiving work queue means,

C. means for altering the link in the last entry of the service queue means to identify the new entry, and

D. means for altering the tail pointer means of said service means to identify the new entry in the service queue means.

23. A station as defined in claim 22 in which said retrieving means comprises service queue retrieval means for retrieving an entry from said service queue means comprising:

A. means for retrieving the head pointer means of said service queue means to determine the identity of the first entry in the service queue means;

B. entry retrieving means connected to said service queue head pointer retrieving means for using the retrieved head pointer means of said service queue means to retrieve the first entry from said service queue means,

C. means connected to said entry retrieving means for replacing the head pointer means of the service queue means with the link from the first entry in said service queue means in response to the retrieval of an entry from said service queue means, the link constituting the new head pointer means for the service queue means.

24. A station as defined in claim 18 wherein each control block includes a queue link pointer means for identifying the next control block in each work queue means, said retrieval means comprising:

A. identification means for using the head pointer means to identify the first control block in the sequence of control blocks in the work queue means,

B. means connected to said identification means for retrieving the identified control block from the work queue means, and

C. means connected to said control block retrieving means for using the queue link pointer of the retrieved control block to alter the head pointer means to identify the next control block in said work queue means.

25. A station as defined in claim 16 wherein the generating means generates a plurality of control blocks in response to a command, the control blocks generated by the generating means each containing a pointer identifying the first route vector in the route, with the operations identified in all of the routes being required to execute the command, the memory means further including a counter means that is associated with the command and set by the generating means to identify the number of control blocks generated by the generating means in response to the command, the control blocks associated with the command including counter identification means for identifying the location in the memory means of said counter means, said transfer means further including:

A. means for determining that the station is executing the last route vector in the route,

B. means connected to said determining means and to said memory means for decrementing said counter means when said processing means has completed performing the operation specified by the route vector.

26. A station as defined in claim 25 wherein the last route vector in each route includes a last route vector flag which indicates that it is the last route vector, said determining means including means for testing said last route vector flag.

27. A method of controlling a multiprocessor system which executes commands, one of the processors comprising a source processor and the other processors comprising execution processors, the commands requiring a plurality of operations each performed by a selected one of the execution processors in the multiprocessor system, each command being associated with a route that comprises a series of route vectors each identifying an operation to be performed and the execution processor to perform the operation, each execution processor including a work queue for storing control blocks, the method comprising the steps of:

a. the source processor;

(i) generating a control block in response to the receipt of a command, the control block including a route vector pointer identifying the first route vector in a route, and

(ii) coupling the control block to the work queue of the execution processor identified by the first route vector in the identified route,

B. each execution processor;

(i) serially retrieving control blocks from its associated work queue and performing the operation required by the route vector identified by the control block,

(ii) advancing the route vector pointer in the control block to identify the next route vector in the route, and

(iii) coupling the control block to the work queue of the execution processor identified by the route vector identified by the advanced route vector pointer.

28. A method as defined in claim 27 in which the transfer step includes the steps of:

A. retrieving the identification of the execution processor to process the route vector identified by the advanced route vector pointer from said memory means, and

B. coupling the control block identifying the route to the work queue of the identified execution processor.

29. A method as defined in claim 28, each work queue being identified by a work queue pointer means for identifying the control blocks in the work queue, the transfer step including the step of altering the work queue pointer means when coupling a new control block to the work queue.

30. A method as defined in claim 29, said work queue pointer means including a tail pointer means for identifying the last control block in the work queue, the transfer step including the step of altering the tail pointer means when coupling a new control block to the work queue.

31. A method as defined in claim 29, said work queue pointer means includes a head pointer means for identifying the first control block in the work queue, the transfer step including the step of altering the head pointer means when coupling a new control block to the work queue.

32. A method as defined in claim 31, said route vector further including flag means having a first condition for indicating that the control block is to be transferred to the head of the work queue and a second condition for indicating that the control block is to be transferred to the tail of the work queue, the transfer step including the step of testing said flag means prior to coupling the control block to the work queue.

33. A method as defined in claim 32, each control block further including a queue link pointer means for identifying the next control block in each work queue, the queue link pointer means of the last control block identifying the tail pointer means of the work queue, the transfer step including the steps of:

A. modifying the queue link pointer means of the last control block in the recipient work queue to identify the control block being transferred to the work queue, and

B. modifying the queue link pointer means of the control block being transferred to the work queue to identify the tail pointer means of the work queue.

34. A method as defined in claim 32, an execution processor including a plurality of work queues and a service queue having a series of entries each of which identifies those work queues which have gone from an empty condition to a non-empty condition, each entry in the series including a link to the next entry, the service queue comprising a head pointer means and a tail pointer means, the work queue further including a service queue pointer means which identifies the service queue, the transfer step further comprising the steps of:

A. determining whether the receiving work queue is empty,

B. generating a new entry for the service queue to identify the receiving work queue,

C. altering the link in the last entry of the service queue to identify the new entry, and

D. altering the tail pointer means of said service queue to identify the new entry in the service queue.

35. A data processing system as defined in claim 34, the retrieval step comprising the steps of:

A. retrieving the head pointer means of said service queue to determine the identity of the first entry in the service queue;

B. using the head pointer means of said service queue to retrieve the first entry from said service queue,

C. replacing the head pointer means of the service queue with the link from the first entry in said service queue, the link constituting the new head pointer means for the service queue.

36. A method as defined in claim 33, each control block including a queue link pointer means for identifying the next control block in each work queue, the retrieval step comprising the steps of:

A. using the head pointer means to identify the first control block in the sequence of control blocks in the work queue,

B. retrieving the first control block from the work queue, and

C. using the queue link pointer of the retrieved control block to alter the head pointer means to identify the next control block in said work queue.

37. A method as defined in claim 27, said source processor generating a plurality of control blocks in response to a command each containing a pointer identifying the first route vector in a route, the operations identified in all of the routes being required to execute the command, the source processor further establishing a counter to identify the number of control blocks generated by said generating means in response to the command, the control blocks associated with the command including counter identification means for identifying the counter, the transfer step including the steps of:

A. determining that the execution processor is executing the last route vector in the route,

B. decrementing said counter means when said processing means has completed performing the operation specified by the route vector.

38. A method as defined in claim 37 the last route vector in each route including a last route vector flag which indicates that it is the last route vector, the determining step including the step of testing the last route vector flag.

39. A method as defined in claim 38 further including the step of the source processor generating an indication that the command has been completed when said counter has decremented to a selected value.

40. A peripheral controller for connection to a host data processing system for controlling transfers of data between external units, including the host system and a peripheral unit, in response to commands from the host system, said peripheral controller comprising a plurality of execution processor means each for connection to an external unit, said peripheral controller further including:

A. memory means including control storage means for storing a route for each command, each route including a sequence of route vectors each including an operation specifying portion identifying an operation to be performed in execution of the command and an execution processor specifying portion identifying and execution processor means for performing the identified operation,

B. source processor means comprising;

(i) means connected to said control storage means for generating, in response to a command from the host system, a control block containing a pointer identifying the first route vector in the route associated with the command and the execution processor means for performing the operation; and

(ii) control block transmitting means connected to said generating means and to all of said execution processor means for coupling the generated control block to the execution processor means to process the first route in the route vector;

C. each execution processor means comprising;

(i) work queue means connected to said control block transmitting means and to said other execution processor means for receiving and storing control blocks,

(ii) means connected to said work queue means for sequentially retrieving the control blocks from its work queue means,

(iii) processing means connected to said retrieving means and to said memory means for retrieving the route vector from said memory means identified by the route vector pointer in the retrieved control block and for performing the operation specified by the identified route vector, and

(iv) transfer means connected to said processing means and to the work queue means of the other execution processors for advancing the route vector pointer in the control block to identify the next route vector in the route and for transferring the control block to the work queue means of the execution processor means that is to execute the route vector identified by the route vector pointer.

41. A peripheral controller as defined in claim 40 wherein said memory means further includes data storage means, each processing means including means for coupling data between said data storage means and the external unit to which it is connected.

42. A peripheral controller as defined in claim 41 wherein one of the external units is divided into a plurality of sectors each for storing a predetermined amount of data, said data storage means being divided into a plurality of segments each for storing a like predetermined amount of data, said source processor means generating a plurality of control blocks each for enabling the execution processor associated with the external unit to transfer data between one of the segments and one of the sectors.

43. A peripheral controller as defined in claim 42 wherein said execution processor associated with said one of said external units includes a plurality of work queue means, retrieving means, processing means, and transfer means each associated with one of said sectors.

44. A peripheral controller as defined in claim 43 wherein said source processor means establishes a counter identifying the number of control blocks associated with a command and identifies the counter in the control blocks associated with the command, each transfer means of said execution processor associated with said one of said external units further including means for decrementing the counter following the execution of the last route vector in the route.

45. A peripheral controller as defined in claim 44 wherein said source processor further includes means for generating a message for transmission to the host system indicating the decrement of the counter to indicate the completion of execution of the last route associated with execution of the command.

46. An execution processor for connection in a peripheral controller that controls transfers of data between external units and host system and a peripheral unit in response to commands from the host system, the peripheral controller including a plurality of execution processors and a memory for storing a route for each command comprising a plurality of route vectors each including an operation specifying portion identifying an operation to be performed in partial execution of the command and an execution processor to perform the operation and a source processor means for generating a control block in response to each command containing a pointer identifying the first route vector in the route associated with the command and for coupling the control block to an execution processor, the execution processor being for connection to an external unit and comprising:

(i) work queue means connected to said source processor means and to said other execution processors for receiving and storing control blocks,

(ii) means connected to said work queue means for sequentially retrieving the control blocks from said work queue means,

(iii) processing means connected to said retrieving means and to said memory means for retrieving the route vector from said memory means identified by the route vector pointer in the retrieved control block and for performing the operation specified by the identified route vector, and

(iv) transfer means connected to said processing means and to the other execution processors for advancing the route vector pointer in the control block to identify the next route vector in the route and for transferring the control block to the execution processor that is to execute the route vector identified by the route vector pointer.

47. An execution processor as defined in claim 46, said memory means further storing data for transfer with said external units, said processing means including means for transferring data between the memory and the external unit.

48. A peripheral controller as defined in claim 47, the external unit being divided into a plurality of sectors each for storing a predetermined amount of data, the memory being divided into a plurality of segments each for storing a like predetermined amount of data, and the source processor means generating a plurality of control blocks each for enabling the execution processor to transfer data between one of the segments and one of the sectors, the execution processor including a plurality of work queue means, retrieving means, processing means, and transfer means each associated with one of said sectors.

49. A peripheral controller as defined in claim 48, the source processor establishing a counter identifying the number of control blocks associated with a command and identifying the counter in the control blocks associated with the command, all of said transfer means further including means for decrementing the counter following the execution of the last route vector in the route.