JP4904802B2 - Cache memory and processor - Google Patents

Description

  The present invention relates to a cache memory and a processor, and more particularly to a cache memory provided in a processor that executes a plurality of processes in parallel, such as a multithread processor, and a processor including such a cache memory.

  In recent years, attention has been paid to a multiprocessor (multicore) or a multithread processor that executes a plurality of threads and tasks (in the first embodiment, unified as threads) in parallel. Such processors are collectively referred to as multiprocessor systems. In a multiprocessor system, data that may be used for processing out of data once read from the external memory is stored in order to improve the efficiency of access to the external memory in which data or the like is stored. There are multiprocessor systems with cache memory. For example, Patent Document 1 is cited as a conventional technique having such a configuration.

  In addition, in a multiprocessor having a cache memory as shown in Patent Document 1, it is necessary to maintain consistency (coherency) of data used for processing among a plurality of processors. Conventional processors often employ bus snoops to maintain data coherency. Bus snoop is a function for observing a transaction on a memory interface bus shared between processors and detecting whether a transaction related to data in a cache memory allocated to the processor has occurred. .

When a transaction of data in the cache memory allocated to itself occurs, the processor updates the corresponding entry in the cache memory, and the contents of the data stored in the cache memory area of each processor in the multiprocessor system To unify. There are many implementations of bus snoop, such as write-once and Berkeley protocols.
JP 2004-178571 A

  However, the above-described invention of Patent Document 1 divides the storage area of the cache memory into independent areas and assigns them to threads that are simultaneously executed in the multiprocessor system. According to Patent Document 1 described above, there is a problem in that data required for the cache memory is stored, and the rate (hit rate) of successful access (hit) to the data decreases.

  Furthermore, when the coherency is maintained using the bus snoop function in the configuration described in Patent Document 1, the hardware configuration of the multiprocessor system is enlarged by a circuit that monitors the bus. Further, power consumption increases because the bus is constantly monitored, and data is rewritten by accessing each independent area of the cache memory, resulting in low coherency holding operation efficiency.

  The present invention has been made in view of the above-described points, and maintains data coherency between processors efficiently in a multiprocessor system without increasing the device configuration or increasing power consumption. It is an object of the present invention to provide a cache memory capable of performing the above and a processor including the cache memory.

In order to solve the above problems, the cache memory of the present invention caches at least a part of data read from a storage device by a plurality of processors, and supplies at least a part of the cached data to the processor. A data storage means for storing data read from the storage device, and an address of the data stored in the data storage means, the entire data stored in the data storage means Address management means that collectively manage the data, and the address of the data requested to be supplied by the processor is checked against the address managed by the address management means, and the data requested to be supplied is read from the data storage means Hit detection means for detecting whether or not possible, and the hit detection means Data if it is detected is readable, characterized in that it comprises a data supply means for supplying the detected data to said processor by.

  According to such an invention, since the addresses in the data storage means of the data cached by the plurality of processors can be collectively managed, the data cached by the plurality of processors is substantially stored in one data storage means. Therefore, it is possible to eliminate data inconsistency in the data storage means. Therefore, it is possible to provide a cache memory that can keep data coherency between processors efficiently. Furthermore, since it is not necessary to add a separate circuit or the like to maintain data coherency, the cache memory device configuration is not increased or the power consumption is not increased.

The cache memory according to the present invention further includes buffer means for temporarily storing at least one of data read from the data storage means and data written to the data storage means.
According to such an invention, the number of accesses to the data management means and the data storage means can be reduced, the access speed to the cache memory can be increased, and the processing speed of the processor employing the cache memory can be improved.

  The cache memory according to the present invention supplies the detected data to the processor and the processor when the data supply means detects that the data can be read by the hit detection means. The data including the continuous data is also supplied to the buffer means for temporarily storing the data read from the data storage means.

  According to such an invention, data following the data supplied to the processor can be stored in the buffer in advance, and there is no need to access the data management means and the data storage means when this data is requested next time. Therefore, the number of accesses to the data management unit and the data storage unit can be reduced, the access speed to the cache memory can be increased, and the processing speed of the processor employing the cache memory can be improved.

