JPH0661065B2 - Cache memory control method - Google Patents

Description

The present invention relates to a cache memory control system in a multiprocessor system sharing a main memory.

[Prior Art] FIG. 4 shows, for example, "COMPUTER DESIGN",
Glen G. Langdon, Jr. By (COMPUTEACH P
RESS INC. 1982) is a block diagram showing the configuration of the cache memory control system shown in FIG. In the figure, 1 is a main memory device for storing data necessary for data processing, 2 is a central processing unit (CPU) which shares the main memory device 1 and performs arithmetic / control for data processing, and 3 is a central processing unit 2. A cache memory for speeding up data transfer between the main memory devices 1, 4 is a read data path, 5 is a main memory read path, 6 is a write data path, 7 is a load through path, and 8 is a store through path.

Next, the operation will be described. The cache memory 3 stores the data when the central processing unit 2 accesses the data from the main memory 1. Generally, it is said that once used data is highly likely to be used again, there are many cases where the data can be accessed from the cache memory 3 when accessing the data thereafter. Further, since the cache memory 3 can be accessed much faster than the main memory 1, the cache memory 3 is
If the data to be accessed is in the cache memory 3, the data can be accessed at a considerably high speed. When the data is not in the cache memory 3, the main memory 1
Since it needs to access the data to, it will be slow.

When the central processing unit 2 accesses data, first,
A request for necessary data is issued, and it is tested whether the requested access data exists in the cache memory 3. If there is, the data in the cache memory 3 is read out and taken out from the data path 4 as it is. If there is no necessary data in the cache memory 3, the data is read once from the main memory 1 into the cache memory 3 by the main memory read path 5, and then the cache memory 3 is read. Alternatively, the data is read from the main memory read path 5 to the cache memory 3 and simultaneously to the central processing unit 2 via the load through path 7. The same test is performed during the write operation, and the data is written to the cache memory 3 through the data write data path 6 or the main memory 1 through the store through path 8.

Therefore, it is desirable to store the most frequently used data in the cache memory 3 having a considerably smaller capacity than the main memory 1. Normal cache memory 3
The data most recently used in the cache memory 3 is long, and the data in the cache memory 3 is replaced so that the oldest used data is returned to the main memory 1.

Further, as shown in FIG. 5, in a multiprocessor system in which a plurality of central processing units each having such a cache memory are coupled and the main storage device 1 is shared,
There is a more complicated problem. In the multiprocessor system, since the same main storage device 1 is shared, the cache memories 3a to 3d which are copies of the main storage device 1,
There may be a copy of the data in the same main storage device 1 corresponding to a plurality of central processing units 2a to 2d. if,
When one of the central processing units rewrites the contents of its cache memory, the copy of the data before update of the cache memories 3a to 3d in all the central processing units 2a to 2d is no longer correct and should not be used by mistake. It should be invalid. This is called invalidation of cache memory. This invalidation of the cache memory usually occurs each time writing is performed by the central processing unit.

FIG. 6 shows a data store operation (write operation) in one central processing unit 2 in the multiprocessor system. In this flowchart, the main storage device 1 is stored even when a cache hit occurs at the time of store.
It is described assuming a store-through method for writing to. In FIG. 6, in step S1, it is determined whether or not there is data in a certain cache memory, and if there is data, the process proceeds to step S3 to store the data in the cache memory 3, and if there is no data, the process proceeds to step S2 and the main storage device. Store the data in 1. In step S4, it is determined whether or not the target data is in the cache memory of another central processing unit. If there is the target data, the process proceeds to step S6 to invalidate the contents of the cache memory of the other central processing unit. If there is not, the process proceeds to step S5 and no process is performed.

As shown here, for the data store, even in the case of a cache hit or a cache miss, the contents of the cache memory of another (other system) central processing unit are tested and the target data is If it is also in the central processing unit, its cache memory must be invalidated.

In a recent multiprocessor system, unlike parallel processing which is conventionally performed to allocate a plurality of jobs to a plurality of central processing units to improve the throughput as a system, a plurality of central processing units are used. When the device executes one job, parallel processing may be performed for the purpose of improving the response of the job. In this case, the data of the same block in the main storage device may be divided into a plurality of central processing units, and the data of this same block is frequently accessed by another central processing unit.

