Wis. Alumni Research Found. v. Apple Inc.

• Citation: 905 F.3d 1341
• Decision Date: 28 September 2018
• Docket Number: 2017-2265,2017-2380
• Parties: WISCONSIN ALUMNI RESEARCH FOUNDATION, Plaintiff-Appellee v. APPLE INC., Defendant-Appellant
• Court: United States Courts of Appeals. United States Court of Appeals for the Federal Circuit

905 F.3d 1341

WISCONSIN ALUMNI RESEARCH FOUNDATION, Plaintiff-Appellee

v.APPLE INC., Defendant-Appellant

2017-2265

2017-2380

United States Court of Appeals, Federal Circuit.

Decided: September 28, 2018

Morgan Chu, Irell & Manella LLP, Los Angeles, CA, argued for Plaintiff-Appellee. Also represented by Christopher Abernethy, Gary N. Frischling, Alan J. Heinrich, Amy E. Proctor, Jason Sheasby.

William F. Lee, Wilmer Cutler Pickering Hale and Dorr LLP, Boston, MA, argued for Defendant-Appellant. Also represented by Andrew J. Danford, Felicia H. Ellsworth, Lauren B. Fletcher, Keith Syverson.

Before Prost, Chief Judge, Bryson and O'Malley, Circuit Judges.

Prost, Chief Judge.

The Wisconsin Alumni Research Foundation ("WARF") sued Apple Inc. for infringement of U.S. Patent No. 5,781,752 ("the '752 patent"). After a two-week, bifurcated trial, a jury found Apple liable for infringement and awarded over $234 million in damages. The district court denied Apple's post-trial motions for judgment as a matter of law and for a new trial. Because no reasonable juror could have found infringement based on the evidence presented during the liability phase of trial, we reverse the district court's denial of Apple's motion for judgment as a matter of law. With respect to invalidity, we affirm the grant of summary judgment in favor of WARF.

I

The technology at issue relates to how computer processors execute a computer program's instructions. Computer programs are made up of lists of program instructions written in "program order." Although these instructions could be executed sequentially—i.e., in program order—some processors execute program instructions "out-of-order" to improve computer performance.

Of course, when executing instructions out-of-order, the processor must obtain the same result as if it had executed the instructions in program order. This can be complicated by the fact that "data dependencies" may exist between individual program instructions. A data dependence exists between two instructions if one instruction relies upon data produced or modified by an earlier, or "older," instruction in the program order. To illustrate, the parties discuss "store" and "load" instructions that access the same location in memory. Memory can be thought of as a set of places to store data, where each place has an address by which the contents of that place can be accessed. See J.A. 1713 (testimony of Apple's expert, Dr. Colwell). A "store" instruction, or simply a "store," writes data to a given location in memory, over-writing any data that had previously been stored in that memory location. A "load instruction," or "load," reads data from a given memory location and then uses that data to perform some function. Id. at 1714. A data dependence exists between a store instruction and a load instruction if (1) the store instruction appears earlier than the load instruction in the program order; and (2) the store and load instructions will access the same memory location—i.e., the same address—if and when the store and load instructions are executed. In such a scenario, the load instruction depends on the store instruction having been executed first so that the data the load instruction reads from memory is current and correct.

At the time a processor decides whether to allow instructions to execute out-of-order, it may be unclear whether a data dependence exists between given store and load instructions. This is called an "ambiguous dependency." J.A. 1429 (testimony of WARF's expert, Dr. Conte), 1715 (testimony of Dr. Colwell). This ambiguity can occur, for example, if the address where the store instruction will store data has not yet been determined, due to some independent calculation. Without knowing the ultimate storage location, the processor cannot determine whether the store and load instructions will access the same memory location and, thus, cannot determine whether a data dependence exists between those store and load instructions.

Even where an ambiguous dependency exists, the processor may nonetheless choose to execute the potentially dependent load instruction before the store instruction has finished executing. This is called "speculation" because the processor is effectively speculating that no data dependence exists between those store and load instructions. A "mis-speculation" occurs if a data dependence does exist between the two instructions, and the processor executes the dependent load instruction before the store instruction. If a processor correctly speculates—in other words, if the processor correctly guesses that a load instruction is not dependent on an earlier store instruction that has not yet executed—processor performance may be improved because the processor did not needlessly delay execution of that load instruction. J.A. 1431–32 (testimony of Dr. Conte). But, if a processor mis-speculates, the processor essentially has to discard work it has already performed and re-do the work in the correct order. J.A. 1433 (testimony of Dr. Conte), 1717–19 (testimony of Dr. Colwell). This recovery process is called "squashing" or "flushing." J.A. 1433 (testimony of Dr. Conte). As might be expected, mis-speculations do not help processor performance, and may in fact harm performance. In short, while out-of-order execution of instructions with ambiguous dependencies may improve performance in cases where the processor speculates correctly, performance may be decreased by mis-speculation.

One method to minimize mis-speculation is for the processor to make an informed decision as to whether it should speculate. This is called "prediction." This case concerns a particular prediction method used to increase the accuracy of processor speculation such that mis-speculations are minimized.

A

The '752 patent, which expired on December 26, 2016, describes a specific prediction technique for an out-of-order processor. In this case, WARF asserted independent claims 1 and 9, as well as dependent claims 2, 3, 5, and 6. Claim 1 reads:

1. In a processor capable of executing program instructions in an execution order differing from their program order, the processor further having a data speculation circuit for detecting data dependence between instructions and detecting a mis-speculation where a [load] instruction dependent for its data on a [store] instruction of earlier program order, is in fact executed before the [store] instruction, a data speculation decision circuit comprising:

a) a predictor receiving a mis-speculation indication from the data speculation circuit to produce a prediction associated with the particular [load] instruction and based on the mis-speculation indication; and

b) a prediction threshold detector preventing data speculation for instructions having a prediction within a predetermined range.

