US007584330B2
`
`US 7,584,330 B2
`(10) Patent No.:
`a2) United States Patent
`McKinneyetal.
`(45) Date of Patent:
`Sep. 1, 2009
`
`
`(54) MULTI-PROCESSOR DATA COHERENCY
`
`(75)
`
`Inventors: Arthur C. McKinney, Madison, AL
`(US); Charles H. McCarver, Jr.,
`Huntsville, AL (US); Vahid Samiee,
`Austin, TX (US)
`
`(73) Assignee:
`
`Intergraph Hardware Technologies
`Company, Las Vegas, NV (US)
`
`4,868,738 A
`4,934,764 A
`5,055,999 A
`5,067,071 A
`5,077,736 A
`
`9/1989 Kishetal. veces 364/200
`6/1990 Leitermannetal. ......... 312/111
`10/1991 Franketal. ..cceece 711/163
`11/1991 Schanin et all.
`.......000... 710/113
`12/1991 Dunphy, Jr.et al.
`........ 371/10.1
`
`(Continued)
`
`(*) Notice:
`
`Subject to any disclaimer, the term ofthis
`patent is extended or adjusted under 35
`US.C. 154(b) by 148 days.
`
`EP
`
`FOREIGN PATENT DOCUMENTS
`/
`7/1995
`
`0 661 651
`
`(21) Appl. No.: 10/886,231
`
`(22)
`
`Filed:
`
`Jul. 7, 2004
`
`(65)
`
`Prior Publication Data
`US 2005/0188009 Al
`Aug. 25, 2005
`
`Related U.S. Application Data
`
`(63) Continuation of application No. 10/037,129, filed on
`Jan. 4, 2002, now abandoned, which is a continuation
`of application No. 08/802,827, filed on Feb. 19, 1997,
`now Pat. No. 6,374,329.
`
`(60) Provisional application No. 60/011,979,filed on Feb.
`20, 1996, provisional application No. 60/011,932,
`filed on Feb. 20, 1996.
`
`(51)
`
`Int. Cl.
`(2006.01)
`GO6F 12/08
`(52) U.S.C. ieee eeeeeeeeeeeeeeeeeeeeen 711/146; 711/144
`(58) Field of Classification Search ..............000 None
`See application file for complete search history.
`.
`References Cited
`U.S. PATENT DOCUMENTS
`
`(56)
`
`4,394,731 A
`4,426,688 A
`4,484,267 A
`4,710,926 A
`4,745,524 A
`
`7/1983 Fluscheet al. «.........0... TLL/L45
`
`1/1984. Moxley. o....ssseeeeeeeeeee 365/200
`11/1984 Fletcher...
`eee 711/124
`
`
`12/1987 Brown etal. oe 371/9
`5/1988 Patton, III .........c eee 361/399
`
`(Continued)
`OTHER PUBLICATIONS
`
`Patent Cooperation Treaty, Int’1 Search Report, Int’] Appl. No. PCT/
`US 97/21457, mailed on Apr. 23, 1998, 4 pages.
`
`(Continued)
`
`Primary Examiner—Denise Tran
`(74) Attorney, Agent, or Firm—Sunstein Kann Murphy &
`Timbers LLP
`
`(57)
`
`ABSTRACT
`
`A method for maintaining coherent data in a multiprocessor
`system having a plurality of processors coupled to main
`memory, where each processorhas an internal cache whichis
`externally unreadable outside the processor. The method
`includes requesting data associated with a memory location
`in main memory and determining ifan external cache coupled
`to an application specific integrated circuit associated with a
`secondprocessor containsa referenceto the requested data. A
`snoop cycle is performed on the second processor if the
`external cache has a reference to the requested data, where-
`upon a determination is madeas to whetherthe requested data
`has been modified.
`
`6 Claims, 11 Drawing Sheets
`
`
`Track Data Entering And Exiting First Processor SegmentTo Derive A
`
`
`Status Of Data In Private Cache Associated With First Processor
`
`Segment
`
`I
`Store Status In Extemal Tag Memory Associated With First Processor
`7004
`I
`4006|Receive Request From Processor In Second Procassor Segment For
`Data Associated With Memory Segment
`
`
`1008|Tag Memory indicates That Requested Data &|No
`
`
`
`
`Held Within First Processor Segment?
`
`] ves
`
`SnoopFirst Processor Segment
`1010
`1012|Requested Data Within First Processor Segment?
`
`Tres
`No
`
`
`
`1014[Tag "Modified’ Status Correct? [No
`[ves
`4
`1018
`PostTransaction Of
`Re-Post Request of Data From
`Requested Data From
`Memory Segment,Set Status
`
`
`Processor Segment
`ae Invalid
`
`
`=
`1
`
`SAMSUNG1054
`SAMSUNG 1054
`SAMSUNG v. SMART MOBILE
`SAMSUNGv. SMART MOBILE
`IPR2022-01004
`IPR2022-01004
`
`1002
`
`1016
`
`1
`
`

`

`US 7,584,330 B2
`Page 2
`
`U.S. PATENT DOCUMENTS
`
`5/1992 Parrish etal. «0.0.00... 395/425
`5,117,350 A
`6/1992 Frank etal. 0... 710/100
`5,119,481 A
`. 364/708
`6/1992 Morita
`5,126,954 A
`
`9/1992 Wille et al.
`395/800
`5,151,994 A
`4/1993 Fielder .......cee cece 395/325
`5,201,038 A
`w+ 370/405
`7/1993 Frank etal.
`.
`5,226,039 A
`
`9/1993 Hauck, Jr. wees 708/499
`5,245,563 A
`9/1993 Costaetal. oe. 395/650
`5,247,673 A
`10/1993 Frank etal.
`.
`. 711/163
`5,251,308 A
`11/1993 Sindhuetal.
`. 395/425
`5,265,235 A
`.
`12/1993 Costa etal.
`. 711/206
`5,274,789 A
`.
`1/1994 Frank etal.
`. 370/403
`5,282,201 A
`3/1994 Frank etal. 0... 711/202
`5,297,265 A
`5/1994 Kaufman et al.
`............ 718/102
`5,313,647 A
`8/1994 Frank etal.
`....
`. 711/163
`5,335,325 A
`
`8/1994 Frank etal.
`.
`. 711/206
`5,341,483 A
`
`8/1994 Keeley etal.
`..
`. 395/800
`5,341,508 A
`. BI/61
`10/1994 Sample etal.
`5,352,123 A
`
`. 395/800
`12/1994 Gove etal. ..
`5,371,896 A
`wee 395/575
`2/1995 Shah ..........
`5,390,326 A
`
`we 711/148
`2/1995 Hunteretal.
`5,394,555 A
`
`4/1995 Marietta 0.0...
`eee 377/64
`5,406,607 A
`6/1995 Hvasshovéd.....
`w+ 395/600
`5,423,037 A
`
`. 707/205
`9/1995 Nelsonetal.
`5,452,447 A
`...
`. TAL/113
`2/1996 Solton etal.
`5,493,728 A
`
`
`4/1996 Kandasamyet al.
`.
`wee T14/6
`5,513,314 A
`.........
`. 707/201
`8/1996 Steely, Jn.
`5,551,048 A
`. 395/800
`9/1996 Watsonetal.
`5,560,027 A
`
`wee 710/5
`11/1996 Stager ........
`5,574,944 A
`4/1997 Brayton et al.
`.
`. 395/468
`5,623,628 A
`
`.
`. 711/145
`5/1997 Laudon etal.
`5,634,110 A
`7/1997 Miller etal.
`. 707/200
`5,649,194 A
`. 707/104
`10/1997 Miller etal.
`5,675,787 A
`
`
`. 711/145
`10/1997 Laudon ......
`5,680,576 A
`11/1997 Miller etal.
`. 707/10
`5,689,700 A
`.
`5/1998 Blake etal.
`. 711/144
`5,752,264 A *
`. 711/141
`7/1998 Laudonetal.
`5,787,476 A
`
`1/1999 Sell wc.
`. 711/146
`5,860,114 A *
`
`we 714/8
`11/1999 Laudonetal. .
`5,991,895 A
`
`. 712/214
`8/2000 Chamdanietal.
`6,112,019 A
`............. 711/141
`6,631,447 B1* 10/2003 Moriokaetal.
`
`FOREIGN PATENT DOCUMENTS
`
`EP
`GB
`GB
`JP
`JP
`JP
`JP
`JP
`JP
`JP
`WO
`WO
`WO
`WO
`WO
`WO
`
`0 288 636
`21715424
`2 257 273
`94-6
`5 40690
`05040690
`100-2
`101-16
`107-19
`109-7
`WO 95/02307
`WO 95/14279
`WO 95/22111
`WO 95/25306
`WO 96/23268
`WO 96/30847
`
`11/1998
`8/1986
`1/1993
`6/1992
`2/1993
`2/1993
`6/1993
`8/1993
`T1994
`12/1994
`1/1995
`5/1995
`8/1995
`9/1995
`8/1996
`10/1996
`
`OTHER PUBLICATIONS
`
`Patent Cooperation Treaty, Int’l Search Report, Int’] Appl. No. PCT/
`US97/21458, mailed Apr. 23, 1998, 3 pages.
`Patent Cooperation Treaty, Intl Search Report Int’! Appl. No. PCT/
`US 97/21459, mailed on Apr. 23, 1998, 4 pages.
`Patent Cooperation Treaty, Int’l Search Report, Int’] Appl. No. PCT/
`US 97/21460, mailed on Apr. 23, 1998, 5 pages.
`Patent Cooperation Treaty, Int’l Search Report, Int’] Appl. No. PCT/
`US 97/21466, mailed on Apr. 23, 1998, 3 pages.
`
`Patent Cooperation Treaty, Int’1 Search Report, Int’] Appl. No. PCT/
`21733, mailed on Apr. 23, 1998, 3 pages.
`Patent Cooperation Treaty, Int’! Search Report, Int’1 Appl. No. PCT/
`US 97/21734, mailed on Apr. 23, 1998, 4 pages.
`Anderson, T., et al. “Serverless Network File Systems,’ Operating
`Systems Review (SIGOPS), vol. 29, No. 5, Dec. 1, 1995, pp. 109-
`126.
`Carter, J., et al. “Network Multicomputing Using Recoverable Dis-
`tributed Shared Memory,” Proceedings ofthe Spring Computer Soci-
`ety International Conference (COMPCON), San Francisco, Feb.
`22-26, 1993, pp. 519-527.
`Huber, J., et al. “PPFs: A High Performance Portable Paralel File
`System,” Proceedings of
`the
`International Conference
`on
`Supercomputing, Barcelona, Jul. 3-7, 1995, pp. 385-294.
`“Java Dynamic Class Loader,” IBM Technical Disclosure Bulletin,
`vol. 39, No. 11, Nov. 1996, pp. 107-108.
`Lee, E., et al. “Petal Distributed Virtual Disks,” 7” International
`Conference on Architectural Support for Programming Languages
`and Operation Systems, Cambridge, MA, Oct. 1-5, 1996, pp. 84-92.
`Neal, D. “The Harvest Object Cache in New Zealand,” Computer
`Networks and ISDN Systems, vol. 11, No. 28, May 1996, pp. 1415-
`1430.
`Raghavan, G. “A Domain Model of WWW Browsers,” Proceedings
`of Southeastcon, Bringing Together Education, Science and Technol-
`ogy, Tampa, Apr. 11-14, 1996, pp. 436-439.
`Ng. T. “The Design and Implementation of a Reliable Distributed
`Operating System-Rose,” Proc, 1990, pp. 2-11.
`Yeung, D., et al. “MGS A Multigrain Shared Memory System,”
`Computer Architecture News, vol. 24, No. 2, May 1, 1996, pp. 44-55.
`Henskens et al. “Course and Fine Grain Objects in a Distributed
`Persistent Store,’ Object Orientation in Operating Systems, 1993,
`IEEE,pp. 116-123.
`Amaral et al. “A Model for Persistent Shared Memory Addressing in
`Distributed Systems,” Object Orientation in Operating Systems,
`1992, IEEE,pp. 2-11.
`Irelenbusch etal. “Towards a Resilient Shared Memory Concept for
`Distributed Persistent Object Systems,” Procecdings of the 28”
`Annual Hawaii Int’. Conference on System Sciences, 1995, IEEE,
`pp. 675-684.
`Lea et al. “Cool: System Support for Distributed Programming,”
`Communications of the ACM,vol. 36, No. 9, pp. 37-46.
`Wilson, Andrew W., “Organization and. Statisitcal Simulation of
`Hierarchical Multiprocessors,” UMI Dissertation Information Ser-
`vice (1985).
`Li, Kai, “Shared. Virtual Memory on Loosely Coupled Multiproces-
`sors,” Yale University, Department of Computer Science,
`(Sep.
`1986).
`Wilson, Andrew, W.“Hierachical Cache/Bus Architecture for Shared.
`Memory Multiprocessors,” ACM,pp. 244-252 (1987).
`Carter, J.B. et al., “Optimistic Implementation of Bulk Data Transfer
`Protocols,” In Proceedings of the 1989 Signetrics Conference, pp.
`61-69 (May 1989).
`Carter, J.B. et al., “Distributed Operating Systems Based on a Pro-
`tected Global Virtual Address Space,” In the Proceedings ofthe Third
`Workshop on Workstation Operating Systems,
`(WWOS)
`(May
`1992).
`Carter, J.B. et al., “Flex: A Tool for Building Efficient and Flexible
`Systems,”In the Proceedings ofthe Fourth Workshop on Workstation
`Operating Systems (WWOS) (Oct. 1993).
`Carter, John B., “Design of the Munin Distributed Shared Memory
`Station,” To appear in the special issue of the Journal of Parallel and
`Distributed Computing on Distributed Shared Memory (1995).
`Carter, J.B. et al., “Techniques for Reducing Consistency-Related.
`Communication in Distributed Shared Memory Systems,” ACM
`Transactions on Computer Systems, pp. 205-243, vol. 13, No. 3
`(Aug. 1995).
`Carter, J.B. et al., “Reducing Consistency Traffic and Cache Missesin
`the Avalance Multiprocessor,” Universiey of Utah techincal report.
`Tricord Systems, Inc. Web Page, http://www.tricord.com/2/10/10-3-
`96.html, printed May 22, 1997.
`Network Appliance, Inc. Web Page http://www.netapp.com/prod-
`ucts/level3/nfs-html, printed on May 22, 1997.
`
`2
`
`

`

`US 7,584,330 B2
`Page 3
`
`Network Appliance, Inc. Web Page, http://www.netapp.com/prod-
`ucts/level13/ontap.html, printed on May 22, 1997.
`Network Appliance, Inc. Web Page, http://www.netapp.com/prod-
`ucts/level13/windows.html, printed on May 22, 1997.
`Jou et al., “A Scalable Snoopy Coherence Scheme on Distributed
`Shared-Memory Multiprocessors”, Supercomputing ’92, (1992), pp.
`652-660.
`Mudgeet al., “Multiple Bus Architectures”, Computer, (1987), pp.
`42-48.
`Dik et al, “EMPS: The design of an architecture for a distributed
`homogeneous multiprocessor
`system”, Microprocessors
`and
`Microsystems, (1991), vol. 15, No. 4, pp. 187-194.
`Per Stenstrém, “Reducing Contention in Shared-Memory Multipro-
`cessors”, Computer, (1988), pp. 26-36.
`Nayfehet al., The Impact of Shared-Cache Clustering in Small-Scale
`Share-Memory Multiprocessors, IEE Computer Soc. Press, (1996),
`pp. 74-84.
`Laudon, James Pierce, Ph.D., “Architectural and Implementation
`Tradeoffs for Multiple-Context Processors”, Copyright @ 1994 by
`Laudon, JamesPierce, a dissertation, pp. 1-186.
`Heinrich, et al... “The Performance Impact of Flexibility in the
`Stanford Flash Multiprocessor”, appeared in Proceedings of the 6th
`International Conference on Architectural Support for Programming
`Languages and Operating Systems (ASPLOS-VI), San Jose, CA
`(Oct. 1994) pp. 1-12.
`Heinlein,et al., “Integration ofMessage Passing and Shared Memory
`in the Stanford Flash Multiprocessor”, Proceedings of the 6” Inter-
`national Conference on Architectural Support for Programming Lan-
`guages and Operating Systems (ASPLOS), Oct. 1994, pp. 1-13.
`Gustavson, et al., “Overview of the Scalable Coherent Interface”,
`IEEE STD 1596 (1993) pp. 488-490.
`Hagersten, et al., “DDM-A Cache-Only Memory Architecture”,
`IEEE (1992), pp. 44-54.
`Sam Dickey, Contributor, “Convex Takes A RISC on HP”, HP Pro-
`fessional, | P’g.
`Baer, et al., “Architectural Choices for Multilevel Cache Hierar-
`chies”, Proceedingsofthe 1987 International Conference on Parallel
`Processing, (Aug. 17-21, 1987), pp. 257-261.
`Baer, et al., “On The Inclusion Properties for Multi-Level Cache
`Hierarchies”, IEEE (1988) pp. 73-80.
`Brewer, Tony, “A Highly Scalable System Utilizing up to 128 PAA-
`RISC Processors”, Convex Computer Corporation, Proceedings of
`the 40”
`IEEE Computer Society International Conference
`(COMPCON), 1995, pp. 133-140.
`Brewer, et al., “The Evolution of the HP/Convex Exemplar’, IEEE
`(1997), pp. 81-86.
`Chaiken,et al., “LimitLESS Directories: A Scalable Cache Coher-
`ence Scheme”, Appeared in ASPLOS-IV, (Apr. 1991), pp. 1-11.
`Archibald,et al., “An Economical Solution to the Cache Coherence
`Problem”, 1984 IEEE,pp. 355-362.
`Archibald, et al., “Cache Coherence Protocols: Evaluation Using a
`Multiprocessor Simulation Model”, ACM Transactions on Computer
`Systems, vol. 4 (Nov. 1986), pp. 273-298.
`Archibald, “A Cache Coherence Approach for Large Multiprocessor
`Systems”, proceedings of
`the
`International Conference
`on
`Supercomputing, (1988) , pp. 282-290, Copyright @ 1988, Associa-
`tion for Computing Machinery.
`White Paper, “The Dolphin SCI Interconnect” (Feb. 1996), Dolphin
`Interconnect Solutions, pp. 1-16.
`Tomasevic, et al., “The Cache Coherence Problem in Shared-
`Memory Multiprocessors: Hardware Solutions”, IEEE Computer
`Society Press, IEEE (1993) pp. 1-281.
`Wilson, Andrew Wilkins, Jr., “Organization and Statistical Simula-
`tion of Hierarchical Multiprocessors”, 1985, UMI Dissertation Ser-
`vices from ProQuest Company, pp. 1-168.
`Lenoski, Daniel E., “Scalable Shared-Memory Multiprocessing”,
`(1995) by Morgan Kaufmann Publishers, Inc., pp. 1-331.
`Goodman,et al., “The Wisconsin Multicube: A New Large-Scale
`Sache-Coherent Multiprocessor”, proceedings of the 15” Interna-
`tional Symposium on Computer Architecture (1988) pp. 291-300,
`Copyright @ 1988 by IEEE.
`Wilson, et al., “Shared Memory Multiprocessors: The Right
`Approachto Parallel Processing” (1989), IEEE, pp. 72-80.
`
`Weber,et al., “The Mercury Interconnect Architecture: A Cost-effec-
`tive Infrastructure for High-performance Servers”, ISCA (1997)
`Copyright @ 1997 ACM,pp. 98-107.
`Tomasevic, et al., “Hardware Approaches to Cache Coherence in
`Shared-Memory Multiprocessors, Part 1”, IEEE Computer Society
`(Oct. 1994), pp. 52-59.
`Tomasevic, et al., “Hardware Approaches to Cache Coherence in
`Shared-Memory Multiprocessors, Part 2”, IEEE Micro, published by
`IEEE Computer Society, vol. 14, No. 6, pp. 60-66.
`Lenoski, et al., “The Dash Prototype: Implementation and Perfor-
`mance”, 1992 ACM,pp. 92-103.
`Leonski,et al., “The Directory-Based Cache Coherence Protocol for
`the Dash Multiprocessor”, IEEE (1990), pp. 148-159.
`Lovett,et al., “Sting: A CC-NUMA Computer System for the Com-
`mercial Marketplace”, ISCA (1996) Copyright @ 1996 ACM,pp.
`308-317.
`McMillan, etal., “Formal Verification of the Gigamax Cache Con-
`sistency Protocol”, International Symposium on Shared Memory
`Multiprocessing, Tokyo, Japan (Apr. 1991), pp. 242-251.
`Jr., Simoni, Richard T., “Cache Coherence Directories for Scalable
`Multiprocessors” (Mar. 1995), pp. 1-145.
`IEEE Standard for Scalable Coherent Interface (SCI), Microproces-
`sor and Microcomputer Standards Subcommittee of theIEEE Com-
`puter Society, IEEE-SA Standards Board (Mar. 19, 1992), pp. 1-243.
`Gharachorloo, Kourosh, “Memory Consistency Models for Shared-
`Memory Multiprocessors”, A Dissertation, (Dec. 1995), pp. 1-372.
`Joe, et al., “Hierarchy Impact and Performance Evaluation of
`ASURA:A Distributed Shared Memory Multiprocessor” (Aug. 19,
`1992), pp. 1-8.
`Saito, et al., “An Implementation of the Event Correspondent Cache
`Coherency Schemeand Its Performance Analysis” (Jan. 22, 1993),
`pp. 129-136.
`Saito,et al., “The Event Correspondent Cache Coherency Scheme
`and Its Application to Barrier Synchronization” (Aug. 19, 1992), pp.
`9-16.
`Fraser, et al., “An Overview of Asura’s Network with Simulation
`Results” (Aug. 12, 1998), pp. 133-140.
`Agarwal, et al., “Sparcle: An Evolutionary Processor Design for
`Large-Scale Multiprocessors” (Mar. 12, 1993), pp. 1-23.
`Saito, et al., “Event Correspondent Cache Coherence Control
`Scheme Application Example and Basic Performance Thereof” (Jan.
`22, 1993), pp. 1-18.
`Archibald, J. “High Performance Cache Coherence Protocols for
`Shared-Bus Multiprocessors” (Jun. 11, 1986), pp. 1-20.
`Agarwal, et al., “The MIT Alewife Machine: Architecture and. Per-
`formance”, appeard in ISCA (1995), pp. 1-12.
`Heinlein,et al., “Integrating Multiple Communication Paradigmsin
`High Performance Multiprocessors”, Technical Report CSL-TR-94-
`604 (Feb. 10, 1994), pp. 1-30.
`Joe, et al., “An Analytical Model of the Asura System”, computer
`Architecture 99-17 (Mar. 12, 1993), pp. 1-15.
`Joe, et al., “Hierarchical Properties and Evaluation of the “Asura”
`Distributed Shared Memory Multiprocessor System’, Computer
`Architecture 95-1 (Aug. 19, 1992), pp. 1-12.
`Mori, et al., “Overview of the Asura: A Distributed Shared Memory
`Multiprocessor”, Computer Architecture 94-6 (Jun. 12, 1992), pp.
`1-12.
`
`Tilborg, Dr. Andre Van, “Semi-Annual Technical Progress”, Nov.
`1989-Mar. 1990, R&T Project Code: 4331685, Office of Naval
`Research, Code 1133, pp. 1-20.
`Mori, et al., “A Distributed Shared Memory Multiprocessor:
`Asura—Memory and Cache Architectures”, (1993), ACM 0-8186-
`4340-4/93/0011, pp. 740-749.
`Sequent, “Sequent’s NUMA-Q Architecture”, Copyright @ 1997,
`Sequent Computer Systems, Inc., pp. 1-9.
`Sequent, “Sequent’s NUMA-Q SMPArchitecture, How It Works and
`WhereIt Fits In High-Performance Computer Architectures”, Copy-
`right @ 1997, Sequent Computer Systems, Inc., pp. 1-18.
`Saito, et al., “Event Correspondent Cache Coherence Control
`Schemeand Application Thereof to Barrier Synchronization”, Com-
`puter Architecture 95-2 (Aug. 19, 1992), pp. 1-14.
`
`3
`
`

`

`US 7,584,330 B2
`
`Page 4
`
`Goshima,et al., “High-Performance Cache System Supporting Com-
`munication Between Fine-Grain Processors”, Computer Architec-
`ture 101-16, (Aug. 20, 1993), pp. 1-17.
`Goshima,et al., “Virtual Queue: A Message Communication Mecha-
`nism for Massively Parallel Computers”, Computer Architecture
`107-19 (Jul. 22, 1994), pp. 1-17.
`Lenoski, et al., “The Stanford Dash Multiprocessor’, IEEE, (Mar.
`1992), pp. 63-79.
`Moti, et al., “Self-Cleanup Cache Evaluation”, Computer Architec-
`ture 109-7 (Dec. 13, 1994), pp. 1-15.
`Moti, et al., “Proposal for Self-Clean-Up Type Write-Back Cache”,
`Computer Architecture 100-2 (Jun. 11, 1993), pp. 1-13.
`Erickson,C. B., Ph.D., “Design and Evaluation ofA Hierarchical Bus
`Multiprocessor”, Michigan State University, (1991), Dept. of Elec-
`trical Engineering, pp. 1-155.
`Archibald, J.K., “The Cache Coherence Problem in Shared- Memory
`Multiprocessors”, Technical Report (Feb. 6, 1987), Dept. of Com-
`puter Science and Engineering, FR-35, University ofWashington, pp.
`1-215.
`Lenoski, Daniel E., “The Design and Analysis of DASH: A Scalable
`Directory-Based Multiprocessor”, A Disseratation (Copyright @
`1991), pp. 1-173.
`Simoni, Richard Thomas, Jr., Ph.D., “Cache Coherence Directories
`for Scalable Multiprocessors”, A Dissertation (Jul. 1992), pp. 1-145.
`McMillan, Kenneth L., “Symbolic Model Checking: An Approach To
`The State Explosion Problem”, Submitted to Carnegie Mellon Uni-
`versity in Partial Fulfillment of the Requirements for the Degree of
`Dr. of Philosophy in Computer Science (1992), pp. 11-212.
`Pacer Online Electronic Access Service, Pacer Docket Report for
`Case #: 6:04-cv-002 14-LED,Intergraph Hardware Technologies Co.
`v. Hewlett Packard Co., (E.D. Tex. filed May 7, 2004), terminated
`Feb. 2, 2005.
`Pacer Docket Report #: 1, Complaint against Hewlett-Packard Com-
`pany , filed by Intergraph Hardware Technologies Company, Inc.
`(Entered: May 7, 2004).
`Pacer Docket Report #: 29, Amended Answer to Complaint Including
`AmendedAffirmative Defenses and, Counterclaim against Intergraph
`Corporation, Intergraph Hardware Technologies Company, Inc by
`Hewlett-Packard Company (Entered: Jul. 15, 2004).
`Pacer Docket Report #:74, Brieffiled Jntegraph Hardware Technolo-
`gies Company,
`Inc.’s Opening Claim Construction Brief by
`Intergraph Hardware Technologies Company, Inc. (Entered: Nov. 5,
`2004).
`Pacer Docket Report #: 74-3, Exhibit B To Intergraph Hardware’s
`Opening Claim Construction Brief Intergraph Hardware’s Proposed
`Construction And Supporting Evidence (Entered: Nov. 5, 2004).
`Pacer Docket Report #: 74-18, Exhibit E To Intergraph Hardware’s
`Opening Claim Construction Brief—‘The Oxford Encyclopedic
`English Dictionary”, Third Edition, New York, Oxford University
`Press, 1996 (Entered: Nov. 5, 2004).
`Pacer Docket Report #: 74-19, Exhibit F To Intergraph Hardware’s
`Opening Claim Construction Brief—The IEEE Standard Dictionary
`of Electrical and Electronic Terms, Sixth Edition, Published by the
`Electrical and Electronics Engineers, Inc., 1996 (Entered: Nov. 5,
`2004).
`Pacer Docket Report #: 87, Brief filed Intergraph Hardware Tech-
`nologies Company, Inc.’s Reply Claim Construction BriefPursuant
`to Local Patent Rule 4-3(c) by Intergraph Corporation, Intergraph
`Hardware Technologies Company,Inc. (Entered: Nov. 24, 2004).
`Pacer Docket Report #: 93, Memorandum and Opinion, Order: The
`Court interprets the claim languagein the case in the mannerset forth.
`(Entered: Dec. 22, 2004).
`Pacer Docket Report #: 94, Transcript of Markman Hearing Proceed-
`ings held Dec. 8, 2004 at 9:00 AM before Judge Leonard Davis
`(Entered: Jan. 3, 2005).
`Hewlett-Packard, Hewlett-Packard Company’s Preliminary Invalid-
`ity Contentions (Executed/served Oct. 4, 2004).
`Archibald, et al., “4” Evaluation of Cache Coherency Solutions in
`Shared-Bus Multiprocessors,” Draft Article on file with University of
`Washington Department of Computer Science.
`Agarwal, et al., April: A Processor Architecturefor Multiprocessing.
`Proceedings of the 17th Annual International Symposium on Com-
`puter Architecture, Jun. 1990, pp. 104-114.
`
`Agarwal, et al., The MIT Alewife Machine: A Large-Scale Distrib-
`uted-Memory Multiprocessor, MIT/LCS Technical Memo 454,
`1991. Also in Scalable Shared Memory Multiprocessors, Kluwer
`Academic Publishers, 1991.
`Astfalk, et al., “Cache Coherence in the Convex MPP, ”Internal
`HP/CONVEX document, Feb. 24, 1994.
`the Convex SPP2000
`Astfalk,
`et
`al.
`“An
`overview of
`hardware,’Internal HP/CONVEX document, Mar. 19, 1996.
`Astfalk,et al., “The HP/Convex SPP2000 CTIInterconnect,” Internal
`HP/CONEX document, Sep. 27, 1996.
`Brewer, et al., Convex Computer Corporation, “Camelot Coherency
`Specification Version 1.1,’ Internal HP/CONVEX document No.
`700-039430-00, Jan. 28, 1993.
`Brewer, Tony, Brewer, Tony, “Excalibur Architecture Reference,’
`Internal HP/CONVEX document, Revision 2.1, Jun. 1996 (including
`Initial Release, dated Oct. 1994).
`Cheriton et al, ParaDiGM: A highly scalable shared memory multi-
`computer architecture. [EEE Computer, vol. 24 No. 2. Feb. 1991.
`Dolphin SCI Technology, Dolphin SCI Technology, “Dolphin
`Nodechip™Functional Specification,” Internal Dolphin SCI Tech-
`nology document, Aug. 1992.
`Gharachorloo, et al., Memory Consistency and Event Ordering in
`Scalable Shared-Memory Multiprocessors. In Proceedings of the
`17International Symposium on Computer Architecture, pp. 15-16,
`May 1990.
`Gharachorloo, et al., Revision to “Memory Consistency and Event
`Ordering in Scalable Shared-Memory Multiprocessors”. Technical
`Report CSL-TR-93-568, Computer Systems Laboratory, Stanford.
`University, Apr. 1993.
`Hewlett-Packard, HP/CONVEX Computer Corporation, “Exemplar
`SPP1000-Series Architecture,’ Internal HP/CONVEX document
`No. 081-023430-000, First Edition, Nov. 1993.
`Hewlett-Packard, CONVEX Computer Corporation, “Camelot Pro-
`cessor Agent Functional Specification,’
`Internal HP/CONVEX
`document No. 700-033930-000, Nov. 17, 1993.
`Hewlett-Packard, CONVEX Computer Corporation, “Cache Coher-
`ency with CxRing,” Internal HP/CONVEX document, date currently
`unknown.
`Hewlett-Packard, HP/CONVEX Computer Corporation, “Exemplar
`SPP1000-Series Architecture,’ Internal HP/CONVEX document
`No. 081-23430-003, Fourth Edition, May 1996.
`Hewlett-Packard, Hewlett-Packard Company, “Runway Bus Specifi-
`cation,” Internal HP document, Revision 1.30, Dec. 3, 1993.
`Hewlett-Packard, “Excalibur MAC,” Internal HP/CONVEX docu-
`ment, Jan. 21, 1994.
`Hewlett-Packard, “Excalibur Functional Specification,’
`HP/CONVEX document, dated believed to be 1996.
`Hewlett-Packard, Hewlett-Packard Company, “Runway Bus Specifi-
`cation,” Internal HP document, Revision 1.30, Dec. 3, 1993.
`IEEE,
`IEEE Standard for Scalable Coherent
`Interface (SCI)
`(approved Mar. 19, 1992),
`Kuskin,et al., “The Stanford Flash Multiprocessor,” In Proceedings
`of the 21 st International Symposium on Computer Architecture, pp.
`302-313, Chicago, IL, Apr. 1994.
`Lenoski, et al., “Design of the Stanford Dash Multiprocessor,”
`Stanford University, Computer Systems Laboratory Technical
`Report, CSL-89-403 (Dec. 1989).
`Palmer, et al., “Camelot Coherent Memory Controller Functional
`Specification,” Internal HP/CONVEX document No. 700-034 130-
`000, Aug. 1, 1994.
`Rashid, et al., Machine-Independent Virtual Memory Management
`for Paged Uniprocessor and Multiprocessor Architectures (1987).
`Schanin, David J., The Design and Development of a Very High
`Speed. System Bus—The Encore Multimax Nanobus (1986).
`Simoni,et al., Dynamic Pointer Allocation for Scalable Cache Coher-
`ence Directories. In Proceedings of the International Symposium on
`Shared Memory Multiprocessing, pp. 72-81, Apr. 1991. Also in
`Shared Memory Multiprocessing, Norihisa Suzuki (Ed.), pp. 463-
`482, MIT Press, 1992.
`Sterling et al., “4 Performance Evaluation ofthe Convex SPP-1000
`Scalable Shared Memory Parallel Computer,’ Conference on High
`Performance Networking and Computing, Proceedings of the 1995
`ACM/TEEEconference on Supercomputing (1995) at p. 55.
`
`Internal
`
`4
`
`

`

`US 7,584,330 B2
`Page 5
`
`Weber,et al., “The Mercury Interconnect Architecture: A Cost-effec-
`tive Infrastructure for High-performance Servers,” Proceedings of
`the 24th Annnual
`International Symposium on Computer
`Architecure, 1997, at pp. 98-107.
`Weber, Wolf-Dietrich, “Scalable directories for cache-coherent
`shared memory multiprocessors,” Ph.D. Thesis, Stanford University,
`1993, Stanford University Technical Report, CSL-TR-93-557.
`Woodbury, et al., Shared Memory Multiprocessors: The Right
`Approachto Parallel Processing (1989).
`Yeung, et al., How to Choose the Grain Size ofa Parallel Computer.
`MIT-LCR- TR 739, Feb. 1994.
`Lenoski,et al., Scalable Shared-Memory Multiprocessing (Morgan
`Kaufman Publishers 1995).
`Archibald, “A Cache Coherence Approach for Large Multiprocessor
`Systems”, proceedings of
`the
`International Conference
`on
`Supercomputing, 1988, pp. 337-345, Association for Computing
`Machinery. IDS Aug. 17, 2005.
`Lovett et al., “Sting: A CC-NUMA Computer System for the Com-
`merical Marketplace,” ISCA 1996, ACM,pp. 308-317. IDS Aug. 17,
`2005.
`
`Gharachorloo, “Memory Consistency Models for Shared-Memory
`Multiprocessors”, a dissertation, Dec. 1995, Appendix K. IDS Mar.
`28, 2006.
`
`Lenoski et al., “The Stanford Dash Multiprocessor,’ IEEE, Mar.
`1992, pp. 63-79. IDS Mar.28, 2006.
`Erickson, “Design and Evaluation of a Hierarchical Bus Multipro-
`cessor,” Michigan State University thesis dated 1991, Dept. of Elec-
`trical Engineering. IDS Mar. 28, 2006.
`Intergraph Hardware Technologies Company, Inc.’s Opening Claim
`Construction Brief. IDS May 19, 2008.
`Intergraph Hardware Technologies Company, Inc.’s Reply Claim
`Construction Brief Pursuant to Local Patent Rule 4-3(c). IDS May
`19, 2008.
`Memorandum and Opinion, Order. The Court interprets the claim
`language in the case in the manner set forth. (“Markman Hearing”
`claim construction.) IDS May 19, 2008.
`Hewlett-Packard Company’s Preliminary Invalidity Contentions.
`IDS May 19, 2008.
`Breweret al., CONVEX Computer Corporation, “Camelot Coher-
`ency Specification Version 1.1,” Internal HP/CONVEX document
`No. 700-039430- 000, Jan. 28, 1993. Chapter 2. IDS May 19, 2008.
`Hewlett-Packard, “Excalibur MAC,” Internal HP/CONVEX docu-
`ment, Jan. 21, 1994. IDS May 19, 2008.
`Lenoski et al, Scalable Shared-Memory Multiprocessing (Morgan
`Kaufman Publishers 1995), §6.5. Current IDS.
`
`* cited by examiner
`
`5
`
`

`

`(00)nae
`
`
`WINaND3Svwaas|(00)snavx$=(10)snavx|$~(01)
`
`
` 00!OC|Ort
`YOSSII0Nd
`atlQLtwitZi
`
`snavx
`
`
`{(ut)‘(ano(10)“(00))snavx901
`
`(
`
`00)
`
`élo¢l
`
`
`
`(10)sn@ax
`
`
`
`(10)Snax
`
`
`
`(o1)sngax
`
`gzt 92l
`
`
`
`AXOWINAMONIN
`
`00IN3ND3S40IN3NO3S
`
`AYOWIA
`
`
`
`OlLN3ND3S
`
`LLIN3AOIS
`
`|Sls
`
`{(1)‘(0L)‘(ro)‘Coo
`
`)]sngax
`
`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 1 of 11
`
`US 7,584,330 B2
`
`vOL
`
`
`
`(00)SNgax
`
`2IN3N9IS
`
`3IN3K93S
`
`801
`
`
`
`(00)sneax
`
`
`
`
`
`
`
`
`
`
`
`{(tt)“(01)‘(10)‘(00)]snavx
`
`
`
`
`
`
`
`
`
`
`
`(10)‘(00)]snavx
`
`
`
`
`
`‘(00)]snaax
`
`YOSSII0Nd
`
`@IN3ND3S
`
`6
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 2 of 11
`
`US 7,584,330 B2
`
`BUS
`
`ADDRESS
`
`FIG. 2
`
`7
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 3 of 11
`
`US 7,584,330 B2
`
`oo80
`
`AYOWIN
`
`oacoa
`
`COL
`
`€Ola
`
`4iyjoe0SNeax
`=~).
`80¢ohEE
` 8d0/Y0SS3I00%dY3HIOd40OdX¢6
`
`
`SNOILWNISHOD
`
`a.
`z
`
`8
`
`
`
`
`
`

`

