JP2023133850A - Arithmetic processing device and processing method - Google Patents

Abstract

To reduce a circuit scale of a conflict determination unit that determines a conflict between an address included in a memory access instruction and an address held in a queue that holds the memory access instruction.SOLUTION: An arithmetic processor includes: a queue configured to hold a memory access instruction including one or more addresses; a contracted address generation unit configured to generate a contracted address by contracting bits of multiple addresses in a case where the memory access instruction includes the multiple addresses; a conflict determination unit configured to determine a conflict between the contracted address and the address held in the queue; and an access control unit configured to control processes of the memory access instruction held in the queue, based on a determination result of the conflict detection unit.SELECTED DRAWING: Figure 1

Description

The present invention relates to an arithmetic processing device and an arithmetic processing method.

In an arithmetic processing device having a SIMD (Single Instruction Multiple Data) arithmetic function, processing performance is improved by executing arithmetic operations on a plurality of data in parallel. For example, multiple pieces of data used in multiple data operations are read from memory in parallel using vector load instructions. That is, an arithmetic processing device having a SIMD arithmetic function has an architecture that makes data transfer more efficient.

For example, in this type of arithmetic processing device, there is a known method for managing address collisions by executing a check instruction to determine whether a memory address in an address hazard state exists when a vector operation is executed (e.g. , see Patent Document 1). In addition, when executing a vector gather instruction, there is a known method of calculating the number of duplicate addresses in one line, integrating the requests, and notifying the scalar operation unit of the integrated value of the number of duplicate addresses between multiple lines. (For example, see Patent Document 2). Furthermore, there is a known method of holding the subsequent memory access instruction when an overlap between the address range of a vector scatter instruction with area specification and the address of a subsequent memory access instruction is known (for example, Patent Document 3 reference).

Special table 2019-517060 publication JP2020-52862A Japanese Patent Application Publication No. 2002-24205

By the way, an arithmetic processing device that executes instructions out-of-order has a mechanism for committing instructions in-order. When committing memory access instructions in-order, a load/store queue may be provided to hold addresses included in the memory access instructions. Then, a collision between the address held in the load store queue and an address included in a subsequent or preceding memory access instruction is determined, and based on the determination result, whether or not to commit the memory access instruction held in the load store queue is determined. is determined.

For example, when a memory access instruction is executed, its address is stored in a load store queue and compared with the address of another memory access instruction that has already been stored. In the case of a vector memory access instruction that includes multiple addresses, such as a gather instruction or a scatter instruction, each of the multiple addresses is stored in a load store queue and compared.

For this reason, an arithmetic processing device capable of executing vector memory access instructions may be provided with a plurality of comparators that compare a plurality of addresses in parallel. When a plurality of comparators are provided, the circuit scale of the arithmetic processing device increases.

In one aspect, the present invention aims to reduce the circuit scale of a collision determination unit that determines a collision between an address included in a memory access instruction and an address held in a queue that holds memory access instructions.

According to one aspect, an arithmetic processing unit includes a queue holding a memory access instruction including at least one address, and when the memory access instruction includes a plurality of addresses, compressing bits of the plurality of addresses. a condensed address generation unit that generates a condensed address; a collision determination unit that determines a collision between the condensed address and an address held in the queue; and an access control unit that controls processing of the held memory access command.

It is possible to reduce the circuit scale of a collision determination unit that determines a collision between an address included in a memory access command and an address held in a queue that holds memory access commands.

FIG. 2 is a block diagram illustrating an example of a main part of an arithmetic processing device in an embodiment. FIG. 2 is an explanatory diagram showing an example of a change in the state of the payload in FIG. 1; FIG. 2 is an explanatory diagram showing an example of a method for generating a contracted address by the contracted address generation unit of FIG. 1; FIG. 4 is an explanatory diagram showing an example of an address range indicated by the contracted address in FIG. 3; FIG. 2 is an explanatory diagram showing an example of an address determination operation by each coincidence determination circuit of the coincidence determination section in FIG. 1; FIG. 3 is a block diagram illustrating an example of another arithmetic processing device. It is a block diagram showing an example of an arithmetic processing device in another embodiment. FIG. 8 is an explanatory diagram illustrating an example of the payload of FIG. 7 and an example of a method for generating an abbreviated address by an abbreviated address generation unit. 8 is a circuit diagram showing an example of the match determination circuit of FIG. 7. FIG. FIG. 3 is a block diagram showing an example of a main part of an arithmetic processing device in another embodiment. FIG. 3 is a block diagram showing an example of a main part of an arithmetic processing device in another embodiment. FIG. 3 is a block diagram showing an example of a main part of an arithmetic processing device in another embodiment. FIG. 13 is an explanatory diagram showing an example of the operation of the match determination circuit of FIG. 12;

Embodiments will be described below with reference to the drawings.

FIG. 1 shows an example of an arithmetic processing device in one embodiment. The arithmetic processing device 1 shown in FIG. 1 is, for example, a processor such as a CPU (Central Processing Unit) capable of executing SIMD arithmetic instructions.

The arithmetic processing device 1 includes a load/store queue 2, an access control section 8, and a data cache 9. The load store queue 2 includes a contracted address generator 3, a payload 4, and a match determiner 5. Note that FIG. 1 shows some of the elements used for memory access. In reality, the arithmetic processing device 1 may include an instruction cache (not shown), an instruction decoder, a scheduler such as a reservation station, a register file, an arithmetic unit including an arithmetic unit capable of executing SIMD arithmetic instructions, and the like.

An arithmetic processing device 1 having a scheduler such as a reservation station may execute instructions in an order different from the order of instructions decoded by an instruction decoder (that is, the order of instructions written in a program). Therefore, in order to ensure that load instructions and store instructions are committed in in-order order, a load store queue 2 is provided that detects address collisions. Address collisions are explained in FIG. 2. Load and store instructions include a single address or multiple addresses.

When a memory access instruction MA such as a load instruction or a store instruction includes a plurality of addresses AD (AD0-AD7), the abbreviated address generation unit 3 abridges the plurality of addresses AD to generate an abbreviated address CAD. . For example, the reduced address generation unit 3 reduces a plurality of addresses included in a vector load instruction or a vector store instruction based on a vector load instruction or a vector store instruction issued from a scheduler.

