Foundation v. Apple, Inc.

WISCONSIN ALUMNI RESEARCH FOUNDATION, Plaintiff, v. APPLE, INC., Defendant.

14-cv-062-wmc

UNITED STATES DISTRICT COURT FOR THE WESTERN DISTRICT OF WISCONSIN

August 5, 2015

OPINION AND ORDER

In this lawsuit, plaintiff Wisconsin Alumni Research Foundation ("WARF") alleges that defendant Apple, Inc. infringes U.S. Patent No. 5,781,752 (the "'752 patent"), which concerns a "table based data speculation circuit for parallel processing computer." Before the court are the parties' cross-motions for summary judgment and claim construction. (Dkt. ##116, 117.) For the reasons that follow, the court will adopt WARF's proposed construction of the term "prediction" and grant summary judgment to WARF on Apple's counterclaims and defenses based on anticipation under 35 U.S.C. § 102 with respect to U.S. Patent No. 5,619,662 ("Steely" or the "Steely patent"), as well as indefiniteness under 35 U.S.C. § 112 ¶ 2 with respect to claims 5 and 6. In turn, the court will deny Apple's motion for summary judgment based on those same defenses and counterclaims. As for Apple's motion for summary judgment on WARF's claim of willful infringement, the court will deny Apple's motion with respect to any defenses premised on (1) Apple's claim construction, (2) anticipation by Steely, and (3) indefiniteness of claims 5 and 6, but will reserve on Apple's motion in all other respects.

UNDISPUTED FACTS¹

A. The Parties and Overview of This Lawsuit

Plaintiff Wisconsin Alumni Research Foundation ("WARF") is a Wisconsin corporation, with its principal place of business in Madison, Wisconsin. WARF is the owner of the '752 patent. Defendant Apple, Inc. is a California corporation, with its principal place of business in Cupertino, California.

On January 31, 2014, WARF filed suit against Apple alleging infringement of the '752 patent. Apple answered and asserted counterclaims for declaratory judgment of non-infringement and invalidity of the '752 patent. Material to the present motions, Apple contends that claims 1-3, 5, 6, and 9 of the '752 patent are invalid as anticipated by the "Steely patent. Apple also alleges that claims 5 and 6 of the '752 patent are invalid as indefinite.

B. Technology Overview

A modern computer device includes both hardware and software. Hardware typically includes memory, a microprocessor and peripherals, while software typically consists of sequences of instructions or "programs" that run on the hardware. At a general level, the microprocessor is responsible for fetching instructions and data, executing those instructions to modify the data, and then saving the results.² Typically,individual instructions call for the performance of a relatively simple task, such as reading a value from or writing a value to a memory location, or adding, subtracting or comparing two numbers. There are generally three types of software instructions: (1) memory instructions; (2) computing instructions; and (3) control instructions.