`Sep. 1, 2009
`
`Sheet 4 of 11
`
`US 7,584,330 B2
`
`U.S. Patent
`
`90+
`
`COP
`
`vyOld
`
`AlddfS
`
`SS™S—~dYiSSCSYSCS|i
`
`POSSIsid>Sero
`LTBOSSiClr
`a7esdZ0¥—[C—O
`
`
`eee
`OdWSI3401D
`scuvoguaMOd
`OSSD
`Po
`
`WS4019d
`
`80%Oly
`
`souyog
`
`Adds
`
`9
`
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 5 of 11
`
`US 7,584,330 B2
`
`ao
`ha
`=
`=s
`Fe
`eS
`3
`
`CONDITIONER
`
`m~
`la
`=
`S
`=
`SSs
`3
`
`502
`
`POWERCONDITIONER
`
`FIG.5
`
`10
`
`10
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 6 of 11
`
`US 7,584,330 B2
`
`POWERCONDITIONER
`
`CONDITIONER
`
`FIG.6
`
`POWERCONDITIONER
`
`POWER
`
`a y
`
`oO oS
`Fe
`aSoO
`qo
`
`11
`
`

`

`U.S. Patent
`
`US 7,584,330 B2
`
`Sep. 1, 2009
`
`Sheet 7 of 11
`
`
`
`12
`
`