The cache memory according to the present invention further includes pre-read data storage means for caching data expected to be supplied by the processor.
According to such an invention, the number of accesses to the data management means and the data storage means can be reduced, the access speed to the cache memory can be increased, and the processing speed of the processor employing the cache memory can be improved.

  In the cache memory according to the present invention, the data management unit manages the address of the data storage unit as a plurality of ways, and stores data stored in the data storage unit in the data storage unit. The storage priority is assigned to each way, and the storage priority assigned to each way is determined based on the state of access to the data managed by the way. .

According to such an invention, even when data is managed by a plurality of ways, the cache hit rate can be increased by adopting the LRU method.
The cache memory according to the present invention is characterized in that at least one of the data storage means and the data management means is a multiport memory.
According to such an invention, it becomes possible for a plurality of processors to access the data memory and the tag memory at high speed, and the processing capability of the multiprocessor can be improved.

The processor of the present invention includes a cache memory that caches at least part of data read from the storage device by a plurality of processors and supplies at least part of the cached data to the processor. In the cache memory, the data storage means stores the data storage means for storing the data read from the storage device, and the address of the data stored in the data storage means. Address management means for collectively managing the entire data, the address of the data requested to be supplied by the processor is collated with the address managed by the address management means, and the data requested to be supplied is the data storage means Hit detection means for detecting whether or not reading is possible, and If the data by Tsu preparative detecting means is detected to be readable, characterized in that it comprises a data supply means for supplying the detected data to said processor.

  According to such an invention, since the addresses in the data storage means of the data cached by the plurality of processors can be collectively managed, the data cached by the plurality of processors is substantially stored in one data storage means. Therefore, it is possible to eliminate data inconsistency in the data storage means. For this reason, it is possible to provide a processor that can maintain data coherency between processors efficiently. Furthermore, since it is not necessary to add a separate circuit or the like to maintain data coherency, the apparatus configuration in the processor is not increased, or power consumption is not increased.

In addition, the cache memory according to the present invention is characterized in that each of the plurality of processors executes processing for each thread and can change a thread being executed during the processing to another thread.
According to such an invention, even in a multithread processor in which one processor is likely to access common data, data coherency can be maintained between the processors with high operational efficiency.

  Hereinafter, a first embodiment and a second embodiment of a cache memory according to the present invention and a processor including the cache memory will be described with reference to the drawings.

(Embodiment 1)
FIG. 1 is a diagram showing a multi-thread processor 101 having a cache memory common to the first and second embodiments of the present invention. The multi-thread processor 101 reads data from the external memory 105 or writes the result of the executed thread in the external memory 105.

  In addition, the multi-thread processor 101 includes a cache memory 109 and reads or writes data to and from the external memory 105 via the cache memory 109. The cache memory 109 stores data cached by a plurality of processors included in the multi-thread processor 101, and supplies at least a part of the cached data to any of the plurality of processors. Therefore, the multi-thread processor 101 can receive a large amount of data without accessing the external memory 105.

  The cache memory 109 generally has a configuration that allows a processor to access it faster than the external memory 105. For this reason, the configuration in which the cache memory 109 is accessed to acquire data speeds up the reading and writing of data of the multithread processor 101 and reduces the number of accesses to the external memory 105, Processing efficiency can be increased.

  In addition, the multi-thread processor 101 does not assign a plurality of threads and a processor used for executing the thread one-to-one, and each of the plurality of processors executes a process for each thread and executes the process. Threads running inside can be changed with other threads. Such a multi-thread processor 101 is operated by a multi-thread OS.

  That is, in the multi-thread processor 101, a plurality of processors dynamically change threads to be executed according to the priority order of threads. Such an operation is illustrated in FIG. In the example shown in FIG. 2, the multi-thread processor 101 includes four processors from processor 0 to processor 3. In any of the processors, an interrupt of a thread having a higher priority is entered during execution of the thread, and the processing is switched to the interrupted thread.