For example, vector load instructions and vector store instructions include continuous address vector load instructions and continuous address vector store instructions in which addresses are consecutive in ascending or descending order, and stride vector load instructions and stride vector store instructions in which addresses are equally spaced. Further, as a vector load instruction, there is a gather instruction in which a plurality of arbitrary addresses are specified. As a vector store instruction, there is a scatter instruction in which multiple arbitrary addresses are specified.

Although FIG. 1 shows an example in which eight addresses AD0 to AD7 are contracted, the contracted address generation unit 3 can contract two or more addresses AD, and can contract a single address AD. It is also possible to output as approximately address CAD. For example, when the contracted address generation unit 3 receives a single address AD in response to the memory access command MA, it may output the single address AD as the contracted address CAD. In this case, the route for transferring the address AD to the payload 4 may be omitted.

Payload 4 includes multiple entries ENT holding memory access instructions MA. Payload 4 is an example of a queue. For example, the entry ENT holds an execution flag, an instruction code indicating a load instruction or a store instruction, an address, and data as a memory access instruction MA. The data held in the entry ENT is store data included in the memory access instruction MA or load data read from the data cache 9. In FIG. 1, only the address area of each entry ENT is shown for simplicity. An example of payload 4 is shown in FIG.

The payload 4 outputs the address (AD or CAD) held in each entry ENT to the match determination unit 5. The payload 4 also outputs the memory access instruction MA held in the entry ENT instructed by the access control unit 8 to the data cache 9. The payload 4 holds a memory access instruction MA transferred from a scheduler and a register file (not shown) and an abbreviated address CAD output from the abbreviated address generator 3.

By storing the abbreviated address CAD generated by the abbreviated address generation unit 3 in the payload 4, the memory access command that can be stored in the payload 4 is more The number of MAs can be increased. Thereby, the number of memory access instructions MA whose processing can be controlled by the access control unit 8 can be increased, and the processing performance of the arithmetic processing device 1 can be improved. Further, when the processing performance of the arithmetic processing device 1 is not changed, the number of entries ENT of the payload 4 can be reduced, and the circuit scale of the arithmetic processing device 1 can be reduced.

The match determining unit 5 includes a plurality of match determining circuits 6 each corresponding to the entry ENT of the payload 4. Each match determination circuit 6 compares the address (AD or CAD) from the payload 4 with the contracted address CAD generated by the contracted address generation section 3, and outputs a collision signal COL if an address collision is detected. The match determination unit 5 is an example of a collision determination unit that determines a collision between the contracted address CAD and the address held in the payload 4.

The access control unit 8 controls the processing of the memory access command MA held in the payload 4. For example, the access control unit 8 controls access to the data cache 9 based on the memory access instruction MA held in the payload 4. Furthermore, the access control unit 8 controls the commit processing of the memory access instruction MA held in the payload 4 based on the collision signal COL output from the match determination unit 5.

The data cache 9 reads the data DT to be read from the data array in the data cache 9 and outputs it to the register file based on the reception of the read request corresponding to the load instruction. The data cache 9 updates the data held in the data array with the data to be written based on the reception of the write request corresponding to the store command. If the data to be accessed is not held in the data array (cache miss), the data cache 9 reads the data from a lower cache or a memory such as the main memory.

Note that FIG. 1 shows an example in which the load/store queue 2 operates in common for load instructions and store instructions. However, for example, the load/store queue 2 may operate in response to each of a load instruction and a store instruction. In this case, the payload 4 includes multiple entries ENT in which load instructions are stored and multiple entries ENT in which store instructions are stored.

When the abbreviated address generation unit 3 receives a plurality of addresses AD included in the load instruction, the abbreviated address generation unit 3 compares the generated abbreviated address CAD with the plurality of addresses respectively held in the entry ENT for the store instruction to avoid collisions. Determine. When the abbreviated address generation unit 3 receives a plurality of addresses AD included in a store instruction, the abbreviated address generation unit 3 compares the generated abbreviated address CAD with the plurality of addresses respectively held in the entry ENT for the load instruction to determine a conflict. do.

FIG. 2 shows an example of a change in the state of the payload 4 in FIG. 1. In FIG. 2, an example is shown in which two store instructions ST (ST1, ST2) and two load instructions LD (LD3, LD4) are stored in entries ENT1, ENT2, ENT3, and ENT4 of payload 4, respectively. . For example, payload 4 functions as a ring buffer, and the entry number ENT indicates the order in which instructions are written in the program.

An execution flag of "0" indicates that the instruction is not being executed. An execution flag of "1" indicates that the instruction has been executed. "0x" added in front of the numerical value shown in the address and data columns indicates that the numerical value is a hexadecimal number. The symbol n/a shown in the address and data column indicates that the address or data has not been determined. A shaded entry ENT indicates that the state has changed. For example, control of the payload 4 is executed by the access control unit 8 in FIG.

Note that in FIG. 2, for the sake of simplicity, an example is shown in which a scalar store instruction ST and a scalar load instruction LD including a single address are stored in the payload 4. However, a vector store instruction ST and a vector load instruction LD including multiple addresses may be stored in the payload 4. When the vector store instruction ST and vector load instruction LD are stored in the payload 4, the contracted address CAD is stored in the entry ENT. Furthermore, when the vector store instruction ST is stored in the payload 4, a plurality of pieces of data corresponding to a plurality of addresses are stored.

In state 1, store instruction ST1 and load instruction LD4 are executed, and store instruction ST2 and load instruction LD3 are not executed. Since the address of the store instruction ST2 has not been determined, the data "0x456" acquired by the load instruction LD4 subsequent to the store instruction ST2 may be incorrect.

Next, in state 2, load instruction LD3 is executed. The address included in the load instruction LD3 is output from the abbreviated address generation unit 62 as an abbreviated address CAD. The match determining unit 5 compares the address of the load instruction LD3 with the addresses of all instructions stored in the payload 4, regardless of the type of instruction.

The access control unit 8 refers to the comparison results of the address of the load instruction LD3 and the addresses of the store instructions ST1 and ST2 that precede the load instruction LD3 and are stored in the payload 4, among the comparison results by the match determination unit 5. Then, the access control unit 8 detects a collision between the address of the load instruction LD3 and the address of the store instruction ST1. Therefore, the access control unit 8 decides to forward the data to be read by the load instruction LD3 from the entry ENT1 instead of reading it from the data cache 9, and transfers the data "0x123" held in the entry ENT1 to the entry. Store in ENT3.