`

`
`
`13
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 9 of 11
`
`US 7,584,330 B2
`
`6Sls
`
`802
`
`CCC
`
`YATIONLNOOD
`
`OVL
`
`
`
`AYOWSAWdVLS,
`
`S06
`
`Ole
`
`JINX
`
`SsSayddqv
`
`SALVAIYd
`
`AHOVD
`
`YAdOONScl202
`
`vO?
`
`VIE
`
`YAHLOYO9d
`
`YOsss90dd
`
`YyaLlLsnld
`
`L06
`
`14
`
`14
`
`
`
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet 10 of 11
`
`US 7,584,330 B2
`
`1002
`
`
`
`Track Data Entering And Exiting First Processor Segment To Derive A
`Status Of Data In Private Cache Associated With First Processor
`Segment
`
`4004
`
`Store Status In External Tag Memory Associated With First Processor
`Segment
`
`1006
`
`Receive Request From Processor In Second Processor Segment For
`Data Associated With Memory Segment
`
`1008
`
`Tag Memory Indicates That Requested Data Is
`Held Within First Processor Segment?
`
`Yes
`
`1010
`
`Snoop First Processor Segment
`
`No
`
`
`
`
`
`1012|Requested Data Within First Processor Segment?
`
`
`
`1014|Tag “Modified” Status Correct?
`
`1016
`
`Post Transaction Of
`Requested Data From
`Processor Segment
`
`Re-Post Request of Data From
`Memory Segment, Set Status
`as Invalid
`
`Fig. 10
`
`15
`
`15
`
`