When the thread is switched, the multi-thread processor 101 saves the state and result (context) of the thread immediately before the switching, and sets the context of the thread to be executed next as the processor.
In the multi-thread processor 101, the OS operates in any of the processors 0 to 3, and can control other processors. In such a multi-thread processor, a plurality of processors share processing from an equivalent standpoint, and is also called a symmetric multiprocessor (SMP).

  Further, the cache memory 109 includes a cache memory unit 107 that is used for storing data, and a cache control unit 103 that controls storage of data in the cache memory unit 107. As shown later, the cache memory unit 107 includes a tag memory for managing addresses and states attached to data, and a data memory for storing a data body.

  FIG. 3 is a diagram showing the configuration of the cache memory 109 in more detail. In the first embodiment, the cache memory 109 can be connected to four processors from the processor 0 to the processor 3 to receive data requests from the four processors and write data received from the four processors. . In the first embodiment, a data request made by each processor to the cache memory 109 is hereinafter referred to as a read command.

  As shown in FIG. 1, the cache memory 109 includes a cache control unit 103, a cache memory unit 107, and a hit detection unit 208. The cache memory unit 107 includes a tag memory 206 and a data memory 207, and the data memory 207 is configured to store data read from the external memory 105. The tag memory 206 is configured to collectively manage addresses in a data memory 207 that stores data read from the external memory 105 and a read buffer described later.

  The tag memory 206 is a memory that stores, for example, a table or the like associating data in the external memory 105 with data and an address where the data is currently stored. Since the data may be stored in the data memory 207 in addition to the external memory 105, the address where the data is currently stored can be the address of the data memory 207.

In the first embodiment, the tag memory 206 manages not only the data address but also the state (status). The status here is information indicating whether the data is valid, invalid, dirty (changed after being read from the external memory 105), or the like.
The cache control unit 103 includes an address control unit 201, a buffer management unit 202, a write buffer 203, and a read buffer 205.

  The address control unit 201 acquires the address of the requested data from the read command input from the processor, converts it to an address for accessing the tag memory 206 and the data memory 207, and outputs it to the tag memory 206. Alternatively, when the data cached in the data memory 207 is read, the address of the data read to the tag memory 206 and the data memory 207 is output. Further, when data not cached in the data memory 207 is read from the external memory 105, an address of the external memory 105 is generated and output to the external memory 105.

  The cache control unit 103 controls access to the tag memory 206 and the data memory 207 based on the address generated by the address control unit 201. The cache control unit 103 can also reduce power consumption by a method such as supplying a memory access clock only when access to the tag memory 206 and the data memory 207 actually occurs.

  The write buffer 203 is a buffer that temporarily stores (buffers) data to be written to the data memory 207, and includes buffers 203a, 203b, 203c, and 203d corresponding to the processors 0 to 3, respectively. . Further, the read buffer 205 is a buffer for buffering data read from the data memory 207. Similarly to the write buffer 203, the buffers 205a, 205b, and 205c corresponding to the processors 0 to 3, respectively. , 205d. The write buffer 203 and the read buffer 205 are provided to adjust the timing of writing or reading to the data memory 207.

  Further, the cache control unit 103 includes a buffer management unit 202. The buffer management unit 202 has a configuration for ensuring data consistency between the write buffer 203 and the read buffer 205. That is, the buffer management unit 202 compares the data stored in the write buffer 203 with the data stored in the read buffer 205, and when a mismatch between data that should be the same data is detected. For example, the data on the side stored in the read buffer 205 is updated or deleted to make them coincide.

  The hit detection unit 208 compares the address of the data requested to be supplied by the processor with the address managed by the tag memory 206, and detects whether there is data requested to be supplied to the data memory 207. Furthermore, in the first embodiment, when the data requested to be supplied is detected, the hit detection unit 208 supplies the detected data to the multithread processor 101.

  Next, the operation of the above-described configuration will be described for reading and writing with respect to the cache memory 109.

(Read operation)
The multi-thread processor 101 outputs a read command from, for example, the processor 0 among the plurality of processors. The read command includes an address (read address) of data requested to be supplied in the external memory 105 and a signal instructing reading (read control signal). The address control unit 201 detects data stored in the buffer 205 a corresponding to the processor 0 of the read buffer 205.

  When data is stored in the buffer 205a, the tag address attached to the stored data is compared with the read address. If the read address matches the tag address of the data stored in the buffer 205a of the read buffer 205, the data stored in the buffer 205a is output to the processor 0 to complete the read process.

  When the data with the tag address corresponding to the read address is not stored in the read buffer 205, the address control unit 201 accesses the tag memory 206 and collates the read address. The processor uses an address in the external memory 105 as a read address. In the first embodiment, the address control unit 201 converts an address in the external memory 105 into an address for accessing the data memory 207.

  The tag memory 206 stores the address in the data memory 207 of the data to be read in association with the status. If the data specified by the read address is in the data memory 207 as a result of the collation in the tag memory 206, the tag memory 206 outputs the data status to the hit detection unit 208. The collation result in the tag memory 206 is also output to the data memory 207, and data read by the processor 0 is output from the data memory 207 to the hit detection unit 208. The hit detection unit 208 outputs the hit data to the processor 0 when it is determined that the data can be read based on the data status, that is, the cache hit.

