Data Processing Device, Data Processing Program, and Recording Medium Recording Data Processing Program

• US 20080250232A1
• Filed: 03/25/2005
• Published: 10/09/2008
• Est. Priority Date: 03/29/2004
• Status: Active Grant

• Current Assignee: Japan Science & Technology Trading Co. Limited
• Original Assignee: Japan Science & Technology Trading Co. Limited
• Inventors: Nakashima, Yasuhiko
• Granted Patent: US 8,055,885 B2
• Time in Patent Office: Days
• US Class Current: 712/225
• CPC Class Codes: G06F 9/3808 for instruction reuse, e.g. trace cache, branch target cache
• CPC Class Codes: G06F 9/383 Operand prefetching cache prefetching G06F12/0862

Abstract

A dependence relationship storage unit M indicates from which input address and input value each of the output addresses and output values derives. An inter-line AND comparator MR performs AND between each of the line components stored in the dependence relationship storage unit M and sets an I/O group including an output pattern containing at least one output address and output value and an input pattern containing at least one input address and input value. Thus, it is possible to provide a data processing device capable of registering an I/O group appropriate for reuse in instruction section storage means.

Claims

1. A data processing device which reads out an instruction region from main memory means and writes a result of a computation into the main memory means,

the data processing device comprising:

first computing means for performing a computation based on the instruction region read out from the main memory means;

a register by which the first computing means reads out or writes data to/from the main memory means;

input/output generating means for generating an input/output group which is made up of an input pattern and an output pattern at the time of execution of the instruction region by the first computing means; and

instruction region storage means for storing the input/output group generated by the input/output generating means,

at the time of execution of the instruction region, if the input pattern of the instruction region is matched with an input pattern stored in the instruction region storage means, the first computing means performing reuse so that the output pattern, which is stored in the instruction region storage means in association with the input pattern, is outputted to the register and/or the main memory means, and

the input/output generating means including;

a dependency relations storage section which indicates from which input element in the input pattern each output element in the output pattern derives; and

input/output group setting means for setting, based on information stored in the dependency relations storage section, an input/output group which is made up of an output pattern including at least one said output element and an input pattern including at least one said input element.

2. The data processing device as defined in claim 1, wherein,

in a case where a first group of input elements from which a first output element derives is all included in a second group of input elements from which a second output element different from the first output element derives, the input/output group setting means sets (i) the second group as the input pattern and (ii) the first group and the second group as the output pattern.

3. The data processing device as defined in claim 1, wherein,

in a case where there is no shared input element between a first group of input elements from which a first output element derives and a second group of input elements from which a second output element different from the first output element derives, the input/output pattern group setting means sets (i) a first input/output group in which the first group of the input elements is the input pattern and the first output element is the output pattern and (ii) a second input/output group in which the second group of the input elements is the input pattern and the second output element is the output pattern.

4. The data processing device as defined in claim 1, wherein,

the dependency relations storage section is made up of a 2D-arranged memory in which the output elements are row elements and the input elements are column elements, and each of memory elements of the 2D-arranged memory has information regarding whether or not an output element corresponding to a row element of the memory element is derived from an input element corresponding to a column element of the memory element.

5. The data processing device as defined in claim 4, wherein,

in a case where readout from the register and/or the main memory means is carried out when the first computing means performs the calculation of the instruction region, the input/output generating means performs:

(1) when an address of the register and/or the main memory means from which the readout is carried out has been registered, as an output element, in the dependency relations storage section, a process to temporarily store a provisional matrix which is made up of a row element, of the dependency relations storage section, which element corresponds to the output element;

(2) when an address of the register and/or the main memory means from which the readout is carried out is registered, as an input element rather than an output element, in the dependency relations storage section, a process to temporarily store a provisional matrix in which a memory element corresponding to a column, of the dependency relations storage section, which column corresponds to the input element is set at 1, and remaining memory elements are set at 0; and