Next, in state 3, after the contracted address generation unit 3 stores the address of the store instruction ST2 in the entry ENT2, the store instruction ST2 is executed. Then, the address "0x100" and data "0x789" of the store instruction ST2 are stored in the entry ENT2. The address included in the store instruction ST2 is output from the abbreviated address generation unit 62 as an abbreviated address CAD.

The match determining unit 5 compares the address of the store instruction ST2 with the addresses of all instructions stored in the payload 4, regardless of the type of instruction. The access control unit 8 refers to the comparison results of the address of the store instruction ST2 and the addresses of the load instructions LD3 and LD4 subsequent to the store instruction ST2, which are stored in the payload 4, among the comparison results by the match determination unit 5. Then, the access control unit 8 detects a collision between the address of the store instruction ST2 and the address of the load instruction LD3.

In state 4, the access control unit 8 cancels the execution of the load instructions LD3 and LD4 subsequent to the store instruction ST2, and evicts them from the entries ENT3 and ENT4. This makes it possible to cancel the data "0x123" of the load instruction LD3 that was erroneously forwarded from the entry ENT1 in state 2. The canceled load instructions LD3 and LD4 are then reissued.

In this embodiment, the match determining unit 5 compares the abbreviated address CAD generated by the abbreviated address generating unit 3 with the address held in the payload 4, so when a plurality of addresses before abbreviation are used for comparison. The number of match determination circuits 6 can be reduced compared to the above. This makes it possible to reduce the circuit scale of the match determination unit 5 compared to the case where a plurality of addresses before contraction are used for comparison.

In addition, since the contracted address CAD is stored in payload 4, it is possible to improve the usage efficiency of entry ENT compared to the case where multiple addresses before contracting are stored in payload 4, and it can be stored in payload 4. The number of memory access instructions MA can be increased. Thereby, the number of memory access instructions MA whose processing can be controlled by the access control unit 8 can be increased, and the processing performance of the arithmetic processing device 1 can be improved.

Furthermore, if it is not necessary to improve the usage efficiency of entries ENT, the number of entries ENT can be reduced. Thereby, the number of match determination circuits 6 can be further reduced, and the circuit scale of the match determination section 5 can be further reduced.

FIG. 3 shows an example of a method for generating a contracted address by the contracted address generation unit 3 of FIG. 1. FIG. 3 shows an example where the memory access instruction MA1 is a gather instruction or a scatter instruction including eight addresses AD0 to AD7. For simplicity, FIG. 3 shows an example in which each address AD0-AD7 is 8 bits, but the number of bits of each address AD0-AD7 is not limited to 8 bits. Addresses AD0 to AD7, which will be explained from FIG. 3 onwards, are also not limited to 8 bits.

In generation method 1, when the bit values are all "0" at each bit position of addresses AD0 to AD7, the contracted address generation unit 3 sets the bit value of the contracted address CAD to "0" and generates the bit value. are all "1", the bit value of the contracted address CAD is set to "1". In addition, when bit values of "0" or "1" coexist in each bit position of addresses AD0 to AD7, the contracted address generation unit 3 sets the bit value of the contracted address CAD to an undefined value "X". do. In the generation method 2, in addition to the rules of the generation method 1, the contracted address generation unit 3 sets the bits lower than the bit position indicating the indefinite value "X" in the contracted address CAD to the indefinite value "X".

In this way, the contracted address generation unit 3 uses generation method 1 or generation method 2 to generate the contracted address CAD expressed in three-valued logic of "0", "1", and "X". be able to. Note that when the memory access instruction MA1 includes a single address AD, the contracted address generation unit 3 sets the single address AD as the contracted address CAD.

Thereby, the abbreviated address CAD generated by the abbreviated address generation unit 3 can be stored in the payload 4 regardless of whether the memory access instruction MA includes a single address AD or multiple addresses AD. Therefore, compared to the case where the method of storing the payload 4 is different depending on whether it is a single address AD or a contracted address CAD, it is possible to easily control the storage of the addresses AD and CAD in the payload 4. can.

However, since the arithmetic processing device 1 handles binary numbers, it cannot use the indefinite value "X". Therefore, in practice, as explained in FIG. 8, the contracted address generation unit 3 converts the contracted address CAD expressed in ternary logic into a format that can be expressed in binary numbers. Note that, for example, in the contracted address CAD, the contracted address generation unit 3 sets the undefined value "X" to the value "00", sets the value "0" to the value "01", and sets the value "1" to the value "00". It may be set to the value "10".

FIG. 4 shows an example of the address range indicated by the contracted address CAD in FIG. The eight addresses AD0-AD7 included in the memory access instruction MA1 illustrated in FIG. 4 are the same as the addresses AD0-AD7 illustrated in FIG. 3. Further, the contracted address MA1.exemplified in FIG. CAD uses the contracted address MA1. shown in generation method 2 in FIG. It is the same as CAD. When the contracted address CAD is generated by the generation method 2 shown in FIG. 3, the match determining unit 5 converts the address AD in the range from "10100000" to "10111111" shown in FIG. 4 into the contracted address MA1. It is determined that there is a conflict with CAD.

When the contracted address CAD is generated by the generation method 1 of FIG. 3, for example, the address MA1. The address AD of "10110001" where the second bit from the least significant bit of AD0 is "0" is the contracted address MA1. It is determined that there is no conflict with CAD. Therefore, in the generation method 1, the number of addresses AD included in the contracted address CAD can be reduced compared to the generation method 2, and the accuracy of collision determination can be improved.

FIG. 5 shows an example of an address determination operation by each coincidence determination circuit 6 of the coincidence determination section 5 of FIG. 1. In FIG. As shown in FIG. 1, the match determination circuit 6 compares each bit of the abbreviated address CAD generated by the abbreviated address generator 3 with each bit of the address held in one of the entries ENT of the payload 4. compare. Here, the address held in either entry ENT of payload 4 is a single address AD or a contracted address CAD.

For example, when the bit values to be compared are "0" and "1" or "1" and "0", the match determination circuit 6 outputs "0" indicating a mismatch to the AND circuit AND. When the bit values to be compared are "0" and "1", or when at least one of the bit values to be compared is an undefined value "X", the match determination circuit 6 outputs "1" indicating a match using an AND circuit. Output to AND.