Memory instructions are instructions that "when executed, cause data to be loaded into the processing unit from memory or stored from the processing unit to memory." ('752 Patent (dkt. #1-1) 1:38-40.) So-called "LOAD" instructions copy or read a value stored at a memory location specified by an address and return a value. LOAD instructions are also called "data consuming instructions," because they consume data by obtaining data from memory, though as Apple cautions, other types of software instructions also "consume" data. "STORE" instructions, on the other hand, copy or write a value to a memory location specified by an address. For that reason, STORE instructions are also called "data producing instructions," as they produce data by providing data to memory. (Apple similarly points out that other types of instructions "produce" data.) When a STORE instruction executes, it overwrites any value previously stored at that memory location. Both LOAD and STORE instructions are memory instructions.

Generally speaking, software instructions in a program have a predefined "program order," where the processor performs the instructions sequentially. Instructions, however, need not always be executed in the listed order. Instead, they may be executed "out of order." In out-of-order executions, instructions are typically executed when ready -- in other words, based on the availability of their input data, or "operands," rather thana specified program order.³ There are some obvious benefits to permitting instructions to execute out of order. For instance, because some instructions in a program take longer to execute than others, performing instructions in program order may slow processor performance since it requires waiting for earlier instructions to execute before performing later instructions in the program. Out-of-order execution, therefore, may result in increased efficiency since it allows the processor to use free time to execute other instructions that are ready to be processed. On the other hand, out-of-order execution may have a detrimental effect on performance if it leads to errors that require the processor to expend resources to correct.

A key requirement of efficient out-of-order execution, therefore, is that it must yield the same results as would the execution of instructions in program order. This requirement touches on the concept of "instruction dependency." A dependent instruction is one that must wait for the result of an earlier-in-order execution before it can safely execute.⁴ For example, data dependency exists when an earlier-in-order STORE instruction writes data to the same address that is accessed by a later-in-order LOAD instruction. In that situation, the STORE and LOAD must execute in program order for the LOAD to read the correct data from the shared memory address that both instructions access.

In some situations, whether a given LOAD instruction depends on a STORE instruction from an earlier earlier-in-order program step cannot be known until after one or both of the instructions are executed. In other words, the processor lacks sufficient information to resolve whether or not a dependency actually exists. This uncertainty is known as "ambiguous dependency." Ambiguous dependencies may occur, for example, when the memory addresses that must be accessed by a given LOAD or STORE instruction are computed "on the fly" as the program executes. In those circumstances, the processor may have to perform additional computations with data that are not currently available in order to resolve whether one instruction is dependent on another.

To maximize processing speed, however, the processor may elect to execute a LOAD instruction before an earlier STORE instruction. The out-of-order execution of instructions without knowing if there is an actual dependency between them is known as "speculation" or "speculative execution," because the processor is speculating that there is no actual dependency. Speculation can be advantageous if it turns out to be correct (i.e., the LOAD instruction in fact was not dependent on the STORE instruction); then the out-of-order execution will yield the correct result and the performance will improve.⁵ In contrast, if a LOAD instruction is speculatively executed ahead of a STORE instruction of earlier program order and it turns out that the speculation was incorrect (i.e., theLOAD instruction was in fact dependent on the earlier STORE instruction), then the instructions will cause an error -- the prematurely executed LOAD instruction having obtained incorrect or stale data.⁶

In the patent-in-suit, this error is referred to as "mis-speculation," although the Steely patent -- as described below -- refers to it as a "collision." As discussed generally already, and as the patent-in-suit explains specifically, a mis-speculation can be detrimental to processor performance because it requires "the results of the prematurely executed dependent instructions [to] be discarded" or "squashed," and the instruction will need to be re-executed in program order. ('752 patent (dkt. #1-1) 2:46-49; Def.'s PFOFs (dkt. #119) ¶ 33.)⁷

C. The '752 Patent

i. Overview and Prosecution History

The '752 patent, entitled "Table Based Data Speculation Circuit for Parallel Processing Computer," was filed on December 26, 1996, and issued on July 14, 1998. The listed inventors are Drs. Andreas I. Moshovos, Scott E. Breach, Terani N. Vijaykumar, Gurindar S. Sohi. Plaintiff WARF is listed as the original assignee. WARF maintains that the named inventors conceived of the claimed invention no later than December 11, 1995.

During prosecution of the '752 patent, the named inventors provided no prior art to the Patent Office. On October 8, 1997, the patent examiner issued a Notice of References Cited, which listed four pieces of prior art. The patent examiner rejected pending claims 1-2, 6 and 8-11 as anticipated in light of U.S. Patent No. 5,555,432 ("Hinton"). On January 5, 1998, WARF filed a response cancelling pending claims 9 and 10, but arguing that claims 1, 2, 6, 8 and 11 were allowable over Hinton. On February 3, 1998, the examiner allowed those claims.

ii. Objectives and Specification

The '752 patent recognizes that "[t]he performance cost is a function of the frequency that speculation is required, the probability of mis-speculation and the time required to recover from a mis-speculation." ('752 patent at 3:14-18.) The '752 patent also observes that "most data dependent mis-speculations can be attributed to a few static STORE/LOAD instruction pairs," and that mis-speculations typically "exhibit 'temporal locality,'" such that "if one LOAD/STORE pair causes a data mis-speculation at a given point in time, it is highly likely that a later instance of the same pair will soon cause another mis-speculation." (Id. at 3:51-57.) The patent further observes that

The present inventors believe that a relatively limited number of LOAD/STORE pairs will create mis-speculation and so the operation described above

...