Address translation

Details Address translation Address translation

2001-08-08

2004-10-19

Padmanabhan, Mano (Department: 2188)

Electrical computers and digital processing systems: memory

Address formation

Address mapping

C711S118000, C711S202000, C711S206000

Reexamination Certificate

active

06807618

ABSTRACT:

BACKGROUND
A wide variety of devices store computer data. These devices vary greatly in their storage capacities and speeds. For example, a disk typically stores much more data than a memory chip. A memory chip, on the other hand, can often provide access to data much faster than a disk.
Many systems combine different types of storage devices to provide both large storage capacity and fast access to data. For example, a common technique for speeding data access involves caching (pronounced “cashing”) data in high-speed memory. For instance, a data cache may store a copy of some data also stored by a slower storage device. When a request for the cached data arrives, a system can quickly respond to the request by accessing the cached copy instead of waiting for data retrieval by the slower storage device.
SUMMARY
In general, in one aspect, the description includes a method of data storage address translation. The method includes receiving a first address in a first address space, traversing a trie based on the first address, and determining a second address based on the traversal.
Embodiments may include one or more of the following features. The first address may have a different (e.g., larger) address space than the second address. The trie may include at least one leaf identifying an address in the second address space. The second address may be an address of a cache memory. The first address may be an address of permanent data storage. The second address associated with the first address may dynamically change, for example, based on changing cache contents.
The method may further include determining whether the cache stores information identified by the first address. Traversing the trie may include performing an operation on the first address and traversing the trie using the operation results.
The trie may be implemented as a multi-dimensional array where an index of a dimension of the array corresponds to different trie branches. Traversing such a trie may include repeatedly indexing into the array using a portion of the first address.
In general, in another aspect, the description includes a data storage system. The system includes a storage area having a first address space, a cache having a second address space, and instructions for causing a processor to receive a first address in the first address space, traverse a trie based on the first address, and determine a second address in the second address space based on the traversal.
In general, in another aspect, the description includes a computer program product, disposed on a computer readable medium, for data storage address translation. The computer program includes instructions for causing a processor to receive a first address within a first address space, traverse a trie based on the first address, and determine a second address based on the traversal.
In general, in another aspect, the description includes a method of data storage address translation at a system having a storage area composed of different physical devices, a shared cache for caching blocks of data in the storage area, and connections to different host processors. The method includes receiving a storage area address within a storage area address space based on a request received from one of the host processors, traversing a trie based on the storage area address, the traversing identifying a trie leaf identifying a cache address in a cache address space, and changing the cache address associated with the trie leaf based on an alteration of cache contents.
In general, in another aspect, the description includes a memory for storing data for access by an application program being executed on a data processing system. The memory includes a data structure that includes information corresponding to a trie having leaves identifying different respective cache addresses.
Advantages will become apparent in view of the following description, including the figures and the claims.


REFERENCES:
patent: 6151662 (2000-11-01), Christie et al.
patent: 6499032 (2002-12-01), Tikkanen et al.
patent: 6505206 (2003-01-01), Tikkanen et al.
patent: 6549210 (2003-04-01), Van Hook et al.
patent: 2002/0046291 (2002-04-01), O'Callaghan et al.
patent: 2002/0184231 (2002-12-01), Baskins et al.
“What's Going on Inside the Box? ISV Access to Symmetrix Performance and Utilization Metrics”, Jan. 2000, EMC Corporation.
“Growing an Enterprise Application Environment: A Guide to Achieving Terabyte Scalability”, Aug. 1997.
“Symmetrix 8000 Enterprise Storage System: Product Description Guide”, 2000, EMC Corporation.
Shaffer, “Designing Very Large Content Addressable Memories”, Dec. 5, 1992.
Baeza-Yates, “Fast Text Searching for Regular Expressions or Automaton Searching on Tries”, Nov. 1996.
Morrison, “PATRICIA—Practical Algorithm to Retrieve Information Coded in Alphanumeric”, Oct. 1968.
Doeringer, “Routing on Longest-Matching Prefixes”, 1996.

Affiliated with

Also associated with

Rating

Address translation does not yet have a rating. At this time, there are no reviews or comments for this patent.

If you have personal experience with Address translation, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Address translation will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFUS-PAI-O-3328096