The hit detection unit 208 transfers the data for one entry related to the output data to the read buffer 205 at the same time as the output of the data. By such processing, when data transferred at the next access is read, the data can be read without the cache control unit 103 accessing the tag memory 206 and the data memory 207.
On the other hand, if the data corresponding to the read address is not in the tag memory or the data cannot be read because the data status is invalid (cache miss hit), the cache control unit 103 receives data from the external memory 105. The data is read into the memory and transferred to the read buffer 205, and then output to the processor 0. Similarly to the case of a cache hit, the data for one entry is transferred to the read buffer 205.

  In the first embodiment described above, the read buffer 205 includes buffers 205a to 205d corresponding to each of the plurality of processors. However, the first embodiment is not limited to such a configuration, and the case where data with a tag address that matches the read address of the read instruction by the processor 0 is stored in a buffer other than the buffer 205a. In addition, a function of reading data stored in a buffer other than the buffer 205a can be added.

  In a multi-thread processor in which a plurality of processors dynamically execute processing by switching threads, the same data may be repeatedly used by a plurality of different processors. For this reason, as described above, if the processor that has output the read command can access any of the buffers 205a to 205d in the read buffer 205, for example, the processor 0 can access the read buffer 205 during processing of another processor. The transferred data can be read.

According to such processing, the number of times that the cache control unit 103 accesses the tag memory 206 and the data memory 207 is reduced, and the processing efficiency of the multithread processor 101 relating to data reading is improved.
Further, the first embodiment described above can maintain data coherency between processors with high operational efficiency. That is, for example, in a configuration including a tag memory and a data memory for each processor, data having the same tag address is stored in a plurality of different data memories. Then, data mismatch between processors occurs because only a part of data existing in a plurality of data memories is updated.

  However, according to the first embodiment, since the tag memory 206 collectively manages the addresses in the data memory 207 of the data read from the external memory 105, the data read by only one data memory is saved. As a result, the data mismatch in the cache memory can be eliminated. For this reason, the first embodiment does not need to monitor the bus, and does not require a circuit or power consumption for monitoring the bus. Therefore, the apparatus configuration of the multiprocessor system is not increased or the power consumption is not increased in order to maintain data coherency between processors.

Furthermore, as shown in FIG. 2, the multi-thread processor according to the first embodiment is applied to a configuration in which data mismatch is likely to occur, such as a multi-thread OS in which a single processor dynamically switches and executes a plurality of threads This is particularly advantageous.
In the first embodiment, the data for one entry related to this data is transferred to the read buffer 205 while reading the hit data. Therefore, the number of times the processor accesses the tag memory 206 and the data memory 207 can be reduced, and the load on the multi-thread processor for reading data can be reduced.

  In other words, a data memory that stores data to be read generally has a slower access time than a buffer and is likely to become a bottleneck for improving the performance of the processor. By providing a read buffer and a write buffer in front of the data memory, it becomes possible to apparently hide the delay of memory access, and as a result, the performance of the processor can be improved.

(Light operation)
Next, a write operation by the multithread processor of the first embodiment will be described. The write operation described below uses write back as an example, but can also be applied to write through.
The multithread processor 101 outputs an instruction (write instruction) instructing to write data from, for example, the processor 0 among the plurality of processors. The write command includes an address (write address) of data requested to be written in the external memory 105 and a signal instructing writing (write control signal). In the write operation, data (write data) written together with the write command is also sent from the processor.

Write data is first stored in the write buffer 203 together with the write address in the cache memory 109. The write buffer 203 is a FIFO memory (First In First Out memory), and writes the written data into the data memory 207 in the order of writing.
In order to write data to the data memory 207, the cache control unit 103 first checks the write address against the tag address of the tag memory 206 and detects the status of the data. As a result, when it is determined that data can be written into the data memory 207, that is, when a cache hit is determined, the write data is written into the data memory 207. Further, the flag indicating the status of the data stored in the tag memory is set to “dirty”.

