EXHIBIT M 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 1 of 12 PageID #: 1587
USOO6823409B2 

(12) United States Patent (10) Patent No.: US 6,823,409 B2 

Jones et al. (45) Date of Patent: Nov. 23, 2004 

(54) COHERENCY CONTROL MODULE FOR 5,331,646 A 7/1994 Krueger et al. ............ 371/40.1 

MAINTAINING CACHE COHERENCY IN A 5,367,669 A 11/1994 Holland et al. ....... ... 395/575 

MULTI-PROCESSOR-BUS SYSTEM 5,819,105 A * 10/1998 Moriarty et al. ............... 710/5 

5,822,611 A * 10/1998 Donley et al. ................. 710/6 

(75) Inventors: Philip M. Jones, Spring, TX (US); 5,893,151 A * 4/1999 Merchant ....... ... 711/140 

Paul B. Rawlins, Spring, TX (US) 5,966,729 A * 10/1999 Phelps ... ... 711/146 : 

(73) Assignee: Hewlett-Packard Development 5.991,819 A 11/1999 Young - - - - - - - - - - - ... 709/253 

Company, L.P., Houston, TX (US) 6,098,132 A 8/2000 Olarig et al. ............... 710/103 

9 s s 6,209,067 B1 * 3/2001 Collins et al. .............. 711/158 

(*) Notice: Subject to any disclaimer, the term of this 6,223,301 B1 4/2001 Santeler et al. ................ 714/6 

patent is extended or adjusted under 35 6,226,695 B1 5/2001 Kaiser et al. .................. 710/5 

U.S.C. 154(b) by 414 days. 6.279,084 B1 * 8/2001 VanDoren et al. .......... 711/141 

6.279,087 B1 * 8/2001 Melo et al. ........... ... 711/146 

(21) Appl. No.: 09/965,894 6,345,341 B1 2/2002 Arimilli et al. ............. 711/141 

6,487,621 B1 11/2002 MacLaren ................... 710/240 

(22) Filed: Sep. 28, 2001 2003/0065843 A1 4/2003 Jones et al. ................. 710/107 

(65) Prior Publication Data 2003/020O397 A1 * 10/2003 McAllister et al. - - - - - - - - - 711/141 

US 2003/0070016 A1 Apr. 10, 2003 * cited by examiner 

(51) Int. Cl." ................................................ G06F 13/00 

(52) U.S. Cl. ... ... 710/107; 710/52; 710/305; 710/306; 711/146 Primary Examiner Xuan M. Thai 

(58) Field of Search .......................... 710/52, 107, 305, 57 ABSTRACT 

710/306; 711/141, 143, 146, 163, 167, (57) 

168 A mechanism for efficiently filtering Snoop requests in a 

(56) References Cited multi-processor bus system. Specifically, a Snoop filter is 

provided to filter unnecessary Snoops in a multi-bus System. 

U.S. PATENT DOCUMENTS 

5,313,626 A 5/1994 Jones et al. ................. 395/575 17 Claims, 3 Drawing Sheets 

4-O 

TAGRAM 

NTERFACE 

MODULE 

RESPONSE 

MODULE 

29 

ACVESNOOP 

QUEUE 

(ASQ) 

TCON MODULE 

 

 

 

 

 

 

 

 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 2 of 12 PageID #: 1588
U.S. Patent Nov. 23 2004 Sheet 1 of 3 US 6,823,409 B2 

92- 

V09 

£102ClO200202Z gOZVOZNo.w ||GWw

No.w ||owl

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 3 of 12 PageID #: 1589
U.S. Patent Nov. 23, 2004 Sheet 2 of 3 US 6,823,409 B2 

FIG 2 

RESPONSE 

MODULE 

4-O 

TAGRAM 

NERFACE 

MODULE 

29 

ACTIVESNOOP 

QUEUE 

(ASQ) 

TCONMODULE 

 

 

 

 

 

 

 

 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 4 of 12 PageID #: 1590
U.S. Patent Nov. 23, 2004 Sheet 3 of 3 US 6,823,409 B2 

REQUES TO MEMORY26 

CAM-0 4-4A 

62A 56A 

523 

BUS 

14B 

625 44 

44 

TO MEMORY26 74. 

27 -righ 

58C 

-REC E. 

REQUEST READ 

BUFFER 

56C 2M 62C i D 

WRITE 74 ODD-2 

BUFFER SELEC 

FIG. 3 

4-2 

 

 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 5 of 12 PageID #: 1591
US 6,823,409 B2 

1 

COHERENCY CONTROL MODULE FOR 

MAINTAINING CACHE COHERENCY IN A 

MULTI-PROCESSOR-BUS SYSTEM 

BACKGROUND OF THE INVENTION 

1. Field of the Invention 

This invention relates generally to a multi-processor-bus 

memory System and, more particularly, to an efficient 

mechanism for filtering processor cache Snoops in a multi 

processor-bus-System. 

2. Description of the Related Art 

This Section is intended to introduce the reader to various 

aspects of art which may be related to various aspects of the 

present invention which are described and/or claimed below. 

This discussion is believed to be helpful in providing the 

reader with background information to facilitate a better 

understanding of the various aspects of the present inven 

tion. Accordingly, it should be understood that these State 

ments are to be read in this light, and not as admissions of 

prior art. 

The use of computerS has increased dramatically over the 

past few decades. In years past, computers were relatively 

few in number and primarily used as Scientific tools. 

However, with the advent of standardized architectures and 

operating Systems, computerS Soon became virtually indis 

pensable tools for a wide variety of busineSS applications. 

Perhaps even more significantly, in the past ten to fifteen 

years with the advent of relatively simple user interfaces and 

ever increasing processing capabilities, computers have now 

found their way into many homes. 

The types of computer Systems have similarly evolved 

over time. For example, early Scientific computers were 

typically Stand alone Systems designed to carry out relatively 

Specific tasks and required relatively knowledgeable users. 

AS computer Systems evolved into the business arena, main 

frame computers emerged. In mainframe Systems, users 

utilized “dumb' terminals to provide input to and to receive 

output from the mainframe computer while all processing 

was done centrally by the mainframe computer. AS users 

