Apparatus and method for distributed program stack

• US 5,659,701 A
• Filed: 05/17/1994
• Issued: 08/19/1997
• Est. Priority Date: 12/02/1991
• Status: Expired due to Fees

• Current Assignee: International Business Machines Corporation
• Original Assignee: International Business Machines Corporation
• Inventors: Shani, Uri, Amit, Neta Jacob, Marberg, John Michael
• Primary Examiner(s): Kriess, Kevin A.
• Assistant Examiner(s): Chaki, Kakali
• Application Number:
  US08/245,052
• Time in Patent Office: 1,190 Days
• Field of Search: 364/DIG. 1, 364/DIG. 2, 395/200, 395/650, 395/700, 395/200.03, 395/680, 395/684
• US Class Current: 719/317
• CPC Class Codes: G06F 9/547 Remote procedure calls [RPC]; Web services

Abstract

A multi-processor computer system executes a single-thread program having a plurality of callable procedures. The local memory of each processor contains a program stack, the object code of each procedure that executes on that processor, and an agent object. In addition, the local memory contains a c-stub module for each procedure executable on a different processor, and a s-stub module for each local procedure that can be called by a remote procedure. When a procedure P1 executing on processor A calls a procedure P2 which executes in processor B, it issues a local call to P2'"'"'s c-stub in processor A'"'"'s local memory. The P2 c-stub then invokes the agent process in processor A, which communicates with a corresponding agent process in processor B. The agent process in processor B causes P2'"'"'s s-stub in processor B to issue a local call to procedure P2. The return from a procedure follows the same path in reverse. Each processor independently maintains its own version of the program stack, with stack entries referencing the locally executable procedures, local stubs, or local agents. As a result, remote procedure calls are not constrained by the past calling history of a process. A procedure P1 in processor A may call a procedure P2 in processor B, which may in turn call another procedure P3 in processor A. It is therefore possible to convert a conventional single-thread program for operation on a multi-processor system without any significant modification to the source code.

Claims

1. A distributed processing apparatus for executing a program having a plurality of callable procedures, comprising:

a first processor coupled to a first local memory for executing procedures contained in said first local memory;

a second processor coupled to a second local memory for executing procedures contained in said second local memory;

means for communicating data between said first and second processors;

means for a first callable procedure of said program contained in said first local memory to call a second callable procedure of said program contained in said second local memory;

means for said second callable procedure to recursively call a callable procedure contained in said first local memory while executing on behalf of said first callable procedure.

2. The distributed processing apparatus of claim 1, further comprising:

means for maintaining a first program stack contained in said first local memory, said first program stack comprising one or more activation blocks, each activation block containing the state information of an instance of a procedure contained in said first local memory; and

means for maintaining a second program stack contained in said second local memory, said second program stack comprising one or more activation blocks, each activation block containing the state information of an instance of a procedure contained in said second local memory.

3. The distributed processing apparatus of claim 1, further comprising:

means for calling an outer procedure of said program to commence execution of said program in said first processor;

means for automatically establishing a link, without prompting from an external command, between said first procedure and said second procedure, wherein said means for said first callable procedure to call said second callable procedure of is automatically enabled; and

means for automatically establishing a link, without prompting from an external command, between said second procedure and a callable procedure contained in said first local memory, wherein said means for said second callable procedure to call a callable procedure contained in said first local memory while executing on behalf of said first callable procedure is automatically enabled.

4. A distributed processing apparatus for executing a program having a plurality of callable procedures, comprising:

a first processor coupled to a first local memory for executing procedures contained in said first local memory;

a second processor coupled to a second local memory for executing procedures contained in said second local memory;

means for communicating data between said first and second processors;

means for a first callable procedure of said program contained in said first local memory to call a second callable procedure of said program contained in said second local memory, said means comprising;

(a) means for said first callable procedure to issue a first local call to a first c-stub module, said first c-stub module being contained in said first local memory and representing said second callable procedure;

(b) means, responsive to said first local call, for said first c-stub module to communicate data contained in said first local call to a first s-stub module, said first s-stub module contained in said second local memory and representing said second callable procedure;

