TOP > 外国特許検索 > Memory management method, information processing device, program creation method, and program

Memory management method, information processing device, program creation method, and program

外国特許コード F110003067
整理番号 138-US
掲載日 2011年5月25日
出願国 アメリカ合衆国
出願番号 52540408
公報番号 20100174876
公報番号 8438359
出願日 平成20年2月27日(2008.2.27)
公報発行日 平成22年7月8日(2010.7.8)
公報発行日 平成25年5月7日(2013.5.7)
国際出願番号 JP2008053891
国際公開番号 WO2008105558
国際出願日 平成20年2月27日(2008.2.27)
国際公開日 平成20年9月4日(2008.9.4)
優先権データ
  • 特願2007-050269 (2007.2.28) JP
  • 2008JP053891 (2008.2.27) WO
発明の名称 (英語) Memory management method, information processing device, program creation method, and program
発明の概要(英語) Provided is a method for managing a memory storage region used by a processor.
The processor is connected to the memory that stores data accessed while a task is being executed.
The memory management method including the steps of: dividing the memory area of the memory into blocks having a plurality of different sizes; selecting a block having a size matching a size of the data accessed while the task is being executed; and storing the data accessed while the task is being executed in the selected block.
従来技術、競合技術の概要(英語) BACKGROUND ART
Multi-core processors (chip multi-processors) in which a plurality of processor cores are integrated on one chip have been released one after another from respective microprocessor manufacturers.
In the fields of information home electric appliances and device embedding (such as cellular phones, game machines, car navigation systems, digital television receivers, HDD/DVD recorders/players), as well as in the fields of super computers, servers, desktop computers, and PC servers, there is a trend toward employment of multi-core microprocessors.
In this way, the multi-core processors are used at present in most of information devices ranging from the information home electric appliances to the super computers, and it is expected that the multi-core processor will be integrated into more information devices in the future.
The multi-core processor can utilize not only parallelism on the fine grain instruction level, but also parallelism on the loop level having larger parallelism, parallelism between loops with coarser granularity, and rough grain task parallelism between functions.
In this way, the multi-core processor is advantageous in, by using larger parallelism, increasing processing performance of a processor.
Moreover, the multi-core processor can attain the same performance by using n processor cores, and hence, by decreasing the clock frequency to one n-th and by decreasing a voltage to be applied, the multi-core processor is also advantageous in capability of keeping power consumption (which increases with the square of the voltage) low.
Moreover, in terms of software, parallel programming for the multi-core processor usually requires a large amount of time for tuning, and, thus, development of application software is troublesome.
However, a relatively small number of processors are presently integrated, and hence it is possible to obtain a high performance by means of an automatic parallelizing compiler which automatically parallelizes a sequential program.
In the field of the information home electric appliances, quality and the number of applications determine competitiveness in the market, and hence, when the automatic parallelizing of a program for four-core, eight-core, and sixteen-core multi-processor is possible by a compiler, advantage of multi-core configuration increases.
Moreover, as multi-grain parallelizing, a technology of, by combining all parallelisms such as those on a statement-level, a loop-level, and a more coarse level (such as between loops, between subroutines, and between basic blocks), by means of the earliest executable condition analysis, for extracting a parallelism is disclosed in JP 2001-175619 A.