desired more autonomy in their choice of computing Services, personal computers evolved to provide processing capability on each users desktop. More recently, personal 

computers have given rise to relatively powerful computers 

called Servers. Servers are typically multi-processor com 

puters that couple numerous personal computers together in 

a network. In addition, these powerful Servers are also 

finding applications in various other capacities, Such as in 

the communications and Internet industries. 

Computers today, Such as the personal computers and 

Servers discussed above, rely on microprocessors, associated 

chip Sets, and memory chips to perform most of their 

processing functions. Because these devices are integrated circuits formed on Semi-conducting Substrates, the techno 

logical improvements of these devices have essentially kept 

pace with one another over the years. In contrast to the 

dramatic improvements of the processing portions of the 

computer System, the mass Storage portion of the computer 

System has experienced only modest growth in Speed and 

reliability. As a result, computer Systems failed to capitalize 

fully on the increased Speed of the improving processing 

Systems due to the dramatically inferior capabilities of the 

mass data Storage devices coupled to the Systems. 

There are a variety of different memory devices available 

for use in microprocessor-based Systems. The type of 

15 

25 

35 

40 

45 

50 

55 

60 

65 

2 

memory device chosen for a specific function within a microprocessor-based System generally depends upon which 

features of the memory are best Suited to perform the 

particular function. There is often a tradeoff between Speed and cost of memory devices. Memory manufacturers pro vide an array of innovative, fast memory chips for various 

applications. Dynamic Random Access Memory (DRAM) 

devices are generally used for main memory in computer 

Systems because they are relatively inexpensive. When 

higher data rates are necessary, Static Random Access 

Memory (SRAM) devices may be incorporated at a higher 

cost. To Strike a balance between Speed and cost, computer 

Systems are often configured with cache memory. Cache 

memory is a special high-speed Storage mechanism which 

may be provided as a reserved Section of the main memory 

or as an independent high-speed Storage device. A memory 

cache is a portion of the memory which is made of the high 

speed SRAM rather than the slower and cheaper DRAM 

which is used for the remainder of the main memory. 

Memory caching is effective since most computer Systems 

implement the same programs and request access to the 

Same data or instructions repeatedly. By Storing frequently 

accessed data and instructions in the SRAM, the System can 

minimize its access to the slower DRAM. 

Some memory caches are built into the architecture of the 

microprocessor themselves, such as the Intel 80486 micro 

processor and the Pentium processor. These internal caches 

are often called level 1 (L1) caches. However, many com 

puter Systems also include external cache memory or level 

2 (L2) caches. These external caches sit between the central 

processing unit (CPU) and the DRAM. Thus, the L2 cache 

is a separate ship residing externally with respect to the 

microprocessor. However, despite the apparent discontinuity 

in nonmanclature, more and more microprocessors are 

incorporating larger caches into their architecture and refer 

ring to these internal caches as L2 caches. Regardless of the 

term used to describe the memory cache, the memory cache 

is simply an area of memory which is made of Static RAM 

to facilitate rapid access to often used information. 

AS previously discussed, frequently accessed data may be 

Stored in the cache memory area of main memory. Thus, the 

portion of the System which is accessing the main memory 

should be able to identify what area of main memory it must 

access to retrieve the required information. A “tag RAM” 

identifies which data from the main memory is currently 

Stored in each cache line. The data is Stored in the cache. The 

values stored in the tag RAM determine whether the actual 

data can be retrieved quickly from the cache or if the 

requesting device will have to access the slower DRAM 

portion of the main memory. The size of the data Store 

determines how much data the cache can hold at any one 

time. The size of the tag RAM determines what range of 

main memory can be cached. Many computer Systems, for 

example, are configured with a 256k L2 cache and tag RAM 

that is 8 bits wide. This is sufficient for caching up to 64 MB 

of main memory. 

In a multi-processor System, each processor may have a 

corresponding main memory, with each main memory reserving a portion for cache memory. The process of 

managing the caches in a multi-processor System is com 

plex. "Cache coherence” refers to a protocol for managing 

the caches of a multi-processor System So that no data is lost or over-written before the data is transferred from a cache to 

a requesting or target memory. Each processor may have its 

own memory cache that is separate from a larger shared 

RAM that the individual processors will access. When these 

multi-processors with Separate caches share a common 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 6 of 12 PageID #: 1592
US 6,823,409 B2 

3 

memory, it is necessary to keep the caches in a State of 

coherence by insuring that any shared operand that has 

changed in any cache is changed throughout the entire 

System. Cache coherency is generally maintained through either a directory based or a Snooping System. In a directory 

based System, the data being shared is placed in a common 

directory that maintains the coherence between the caches. 

The directory acts as a filter through which the processor 

must ask permission to load an entry from the primary 

memory to its cache. When an entry is changed, the direc 

tory either updates or invalidates the other caches with that 

entry. Disadvantageously, directory based coherency Sys 

tems add to the cycle time (previously reduced by the 

implementation of cache memory) by requiring that each 

access to the cache memory go through the common direc 

tory. In typical Snooping Systems, all caches on a bus 

monitor (or Snoop) the bus to determine if they have a copy 

of the block of data that is requested on the bus. Every cache 

has a copy of the Sharing Status of every block of physical 

memory it has. 

Thus, cache coherence aims at Solving problems associ 

ated with sharing data in a multi-processor computer System 

which maintains Separate caches. This problem is further 

promulgated when the computer System includes multiple 

processor buses. In a multi-processor-bus shared memory 

System, a host controller must maintain memory coherency 

throughout all the processor caches. This requires Snoop 

cycles to be run on buses other than the originating bus. A 

Snoop filter may be implemented to minimize the amount of 

Snoop cycles on other buses. To maintain efficiency, the 

Snoop filter should facilitate data look up from the tag RAMs 

as quickly as possible to determine the proper Snoop 

response on the processor bus in a minimal number of clock 

cycles. 

The present invention may be directed to one or more of 

the problems set forth above. 

BRIEF DESCRIPTION OF THE DRAWINGS 

The foregoing and other advantages of the invention will 

become apparent upon reading the following detailed 

description and upon reference to the drawings in which: 

FIG. 1 illustrates a block diagram of an exemplary multi 

