Electrical computers and digital processing systems: multicomput – Computer-to-computer data routing – Least weight routing
Reexamination Certificate
1997-11-26
2002-08-27
Maung, Zarni (Department: 2151)
Electrical computers and digital processing systems: multicomput
Computer-to-computer data routing
Least weight routing
C717S127000, C717S131000
Reexamination Certificate
active
06442585
ABSTRACT:
FIELD OF THE INVENTION
The present invention relates generally to measuring the performance of computer systems, and more particularly to schedule execution contexts according to the measured performance.
BACKGROUND OF THE INVENTION
The speed at which modern computer systems operate is often limited by the performance of their memory sub-systems, such as caches and other levels of a hierarchical memory subsystem containing SRAM, DRAM, disks and the like. Cache memories are intended to store data that share spatial and temporal localities. Other memories can store data in any number of organized manners, short term and long term.
In order to analyze and optimize the performance of memory transactions, better measuring tools are required. Currently, there are very few tools that can accurately measure and capture detailed information characterizing memory transactions.
Existing hardware event counters can detect discrete events related to specific memory transactions, such as cache references, or cache misses, but known event counters provide little detail that would allow one to exactly deduce the causes of performance debilitating events, and how such events could be avoided.
For example, currently it is extremely difficult to obtain information about the status of a cache block, such as clean or dirty, or shared or non-shared, while data are accessed. It is also very difficult to determine which memory addresses are actually resident in the cache, or which memory addresses are conflicting for a particular cache block, because existing systems do not provide an easy way to obtain the virtual and physical address of the data that are accessed.
Similarly, it is difficult to ascertain the source of a particular memory reference that caused a performance debilitating event. The source might be an instruction executed in the processor pipeline on behalf of a particular context (e.g., process, thread, hardware context, and/or address space number), it might be a memory request that is external to the processor pipeline, such as direct memory access (DMA) originating from various input/output devices, or it may be a cache-coherency message originating from other processors in a multiprocessor computer system. Sampling accesses to specific regions of memories, such as specific blocks in lines of a cache, physical addresses in a main memory, or page addresses in a virtual memory is even more difficult.
It may be possible, using simulation or instrumentation, to track memory addresses for processor initiated accesses, such as those due to load and store instructions. However, simulation and instrumentation techniques usually disturb the true operation of the system enough to give less than optimal measurements, particularly for large scale systems with real production workloads. Also, because instrumentation techniques modify or augment programs, they inherently alter memory and cache layouts, distorting the memory performance of the original system. For example, instruction cache conflicts may differ significantly between instrumented and uninstrumented versions of a program.
However, when the memory accesses are due to some event, such as a DMA transaction or a cache coherency transaction in a multi-processor, tracking accessed addresses can usually only be done by specialized hardware designed specifically for that part of the memory subsystem which is to be monitored.
In addition, in order to optimize operating system and application software, it would be useful to be able to obtain other types of information about memory transactions, such as the amount of memory that is used by different execution threads or processes, and the amount of time required to complete a particular memory transaction. Furthermore, it would be even more useful if the information could be used to optimize instruction scheduling and data allocation, perhaps even while the system is operating under a real workload.
SUMMARY OF THE INVENTION
A method schedules execution contexts in a computer system based on memory interactions. The computer system includes a processor and a hierarchical memory arranged in a plurality of levels. Memory transactions are randomly sampled for a plurality of contexts.
The contexts can be threads, processes, or hardware contexts. Resource interactions of the plurality of contexts is estimated, and particular contexts are chosen to be scheduled based on the estimated resource interactions.
Chosen contexts can be contexts that have minimal resource conflicts, contexts that have maximal resource sharing, and contexts that underutilize allocated resources. Allocated resources can include cache memories.
REFERENCES:
patent: 4084231 (1978-04-01), Capozzi et al.
patent: 4481583 (1984-11-01), Mueller
patent: 4583165 (1986-04-01), Rosenfeld
patent: 4590550 (1986-05-01), Eilert et al.
patent: 4800521 (1989-01-01), Carter et al.
patent: 4821178 (1989-04-01), Levin et al.
patent: 4845615 (1989-07-01), Blasciak
patent: 5103394 (1992-04-01), Blasciak
patent: 5151981 (1992-09-01), Westcott et al.
patent: 5268995 (1993-12-01), Diefendorff et al.
patent: 5269017 (1993-12-01), Hayden et al.
patent: 5287508 (1994-02-01), Hejna, Jr. et al.
patent: 5301299 (1994-04-01), Pawlowski et al.
patent: 5321836 (1994-06-01), Crawford et al.
patent: 5339425 (1994-08-01), Vanderah et al.
patent: 5379427 (1995-01-01), Hiroshima
patent: 5379432 (1995-01-01), Orton et al.
patent: 5388242 (1995-02-01), Jewett
patent: 5418973 (1995-05-01), Ellis et al.
patent: 5446876 (1995-08-01), Levine et al.
patent: 5450349 (1995-09-01), Brown, III et al.
patent: 5450586 (1995-09-01), Kuzara et al.
patent: 5450609 (1995-09-01), Schultz et al.
patent: 5452440 (1995-09-01), Salsburg
patent: 5463775 (1995-10-01), DeWitt et al.
patent: 5479629 (1995-12-01), Angjelo et al.
patent: 5479652 (1995-12-01), Dreyer et al.
patent: 5485574 (1996-01-01), Bolosky et al.
patent: 5493673 (1996-02-01), Rindos et al.
patent: 5500943 (1996-03-01), Ho et al.
patent: 5515538 (1996-05-01), Kleiman
patent: 5528753 (1996-06-01), Fortin
patent: 5530964 (1996-06-01), Alpert et al.
patent: 5537541 (1996-07-01), Wibecan
patent: 5546593 (1996-08-01), Kimura et al.
patent: 5560032 (1996-09-01), Nguyen et al.
patent: 5572672 (1996-11-01), Dewitt et al.
patent: 5581482 (1996-12-01), Weidenman et al.
patent: 5581745 (1996-12-01), Muraoka et al.
patent: 5594741 (1997-01-01), Kinzelman et al.
patent: 5594864 (1997-01-01), Trauben
patent: 5603004 (1997-02-01), Kurpanek et al.
patent: 5608892 (1997-03-01), Wakerly
patent: 5623627 (1997-04-01), Witt
patent: 5630157 (1997-05-01), Dwyer, III
patent: 5649136 (1997-07-01), Shen et al.
patent: 5651112 (1997-07-01), Matsuno et al.
patent: 5691920 (1997-11-01), Levine et al.
patent: 5748468 (1998-05-01), Notenboom et al.
patent: 5751945 (1998-05-01), Levine et al.
patent: 5752031 (1998-05-01), Cutler et al.
patent: 5765204 (1998-06-01), Bakke et al.
patent: 5768500 (1998-06-01), Agrawal et al.
patent: 5774718 (1998-06-01), Aoshima et al.
patent: 5799143 (1998-08-01), Butt et al.
patent: 5802378 (1998-09-01), Arndt et al.
patent: 5802386 (1998-09-01), Kahle et al.
patent: 5802593 (1998-09-01), Grimsrud
patent: 5809450 (1998-09-01), Chrysos et al.
patent: 5854934 (1998-12-01), Hsu et al.
patent: 5857097 (1999-01-01), Henzinger et al.
patent: 5860018 (1999-01-01), Panwar
patent: 5862371 (1999-01-01), Levine et al.
patent: 5878208 (1999-03-01), Levine et al.
patent: 5884080 (1999-03-01), Blandy et al.
patent: 5922070 (1999-07-01), Swoboda et al.
patent: 5923872 (1999-07-01), Chrysos et al.
patent: 5933626 (1999-08-01), Mahalingaiah et al.
patent: 5944841 (1999-08-01), Christie
patent: 5964867 (1999-10-01), Anderson et al.
patent: 5987598 (1999-11-01), Levine et al.
patent: 6000044 (1999-12-01), Chrysos et al.
patent: 0 086 380 (1983-08-01), None
patent: 0 458 127 (1991-11-01), None
patent: 0 465 765 (1992-01-01), None
patent: 0 689 141 (1995-12-01), None
patent: 0 766 177 (1997-04-01), None
Abraham et al., Predicting Load Latencies Using Cache Profiling, HPL-94-110, Nov. 1994, copyright Hewlett-Packard Co.*
Anderson et al., Co
Dean Jeffrey A.
Waldspurger Carl A.
Compaq Computer Corporation
Leah Sherry Oppenheimer Wolff & Donnelly
Maung Zarni
Opie George
LandOfFree
Method for scheduling contexts based on statistics of memory... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Method for scheduling contexts based on statistics of memory..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method for scheduling contexts based on statistics of memory... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2967942