If the bit values of the comparison result are all "1" (all match), the AND circuit AND sets the collision signal COL to "1" indicating address collision. If any of the bit values of the comparison result is "0" (mismatch), the AND circuit AND sets the collision signal COL to "0" indicating that there is no address collision. The access control unit 8 in FIG. 1 compares the abbreviated address CAD generated by the abbreviated address generation unit 3 with the address held in the payload 4 based on the logical value of the collision signal COL output from each coincidence determination circuit 6. Determine the collision. Then, the access control unit 8 determines whether or not to commit the memory access instruction MA based on the determination result, and controls the processing of the memory access instruction MA held in the queue.

FIG. 6 shows an example of another arithmetic processing device. The arithmetic processing device 1A shown in FIG. 6 does not have the contracted address generation section 3 of FIG. 1, but has a match determination section 5A and an access control section 8A instead of the match determination section 5 and access control section 8 of FIG.

When the arithmetic processing device 1A does not have the contracted address generation section 3, the coincidence determination section 5A directly receives the plurality of addresses AD0 to AD7 included in the vector load instruction LD or vector store instruction ST. Then, the match determining unit 5A compares the received addresses AD0 to AD7 with the addresses AD held in each entry ENT of the payload 4. For this reason, the match determining section 5A has a number of match determining circuits 6 corresponding to the product of the number of addresses AD0 to AD7 and the number of entries ENT.

The access control unit 8A receives the collision signals COL output from all the coincidence determination circuits 6, and controls the commit processing of the memory access instruction MA held in the payload 4 based on the received collision signal COL. As shown in FIG. 6, the circuit scale of the match determination unit 5A and the access control unit 8A of the arithmetic processing device 1A that does not have the contracted address generation unit 3 is the same as that of the match determination unit 5 and the access control unit 8 in FIG. bigger.

Note that, for example, the circuit scale of the contracted address generation unit 3 in FIG. 1 is about two match determination circuits 6 for each address AD. Therefore, the reduction in the circuit scale of the match determination section 5 and the access control section 8 in FIG. 1 is sufficiently larger than the increase in the circuit scale of the contracted address generation section 3.

As described above, in this embodiment, the match determining unit 5 compares the abbreviated address CAD generated by the abbreviated address generating unit 3 with the address held in the payload 4. Therefore, compared to the case where a plurality of addresses AD0 to AD7 before contraction are used for comparison, the number of match determination circuits 6 can be reduced, and the circuit scale of the match determination section 5 can be reduced.

Since the contracted address CAD is stored in the payload 4, it is possible to improve the usage efficiency of the entry ENT compared to the case where multiple addresses before contracting are stored in the payload 4, and the memory that can be stored in the payload 4 is The number of access instructions MA can be increased. Thereby, the number of memory access instructions MA whose processing can be controlled by the access control unit 8 can be increased, and the processing performance of the arithmetic processing device 1 can be improved.

By converting a single address AD into a contracted address CAD by the contracted address generation unit 3, regardless of whether the address AD included in the memory access instruction MA is single or multiple, the contracted address generation unit 3 generates the contracted address AD. The condensed address CAD can be stored in the payload 4. Therefore, it is possible to easily control storing the addresses AD and CAD in the payload 4.

FIG. 7 shows an example of an arithmetic processing device in another embodiment. Detailed description of elements similar to those in FIGS. 1 to 6 will be omitted. The arithmetic processing device 100 shown in FIG. 7 is, like the arithmetic processing device 1 in FIG. 1, a processor such as a CPU that can execute SIMD arithmetic instructions, for example.

The arithmetic processing device 100 includes an instruction cache 10, a decoder 20, a scheduler 30 such as a reservation station, a register file 40, a plurality of load/store (LDST) units 50, and a plurality of arithmetic units 90.

The instruction cache 10 holds instructions transferred from a memory such as the main memory, and outputs the held instructions to the decoder 20. For example, instruction cache 10 may be a primary instruction cache. The instructions held in the instruction cache 10 are arithmetic instructions and memory access instructions.

For example, the arithmetic instructions include integer arithmetic instructions, fixed point arithmetic instructions, floating point arithmetic instructions, and the like. For example, memory access instructions include load instructions, store instructions, and the like. Furthermore, at least one of the integer arithmetic instructions, fixed point arithmetic instructions, and floating point arithmetic instructions may include a SIMD arithmetic instruction. Furthermore, similar to the arithmetic processing device 1 of FIG. 1, the load instructions include a continuous address load instruction LD as a vector load instruction LD and a gather instruction in addition to a scalar load instruction including a single address. Store instructions include a scalar store instruction including a single address, a continuous address store instruction ST as a vector store instruction ST, and a scatter instruction.

The decoder 20 decodes instructions received in-order from the instruction cache 10 and outputs the decoded instructions to the scheduler 30. Note that the arithmetic processing device 100 may have an instruction buffer between the instruction cache 10 and the decoder 20 that stores a plurality of instructions transferred from the instruction cache 10.

The logical register number included in the instruction decoded by the decoder 20 may be converted, for example, by a rename unit into a physical register number that identifies a physical register within the register file 40. The logical register number is a register number written in the program. By installing the rename unit, the arithmetic processing device 100 can install more physical registers in the register file 40 than the number of registers that can be written in a program. As a result, compared to the case where no rename unit is provided, the frequency of register conflicts can be reduced, and the efficiency of instruction execution can be improved.

Scheduler 30 has an operation queue that includes a plurality of entries that hold arithmetic instructions output from decoder 20, and a memory access queue that includes a plurality of entries that hold memory access instructions that are output from decoder 20. The scheduler 30 issues the arithmetic instructions held in the arithmetic queue to any of the arithmetic units 90 in an executable order out of order. Furthermore, the scheduler 30 outputs the instructions held in the memory access queue to any of the load/store units 50 in an executable order out of order.

Each of the plurality of load/store units 50 executes a load instruction and a store instruction. Each of the plurality of load store units 50 has a plurality of address calculators 52. Further, the plurality of load/store units 50 have a load/store queue 60, an access control section 70, and an L1 (Level 1) data cache 80 that are common to the plurality of load/store units 50. The load/store queue 60 has a contracted address generation section 62 corresponding to each of the plurality of load/store units 50, and a payload 64 and a match determination section 66 common to the plurality of load/store units 50. The match determination section 66 includes a plurality of match determination circuits 67.