In addition, when the cache control unit 103 determines that data cannot be written to the data memory 207, that is, a cache miss has occurred, the cache control unit 103 reads data corresponding to the write data from the external memory 105 to the data memory 207. Then, the tag memory 206 written to the write buffer 203 is updated.
In the first embodiment, since the FIFO memory is employed for the write buffer 203, writing to the write buffer 203 by the processor is successively performed until the write buffer 203 becomes full. Further, the data written in the write buffer 203 is written using the free time while arbitrating with other processes according to the access status to the tag memory 206 and the data memory 207.

Note that the buffer management unit 202 arbitrates writing to the read buffer 205 in the above read operation and writing to and reading from the write buffer 203 in the write operation. In addition, data consistency (coherency) is ensured between the write buffer 203 and the read buffer 205.
The data consistency between the write buffer 203 and the read buffer 205 is that the data written in the write buffer 203 is read-accessed to the same data in the read buffer 205 before the data memory 207 is written. When this happens, it becomes a problem. In such a case, the buffer management unit 202 updates the contents of the read buffer 205 with the written data. Alternatively, it is conceivable that the data in the read buffer 205 is once invalidated, the write data is written from the write buffer 203 to the data memory 207, and then the written data is read.

From the viewpoint of processing efficiency, it is desirable to update the contents of the read buffer 205 with the written data.
In addition, when the read buffer 205 is updated, even when the processor 0 accesses the corresponding read buffer portion of the read buffer 205, the read buffer 205 corresponding to another processor is also updated. There is a need. That is, since the same data may be used in a plurality of threads, it is necessary to guarantee data consistency between reading and writing by a processor other than processor 0 with respect to writing by processor 0.

  According to the first embodiment described above, since the write data is written to the data memory 207 whose addresses are collectively managed by the tag memory 206, the data read by only one data memory is saved. Thus, data mismatch in the cache memory can be eliminated. For this reason, the first embodiment does not need to monitor the bus, and does not require a circuit or power consumption for monitoring the bus. Therefore, the apparatus configuration of the multiprocessor system is not increased or the power consumption is not increased in order to maintain data coherency between processors.

FIG. 4 is a flowchart for explaining the data read or write operation executed in the cache memory of the first embodiment described above. FIG. 5 is a flowchart for explaining the data read operation executed in the conventional cache memory for comparison with FIG.
As shown in FIG. 4, the cache memory of the first embodiment detects a cache hit in the tag memory 206 when one of a plurality of processors (referred to as processor k) requests access to the cache memory 109. (S401). As a result, when a cache hit is detected (S402: Yes), the data memory 207 is accessed, and data to be read is read (S406). Further, the status of data in the tag memory 206 is updated (S407).

  When the cache memory 109 detects a cache miss hit in step S402 (S402: No), the cache memory 109 determines data to be replaced among the data stored in the data memory 207 (S403). Then, dirty data is written out from the data memory 207 (S404), and new data stored in the external memory 105 is read out to the data memory 207 (S405).

  The conventional cache memory whose processing is shown in FIG. 5 is different from the cache memory of the first embodiment in that each of k processors includes an independent tag memory and data memory. Therefore, in the determination in step S502, the conventional cache memory accesses the data memory corresponding to the processor k that requested access (S506), and updates the tag memory corresponding to the processor k (S507).

Further, it is determined whether or not the access of the processor k is writing (S508). If it is writing (S508: Yes), the data in the data memory and the tag memory corresponding to the processors other than the processor k are stored. Updates and adjusts data coherency between data memories.
The cache memory according to the present embodiment described above is not limited to the configuration described above, and may be configured with a data pre-read function. In FIG. 6, the cache memory of the first embodiment is also applied to an instruction cache and configured as a prefetch cache.

  The configuration shown in FIG. 6 further includes a prefetch buffer that is a prefetch data storage unit that caches data (instructions) expected to be supplied by the processor. Since a plurality of processors connected to the cache memory independently access different programs, the number of prefetch buffers corresponding to the number of processors is required. The address controller 601 of the prefetch cache detects the address of the next tag memory every time it crosses the entry boundary in order to detect the continuity of the address for prefetching or to perform the tag memory and the data memory in units of cache entries. Generate.

  The function of the prefetch buffer has heretofore been aimed at reducing power consumption by reducing the number of accesses to the tag memory and data memory. However, when applying the read-ahead function to a multi-thread processor, as with the read buffer 205 and write buffer 203 shown in FIG. The processing speed can be improved.