(c) means, responsive to said means for said first c-stub module to communicate data contained in said first local call to said first s-stub module, for said first s-stub module to issue a second local call to said second callable procedure on behalf of said first callable procedure; and

means for said second callable procedure to call a callable procedure contained in said first local memory while executing on behalf of said first callable procedure, said means comprising;

(a) means for said second callable procedure to issue a third local call to a second c-stub module while said second callable procedure is executing on behalf of said first callable procedure, said second c-stub module being contained in said second local memory and representing said procedure contained in said first local memory which may be called by said second callable procedure while executing on behalf of said first callable procedure;

(b) means, responsive to said third local call, for said second c-stub module to communicate data contained in said third local call to a second s-stub module, said second s-stub module being contained in said first local memory and representing said procedure contained in said first local memory which may be called by said second callable procedure while executing on behalf of said first callable procedure;

(c) means, responsive to said means for said second c-stub module to communicate data contained in said third local call to said second s-stub module, for said second s-stub module to issue a fourth local call to said procedure contained in said first local memory which may be called by said second callable procedure while executing on behalf of said first callable procedure wherein said fourth local call is issued on behalf of said second callable procedure.

5. The distributed processing apparatus of claim 4, wherein said means for said second callable procedure to call a procedure contained in said first local memory comprises means for said second callable procedure to recursively call said first callable procedure.

6. The distributed processing apparatus of claim 4, further comprising:

means for maintaining a first program stack contained in said first local memory, said first program stack comprising one or more activation blocks, wherein each instance of a procedure contained in said first local memory, each instance of a c-stub contained in said first local memory, and each instance of an s-stub contained in said first local memory, is represented by a unique activation block in said first program stack containing the state information of said instance; and

means for maintaining a second program stack contained in said second local memory, said second program stack comprising one or more activation blocks, wherein each instance of a procedure contained in said second local memory, each instance of a c-stub contained in said second local memory, and each instance of an s-stub contained in said second local memory, is represented by a unique activation block in said first program stack containing the state information of said instance.

7. The distributed processing apparatus of claim 4, further comprising:

means for calling an outer procedure of said program to commence execution of said program in said first processor;

means for automatically establishing a link, without prompting from an external command, between said first procedure and said second procedure, wherein said means for said first callable procedure to call said second callable procedure of is automatically enabled; and

means for automatically establishing a link, without prompting from an external command, between said second procedure and a callable procedure contained in said first local memory, wherein said means for said second callable procedure to call a callable procedure contained in said first local memory while executing on behalf of said first callable procedure is automatically enabled.

8. A method for executing a computer program on a multi-processor system, comprising the steps of:

allocating a first set of callable procedures contained in said program to a first processor;

allocating a second set of callable procedures contained in said program to a second processor;

executing, with said first processor, a first callable procedure contained in said first set of callable procedures;

calling, from said first callable procedure, a callable procedure contained in said second set of callable procedures while performing said step of executing, with said first processor, a first callable procedure;

executing, with said second processor, a second callable procedure on behalf of said first callable procedure; and

recursively calling, from said second callable procedure, a callable procedure contained in said first set of callable procedures while performing said step of executing, with said second processor, said second callable procedure.

9. The method of claim 8, further comprising the steps of:

maintaining, in a first local memory of said first processor, a first program stack, said first program stack comprising one or more activation blocks, each activation block containing state information of an instance of a procedure contained in said first local memory; and

maintaining, in a second local memory of said second processor, a second program stack, said second program stack comprising one or more activation blocks, each activation block containing state information of an instance of a procedure contained in said second local memory.

10. The method of claim 8, further comprising the steps of:

calling an outer procedure of said program to commence execution of said program in said first processor;

automatically establishing a link, without prompting from an external command, between said first procedure and a callable procedure contained in said second set, wherein said step of calling, from said first callable procedure, a callable procedure contained in said second set of callable procedures is automatically enabled; and

automatically establishing a link, without prompting from an external command, between said second procedure and a callable procedure contained in said first set of callable procedures, wherein said step of calling, from said second callable procedure, a callable procedure contained in said first set of callable procedures is automatically enabled.

11. A method for executing a computer program on a multi-processor system, comprising the steps of:

allocating a first set of callable procedures contained in said program to a first processor;

