EXHIBIT 6

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 1 of 8 PageID #: 117
USOO6871264B2 

(12) United States Patent (10) Patent No.: US 6,871,264 B2 

Soltis, Jr. (45) Date of Patent: Mar. 22, 2005 

(54) SYSTEM AND METHOD FOR DYNAMIC 6,381,682 B2 4/2002 Noel et al. .................. 711/153 

PROCESSOR CORE AND CACHE 6,438,653 B1 * 8/2002 Akashi et al. ... 711/128 

PARTITIONING ON LARGE-SCALE 6,460,122 B1 10/2002 Otterness et al. ........... 711/154 

MULTITHREADED, MULTIPROCESSOR 6,604,174 B1 8/2003 Dean et al. ................. 711/131 

INTEGRATED CIRCUITS 6,681,296 B2 1/2004 Liao et al. .................. 711/129 

(75) Inventor: Ryd C. Soltis, Jr., Fort Collins, CO * cited by examiner 

(73) Assignee: Hewlett-Packard Development Primary Examiner Mano Padmanabhan 

Company, L.P., Houston, TX (US) ASSistant Examiner Pierre M. Vital 

(*) Notice: Subject to any disclaimer, the term of this (57) ABSTRACT 

patent is extended or adjusted under 35 

U.S.C. 154(b) by 194 days. A processor integrated circuit capable of executing more 

than one instruction Stream has two or more processors. 

(21) Appl. No.: 10/092,645 Each processor accesses instructions and data through a 

(22) Filed: Mar. 6, 2002 cache controller. There are multiple blocks of cache 

O O memory. Some blocks of cache memory may optionally be 

(65) Prior Publication Data directly attached to particular cache controllers. The cache 

US 2003/0172234 A1 Sep. 11, 2003 controllers access at least Some of the multiple blocks of 

7 cache memory through high Speed interconnect, these (51) Int. Cl." ................................................ G06F 12/08 blocks being dynamically allocable to more than one cache (52) U.S. Cl. ....................... 711/122; 711/123; 711/129; 711/143 controller. A resource allocation controller determines which 

(58) Field of Search ......................... 711/118-120, 122, S.S. NS, in RSR 

711/129, 133, 143, 153-154, 173; 712/13-15; controllers and cache memory blocks are associated with 709/226, 104 Second level cache, each processor accesses the Second level 

(56) References Cited cache controllers upon missing in a first level cache of fixed 

U.S. PATENT DOCUMENTS 

size. 

5,809,537 A * 9/1998 Itskin et al. ................ 711/146 11 Claims, 3 Drawing Sheets 