(Embodiment 2)
Next, Embodiment 2 of the present invention will be described.
The cache memory of the second embodiment has the configuration of FIG. 3 described in the first embodiment. For this reason, in the second embodiment, a part of the illustration and description of the configuration of the cache memory is omitted. In the cache memory according to the second embodiment, at least one of the data memory 207 and the tag memory 206 is a multi-port memory. When the data memory 207 is a multi-port memory, the multi-port memory requires a number of ports obtained by multiplying the number of processors by the number of ways. Further, when the tag memory 206 is a multi-port memory, this multi-port memory requires a number of ports corresponding to the number of processors.

The processor according to the second embodiment describes a configuration related to data writing (operation for writing data from the data memory 207 to the external memory 105) described in the second embodiment.
In the second embodiment, a so-called LRU (Least Recently Used algorithm) system is adopted for reading and writing operations. LRU is determined based on the state of a processor supply request for data by removing from cache memory data that has passed the longest time after being accessed by the processor among the cached data. According to such a system, data frequently requested by the processor can always be cached in the data memory 207, and the processing efficiency of the configuration employing the cache memory can be improved.

  There are various cache memory systems. In the second embodiment, the cache memory 109 is assumed to be a 2-way (way A, B) set-associative cache memory. In the set associative method, the hit ratio is improved by dividing the cache memory into a plurality of areas (way) and storing data of different addresses on the memory device in each way. This is possible.

In the cache memory of the second embodiment, the tag memory 206 manages the address of the data memory 207 as a plurality of ways. Then, the storage priority, which is the priority when the data stored in the data memory 207 is stored in the data storage unit, is assigned to each way, and the storage priority assigned to each way is set. For the data managed by the way, in the second embodiment, the access state that is the basis for determining the storage priority is the number of accesses in a predetermined period relatively close to the current time. According to such Embodiment 2,
First, the configuration of the tag memory 206 and the data memory 207 of the second embodiment will be described in detail. FIGS. 7A, 7 </ b> B, and 7 </ b> C are diagrams for explaining the structures of data stored in the tag memory 206 and the data memory 207. (A) shows the status flag managed by the tag memory 206.

The flags are stored in the tag memory 206 for each of the processors 0 to 3, and in the second embodiment, the status of the data is indicated by three flags: Valid flag, Dirty flag, and Used flag. The Valid flag is a flag indicating the validity of data. Dirty flag indicates that the cached data is communicated from the read value (dirty data), and Used flag indicates the priority of writing (writing priority).
In the second embodiment, the writing priority of each way is managed in a table (Used table) based on the Used flag. The Used table will be described with reference to FIG.

  FIG. 7B is a diagram for explaining the data structure of the tag memory 206. FIG. 7C is a diagram for explaining the data structure of the data memory 207. In the second embodiment adopting the two-way set associative method, each of the processor 0 to the processor 3 has two ways, and the tag memory 206 includes the data memory 207 in a total of eight ways (W0 to U7). Manage as.

Data (tag information) stored in the tag memory 206 is data for detecting data hits and miss hits, and stores 16 bits of the address of the accessed data. In addition, data read based on the tag information is cached in the data memory as 32-bit data of one word.
FIGS. 8A and 8B are diagrams for explaining LRU processing according to the second embodiment, and show used tables before and after data reading. In the second embodiment, the Used table is stored in the tag memory 206 and updated by the cache control unit 103.

  Data read by the processors 0 to 3 is cached in any of the ways U0 to U7 of the data memory 207. When another data needs to be cached after the cacheable number of data is cached in the ways U0 to U7, the cache control unit 103 selects one of the data currently cached in the ways U0 to U7. Write to the external memory 105. Then, other newly cached data is stored in the area where the written data has been cached.