(3) when an address of the register or the main memory means from which the readout is carried out is registered, in the dependency relations storage section, as neither an output element nor an input element, a process to (i) register, as input elements, the address and its value in the dependency relations storage section, (ii) temporarily store 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 1, and remaining memory elements are set at 0,

in a case where writing is carried out to the register and/or the main memory means, the input/output generating means performs;

(4) when an address of the register and/or the main memory means to which the writing is carried out is registered as an output element, a process to (iii) update an output value corresponding to the registered output element to the written value, (iv) replace a row element, of the dependency relations storage section, which element corresponds to the registered output element, with a logical OR of all provisional matrices temporarily stored at the time, and (v) then initialize the temporarily-stored provisional matrices; and

(5) when an address of the register and/or the main memory means to which the writing is carried out is not registered as an output element, a process to (vi) register the address and its value, as output elements, in the dependency relations storage section, (vii) replace a row element, of the dependency relations storage section, which corresponds to the output element, with a logical OR of all provisional matrices temporarily stored at the time, and (viii) then initialize the temporarily-stored provisional matrices.

6. The data processing device as defined in claim 4, wherein,

the input/output group setting means includes a rows AND comparison section which performs a logic operation AND of the row elements in the 2D-arranged memory, and

in the dependency relations storage section, the input/output group setting means (i) extracts a group of row elements in which a logical AND of an inversion of a first row element and a second row element is all 0, and (ii) among the extracted group of the row elements, excludes, from a candidate as the input/output group, row elements other than a row element which includes the largest number of the input elements.

7. The data processing device as defined in claim 4, wherein,

the input/output group setting means includes a rows AND comparison section which performs a logic operation AND of the row elements in the 2D-arranged memory, and

in the dependency relations storage section, the input/output group setting means sets, as the input/output group, a row element whose logical AND with any other row elements is all 0.

8. The data processing device as defined in any claim 1, further comprising at least one second computing means,

in regard of the instruction region processed by the first computing means, the second computing means subjecting the instruction region to a computation based on a predicted input value which is assumed to be inputted hereafter, and registering a result of the computation in the instruction region storage means.

9. The data processing device as defined in claim 1, wherein,

the input/output group setting means includes:

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 a changed dependency relation between an output element and an input element, when there is a change in the dependency relations storage section while the input/output group is generated; and

a group temporal storage section which stores information of a changed input/output group when there is a change in the dependency relations storage section while the input/output group is generated.

10. The data processing device as defined in claim 9, wherein,

the input/output group setting means further includes a group management section that stores information of the input/output group which has already been allocated to the output element and/or the input element, while the input/output group is generated.

11. The data processing device as defined in claim 9, wherein,

the dependency relations storage section is made up of a 2D-arranged memory in which the output elements are row elements and the input elements are column elements, and each of memory elements of the 2D-arranged memory has information regarding whether or not an output element corresponding to a row element of the memory element is derived from an input element corresponding to a column element of the memory element.

12. The data processing device as defined in claim 11, wherein,

the temporal storage section stores a logical OR of memory elements of a plurality of rows in the dependency relations storage section, and

the group temporal storage section stores (i) a logical OR of memory elements of a plurality of rows in the output side group storage section and/or (ii) a logical OR of memory elements corresponding to a plurality of input elements in the input side group storage section.

13. The data processing device as defined in claim 9, wherein,

the input/output group setting means further includes a conditional branch storage section which stores, when a conditional branch instruction is detected while the input/output group is generated, information regarding an input element on which the conditional branch instruction depends.

14. The data processing device as defined in claim 12, wherein,

in a case where readout from the register and/or the main memory means is carried out while the first computing means performs a calculation of the input region, the input/output generating means performs:

(1) when an address of the register and/or the main memory means from which the readout is carried out has been registered, as an output element, in the dependency relations storage section, a process to temporarily store, in the temporal storage section, a logical OR of (i) a row element, of the dependency relations storage section, which corresponds to the output element and (ii) the elements in the temporal storage section, and store, in the group temporal storage section, a logical OR of (iii) a row element, of the output side group storage section, which corresponds to the output element and (iv) the elements in the group temporal storage section;