processor-bus computer System; 

FIG. 2 illustrates a block diagram of a Snoop filter in 

accordance with the present technique; 

FIG. 3 illustrates a more detailed block diagram of an 

exemplary embodiment of the Snoop filter of FIG. 2; and 

FIG. 4 illustrates a block diagram of an exemplary two 

dimensional doubly linked list structure. 

DETAILED DESCRIPTION OF SPECIFIC 

EMBODIMENTS 

One or more specific embodiments of the present inven 

tion will be described below. In an effort to provide a concise 

description of these embodiments, not all features of an 

actual implementation are described in the Specification. It 

should be appreciated that in the development of any Such 

actual implementation, as in any engineering or design 

project, numerous implementation-specific decisions must 

be made to achieve the developerS Specific goals, Such as 

compliance with System-related and busineSS-related 

constraints, which may vary from one implementation to 

another. Moreover, it should be appreciated that Such a 

development effort might be complex and time consuming, 

but would nevertheless be a routine undertaking of design, 

15 

25 

35 

40 

45 

50 

55 

60 

65 

4 

fabrication, and manufacture for those of ordinary skill 

having the benefit of this disclosure. 

Turning now to the drawings and referring initially to 

FIG. 1, a block diagram of an exemplary multi-processor buS computer System is illustrated and designated generally 

as reference numeral 10. The computer system 10 typically includes one or more processors or CPUs. In the exemplary embodiment, the System 10 utilizes eight microprocessors 

12A-12H. The system 10 utilizes a split bus configuration in 

which the processors 12A-12D are coupled to a first bus 

14A, whereas the processors 12E-12H are coupled to a 

second bus 14B. It should be understood that the processor 

or processors 12A-12H may be of any Suitable type, Such as 

a microprocessor available from Intel, AMD, or Motorola, 

for example. Furthermore, any Suitable bus arrangement 

may be coupled to the processors 12A-12H, Such as a split 

bus (as illustrated), or individual buses. By way of example, the exemplary system 10 may utilize Intel Pentium III 

processors and the buses 14A and 14B may operate at 

100/133 MHz. 

Each of the buses 14A and 14B is coupled to a chip set 

which includes a host controller 16 and a data controller 18. 

In this embodiment, the data controller 18 is effectively a 

data cross bar slave device controlled by the host controller 

16. Therefore, these chips will be referred to together as the 

host/data controller 16,18. The host/data controller 16, 18 is 

further coupled to one or more memory controllers. In this 

particular example, the host/data controller 16, 18 is coupled 

to five memory controllers 20A-20E via five individual bus 

Segments 22A-22E, respectively. Each of the memory con 

trollers 20A-20E is further coupled to a segment of main 

memory designated as 24A-24E, respectively. AS discussed 

in detail below, each of the memory Segments or modules 

24A-24E is typically comprised of dual inline memory 

modules (DIMMs). Further, each memory module 24A-24E 

and respective memory controller 20A-20E may comprise a 

single memory cartridge 25A-25E which may be remov 

able. In the present configuration, data may be Stored in a 

“4+1’ parity Striping pattern wherein one of the memory cartridges 25A-25E is used to provide redundancy. Collectively, the memory cartridges 25A-25E (containing 

the memory modules 24A-24E) make up the RAM memory 

26 of the system 10. Further, the system 10 includes an area 

of cache memory, functionally illustrated as tag RAM 29. 

The host/data controller 16, 18 is typically coupled to one 

or more bridges 28A-28C via an input/output (I/O) bus 27. 

The opposite side of each bridge 28A-28C is coupled to a 

respective bus 30A-30C, and a plurality of peripheral 

devices 32A and 32B, 34A and 34B, and 36A and 36B may be coupled to the respective buses 30A, 30B, and 30C. The 

bridges 28A-28C may be any of a variety of suitable types, 

Such as PCI, PCI-X, EISA, AGP, etc. 

As previously discussed, each CPU 12A-12H may include a Segment of cache memory for Storage of frequently 

accessed data and code. Coherency between the caches 

found in each CPU 12A-12H is further complicated by the 

Split bus configuration Since coherency must be maintained 

between the Separate buses. Also, because requests may 

originate from or be directed to not only one of the CPUs 

12A-12H but also from one of the peripheral devices 

32A-B, 34A-B, or 36A-B, cache coherency must be main 

tained along the I/O bus 27, as well. To maintain coherency, 

a mechanism is provided in the host/data controller 16, 18 to 

efficiently facilitate Snooping of the buses in the present multi-processor/multi-bus system 10. 

The host controller 16 typically includes a processor 

controller (PCON) for each of the processor and I/O bus 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 7 of 12 PageID #: 1593
US 6,823,409 B2 

S 

14A, 14B, and 27. For simplicity, the processor controller 

corresponding to the processor buS 14A is designated as 

“PCONO.' The processor controller corresponding to the 

processor bus 14B is designated as “PCON1.” The processor 

controller corresponding to the I/O buS 27 is designated as 

“PCON2. Essentially, each processor controller 

PCONO-PCON2 serves the same function which is to 

connect the buses which are external to the host controller 16 

(i.e., processor bus 14A and 14B and I/O bus 27) to the 

internal blocks of the host controller 16. Thus, 

PCONO-PCON2 provide the interfaces between the buses 

14A, 14B, and 27 and the host controller 16. 

FIG.2 illustrates a block diagram of a tag control (TCON) 

module 40 which may be used in accordance with the 

present techniques to manage the Snooping process effi 

ciently. That is to say, the TCON module 40 serves as a 

Snoop filter to minimize the number of clock cycles required 

to obtain cache State information and to determine the proper 

Snoop response on the processor or I/O buses 14A, 14B, and 

27. In the present embodiment, the TCON module 40 resides 

within the host controller 16. Alternatively, the TCON 

module 40 may reside in some external device which has 

access to each of the processor buses 14a and 14B and the 

I/O bus 27. 

There are four main functional blocks within the TCON 

module 40. The first block is the request module 42. The 

request module 42 accepts the cycle requests from the 

processor controllers PCONO, PCON1, and PCON2 (FIG. 1) 

and Schedules the cycles to be run through the tag look up. Generally, the request module 42 maintains proper request 