Each of the plurality of address calculators 52 calculates the address to be accessed by the memory access command by performing addition processing of data transferred from the register file 40 and the like. Each of the plurality of address calculators 52 outputs the address obtained by calculation to the corresponding contracted address generation section 62 and payload 64. Further, if it is a load instruction, the address AD is output to the L1 data cache 80. By providing a plurality of address calculators 52 in each load/store unit 50, a plurality of addresses included in a vector load instruction or a vector store instruction can be calculated in parallel.

The contracted address generation section 62, similar to the contracted address generation section 3 in FIG. 1, contracts a plurality of addresses AD included in a load instruction or a store instruction to generate a contracted address CAD. An example of a method for generating the reduced address CAD is shown in FIG. The payload 64, like the payload 4 in FIG. 1, includes a plurality of entries ENT (not shown) that hold memory access instructions. Payload 64 is an example of a queue. An example of payload 64 is shown in FIG.

The match determination unit 66 has a plurality of match determination circuits 67 in the entry of the payload 64, similar to the match determination unit 5 in FIG. Each match determination circuit 67 compares the address from the payload 64 with the contracted address CAD generated by the contracted address generation section 62, and outputs a collision signal COL according to the comparison result. The match determination unit 66 is an example of a collision determination unit that determines a collision between the contracted address CAD and the address held in the payload 4. The coincidence determination circuit 67 is an example of a collision determination circuit.

The access control unit 70 controls the processing of the memory access command held in the payload 64 based on the collision signal COL, and controls access to the L1 data cache 80, similar to the access control unit 8 in FIG. L1 data cache 80 has the same configuration and functions as data cache 9 in FIG. 1.

Each arithmetic unit 90 executes arithmetic instructions. For example, each arithmetic unit 90 has a fixed-point arithmetic unit, a floating-point arithmetic unit, and a logic arithmetic unit.

FIG. 8 shows an example of the payload 64 of FIG. 7 and an example of a method for generating a contracted address by the contracted address generation unit 62. The payload 64 includes a plurality of entries ENT (ENT1 to ENT6, etc.) holding memory access instructions MA. For example, each entry ENT holds an execution flag, instruction type (load instruction LD or store instruction ST), key address KEY, data, mask vector MSK, and original address. The original address is the address calculated by each address calculator 52 before reduction. In this embodiment, the contracted address CAD is expressed as a key address KEY and a mask vector MSK.

Similar to the contracted address generator 3 in FIG. 1, the contracted address generator 62 generates the contracted address CAD using three-value logic expressed by "0", "1", and an undefined value "X". generate. However, the contracted address generation unit 62 expresses the contracted address CAD as a key address KEY and a mask vector MSK in order to determine address collision using binary numbers handled by the arithmetic processing unit 100.

By converting the contracted address CAD expressed in three-value logic into a format that can be expressed in binary numbers, the match determination unit 66 in the arithmetic processing device 100 that handles binary numbers converts the contracted address CAD that includes the indefinite value "X" into a format that can be expressed in binary numbers. Address CAD collisions can be determined. In other words, without changing the architecture of the arithmetic processing device 100, it is possible to determine the collision of contracted addresses CAD including the undefined value "X".

The contracted address generation unit 62 selects any one of the plurality of addresses AD included in the memory access instruction MA as the key address KEY. Further, the contracted address generation unit 62 calculates the exclusive OR (XOR) of the bit values at each bit position of the plurality of addresses AD included in the memory access instruction MA, and sets it as a mask vector MSK. FIG. 8 shows an example of calculating the mask vector MSK from eight addresses AD0 to AD7 included in the memory access instruction MA1. The contracted address CAD (KEY, MSK) generated by the contracted address generation section 62 is used for determination by the match determination section 66, and is stored in the payload 64 together with information on the memory access instruction MA.

FIG. 9 shows an example of the match determination circuit 67 of FIG. The match determination circuit 67 includes a negative exclusive OR circuit XNOR, OR circuits OR1 and OR2, and an AND circuit AND. The OR circuit OR1 is an example of a first OR circuit, and the OR circuit OR2 is an example of a second OR circuit. The AND circuit AND is an example of an AND circuit.

The negative exclusive OR circuit XNOR calculates the negative exclusive OR of the bits of the key address KEY held in any of the entries ENT of the payload 64 and the key address KEY generated by the contracted address generation unit 62. do. The OR circuit OR1 calculates the logical OR of the bits of the mask vector MSK held in any of the entries ENT of the payload 64 and the mask vector MSK generated by the contracted address generation section 62.

The OR circuit OR2 calculates the bitwise OR of the output of the negative exclusive OR circuit ENOR and the output of the OR circuit OR1. The AND circuit AND calculates the AND of all bits of the output of the OR circuit OR2, and outputs the calculation result as a collision signal COL.

When the match determination circuit 67 receives the key address KEY and the mask vector MSK illustrated in parentheses in FIG. 9 from the payload 64 and the contracted address generator 62, respectively, the match determination circuit 67 generates a collision signal COL (="1") indicating an address collision. ) is output. In this way, the match determination circuit 67 can determine address collision even when the contracted address CAD is expressed by the key address KEY and the mask vector MSK. That is, the match determination circuit 67 can determine a collision of contracted addresses expressed in ternary logic.

As described above, in this embodiment as well, the same effects as in the above-described embodiment can be obtained. For example, since the match determination unit 66 compares the contracted address CAD with the address held in the payload 64, the number of match determination circuits 67 is reduced compared to the case where multiple addresses AD before contraction are used for comparison. Therefore, the circuit scale of the match determination section 66 can be reduced. Furthermore, by storing the contracted address CAD in the payload 64, more memory access instructions MA can be stored in the payload 64 than in the case of storing a plurality of addresses AD before contracting in the payload 64. The processing performance of the processing device 100 can be improved.