`

`U.S. Patent
`
`Sep. 1, 2009
`
`Sheet11 of 11
`
`US 7,584,330 B2
`
`1102
`
`Store Data Evicted By The First Processor In External Cache
`Associated With First Processor Segment
`
`4104
`
`Store Status Of Data Evicted By First Processor In External Tag
`Memory Associated With First Processor Segment
`
`4106
`
`Receive Request From Processor In Second Processor Segment
`For Data Associated With Memory Segment
`
`4108
`
`Status Indicates Requested Data Was Evicted From
`First Processor Segment?
`
`No
`
`Status Indicates Requested Data Was Modified And First
`Processor Segment Has Not Re-requested The Data?
`
`OR
`
`External Cache 1110
`
`Status Indicates Requested Data Was Not Modified?
`
`4112
`
`Post Transaction Of Requested Data From
`
`16
`
`

`

`US 7,584,330 B2
`
`1
`MULTI-PROCESSOR DATA COHERENCY
`
`PRIORITY
`
`2
`allows more than four processors to a bus, then cluster size
`referenced herein may be adjusted accordingly.
`
`BRIEF DESCRIPTION OF THE DRAWINGS
`
`This application is a continuation of U.S. application Ser.
`No. 10/037,129, filed Jan. 4, 2002, abandoned, which in turn
`is a continuation of U.S. application Ser. No. 08/802,827,
`filed Feb. 19, 1997, now issued as U.S. Pat. No. 6,374,329,
`which claimspriority from subject matter disclosed in two
`provisional applications entitled HIGH-AVAILABILITY
`SUPER SERVER,having Ser. No. 60/011,979, filed Feb. 20,
`1996, and METHOD AND APPARATUS FOR SIGNAL
`HANDLING ON GTL-TYPE BUSES, having Ser. No.
`60/011,932, filed Feb. 20, 1996. Each of the above described
`applications are hereby incorporated herein by reference.
`
`10
`
`15
`
`FIELD OF THE INVENTION
`
`This inventionrelates to providing high-availability paral-
`lel processing super servers.
`
`20
`
`SUMMARY
`
`The present invention provides a high-availability parallel
`processing server that is a multi-processor computer with a
`segmented memory architecture. The processors are grouped
`into processorclusters, with each cluster consisting of up to
`four processors in a preferred embodiment, and there may be
`up to 5 clusters of processors in a pref