order, prioritizes the input, and establishes each of the 

queues or list structures. The request module 42 insures 

memory coherency through proper cycle order, arbitrates 

access to the memory among the processor and I/O buses 

14a, 14B, and 27, and optimally utilizes the tag look up 

bandwidth. 

AS previously Stated, the request module 42 is responsible for maintaining proper cycle order. This is accomplished 

using content addressable memory (CAM) of new cycles against existing cycles. Generally, the CAM requests pro 

vide a means of insuring that memory WRITEs are only performed when necessary. Because many READ and 

WRITE requests are active at any given time on the memory 

and I/O buses 14A, 14B, and 27, a CAM request is issued 

to insure that the READ and WRITE requests are performed only when necessary and according to proper dependencies. 

When one of the processor controllers PCONO-PCON2 

issues a new cycle request, the cycle checks for cycle order 

dependencies acroSS the existing cycles in the request buffer. 

READS are compared against all WRITEs across all buses 

14A, 14B and 27 to preserve data coherency. Further, 

READS are compared against all READs on the same bus to 

preserve data coherency through proper data order. Only one 

memory READ can be deferred at a time. If a cycle is 

deferrable, Subsequent cycles are retried. Otherwise, the 

Subsequent cycles are held in a parent/child list which 

defines the priority of the dependent requests (or children) 

based on the priority of the primary request (or parent). If, 

for instance, a WRITE request is issued to a particular location in memory, and Subsequently, a READ request is 

issued to that Same location in memory, the request module 

42 will insure that the WRITE request is executed before the 

READ request. When the READ request is submitted, it is 

compared to all outstanding WRITE requests. Because 

READ requests are typically prioritized ahead of WRITE 

requests, without a CAM cycle, the READ could be pro 

cessed before the WRITE request and thus return old or 

15 

25 

35 

40 

45 

50 

55 

60 

65 

6 

invalid data from the memory location. The request module 

42 will be further discussed with reference to FIG. 3. 

The TCON module 40 also includes an active Snoop 

queue (ASQ) 44 which may include one or more buffers 

which contain the indices of all requests which are currently active in the TCON module 40. The indices are used to 

prevent multiple accesses to the same indeX Simultaneously. 

In general, the ASQ 44 includes buffers to maintain a list of 

current cycles that are being processed through the tag RAM 

interface module 46. The ASQ 44 only permits one access 

per cache line indeX at a time to maintain proper cycle order 

and cache State information. In the present embodiment, 

there is one ASQ 44 for each tag RAM interface module 46. 

A single ASQ 44 and tag RAM interface module 46 are 

illustrated in FIG. 2. However, as further explained with 

reference to FIG. 3, it may be advantageous to incorporate 

more than one ASQ 44 and tag RAM interface module 46. 

In the present embodiment, each ASQ 44 permits sixteen 

cycles to be active at a time, with each of these cycles being processed independently. Because the ASQ 44 buffers 

include a fixed number of locations, the number of tag lines 

that are currently active is limited by the size of the buffers 

in the ASO 44. The ASO 44 will be further discussed with 

reference to FIG. 3. 

The tag RAM interface module 46 provides the interface 

with the tag RAM 29. The tag RAM 29 is a separate memory 

Storage device from main memory 26 that keeps track of all 

cachelines in use by the CPUs 12A-12H. Thus, the tag RAM 

29 provides a look-up table for the cache state in cache 

memory. The tag RAM interface module 46 is optimized to 

make efficient use of the bandwidth in the SRAM (i.e., cache 

memory). To minimize the turn around clocks required when 

switching between READ and WRITE requests, the WRITE 

requests are queued So that they may burst directly to the 

SRAM in back-to-back clock cycles. The tag RAM interface 

module 46 also reduces the number of READS to the SRAM 

whenever possible by interpreting the cache data based on 

the cycle characteristics. This may occur if a cycle has a 

non-cacheable attribute or if the cycle is an explicit write 

back. If the cycle has a non-cacheable attribute, there is no 

reason to check the tag RAM Since the requested informa 

tion will not be stored in the cache memory. Conversely, if 

the request is an explicit writeback (which is a cycle initiated 

by a CPU 12A-12H to update the memory 26 with modified 

data), the requested data is known to be in the cache 

memory, without checking the tag RAM 29. When one of 

these cycles occur, the tag RAM interface module 46 may 

Switch from a READ mode to a WRITE mode. The tag 

RAM interface module 46 also minimizes the amount of 

WRITEs to the SRAM whenever the processor performs a 

WRITE to an unallocated address. This preserves the 

address that was allocated prior to the WRITE and alleviates 

the need to perform an unnecessary castout which is a forced 

expulsion of old data from the cache. Finally, the tag RAM 

interface module 46 has programmable State transition Val 

ues that can be tuned to optimize performance based on 

testing. The programmability includes Selecting shared Ver 

SuS owned on a code READ and Shared versus owned on a 

data READ. As can be appreciated by those skilled in the art, 

basic cache protocol dictates that data be one of the four 

types: modified, exclusive, shared, or invalid (MESI). 

“Owned' data refers to data that is either modified or 

exclusive. The functionality of the tag RAM interface mod 

ule 46 will be better understood in light of FIG. 3 and the corresponding description. 

The response module 50 receives the current tag state 

information for a cycle being processed by the ASQ 44. 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 8 of 12 PageID #: 1594
US 6,823,409 B2 

7 

Based on the tag State value, castout Snoops, shared Snoops, 

or invalidate Snoops may be run on one or more of the 

processor buses 14A and 14B to maintain cache coherency. 

A castout Snoop is run when the tag index of the current 

cycle does not match the value in the tag RAM 29. A shared 

Snoop is run when a cacheline must be removed from 

modified or exclusive to shared. An invalidate Snoop is run 

when a cacheline must be removed from modified, 

exclusive, or shared to invalid. After all required Snoops have been completed, the response module 50 updates the 

tag RAM 29 with the new state information and releases the 

slot occupied in the ASQ 44. 

Turning now to FIG. 3, a more detailed description of the 

TCON module 40 and the data path through the TCON 

module 40 is illustrated. As previously discussed, the TCON 