Furthermore, in this embodiment, by converting the contracted address CAD expressed in ternary logic into a format that can be expressed in binary numbers, the match determination unit 66 in the arithmetic processing device 100 that handles binary numbers A collision of contracted addresses CAD containing "X" can be determined. In other words, without changing the architecture of the arithmetic processing device 100, it is possible to determine the collision of contracted addresses CAD including the undefined value "X". The match determination circuit 67 can also determine address collision when the contracted address CAD is expressed by a key address KEY and a mask vector MSK.

FIG. 10 shows an example of a main part of an arithmetic processing device in another embodiment. Detailed description of elements similar to those in the embodiment described above will be omitted. The arithmetic processing device 100A shown in FIG. 10 includes a load/store queue 60A, an access control section 70A, and an L1 data cache 80. The load store queue 60A includes a contracted address generation section 62A, a payload 64, and a match determination section 66A. The coincidence determination section 66A is an example of a collision determination section.

The abridged address generation unit 62A groups a plurality of addresses AD (AD0-AD7) included in a memory access instruction MA (load instruction or store instruction), and generates abbreviated addresses CAD0, CAD0, and CAD0 for each of the divided address groups. Generate CAD1. The contracted addresses CAD0 and CAD1 are output to the match determination unit 66A and stored in the payload 64.

By generating abbreviated addresses CAD0 and CAD1 for each address group, compared to the case where one abbreviated address CAD is generated without dividing addresses AD into groups, the address indicated by each abbreviated address CAD0 and CAD1 is The range of AD can be narrowed. Thereby, the number of addresses AD included in each contracted address CAD0, CAD1 can be reduced, and the accuracy of collision determination can be improved.

The match determining unit 66A has a plurality of match determining circuits 67, the number of which corresponds to the entries ENT of the payload 64, for each contracted address CAD0 and CAD1. Each match determination circuit 67 has the same configuration and function as the match determination circuit 67 in FIG. Similar to the match determining circuit 6 in FIG. 1, the match determining circuit 67 in FIG. 10 compares the address held by the corresponding entry ENT of the payload 64 with the corresponding contracted address CAD0 or AD1. Then, the match determination circuit 67 outputs a collision signal COL according to the comparison result to the access control unit 70A.

The access control unit 70A controls the processing of the memory access command held in the payload 64 based on the plurality of collision signals COL for each contracted address CAD0 and CAD1, and controls access to the L1 data cache 80.

As described above, in this embodiment as well, the same effects as in the above-described embodiment can be obtained. For example, the match determination unit 66A compares the contracted address CAD with the address held in the payload 64. Therefore, compared to the case where a plurality of addresses AD before contraction are used for comparison, the number of match determination circuits 67 can be reduced, and the circuit scale of the match determination section 66A can be reduced. Further, the contracted address generation unit 62A stores the plurality of generated contracted addresses CAD0 and CAD1 in the payload 64. Therefore, the number of memory access instructions that can be stored in the payload 64 can be increased compared to the case where a plurality of addresses AD before contraction are stored in the payload 64. Thereby, the processing performance of the arithmetic processing device 100A can be improved.

Furthermore, in this embodiment, the contracted address generation unit 62A generates a plurality of contracted addresses CAD0 and CAD1. As a result, the range of addresses AD indicated by each of the contracted addresses CAD0 and CAD1 can be narrowed compared to the case where one contracted address CAD is generated. Therefore, the number of addresses AD included in each contracted address CAD0, CAD1 can be reduced, and the accuracy of collision determination can be improved. As a result, for example, it is possible to reduce the frequency that a load instruction LD whose address AD does not actually conflict is canceled because it is determined to conflict with a preceding store instruction ST, and the processing performance of the arithmetic processing unit 100A can be reduced. The decrease can be suppressed.

FIG. 11 shows an example of a main part of an arithmetic processing device in another embodiment. Detailed description of elements similar to those in the embodiment described above will be omitted. The arithmetic processing device 100B shown in FIG. 11 has the same configuration as the arithmetic processing device 100A in FIG. 10, except that it has a load/store queue 60B instead of the load/store queue 60A in FIG.

The load/store queue 60B has a contracted address generator 62 added to the load/store queue 60A in FIG. The condensed address generation section 62 has the same configuration and function as the condensed address generation section 62 in FIG. 8 . That is, the contracted address generation unit 62 contracts a plurality of addresses AD (AD0-AD7) included in a memory access instruction MA (load instruction or store instruction) to generate a contracted address CAD. The abbreviated address generation unit 62 in FIG. 11 is an example of a first abbreviated address generation unit, and the abbreviated address CAD generated by the abbreviated address generation unit 62 is an example of the first abbreviated address. The condensed address generation unit 62A is an example of a second condensed address generation unit, and the condensed addresses CAD0 and CAD1 generated by the condensed address generation unit 62A are examples of second condensed addresses.

The contracted address CAD generated by the contracted address generation unit 62 is stored in the payload 64. Therefore, in this embodiment, the number of contracted addresses CAD stored in the payload 64 can be reduced from the number of contracted addresses CAD0 and CAD1 stored in the payload 64 of FIG. As a result, the number of addresses AD stored in the payload 64 increases relatively, so the number of memory access instructions stored in the payload 64 can be increased, and the processing performance of the arithmetic processing unit 100B can be improved. .

As described above, in this embodiment as well, the same effects as in the above-described embodiment can be obtained. Furthermore, in this embodiment, the contracted address CAD is stored in the payload 64, and the contracted addresses CAD0 and CAD1 are output to the match determination section 66A. This makes it possible to increase the number of addresses AD stored in the payload 64 compared to the case where the contracted addresses CAD0 and CAD1 are stored in the payload 64, while improving the accuracy of collision determination by the match determination unit 66A. . As a result, the processing performance of the arithmetic processing device 100B can be improved.

In the above example, the abbreviated address CAD generated by the abbreviated address generation unit 62 is a single abbreviated address. However, a plurality of abbreviated addresses may be generated for each of a plurality of groups divided by a different number or a different method of grouping from the abbreviated addresses generated by the abbreviated address generation unit 62A. Furthermore, although two examples are used to explain the number of contracted addresses generated by the contracted address generation unit 62A, there may be three or more contracted addresses.

