Accelerated graphics port multiple entry gart cache allocation system and method

A computer system having a core logic chipset that functions as a bridge between an Accelerated Graphics Port ("AGP") bus device such as a graphics controller, and a host processor and computer system memory wherein a Graphics Address Remapping Table ("GART table") is used by the core logic chipset to remap virtual memory addresses used by the AGP graphics controller into physical memory addresses that reside in the computer system memory The GART table enables the AGP graphics controller to work in contiguous virtual memory address space, but actually use non-contiguous blocks or pages of physical system memory to store textures, command lists and the like. The GART table is made up of a plurality of entries, each entry comprising an address pointer to a base address of a page of graphics data in memory. The core logic chipset may cache a subset of the most recently used GART table entries to increase AGP performance when performing the address translation. When a GART table entry is not found in the cache, a memory access is required to obtained the needed GART table entry. There are two GART table entries in each quadword returned in toggle mode of the cacheline of memory information returned from the memory read access. At least one quadword (two GART table entries) are stored in the cache each time a memory access is required because of a cache miss.

BACKGROUND OF THE INVENTION 
1. Field of the Invention 
The present invention relates to computer systems using a bus bridge(s) to 
interface a central processor(s), video graphics processor(s), random 
access memory and input-output peripherals together, and more 
particularly, in utilizing a graphics address remapping table (GART table) 
for remapping non-contiguous physical memory pages into contiguous 
accelerated graphics port (AGP) device addresses, wherein selected entries 
of the GART table are cached to speed up the remapping process such that 
when a GART table entry is retrieved from the computer system random 
access memory a plurality of GART table entries are retrieved using the 
same memory access. 
2. Description of the Related Technology 
Use of computers, especially personal computers, in business and at home is 
becoming more and more pervasive because the computer has become an 
integral tool of most information workers who work in the fields of 
accounting, law, engineering, insurance, services, sales and the like. 
Rapid technological improvements in the field of computers have opened up 
many new applications heretofore unavailable or too expensive for the use 
of older technology mainframe computers. These personal computers may be 
stand-alone workstations (high end individual personal computers), 
desk-top personal computers, portable lap-top computers and the like, or 
they may be linked together in a network by a "network server" which is 
also a personal computer which may have a few additional features specific 
to its purpose in the network. The network server may be used to store 
massive amounts of data, and may facilitate interaction of the individual 
workstations connected to the network for electronic mail ("E-mail"), 
document databases, video teleconferencing, white boarding, integrated 
enterprise calendar, virtual engineering design and the like. Multiple 
network servers may also be interconnected by local area networks ("LAN") 
and wide area networks ("WAN"). 
A significant part of the ever increasing popularity of the personal 
computer, besides its low cost relative to just a few years ago, is its 
ability to run sophisticated programs and perform many useful and new 
tasks. Personal computers today may be easily upgraded with new peripheral 
devices for added flexibility and enhanced performance. A major advance in 
the performance of personal computers (both workstation and network 
servers) has been the implementation of sophisticated peripheral devices 
such as video graphics adapters, local area network interfaces, SCSI bus 
adapters, full motion video, redundant error checking and correcting disk 
arrays, and the like. These sophisticated peripheral devices are capable 
of data transfer rates approaching the native speed of the computer system 
microprocessor central processing unit ("CPU"). The peripheral devices' 
data transfer speeds are achieved by connecting the peripheral devices to 
the microprocessor(s) and associated system random access memory through 
high speed expansion local buses. Most notably, a high speed expansion 
local bus standard has emerged that is microprocessor independent and has 
been embraced by a significant number of peripheral hardware manufacturers 
and software programmers. This high speed expansion bus standard is called 
the "Peripheral Component Interconnect" or "PCI." A more complete 
definition of the PCI local bus may be found in the PCI Local Bus 
Specification, revision 2.1; PCI/PCI Bridge Specification, revision 1.0; 
PCI System Design Guide, revision 1.0; PCI BIOS Specification, revision 
2.1, and Engineering Change Notice ("ECN") entitled "Addition of `New 
Capabilities` Structure," dated May 20, 1996, the disclosures of which are 
hereby incorporated by reference. These PCI specifications and ECN are 
available from the PCI Special Interest Group, P.O. Box 14070, Portland, 
Oreg. 97214. 
A computer system has a plurality of information buses (used for 
transferring instructions, data and address) such as a host bus, a memory 
bus, at least one high speed expansion local bus such as the PCI bus, and 
other peripheral buses such as the Small Computer System Interface (SCSI), 
Extension to Industry Standard Architecture (EISA), and Industry Standard 
Architecture (ISA). The microprocessor(s) of the computer system 
communicates with main memory and with the peripherals that make up the 
computer system over these various buses. The microprocessor(s) 
communicates to the main memory over a host bus to memory bus bridge. The 
peripherals, depending on their data transfer speed requirements, are 
connected to the various buses which are connected to the microprocessor 
host bus through bus bridges that detect required actions, arbitrate, and 
translate both data and addresses between the various buses. 
Computer systems typically utilize at least one "cache memory" for improved 
performance. In common usage, the term "cache" refers to a hiding place. 
The name "cache memory" is an appropriate term for this high speed memory 
that is interposed between a processor, or bus agent, and main memory 
because cache memory is hidden from the user or programmer, and thus 
appears to be transparent. Cache memory, serving as a fast storage buffer 
between the processor, or bus agent, and main memory, is not user 
addressable. The user is only aware of the apparently higher-speed memory 
accesses because the cache memory is satisfying many of the requests 
instead of the slower main memory. 
Cache memory is smaller than main memory because cache memory employs 
relatively expensive high speed memory devices, such as static random 
access memory ("SRAM") Therefore, cache memory typically will not be large 
enough to hold all of the information needed during program execution. As 
a process executes, information in the cache memory must be replaced, or 
"overwritten" with new information from main memory that is necessary for 
executing the current process(es). 
Information is only temporarily stored in cache memory during execution of 
the process(es). When process data is referenced by a processor, or bus 
agent, the cache controller will determine if the required data is 
currently stored in the cache memory. If the required information is found 
in cache memory, this is referred to as a "cache hit." A cache hit allows 
the required information to be quickly retrieved from or modified in the 
high speed cache memory without having to access the much slower main 
memory, thus resulting in a significant savings in program execution time. 
When the required information is not found in the cache memory, this is 
referred to as a "cache miss." A cache miss indicates that the desired 
information must be retrieved from the relatively slow main memory and 
then placed into the cache memory. Cache memory updating and replacement 
schemes attempt to maximize the number of cache hits, and to minimize the 
number of cache misses. 
A cache memory is said to be "direct mapped" if each byte of information 
can only be written to one place in the cache memory. The cache memory is 
said to be "fully associative" if a byte of information can be placed 
anywhere in the cache memory. The cache memory is said to be "set 
associative" if a group of blocks of information from main memory can only 
be placed in a restricted set of places in the cache memory, namely, in a 
specified "set" of the cache memory. Computer systems ordinarily utilize a 
variation of set associative mapping to keep track of the bytes of 
information that have been copied from main memory into cache memory. 
The hierarchy of a set associative cache memory resembles a matrix. That 
is, a set associative cache memory is divided into different "sets" (such 
as the rows of a matrix) and different "ways" (such as the columns of a 
matrix). Thus, each line of a set associative cache memory is mapped or 
placed within a given set (row) and within a given way (column). The 
number of columns, i.e., the number of lines in each set, determine the 
number of "ways" of the cache memory. Thus, a cache memory with four 
columns (four lines within each set) is deemed to be "4-way set 
associative." 
Set associative cache memories include addresses for each line in the cache 
memory. Addresses may be divided into three different fields. First, a 
"block-offset field" is utilized to select the desired information from a 
line. Second, an "index field" specifies the set of cache memory where a 
line is mapped. Third, a "tag field" is used for purposes of comparison. 
When a request originates from a processor, or bus agent, for new 
information, the index field selects a set of cache memory. The tag field 
of every line in the selected set is compared to the tag field sought by 
the processor. If the tag field of some line matches the tag field sought 
by the processor, a "cache hit" is detected and information from the block 
is obtained directly from or modified in the high speed cache memory. If 
no match occurs, a "cache miss" occurs and the cache memory is typically 
updated. Cache memory is updated by retrieving the desired information 
from main memory and then mapping this information into a line of the set 
associative cache. When the "cache miss" occurs, a line is first mapped 
with respect to a set (row), and then mapped with respect to a way 
(column). That is, the index field of a line of information retrieved from 
main memory specifies the set of cache memory wherein this line will be 
mapped. A "replacement scheme" is then relied upon to choose the 
particular line of the set that will be replaced. In other words, a 
replacement scheme determines the way (column) where the line will be 
located. The object of a replacement scheme is to select for replacement 
the line of the set that is least likely to be needed in the near future 
so as to minimize further cache misses. 
Several factors contribute to the optimal utilization of cache memory in 
computer systems: cache memory hit ratio (probability of finding a 
requested item in cache), cache memory access time, delay incurred due to 
a cache memory miss, and time required to synchronize main memory with 
cache memory (write back or write through). In order to minimize delays 
incurred when a cache miss is encountered, as well as improve cache memory 
hit rates, an appropriate cache memory replacement scheme is used. 
Set associative cache memory replacement schemes may be divided into two 
basic categories: non-usage based and usage based. Non-usage based 
replacement schemes, which include first in, first out ("FIFO") and 
"random" replacement schemes, make replacement selections on some basis 
other than memory usage. The FIFO replacement scheme replaces the line of 
a given set of cache memory which has been contained in the given set for 
the longest period of time. The random replacement scheme randomly 
replaces a line of a given set. 
Usage based schemes, which include the least recently used ("LRU") 
replacement scheme, take into account the history of memory usage. In the 
LRU replacement scheme the least recently used line of information in 
cache memory is overwritten by the newest entry into cache memory. An LRU 
replacement scheme assumes that the least recently used line of a given 
set is the line that is least likely to be reused again in the immediate 
future. An LRU replacement scheme thus replaces the least recently used 
line of a given set with a new line of information that must be copied 
from main memory. 
When a cache miss occurs, a main memory access must be performed to 
obtained the desired information which will be stored in the cache. 
Typically a main memory read access is a cacheline, four quadwords, or 32 
bytes in size. Whenever a cacheline of information from the main memory 
read access is returned, it is returned in toggle mode order, critical 
quadword first. The transfer order of the four quadwords comprising the 
cacheline is based on the position of the critical quadword within the 
cacheline. The toggle mode transfer order is based on an interleaved main 
memory architecture where the quadwords are woven, or interleaved, between 
at least two banks of main memory. The four quadwords comprising the 
cacheline are taken in an order that always accesses opposite main memory 
banks so that the main memory bank not being accessed may be charged up 
and ready to accept another access. The toggle mode allows better main 
memory performance when using dynamic random access memory (DRAM) because 
memory accesses are not slowed down by pre-charge delays associated with 
operation of the DRAM. 
Increasingly inexpensive but sophisticated microprocessors have 
revolutionized the role of the personal computer by enabling complex 
applications software to run at mainframe computer speeds. The latest 
microprocessors have brought the level of technical sophistication to 
personal computers that, just a few years ago, was available only in 
mainframe and mini-computer systems. Some representative examples of these 
new microprocessors are the "PENTIUMN" and "PENTIUM PRO" (registered 
trademarks of Intel Corporation). Advanced microprocessors are also 
manufactured by Advanced Micro Devices, Cyrix, IBM, Digital Equipment 
Corp., Sun Microsystems and Motorola. 
These sophisticated microprocessors have, in turn, made possible running 
complex application programs using advanced three dimensional ("3-D") 
graphics for computer aided drafting and manufacturing, engineering 
simulations, games and the like. Increasingly complex 3-D graphics require 
higher speed access to ever larger amounts of graphics information stored 
in memory. This memory may be part of the video graphics processor system, 
but, preferably, would be best (lowest cost) if part of the main computer 
system memory because shifting graphics information from local graphics 
memory to main memory significantly reduces computer system costs when 
implementing 3-D graphics. Intel Corporation has proposed a low cost but 
improved 3-D graphics standard called the "Accelerated Graphics Port" 
(AGP) initiative. With AGP 3-D, graphics data, in particular textures, may 
be shifted out of the graphics controller local memory to computer system 
main memory. The computer system main memory is lower in cost than the 
graphics controller local memory and is more easily adapted for a 
multitude of other uses besides storing graphics data. 
The proposed Intel AGP 3-D graphics standard defines a high speed data 
pipeline, or "AGP bus," between the graphics controller and system main 
memory. This AGP bus has sufficient bandwidth for the graphics controller 
to retrieve textures from system memory without materially affecting 
computer system perfonnance for other non-graphics operations. The Intel 
3-D graphics standard is a specification which provides signal, protocol, 
electrical, and mechanical specifications for the AGP bus and devices 
attached thereto. The AGP specification is entitled "Accelerated Graphics 
Port Interface Specification Revision 1.0," dated Jul. 31, 1996, the 
disclosure of which is hereby incorporated by reference. The AGP 
Specification is available from Intel Corporation, Santa Clara, Calif. 
The AGP Specification uses the 66 MHz PCI (Revision 2.1) Specification as 
an operational baseline, with three performance enhancements to the PCI 
Specification which are used to optimize the AGP Specification for high 
performance 3-D graphics applications. These enhancements are: 1) 
pipelined memory read and write operations, 2) demultiplexing of address 
and data on the AGP bus by use of sideband signals, and 3) data transfer 
rates of 133 MHz for data throughput in excess of 500 megabytes per second 
("MB/s"). The remaining AGP Specification does not modify the PCI 
Specification, but rather provides a range of graphics-oriented 
performance enhancements for use by 3-D graphics hardware and software 
designers. The AGP Specification is neither meant to replace nor diminish 
full use of the PCI Specification in the computer system. The AGP 
Specification creates an independent and additional high speed local bus 
for use by 3-D graphics devices such as a graphics controller, wherein the 
other input-output ("I/O") devices of the computer system may remain on 
any combination of the PCI, SCSI, EISA and ISA buses. 
To functionally enable this AGP 3-D graphics bus, new computer system 
hardware and software are required. This requires new computer system core 
logic designed to function as a host bus/memory bus/PCI bus to AGP bus 
bridge meeting the AGP Specification, and new Read Only Memory Basic Input 
Output System ("ROM BIOS") and Application Programming Interface ("API") 
software to make the AGP dependent hardware functional in the computer 
system. The computer system core logic must still meet the PCI standards 
referenced above and facilitate interfacing the PCI bus(es) to the 
remainder of the computer system. In addition, new AGP compatible device 
cards must be designed to properly interface, mechanically and 
electrically, with the AGP bus connector. 
AGP and PCI device cards are not physically interchangeable even though 
there is some commonality of signal functions between the AGP and PCI 
interface specifications. The resent AGP Specification only makes 
allowance for a single AGP device on an AGP bus, whereas, the PCI 
Specification allows two plug-in slots for PCI devices plus a bridge on a 
PCI us running at 66 MHz. The single AGP device is capable of functioning 
in both a 1x mode 264 MB/s peak) and a 2x mode (532 MB/s peak). The AGP 
bus is defined as a 32 bit bus, and may have up to four bytes of data 
transferred per clock in the 1x mode and up to eight bytes of data per 
clock in the 2x mode. The PCI bus is defined as either a 32 bit or 64 bit 
bus, and may have up to four or eight bytes of data transferred per clock, 
respectively. The AGP bus, however, has additional sideband signals which 
enables it to transfer blocks of data more efficiently than is possible 
using a PCI bus. An AGP bus running in the 2x mode provides sufficient 
video data throughput (532 MB/s peak) to allow increasingly complex 3-D 
graphics applications to run on personal computers. 
A major performance/cost enhancement using AGP in a computer system is 
accomplished by shifting texture data structures from local graphics 
memory to main memory. Textures are ideally suited for this shift for 
several reasons. Textures are generally read-only, and therefore problems 
of access ordering and coherency are less likely to occur. Shifting of 
textures serves to balance the bandwidth load between system memory and 
local graphics memory, since a well-cached host processor has much lower 
memory bandwidth requirements than does a 3-D rendering machine; texture 
access comprises perhaps the single largest component of rendering memory 
bandwidth, so avoiding loading or caching textures in local graphics 
memory saves not only this component of local memory bandwidth, but also 
the bandwidth necessary to load the texture store in the first place, and, 
further, this data must pass through main memory anyway as it is loaded 
from a mass store device. Texture size is dependent upon application 
quality rather than on display resolution, and therefore may require the 
greatest increase in memory as software applications become more advanced. 
Texture data is not persistent and may reside in the computer system 
memory only for the duration of the software application, so any system 
memory spent on texture storage can be returned to the free memory heap 
when the application concludes (unlike a graphic controller's local frame 
buffer which may remain in persistent use). For these reasons, shifting 
texture data from local graphics memory to main memory significantly 
reduces computer system costs when implementing 3-D graphics. 
Generally, in a computer system memory architecture the graphics 
controller's physical address space resides above the top of system 
memory. The graphics controller uses this physical address space to access 
its local memory which holds information required to generate a graphics 
screen. In the AGP system, information still resides in the graphics 
controller's local memory (textures, alpha, z-buffer, etc.), but some data 
which previously resided in this local memory is moved to system memory 
(primarily textures, but also command lists, etc.). The address space 
employed by the graphics controller to access these textures becomes 
virtual, meaning that the physical memory corresponding to this address 
space doesn't actually exist above the top of memory. In reality, each of 
these virtual addresses corresponds to a physical address in system 
memory. The graphics controller sees this virtual address space, 
referenced hereinafter as "AGP device address space," as one contiguous 
block of memory, but the corresponding physical memory addresses may be 
allocated in 4 kilobyte ("KB"), non-contiguous pages throughout the 
computer system physical memory. 
There are two primary AGP usage models for 3D rendering, that have to do 
with how data are partitioned and accessed, and the resultant interface 
data flow characteristics. In the "DMA" model, the primary graphics memory 
is a local memory referred to as `local frame buffer` and is associated 
with the AGP graphics controller or "video accelerator." 3D structures are 
stored in system memory, but are not used (or "executed") directly from 
this memory; rather they are copied to primary (local) memory, to which 
the rendering engine's address generator (of the AGP graphics controller) 
makes references thereto. This implies that the traffic on the AGP bus 
tends to be long, sequential transfers, serving the purpose of bulk data 
transport from system memory to primary graphics (local) memory. This sort 
of access model is amenable to a linked list of physical addresses 
provided by software (similar to operation of a disk or network I/O 
device), and is generally not sensitive to a non-contiguous view of the 
memory space. 
In the "execute" model, the video accelerator uses both the local memory 
and the system memory as primary graphics memory. From the accelerator's 
perspective, the two memory systems are logically equivalent; any data 
structure may be allocated in either memory, with performance optimization 
as the only criteria for selection. In general, structures in system 
memory space are not copied into the local memory prior to use by the 
video accelerator, but are "executed" in place. This implies that the 
traffic on the AGP bus tends to be short, random accesses, which are not 
amenable to an access model based on software resolved lists of physical 
addresses. Since the accelerator generates direct references into system 
memory, a contiguous view of that space is essential. But, since system 
memory is dynamically allocated in, for example, random 4,096 byte blocks 
of the memory, hereinafter 4 kilobyte ("KB") pages, it is necessary in the 
"execute" model to provide an address mapping mechanism that maps the 
random 4 KB pages into a single contiguous address space. 
The AGP Specification, incorporated by reference hereinabove, supports both 
the "DMA" and "execute" models. However, since a primary motivation of the 
AGP is to reduce growth pressure on the graphics controller's local memory 
(including local frame buffer memory), the "execute" model is preferred. 
Consistent with this preference, the AGP Specification requires a 
virtual-to-physical address re-mapping mechanism which ensures the 
graphics accelerator (AGP master) will have a contiguous view of graphics 
data structures dynamically allocated in the system memory. This address 
re-mapping applies only to a single, programmable range of the system 
physical address space and is common to all system agents. Addresses 
falling in this range are re-mapped to non-contiguous pages of physical 
system memory. All addresses not in this range are passed through without 
modification, and map directly to main system memory, or to device 
specific ranges, such as a PCI device's physical memory. Re-mapping is 
accomplished via a "Graphics Address Remapping Table" ("GART table") which 
is set up and maintained by a GART miniport driver software, and used by 
the core logic chipset to perform the re-mapping. In order to avoid 
compatibility issues and allow future implementation flexibility, this 
mechanism is specified at a software (API) level. In other words, the 
actual GART table format may be abstracted to the API by a hardware 
abstraction layer ("HAL") or mini-port driver that is provided with the 
core logic chipset, While this API does not constrain the future 
partitioning of re-mapping hardware, the remapping function will typically 
be implemented in the core logic chipset. 
The contiguous AGP graphics controller's device addresses are mapped 
(translated) into corresponding physical addresses that reside in the 
computer system physical memory by using the GART table which may also 
reside in physical memory. The GART table is used by the core logic 
chipset to remap AGP device addresses that can originate from either the 
AGP, host, or PCI buses. The GART table is managed by a software program 
called a "GART miniport driver." The GART miniport driver provides GART 
services for the computer software operating system. 
Residing in the system memory, the GART table may be read from and/or 
written to by the core logic driver software, i.e. the aforementioned GART 
miniport driver, or any other software program or application specific 
interface ("API") program using the host microprocessor(s), AGP graphics 
devices, or a PCI device. The GART table is used by the computer system 
core logic to remap the virtual addresses of the graphics data requested 
by the AGP graphics controller to physical addresses of pages that reside 
in the computer system memory (translate addresses). Thus, the AGP 
graphics controller can work in contiguous virtual address space, but use 
non-contiguous pages of physical system memory to store graphics data such 
as textures and the like. 
Typically, the core logic will cache a subset of the most recently accessed 
GART table entries to increase system perfonnance when mapping from the 
AGP device address space (AGP virtual address space) to the physical 
address space of the computer system main memory. A GART table entry is 
typically a doubleword which is four bytes in size. An access to main 
memory is typically a cacheline which is four quadwords or 32 bytes in 
size, the desired quadword is returned in toggle mode order as described 
above. If only one GART table entry (a doubleword) is stored in the core 
logic cache for each memory access of the GART table, half of the quadword 
and most of the cacheline memory access (three quadwords) will not be 
utilized, and for each subsequent cacheline miss another memory access 
must be performed. 
What is needed is a system, method and apparatus for improving the 
probability of GART cache hits and to better utilize the cacheline data 
returned from a memory access of the GART table stored in the computer 
system main memory. 
OBJECTS OF THE INVENTION 
It is therefore an object of the present invention to improve the 
probability of GART cache hits. 
Another object of the present invention is to better utilize the cacheline 
data returned from a memory access of the GART table stored in the 
computer system main memory. 
Another object is to prefetch the quadword aligned companion GART table 
entry on each GART cache miss allocation cycle. 
Still another object is to prefetch the cacheline aligned companion GART 
table entries on each GART cache miss allocation cycle. 
Yet another object is to cache at least one quadword of GART table entries 
each time a memory access is required because of a cache miss. 
Another object is to cache coterminous GART table entries each time a 
memory access is required because of a cache miss. 
SUMMARY OF THE INVENTION 
The above and other objects of the present invention are satisfied, at 
least in part, by providing in a computer system a core logic chipset that 
functions as a bridge between an AGP bus, host and memory buses, and a PCI 
bus wherein a "Graphics Address Remapping Table" ("GART table") is used by 
the core logic chipset to remap virtual addresses into physical addresses 
that reside in the computer system memory. Entries of the GART table may 
also reside in the computer system memory. The core logic chipset uses the 
GART table entries so that a host processor(s), an AGP graphics 
controller, or a PCI device may reference addresses of graphics 
information in contiguous virtual address space, hereinafter "AGP device 
address space," but actually have the graphics information stored in 
non-contiguous blocks of the computer system physical memory. The graphics 
information may be textures, z-buffers, command lists and the like. The 
core logic chipset of the present invention caches the necessary GART 
table entries in order to speed up retrieval of the graphics data from the 
computer system memory. 
The GART table is made up of a plurality of entries. A GART miniport driver 
creates the entries in the computer system memory that make up the GART 
table. Each of these entries comprise a translation pointer which 
references the physical address of the first byte of a page in physical 
memory, and feature flags associated with the referenced page. Each page 
in physical memory referenced by the GART table contains AGP graphics 
textures. The feature flags may be used to customize each associated page 
of memory referenced by the pointer address. 
The AGP Specification entitled "Accelerated Graphics Port Interface 
Specification Revision 1.0," dated Jul. 31, 1996, as referenced above, is 
available from Intel Corporation, and is hereby incorporated by reference. 
Further definition and enhancement of the AGP Specification is more fully 
defined in "Compaq's Supplement to the `Accelerated Graphics Port 
Interface Specification Version 1.0`," Revision 0.8, dated Apr. 1, 1997, 
and is hereby incorporated by reference. Both of these AGP specifications 
were included as Appendices A and B in commonly owned, co-pending U.S. 
patent application Ser. No. 08/853,289; filed May 9, 1997, entitled "Dual 
Purpose Apparatus, Method and System for Accelerated Graphics Port and 
Peripheral Component Interconnect" by Ronald T. Horan and Sompong Olarig, 
and which is hereby incorporated by reference. A detailed description of 
enhancements made to AGP is also disclosed in commonly owned, co-pending 
patent application U.S. patent application Ser. No. 08/925,772, filed Sep. 
8, 1997, entitled "Graphics Address Remapping Table Entry Feature Flags 
for Customizing the Operation of Memory Pages Associated with an 
Accelerated Graphics Port Device" by Ronald T. Horan, Phillip M. Jones, 
Gregory N. Santos, Robert Allan Lester, and Robert Elliott, and is hereby 
incorporated by reference. 
In an embodiment of the present invention, when there is a GART cache miss 
of a required GART table entry needed for a GART address translation 
request(s), a quadword aligned companion GART table entry is also 
prefetched and stored in the GART cache during the GART cache miss 
allocation cycle which accesses the GART table in the main memory for the 
needed GART table entry. GART table entries are arranged in sequential 
contiguous addresses in at least 4 KB blocks of the main memory. If the 
GART cache miss address is quadword aligned, the next GART table entry is 
prefetched. However, if the GART cache miss address is not quadword 
aligned, the previous GART table entry is prefetched. In either case, two 
GART table entries within a quadword are stored in the GART cache and may 
be used for address translation pointers. Each GART table entry points to 
a 4 KB range of AGP device address space, thus according to the present 
invention, two GART table entries (one quadword) may be obtained from the 
main memory in a single memory read access cycle. These two GART table 
entries may be used as pointers (the one needed because of the GART cache 
miss, the other one in anticipation of future GART address translations) 
for translating at least a 4 KB range (the requested GART table entry) and 
possibly an 8 KB range (the requested GART table entry plus the prefetched 
GART table entry) of AGP device address space to the address space in the 
main memory where the AGP graphics information is stored. Since the 
required GART table entry (doubleword) had to be fetched from the main 
memory on a GART cache miss, the next or prior GART table entry (other 
doubleword) prefetched in the aforementioned manner is part of the 
quadword returned in toggle mode from the memory read access cycle, it is 
therefore free to be used for a future GART address translation without 
creating a penalty in computer cycle time. 
In a fuirther embodiment of the present invention, the required GART table 
entry is fetched on a GART cache miss as disclosed above, and its quadword 
aligned other GART table entry is also present in the first quadword 
returned in toggle mode from the memory read access. Both GART table 
entries being stored in the GART cache, the one GART table entry needed 
because of the cache miss and the other GART table entry in anticipation 
of a future GART address translation(s). The second, third and fourth 
quadwords being returned in toggle mode from the memory read access cycle 
each contain two GART table entries, which according to this embodiment of 
the present invention, are also stored in the GART cache of the core logic 
chipset in anticipation of future GART address translations. If these GART 
table entries are not needed, there is no time penalty since a memory read 
access cycle returns a cacheline of information, and if these GART table 
entries are needed, a substantial increase in the GART cache hit to miss 
ratio is realized. GART cache size may be adjusted to optimize operation 
of the present invention as well as selection of replacement algorithms. 
A feature of the present invention is that up to eight GART table entries 
may be obtained from a single memory read access cycle initiated by a GART 
cache miss. 
Another feature of the present invention is that more than one GART table 
entry is returned for every memory read access cycle without additional 
computer system operating time. 
Still another feature is the first quadword returned in toggle mode has two 
GART table entries which are stored in the GART cache of the core logic 
chipset. 
An advantage of the present invention is that a greater hit to miss ratio 
may be realized over caching just a single GART table entry from a memory 
read access cycle when a GART cache miss has occurred. 
Other and further objects, features and advantages will be apparent from 
the following description of presently preferred embodiments of the 
invention, given for the purpose of disclosure and taken in conjunction 
with the accompanying drawings.

DETAILED DESCRIPTION OF THE PREFERRED EMBODIMENTS 
The present invention provides a core logic chipset in a computer system 
which is capable of implementing a bridge between host processor and 
memory buses, an AGP bus adapted for an AGP device(s), and a PCI bus 
adapted for PCI devices. The AGP device may be a graphics controller which 
utilizes graphical data such as textures by addressing a contiguous 
virtual address space, hereinafter "AGP device address space," that is 
translated from non-contiguous memory pages located in the computer system 
physical memory by the core logic chipset. The core logic chipset utilizes 
a "Graphics Address Remapping Table" ("GART table") which may reside in a 
physical memory of the computer system, such as system random access 
memory, and may be controlled by the core logic chipset software 
driver(s). The function of the GART table is to remap virtual addresses 
referenced by the AGP device to the physical addresses of the graphics 
information located in the computer system physical memory. Each entry of 
the GART table describes a first byte address location for a page of 
physical memory. The page of physical memory may be 4,096 bytes (4 KB) in 
size. A GART table entry comprises a memory address translation pointer 
which may be cached to improve the performance of the core logic chipset 
when mapping from the virtual memory address space to the physical 
addresses that reside in the physical (main) memory. 
The AGP Specification entitled "Accelerated Graphics Port Interface 
Specification Revision 1.0," dated Jul. 31, 1996, as referenced above, is 
available from Intel Corporation, and is hereby incorporated by reference. 
Further definition and enhancement of the AGP Specification is more fully 
defined in "Compaq's Supplement to the `Accelerated Graphics Port 
Interface Specification Version 1.0`," Revision 0.8, dated Apr. 1, 1997, 
and is hereby incorporated by reference. Both of these AGP specifications 
were included as Appendices A and B in commonly owned, co-pending U.S. 
patent application Ser. No. 08/853,289; filed May 9, 1997, entitled "Dual 
Purpose Apparatus, Method and System for Accelerated Graphics Port and 
Peripheral Component Interconnect" by Ronald T. Horan and Sompong Olarig, 
and which is hereby incorporated by reference. A detailed description of 
enhancements made to AGP is also disclosed in commonly owned, co-pending 
patent application U.S. patent application Ser. No. 08/925,772; filed Sep. 
8, 1997, entitled "Graphics Address Remapping Table Entry Feature Flags 
for Customizing the Operation of Memory Pages Associated with an 
Accelerated Graphics Port Device" by Ronald T. Horan, Phillip M. Jones, 
Gregory N. Santos, Robert Allan Lester, and Robert Elliott, and is hereby 
incorporated by reference. 
A memory controller and interface logic of the core logic chipset is used 
for memory accesses, both read and write, and refresh cycles to the main 
memory. The memory controller and interface logic may perform memory 
accesses for a certain number of bytes of information at one time. The 
number of bytes of information accessed by the memory controller and 
interface logic in one transaction is designed to result in the most 
efficient operation of the main memory, which ultimately results in the 
highest memory bandwidth or data throughput. Different types of computer 
systems, i.e., using various combinations of microprocessors and types of 
main memory, may have a different optimum number of bytes of information 
that may be accessed at one time. 
For illustrative purposes, the preferred embodiment of the present 
invention is described hereinafter for computer systems utilizing the 
Intel x86 microprocessor architecture and certain terms and references 
will be specific to those processor platforms. AGP and PCI are interface 
standards, however, that are hardware independent and may be utilized with 
any host computer designed for these interface standards. It will be 
appreciated by those skilled in the art of computer systems that the 
present invention may be adapted and applied to any computer platform 
utilizing the AGP and PCI Specifications. 
Referring now to the drawings, the details of preferred embodiments of the 
present invention are schematically illustrated. Like elements in the 
drawings will be represented by like numbers, and similar elements will be 
represented by like numbers with a different lower case letter suffix. 
Referring now to FIG. 1, a schematic block diagram of a computer system 
utilizing the present invention is illustrated. A computer system is 
generally indicated by the numeral 100 and comprises a central processing 
unit(s) ("CPU") 102, core logic 104, system random access memory ("RAM") 
106, a video graphics controller 110, a local frame buffer 108, a video 
display 112, a PCI/SCSI bus adapter 114, a PCI/EISA/ISA bridge 116, and a 
PCI/IDE controller 118. The CPU 102 may be a plurality of CPUs 102 in a 
symmetric or asymmetric multi-processor configuration. 
The CPU(s) 102 is connected to the core logic 104 through a host bus 103. 
The system RAM 106 is connected to the core logic 104 through a memory bus 
105. The video graphics controller(s) 110 is connected to the core logic 
104 through an AGP bus 107. The PCI/SCSI bus adapter 114, PCI/EISA/ISA 
bridge 116, and PCI/IDE controller 118 are connected to the core logic 104 
through a PCI bus 109. Also connected to the PCI bus 109 are a network 
interface card ("NIC") 122 and a PCI/PCI bridge 124. Some of the PCI 
devices such as the NIC 122 and PCI/PCI bridge 124 may plug into PCI 
connectors on the computer system 100 motherboard (not illustrated). 
Hard disk 130 and tape drive 132 are connected to the PCI/SCSI bus adapter 
114 through a SCSI bus 111. The NIC 122 is connected to a local area 
network 119. The PCI/EISA/ISA bridge 116 connects over an EISA/ISA bus 113 
to a ROM BIOS 140, non-volatile random access memory (NVRAM) 142, modem 
120, and input-output controller 126. The modem 120 connects to a 
telephone line 121. The input-output controller 126 interfaces with a 
keyboard 146, real time clock (RTC) 144, mouse 148, floppy disk drive 
("FDD") 150, a serial port 152, and a parallel port 154. The EISA/ISA bus 
113 is a slower information bus than the PCI bus 109, but it costs less to 
interface with the EISA/ISA bus 113. 
Referring now to FIG. 2, a schematic functional block diagram of the core 
logic 104 of FIG. 1, according to the present invention, is illustrated. 
The core logic 104 functionally comprises CPU host bus interface and 
queues 202, a memory interface and control 204, a host/PCI bridge 206, an 
AGP logic 218, and a PCI/PCI bridge 220. The AGP logic 218 comprises AGP 
request/reply queues 212, an AGP data and control 210, an AGP arbiter 216, 
and a GART cache 224. The CPU host bus interface and queues 202 connect to 
the host bus 103 and include interface logic for all data, address and 
control signals associated with the CPU(s) 102 of the computer system 100. 
Multiple CPUs 102 and cache memory associated therewith (not illustrated) 
are contemplated and within the scope of the present invention. 
The CPU host bus interface and queues 202 interface with the host/PCI 
bridge 206 and memory interface and control 204 over a core logic bus 211. 
The CPU host bus interface and queues 202 interface with the AGP logic 218 
over the core logic bus 211. The memory interface and control 204 
interfaces with the AGP logic 218 over a core logic bus 209. An advantage 
of having separate buses 209 and 211 is that concurrent bus operations may 
be performed thereover. For example, AGP graphics data stored in system 
RAM 106, connected to the bus 105, may be transferring to the video 
graphics controller 110 (AGP device) on the AGP bus 107 while the CPU 102 
on the host bus 103 is accessing an independent PCI device (i.e., NIC 122) 
on the PCI bus 109. 
The host bus interface and queues 202 allow the CPU 102 to pipeline cycles 
and schedule snoop accesses. The memory interface and control 204 
generates the control and timing signals for the computer system RAM 106 
which may be synchronous dynamic RAM (SDRAM) and the like. The memory 
interface and control 204 has an arbiter (not illustrated) which selects 
among memory accesses for CPU writes, CPU reads, PCI writes, PCI reads, 
AGP reads, AGP writes, and dynamic memory refresh. Arbitration may be 
pipelined into a current memory cycle, which ensures that the next memory 
address is available on the memory bus 105 before the current memory cycle 
is complete. This results in minimum delay, if any, between memory cycles. 
The host/PCI bridge 206 controls the interface to the PCI bus 109. When 
the CPU 102 accesses the PCI bus 109, the host/PCI bridge 206 operates as 
a PCI master. When a PCI device is a master on the PCI bus 109, the 
host/PCI bridge 206 operates as a PCI slave (target). The host/PCI bridge 
206 contains base address registers for PCI device targets on its PCI bus 
109 (not illustrated). Operation of PCI is more fully described in the PCI 
Local Bus Specification, revision 2.1; PCI/PCI Bridge Specification, 
revision 1.0; PCI System Design Guide, revision 1.0; PCI BIOS 
Specification, revision 2.1, and Engineering Change Notice ("ECN") 
entitled "Addition of `New Capabilities` Structure," dated May 20, 1996, 
the disclosures of which are hereby incorporated by reference. These PCI 
specifications and ECN are hereby incorporated by reference and are 
available from the PCI Special Interest Group, P.O. Box 14070, Portland, 
Oreg. 97214. 
The AGP data and control 210, AGP arbiter 216, and AGP request/reply queues 
212 interface to the AGP bus 107 and also have signal, power and ground 
connections (not illustrated) for implementation of signals defined in the 
AGP and PCI specifications incorporated by reference hereinabove. The AGP 
bus 107 is adapted for connection to an AGP device(s) and/or an AGP 
connector(s) (not illustrated). 
The PCI/PCI bridge 220 is connected between the PCI bus 109 and the AGP bus 
107. The PCI/PCI bridge 220 allows existing enumeration code in the 
computer system BIOS 140 to recognize and handle AGP compliant devices, 
such as the video graphics controller 110, residing on the AGP bus 107. 
The PCI/PCI bridge 220, for example, may be used in configuring the 
control and status registers of the AGP graphics controller 110 or the AGP 
logic 218 by bus enumeration during POST, both being connected to the AGP 
bus 107. 
The memory interface and control 204 accesses the RAM 106 a cacheline at a 
time, i.e., 32 bytes of information are transferred between the memory 
interface and control 204 and the RAM 106 during each memory access cycle. 
These 32 bytes of information are available a quadword at a time and are 
returned in toggle mode order, critical quadword first. The transfer order 
of the four quadwords comprising the cacheline is based on the position of 
the critical quadword within the cacheline. The toggle mode transfer order 
is based on an interleaved main memory architecture where the quadwords 
are woven, or interleaved, between two banks of main memory. The four 
quadwords comprising the cacheline are taken in an order that always 
accesses opposite main memory banks so that the main memory bank not being 
accessed may be charged up and ready to accept another access. The toggle 
mode allows better main memory performance when using dynamic random 
access memory (DRAM) because memory accesses are not slowed down by 
pre-charge delays associated with operation of the RAM 106. 
Referring now to FIGS. 3 and 4, schematic diagrams of a memory map of the 
computer system, and a GART table in the computer system memory are 
illustrated. A logical memory map of the computer system memory 106 is 
generally indicated by the numeral 402, the graphics controller physical 
address space by the numeral 404, and the AGP device address space 
(virtual memory) by the numeral 406. The computer system 100 may address 
up to 4 gigabytes ("GB") of memory with a 32 bit address, however, some of 
this 4 GB of memory address space may be used for local memory associated 
with various devices such as the AGP video graphics controller's 110 
memory which may include the local frame buffer 108, texture cache, alpha 
buffers, Z-buffers, etc., all being addressed within the graphics 
controller physical address space 404. In addition, according to the 
present invention, some of the memory address space 402 is used for the 
AGP device address space 406. In FIG. 3, the bottom (lowest address) of 
the computer system memory 106 is represented by the numeral 408 and the 
top (highest address) is represented by the numeral 410. In between the 
bottom 408 and the top 410 are various blocks or "pages" of AGP memory 
represented by the numeral 412. Each page 412 has a contiguous set of 
memory addresses. 
In the present invention, some of these AGP memory pages (indicated by 
412a, 412b and 412c) are used to store AGP information, such as textures, 
lists and the like, and at least one page (represented by the number 414) 
is used to store entries in the GART table 414. The GART table 414 
comprises a plurality of entries 418 (FIG. 4). Enough GART table entries 
418 are stored to represent all of the associated AGP device address space 
406 being used in the computer system 100. Each GART table entry 418 
represents the base address 416 of the respective page 412 of the AGP 
memory. Another memory page may also be used to store a GART directory 
(represented by the number 420). The GART directory 420 is used for 
two-level address remapping as more fully described in the AGP 
specifications incorporated by reference hereinabove. Each GART table 
entry 418 stores 32 binary bits of information (a doubleword). The GART 
table 414 is used to remap AGP device address space 406 to addresses of 
the pages 412, by using the upper bits (31:12) to store a base address 416 
for each of the corresponding 4 KB pages 412. The lower 12 bits of the AGP 
device address 406 is the same as the lower 12 bits of the address of the 
page 412, as more fully described in "Compaq's Supplement to the 
`Accelerated Graphics Port Interface Specification Version 1.0`," Revision 
0.8, dated Apr. 1, 1997, incorporated by reference hereinabove. 
The video graphics controller 10 asserts addresses on the AGP bus 107 
requesting the required graphical texture data. The AGP logic 218 receives 
these addresses for the requested graphical texture data which reference 
the AGP device addresses 406, however, the AGP device addresses 406 are 
virtual addresses and do not physically exist in the computer system 100 
RAM 106. The AGP logic 218 therefore must remap these AGP device addresses 
406 into the actual AGP pages 412 residing in the RAM 106. These AGP pages 
412 are not contiguous nor are they in any particular order. The GART 
table 414 is used to remap the AGP device addresses 406 to the actual 
physical addresses of the AGP pages 412 residing in the RAM 106 (physical 
memory--logical memory map 402). The core logic chipset 104 caches a 
subset of the most recently used GART table entries 418 in the GART cache 
224 to increase AGP performance when performing the GART address 
translations. AGP GART address translation speed is improved whenever a 
read to the RAM 106 is not needed to obtain a selected GART table entry 
418, i.e., there is a "cache hit" in the GART cache 224. 
Referring now to FIG. 5, a schematic functional block diagram of the GART 
cache 224 and a portion of the AGP memory map 402 are illustrated. When 
the video graphics controller 110 requests graphics texture data on the 
AGP bus 107, the AGP logic 218 evaluates the asserted AGP device address 
space 406a to determine if the associated GART table entry 418a is in the 
GART cache 224. If the GART table entry 418a is in the GART cache 224 (a 
cache hit) the AGP logic 218 performs a memory read access of the AGP page 
412 located in the physical memory (RAM 106) and remaps the page 412 to 
the desired AGP device address space 406. However, if the necessary GART 
table entry 418 (FIG. 4) is not found in the GART cache 224, then the AGP 
logic 218 must first update the GART cache 224 with the necessary GART 
table entry 418. 
FIG. 5 illustrates four GART table entries for illustrative clarity, 
however, any number of GART table entries 418 may be cached in the present 
invention and are contemplated herein. Once the selected GART table 
entries 418 are written into the cache 224, the AGP pages 412 may be read 
from the physical memory 106. The AGP pages 412 are not stored in the AGP 
logic 218 but are used by the video graphics controller 110 directly from 
the RAM 106. The AGP logic 218 acts as an address translator to remap the 
randomly ordered and non-contiguous AGP pages 412 into the contiguous AGP 
device address space 406. 
When a needed GART table entry 418a is not found in the GART cache 224, 
there is a cache miss and the core logic chipset 104 must fetch the needed 
GART table entry 418a from the GART table 414 stored in the RAM 106. A 
memory transaction read request for the needed GART table entry 418a is 
sent to the memory interface and control 204 by the AGP logic 218. The 
memory interface and control 204 requests a memory read access of the RAM 
106 over the bus 105. Referring now to FIG. 6, a cacheline (represented by 
the number 602) of GART table entries 418 is read from the RAM 106 by the 
memory interface and control 204. The cacheline 602 is returned a quadword 
at a time, with the most critical quadword 604a (the quadword having the 
needed GART table entry 418a) returned first. The remaining three 
quadwords 604b, 604c and 604d of the cacheline 602 are returned in toggle 
mode. 
On a cache miss, if the GART table entry 418a is quadword 604a address 
aligned, the next GART table entry 418b in the quadword 604a may be 
prefetched and stored in the GART cache 224 along with the needed GART 
table entry 418a. However, if for example, the GART table entry 418d is 
not quadword address aligned (quadword 604b), the previous GART table 
entry 418c in quadword 604b may be prefetched and stored in the GART cache 
224 along with the needed GART table entry 418d. In either case, two GART 
table entries 418 within the same quadword 604 are returned in toggle mode 
from the memory read access cycle and stored in the GART cache 224. Thus, 
two GART table entries (one quadword) may be obtained from the main memory 
in a single memory read access cycle. 
The memory read access cycle returns in toggle mode the needed GART table 
entry 418a in the first critical quadword 604a along with its coterminous 
GART table entry 418b within the same quadword 604a. However, quadwords 
604b, 604c and 604d are also being returned in toggle mode from the memory 
read access cycle and each of these quadwords may contain two GART table 
entries 418c and 418d, 418e and 418f, and 418g and 418h, respectively, 
which according to the present invention, may also be stored in the GART 
cache 224 in anticipation of future GART address translations. If any of 
these GART table entries 418a-418h are not needed, there is no memory 
access time penalty since a memory read access cycle returns a cacheline 
of information whenever a cache miss occurs, and if any of these GART 
table entries 418a-418h are needed, a substantial increase in the GART 
cache hit to miss ratio may be realized. The size of the GART cache 224 
may be adjusted to optimize operation of the present invention as well as 
selection of replacement algorithms. 
GART directory 420 entries (FIG. 3) may be cached in a similar manner as 
disclosed above and the GART cache 224 may be a one or more way cache. 
Coherency of the GART cache 224 may be maintained as more fully disclosed 
in commonly owned co-pending U.S. patent application Ser. No. 08/926,421; 
filed Sep. 8, 1997, entitled "System and Method for Invalidating and 
Updating Individual GART Table Entries for Accelerated Graphics Port 
Transaction Requests" by Gregory N. Santos and Robert C. Elliott, and 
which is hereby incorporated by reference. 
The present invention, therefore, is well adapted to carry out the objects 
and attain the ends and advantages mentioned, as well as others inherent 
therein. While the present invention has been depicted, described, and is 
defined by reference to particular preferred embodiments of the invention, 
such references do not imply a limitation on the invention, and no such 
limitation is to be inferred. The invention is capable of considerable 
modification, alternation, and equivalents in form and function, as will 
occur to those ordinarily skilled in the pertinent arts. The depicted and 
described preferred embodiments of the invention are exemplary only, and 
are not exhaustive of the scope of the invention. Consequently, the 
invention is intended to be limited only by the spirit and scope of the 
appended claims, giving full cognizance to equivalents in all respects.