module 40 receives input from the processor controllers 

PCONO-PCON2. Specifically, the processor controllers 

PCONO, PCON1, and PCON2, designated as 52A-52C, 

each monitor a corresponding bus and sends cycle requests 

to the appropriate destination (e.g., I/O or memory). 

Requests from each processor controller 52A-52C are then 

stored in respective READ and WRITE buffers 54A-54C 

and 56A-56C until the requests are dispersed to their proper 

destination. In this embodiment, each READ buffer 

54A-54C and each WRITE buffer 56A-56C can store up to 

sixteen READ and WRITE cycles respectively. A request is 

delivered from the processor controller 52A-52C to the 

READ buffer 54A-54C or WRITE buffer 56A-56C along a 

request path 58A-58C. The request signals which are deliv 

ered along the request path 58A-58C may be buffered for 

fanout purposes. In the present embodiment, the entries into 

the READ and WRITE buffers 54A-54C and 56A-56C may be indexed using bits 3-0 in the request. Bit 4 may be set to 

distinguish between READ requests and WRITE requests 

and therefore provides the routing information to Send the 

request to the proper buffer 54A-54C or 56A-56C. 

AS previously discussed, for each request which is Stored 

in a respective READ buffer 54A-54C, the READ request is advantageously compared against WRITE requests acroSS 

all processor controllers 52A-52C and against all READ 

requests on the same processor controller 52A-52C to 

preserve data coherency through a CAM request. The 

request module 42 controls the CAM requests 62A-62C for 

each of the respective READ buffers 54A-54C. Depending 

on the response from the CAM request 62A-62C, the 

request module 42 may reprioritize the present READ 

request. 

A primary concern in maintaining cache coherency is to 

find the State of the cache line in the System as efficiently as 

possible. Memory READS are generally higher priority than 

memory WRITEs since providing READ requests as 

quickly as possible is advantageous. WRITE requests can 

generally be fulfilled with less time criticality. There may be 

exceptions when, for instance, the WRITE buffers 56A-56C 

become full or reach a threshold or when READ requests are 

dependent on a WRITE request. To provide the requested 

information as quickly as possible, a bypass path 64A-64C 

is provided for each processor controller 52A-52C. Often, 

the READ request can be sent immediately to the tag RAM 

interface module 46 if there are no other requests waiting to 

be run in the system. Each time a READ request is delivered, 

it is sent quickly through the bypass path 64A-64C, thus 

bypassing Storage and compare logic which may be unnec 

essary. On a first clock cycle, the READ request is sent along 

the bypass path 64A-64C. On the next clock cycle, the CAM 

request 62A-62C is performed. If there are no other requests 

at that particular address, no additional management Steps 

15 

25 

35 

40 

45 

50 

55 

60 

65 

8 

are used to maintain coherency. If the CAM request 

62A-62C detects a WRITE request to the same address, the 

response module Sends an abort through the System to cancel 

the READ request which was Sent along the bypass path 

64A-64C. The abort command is sent on the next clock 

cycle. ESSentially, the Speed of the processing of the READ 

requests is made more efficient by forcing the READ request quickly through the System and Subsequently checking to 

see if the READ request is going to be valid. If not, then the 

READ request sent ahead on the bypass path 64A-64C is 

aborted, and the READ request is then prioritized using the 

list Structures and arbitration mechanisms discussed below. 

The request Signals delivered along the bypass path 

64A-64C may be buffered for fanout purposes. 

The TCON module 40 incorporates a plurality of list 

structures to maintain the order of the requests in the READ 

and WRITE bufferS 54A-54C and 56A-56C. The WRITE 

list structures 56A-56C are generally first-in-first-out 

(FIFO) such that requests are processed in the order in which 

they were received, thereby fulfilling the ordering require 

ments for the WRITE requests. This simple processing 

Scheme is generally adequate for the WRITE requests since 

they are generally less time critical than the READ requests. The READ requests are generally more complicated based 

on the prioritization and arbitration Scheme discussed 

herein. Generally, the list Structures are designed as two 

dimensional doubly-linked lists. These lists insure that 

proper cycle order is maintained for each type of transaction. 

The design of the lists allow for both the insertion and 

deletion of a cycle request in a single clock cycle. In 

addition, the READ request list for each processor controller 

52A-52C is designed to immediately rotate a request cycle 

from the head to the tail of the list whenever the required 

resources are unavailable, thus allowing other READ 

requests to gain access to the resources. The list Structures are described in more detail below and discussed further 

with reference to FIG. 4. 

AS previously explained, each processor controller 

52A-52C connects an external bus, Such as the processor 

bus 14A or 14B or the I/O bus 27, to the internal blocks of 

the host controller 16. To identify the individual list 

Structures, the nomenclature described in table 1 may be 

helpful. Table 1 describes requests between the input/output 

(“I”), the processor (“P”), and the memory (“M”). Thus, 

transactions involving one of the CPUs 12A-12H will 

include a P in the name of the list structure, and so forth. 

Thus, the list structure 12P refers to READ requests from 

one of the processors 12A-12H to one of the devices on the 

I/O bus 27. The P2I list structure refers to a WRITE request 

from one of the processors 12A-12H to one of the devices 

on the I/O bus 27. M2P-0 refers to the list structure con 

taining READ requests from the memory 26 to one of the 

processors 12A-12D on the processor bus 14A. P2M-0 

refers to the list Structure wherein one of the processors 

12A-12D on the processor bus 14A wants to WRITE to 

memory 26. For transactions involving the processors 

12E-12H on processor bus 14B, the list structures are 

designated M2P-1 and P2M-1 referring to the corresponding 

READ and WRITE requests between the processors 

12E-12H on processor bus 14B and the memory 26. The 

M2I list structure refers to the READ requests from the 

devices on the I/O bus 27 to the memory 26. The I2M list 

structure refers to WRITE requests from devices on the I/O 

bus 27 to the memory 26. The nomenclature is summarized 

in Table 1, below. 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 9 of 12 PageID #: 1595
US 6,823,409 B2 

9 

TABLE 1. 

List Structure Nomenclature 

List Name Request Type Description 

I2P READ I/O (PCON2) wants to read 

