Process for allocating memory in a multiprocessor data processing system

• US 6,272,612 B1
• Filed: 09/02/1998
• Issued: 08/07/2001
• Est. Priority Date: 09/04/1997
• Status: Expired due to Fees

• Current Assignee: Bull Sas (Atos SE)
• Original Assignee: Bull Sas (Atos SE)
• Inventors: Bordaz, Thierry, Romand, Patrice, Sorace, Jean-Dominique
• Primary Examiner(s): Yoo, Do Hyun
• Assistant Examiner(s): MCLEAN MAYO, KIMBERLY N
• Application Number:
  US09/145,642
• Time in Patent Office: 1,070 Days
• Field of Search: 711/203, 711/216, 711/209, 711/170, 711/171, 711/172, 711/173, 711/147, 711/148, 711/153
• US Class Current: 711/203
• CPC Class Codes: G06F 12/1072 Decentralised address translation, e.g. in distributed shared memory systems
• CPC Class Codes: G06F 12/121 using replacement algorithms
• CPC Class Codes: G06F 9/5016 the resource being the memory

Abstract

The invention relates to a process for allocating physical memory locations in a multiprocessor data processing system comprising a non-uniform access memory unit distributed among a plurality of modules. Software applications are linked to a set of predefined memory allocation rules. When there is no entry for a virtual address in an address correspondence table, there is a generation of a page fault, and the allocation of a location in physical memory is carried out in accordance with a predefined rule as a function of the profile of the application and of the page fault type. The memory may be organized into segments and the segments subdivided into virtual address ranges, with the ranges associated with a specific memory allocation policy. In the case where there is an entry for a virtual address in an address correspondence table, the policy of the segment prevails.

Claims

1. A process for allocating physical main memory locations by mapping with at least one range of contiguous memory addresses in a virtual address space, associated with a given software application (Appli_x), the application (Appli_x) being run in a data processing system (1¹, 1ⁿ) comprising a non-uniform access memory unit (Mem) and using a plurality of virtual memories (tyM₁-tyM₆), said mapping being carried out by scanning an address correspondence table, and without modifying at least one of said software applications running in said data processing system, characterized in that said process comprises:

linking said given software application (Appli_x) to memory allocation rules (Rg) chosen from a set of predefined rules;

generating an exception (Fp) and allocating a physical main memory location (Z₁-Z_n) according to one of said memory allocation rules (Rg), when said address correspondence table does not comprise an entry for a contiguous memory address range of a virtual address associated with said given software application (Appli_x), the choice of the rule being subject to a profile (Pa_x) of said virtual memories (tyM₁-tyM₆) used by the given software application (Appli_x);

wherein said ranges of contiguous virtual memory addresses are subdivided into a plurality of categories causing distinct exception types (Fp), and said process further comprising determining said distinct exception type (Fp), said memory allocation rule being a function of the combination of said profile and said exception type (Fp);

wherein said virtual address space is organized into segments (Sg_x, Sg_y) associated with said memory allocation rules (Rg);

wherein said segments are subdivided into virtual address ranges (Ra₁-Ra₅), each being allocated to at least one of said applications (Appli_x), and comprising providing a first digital datum, specifying whether there is at least one virtual address range (Ra₁-Ra₅) with which a specific memory allocation rule is associated, and in at least one second digital datum specifying the nature of said memory allocation rule and providing a third digital datum comprised of an optional number addressing one of said modules (Ma-Mc);

wherein said second digital datum specifies at least one of the following rules;

a first rule allocating a memory location exclusively in said local memory unit;

a second rule allocating a memory location by distribution, in slices, in said local memory unit and said remote memory units;

a third rule allocating a pre-established fixed memory location in said local memory unit or said remote memory units, and

a fourth default rule, allocating a memory location according to a global memory allocation policy of said data processing system, said fourth rule being the type of one of said first through third rules;

wherein said memory allocation policy records comprise two supplementary fields, a first field storing a digital datum specifying the lower address boundary, in a given segment (Sg_x, Sg_y), of said virtual address range (Ra₁-Ra₅), and a second field storing a digital datum specifying the upper address boundary of this virtual address range, and said process further comprises the following phases;

a preliminary phase comprised of creating, at the request of said applications, for each segment comprising at least one virtual range associated with a specific memory allocation policy, a list structure comprising a number of cascaded elements (LRa₁-LRa_z) equal to the number of said virtual address ranges (Ra₁-Ra₅) comprised in said segment (Sg_x, Sg_y), each element storing said memory allocation policy records as well as said first and second supplementary address fields, and being associated with one of the virtual address ranges (Ra₁-Ra₅);

a subsequent phase, upon the generation of an exception (Fp) at an address comprised in a given segment (Sg_x, Sg_y) comprising at least the following steps;