allocating a second set of callable procedures contained in said program to a second processor;

executing, with said first processor, a first callable procedure contained in said first set of callable procedures;

calling, from said first callable procedure, a callable procedure contained in said second set of callable procedures while performing said step of executing, with said first processor, a first callable procedure, wherein said step of calling, from said first callable procedure, a callable procedure in said second set comprises the steps of;

(a) issuing a first local call from said first callable procedure to a first c-stub module contained in a first local memory of said first processor;

(b) communicating said first local call to a first s-stub module contained in a second local memory of said second processor;

(c) issuing a second local call from said first s-stub module to a callable procedure in said second set on behalf of said first callable procedure;

executing, with said second processor, a second callable procedure on behalf of said first callable procedure; and

calling, from said second callable procedure, a callable procedure contained in said first set of callable procedures while performing said step of executing, with said second processor, said second callable procedure, wherein said step of calling, from said second callable procedure, a callable procedure contained in said first set of callable procedures comprises the steps of;

(d) issuing a third local call from said second callable procedure to a second c-stub module contained in said second local memory;

(e) communicating said third local call to a second s-stub module contained in said first local memory;

(f) issuing a fourth local call from said second s-stub module to a callable procedure in said first set on behalf of said second callable procedure.

12. The method of claim 11, further comprising the steps of:

maintaining, in said first local memory of said first processor, a first program stack, said first program stack comprising one or more activation blocks, wherein each instance of a procedure contained in said first local memory, each instance of a c-stub contained in said first local memory, and each instance of an s-stub contained in said first local memory, is represented by a unique activation block in said first program stack containing the state information of said instance; and

maintaining, in said second local memory of said second processor, a second program stack, said second program stack comprising one or more activation blocks, wherein each instance of a procedure contained in said second local memory, each instance of a c-stub contained in said second local memory, and each instance of an s-stub contained in said second local memory, is represented by a unique activation block in said second program stack containing the state information of said instance.

13. A method for executing a single-thread computer program having a plurality of callable procedures, comprising the steps of:

allocating each of said plurality of callable procedures in said program to one of a plurality of sets of callable procedures;

storing callable procedures of a first set of said plurality of sets of callable procedures in a first local memory of a first processor of a multi-processor computer system;

storing callable procedures of a second set of said plurality of sets of callable procedures in a second local memory of a second processor of said multi-processor computer system;

executing said program on said multi-processor system, wherein said executing step comprises the steps of;

(a) executing callable procedures contained in said first set of callable procedures on said first processor, wherein at least one procedure in said first set calls a procedure in said second set while executing on behalf of a procedure in said second set; and

(b) executing callable procedures contained in said second set of callable procedures on said second processor, wherein at least one procedure in said second set calls a procedure in said first set while executing on behalf of a procedure in said first set.

14. The method of claim 13, wherein said step of allocating each of said plurality of callable procedures in said program to one of a plurality of sets of callable procedures comprises the step of:

determining, with respect to each said callable procedure, which processor of said multi-processor system should execute the callable procedure, wherein said determination is made without reference to a calling history of said program.

15. The method of claim 14, wherein said first processor executes callable procedures of a first type more efficiently than said second processor, and said second processor executes callable procedures of a second type more efficiently than said first processor, and wherein said determining step determines that callable procedures of said first type should execute on said first processor, and that callable procedures of said second type should execute on said second processor.

16. The method of claim 15, wherein said first processor is a general-purpose commercial transaction processor and said second processor is a numeric-intensive processor.

17. The method of claim 13, wherein said step of executing said program on said multi-processor system comprises the steps of:

calling an outer procedure of said program to commence execution of said program in said first processor;

automatically establishing a link, without prompting from an external command, between a procedure in said first set of callable procedures and a procedure in said second set, wherein the procedure in said first set is automatically enabled to call the procedure in said second set; and

automatically establishing a link, without prompting from an external command, between a procedure in said second set of callable procedures and a procedure in said first set, wherein the procedure in said first set is automatically enabled to call the procedure in said second set.

18. A method for adapting a single-thread computer program having a plurality of callable procedures and originally written to execute on a single processor system to execute on a multi-processor system, said method comprising the machine-executed steps of:

creating a first partition of said computer program, said first partition comprising a first set of callable procedures;

creating a second partition of said computer program, said second partition comprising a second set of callable procedures, wherein said first and second sets are disjoint;

wherein a callable procedure in said first set of callable procedures contains a call to a callable procedure in said second set of callable procedures;

wherein a callable procedure in said second set of callable procedures contains a call to a callable procedure in said first set of callable procedures;

placing in said first partition means for a receiving a local call from a procedure in said first set to a procedure in said second set;

placing in said second partition means for issuing a local call to a procedure in said second set on behalf of a procedure in said first set;

placing in said second partition means for receiving a local call from a procedure in said second set to a procedure in said second set; and

placing in said first partition means for issuing a local call to a procedure in said first set on behalf of a procedure in said second set.

19. The method of claim 18, wherein said multi-processor system comprises a first processor and a second processor, wherein said first processor executes callable procedures of a first type more efficiently than said second processor, and said second processor executes callable procedures of a second type more efficiently than said first processor, and wherein said steps of creating a first partition and creating a second partition allocate procedures of said first type to said first partition and procedures of said second type to said second partition.

20. The method of claim 19, wherein said first processor is a general-purpose commercial transaction processor and said second processor is a numeric-intensive processor.

21. A program product for execution on a multi-processor computer system, said program product having a plurality of computer executable instructions recorded on a computer readable recording medium, said plurality of computer executable instructions representing a computer program for execution in single-thread mode, said program product comprising:

a first partition of said computer program for execution on a first processor of said multi-processor system, said first partition comprising a plurality of callable procedures executable on said first processor;

a second partition of said computer program for execution on a second processor of said multi-processor system, said second partition comprising a plurality of callable procedures executable on said second processor;

means in a first callable procedure contained in said first partition, when executing on said first processor of said multi-processor system, for issuing a call to a callable procedure in said second partition while executing on behalf of a callable procedure in said second partition;

means in a second callable procedure contained in said second partition, when executing on said second processor of said multi-processor system, for issuing a call to a callable procedure contained in said first partition while executing on behalf of said first callable procedure.

22. The program product of claim 21, wherein said second callable procedure comprises means for recursively calling said first callable procedure.

23. The program product of claim 21, further comprising:

a first c-stub module contained in said first partition and representing a callable procedure contained in said second partition;

a first s-stub module contained in said second partition and representing said first callable procedure;

a second c-stub module contained in said second partition and representing a callable procedure contained in said first partition;

a second s-stub module contained in said first partition and representing said second callable procedure;

wherein said means, contained in said first callable procedure, for issuing a call to a procedure in said second partition, comprises means for issuing a first local call to said first c-stub module;

wherein said first c-stub module comprises means for sending data to said first s-stub module in response to said first local call;

wherein said first s-stub module comprises means for issuing a second local call to a callable procedure contained in said second partition, on behalf of said first callable procedure;

wherein said means, contained in said second callable procedure, for issuing a call to a callable procedure contained in said first partition while executing on behalf of said first callable procedure, comprises means for issuing a third local call to said second c-stub module;

wherein said second c-stub module comprises means for sending data to said second s-stub module in response to said third local call; and

wherein said second s-stub module comprises means for issuing a fourth local call to a callable procedure contained in said first partition on behalf of said second callable procedure.

24. A distributed processing apparatus for executing a program having a plurality of callable procedures, comprising:

a first processor coupled to a first local memory for executing procedures contained in said first local memory;

a second processor coupled to a second local memory for executing procedures contained in said second local memory;

means for communicating data between said first and second processors;

means for maintaining a first program stack contained in said first local memory, said first program stack comprising one or more activation blocks, each activation block containing state information of an instance of a procedure contained in said first local memory;

means for maintaining a second program stack contained in said second local memory, said second program stack comprising one or more activation blocks, each activation block containing state information of an instance of a procedure contained in said second local memory;

means for a first instance of a callable procedure of said program contained in said first local memory to call a second instance of a callable procedure of said program contained in said second local memory;

means for said second instance of a callable procedure to call a third instance of a callable procedure contained in said first local memory while executing on behalf of said first instance of a callable procedure; and