from CPU 

P2I WRITE I/O (PCON2) wants to write to CPU 

M2P-O READ CPU (PCONO) wants to read 

from memory 

P2M-O WRITE CPU (PCONO) wants to 

write to memory 

M2P-1 READ CPU (PCON1) wants to read 

from memory 

P2M-1 WRITE CPU (PCON1) wants to 

write to memory 

M2 READ I/O device (PCON2) wants 

to read from memory 

2M WRITE I/O device (PCON2) wants 

to write to memory 

The list Structures may contain any number of desirable 

locations. In the present embodiment, the P2M and M2P list 

structures contain sixteen locations per PCONO and PCON1. 

The I2M and the M2I list structures each contain sixteen 

locations for PCON2. The P2I and I2P list structures each 

contain 32 locations, sixteen for PCONO and sixteen for 

PCON1. 

Dependency pointers are used to guarantee proper order 

ing of cycles to preserve the memory coherency and proper 

request processing order. The dependencies are established 

at the time a new request is delivered to a READ or WRITE 

buffer 54A-54C or 56A-56C. The dependency status is 

cleared whenever a cycle is removed from the READ or 

WRITE buffers 54A-54C and 56A-56C. A CAM request 62A-62C is performed using the ID of the retired cycle against all dependencies. When a new memory READ 

request is received (i.e., M2P or M2I), a CAM lookup of the 

address is performed against the WRITE request buffer of all 

three PCONs 52A-52C. If a “CAMHIT results, a depen 

dency of the READ to follow the last WRITE for each 

PCON 52A-52C with a CAMHIT is established. Further, 

when a new I2P request is received, a dependency of the 

READ to follow the last cycle, if any, in the P2I list is 

structure established. Finally, when a new P2I request is 

received, a dependency of the WRITE to follow the last 

cycle, if any, in the I2P list structure is established. When a 

cycle is retired out of order due to a CAMHIT, all depen dencies on that cycle are modified to point to the previous cycle in the corresponding list. If there is no previous cycle, 

the dependency Status is cleared. 

The “head” and “tail” pointer structures associated with 

each list Structure indicate the first and last locations in the 

list structure which are filled. When a request is added to the 

list structure, it is Submitted to the tail of the list structure. 

Once a request reaches the head of the list Structure, the 

request will be processed unless it has a dependency in 

which case the request will be moved to the tail of the list 

Structure. 

There are two types of list Structures utilized to maintain 

order of the cycles stored in the READ request buffers 

54A-54C: Active List and Parent Child List. The WRITE 

request buffers 56A-56C utilize only the Active List. The 

Active List contains pointers to cycles that are available for 

arbitration to the ASO 44. The structure is a double linked 

list with a head and tail pointer as previously discussed and 

further discussed with reference to FIG. 4, below. Each cycle 

15 

25 

35 

40 

45 

50 

55 

60 

65 

10 

in the request buffers 54A-54C and 56A-56C corresponds to a location in a next-pointer array and the previous-pointer 

array. READ and WRITE cycles are never combined into 

the same list Structure So the pointers do not need to maintain 

the READ/WRITE bit from the cycle request id (bit 4 in the 

example described above). The Parent Child List contains 

pointers to memory READ cycles that are to the same 

address as another memory READ cycle active in the 

request buffer within the same PCON 52A-52C. The struc 

ture is a double-linked list without a head or tail pointer as 

will be discussed further with reference to FIG. 4 below. If 

a request cycle does not have a parent, it appears on the 

Active List. Conversely, if an active cycle does have a 

parent, it appear on the Parent Child List. A request cycle is 

assigned to the Parent Child List if a READ request is 

dependent on another READ request occurring first. It will 

be doubly-linked below the parent on which it depends. 

Once the parent request is processed, the child request is 

moved to the tail end of the Active List. 

To reduce the latency in an idle System, requests to the tag 

RAM interface 46 proceed immediately when a request is 

received. One clock cycle later, the status of the ASQ 

CAMHIT is valid, indicating whether the requested address 

was found. If true, the abort status of the cycle will be set. 

This results in a slot assigned to the request in the active 

Snoop buffer being marked available. Further, upon comple 

tion of the tag lookup from SRAM, if the cycle was not 

aborted, the tag RAM interface module 46 will transfer the 

results to the TCON response module 50. 

The cycle request arbitration portion of the Request 

module 42 is designed to optimize the utilization of the two 

tag RAM interface 46 and includes a plurality of multiplex 

ors. The present embodiment illustrates a System wherein 

the even and odd addresses of each request have been 

Separated to be processed by individual portions of the 

TCON module 40. Thus, the TCON module 40 illustrated in 

FIG. 3 illustrates even and odd arbitration logic (multiplexors, discussed below), even and Odd ASOS (active 

Snoop buffer) 44A and 4.4B and even and odd tag RAM 

interface modules 46A and 46B. In an alternate embodiment, 

a different arbitration configuration and a single ASQ 44 and 

tag RAM interface module 46 may be implemented. Further, 

in another embodiment, it may be advantageous to imple 

ment more than two ASOS 44A and 4.4B and more than two 

tag RAM interfaces 46A and 46B. The arbiters efficiently assign requests for the READ queue and WRITE queue of 

each of the three processor controllers 52A-52C (PCONO, 

PCON1, and PCON2) to the tag RAM interfaces 46A and 

46B. READ requests from one of the three processor con 

trollers 52A-52C bypass the front end list structures and are 

sent immediately to one of the tag RAM interfaces 46A and 

46B via the bypass path 64A-64C prior to performing any 

qualifying checks on the READ. On the next clock, the 

qualifying checks are performed. If a conflict is detected, the 

READ request to the tag RAM interface 46A or 46B is 

aborted. 

READ requests that could not bypass the front and list 

structures are normally arbitrated to the tag RAM interface 

44A or 44B at higher priority than WRITEs since WRITES 

are posted and do not affect System performance. AS previ 

ously discussed, WRITEs are dynamically arbitrated at 

higher priority than READS under two conditions: 1) there 

is a READ cycle that has a dependency upon a WRITE 

cycle; and 2) the number of queued WRITEs has surpassed 

Some programmable threshold. The Second condition may 

