Operating system for use with computer networks incorporating one or more data processors linked together for parallel processing and incorporating improved dynamic binding and/or load-sharing techniques

• US 5,930,511 A
• Filed: 06/21/1995
• Issued: 07/27/1999
• Est. Priority Date: 10/30/1992
• Status: Expired due to Term

• Current Assignee: Tao Group Limited (Tao Media Ltd.)
• Original Assignee: Tao Group Limited (Tao Media Ltd.)
• Inventors: Hinsley, Christopher Andrew
• Primary Examiner(s): Banankhah, Majid A.
• Application Number:
  US08/424,367
• Time in Patent Office: 1,497 Days
• Field of Search: 395/650, 395/700, 395/675, 395/705, 395/706, 395/710, 395/711, 395/707
• US Class Current: 717/164
• CPC Class Codes: G06F 2209/501 Performance criteria
• CPC Class Codes: G06F 2209/5017 Task decomposition
• CPC Class Codes: G06F 8/45 Exploiting coarse grain parallelism in compilation, i.e. parallelism between groups of instructions
• CPC Class Codes: G06F 9/445 Program loading or initiating bootstrapping G06F9/4401; security arrangements for program loading or initiating G06F21/57
• CPC Class Codes: G06F 9/5027 the resource being a machine, e.g. CPUs, Servers, Terminals
• CPC Class Codes: G06F 9/5044 considering hardware capabilities
• CPC Class Codes: G06F 9/5088 involving task migration

Abstract

A data processing system is disclosed incorporating one or more processors linked together in a network and capable of parallel processing using a plurality of individual code segments common to all the data processors in the system but written for a virtual processor in a virtual processor code language which is different from that of all the data processors in the system. The code segments form unique autonomous tools common to all the processors in the system and are selected, translated and bound into a complete executable task by each individual processor at the time of loading or execution of a task by the respective processor.

Claims

1. A data processing system comprising:

one or more data processors having a local memory and executing coded instructions written in a program code language native to that data processor; and

a store containing a collection of independent program code segments available to and shared by all the data processors in the system if more than one, the program code segments being written for a virtual processor using a predefined, virtual processor program code language different from the native program code language of the or each of the data processors, each independent program code segment in the collection constituting an individual program tool individually selectable and individually loadable, independent of other program code segments in the collection, into the local memory of each data processor for the purpose of executing data processing tasks allocated to that processor;

the one or more data processors each including;

a selector individually selecting from the collection of independent program code segments only specific ones of the program code segments from the collection required by the data processor for the execution of a current task allocated to the data processor;

a loader individually loading only the selected program code segments from the collection into the local memory of the data processor;

a translator translating the selected program code segments from the virtual processor program code language into the native program code language of the data processor in question to provide a plurality of translated program code segments; and

a binder binding the translated program code segments into an executable task to be performed by the data processor,

wherein only the selected program code segments required for execution of the task are translated and bound into the executable task just at the time of loading the selected program code segments into the local memory of the data processor or during the execution of the task by the data processor.

2. A system as claimed in claim 1, wherein the binder receives a message commanding execution of a task, determines those program code segments not stored in the local memory which are required for execution of the commanded task, and retrieves those determined program code segments, and wherein the translator translates the retrieved program code segment and stores the translated program code segments in the local memory.

3. A system as claimed in claim 2, wherein the binder employs a usage flag corresponding to each translated program code segment, the usage flag being incremented when the corresponding program code segment is referenced by a task and decremented when the corresponding program code segment is de-referenced by a task, and inhibits removal of the translated program code segment from the local memory when the corresponding usage flag indicates usage of the respective translated program code segment.

4. A system as claimed in claim 2, wherein the collection of program code segments includes a kernel of process objects and a group of tool objects, and where each of the tool objects may be called by one or more of the process objects to act upon selected data.

5. A system as claimed in claim 1, wherein the data processor is one of a plurality of data processors connected as nodes in a network of processors that parallel process allocated tasks, the collection of independent program code segments being common to and shared by all the processors in the system at the same time.

6. A system as claimed in claim 5, wherein the data processors are of different types and operate using a respective one of several different native program code languages, wherein the virtual processor program code language is common to the system, and wherein the translator of each data processor translates selected program code segments from the common virtual program code processor language to the respective program code language of that data processor.

7. A data processing system comprising:

a plurality of data processors connected as nodes in a network of processors performing data processing tasks in parallel, each processor having a local memory and executing coded instructions written in a program code language native to that data processor; and

a store containing a collection of independent program code segments available to and shared by all the data processors in the system, the program code segments being written for a virtual processor using a predefined virtual processor program code language different from the native program code language of the data processors in the system, each independent program code segment constituting an individual program tool individually selectable and individually loadable, independent of other program code segments in the collection, into the local memory of each respective data processor for the purpose of executing data processing tasks allocated to that data processor;

each of the data processors including;

a selector individually selecting from the collection of independent program code segments only specific ones of the code segments required by the data processor for the execution of a current task allocated to the data processor;

a loader individually loading only the selected code segments from the collection to the local memory of the processor;

a translator translating the selected program code segments from the virtual processor program code language into the native program code language of the data processor in question to provide a plurality of translated program code segments; and

a binder binding the translated program code segments into the executable task to be performed by the data processor;