(2) when an address of the register and/or the main memory means from which the readout is carried out is registered, as an input element rather than an output element, in the dependency relations storage section, a process to store, in the temporal storage section, information in which a memory element corresponding to a column, of the dependency relations storage section, which corresponds to the input element is set at 1 and remaining memory elements are set at 0, and store, in the group temporal storage section, a logical OR of (v) elements, in the input side group storage section, which 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 means from which the readout is carried out is not registered in the dependency relations storage section as either an output element or an input element, a process to register, as input elements, the address and its value in the dependency relations storage section, and temporarily store 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 1 while remaining memory elements are set at 0,

in a case where writing is carried out to the register and/or the main memory means, the input/output generating means performs;

(4) when an address of the register and/or the main memory means to which the writing is carried out is registered as an output element, a process to update an output value corresponding to the registered output element to the written value, replace a row element, of the dependency relations storage section, which corresponds to the registered output element, with the information temporarily stored in the temporal storage section at the time, and update (viii) the information in the output side group storage section, which information corresponds to the output element, and (ix) 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 means to which the writing is carried out is not registered as an output element, a process to register the address and its value, as output elements, in the dependency relations storage section, replace a row element, of the dependency relations storage section, which corresponds to the output element, with the information temporarily stored in the temporal storage section at the time, and update (x) the information, in the output side group storage section, which information corresponds to the output element, and (xi) 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.

15. The data processing device as defined in claim 1, wherein,

the instruction region storage means includes input pattern storage means which stores the input patterns as a tree structure in which items to be subjected to equal comparison are regarded as nodes.

16. The data processing device as defined in claim 15, wherein,

the input pattern storage means realizes 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 to be subjected to comparison next.

17. The data processing device as defined in claim 16, wherein,

the input pattern storage means includes associative search means and additional storage means,

the associative search means includes one or more search target line which includes:

a value storage area where a value of an item to be subjected to equal comparison is stored; and

a key storage area where a key for identifying each item is stored, and

the additional storage means has a search item designation area in which an item to be subjected to associative search next is stored in accordance with a corresponding line corresponding to said one or more search target line.

30. A data processing program, causing a computer to execute processes carried out by the means of the data processing device defined in claim 1.

31. A computer-readable storage medium, storing the data processing program defined in claim 30.

18. A data processing device which reads out an instruction region from main memory means and writes a result of a computation into the main memory means,

the data processing device comprising:

first computing means for performing a computation based on the instruction region read out from the main memory means;

a register by which the first computing means reads out or writes data to/from the main memory means; and

input/output pattern storage means for storing an input pattern and an output pattern which are a result of execution of a plurality of instruction regions,

in a case where the first computing means executes an instruction region and an input pattern of the instruction region is matched with an input pattern stored in the input/output storage means, a reuse process is performed so that an output pattern, which is stored in the input/output storage means in association with the input pattern, is outputted to the register and/or the main memory means,

the data processing device further comprising;

registration processing means for (i) distinguishing, among the input elements in the input pattern, an input element to be subjected to prediction from an input element not requiring prediction, at the time of storing, in the input/output storage means, a result of execution of the instruction region by the first computing means, and (ii) registering, in the input/output storage means, information regarding the distinction;

prediction processing means for predicting a variation of a value of the input element to be subjected to prediction among the input elements stored in the input/output storage means, based on the information regarding the distinction; and

second computing means for subjecting the instruction region to precomputation, based on the input element predicted by the prediction processing means,

a result of the precomputation of the instruction region by the second computing means being stored in the input/output storage means.

19. The data processing device as defined in claim 18, wherein,

in a case where (i) an address of the register used for input is used as a stack pointer or a frame pointer or (ii) a writing instruction to the address is a constant setting instruction, the registration processing means sets a constant flag in the address, as the information for the distinction, while in a case where neither (i) or (ii) holds true, the registration processing means resets a constant flag of the address.

