Electrical computers and digital processing systems: memory – Address formation – Hashing
Patent
1995-11-22
1999-01-12
Swann, Tod R.
Electrical computers and digital processing systems: memory
Address formation
Hashing
39520049, 711144, G06F 1300, G06F 1516
Patent
active
058601538
ABSTRACT:
A bit map is maintained by a provider object of a name server to keep track of names cached by a cache object of the client. The bit map is indexed by performing a hash of the name. When a name is looked up by the server on behalf of a client, the server hashes the name, and sets the bit in the bit map indexed by the result of the hash modulo the size of the bit map. The result of the hash is returned to the client and is stored with the entry in the cache. A bit "set" in the bit map indicates that the client caches at least one name that hashes into the bit. When the server invalidates a name, a hash of the name to be invalidated is used to find the corresponding bit in the bit mask. If the bit is set, the server sends an invalidation request to the client. The invalidation request includes the result of the hash, and the size of the provider's bit map. The client invalidates all entries that hash into the specified bit in the bitmap on the server. Alternatively, the invalidation request also includes the name to be invalidated and the client invalidates only the entry that matches the name.
REFERENCES:
patent: 4887204 (1989-12-01), Johnson et al.
patent: 5151989 (1992-09-01), Johnson et al.
patent: 5265245 (1993-11-01), Nordstrom et al.
patent: 5434914 (1995-07-01), Fraser
patent: 5495608 (1996-02-01), Antoshenkov
patent: 5537574 (1996-07-01), Elko et al.
patent: 5581704 (1996-12-01), Barbara et al.
patent: 5604882 (1997-02-01), Hoover et al.
Wirth, Niklaus. Algorithms +Data Structures =Programs. pp. 264-274, 1976.
Chaiken, D. et al. "Directory-Based Cache Coherence in Large-Scale Multiprocessors", Computer, IEEE, pp. 49-58, Jun. 1990.
Su, Ching-Long et al. "A Study of Cache Hashing Functions for Symbolic Applications in Micro-Parallel Processors", Proceedings of the 1994 Internation Conference on Parallel and Distributed Systems, pp. 530-535, Jun. 1994.
Bernabeu-Auban Jose M.
Khalidi Yousef A.
Matena Vladimir
Shirriff Kenneth W.
Thadani Moti N.
King , Jr. Conley B.
Sun Microsystems Inc.
Swann Tod R.
LandOfFree
Memory efficient directory coherency maintenance does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Memory efficient directory coherency maintenance, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Memory efficient directory coherency maintenance will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-1525517