For example, as shown in FIG. 2, when a loop in a program is to be processed in parallel by a plurality of central processing units, so-called spatial parallelism is used, and the loop is divided for each iteration. Is often processed. In the second example, the statement DOALL indicates that parallel processing is performed, it is assumed that there are four central processing units, and it is shown that each of the four expressions in this loop is assigned to one central processing unit. ing. In other words, the loop is divided into four, and the central processing unit 2a performs the first, fifth, ninth, ... The second, the sixth, the tenth, ..., Which is the process of the formula, the central processing unit 2c is the third, the seventh, the eleventh, which is the process of the third formula. The central processing unit 2d is responsible for the fourth, eighth, twelfth, and so on, which is the processing of the fourth equation. This means that data spatially concentrated, for example, the elements of the array A are intentionally divided into a plurality of central processing units, and therefore the cache memories 3a of the plurality of central processing units 2a to 2d.
This results in the presence of the same block of data for the elements of array A in ~ 3d. The plurality of cache memories 3a to 3
In order to maintain the validity of the data in d, the address of the written block is sent to the central processing unit of other system every time the writing of the data to the block is performed by each central processing unit, and the cache is cached. It is necessary to invalidate the data in the corresponding cache memory block of the central processing unit that has the block of that address in memory. When the central processing unit that has the invalidated block wants to use the block, it needs to access the block, a part of which has been changed, from the main memory 1 again. In the example of FIG. 2, this situation occurs every time one arithmetic processing is performed in each of the central processing units 2a to 2d. At each time, invalidation of data in the cache memories 3a to 3d in each of the central processing units 2a to 2d and data transfer between the cache memories 3a to 3d and the main storage device 1 are performed, so that the multiprocessor Significantly affects system performance.

[Problems to be Solved by the Invention] Since the conventional cache memory control system operates as described above, in a multiprocessor system which executes parallel processing, the cache memory is written to the cache memory at each write processing of each central processing unit. A content invalidation request is issued, and each time data is transferred between the cache memory and the main memory, there is a problem that processing performance is significantly reduced.

The present invention has been made to solve the above problems, and the central processing unit that has performed the write operation performs processing without invalidating the cache memory corresponding to all the other central processing units. It is an object of the present invention to obtain a cache memory control method capable of improving performance.

[Means for Solving the Problems] In the cache memory control system according to the present invention, a central processing unit that performs a write operation among a plurality of central processing units that share a main memory is the same for all other central processing units. The write data is transferred to the cache memory, and the write data is written in the cache memory corresponding to the central processing unit in which the parallel data processing is performed by the recognition means.

[Operation] In the cache memory control system of the present invention, the central processing unit that performs the write operation sends the address where the data has been written to all the other central processing units that share the main storage device, and all the other operations. Instead of disabling the cache memory corresponding to this central processing unit, the write data is transferred to all the other central processing units together with the address of the written data, and the transferred write data is parallelized. Write to the cache memory corresponding to the central processing unit indicated to perform data processing.

[Embodiment of the Invention] FIG. 1 is a block diagram showing a configuration of a multiprocessor system adopting a cache memory control system according to an embodiment of the present invention. In the figure, 1 is a main storage device that stores data required for data processing, 2a to 2d are a plurality of central processing units (CPUs) that share the main storage device 1 and perform arithmetic / control related to data processing, and 3a to 3d. A plurality of cache memories 10 provided respectively corresponding to the central processing units 2a to 2d for speeding up data transfer between the central processing units 2a to 2d and the main storage unit 1 are mainly constituted by the central processing units 2a to 2d. A global memory path for accessing the storage device 1, 11 is each cache memory 3a to 3d
And a data path for broadcasting write data to all the central processing units 2a to 2d at the time of a write operation and a function of a transfer means for directly transferring data between them, 9a to 9d
For recognizing that the designated central processing unit is one of the plurality of central processing units 2a to 2d when parallel data processing is being executed by the designated two or more central processing units. It is a parallel processing mode flag as a recognition means.

Next, the operation will be described.

FIG. 1 shows a multiprocessor system having four central processing units 2a to 2d. When performing parallel processing in this multiprocessor system, there is a method of dividing the loop part of the program into the simplest and most commonly performed method. Assuming automatic parallelization by a compiler or the like, the division is often such a simple thing because of the difficulty of parallelization. For example, as shown in FIG. 2, divide a loop with a large number of iterations into four,
It is transformed as shown by the DOALL statement. The statement DOALL indicates that parallel processing is performed, and 4 in this loop
It is shown that each of the equations is assigned to one central processing unit. In other words, the loop is divided into four, and the central processing unit 2a performs the first, fifth, ninth, ... The second, the sixth, the tenth, ..., Which is the process of the formula, the central processing unit 2c is the third, the seventh, the eleventh, which is the process of the third formula. The central processing unit 2d is responsible for the fourth, eighth, twelfth, and so on, which is the processing of the fourth equation.