In the second embodiment having a total of eight ways of cache memory, which of the data cached in the ways U0 to U7 is to be written is determined based on the state of the processor supply request to the way. It is assumed that data having the smallest number of accesses in the determined way is written out.
In the second embodiment, if the determination of the number of accesses is limited to a short time, it is possible to determine the way to which data is to be written depending on the presence or absence of the previous data access.

  The writing priority order is recorded in the Used table as the LRU order in the tables of FIGS. The LRU ranking referred to in the second embodiment is represented by a numerical value of 0 to 7, where 0 indicates the highest LRU ranking and 1 indicates the lowest LRU ranking. The data of the way assigned with the LRU order 7 is written to the external memory 105 in preference to the data of other ways at the next cache miss hit.

  FIG. 8A is a diagram for explaining the determination of the LRU order when the data requested by the processor mis-hits in the data memory 207. Since the data requested by the processor is not included in the data managed in the tag memory 206, the processor accesses the external memory 105 to read the data and caches it in the data memory 207. At this time, the cache control unit 103 refers to the Used table and refers to the LRU order of the ways U0 to U7.

  In the case of FIG. 8A, since the LRU rank of the way U6 is the lowest 7, the cache control unit 103 caches the way U6, sets the LRU rank of the cached way 6 to 0, and sets the other way. It is determined based on the state of the processor supply request for U LRU data. Data is written out by removing from the cache memory the one that has passed the longest time after being accessed by the processor. The latest data lowers the rank one by one.

  FIG. 8B is a diagram for explaining determination of the LRU order when the data requested by the processor hits data managed in the data memory 207. When the data requested by the processor hits the data of the way U4, the cache control unit 103 reads this data and supplies it to the processor. At this time, it is not necessary to write out data, but the LRU rank of the way U4 hit immediately before is updated to 0, and the LRU rank higher than the LRU rank (4) of the way U4 before hit is updated accordingly. .

  FIG. 9 is a flowchart for explaining cache control in the second embodiment described above. The cache control unit 103 receives a data access request from the processor and detects whether or not the requested data hits the tag memory 206 (S701). It is determined whether or not the data managed corresponding to the processor has been hit (S702), and if a hit is detected (S702: Yes), it is determined whether or not the access requires data writing. (S707). When data writing is requested (S707: Yes), data is written to the way (Way (n)) corresponding to the tag of the data memory (S710).

  If it is determined in step S707 that the access is not intended to write data (S707: No), the data cached in Way (n) is read and supplied to the accessed processor (S708). . Then, the cache control unit 103 updates the information indicating the access history of this data in the tag memory 206 according to the LRU (S709).

  On the other hand, if it is determined in step S702 that the data does not hit (S702: No), the cache control unit 103 detects the way (Way (n)) with the smallest access count, and further detects the way (Way (n)). In step S703, the data having the longest time elapsed since the processor accessed in step) is detected by the LRU algorithm. Then, it is determined whether the detected data is dirty data (S704). If the data is dirty data (S704: Yes), the data is written from the data memory 207 (S705), and the data is read from the external memory 105 to the written area (S706).

  FIG. 10 is a flowchart for explaining processing for changing the LRU order of the Used table in the processing shown in FIG. The cache control unit 103 inquires of the tag memory 206 about the data requested by the processor, and determines whether the requested data hits any way (S801). If it is determined that a hit has occurred (S801: Yes), the LRU rank of the hit way is updated to 0 (S806).

Next, the cache control unit 103 sets the variable s to 0 (S807), and sequentially updates the LRU order s of each way of the plurality of processors to s + 1 (S808). This update is performed until the updated LRU order reaches the LRU order just before the hit of the hit processor way (S809).
On the other hand, when the data requested by the processor k does not hit the cache (S801: No), the cache control unit 103 detects the way with the lowest LRU order. Then, the LRU rank of this way is updated to 0 (S802). At this time, the data read from the external memory 105 is cached in the way whose LRU rank is updated to 0 this time.

Then, the cache control unit 103 sets the variable s to 0 (S808), and sequentially updates the LRU order s of each way of the plurality of processors to s + 1 (S809). This update is performed for all ways.
According to the second embodiment described above, an LRU method suitable for a multiprocessor having a plurality of ways can be realized, and the cache hit rate can be increased. In addition, since the data memory and the tag memory are multi-port memories, a plurality of processors can simultaneously access the cache memory. For this reason, Embodiment 2 can improve the processing capability of the multiprocessor.

  It should be noted that the update of the LRU order when a plurality of processors simultaneously access the cache memory can be performed, for example, by assigning priorities to the processors in advance and updating them in the order according to the priorities. It is.

