Electrical computers and digital processing systems: memory – Storage accessing and control – Hierarchical memories
Reexamination Certificate
1997-11-12
2001-05-29
Bragdon, Reginald G. (Department: 2185)
Electrical computers and digital processing systems: memory
Storage accessing and control
Hierarchical memories
C711S146000
Reexamination Certificate
active
06240491
ABSTRACT:
BACKGROUND OF THE INVENTION
a) Field of the Invention
The invention relates to a process for managing exchanges between electronic memories in an information system, as well as to an information system, a memory and a recording medium which implement this process. The invention applies more specifically to multiprocessor information systems with memories that are logically shared and/or physically distributed.
b) Description of Related Art
An information system is constituted by a central subsystem which can communicate with one or more peripheral subsystems by means of input-output units. The central subsystem in a large system ordinarily includes several processors linked to a central memory and to the input-output units.
The function of each processor is the execution of the instructions of the programs contained in the central memory. These instructions and the data necessary for their execution can be accessed by the processor by using the addressing means of the central memory. However, taking into account the relatively long access times in the central memory, the processors are usually equipped with a cache memory which is much faster but whose contents are limited to a certain number of extracts from the contents of the central memory. For example, the central memory is constituted by memory elements, each of which is ordinarily made from an integrated dynamic memory circuit or DRAM (Dynamic Random Access Memory) with 16 megabits, for example, which presently takes about 60 nanoseconds to access a bit, while the cache memory is currently made from a static random access memory (SRAM) which requires on the order of 10 nanoseconds to access a bit. A cache memory is composed of a data memory and a mechanism for managing the addresses of data in the memory. The data memory of a cache memory is divided into memory blocks of the same predetermined size, each of which corresponds to a quantum of exchange with the central memory. A memory block is therefore a logical entity defined by a structure which essentially comprises an address part and a part reserved for the data. Each block is therefore identified by its address, whereas the specific contents of a memory block constitute a copy of it. In other words, each block is made up of one or more copies. A cache memory can be an associative type with a single level, better known as “direct mapped cache memory” or an associative type with several levels. In a cache memory, the mechanism for managing addresses is currently called a directory or “cache tags.”
A processor is composed of various processing circuits. An example of a description of these circuits adapted to a microprogrammed processor will be found in the Applicant's patent application EP-A-0434483 (corresponding to U.S. Pat. No. 5,408,623). In this document, the processors are connected by means of their cache memory to a bus which allows them to communicate with the central memory. Each processor and its cache memory resides together on the same printed circuit board which links several integrated circuit packages. Today, the ever-increasing scale of integration makes it possible to integrate each processor in a chip and to associate it with at least one part of the cache memory.
Current advanced information systems interpose other memory levels between the memory and the cache memory of the processor. For example, an intermediate cache memory is used as described in the above-mentioned patent. In this patent, the cache memories near the processors communicate with the central memory through an intermediate cache memory. The cache memories near the processors are therefore called private cache memories and they share the intermediate cache memory, which is therefore called a shared cache memory. A private cache memory is also composed of a data memory and an address management mechanism. More generally, a more or less complex hierarchy can exist between the memories which link a processor to a central memory. In this hierarchy, it is said that the level is higher when it is nearer to the processor. On the other hand, the central memory, which constitutes the lowest level, can also be shared and its elements can be distributed in the information system. The invention generally applies to the management of exchanges between two levels of any hierarchy of electronic memories in an information system.
SUMMARY OF THE INVENTION
The invention relates to the problem posed by the coherence of the management of these exchanges. The problem is linked to the fact that a copy of a memory block requested by a processor can be modified by the processor, thus no longer corresponding to the copy stored in a cache memory that is normally available to other processors.
The current solution consists of using one of two opposite strategies for managing exchanges, one of which is carried out in an update mode, the other in an invalidation mode. When a copy of a block has been modified by a first processor, this copy becomes the reference copy, and the invalidation consists of invalidating all the other copies of the block that have not been updated. Invalidation is a simple strategy, because it reduces the number of copies to manage, thus reducing traffic. The execution is also simple, since it is done by modifying a status bit in the directory. The invalidation is terminated when an acknowledgement message is received by the cache memory which possesses the reference copy. The acknowledgement can be implicit, in the construction of the machine for example, or it can take place after a predetermined period of time. However, when a second processor requests a copy of the block, its cache memory must search for the reference copy in the cache memory of the first processor. What follows is a reduction in the hit ratio of the second processor's access to its cache memory, and a slowing of its processing speed. Updating all the existing copies of a block offers the advantage of making them available to the other processors and thus avoids the necessity of the processor requesting a copy of this block having to search for the reference copy at the level of another processor. But updating necessitates sending more voluminous messages to all the memories which have a copy of the block and the acknowledgement that they all have the good copy. These messages obstruct traffic between the memories considerably, and thus slow down the mean access of a processor to a block copy that is not directly available. This disadvantage is aggravated by the fact that not all the updated copies are used.
In the prior art, the management mode is predetermined and it applies to the entire set of blocks contained in the memories, or to a subset such as a memory page. For example, the software can be designed so that it decides to use updating when the page is shared intimately among several processors, and invalidation when it is not shared or shared very little. Once the mode for a page has been chosen, the software uses it from the beginning to the end of the execution of the program on this page. This mode applies to all the blocks in the page, and it generally applies during the entire execution of a program. The two modes therefore represent static strategies which are easy to use. The mode chosen is used in the control circuit of each of the memories. The advantage of using static modes also resides in the physical simplicity of their means of implementation in the control circuit of each of the memories. However, the mode chosen can only be adapted to one phase of the program and to a limited number of blocks in one page. If the software developer wishes to adapt the mode to each phase of a program, this necessarily complicates his program considerably.
The invention solves the problem posed by the coherence of the management of the exchanges between the memories in an information system by dynamically applying to each block the management mode that is best adapted to the use that is made of it. The invention thus applies to each block and it consists of making a management choice for each block
Abily Jacques
Pairault Jean-Jacques
Perraudeau Jean
Bragdon Reginald G.
Bull S.A.
Kondracki Edward J.
Miles & Stockbridge P.C.
LandOfFree
Process and system for switching between an update and... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Process and system for switching between an update and..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Process and system for switching between an update and... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2510729