Electrical computers and digital processing systems: memory – Address formation – Address mapping
Reexamination Certificate
2001-07-13
2003-12-16
Padmanabhan, Mano (Department: 2188)
Electrical computers and digital processing systems: memory
Address formation
Address mapping
C711S202000, C711S203000, C711S207000, C345S566000, C345S568000
Reexamination Certificate
active
06665788
ABSTRACT:
BACKGROUND OF THE INVENTION
1. Field of the Invention
This invention is related to the field of computer systems and, more particularly, to address relocation/translation and address mapping in distributed memory computer systems.
2. Description of the Related Art
In distributed memory computer systems, system memory is divided into two or more portions, each of which is located within the system at a different point than the other portions. For example, the computer system may be arranged into nodes, some of which may be coupled to portions of the system memory. Similarly, systems may support the connection of peripheral devices (also referred to as input/output (I/O) devices) at different points in the system (e.g. to different nodes). Accordingly, an address map is typically included in nodes. The address map stores indications of address ranges and a destination identifier for each address range which indicates the destination within the system for a transaction having an address within that address range. Thus, the address map can be accessed to determine the destination of a transaction having a particular address.
Additionally, however, some nodes (or some transactions generated within a node) may require translation of a generated address to another address prior to accessing memory (and thus prior to accessing the address map). For example, the Graphics Aperture Relocation Table (GART) is used in personal computer systems to translate physical addresses within a memory region to different physical addresses. The GART can be used to allow a graphics device to address a large, contiguous address space while still allowing the operating system to freely map the pages within the contiguous address space (e.g. to non-contiguous addresses). Other types of translations exist as well (e.g. central processing units (CPUs) typically translate virtual addresses generated by executing program code).
Unfortunately, translating a first address to a second (physical) address and mapping that address to a destination identifier in the address map is a serial process. The latency of the procedure is approximately the sum of the latency of the translation and the latency of the address mapping. Additionally, in some cases the translation is either required or not required based on the source of the address (or the address itself). Thus, transactions which have no need to pass through the translation hardware may still be delayed by the latency of the translation hardware (or complicated bypass circuitry may be included to reduce the latency).
SUMMARY OF THE INVENTION
An address relocation cache includes a plurality of entries. Each of the plurality of entries is configured to store at least a portion of an input address, at least a portion of an output address to which the input address translates, and a destination identifier corresponding to the output address. An input address may be translated to the output address and the corresponding destination identifier may be obtained concurrently for input addresses which hit in the address relocation cache. The latency for performing the translation and the address mapping may be reduced. If an input address misses in the address relocation cache, a translation corresponding to the address may be located for storing into the address relocation cache. The output address indicated by the translation may be passed through the address map to obtain the destination identifier, and the destination identifier may be stored in the address relocation cache along with the output address.
In one embodiment, addresses are translated for only a portion of a memory range. In such an embodiment, the address map may be accessed with the input address to the address relocation cache in parallel with accessing the address relocation cache. If the input address is outside the memory region for which translation is performed, the input address and the destination identifier output from the address map in response to the input address may be used.
Broadly speaking, an apparatus is contemplated, comprising a memory. The memory includes a plurality of entries. Each of the plurality of entries is configured to store: (i) at least a portion of an input address and at least a portion of a corresponding output address to which the input address translates; and (ii) a destination identifier indicative of a destination corresponding to the output address.
Additionally, a method is contemplated. At least a portion of an input address is received in a memory. The memory outputs at least a portion of an output address. The output address is a translation of the input address. A first destination identifier is also output from the memory. The first destination identifier is indicative of a destination corresponding to the output address.
Furthermore, an apparatus is contemplated, comprising a table walk circuit, an address map coupled to the table walk circuit, and a memory coupled to the table walk circuit. The table walk circuit is configured to locate a translation of an input address to an output address. The table walk circuit is configured to provide the output address to the address map, which is configured to output a destination identifier in response thereto. The destination identifier is indicative of a destination corresponding to the output address. The memory is configured to store at least a portion of the input address, at least a portion of the output address, and the destination identifier.
REFERENCES:
patent: 4669043 (1987-05-01), Kaplinsky
patent: 4700291 (1987-10-01), Saito
patent: 5060137 (1991-10-01), Bryg et al.
patent: 5586283 (1996-12-01), Lopez-Aguado et al.
patent: 5623619 (1997-04-01), Witt
patent: 5666509 (1997-09-01), McCarthy et al.
patent: 5671444 (1997-09-01), Akkary et al.
patent: 5680566 (1997-10-01), Peng et al.
patent: 5680572 (1997-10-01), Akkary et al.
patent: 5696925 (1997-12-01), Koh
patent: 5751996 (1998-05-01), Glew et al.
patent: 5752274 (1998-05-01), Garibay, Jr. et al.
patent: 5761691 (1998-06-01), Witt
patent: 5895501 (1999-04-01), Smith
patent: 5913923 (1999-06-01), Dunlap et al.
patent: 5924125 (1999-07-01), Arya
patent: 5960463 (1999-09-01), Sharma et al.
patent: 6189074 (2001-02-01), Pedneau
patent: 6304944 (2001-10-01), Pedneau
patent: 2210479 (1989-06-01), None
Computer Architecture: A Quantitative Approach,Patter and Hennessy, Morgan Kaufmann Publisher, Inc., 1990, pp. 437-438.
Pentium Pro Family Developer's Manual, vol. 3: Operating System Writer's Guide,Intel, 1995, pp. 11-13 to 11-26.
AGP Memory Mapping: Accelerated Graphics Port Technology,Chapter 4, Intel, Apr. 6, 2001, 1 page.
Accelerated Graphics Port Interface Specification,Intel, May 4, 1998, pp. 23-29.
Advanced Micro Devices , Inc.
Merkel Lawrence J.
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Namazi Mehdi
Padmanabhan Mano
LandOfFree
Reducing latency for a relocation cache lookup and address... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Reducing latency for a relocation cache lookup and address..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Reducing latency for a relocation cache lookup and address... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3167702