FIG. 12 shows an example of a main part of an arithmetic processing device in another embodiment. Detailed description of elements similar to those in the embodiment described above will be omitted. The arithmetic processing device 100C shown in FIG. 12 is the arithmetic processing device 100 in FIG. 7, the arithmetic processing device 100A in FIG. 10, or the arithmetic processing device 100B in FIG. ing. Although one match determination circuit 67C is shown in FIG. 12, in reality, a match determination circuit 67C is provided for each entry ENT (not shown) included in the payload 64. A match determining section including a plurality of match determining circuits 67 and a plurality of match determining circuits 67C is provided. The coincidence determination circuit 67C is an example of a collision determination circuit.

The condensed address generation unit 62C generates a condensed address CAD2 indicating a range of a plurality of addresses AD included in the memory access command. The contracted address CAD2 generated by the contracted address generation unit 62C is an example of the fourth contracted address. For example, the abbreviated address generation unit 62C generates the start address AH (=A0) and the offset OFSA, which is the distance from the start address AH to the end address AE, as the abbreviated address CAD2. The contracted address generation unit 62C stores the generated contracted address CAD2 in the payload 64.

For example, in an entry ENT (not shown) of the payload 64, information indicating the memory access command MA and an abbreviated address CAD2 including a start address BH and an offset OFSB generated by the abbreviated address generation unit 62C in the past are stored. That is, each entry ENT of the payload 64 stores the abbreviated address CAD2 or the abbreviated address CAD generated by the abbreviated address generation unit 62 of FIG. Note that when the memory access instruction MA includes a single address AD, the single address AD is set as the start address AH (or BH) and the offset OFSA (or OFSB) is set to "0" according to the reduction rule. Set.

The coincidence determination circuit 67C includes adders ADDa, ADDb, comparators CMPa, CMPb, an OR circuit OR, and an inversion circuit NOT. The adder ADDa calculates the final address AE by adding the start address AH output from the contracted address generation unit 62C and the offset OFSA. The adder ADDb calculates the final address BE by adding the start address BH output from the corresponding entry ENT of the payload 64C and the offset OFSA.

The comparator CMPa compares the final address BE and the first address AH to determine the magnitude relationship. For example, the comparator CMPa outputs "1" when the final address BE is smaller than the starting address AH, and outputs "0" when the final address BE is greater than or equal to the starting address AH. The comparator CMPb compares the start address BH and the end address AE to determine the magnitude relationship. For example, the comparator CMPb outputs "1" when the final address AE is smaller than the starting address BH, and outputs "0" when the final address AE is greater than or equal to the starting address BH.

The OR circuit OR outputs the logical sum of the outputs of the comparators CMPa and CMPb to the inversion circuit NOT. The inverting circuit NOT inverts the logical value output from the OR circuit OR and outputs it as a collision signal COL. Therefore, the logic of the collision signal COL is expressed by equation (1).
COL="not((AE<BH)or(BE<AH)))... (1)

Note that the abbreviated address generation unit 62C may generate the start address AH and the end address AE as the abbreviated address CAD2. In this case, the number of bits of the contracted address CAD2 increases, but the match determination circuit 67C does not need to include the adders ADDa and ADDb. By generating an abbreviated address CAD2 indicating the range of multiple addresses AD included in a memory access instruction, collision determination accuracy is improved compared to an abbreviated address CAD generated using ternary logic. I can do it.

FIG. 13 shows an example of the operation of the match determination circuit 67C of FIG. 12. Note that the match determination section of this embodiment includes the match determination circuit 67 of FIG. 9 and the match determination circuit 67C of FIG. 12. As shown in FIG. 13, the collision signal COL is generated when the range of the contracted address CAD2 indicated by the start address AH and the offset OFSA does not overlap the range of the contracted address CAD2 indicated by the start address BH and the offset OFSB. , is set to "0". The collision signal COL is set to "1" when the range of the contracted address CAD2 indicated by the start address AH and the offset OFSA overlaps the range of the contracted address CAD2 indicated by the start address BH and the offset OFSB. .

In the arithmetic processing device 100C shown in FIG. 12, a contracted address CAD expressed in ternary logic and a contracted address CAD2 indicating a range of addresses AD are generated from a plurality of addresses AD included in a memory access instruction MA. . For example, the contracted address generation unit 62 in FIG. 7 contracts the bits of a plurality of addresses AD to generate a contracted address CAD. Note that the abbreviated address CAD may be generated by the abbreviated address generation unit 62A in FIG. 10 or 11. The abridged address CAD generated by the abbreviated address generators 62 and 62A is an example of the third abridged address. Further, the abbreviated address generation unit 62C in FIG. 12 generates an abbreviated address CAD2 indicating a range of a plurality of addresses AD.

Here, it is difficult to convert the plurality of addresses AD that do not change in ascending order or descending order into the contracted address CAD2 as is. For this reason, the abbreviated address generation unit 62C, like the abbreviated address generation unit 62, first generates an abbreviated address CAD expressed in three-valued logic of "0", "1", and "X". Next, the condensed address generation unit 62C generates the minimum value of the address AD assuming that the undefined value "X" of the generated condensed address CAD is "0", and generates the undefined value "X" of the generated condensed address CAD. Assuming that " is "1", the maximum value of address AD is generated. Then, the abridged address generation unit 62C generates an abridged address CAD2 including the start address AH and the offset OFSB. Note that the contracted address generation unit 62C replaces the undefined value “X” of the contracted address CAD generated by the contracted address generation unit 62 with “0” and “1” to determine the minimum value and maximum value of the address AD. may be generated.

The load store queue including the abbreviated address generation unit 62 and the abbreviated address generation unit 62C outputs the abbreviated address CAD generated by the abbreviated address generation unit 62 to the payload 64 when a plurality of addresses AD do not change in ascending or descending order. Store. The load store queue stores the abbreviated address CAD2 generated by the abbreviated address generation unit 62C in the payload 64 when a plurality of addresses AD change in ascending or descending order.

When the abbreviated address CAD is held in the entry of the payload 64, the match judgment unit including the match judgment circuits 67 and 67C selects the held abbreviated address CAD and the abbreviated address generated by the abbreviated address generation unit 62. Determine collision with CAD. When the abbreviated address CAD2 is held in the entry of the payload 64, the match judgment unit including the match judgment circuits 67 and 67C selects the held abbreviated address CAD2 and the abbreviated address generated by the abbreviated address generation unit 62C. Determine collision with CAD2.