a/ successive steps comprised of reading the digital data stored in said elements of the cascaded list structure (LRa₁-LRa_z);

b/ for each of the list elements, a step comprised of comparing said address having caused the exception (Fp) with said lower and upper address boundaries, and

c/ in case of a positive comparison, a step for reading said second and third digital datum, in order to generate a physical memory allocation instruction in accordance with said rule, and carried out in the module (Ma-Mc) whose number has optionally been specified as a function of this rule, or in the absence of a rule specified by said second digital datum, to allocate a physical memory location in accordance with the memory allocation rules governing the segment (Sg_x, Sg_y) that includes the virtual address range (Ra₁-Ra₅).

2. The process according to claim 1, characterized in that, said data processing system (1′

, 1″

) is constituted by at least two distinct modules (Ma-Mc), each comprising at least one processor (10a-13a, 10b-13b) and a local physical memory unit (14a, 14b), the memory units located outside one module being called remote memory units with respect to memory units in another module, and said set of predefined rules (Rg) comprises at least the following specific rules for allocating memory upon the generation of an exception (Fp);

a first rule allocating a memory location exclusively in a local memory unit;

a second rule allocating a memory location by distribution in slices in said local memory unit and said remote memory unit, and

a third rule allocating a preestablished fixed memory location, in said local memory unit or said remote memory units, in reference to a number assigned to said modules.

3. The process according to claim 1, wherein said data processing system (1′

, 1″

) is constituted by at least two distinct modules (Ma-Mc), each comprising at least one processor (10a-13a, 10b-13b) and a local physical memory unit (14a, 14b), the memory units located outside one module being called remote memory units with respect to memory units in another module, and said set of predefined rules (Rg) comprises at least the following specific rules for allocating memory upon the generation of an exception (Fp);

a first rule allocating a memory location exclusively in a local memory unit;

a second rule allocating a memory location by distribution in slices in said local memory unit and said remote memory unit, and

a third rule allocating a preestablished fixed memory location, in said local memory unit or said remote memory units, in reference to a number assigned to said modules.

4. The process according to claim 1, wherein said data processing system (1′

, 1″

) is constituted by at least two distinct modules (Ma-Mc), each comprising at least one processor (10a-13a, 10b-13b) and a local physical memory unit (14a, 14b), the memory units located outside one module being called remote memory units with respect to memory units in another module, and said set of predefined rules (Rg) comprises at least the following specific rules for allocating memory upon the generation of an exception (Fp);

a first rule allocating a memory location exclusively in a local memory unit;

a second rule allocating a memory location by distribution in slices in said local memory unit and said remote memory unit, and

a third rule allocating a preestablished fixed memory location, in said local memory unit or said remote memory units, in reference to a number assigned to said modules.

5. The process according to claim 1, wherein said data processing system (1′

, 1″

) is constituted by at least two distinct modules (Ma-Mc), each comprising at least one processor (10a-13a, 10b-13b) and a local physical memory unit (14a, 14b), the memory units located outside one module being called remote memory units with respect to memory units in another module, said set of predefined rules (Rg) comprises at least the following specific rules for allocating memory upon the generation of an exception (Fp);

a first rule allocating a memory location exclusively in a local memory unit;

a second rule allocating a memory location by distribution in slices in said local memory unit and said remote memory unit, and

a third rule allocating a preestablished fixed memory location, in said local memory unit or said remote memory units, in reference to a number assigned to said modules.

6. The process according to claim 2, characterized in that it comprises at least one additional predetermined memory allocation rule called a default rule, the memory allocation being carried out in accordance with said default rule when said given software application (Appli_x) having caused an exception (Fp) is not linked to any of said specific rules.

7. The process according to claim 2, characterized in that, said given software application (Appli_x) comprises at least one memory segment shared with other software applications and accessed in a substantially equal way by said modules (Ma, Mb), and said subsequent step for allocating a location of physical memory (Mem) is carried out in accordance with said second rule by distribution in said local and remote memory units (14a, 14b).

8. The process according to claim 2, characterized in that, said given software application (Appli_x) comprises at least one working memory segment accessed locally in one of said modules (Ma-Mc), and said subsequent step for allocating a location of physical memory (Mem) is carried out in accordance with said first rule, the allocation being carried out exclusively in said local memory unit (14a or 14b).

9. The process according to claim 1, wherein at the time of said generation of an exception (Fp) related to an address comprised in said virtual address range (Ra₁-Ra₅), a step for reading said first digital datum, and a subsequent step comprised of allocating a physical memory location in accordance with the memory allocation rules ruling the segment (Sg_x, Sg_y) when said exception translates into an addressing of the memory that does not correspond to any of said virtual address ranges (Ra₁-Ra₅).

