Electrical computers and digital processing systems: memory – Storage accessing and control – Access timing
Reexamination Certificate
2005-06-01
2008-11-25
Portka, Gary J (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Access timing
C711S147000, C711S118000
Reexamination Certificate
active
07457931
ABSTRACT:
An estimate of the throughput of a multi-threaded processor based on measured miss rates of a cache memory associated with the processor is adjusted to account for cache miss processing delays due to memory bus access contention. In particular, the throughput calculated from the cache memory miss rates is initially calculated assuming that a memory bus between the cache memory and main memory has infinite bandwidth, this throughput estimate is used to estimate a request cycle time between memory access attempts for a typical thread. The request cycle time, in turn, is used to determine a memory bus access delay that is then used to adjust the initial processor throughput estimate. The adjusted estimate can be used for thread scheduling in a multiprocessor system.
REFERENCES:
patent: 5151981 (1992-09-01), Westcott et al.
patent: 6119075 (2000-09-01), Dean et al.
patent: 6332178 (2001-12-01), Dean et al.
Ian MacIntyre and Bruno R. Preiss, The Effect of Cache on the Performance of a Multi-Threaded Pipelined RISC Processor, Department of Electrical and Computer Engineering University of Waterloo, 1991, pp. 1-8.
Fedorova, Alexandra “Operating System Scheduling for Chip Multithreaded Processors” http://www.eecs.harvard.edu/˜fedorova/thesis.pdf Harvard University 2006 pp. 12-53, 102-150.
U.S. Appl. No. 11/141,918, filed Jun. 1, 2005.
Fedorova et al., “Modeling the effects of memory hierarchy performance on throughput of multithreaded processors,” Technical Report TR-15-05, Division of Engineering and Applied Sciences, Harvard University, Jun. 2005.
Sorin et al., “Analytic evaluation of shared-memory systems with ILP processors,” Proceedings of the International Symposium on Computer Architecture (ISCA), 1998.
Willick et al., “An analytical model of multistage interconnection networks,” Proceedings of the 1990 ACM SIGMETRICS conference on Measurement and modeling of computer systems, 1990.
Saavedra-Barrera et al., “Analysis of multithreaded architectures for parallel computing,” Proceedings of the 2nd Annual ACM Symposium on Parallel Algorithms and Architectures, 1990.
Dubey et al., “Analytic Performance Modeling for a Spectrum of Multithreaded Processor Architectures,” Proceedings of the 3rd International Workshop on Modeling, Analysis, and Simulation of Computer and Telecommunication Systems, 1995.
Matick et al., “Analytical analysis of finite cache penalty and cycles per instruction of a multiprocessor memory hierarchy using miss rates and queuing theory,” IBM Journal of Research and Development, Nov. 2001.
Onvural, “Survey of closed queueing networks with blocking,” ACM Computing Surveys, Jun. 1990.
Denning, “Thrashing: Its causes and prevention,” Proc. AFIPS 1968 Fall Joint Computer Conference, 33, pp. 915-922, 1968.
Kleinrock, “Queuing systems vol. 1,” Wiley, 1975.
Fedorova, et al., “A Non-Work-Conserving Operating System Scheduler for SMT Processors,” http://www.bioperf.org/FSS06.pdf.
Ilya Gluhovsky, et al., “Comprehensive Multiprocessor Cache Miss rate Generation Using Multivariate Models,” SUN Microsystems Laboratories, ACM Transactions on Computer Systems., vol. 23, No. 2, May 2005, pp. 111-145.
Mario Nemirovsky, et al., “Quantitative Study of Data Caches on a Multistreamed Architecture,” http://www.cs.colostate.edu/TechReports/Reports/1998/mteac98
emirovsky.pdf.
Krishan M. Kavi, et al., “A Non-Blocking Multithreaded Architecture,” http://csrl.unt.edu/˜kavi/Research/adcomp-97.pdf.
Dhruba Chandra, et al., “Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture,” Proceedings of the 11th Int'l Symposium on High-Performance Computer Architecture (HPCA-11 2005).
Kowert Robert C.
Lo Kenneth M
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Portka Gary J
Sun Microsystems Inc.
LandOfFree
Method and apparatus for estimating the effect of processor... 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 and apparatus for estimating the effect of processor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for estimating the effect of processor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4029518