'752 patent claim 1.¹ Claim 9 reads:

9. In a processor capable of executing program instructions in an execution order differing from the program order of the instructions, the processor further having a data speculation circuit for detecting data dependence between instructions and detecting a mis-speculation where a [load] instruction dependent for its data on a [store] instruction of earlier program order, is in fact executed before the [store] instruction, a data speculation decision circuit comprising:

a) a prediction table communicating with the data speculation circuit to create an entry listing a particular [load] instruction and [store] instruction each associated with a prediction when a mis-speculation indication is received; and

b) an instruction synchronization circuit only instructing a processor to delay a later execution of the particular [load] instruction if the prediction table includes an entry.

'752 patent claim 9.²

According to the claim language, when the data speculation circuit detects a mis-speculation, it sends a mis-speculation indication to a predictor. Id. at claim 1. The predictor then produces a prediction, based on the mis-speculation indication, as to whether a data dependence likely exists between the corresponding load and store instructions. A higher prediction value indicates a greater likelihood of data dependence and, therefore, a greater likelihood that a mis-speculation will occur if those instructions are executed out-of-order. Id. at col. 11 ll. 29–32. The prediction may be "updated based on historical mis-speculations detected by the data speculation circuit." Id. at col. 8 ll. 8–9. Going forward, the predictor "provides a dynamic indication to the data speculation circuit ... as to whether data speculation should be performed." Id. at col. 8 ll. 1–3. And, if the prediction for a given load instruction exceeds a certain "predetermined range," speculation is prevented. Id. at claim 1.

B

The products accused of infringement in this case are Apple's A7, A8, and A8X integrated circuit chips, which include one or more processors. These processors include a Load-Store Dependency Predictor ("LSD predictor"), which is the technology at issue in this case.

The LSD predictor detects data dependences between load and store instructions and uses a prediction table to make predictions based on those dependences. Each entry in the prediction table includes (among other things) a load tag, a store tag, and a prediction (or "counter"). The load tag is generated by taking certain information about a load instruction, such as its address, and creating a 12-bit load tag using a hashing function. Because the load tags are limited to 12 bits, only 4,096 load tags are available. The hashing algorithm uses a one-way hash, meaning that a given load tag cannot be expanded back to the load instruction that generated that load tag. Moreover, based on this hashing algorithm, it is possible for multiple load instructions to hash to the same load tag.

When multiple load instructions hash to the same load tag, it is possible for multiple instructions to update the same prediction in the LSD predictor's prediction table....