10. The process according to claim 1, wherein when said second digital datum specifies said second or third memory allocation rules, said third datum comprised of a module number (Ma-Mc) is determined.

11. The process according to claim 1, wherein said data processing system comprising a table for describing the segments (Scb) comprises a number of entries equal to the number of said segments (Sg_x, Sg_y) of said virtual space, and further comprises a step for recording said memory allocation policies in said segment description table (Scb) and a step for recording said profiles (Pa_x) in virtual memory spaces occupied by said applications (Appli_x) that are associated with said profiles.

12. The process according to claim 10, wherein said data processing system comprising a table for describing the segments (Scb) comprises a number of entries equal to the number of said segments (Sg_x, Sg_y) of said virtual space, and further comprises an initial step for recording said memory allocation policies in said segment description table (Scb) and an initial step for recording said profiles (Pa_x) in virtual memory spaces occupied by said applications (Appli_x) that are associated with said profiles.

13. The process according to claim 11, characterized in that each of said memory allocation policy records (Mp_y) comprises at least a first field for storing said first digital datum, a second field for storing said second digital datum and a third field for storing said third digital datum.

14. The process according to claim 12, characterized in that each of said memory allocation policy records (Mp_y) comprises at least a first field for storing said first digital datum, a second field for storing said second digital datum and a third field for storing said third digital datum.

15. The process according to claim 14, characterized in that said memory allocation policy records comprise two supplementary fields, a first field storing a digital datum specifying the lower address boundary, in a given segment (Sg_x, Sg_y), of said virtual address range, and a second field storing a digital datum specifying the upper address boundary of this virtual address range, and in that said process further comprises the following phases:

a preliminary phase comprised of creating, at the request of said applications, for each segment comprising at least one virtual range associated with a specific memory allocation policy, a list structure comprising a number of cascaded elements (LRa₁-LRa_z) equal to the number of said virtual address ranges (Ra₁-Ra₅) comprised in said segment (Sg_x, Sg_y), each element storing said memory allocation policy records as well as said first and second supplementary address fields, and being associated with one of the virtual address ranges (Ra₁-Ra₅);

a subsequent phase, upon the generation of an exception (Fp) at an address comprised in a given segment (Sg_x, Sg_y) comprising at least the following steps;

a/ successive steps comprised of reading the digital data stored in said elements of the cascaded list structure (LRa₁-LRa_z);

b/ for each of the list elements, a step comprised of comparing said address having caused the exception (Fp) with said lower and upper address boundaries, and

c/ in case of a positive comparison, a step for reading said second and third digital datum, in order to generate a physical memory allocation instruction in accordance with said rule, and carried out in the module (Ma-Mc) whose number has optionally been specified as a function of this rule, or in the absence of a rule specified by said second digital datum, to allocate a physical memory location in accordance with the memory allocation rules governing the segment (Sg_x, Sg_y) that includes the virtual address range (Ra₁-Ra₅).

16. The process according to claim 13, characterized in that said memory allocation records comprise two supplementary fields, a first field storing a digital datum specifying a lower address boundary, in a given segment, of said virtual address range (Ra₁-Ra₅) and a second field storing a digital datum specifying an upper address boundary of said virtual address range (Ra₁-Ra₅), and in that said process further comprises the following phases:

a first preliminary supplementary phase comprising the following steps;

1/ a first step comprised of subdividing each of said segments (Sg_y) comprising at least one virtual range associated with a specific policy for allocating memory in subsegments (SS₁-SS_N) having the same fixed lengths; and

2/ a second step comprised of creating a table (Th) comprising as many entries (e₁-e_N) as there are subsegments (SS₁-SS_N);

a second preliminary supplementary phase comprised of creating, for each subsegment (SS₁-SS_N) associated with each of said entries, a list structure (LRa₁₂-LRa₂₂, LRa₁₄, LRa₁₇-LRa₃₇) comprising a number of cascaded elements equal to the number of said virtual address ranges (Ra₀₂-Ra₂₂) comprised in the subsegment (SS₁-SS_N), each element storing said memory allocation policy records as well as said first and second supplementary address fields, and being associated with one of the virtual address ranges (Ra₀₂-Ra₂₂);

a subsequent phase, upon the generation of an exception at an address comprised in a given subsegment (SS₁-SS_N) comprising at least the following steps;

a/ the reading of said entry of the table (Th) associated with the address having caused said exception and the determination based on said reading of whether or not said subsegment (SS₁-SS_N) includes a virtual address range (Ra₁-Ra₅) governed by a specific memory allocation policy, and in case of a negative determination, the utilization of the rule governing said segment (Sg_y);

