Electrical computers and digital processing systems: processing – Dynamic instruction dependency checking – monitoring or...
Reexamination Certificate
1999-12-29
2004-01-20
Kim, Kenneth S. (Department: 2181)
Electrical computers and digital processing systems: processing
Dynamic instruction dependency checking, monitoring or...
C711S141000, C712S032000, C712S218000, C712S225000
Reexamination Certificate
active
06681320
ABSTRACT:
BACKGROUND
1. Field
The present disclosure pertains to the field of processing systems. More particularly, the present disclosure pertains to a memory ordering technique for a multiprocessing system.
2. Description of Related Art
Improving the performance of computer or other processing systems generally improves overall throughput and/or provides a better user experience. One technique of improving the overall quantity of instructions processed in a system is to increase the number of processors in the system. Implementing multiprocessing (MP) systems, however, typically requires more than merely interconnecting processors in parallel. For example, tasks or programs may need to be divided so they can execute across parallel processing resources.
Another major challenge in an MP system is maintaining memory consistency (also known as coherency). Memory consistency is the general requirement that memory remain sufficiently updated to supply a current copy of memory contents to a requesting processor or other device. Maintaining memory consistency is complicated by the use of internal caches and other data structures that store data for more efficient access than is typically available from other (e.g., external) memory circuits.
A system may maintain memory consistency using hardware or using a combination of hardware and software techniques. The hardware provides a particular memory ordering guarantee, a guarantee that the hardware will maintain the sequential nature of program memory accesses (to at least some selected degree) at some selected point in the system hierarchy. Software may be used in some systems to supplement hardware-provided memory ordering by forcing additional ordering restrictions at desired times. The memory ordering scheme implemented is a design choice involving a tradeoff between hardware complexity, software complexity, and the desired ability to cache and buffer data.
One prior art technique that represents a compromise between weakly ordered memory consistency models and very restrictive consistency models is “processor consistency”. The processor consistency model is a known prior art model which allows limited reordering. One implementation is used in some prior current processors (see, e.g., U.S. Pat. No. 5,420,991). Memory ordering constraints for one embodiment of a prior art processor consistency memory model system are shown in
FIG. 1
a.
According to block
100
of
FIG. 1
a
, the prior art system ensures that stores from each individual processor in the system are observed in order by all other processors. In other words, individual stores from a particular processor are not re-ordered with respect to each other. As indicated in block
102
, the system ensures that loads from each processor appear to execute in order. In some systems, optimizations may be done; however, load data appears to be returned to the computation-performing unit in order to avoid altering the ordering relationships between the system loads and stores. On the other hand, if the load data being returned has not been altered by non-globally-observed stores, the order of that the load data is returned may be varied, and the data still appears to be returned in order.
Additionally, as indicated in block
104
, the system ensures that loads and stores to the same address are globally ordered. Thus, all agents in the system observe loads and stores to the same address in the same order. The consequences of the constraints of blocks
100
-
104
are discussed in greater detail (see
FIGS. 4
a-b
) as some embodiments of the present invention include these constraints as well.
Finally, as indicated in block
105
, stores to different addresses by different processors are globally ordered except that each processor can observe its own stores prior to observing stores from other processors. This prior art constraint is further contrasted with the present invention below (see
FIGS. 4
c
-
4
e
for implications of this prior art constraint). Some systems (e.g., systems based on the Profusion Chipset from Intel Corporation of Santa Clara) may require substantial hardware to ensure reasonably efficient ordered global observation of different stores to different memory locations by different processors.
Moreover, memory ordering overhead continues to grow dramatically as systems which implement traditional memory ordering models are scaled up to meet additional processing challenges. Consequently, there is a continuing need for memory ordering techniques that allow improved efficiency while maintaining a predetermined memory ordering protocol such as processor consistency.
REFERENCES:
patent: 5185871 (1993-02-01), Frey et al.
patent: 5265220 (1993-11-01), Kinoshita
patent: 5303362 (1994-04-01), Butts, Jr. et al.
patent: 5404483 (1995-04-01), Stamm et al.
patent: 5420991 (1995-05-01), Konigsfeld et al.
patent: 5613153 (1997-03-01), Arimilli et al.
patent: 5619662 (1997-04-01), Steely, Jr. et al.
patent: 5692151 (1997-11-01), Cheong et al.
patent: 5692153 (1997-11-01), Malik et al.
patent: 5706464 (1998-01-01), Moore et al.
patent: 5751983 (1998-05-01), Abramson et al.
patent: 5751986 (1998-05-01), Fetterman et al.
patent: 5796977 (1998-08-01), Sarangdhar et al.
patent: 5806086 (1998-09-01), Kimmel et al.
patent: 5887146 (1999-03-01), Baxter et al.
patent: 5930822 (1999-07-01), Chaney et al.
patent: 5987549 (1999-11-01), Hagersten et al.
patent: 5987579 (1999-11-01), Nishtala et al.
patent: 5999727 (1999-12-01), Panwar et al.
patent: 6049851 (2000-04-01), Bryg et al.
patent: 6052760 (2000-04-01), Bauman et al.
patent: 6055605 (2000-04-01), Sharma et al.
patent: 6065086 (2000-05-01), Arimilli et al.
patent: 6085295 (2000-07-01), Ekanadham et al.
patent: 6088770 (2000-07-01), Tarui et al.
patent: 6134632 (2000-10-01), Looi et al.
patent: 6167492 (2000-12-01), Keller et al.
patent: 6175930 (2001-01-01), Arimilli et al.
patent: 6253291 (2001-06-01), Pong et al.
patent: 6266768 (2001-07-01), Frederick, Jr. et al.
patent: 6275913 (2001-08-01), Jeddeloh
patent: 6275914 (2001-08-01), Jeddeloh
patent: 6360314 (2002-03-01), Webb, Jr. et al.
patent: 0 911 736 (1998-10-01), None
INTEL Corporation, “Profusion*, An 8-way Symmetric Multiprocessing Chipset”, Jul. 1999, pp. 1-15, URL: http://www.intel.com.
Adve, S. et al, “Shared Memory Consistency Models: A Tutorial,”Rice University ECE Tech. Rep. 9512 and Western Research Laboratory Research Report 95/7,Department of Electrical and Computer Engineering, Rice University and Western Research Laboratory, DEC, Sep. 1995, pp. 1-28 and abstract.
Adve, Sarita V. et al, “A Unified Formalization of Four Shared-Memory Models,”Computer Science Tech. Rep. #CS-1051, Department of Computer Science, University of Wisconsin, Sep. 1991, Revised Sep. 1992, pp. 1-24.
Adve, Sarita V. et al, “Weak Ordering—A New Definition,”Proceedings of the Seventeenth Annual International Symposium on Computer Architecture, pp. 2-14, 1990.
Adve, Sarita Vikram, “Designing Memory Consistency Models for Shared-Memory Multiprocessors,”Tech. Rep., University of Wisconsin at Madison, Madison, WI, 1993.
Ahamad, Mustaque et al, “Scalable Information Sharing in Large Scale Distributed Systems,”Proceedings of the Seventh SIGOPS Workshop, Aug. 1996.
Ahamad, Mustaque et al, “Causal Memory: Definitions, Implementation and Programming,”Tech. Rep. #GIT-CC-93/55, College of Computing, Georgia Institute of Technology, Sep. 17, 1993, Revised Jul. 22, 1994, pp. 1-25.
Ahamad, Mustaque et al, “The Power of Processor Consistency,”Tech. Rep. #GIT-CC-92/34, College of Computing, Georgia Institute of Technology, Dec. 31, 1992, Revised Jul. 8, 1993, pp. 1-21.
Ahamad, Mustaque et al, “Causal Memory Meets the Consistency and Performance Needs of Distributed Applications!,”Proceedings of the 6thWorkshop on ACM SIGOPS European Workshop: Matching Operating Systems to Application Needs, Sep. 1994, pp. 1-6.
Baldoni, R. et al, “Broadcast with Time and Causality Constraints for Multimedia Applications,”Tech. Rep. No. 2976, Insitut National de Recherche en Informatique et en Automatique Rennes, Appe
Draeger Jeffrey S.
Kim Kenneth S.
LandOfFree
Causality-based memory ordering in a multiprocessing... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Causality-based memory ordering in a multiprocessing..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Causality-based memory ordering in a multiprocessing... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-3197705