TOP > 外国特許検索 > Data processing device for implementing instruction reuse, and digital data storage medium for storing a data processing program for implementing instruction reuse

Data processing device for implementing instruction reuse, and digital data storage medium for storing a data processing program for implementing instruction reuse

外国特許コード F110005371
整理番号 K01902WO
掲載日 2011年9月5日
出願国 アメリカ合衆国
出願番号 59369505
公報番号 20080250232
公報番号 8055885
出願日 平成17年3月25日(2005.3.25)
公報発行日 平成20年10月9日(2008.10.9)
公報発行日 平成23年11月8日(2011.11.8)
国際出願番号 JP2005005591
国際公開番号 WO2005093562
国際出願日 平成17年3月25日(2005.3.25)
国際公開日 平成17年10月6日(2005.10.6)
優先権データ
  • 特願2004-097197 (2004.3.29) JP
  • 特願2004-266056 (2004.9.13) JP
  • 特願2004-324348 (2004.11.8) JP
  • 特願2004-347124 (2004.11.30) JP
  • 2005WO-JP05591 (2005.3.25) WO
発明の名称 (英語) Data processing device for implementing instruction reuse, and digital data storage medium for storing a data processing program for implementing instruction reuse
発明の概要(英語) (US8055885)
A method and apparatus is provided for significantly speeding-up program execution in a data processing device.
The data processing device is provided with a specialized instruction region storage section comprising content addressable memory (CAM) and random access memory (RAM) that operatively functions as an instruction sequence reuse table which is capable of registering/storing sequences of program instructions and corresponding instruction sequence output data as input/output (I/O) groups for potential future use in place of re-executing identical portions of program code.
The data processing device includes at least one instruction stream processor which includes a computing unit for executing instructions and a dependency relationship analysis unit or “reuse window” unit (RW) that analyzes instruction sequence patterns from regions of instructions stored in a main memory to determine if the patterns can be divided up into smaller partitions that have no interdependencies and hence are potential candidates for reuse.
特許請求の範囲(英語) [claim1]
1. A data processing apparatus for speeding-up execution of program instructions received from a main memory, comprising: a main memory which stores program instructions and data;
a first instruction stream processor comprising a computing unit configured to perform computations based on one or more instructions obtained from an instruction region in main memory containing program instructions;
a register by which the first instruction stream processor writes and reads instruction data to/from the main memory, and
an input/output group generator, operatively functioning as an instruction sequence reuse window, that generates input/output (I/O) group data based on execution of a sequence of program instructions from the instruction region, said I/O group data having an input pattern comprising one or more instruction sequence input elements and an associated output pattern comprising one or more instruction sequence output elements; and
said data processing apparatus further comprising an instruction region storage section comprising content addressable memory (CAM) and random access memory (RAM) memory portions, operatively functioning as data reuse table, for storing I/O group data used for reusing certain sequences of instructions, wherein said instruction region storage section further includes an I/O group storage portion used to store the I/O group data, and wherein, at a time of executing one or more instructions read out from the instruction region in main memory, and upon identifying a matching pattern of instruction sequence input data found the instruction region with an input pattern of I/O group data stored in the I/O group storage portion, the first stream processor performs a reuse operation that outputs the associated output pattern to the register and/or the main memory, and wherein
the input/output group generator also generates dependency relations information and includes a dependency relations storage memory section for storing dependency relations information, the dependency relations storage memory section comprising a two-dimensional (2D) matrix-arranged memory in which instruction sequence input elements are associated to particular columns of the memory and corresponding instruction sequence output elements are associated to particular rows of the memory, and each storage element within the 2D matrix-arranged memory contains dependency relations information indicative of whether a particular instruction sequence output element corresponding to a particular row of the memory is derived from or has some dependency relationship to a particular instruction sequence input element corresponding to a particular column of the memory, and wherein
the input/output group generator further includes an I/O group data setter which, based on information stored in the dependency relations storage memory, sets I/O group data that is made up of an output pattern that includes at least one of said instruction sequence output elements and an input pattern that includes at least one of said instruction sequence input elements.
[claim2]
2. The data processing device as defined in claim 1, wherein if a first group of instruction sequence input elements, from which a first instruction sequence output element is derived, is included entirely within a second group of instruction sequence input elements, from which a second instruction sequence output element different from the first instruction sequence output element is derived, the I/O group data setter: (i) sets the second group of instruction sequence input elements as the input pattern and (ii) sets the first group of instruction sequence input elements and the second group of instruction sequence input elements as the output pattern.
[claim3]
3. The data processing device as defined in claim 1, wherein if there is no shared instruction sequence input element between a first group of instruction sequence input elements, from which a first instruction sequence output element is derived, and a second group of instruction sequence input elements, from which a second instruction sequence output element different from the first instruction sequence output element is derived, the I/O group data setter: (i) sets a first I/O group data in which the first group of instruction sequence input elements is the input pattern and the first instruction sequence output element is the output pattern and (ii) sets a second I/O group data in which the second group of instruction sequence input elements is the input pattern and the second instruction sequence output element is the output pattern.
[claim4]
4. The data processing device as defined in claim 1, wherein after a readout operation from the register and/or from an instruction region in the main memory is performed and upon said first instruction stream processor performing execution of one or more instructions obtained from the register or the instruction region, the input/output group generator further performs operations of: (1) when an address of the register and/or the main memory from which the readout operation was performed is registered in the dependency relations storage memory section as an instruction sequence output element, creating a temporary provisional dependency relationship information storage matrix comprising rows and columns of memory elements within the dependency relations storage memory section, wherein a particular row is associated to that particular instruction sequence output element corresponding to the registered address;
(2) when an address of the register and/or the main memory from which the readout operation was performed is registered in the dependency relations storage memory section as an instruction sequence input element rather than an instruction sequence output element, creating a temporary provisional dependency relationship information storage matrix comprising rows and columns of memory elements within the dependency relations storage memory section, wherein a particular column of memory elements is associated to that particular instruction sequence input element corresponding to the registered address, and wherein a particular memory element in a column associated with the instruction sequence input element is set to a logical "1", and remaining memory elements in a same column are set to a logical "0"; and
(3) when an address of the register or the main memory from which the readout operation was performed is registered in the dependency relations storage section as neither an instruction sequence output element nor an instruction sequence input element, (i) registering the address and its value in the dependency relations storage section as instruction sequence input elements, and (ii) creating a temporary provisional dependency relationship information storage matrix comprising rows and columns of memory elements within the dependency relations storage memory section, wherein a particular column of memory elements is associated to that particular instruction sequence registered as input elements and a particular memory element in said column is set to a logical "1", and remaining memory elements in that same column are set to a logical "0"; and
under a condition where a writing operation is performed to the register and/or the main memory, the I/O group data generator performs further operations of:
(4) when an address of the register and/or the main memory to which the writing operation is performed is registered as an instruction sequence output element, (iii) updating an instruction sequence output value corresponding to the registered instruction sequence output element to a value written by the writing operation, (iv) replacing a value stored in a row element of the temporary provisional dependency relationship information storage matrix within the dependency relations storage section, wherein said row element being replaced corresponds to a row associated to the registered instruction sequence output element, with a result of a logical OR-ing of all provisional matrices temporarily stored at that time, and then (v) initializing the temporarily-stored provisional matrices; and
(5) when an address of the register and/or the main memory to which the writing operation is performed is not registered as an instruction sequence output element, (vi) registering the address and its value as an instruction sequence output element in the dependency relations storage memory section, (vii) replacing a value stored in a row element of the temporary provisional dependency relationship information storage matrix within the dependency relations storage section, wherein said row element being replaced corresponds to a row associated to that instruction sequence output element, with a result of a logical OR-ing of all provisional matrices temporarily stored at that time, and then (viii) initializing the temporarily-stored provisional matrices.
[claim5]
5. The data processing device as defined in claim 1, wherein, the I/O group data pattern setter includes a logical operation computation section which performs a logical "AND" operation of the row elements in the 2D matrix-arranged memory, and
(i) extracts a group of row elements for which a logical AND operation of an inversion of a first row element and a second row element are each a logical "0", and (ii) among the extracted group of the row elements, excludes, as a candidate for an input/output group, row elements other than a row element that includes a largest number of the input elements.
[claim6]
6. The data processing device as defined in claim 1, wherein, the I/O group data pattern setter includes a logical operation computation section which performs a logical "AND" operation of the row elements in the 2D matrix-arranged memory, and
sets, as an input/output group, a row element whose logical "AND" operation with any other row elements are all logical "0".
[claim7]
7. The data processing device as defined in claim 1, further comprising a second instruction stream processor having a second computing unit configured to perform computations on instructions from an instruction region in main memory, wherein with respect to instructions in the instruction region processed by the first computing unit, the second computing unit subjects instructions from the instruction region to a computation based on a predicted input value, and registers a result of the computation in the instruction region storage section.
[claim8]
8. The data processing device as defined in claim 1, wherein, the I/O group data pattern setter further comprises:
an output-side group storage section which stores information of an input/output group to which each of the output elements belongs;
an input-side group storage section which stores information of an input/output group to which each of the input elements belongs;
a temporal storage section which stores an indication of a changed dependency relation between an output element and an input element whenever there is a change in information stored in the dependency relations storage section when I/O group data is generated; and
a group temporal storage section which stores information of changed I/O group data when there is a change in information stored in the dependency relations storage memory section when the input/output group is generated.
[claim9]
9. The data processing device as defined in claim 8, wherein the I/O group data pattern setter further includes a group management section that stores information of the I/O group data which has previously been allocated to an output element and/or an input element when the input/output group is generated.
[claim10]
10. The data processing device as defined in claim 9, wherein the temporal storage section stores results of a logical OR-ing of memory elements of a plurality of rows in the dependency relations storage section, and
the group temporal storage section stores: (i) the result of a logical OR-ing of memory elements of a plurality of rows in the output side group storage section and/or (ii) the result of a logical OR-ing of memory elements corresponding to a plurality of input elements in the input side group storage section.
[claim11]
11. The data processing device as defined in claim 8, wherein the I/O group data pattern setter further includes a conditional branch storage section that stores information regarding an input element on which the conditional branch instruction depends whenever a conditional branch instruction is detected when the I/O group data is generated.
[claim12]
12. The data processing device as defined in claim 10, wherein, under a condition where a readout operation from the register and/or the main memory is carried out while the first stream processor performs a calculation of the input region, the input/output group generator further performs operations of:
(1) when an address of the register and/or the main memory from which the readout operation was performed has been registered as an output element in the dependency relations storage memory section, temporarily storing, in the temporal storage section, a logical OR of (i) a row element of the dependency relations storage memory section, wherein said row element corresponds to the output element, and (ii) elements in the temporal storage section, and storing, in the group temporal storage section, a logical.
OR of (iii) a row element of the output side group storage section, wherein said row element corresponds to the output element and (iv) elements in the group temporal storage section;
(2) when an address of the register and/or the main memory from which the readout operation was performed is registered as an input element rather than an output element in the dependency relations storage memory section, storing in the temporal storage section information in which a memory element corresponding to a column of the dependency relations storage section, wherein said column corresponds to the input element and is set to a logical "1" and remaining memory elements are set at a logical "0", and storing in the group temporal storage section a logical "OR" of: (v) elements, from the input-side group storage section that correspond to the input element and (vi) the elements in the group temporal storage section; and
(3) when an address of the register and/or the main memory from which the readout operation was performed is not registered in the dependency relations storage memory section as either an output element or an input element, registering as input elements, the address and its value in the dependency relations storage section, and temporarily storing a provisional matrix in which a memory element corresponding to a column, of the dependency relations storage section, which corresponds to the input element is set at a logical "1" while remaining memory elements are set to a logical "0", and
under a condition where writing is carried out to the register and/or the main memory, the input/output group generator performs further operations of:
(4) when an address of the register and/or the main memory to which the writing performed is registered as an output element, updating an output value corresponding to the registered output element to the written value, replacing a row element of the dependency relations storage memory section wherein said row element corresponds to the registered output element, with the information temporarily stored in the temporal storage section at the time, and (viii) updating the information in the output side group storage section, which information corresponds to the output element, and (ix) updating the information in the input side group storage section, which information corresponds to the input elements on which the output element depends, based on the information stored in the group temporal storage section; and
(5) when an address of the register and/or the main memory to which the writing is carried out is not registered as an output element, registering the address and its value as output element in the dependency relations storage memory section, and replacing a row element of the dependency relations storage section, wherein said row element corresponds to the output element, with the information temporarily stored in the temporal storage section at that time, and (x) updating the information in the output-side group storage section, wherein said information corresponds to the output element, and (xi) updating the information in the input side group storage section, wherein said information corresponds to the input elements on which the output element depends, based on the information stored in the group temporal storage section.
[claim13]
13. The data processing device as defined in claim 1, wherein the instruction region storage section includes an instruction sequence input pattern storage section which stores instruction sequence input patterns as a tree structure in which items which should be subjected to equal comparison are regarded as nodes.
[claim14]
14. The data processing device as defined in claim 13, wherein the input pattern storage section is configured to organize and store the tree structure in such a manner that a value of an item in the input pattern, which item is subjected to equal comparison, is stored in association with an item which is to be next subjected to a comparison.
[claim15]
15. The data processing device as defined in claim 14, wherein the input pattern storage section further includes associative search performing circuitry and an additional information storage section, wherein the associative search performing circuitry utilizes one or more search target lines that include a value storage portion in which a value of an item to be subjected to equal comparison is placed, and a key storage portion in which a key for identifying each item is placed; and
the additional information storage section includes a search item designation area in which an item to be next subjected to an associative search is stored in accordance with a search target line.
  • 発明者/出願人(英語)
  • NAKASHIMA YASUHIKO
  • JAPAN SCIENCE AND TECHNOLOGY AGENCY
国際特許分類(IPC)
米国特許分類/主・副
  • G06F009/38B4
  • G06F009/38D2
参考情報 (研究プロジェクト等) PRESTO Information Infrastructure and Applications AREA
ライセンスをご希望の方、特許の内容に興味を持たれた方は、問合せボタンを押してください。

PAGE TOP

close
close
close
close
close
close