b/ in case of a positive determination, successive steps comprised of the reading of the digital data stored in said elements of the cascaded list structure (LRa₁₂-LRa₂₂, LRa₁₄, LRa₁₇-LRa₃₇) associated with the entry linked to the address having caused said exception;

c/ for each of the list elements (LRa₁₂-LRa₂₂, LRa₁₄, LRa₁₇-LRa₃₇), a step comprised of comparing said address having caused the exception to said lower and upper address boundaries;

d/ in case of a positive comparison, a step for reading said second and third digital datum, in order to generate a physical memory allocation instruction in accordance with said rule and carried out in the module number (Ma-Mc) optionally specified as a function of this rule.

17. The process according to claim 14, characterized in that said memory allocation records comprise two supplementary fields, a first field storing a digital datum specifying a lower address boundary, in a given segment, of said virtual address range (Ra₁-Ra₅) and a second field storing a digital datum specifying an upper address boundary of said virtual address range (Ra₁-Ra₅), and in that said process further comprises the following phases:

a first preliminary supplementary phase comprising the following steps;

1/ a first step comprised of subdividing each of said segments (Sg_y) comprising at least one virtual range associated with a specific policy for allocating memory in subsegments (SS₁-SS_N) having the same fixed lengths; and

2/ a second step comprised of creating a table (Th) comprising as many entries (e₁-e_N) as there are subsegments (SS₁-SS_N)

a second preliminary supplementary phase comprised of creating, for each subsegment (SS₁-SS_N) associated with each of said entries, a list structure (LRa₁₂-LRa₂₂, LRa₁₄, LRa₁₇-LRa₃₇) comprising a number of cascaded elements equal to the number of said virtual address ranges (Ra₀₂-Ra₂₂) comprised in the subsegment (SS₁-SS_N), each element storing said memory allocation policy records as well as said first and second supplementary address fields, and being associated with one of the virtual address ranges (Ra₀₂-Ra₂₂);

a subsequent phase, upon the generation of an exception at an address comprised in a given subsegment (SS₁-SS_N) comprising at least the following steps;

a/ the reading of said entry of the table (Th) associated with the address having caused said exception and the determination based on said reading of whether or not said subsegment (SS₁-SS_N) includes a virtual address range (Ra₁-Ra₅) governed by a specific memory allocation policy, and in case of a negative determination, the utilization of the rule governing said segment (Sg_y);

b/ in case of a positive determination, successive steps comprised of the reading of the digital data stored in said elements of the cascaded list structure (LRa₁₂-LRa₂₂, LRa₁₄, LRa₁₇-LRa₃₇) associated with the entry linked to the address having caused said exception;

c/ for each of the list elements (LRa₁₂-LRa₂₂, LRa₁₄, LRa₁₇-LRa₃₇), a step comprised of comparing said address having caused the exception to said lower and upper address boundaries;

d/ in case of a positive comparison, a step for reading said second and third digital datum, in order to generate a physical memory allocation instruction in accordance with said rule and carried out in the module number (Ma-Mc) optionally specified as a function of this rule.

18. The process according to claim 16, characterized in that, said virtual memory address ranges (Ra₀₂-Ra₂₂) have variable lengths, and when said length is greater than the length of said subsegments (SS₁-SS_N) of fixed length, subdividing said virtual memory address ranges into sub-spaces comprised in subsegments (SS₁-SS_N).

19. The process according to claim 17, characterized in that, said virtual memory address ranges (Ra₀₂-Ra₂₂) have variable lengths, and when said length is greater than the length of said subsegments (SS₁-SS_N) of fixed length, subdividing said virtual memory address ranges into sub-spaces comprised in subsegments (SS₁-SS_N).

20. The process according to claim 16, characterized in that said segments (Sg_y) extend over a contiguous virtual space of 256 MB, and in that said table (Th) comprises 256 entries (e₁-e_N), each of which corresponds to a subsegment (SS₁-SS_N) of 1 MB.

21. The process according to claim 17, characterized in that said segments (Sg_y) extend over a contiguous virtual space of 256 MB, and in that said table (Th) comprises 256 entries (e₁-e_N), each of which corresponds to a subsegment (SS₁-SS_N) of 1 MB.

22. The process according to claim 18, characterized in that said segments (Sg_y) extend over a contiguous virtual space of 256 MB, and in that said table (Th) comprises 256 entries (e₁-e_N), each of which corresponds to a subsegment (SS₁-SS_N) of 1 MB.

23. The process according to claim 19, characterized in that said segments (Sg_y) extend over a contiguous virtual space of 256 MB, and in that said table (Th) comprises 256 entries (e₁-e_N), each of which corresponds to a subsegment (SS₁-SS_N) of 1 MB.