be set by the BIOS or firmware to minimize the system delays as a result of a backlog in the WRITE queue. In 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 10 of 12 PageID #: 1596
US 6,823,409 B2 

11 

certain Systems, it may be advantageous, for instance, to 

flush a WRITE queue once there are twelve requests sitting 

in the WRITE buffer. In this case the WRITE buffer will be 

flushed and the WRITE requests will be processed while the 

READ requests, which are normally prioritized higher than 

the WRITE requests, are stalled until either the WRITE 

buffer is emptied or the requests in the WRITE buffer are 

reduced to Some minimum threshold value, Such as four. 

Cycle disbursement may be facilitated as follows. For the 

P2I and the I2P cycle requests (i.e., the WRITE and READ 

requests between PCON2 from the I/O bus and the CPUs 

12A-H) are dispersed to the I/O queue in the order that the 

cycles are received. This is illustrated in FIG. 3 by arbiters 

70 and 72 which may be multiplexors, for example. The 

arbitration Scheme for requests to main memory 26 is more 

complicated. For memory access arbitrations, there are two 

levels of arbitration for both the even and odd active buffers: 

“intra-PCON” and “inter-PCON." Generally, a first multi 

plexor 74 is provided for each of the remaining list 

structures, as with the I2P and P2I structures 70 an 72. The 

multiplexor 74 cycles the requests through from the corre 

sponding READ or WRITE buffer 54A-54C or 56A-56C in 

the order in which they are received. Next, the requests are 

divided based on their even or odd address. Thus, even and 

odd arbitration occurs independently. The next arbitration 

mechanism, here a multiplexor 76, arbitrates between all 

requests from one particular processor controller (PCONO, 

PCON1, or PCON2) 52A-52C. The arbitration performed by the multiplexor 76 for each processor controller is 

referred to as intra-PCON arbitration. The intra-PCON arbi 

tration has a four level priority arbitration: high, medium, 

low, and none. High priority may be assigned to those 

WRITE requests which have a READ dependency thereon. 

Medium priority may be assigned to all other READ 

requests and to WRITE requests when a threshold value is 

exceeded in the list Structures, as previously discussed. Low 

priority may be assigned to all other WRITE requests 

without extenuating circumstances. No priority is assigned if 

the request queue is empty, for example. 

Once the intra-PCON arbitration is settled for a particular 

PCON, the multiplexor 76 will output the highest priority 

request on that particular PCON to an inter-PCON arbitra 

tion mechanism, here a multiplexor 78. The inter-PCON 

arbitration executes a round robin arbitration between the 

three requesting agents (PCONO, PCON1, and PCON2). 

Each multiplexor 78 checks each request from PCONO, 

PCON1, and PCON2 for a high priority request. If one of the 

inputs includes a high priority request, it will be processed 

first. Then the next input is checked. For example, the 

multiplexor 78 may first check the input from PCONO. If the 

request has a high priority, it will be processed through the 

multiplexor first. If it does not, the multiplexor 78 will check 

the request from PCON1. If the request on PCON1 was of 

high priority, it will be processed through the multiplexor 

78. If this request is not high priority the multiplexor 78 will 

check PCON2 to check if there is a high priority on the input of the multiplexor 78. Again, if there is a high priority, the 

request will be processed through the multiplexor 78. The 

proceSS is then repeated Starting again at PCONO, going 

through the medium requests of each of the PCON channels, 

and then repeating again for the low priority requests. AS 

each request is processed through the multiplexor 78, it is 

sent to a respective ASQ 44A or 44B. The ASQ cycle tracker 

maintains a list of current cycles that are being processed 

through the tag RAM interface 46A or 46B as previously 

discussed. 

FIG. 4 illustrates an exemplary two dimensional, doubly 

linked list structure 90 (e.g. M2P-0, P2M-0, M2I, etc.), as 

15 

25 

35 

40 

45 

50 

55 

60 

65 

12 

previously described with reference to FIG. 3. The list 

Structure 90 includes the proper ordering for the processing 

of each of the requests in the respective read and write 

buffers 54A-54C and 56A-56C. Each list structure 90 

includes a head pointer 92 and a tail pointer 94 to insure that 

proper cycle order is maintained. The head and tail pointers 

92 and 94 associated with each list structure 90 indicate the 

first and last locations in the list structure 90 which are filled 

with requests (READ or WRITE, depending on the particu 

lar list structure 90). Thus, when a request is linked (or pointing to) the head pointer 92, as with request A in FIG. 

4, that request is the next request to be processed. When a 

request is added to the list structure 90, it is submitted to the 

tail of the list Structure. Once a request reaches the head of 

the list Structure, the request will be processed unless it has 

a dependency in which case the request will be moved to the 

tail of the list structure, as will be described below. 

The list structure 90 includes an Active List 96 and a 

Parent Child List 98. The Active List 96 contains pointers to 

cycles that are available for arbitration to the ASQ 44. The 

Active List 96 of the list structure 90 is a double linked list 

with a head and tail pointer 92 and 94. Each cycle in the 

request buffer corresponds to a location in a next-pointer 

array and the previous-pointer array. For instance, Request 

A is linked to the Head Pointer 92, as well as Request B. On 

a first transition, Request A will be processed and the link 

from Request B to Request A will be replaced with a link 

from Request B to the head pointer 92. On the next 

transition, Request B will be processed since it is now linked 

to the head pointer 92. The design of the list structure 90 

allows for both the insertion and deletion of a cycle request in a single clock cycle. Thus, if for instance, Request B is 

cancelled, it will be removed from the list structure 90, and 

on the same transition, request C will be linked to Request 

A. In addition, for a list structure associated with a READ 

request the list is designed to immediately rotate a request 

cycle from the head to the tail of the list whenever the 

required resources are unavailable, thus allowing other 

READ requests to gain access to the resources. 

The Parent Child List 98 of the list structure 90 manages the dependencies associated with particular requests with 

need to be performed in a particular order. A request cycle 

is assigned to the Parent Child List 98, if the request is to the 

Same address as another request occurring first and it will be 

doubly linked below its parent on which it depends. Depen dency pointers are used to guarantee proper ordering of 

cycles to preserve the memory coherency and proper pro 