wherein only the selected program code segments required for execution of the task are translated and bound into the executable task just at the time of loading the selected program code segments into the local memory of the data processor or during the execution of the task by the data processor, and

wherein the network performs an allocation process in which each of the data processors in the network, upon being allocated a process, decides at the time that the process is allocated whether that one processor or a neighboring processor in the network is better able at that process allocation time to perform the process, and if the one processor decides that the one processor is better able at that process allocation time to perform the process than any of the neighboring processors, the one processor performs the process, and if the one processor decides that one of the neighboring processors is better able at that process allocation time to perform the process, the one processor reallocates the process to the one neighboring processor.

8. A system as claimed in claim 7, wherein in the allocation process:

the one processor determines a rating of itself representing its own ability at that process allocation time to perform the process, compares that rating with corresponding ratings obtained from its neighboring processors to determine which of the processors has the highest rating, and allocates the process to the neighboring processor having the highest rating unless the one processor has the highest rating, in which case, the one processor performs the process.

9. A system as claimed in claim 8, wherein if the one processor and at least one of said neighboring processors have equal highest ratings, the one processor performs the process.

10. A system as claimed in claim 8, wherein the rating of each processor is determined from the number of processes currently operating on that processor.

11. A system as claimed in claim 10, wherein said rating of each processor is determined from an effective-operations-per-second rating of that processor divided by the number of processes running at that processor multiplied by a function of off-chip communication speed available to that processor.

12. A system as claimed in claim 7, wherein said rating of each processor is determined from an available amount of local memory of that processor.

13. A system as claimed in claim 7, wherein if the one processor allocates the process to a neighboring processor, that neighboring processor repeats the allocation process to decide whether that neighboring processor should perform the process or reallocate the process to another neighboring processor.

14. A system as claimed in claim 7, wherein the one processor allocates the process to the neighboring processor by providing the neighboring processor with a number of bytes required, a name of the process, and an address at which the process is currently stored.

15. A system as claimed in claim 7, wherein information relating to the ability of the processors to perform processes is added to other messages passed between the processors.

16. A system as claimed in claim 7, wherein information relating to the ability of the processors to perform processes is passed between pairs of processors at adjacent nodes when no other information is being passed between those processors.

17. A data processing system comprising:

a plurality of data processors, connected as nodes in a network, performing parallel processing tasks allocated to those processors, each processor having a local memory and executing coded instructions written in a program code language native to that data processor; and

a store containing a collection of independent program code segments available to and shared by all the data processors in the system, each code segment constituting an individual program tool individually selectable and individually loadable, independent of other program code segments in the collection, into the local memory of each respective data processor, and bindable when so loaded with other individual selected and individually loaded program tools to form a task executable jointly by two or more of those processors,

each of the data processors includes;

a selector individually selecting from the collection of independent program code segments only specific ones of the program code segments from the collection required by the data processor for the joint execution of a current task jointly allocated to the data processor and another data processor in the network;

a loader individually loading only the selected program code segments from the collection into the local memory of the data processor; and

a binder binding only the individually selected program code segments into the task to be jointly executed by the data processor and another data processor, the selected program code segments being bound into a task executable jointly by both data processors only at the time of loading the selected code segments into the local memory of both data processors or during execution of the task by both data processors.

18. A method of processing data in an electronic data processor executing coded instructions written in a program code language native to that data processor, comprising the steps of:

providing a collection of independent program code segments written for a virtual processor using a predefined virtual processor program code language different from the native program code language of the data processor, each of the independent code segments in the collection constituting an individual program tool individually selectable and individually loadable, independent of other program code segments in the collection, into the local memory of the data processor, and bindable when so loaded with other such individually selected and loaded tools to form a task executable by the processor;

instructing the data processor to execute a task;

electronically selecting from the collection of independent code segments only specific ones of the program code segments required by the processor to perform the task;

electronically loading only the selected program code segments into the local memory of the processor;

electronically translating the selected code segments from the virtual processor program code language into the native program code language of the data processor;

binding the translated program code segments into a task executable by the data processor; and

executing the task in accordance with the translated and bound code segments,

wherein the translating and binding of only the selected code segments required for execution of the task into the executable task takes place just at the time of loading the selected program code segments into the local memory of the data processor or at the time of execution of the task by the data processor.

19. A method of processing data in a data processing system including a plurality of electronic data processors each having a local memory and executing coded instructions written in its own native program code language, the data processors performing processes in parallel, comprising the steps of:

providing a collection of independent program code segments accessible to and shared by all the data processors in the system and enabling the data processors to perform data processing tasks allocated to them, each program code segment constituting an individual program tool individually selectable and individually loadable, independent of other program code segments in the collection, into the local memory of a respective one of the processors, and bindable by the one processor with other such individually selected and individually loaded program tools to form a task executable jointly by two or more of those processors;

instructing two or more of the data processors jointly to perform a task;

selecting from the collection of independent program code segments only those program code segments needed by the two or more data processors for the joint execution of an allocated task;

loading the selected program code segments into the respective local memories of the two or more data processors;

binding the selected program code segments into a task executable by the data processors and in accordance with the jointly allocated task; and

the two or more data processors jointly executing the task;

where the binding of the selected code segments into the task executable jointly by the two or more data processors takes place only at the time of loading the selected program code segments into the respective local memories of the two or more processors or during execution of the task by the two or more data processors.