20. The data processing device as defined in claim 18, wherein,

in a case where an input element is newly stored in the input/output storage means, the registration processing means resets, as the information for the distinction, a change flag in an address of the input element, while, in a case where, after the input element is stored in the input/output storage means, a storing instruction is executed with respect to the address, the registration processing means sets a change flag in the address.

21. The data processing device as defined in claim 19, wherein,

in a case where an input element is newly stored in the input/output storage means, the registration processing means resets, as the information for the distinction, a history flag in an address of the input element, while, in a case where, at the time of execution of a load instruction with respect to the address, the constant flag is set in a register address from which the address is generated, the registration processing means sets a history flag in the address.

22. The data processing device as defined in claim 21, wherein,

in a case where an input element is newly stored in the input/output storage means, the registration processing means resets, as the information for the distinction, a flag of an address of the input element, while, after the input element is stored in the input/output storage means, a storing instruction is executed with respect to the address, the registration processing means sets a change flag in the address, and

the prediction processing means performs prediction of a variation of an input element, as to an address in which the change flag and the history flag are set, among addresses of the input elements stored in the input/output storage means.

23. The data processing device as defined in claim 18, wherein,

the prediction processing means performs prediction of a variation of an input element, only as to an input element in which a variation of a value of the input element in the history is not 0, among the input elements stored in the input/output storage means.

24. The data processing device as defined in claim 18, wherein,

when the result of execution of the instruction region by the first computing means is stored in the input/output storage means, the registration processing means (i) distinguishes, among the input elements in the input pattern, an input element to be subjected to prediction from an input element not requiring prediction, (ii) registers information regarding the distinction in the input/output storage means, (iii) counts how many times storing is carried out at the time of execution of the instruction region, as to the output elements of the output pattern stored in the input/output storage means, and (iv) store the counted value in the input/output storage means, and

the second computing means (i) subjects the instruction region to precomputation, based on the input element having been predicted by the prediction processing means, and (ii) performs the precomputation of the instruction region by waiting for a time corresponding to the number of times of storing performed with respect to the input element based on the counted value, and then performing readout from the main memory.

25. The data processing device as defined in claim 24, wherein,

the input/output storage means includes an input/output storage area which temporarily stores an input pattern and an output pattern which are the result of execution of the instruction region by the first computing means, and

the input/output storage area includes a store counter which counts how many times the storing is carried out with respect to each of the output elements.

26. The data processing device as defined in claim 25, wherein,

the input/output storage means includes a history storage area which stores a history of a past result of execution of each instruction region subjected to computation by the first computing means, and

the registration processing means (i) stores, in the history storage area, the result of execution which is stored in the input/output storage area, and (ii) with respect to an input element having an address identical with an address of an output element which is stored, in the history storage area, as a result of execution of the last time, registers a store counter of a corresponding directly-preceding output element, as a store counter of the input element.

27. The data processing device as defined in claim 26, wherein,

the input/output storage means includes a predicted value storage area which stores an input element predicted by the prediction processing means, and

the prediction processing means subjects, to prediction, an input element whose value consistently varies between execution histories, among the input elements stored in the history storage area, and stores a result of the prediction in the predicted value storage area.

28. The data processing device as defined in claim 26, wherein,

the input/output storage means includes a waiting-required address storage area which stores an input element that should be read out from the main memory after waiting for a time corresponding to the number of times of the storing, and

with respect to an input element whose address in an execution histories does not change and whose variation of a value between the execution histories is inconsistent, the prediction processing means stores, in the waiting-required address storage area, the store counter and a waiting counter as a value based on a predicted distance.

29. The data processing device as defined in claim 26, wherein,

the input/output storage means includes a waiting-required address storage area which stores an input element that should be read out from the main memory after waiting for a time corresponding to the number of times of the storing, and

with respect to an input element whose address changes between execution histories and values of changed addresses change on account of the storing, among the input elements stored in the history storage area, the prediction processing means stores, in the waiting-required address storage area, a waiting counter as a value based on the store counter.