Dynamic multi-level cache manager

Details Dynamic multi-level cache manager Dynamic multi-level cache manager

2002-06-19

2004-11-02

Ellis, Kevin L. (Department: 2188)

Electrical computers and digital processing systems: multicomput

Remote data accessing

Reexamination Certificate

active

06813633

ABSTRACT:

FIELD OF THE INVENTION
The present invention relates to a multiprocessor caching system. In particular, the present invention relates to a method and apparatus for caching dynamically-changing data in a multiprocessor environment.
BACKGROUND OF THE INVENTION
Multiprocessor computing systems typically use a caching server disposed between the processors and a common file server to improve system performance. For instance, to improve access by client terminals to HTML servers in a World Wide Web environment, an enterprise uses a web server for caching HMTL data requested by all of the enterprise's client terminals. In addition, each client terminal is equipped with a dedicated software cache which caches the HTML data requested by the client terminal.
This approach increases system performance since a subsequent request by a client terminal for static HTML data previously requested from an HTML server can be satisfied locally by accessing either the terminal's dedicated cache or the web server cache, without having to request the data again from the HTML server. However, the conventional caching server cannot offer improved system performance for client queries based on dynamically-changing data, since the caching server cannot determine if the data upon which a previous query was based has changed. Instead, the conventional web caching server accesses web search engines to satisfy client data queries based on dynamically changing data. Still, web search engines typically satisfy search queries by maintaining and periodically updating a database of web server content. Consequently, web search engines frequently return search results which consists of pointers to data which has long since expired.
Attempts have been made to improve the performance of multi-processor computing systems in respect of dynamically-changing data. For instance, Gannon (U.S. Pat. No. 5,265,232) discloses a multiple processor caching system which includes a storage controller, a cross-invalidate directory stored in the storage controller, and a number of processors in communication with the storage controller. Each processor has its own private L
1
store-through cache and associated L
1
cache directory. The system also includes a shared L
2
cache and/or a main memory.
The cross-invalidate directory has entries each associated with a respective data unit of the L
2
cache and main memory. Each cross-invalidate directory entry includes a processor identifier field identifying which processor owns the associated data, and indicates whether the ownership is exclusive or public. Exclusive ownership means that only one of the processors has ownership over the data unit (ie. the identified processor can write to the data unit). Public ownership means that all of the processors have ownership over the data unit (ie. all processors can read from but not write to the data unit).
If one of the processors requests a change in ownership over a data unit (eg. to overwrite the data unit), the request identifies the data unit to be changed, the requesting processor and the ownership type requested. The storage controller queries the directory for the processors which have ownership over the data unit, and transmits a request to the identified processors to terminate their respective ownerships over the data unit, both in the L
1
and the L
2
cache. Each processor which receives the request updates their respective L
1
cache directory to indicate that the data unit is no longer available in their respective L
1
cache, and then signals the storage controller that the processor has terminated its ownership over the data unit. Once all ownership over the data unit has terminated, the storage controller updates the cross-invalidate directory to reflect the new ownership of the data unit, and then modifies the data unit in the L
2
cache and main memory as requested by the requesting processor. The other processors must then access the L
2
cache or main memory to obtain a copy of the modified data unit (copying same into their respective L
1
cache).
Mackenthun (U.S. Pat. No. 6,122,711) discloses a dual cluster multi-processing system which includes a pair of multi-processing clusters interconnected with a main memory and a system controller over a local area network. Each cluster includes a number of processors each having a dedicated store-through cache. Each cluster also includes a storage controller connected to the processors. The storage controller includes a second level cache, and a database of tags. The tags include copies of the data in the first level caches of the processors which are connected to the respective storage controller. The tags also include flags which identify the status of each cache clement (valid, modified), and the processor which “owns” the cache element. If a processor intends to write to its second level cache, the processor must be designated as the owner of the cache element. Only one processor can be designated as the owner of a cache element, although the owner can change.
If a processor (eg. of the first cluster) requests access to a data element, the first storage controller checks its tag database to determine if the element is cached in the second level cache and, if so, if the data in the cached element is valid. If the cached element is present and valid, the first storage controller retrieves the cached element for the processor from the second level cache.
However, if the cached element is not present, or is not valid, the second storage controller checks its tag database to determine if it has a valid cached copy of the data element. If the second storage controller does not have a cached copy of the data element, the data is retrieved from the main memory and stored in the second level cache of the first storage controller. The first storage controller then updates its tag database to indicate that the first storage controller is the owner of the cache element, and provides the processor with the cached element.
On the other hand, if the second storage controller does have a valid cached copy of the data element, the second storage controller transmits the cached element to the first storage controller, and then invalidates its own copy of the cached element by updating the appropriate flag in its tag database. The first storage controller then updates its tag database to indicate that the first storage controller is the owner of the cache element, and provides the processor with the cached element.
If the processor of the first cluster subsequently modifies the cached element, the first storage controller keeps a copy of the modified cached element in its second level cache, and then updates its tag database to indicate that the cached data is different from the data stored in the main memory. If an operator subsequently decides to remove one of the clusters from the system, the system controller retrieves from the first storage controller all second level cache elements which are owned by the first storage controller and whose corresponding tag indicates that the cached data is different from the data stored in the main memory. The system controller then stores the retrieved data in the main memory.
Although both Gannon and Mackenthun are able to offer some improvement in system performance in respect of dynamically-changing data, the performance improvement is limited by the need for a centralized storage controller which controls access by the processors to the shared data. In both solutions, a write request must be acted upon by the storage controller before access to the shared data is granted.
Further, both solutions are unable to provide any improvement in system performance for network clients making similar data queries based on the dynamically-changing data, since the caches can only mirror the contents of the main system memory. These limitations render both solutions inadequate for widely-distributed multi-processing environments, such as World Wide Web computing.
Accordingly, there remains a need for a computing solution which can enhance system per

Affiliated with

Also associated with

Rating

Dynamic multi-level cache manager does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Dynamic multi-level cache manager, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Dynamic multi-level cache manager will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3318424