/* 

Processor Processor Processor Processor 

Yoo Y100 00 100 02 102 O2 102 O First Lewe First ewel First Lewe First level 

Cache Cache Cache Cache 

10 110 110 10 

Secord Second Second soon? level level level level Cache Cache Cache Cache Conto Control Control Cotro: 

20 

High Speed interconnect 

9 a. is a 9 a. g a so 9 a. 9 s x s cs & s > 3 : S: 5 : 5: 5; St s s 

SO Sc SO SO SO SO SO SC 

Y Y22 24 S12, S2, N22 24 22 24 

Memory interface 

140 

132 Allocation Control 

Partition Control 130 

 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 2 of 8 PageID #: 118
U.S. Patent Mar. 22, 2005 Sheet 1 of 3 US 6,871,264 B2 

98 

Processor Processor Processor 

i 

Yoo Y100 100 E. 

102 102 102 

First Level First Level First Level First level 

Cache Cache Cache 

110 110 10 10 

COO 

Level Level 

Cache Cache 

Control Control Control 

20 

High Speed interconnect 

22 24 122 124 

132 Allocation Control 

Partition Control 

Figure 1 

Memory interface 

130 

140 

 

 

 

 

 

 

 

 

 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 3 of 8 PageID #: 119
U.S. Patent Mar. 22, 2005 Sheet 2 of 3 US 6,871,264 B2 

198 19 

Cache Data Ram Cache Data Ram 215 

TAG Ram TAG Ran 

Interconnect interconnect 

interface interface 

Upper 

Level 

Memory 

Interface 

206 

55 Sg 

3 K 

222 220 2 230 

5 218 

Hit logic S. * ||216 8 E ||216 C 

Z C) 3 Writeback 8 

() s 2214 Queue 2 214 s 5 E onitor (5 

O 219 O 219 OWer 

Level Level 212 

Interface 220 interface 

 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 4 of 8 PageID #: 120
U.S. Patent Mar. 22, 2005 Sheet 3 of 3 US 6,871,264 B2 

-300 

Monitor Cache 

Performance 

Determine 

Desired Cache 

Allocation 

Configure Partition 

Allocation Table 

Partition System: 

Stop OS in Each 08 

Partition 

Allocate 

Processors to 10 

Partitions 

Allocate Allocable 

Cache Blocks to 

Processors (& partitions) 

Restart or Boot 14 

OS in Each 

Partition 

Maintain Billing 16 

Records of Time, 

Partitioning, & Fig U6 3 

Cache Allocation 

 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 5 of 8 PageID #: 121
US 6,871,264 B2 

1 

SYSTEMAND METHOD FOR DYNAMIC 

PROCESSOR CORE AND CACHE 

PARTITIONING ON LARGE-SCALE 

MULTITHREADED, MULTIPROCESSOR 

INTEGRATED CIRCUITS 

FIELD OF THE INVENTION 

The invention pertains to the field of design and packag ing of large, complex, integrated circuits Such as multipro 

ceSSor circuits. In particular, the invention relates to an 

apparatus and method for dynamically repartitioning Mul 

tiple CPU integrated circuits so that critical-path threads 

may receive needed resources and System performance may thereby be optimized. 

BACKGROUND OF THE INVENTION 

Modern integrated processor circuits of high performance 

are fabricated with at least Some cache memory on the 

processor integrated circuit. Typically cache is designed as 

multiple blocks of memory cells, together with control logic. 

Some of these circuits have been designed with bonding options Such that a portion of cache may be disabled; a 

technique that permits product differentiation as well as Sale 

of partially defective circuits. Some of these circuits also 

have spare blocks of memory that can be substituted for 

defective Sections of cache. Typically cache is designed as 

multiple blocks of memory cells, together with control logic. 

Much modern Software is written to take advantage of 

multiple processor machines. This Software typically is 

written to use multiple threads. Each thread has a Sequence 

of instructions that can be independently Scheduled for 

execution. Typically, at any given time Some threads may be 

in a “wait” mode, where execution is delayed until Some 

other thread completes an action or an external event occurs, 

while other threads may be ready for execution. 

Software is also frequently able to prioritize those threads, 

determining which thread should receive the most resources 

at a particular time. For example, the Windows 2000 

(trademark of Microsoft), VMS (trademark of Compaq Computer), and UNIX operating Systems all maintain thread 

priorities, which are often derived from an administrator-Set 

base priority. These operating Systems use these priorities to 

determine which threads should execute, and to determine an amount of time each thread should execute before it is 

preempted by another thread. 

In a multiple processor machine, each processor may be 

tasked with executing different threads from among those 

threads that are ready for execution. These threads may belong to the same, or a different, application program, or 

may be associated with System taskS. Such machines are 

often capable of doing more useful work than machines 

having a single processor. 

Multithreaded processors are those that have more than 

one instruction counter, typically have a register Set associ 

ated with each instruction counter, and are capable of 

executing more than one instruction Stream. For example, machines are known wherein a single pipelined execution 

unit is timeshared among Several instruction Streams. Since 

the execution unit is timeshared, each instruction Stream 

tends to execute somewhat slowly. Multithreaded machines 

with a timeshared, Single, execution unit appear to Software 

as multiple, independent, processors. 

Machines of SuperScalar performance, having multiple 

processors on Single integrated circuits, where each proces 

15 

25 

35 

40 

45 

50 

55 

60 

65 

2 

Sor is capable of dispatching multiple instructions in Some 

cycles, are known. Machines of this type include the IBM 

Power-4 and the PA 8800. Typically, each processor on these 

integrated circuits has its own dedicated Set of execution unit 

pipelines and cache. Their die area, and therefore cost, for 

execution units is therefore typically much greater than with 

a timeshared multithreaded machine. These SuperScalar multiple-processor circuits are also capable of executing 

multiple threads and can be regarded as a form of high 

performance multithreaded machine. 

Modern processor integrated circuits are frequently fab 

ricated with cache memory. Cache memory offerS Substan 

tially faster access than main memory; but offers that fast 

access only for information found in the cache. Memory 

references that are found in cache are called “hits” in the 

cache, while references not found in cache are called cache 

“misses.” The ratio of cache hits to total memory references 

is the "hit rate,” and is known to be a function of cache Size, 

cache architecture including the number of “ways of asso 

ciativity of the cache, and the nature of the executing thread. 

It is known that cache hit rates can be measured by using 

counters to count cache hits and memory references. Such 

counters can be read and a hit rate computed. It is also 

known that a low hit rate can drastically impair System performance. 

It is known that Some threads require larger cache Size to 

achieve high hit rates than others. It is also known that 

processor performance can be adversely affected, Sometimes 

Seriously, by a low hit rate in cache. It is therefore necessary 

to provide Sufficient cache to Support high hit rates for all or 

most threads if maximum processor performance is to be 

attained. Large cache Sizes are, however, expensive. Manu 

facturers therefore market integrated circuits having similar 

processors with different cache sizes to different markets 

where application programs, and cache requirements, are 

expected to differ. 

Cache of multiple processor integrated circuits is typically 

limited in Size by processing costs. Large integrated circuits 

typically have fabrication cost that is an exponential func 

tion of their circuit area, and in Some circuits as much as half 

of the integrated circuit area is cache and cache memory control circuitry. 

Multiple-processor integrated circuits typically have pre 

determined amounts of cache allocated to each processor. These circuits therefore typically require an amount of total 

cache equal to the number of processors multiplied by the 

cache required to achieve a high hit rate on the most cache 

intensive thread expected to run. 

Multiple-processor and multithreaded machines are 

known that are capable of simultaneously executing multiple operating Systems. These are partitionable machines. 

Typically, each operating System is run on a partition, where 

a partition is assigned one or more processors, Suitable 

Sections of main memory, and other System resources. Each 

partition is typically configured as a virtual machine, which 

may have dedicated disk space or may share disk space with 

other partitions. Machines exist that are capable of running 

Windows NT (Trademark of Microsoft) in one partition, while running UNIX in another partition. Machines also 

exist that are capable of Simultaneously running Several 

copies of the same operating System with each copy running independently in a separate partition. These machines are 

advantageous in that each partition may be dedicated to 

particular users and applications, and problems (including 

System crashes) that arise in one partition need not adversely affect operation in other partitions. 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 6 of 8 PageID #: 122
US 6,871,264 B2 

3 

It is known that execution time on multiple-processor and 

multithreaded machines may be billed according to the 

number of processors, the amount of memory, and the 

amount of disk space assigned to each partition. It is also 

known that one or more multiple-processor or multithreaded 

integrated circuits may be used as processors in partitionable 

machines. 

Nature of the Problem 

It would be advantageous to dynamically allocate cache to 

processors on a multiple processor integrated circuit, includ 

ing on Such integrated circuits that are parts of partitionable machines, So as to provide an amount of cache appropriate 

to each thread, or partition, executing on the System. 

SUMMARY OF THE INVENTION 

A high performance multiple-processor integrated circuit 

has multiple cache units and multiple instruction fetch and 

decode units, where each instruction fetch and decode unit 

is associated with a real or virtual processor. The integrated circuit also has at least one dynamically allocable cache unit, 

and may have additional cache units that are directly con 

nected to particular processors. 

The integrated circuit also has high-speed interconnect 

that permits use of the dynamically allocable cache units by 

more than one real or virtual processor, and a cache alloca 

tion register. Fields of the cache allocation register deter 

mine which real or virtual processor is permitted to acceSS 

the dynamically allocable cache units. 

In an embodiment, the dynamically allocable cache units 

form part of the second level of cache in the system. In this 

embodiment there are four processors, four fixed-size first 

level caches each associated with a processor, four fixed 

allocation Second-level cache blocks, and four dynamically 

allocable Second-level cache blockS. 

The Second level cache System is instrumented with 

hit-rate monitoring apparatus associated with each proces 

Sor. An operating System driver monitors the hit-rate asso 

ciated with each processor and tracks hit rates. Monitored hit 

rates are useful to determine which threads partitions may benefit from having additional cache assigned to them. 

In a particular embodiment, the dynamically-allocable 

Second-level cache blocks are assigned to processors of a 

particular partition of a partitionable machine. Machine time 

on this machine is billed according to how much dynami 

cally allocated cache is allocated to each partition. In this 

embodiment, dynamically allocated cache is assigned at 

boot time or when partitions are reconfigured; partitions may 

be reconfigured according to a Schedule as well as at boot 

time. 

In an alternative, fine grained, embodiment, each thread is 

asSociated with a requested cache allotment. In this 

embodiment, dynamically allocated cache blocks are real 

located at context Switch time Such that performance is 

optimized. In this embodiment, the operating System may 

track hit rates associated with each thread as achieved with 

previously assigned cache allotments, and Set the requested 

cache allotment according to an optimum cache Size for each 

thread. 

When the dynamically allocated cache is deassigned from 

one partition, or thread, and assigned to another, it is first 

purged by writing all "dirty' cache lines to memory, and 

clearing a “valid’ bit for each cache line. In this way, the 

cache is made effectively empty to ensure that data associ 

ated with one partition is not available to another partition. 

BRIEF DESCRIPTION OF THE DRAWINGS 

FIG. 1 is a block diagram of a multiple-processor inte 

grated circuit having multiple blocks of dynamically allo 

cable cache; 

1O 

15 

25 

35 

40 

45 

50 

55 

60 

65 

4 

FIG. 2, a block diagram of a cache System having multiple 

blocks of dynamically allocated cache, for use in a multiple 

processor integrated circuit; and 

FIG. 3, a flow chart illustrating allocation of cache 

memory on a System utilizing the integrated circuit, and 

billing of processor time thereon. 

DETAILED DESCRIPTION OF THE 

EMBODIMENTS 

A partitionable multiple-processor integrated circuit 98 

(FIG. 1) has several processors 100. Each processor per 

forms memory references for instructions data through a first 

level cache 102. Those references that miss in first level 

cache are directed to second level cache controllers 110. 

Each second level cache controller 110 is coupled to a 

high-speed interconnect 120. High-speed interconnect 120 

allows the second level cache controllers 110 to each access 

one or more of a plurality of cache memory blockS 122 and 

124. Of these memory blocks, at least one is an allocable 

cache memory block 124 that may be allocated to any cache 

controller 110. There may, but need not, be one or more 

cache memory blocks 122 for which allocation is fixed. 

Allocation controller 130 determines which, if any, of the 

dynamically allocated cache memory blockS 124 is accessed 

by each cache controller 110. Partition control 132 operates 

to determine which processors are associated with each 

System partition. Partition control 132 and allocation con 

troller 130 therefore together determine the second level 

cache controller 110, processor 100, and system partition 

each allocable cache memory block 122 and 124 is associ 

ated with. 

Cache references that are not located in first level cache 

102, and not located in Second level cache, are directed 

through a memory interface 140 to off-chip main memory 

(not shown). 

In an alternative embodiment of the integrated circuit 196, 

each dynamically allocated cache memory block 198 (FIG. 

2) incorporates data memory 200, tag memory 202, and an 

interface 204 to interconnect 206. Each cache controller 210 

has an interface 212 for receiving memory references that 

miss in lower level cache. Each cache controller 210 also has 

cache control logic as known in the art, including a write 

back queue 214 for tracking cache writes and controlling writeback to main memory or higher level cache through 

upper level memory interface 215, as well as tag logic 218 

and hit logic 216 for determining those references that are 

located in cache. Each cache controller also incorporates hit 

rate monitor logic 219 for measuring cache performance 

including hit rate. The cache controller 210 has local tag 

memory 220 and data memory 222. Tag memory 220 and 

data memory 222 are Sufficiently large that they can provide 

a high hit rate for Some instruction Streams that have Small 

cache requirements. 

Cache controllers 210 connect to interconnect 206, which 

allows them to communicate with dynamically allocated 

cache memory blocks 198 under control of allocation con 

trol 230. Allocation control 230 and interconnect 206 is 

configured by Software to connect Zero, one, or more 

dynamically allocated cache memory blocks 198 to each 

cache controller 210. Each dynamically allocated cache 

memory block 198 may only be accessed by only one cache 

controller 210 at any given time. 

In an alternative embodiment, each cache controller 110 

is provided with Sufficient tag in the cache controller to 

control as many as four cache memory blockS 122 and 124. 

In this embodiment, dynamically allocated cache memory 

blocks 124 contain cache data memory. 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 7 of 8 PageID #: 123
US 6,871,264 B2 

S 

A method 300 (FIG. 3) for managing a computer system built around one or more of the multiprocessor integrated 

circuits 98 (FIG. 1), includes monitoring 302 (FIG. 3) cache 

performance. Monitoring makes use of the hit rate monitor 

219 shown on FIG. 2, and such other cache performance monitor apparatus as may be incorporated into the integrated 

circuits, to make a record of past cache performance of 

partitions, applications, and prior cache allocation. This 

record of past performance under various conditions is used 

to determine 304 a desired System partitioning taking into 

account cache availability on the one or more multiprocessor 

integrated circuits 98. In a particular embodiment, the vol 

ume of past interprocessor communications is also consid 

ered in determining which processors to place in each 

System partition. The determined partitioning is configured 

306 into a partition allocation table. 

The System is repartitioned each time it is booted, and is 

also capable of being dynamically repartitioned at other 

times when repartitoning is appropriate to improve overall 

System performance. Repartitioning requires that any run 

ning operating System in each affected partition be stopped 

308. The processors 100 of each integrated circuit 98 are 

assigned 310 to partitions according to the partition alloca 

tion table. Then, the dynamically allocable cache blocks 124 

are assigned 312 to processors 100 of each partition accord 

ing to the partition allocation table. Next, the operating 

Systems for each partition are booted, or restarted, 314, and 

billing records are maintained 316 of machine time, System partitioning, and cache allocation. These billing records 

permit charging customers according to the number of 

processors and amount of cache assigned to their applica 

tions. 

While the invention has been particularly shown and 

described with reference to particular embodiments thereof, 

it will be understood by those skilled in the art that various 

other changes in the form and details may be made without 

departing from the Spirit and Scope of the invention. It is to 

be understood that various changes may be made in adapting 

the invention to different embodiments without departing 

from the broader inventive concepts disclosed herein and 

comprehended by the claims that follow. 

What is claimed is: 

1. A processor integrated circuit capable of executing 

more than one instruction Stream comprising: 

a first processor, coupled to fetch instructions and acceSS 

data through a first cache controller, 

a Second processor, coupled to fetch instructions and 

acceSS data through a Second cache controller; 

a plurality of cache memory blocks, 

a high-Speed interconnect coupling the plurality of cache 

memory blocks to the first and Second cache controllers 

Such that at least one allocable cache memory block is 

capable of being used by the first and Second cache 

controllers, and 

a resource allocation controller coupled to determine an 

accessing cache memory controller Selected from the 

group consisting of the first and Second cache memory 

controllers, whereby the accessing cache memory con 

troller is allowed to access the allocable cache memory 

block, 

5 

15 

25 

35 

40 

45 

50 

55 

60 

6 

wherein the cache memory blocks are usable by the cache 

controllers to Store data and instructions fetched from a 

random-access memory. 2. The processor integrated circuit of claim 1, further 

comprising a plurality of first level cache Systems, wherein 

the first processor fetches instructions and accesses data 

from the first cache controller through a first first level cache 

System, and wherein the Second processor fetches instruc 

tions and accesses data from the Second cache controller 

through a Second first level cache System. 

3. The processor integrated circuit of claim 1, wherein the 

cache memory blocks further comprise cache tag memory. 

4. The processor integrated circuit of claim 1, wherein 

each cache controller is provided with cache hit rate moni toring apparatus. 

5. A method of dynamically allocating cache on a 

multiple-processor integrated circuit, where the multiple 

processor integrated circuit is used in a partitionable multiple-processor System and comprises: 

a plurality of processors each coupled to receive instruc 

tions from a first level cache associated there with, 

a plurality of allocable upper level cache memory blocks, interconnect apparatus for transmitting cache misses at 

each first level cache to upper level cache memory blocks assigned thereto, and 

allocation apparatus for assigning upper level cache 

memory blocks to processors, 

the method comprising the Steps of: 

monitoring past cache performance associated with pro 

ceSSorS and partitions, 

determining desired processor to partition and upper level 

cache block allocations to processors, and 

repartitioning the System, the Step of repartitioning the 

System including allocation of upper level cache blockS 

to processors of at least one of the multiple processor 

integrated circuits, 

wherein the upper level cache blocks are usable to Store 

data and instructions fetched from a random-access 

main memory. 

6. The method of claim 5, wherein the upper level cache 

blocks are Second level cache blockS. 

7. The method of claim 5, further comprising the step of 

billing customers according to processor time and allocated 

cache. 

8. The method of claim 5, wherein the multiple processor integrated circuit further comprises a plurality of non 

allocable cache memory blockS. 

9. The method of claim 5, wherein the interconnect 

apparatus further comprises a plurality of upper level cache 

controllers, and where each upper level cache controller is 

capable of controlling operation of the allocable cache 

memory blocks as a writeback cache. 

10. The method of claim 5, wherein each upper level 

allocable cache block further comprises tag memory and 

cache data memory. 

11. The method of claim 10, further comprising the steps of Stopping execution of operating Systems in each partition, 

and restarting execution of operating Systems in each 

partition, and wherein the System is capable of being rep 

artitioned without rebooting each operating System. 

k k k k k 

Case 2:23-cv-00445-JRG Document 1-7 Filed 09/27/23 Page 8 of 8 PageID #: 124