Data processing systems are known that are equipped with a hierarchy of memories, so that the most extensive possible memory space will be available, yet not at prohibitive overall cost, particularly by providing levels in the hierarchy in which the fastest memories with costlier technology are of reduced size, and by increasing the size of the memories in contiguous levels in the hierarchy in inverse proportion to their technological cost, or more simply by adopting, on the highest levels in the hierarchy, memory sizes that are just sufficient for the most useful information to be obtained with an apparent average access time on the order of the cycle time of the fastest part of the hierarchy, for a total capacity of the hierarchy equal to the capacity of the lowest level of memory, which generally has the least costly technology but the largest size.
In conventional terminology, it will be recalled that each hierarchy level is divided into memories which in turn are divided into blocks containing information identified by addresses. The addresses on a lowest level in the hierarchy correspond to the locations of the information, while the copies of these pieces of information that are present in the blocks of the other levels of the hierarchy are associated with the same address but are disposed at any arbitrary location determined by the management processor of the memory in question.
This hierarchy of memories poses a problem with managing the coherence of the copies when copies of the same initial piece of information from a block on a lower level can exist and be modified in different blocks on a higher level in the hierarchy.
In order to assure coherence in the management of the information, it is customary, when a piece of information is modified in one block of a higher level, to proceed to either an update or an invalidation of the information contained in the corresponding blocks of a higher level in the hierarchy. The advantage of updating is that it avoids having misses occur during inquiries that are made on this information in the memories that have not generated the modification of information. However, this updating has the drawback of being costly in terms of machine time, since it must be executed individually with each modification and therefore involves a very high rate of messages in the links between the memories. Conversely, invalidation is less costly in terms of machine time since it can be executed just once for several successive modifications of the information, but it reduces the hit ratio of the inquiries in the memories where the information has been invalidated.
In current data processing systems the processing protocol during updating or invalidation is predetermined either by an instruction on the level of the general management system in the hierarchy of memories or by an instruction of the application program. It now turns out that at times it would be preferable to adapt the processing protocol to the requirements so as to optimize the rate of the messages in the links between the levels of memories in the hierarchy.
USPTO Backgrounds
USPTO Backgrounds