gram order. The dependencies are established through the 

CAM requests 62A-62C at the time a new request is 

delivered to a READ or WRITE buffer 54A-54C or 

56A-56C, as previously discussed. The dependency status is 

cleared whenever a cycle is removed from the READ or 

WRITE bufferS 54A-54C and 56A-56C. The Parent Child 

List 98 contains pointers to memory READ cycles that are 

to the same address as another memory READ cycle active 

in the request buffer within the same processor controller 

(PCONO-2) 52A-52C. The structure is a double linked list 

without a head or tail pointer. In the exemplary list Structure 

illustrated in FIG. 4, Request D is dependent on Request C, 

and Request E is dependent on Request D. Each request is 

doubly linked and thus points to the proceeding and Subse 

quent requests. AS with the Active List 96, when a request 

is retired out of order due to a CAMHIT, for example, all 

dependencies on that cycle are modified to point to the 

previous cycle in the corresponding list. Thus, if Request D 

is cancelled, Request E will be linked to Request C. If there 

is no previous cycle, the dependency Status is cleared. 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 11 of 12 PageID #: 1597
US 6,823,409 B2 

13 

If a Request does not have a parent, as with Requests A, 

B, and C, it appears on the Active List 96. Conversely, if a 

Request does have a parent, as with Requests D and E, it 

appears on the Parent Child List 98. Once the parent request is processed, the child request will be moved to the tail end 

of the Active List 96. Thus, in the present example, once 

Request C is processed, Request D will be moved to the end 

of the Active List 96. 

While the invention may be susceptible to various modi 

fications and alternative forms, specific embodiments have 

been shown by way of example in the drawings and will be 

described in detail herein. However, it should be understood 

that the invention is not intended to be limited to the 

particular forms disclosed. Rather, the invention is to cover 

all modifications, equivalents and alternatives falling within 

the Spirit and Scope of the invention as defined by the 

following appended claims. 

What is claimed is: 

1. A computer System comprising: 

a host controller; 

a first processor bus coupled between the host controller 

and a first processor; 

a Second processor bus coupled between the host control 

ler and a Second processor, 

a random access memory (RAM) coupled to the host 

controller via a memory bus, the RAM comprising a 

portion of Static memory and a portion of dynamic 

memory; and 

a coherency control module operably coupled to the first 

processor bus and the Second processor bus and com 

prising: 

a request module configured to receive requests from 

the first processor bus and the Second processor bus 

and to maintain proper ordering of the requests from 

each processor bus, 

an active Snoop queue (ASQ) module coupled to the 

request module and configured to maintain a list of 

requests currently being processed and to prevent 

Simultaneous multiple accesses to a single address in 

the static portion of the RAM; and 

a Static RAM interface module configured to acceSS an 

address look-up table corresponding to data Stored in 

the static portion of the RAM. 

2. The computer System, as Set forth in claim 1, compris ing an input/output (I/O) bus coupled between the host 

controller and a plurality of I/O devices, wherein the I/O bus 

is operably coupled to the coherency control module and 

wherein the request module is configured to receive requests 

from the I/O bus. 

3. The computer System, as Set forth in claim 1, wherein 

the coherency control module is located within the host 

controller. 

4. The computer System, as Set forth in claim 1, wherein 

the coherency control module comprises a plurality of list 

Structures corresponding to the first processor bus and the 

Second processor bus. 

5. The computer system, as set forth in claim 4, wherein 

the list Structures comprise two-dimensional doubly-linked 

lists with head and tail pointers. 

15 

25 

35 

40 

45 

50 

55 

14 

6. The computer system, as set forth in claim 5, wherein 

the list Structures comprise dependency linkS. 

7. The computer system, as set forth in claim 4, wherein 

the request module comprises a plurality of bypass paths 

configured to provide a direct request path from the first and 

Second processor buses to the Static RAM interface module, 

thereby bypassing the list Structures. 

8. The computer system, as set forth in claim 1, wherein 

the active Snoop queue module comprises a plurality of 

active Snoop queues, each active Snoop queue configured to 

maintain a list of requests currently being processed and to 

function independently with respect to each other. 

9. The computer system, as set for the in claim 1, wherein 

the static RAM interface module comprises a plurality of 

static RAM interfaces, each static RAM interface corre 

sponding to a Segment of the Static portion of the RAM. 

10. A coherency control module configured to control 

access to cache memory in a computer System, the coher 

ency control module comprising: 

a request module configured to receive requests from a 

plurality of buses in a computer System and to maintain 

proper ordering of the requests from each bus, 

an active Snoop queue (ASQ) module coupled to the 

request module and configured to maintain a list of 

requests from all of the buses currently being processed 

and to prevent multiple accesses to a single address in 

the cache memory Simultaneously; and 

a Static RAM interface module configured to access an 

address look-up table corresponding to data Stored in 

the cache memory. 

11. The coherency control module, as set forth in claim 

10, wherein the plurality of buses comprise processor buses. 

12. The coherency control module, as Set forth in claim 

10, wherein the coherency control module comprises a 

plurality of list Structures corresponding to the first proces 

Sorbus and the Second processor bus. 

13. The coherency control module, as set forth in claim 

12, wherein the list Structures comprise two-dimensional 

doubly-linked lists with head and tail pointers. 

14. The coherency control module, as set forth in claim 

13, wherein the list Structures further comprise dependency 

linkS. 

15. The coherency control module, as set forth in claim 

12, wherein the request module comprises a plurality of 

bypass paths configured to provide a direct request path 

from the first and second processor buses to the static RAM 

interface module, thereby bypassing the list Structures. 

16. The coherency control module, as set forth in claim 

10, wherein the active Snoop queue module comprises a 

plurality of active Snoop queues, each active Snoop queue 

configured to maintain a list of requests currently being 

processed and to function independently with respect to each 

other. 

17. The coherency control module, as set forth in claim 

10, wherein the static RAM interface module comprises a 

plurality of static RAM interfaces, each static RAM inter 

face corresponding to a Segment of the Static portion of the 

RAM. 

Case 2:24-cv-00021-JRG Document 44-11 Filed 06/07/24 Page 12 of 12 PageID #: 1598