FIG. 3 shows data in the cache memories 3a to 3d of the respective central processing units 2a to 2d at this time. Assuming that the arrays A1 to A8 are in the same block in the main memory 1, this block has four central processing units 2a.
~ 2d read out to all four central processing units 2a
All ~ 2d write to this block. In this case, the central processing unit 2a has the array A1, the central processing unit 2b has the array A2 as its adjacent element, the central processing unit 2c has the array A3 of its adjacent elements, and the central processing unit 2d has the array. Data will be written to the same block in the array A4 of adjacent elements of A3.
The flow of this operation is continued thereafter, and data is always written to the adjacent element of the element to which the adjacent central processing unit has written. At this time, the central processing units 2a to 2d
All the parallel processing mode flags 9a to 9d are turned on, indicating that all the central processing units 2a to 2d are in the parallel processing mode. According to this, during a write operation, the address where the data was written is sent to the central processing unit of the other system, and instead of invalidating the cache memory of the central processing unit of the other system, the writing is performed to the central processing unit of the other system. The write data together with the address of the written data is broadcast from the data path 11 to all the central processing units. As a result, the parallel processing mode flag 9a
9d are turned on, and each central processing unit 2a-2 holds a block containing written data.
By fetching the write data that has been sent and actually writing the data into the cache memories 3a to 3d, the contents of the cache memories 3a to 3d can be maintained valid and need not be invalidated.

In the above embodiments, the multiprocessor system is described as operating in the parallel processing mode. However, the system is expected to have some effect even when the normal mode is executed. Further, in the embodiment, instead of invalidating the cache memory when storing data only during the parallel processing operation, the store data (write data) is broadcast to all the central processing units, and the parallel processing mode flag is turned on. I was supposed to write to the cache memory. This is because, during normal parallel processing operation, the loop is often divided as described above, and it is very likely that a plurality of central processing units share the same block of data. . However, in an actual job, there are cases where the user explicitly declares to use a plurality of central processing units in the program and causes the processing to be performed. Even in this case, since the data may be shared by the plurality of central processing units, it is necessary to recognize that the user accesses the same block of data among the plurality of central processing units and then use the central processing performed by software. Even if the device is designated and the designated central processing unit broadcasts the store data without invalidating the cache, the intended effect can be obtained.

As described above, according to the present invention, the central processing unit that performs the write operation among the plurality of central processing units sharing the main storage device writes the write data to all the other central processing units. The write data is transferred to the cache memory corresponding to the central processing unit in which the parallel data processing is shown to be executed by the recognition means, so that the cache memory is invalidated for each write operation. Write data is written to the cache memory corresponding to the recognized central processing unit, which allows the data in the cache memory to remain valid and reduces the exchange of data between the cache memory and main memory. Therefore, the effect that the processing performance is improved can be obtained.

[Brief description of drawings]

FIG. 1 is a block diagram showing the configuration of a multiprocessor system adopting a cache memory control system according to an embodiment of the present invention, and FIG. 2 is a diagram showing an example of a typical program to be processed in parallel in this embodiment. 3 shows how the data is divided in the cache memory of each central processing unit when the program is executed in this embodiment, and FIG. 4 shows the configuration of the conventional cache memory control system. FIG. 5 is a block diagram showing the configuration of a multiprocessor system adopting a conventional cache memory control method, and FIG. 6 is a flowchart showing the operation of the cache memory in this conventional example. 1 ... Main storage device, 2a-2d ... Central processing unit, 3a
.. 3d ... Cache memory, 11 ... Data path (transfer means), 9a to 9d ... Parallel processing mode flag (recognition means).

Claims (1)

[Claims] 1. A main storage device for storing data required for data processing, a plurality of central processing units that share the main storage unit and perform arithmetic operations and control relating to data processing, and each of the plurality of central processing units is provided. And a plurality of cache memories provided corresponding to each of the plurality of central processing units, and a write operation is performed among the plurality of central processing units. A cache characterized in that the executing central processing unit transfers write data to all the other central processing units and writes the write data in the cache memory corresponding to the central processing unit indicated by the recognizing means. Memory control method.