The Commons

Back to Results

Patent Title: Method and system for reduced address tags storage within a directory having a tree-like data structure

Assignee: IBM
Patent Number: US5684976
Issue Date: 11-04-1997
Application Number:
File Date:09-25-1996


Abstract: An efficient method and system within a data processing system for storing address tags are disclosed, which include a tag directory having a plurality of congruence classes, wherein each congruence class is arranged as a tree-like data structure. A portion of an address tag common to a plurality of address tags is stored in an entry within a node at a first level of a tree-like data structure corresponding to a congruence class of the directory. Portions of the plurality of address tags are stored in a node at a subsequent level of the tree-like data structure, such that all of the plurality of address tags share in common the portion stored in the entry within the node at the first level. Since a portion common to a plurality of address tags is stored only once, the memory space required to store the plurality of address tags is reduced.

Notes:

Link to USPTO

IBM Pledge dated 1/11/2005