It is the figure which showed the multithread processor provided with the cache memory of Embodiment 1 and Embodiment 2 of this invention. It is a figure for demonstrating the operation | movement which changes the thread by which a some processor is performed according to a priority. FIG. 2 is a diagram showing the configuration of the cache memory shown in FIG. 1 in more detail. 3 is a flowchart for explaining a data read or write operation executed in the cache memory according to the first embodiment. FIG. 5 is a flowchart for explaining a data read operation executed in a conventional cache memory for comparison with FIG. 4. FIG. The cache memory of the first embodiment is also applied to an instruction cache and configured as a prefetch cache. In Embodiment 2 of this invention, it is a figure for demonstrating the structure of the data memorize | stored in a tag memory and a data memory. FIG. 10 is a diagram for explaining LRU processing according to the second embodiment. 10 is a flowchart for explaining cache control in the second embodiment. 10 is a flowchart for explaining LRU update in cache control in the second embodiment.

Explanation of symbols

101 multi-thread processor, 103 cache control unit, 105 external memory, 107 cache memory unit, 109 cache memory, 201 address control unit, 202 buffer management unit, 203 write buffer, 205 read buffer, 206 tag memory, 207 data memory 208 Hit detection unit

Claims (7)

A cache memory that caches at least a part of data read from a storage device by a plurality of processors and supplies at least a part of the cached data to the processor;
A data storage means cached data is stored by a plurality of said processors,
Address management means for collectively managing addresses of data stored in the data storage means for the entire data stored in the data storage means;
Hit detection means for comparing the address of the data requested to be supplied by the processor with the address managed by the address management means and detecting whether the data requested to be supplied is readable from the data storage means When,
Data supply means for supplying the detected data to the processor when the hit detection means detects that the data is readable;
A read buffer for temporarily storing only the data read from the data storage means until the data is output to the processor;
A write buffer for temporarily storing only data transmitted from the processor until the data is written to the data storage means;
The data stored in the read buffer is compared with the data stored in the write buffer, and the data stored in the read buffer and the data stored in the write buffer are compared. When a data mismatch that should be the same data is detected, the data stored in the read buffer is updated to the data written in the data storage means, or stored in the read buffer. The data stored in the read buffer and the write buffer are saved by invalidating the data once written and writing the data from the write buffer to the data storage means and then reading the written data. And a cache control unit that matches the received data. Yumemori. The data supply means, when it is detected by the hit detection means that the data can be read, supplies the detected data to the processor and includes data that is continuous with the data supplied to the processor the cache memory according to claim 1, characterized in that also supplied to the buffer to store the data of data read out from the storage means temporarily.   2. The cache memory according to claim 1, further comprising prefetch data storage means for caching data expected to be supplied by the processor. The data management unit manages the address of the data storage unit as a plurality of ways, and sets a storage priority that is a priority when the data stored in the data storage unit is stored in the data storage unit. subjected to each and to any one of claims 1-3 for the storage priority is assigned to each way and determining based on the state of access to data managed by the way The listed cache memory. It said data storage means, the cache memory according to claim 1, any one of 4, characterized in that at least one is a multi-port memory of the data management unit. A processor comprising a cache memory that caches at least part of data read from a storage device by a plurality of processors and supplies at least part of the cached data to the processor,
The cache memory is
A data storage means cached data is stored by a plurality of said processors,
Address management means for collectively managing addresses of data stored in the data storage means for the entire data stored in the data storage means;
Hit detection means for comparing the address of the data requested to be supplied by the processor with the address managed by the address management means and detecting whether the data requested to be supplied is readable from the data storage means When,
Data supply means for supplying the detected data to the processor when the hit detection means detects that the data is readable;
A read buffer for temporarily storing only the data read from the data storage means until the data is output to the processor;
A write buffer for temporarily storing only data transmitted from the processor until the data is written to the data storage means;
The data stored in the read buffer is compared with the data stored in the write buffer, and the data stored in the read buffer and the data stored in the write buffer are compared. When a data mismatch that should be the same data is detected, the data stored in the read buffer is updated to the data written in the data storage means, or stored in the read buffer. The data stored in the read buffer and the write buffer are saved by invalidating the data once written and writing the data from the write buffer to the data storage means and then reading the written data. A cache control unit that matches the stored data;
A processor comprising: The processor according to claim 6 , wherein each of the plurality of processors executes processing for each thread and can change a thread being executed during execution of the processing with another thread.

Images