Electrical computers and digital processing systems: memory – Storage accessing and control – Access timing
Reexamination Certificate
2008-04-22
2008-04-22
Sough, Hyung S. (Department: 2188)
Electrical computers and digital processing systems: memory
Storage accessing and control
Access timing
C711S118000
Reexamination Certificate
active
07363450
ABSTRACT:
An estimate is calculated of the throughput of a multi-threaded processor having N threads based on measured miss rates of a cache memory associated with the processor by calculating, based on the cache miss rates a probability that the processor is in a state with one thread running, a probability that the processor is in a state with two threads are running and continuing to a probability that the processor is in a state with N threads running, multiplying each probability by a measured throughput of the processor when it is in the corresponding state and summing the resulting products. This estimate may also be corrected for bus delays in transferring information between the cache memory and main memory. The 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.
patent: 6604174 (2003-08-01), Dean et al.
patent: 2005/0198476 (2005-09-01), Gazsi et al.
“A Non-Work-Conserving Operating System Scheduler For SMT Processors” Alexandra Fedorova, Margo Seltzer and Michael D. Smith http://www.bioperf.org/FSS06.pdf.
“Comprehensive Multiprocessor Cache Miss Rate Generation Using Multivariate Models” Ilya Gluhovsky and Brian O'Krafka Sun Microsystems Laboratories ACM Transactions on Computer Systems, vol. 23, No. 2, May 2005, pp. 111-145.
“Quantitative study of data caches on a multistreamed architecture” Mario Nemirovsky and Wayne Yamamoto http://www.cs.colostate.edu/TechReports/Reports/1998/mteac98
emirovsky.pdf.
“A Non-Blocking Multithreaded Architecture” Krishna M. Kavi, David Levine and Ali R. Hurson http://csrl.unt.edu/˜kavi/Research/adcomp-97.pdf.
“Predicting Inter-Thread Cache Contention on a Chip Multi-Processor Architecture” Dhruba Chandra, Fei Guo, Seongbeom Kim, and Yan Solihin Proceedings of the 11th Int'l Symposium on High-Performance Computer Architecture (HPCA-11 2005).
U.S. Appl. No. 11/141,775, 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, pp. 147-240.
Ian MacIntyre, et al., “The Effect of Cache on the Performance of Multi-Threaded Pipelined RISC Processor,” Dept. of Electrical and Computer Engineering Univ. of Waterloo, 1991, pp. 1-8.
Kowert Robert C.
Lo Kenneth M
Meyertons Hood Kivlin Kowert & Goetzel P.C.
Petro Anthony M.
Sough Hyung S.
LandOfFree
Method and apparatus for estimating multithreaded 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 multithreaded processor..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Method and apparatus for estimating multithreaded processor... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-2766385