特許請求の範囲(英語) [claim1]
1. A memory management method of managing a memory area of a memory used by a processor, the processor being connected to the memory that stores data accessed while a task is being executed,
the memory management method comprising the steps of:
dividing the memory area of the memory into a plurality of first size blocks;
creating a plurality of second size blocks by further dividing at least one of the plurality of the first size blocks into a plurality of second size blocks each of which is an integer fraction of the first size blocks so that the second size blocks are assigned to a continuous area and the memory includes both of at least one of the plurality of first size blocks and the plurality of second size blocks;
selecting one of the first size blocks and the second size blocks matching a size of the data accessed while the task is being executed; and
storing the data accessed while the task is being executed in the selected block.
[claim2]
2. The memory management method according to claim 1, wherein the memory area of the memory is divided into the blocks each having a size determined based on information obtained by analysis of a program including the task.
[claim3]
3. The memory management method according to claim 1, further comprising the steps of: storing, by a data transfer module, the data in the selected block after determining to assign the selected block to the data;
reading, by the data transfer module, the data stored in the selected block by a release timing of the selected block; and
storing the data in another memory.
[claim4]
4. The memory management method according to claim 1, further comprising the steps of: assigning, to each of the blocks, a template of n+1 dimensions selected so as to match the array data accessed during the task in a case where the data accessed during the task includes array data of n dimensions; and
assigning, to the each of the blocks, the templates different in value of the added dimension so that a different block is accessed according to the value of the added dimension in a case where a block for storing the data is specified.
[claim5]
5. A memory management method of managing a memory area of a memory by a processor, the processor being connected to the memory that stores data accessed while a program is being executed,
the memory management method comprising the steps of:
dividing the memory area of the memory into a plurality of first size blocks;
creating a plurality of second size blocks by further dividing at least one of the plurality of the first size blocks into a plurality of second size blocks each of which is an integer fraction of the first size so that the second size blocks are assigned to a continuous area and the memory includes both of at least one of the first size blocks and the plurality of second size blocks;
assigning templates having a plurality of shapes and sizes determined based on information obtained by analysis of the program to one of the first size blocks and the second size blocks having matching sizes; and
storing, in at least one of the assigned templates, data having a shape and size matching the plurality of shapes and sizes of the assigned template.
[claim6]
6. The memory management method according to claim 5, wherein the step of assigning the templates includes the steps of: assigning, from a plurality of kinds of the templates which can be assigned to the respective blocks, a template which has dimensions obtained by adding one to dimensions of array data accessed by the program, and which has upper bounds of the respective dimensions equal to or larger than upper bounds of the respective dimensions of the array data accessed by the program; and
assigning a plurality of the templates to a plurality of the blocks so that a different block is accessed according to a value of the added dimension.
[claim7]
7. A computer, comprising: a processor; and
a memory that stores data accessed by the processor, wherein:
a memory area of the memory is divided into blocks having a plurality of sizes determined based on information obtained by analysis of a program executed by the processor;
a shape and size of a template assigned to each of the blocks is determined based on the information obtained by the analysis of the program; and
the processor is configured to:
divide the memory area of the memory into a plurality of first size blocks determined based on the information obtained by the analysis of the program executed by the processor;
create a plurality of second size blocks by further dividing at least one of the plurality of the first size blocks into a plurality of second size blocks each of which is an integer fraction of the first size blocks so that the second size blocks are assigned to a continuous area and the memory includes both of at least one of the first size blocks and the plurality of second size blocks;
assign the template having a shape and size determined based on the information obtained by the analysis of the program to one of the first size blocks and the second size blocks having a matching size; and
store, in the assigned template, data having a shape and size matching the shape and size of the assigned template.
[claim8]
8. The computer according to claim 7 wherein: a template, which has dimensions obtained by adding one to dimensions of array data accessed by the program, and which has upper bounds of the respective dimensions other than the added dimension equal to or larger than upper bounds of the respective dimensions of the array data accessed by the program, is assigned; and
a plurality of the templates are assigned to a plurality of the blocks so that a different block is accessed according to a value of the added dimension.
[claim9]
9. A method of creating a program executable by a processor, comprising the steps of: analyzing information of a source program by a compiler;
dividing the memory area of a memory into a plurality of first size blocks determined based on the information obtained by the analysis of the source program;
creating a plurality of second size blocks by further dividing at least one of the plurality of the first size blocks into a plurality of second size blocks each of which is an integer fraction of the first size so that the second size blocks are assigned to a continuous area so that the memory includes both of at least one of the first size blocks and the plurality of second size blocks;
identifying data necessary for executing respective tasks included in the source program;
determining timing of reading/writing the necessary data from/to the memory according to timing of executing the tasks; and
adding an instruction to assign one of the first size blocks and the second size blocks to the executable program compiled by the determined timing of writing the data.
[claim10]
10. The method of creating an executable program according to claim 9, further comprising the steps of: determining an area to be released and timing of releasing the area based on the information obtained by the analysis of the source program; and
adding an instruction to read the data written in the memory by the determined timing of the executable program to be compiled in order to release the assigned area.
[claim11]
11. The method of creating an executable program according to claim 10, further comprising a step of adding, to the executable program: an instruction to store, by data transfer module, the data in the assigned blocks after assigning blocks; and
an instruction to read, by the data transfer module, by the timing of releasing the assigned blocks, the data stored in the assigned blocks, and store the data in another memory.
[claim12]
12. The method of creating an executable program according to claim 9, wherein the information obtained by the analyzing the source program includes at least one of information on the data accessed by the source program, information on timing in which the data is accessed next, and information on the processor that accesses the data.
[claim13]
13. The method of creating an executable program according to claim 9, wherein: the processor is a multi-processor comprising a plurality of processor cores; and
the method further includes the steps of:
determining when and by which processor the tasks are executed; and
adding an instruction to assign the tasks to the determined processor to the program to be compiled.
[claim14]
14. The method of creating an executable program according to claim 9, further comprising a step of dividing the source program so that the data accessed during the tasks is accommodated in one of the blocks.
[claim15]
15. The method of creating an executable program according to claim 14, wherein: the source program includes nested loops; and
the method further comprises the steps of:
judging whether data accessed during a task created by dividing an outer loop is accommodated in the one of the blocks; and
further dividing an inner loop to change a size of the data in a case where the data accessed during the task created by dividing the outer loop is not accommodated in the one of the blocks.
[claim16]
16. The method of creating an executable program according to claim 9, further including the steps of: assigning, in a case where the data accessed by the source program includes array data in n dimensions, a template in n+1 dimensions selected so as to match the array data accessed by the source program; and
assigning, in a case where an area for storing the data is specified, a plurality of the templates to a plurality of the areas so that the area to be accessed is specified according to a value of the added dimension.
[claim17]
17. A non-transitory machine readable medium, containing at least one sequence of instructions that causes a processor to execute a method comprising the steps of: analyzing a source program;
dividing the memory area of the memory into a plurality of first size blocks determined based on information obtained the analysis of the source program;
creating a plurality of second size blocks by further dividing at least a part of the plurality of the first size blocks into a plurality of second size blocks each of which is an integer fraction of one of the first size blocks so that the second size blocks are assigned to a continuous area and the memory includes both of at least one of the first size blocks and the plurality of second size blocks;
identifying data necessary for executing respective tasks included in an executable program;
determining timing of reading/writing of the necessary data from/to a memory according to timing of executing the tasks; and
adding an instruction to assign one of the first size blocks and the second size blocks by the determined timing of writing the data.
  • 発明者/出願人(英語)
  • KASAHARA HIRONORI
  • KIMURA KEIJI
  • NAKANO HIROFUMI
  • NITO TAKUMI
  • MARUYAMA TAKANORI
  • MIURA TSUYOSHI
  • TAGAWA TOMOHIRO
  • WASEDA UNIVERSITY
国際特許分類(IPC)
米国特許分類/主・副
  • 711/170
  • 711/129
  • 711/153
  • 711/171
  • 711/172
  • 711/173
技術導入、技術提携、実用化開発(受託研究・共同研究等)のご相談を承っております。お気軽にご連絡ください。

PAGE TOP

close
close
close
close
close
close