In this way, when the addresses AD included in the memory access instruction MA are not in ascending or descending order, the abbreviated address CAD generated by the abbreviated address generation unit 62 is used to determine whether the addresses AD collide. When the addresses AD included in the memory access instruction MA are in ascending or descending order, a collision of addresses AD is determined using the abbreviated address CAD2 generated by the abbreviated address generation unit 62C.

For example, a gather instruction or a scatter instruction is a memory access instruction MA in which addresses AD are not in ascending or descending order. For example, as the memory access instruction MA in which addresses AD are in ascending or descending order, there is a continuous address load instruction LD such as a stride access instruction or a continuous address vector store instruction ST.

As described above, in this embodiment as well, the same effects as in the above-described embodiment can be obtained. Furthermore, in this embodiment, when the addresses AD included in the memory access instruction MA are in ascending or descending order, the collision determination accuracy is improved by determining a collision of addresses AD using the contracted address CAD2. be able to.

The features and advantages of the embodiments will become apparent from the above detailed description. It is intended that the appended claims extend to the features and advantages of such embodiments without departing from the spirit and scope thereof. Additionally, all improvements and changes will be readily apparent to those having ordinary knowledge in the relevant technical field. Therefore, it is not intended that the scope of the inventive embodiments be limited to those described above, but suitable modifications and equivalents may be made within the scope disclosed in the embodiments.

1, 1A Arithmetic processing unit 2, 2A Load store queue 3 Contracted address generation unit 4 Payload 5, 5A Match determination unit 8, 8A Access control unit 9 Data cache 10 Instruction cache 20 Decoder 30 Scheduler 40 Register file 50 Load store unit 52 Address calculator 60, 60A, 60B Load store queue 62, 62A, 62C Condensed address generation unit 64 Payload 66, 66A Match determination unit 67, 67C Match determination circuit 70, 70A Access control unit 80 L1 data cache 90 Arithmetic unit 100, 100A, 100B, 100C Processing unit AD (AD0-AD7) Address AE Last address AH Start address BE Last address BH Start address CAD, CAD0, CAD1, CAD2 Condensed address COL Collision signal DT Data ENT Entry ICD Instruction code KEY Key address LD Load instruction MA Memory access instruction MSK Mask vector OFSA, OFSB Offset ST Store instruction STD Store data

Claims (12)

a queue holding memory access instructions including at least one address;
When a memory access instruction includes a plurality of addresses, a contracted address generation unit that contracts bits of the plurality of addresses to generate a contracted address;
a collision determination unit that determines a collision between the contracted address and the address held in the queue;
an access control unit that controls processing of memory access instructions held in the queue based on a determination result by the collision determination unit;
An arithmetic processing unit having: The arithmetic processing device according to claim 1, wherein the abridged address generation unit stores the generated abridged address in the queue. The contracted address generation unit generates the contracted address by contracting a plurality of addresses included in the memory access instruction and a single address included in the memory access instruction according to a reduction rule. The arithmetic processing device according to item 2. The contracted address generation unit generates the contracted address for each of a plurality of address groups obtained by grouping a plurality of addresses included in the memory access instruction,
The arithmetic processing device according to any one of claims 1 to 3, wherein the collision determination unit determines collisions between contracted addresses of the plurality of address groups and addresses held in the queue. The abbreviated address generation unit includes:
a first reduced address generation unit that reduces bits of the plurality of addresses for each of a plurality of groups divided by a different number or a different method of grouping from the plurality of address groups;
a second abridged address generation unit that abridges bits of a plurality of addresses for each of the plurality of address groups;
storing a first condensed address generated by the first condensed address generation unit in the queue;
The arithmetic processing device according to claim 4, wherein the second abbreviated address generated by the second abbreviated address generation unit is output to the collision determination unit. The contracted address generation unit generates a contracted address indicating a range of multiple addresses included in the memory access instruction,
The arithmetic processing device according to any one of claims 1 to 3, wherein the collision determination unit determines a collision between an address included in the range indicated by the contracted address and an address held in the queue. . The abbreviated address generation unit includes:
generating a third contracted address by contracting the bits of the plurality of addresses and a fourth contracted address indicating a range of the plurality of addresses;
holding one or both of the generated third abridged address and fourth abridged address in the queue;
The collision determination unit includes:
If the third condensed address is held in the queue, determining a collision between the third condensed address held in the queue and the third condensed address generated by the condensed address generation unit;
If the fourth condensed address is held in the queue, a collision between the fourth condensed address held in the queue and the fourth condensed address generated by the condensed address generation unit is determined. 6. The arithmetic processing device according to 6. 2. The contracted address generation unit generates a contracted address expressed in three-value logic in which the bit values are all "0", all "1", or undefined at each bit position of the plurality of addresses. The arithmetic processing device according to any one of claims 1 to 7. The arithmetic processing device according to claim 8, wherein the abbreviated address generation unit generates the abbreviated address by making bits lower than a bit position indicating indeterminate as indeterminate. The contracted address generation unit generates, as a contracted address, a key address indicating one of the plurality of addresses and a mask vector expressed by an exclusive OR of bit values at each bit position of the plurality of addresses. The arithmetic processing device according to claim 8 or 9. The collision determination unit includes a plurality of collision determination circuits that respectively determine collisions between the contracted address and the plurality of addresses held in the queue,
Each of the plurality of collision determination circuits includes:
a negative exclusive OR circuit that calculates a negative exclusive OR between bits of a key address included in the contracted address and the contracted address held in the queue;
a first OR circuit that calculates an OR between bits of a mask vector included in the contracted address and the contracted address held in the queue;
a second OR circuit that calculates the bitwise OR of the output of the negative exclusive OR circuit and the output of the first OR circuit;
an AND circuit that calculates an AND of all bits of the output of the second OR circuit;
The arithmetic processing device according to claim 10, wherein an address collision is detected when the output of the AND circuit is "1". An arithmetic processing method for an arithmetic processing device having a queue holding memory access instructions including at least one address, the method comprising:
When a memory access instruction includes a plurality of addresses, a contracted address generation unit included in the arithmetic processing device contracts bits of the plurality of addresses to generate a contracted address;
a collision determination unit included in the arithmetic processing device determines a collision between the contracted address and the address held in the queue;
An arithmetic processing method, wherein an access control unit included in the arithmetic processing device controls processing of memory access instructions held in the queue based on a determination result by the collision determination unit.

Images