means for said third instance of a callable procedure to call an instance of a callable procedure contained in said second local memory while executing on behalf of said first and second instances of callable procedures.

25. The distributed processing apparatus of claim 24, wherein said means for a third instance of a callable procedure to call an instance of a callable procedure in said second local memory comprises means for said third instance to recursively call a procedure in said second local memory.

26. The distributed processing apparatus of claim 24, further comprising means for instances of callable procedures contained in said first and second local memories to alternately call instances of callable procedures contained in the respective opposite local memory, up to and including an Nth instance of a callable procedure contained in the (((N-1) modulo 2)+1) ordered local memory to call an instance of a callable procedure contained in the ((N modulo 2)+1) ordered local memory while executing on behalf of callable procedure instances 1 through (N-1), wherein the value of N is limited only by a maximum size of said first and second program stacks.

27. A distributed processing apparatus for executing a program having a plurality of callable procedures, comprising:

a first processor coupled to a first local memory for executing a first set of callable procedures of said program from said first local memory;

a second processor coupled to a second local memory for executing a second set of callable procedures of said program from said second local memory;

a communications connection for communicating data between said first and second processors;

means for maintaining a first program stack contained in said first local memory, said first program stack containing state information for each instance of a procedure of said first set;

means for maintaining a second program stack contained in said second local memory, said second program stack containing state information for each instance of a procedure of said second set;

a bi-directional peer-to-peer remote procedure call mechanism,

said remote procedure call mechanism enabling a callable first procedure executing on said first processor and contained in said first set of callable procedures to call a callable procedure in said second set of callable procedures for execution on said second processor, while said first procedure is executing on behalf of a procedure in said second set of callable procedures,

said remote procedure call mechanism enabling a callable second procedure executing on said second processor and contained in said second set of callable procedures to call a callable procedure in said first set of callable procedures for execution on said first processor, while said second procedure is executing on behalf of a procedure in said first set of callable procedures; and

wherein said means for maintaining a first program stack and said means for maintaining a second program stack update said respective first and second program stacks in response to a remote procedure call executed by said remote procedure call mechanism.

28. The distributed processing apparatus of claim 27, wherein,

said first program stack is not updated in response to a local call of a callable procedure in said second set by a callable procedure of said second set executing on said second processor;

and

said second program stack is not updated in response to a local call of a callable procedure in said first set by a callable procedure of said first set executing on said first processor.

29. The distributed processing apparatus of claim 27, wherein said remote procedure call mechanism enables callable procedures contained in said first and second local memories to alternately call instances of callable procedures contained in the respective opposite local memory, up to and including an Nth instance of a callable procedure contained in the (((N-1) modulo 2)+1) ordered local memory to call an instance of a callable procedure contained in the ((N modulo 2)+1) ordered local memory while executing on behalf of callable procedure instances 1 through (N-1), wherein the value of N is limited only by a maximum size of said first and second program stacks.

30. A distributed processing apparatus for executing a program having a plurality of callable procedures, comprising:

a first processor coupled to a first local memory for executing procedures contained in said first local memory;

a second processor coupled to a second local memory for executing procedures contained in said second local memory;

means for communicating data between said first and second processors;

means for a first callable procedure of said program contained in said first local memory to make a first local call to a second callable procedure of said program contained in said second local memory;

means for said second callable procedure to make a second local call a callable procedure contained in said first local memory while executing on behalf of said first callable procedure.

31. A method for executing a computer program on a multi-processor system, comprising the steps of:

allocating a first set of callable procedures contained in said program to a first processor of said multi-processor system;

allocating a second set of callable procedures contained in said program to a second processor of said multi-processor system;

executing, with said first processor, a first callable procedure contained in said first set of callable procedures;

calling, from said first callable procedure, a callable procedure contained in said second set of callable procedures while performing said step of executing, with said first processor, a first callable procedure, wherein said calling step is performed via a local call using said first and second processors;

executing, with said second processor, a second callable procedure on behalf of said first callable procedure; and

recursively calling, from said second callable procedure, a callable procedure contained in said first set of callable procedures while performing said step of executing, with said second processor, said second callable procedure, wherein said recursively calling step is performed via a local call using said first and second processors.