CACHE OBLIVIOUS ALGORITHM: SEQUENTIAL PROCESSING

Korde P.S.¹*, Khanale P.B.²*
¹Department of Computer Science, Shri Shivaji College, Parbhani (M.S.) India
²Department of Computer Science, Dnyopasak College, Parbhani (M.S.) India
* Corresponding Author : prakash_khanale@hotmail.com

Received : -     Accepted : -     Published : 21-12-2010
Volume : 1     Issue : 2       Pages : 7 - 9
J Inform Syst Comm 1.2 (2010):7-9

Hardware implements cache as a block of memory for temporary storage of data likely to be used again. Cache Oblivious Algorithm are typically analyzed using an idealized model of cache, but it is much easier to analyze than a real cache’s characteristics. But in many cases a constant factor is provably with in a more realistic cache’s performance. In this paper an efficient technique is proposed to manage cache memory by using sequential processing. The processed technique introduces some modifications on well-known cache oblivious algorithm process. The proposed processing technique accomplished improved results.

[1] Aggarwal A., Alpern B., Chandra A. K. and Snir M. (1987) In Proc. 19th Annu. ACM Sympos. Theory Comput., pages 305-313.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[2] Aggarwal A., Chandra A. K. (1988) In Proc. 20th Annu.ACM Sympos. Theory Comput., pages 173-185.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[3] Aggarwal A., Chandra A. K. and Snir M. (1987) In Proc. 28rd Annu. IEEE Sympos. Found. Comput. Sci., pages 204-216.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[4] Aggarwal A. and Vitter J. S. (1988) Commun. ACM, 31:1116-1127.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[5] Seznec A. (1997) A technical Report No. 1114, IRISA-INRIA, Campus de Beaulieu  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[6] Barry Wilkinson (1996) Computer Architecture, second edition, Prentice Hall  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[7] Alpern B., Carter L. and Feig E. (1990) Uniform memory hierarchies. In focs, pages600-608.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[8] Amato N. M. and Edgar A. Ramos. (1996) In Proc. 12th Annu. ACM Sympos. Comput. Geom., pages 166- 175  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[9] Lindia Null and Julia Lobour. (2006) The essentials of Computer Organization and Architecture second edition, Jones and Bartlett  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[10] Bender M. A., Duan Z., Iacono J. and Wu J. (2002) In Proceedings of the 13th Annual ACM-SIAM Symposium on Discrete Algorithms (SODA), pages 29-38.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[11] Frigo M., Charles Leiserson E., Prokop H. and Ramachandaran S. (1999) In Proc 40th Annual Symposium on Foundation of Computer Science  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[12] Brodal G. S. and Fagerberg R. (2002) In Proc. 13th Annual International Symposium on Algorithms and Computation, Lecture Notes in Computer Science  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[13] Brodal G. S., Fagerberg R. and Fagerberg R. (2001) Technical Report BRICS-RS-01-36, BRICS, Department of Computer Science, University of Aarhus  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[14] Chatterjee S. and Sen S. (2000) Cache-e_cient matrix transposition. In HPCA, pages 195-205.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[15] Chiang Y.-J., Goodrich M. T., Grove E. F., Tamassia R., Vengro D. E. and Vitter J. S. (1995) In Proc. 6th ACMSIAM Sympos.Discrete Algorithms, pages 139-149  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[16] Coppersmith D. and Winograd S. (1990) Journal of Symbolic Computation, 9:251-280  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[17] Cormen T. H., Leiserson C. E. and Rivest R. L. (1990) Introduction to Algorithms. MIT Press, Cambridge, MA.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[18] Eiron N., Rodeh M. and Steinwarts I. (1998) In 2nd Workshop on Algorithm Engineering, volume 16,pages 98- 109.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[19] Frigo M. (1999) In PLDI'99 | Conference on Pro-gramming Language Design and Implementation, Atlanta, GA.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[20] Frigo M. (1999) Portable highperformance programs. Technical Report MIT/LCS/TR-785.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[21] Frigo M., Charles E. Leiserson, Prokop H. and Ramachandran S. (1999) In Proc. 40th Annual Symposium on Foundations of Computer Science  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[22] Mathias Spjuth, Martin Karlsson and Erik (2003) Licentiate Thesis 2003- 009, Department of Information Technology, Uppsala University  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[23] Hill M.D. (!987) A PhD thesis presented to the University of California,Berkeley.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[24] Graham R. L., Knuth D. E. and Patashnik O. (1989) Concrete Mathematics. Addison-Wesley, Reading, MA.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[25] Hennessy J. L. and Patterson D. A. (1990) Computer Architecture: A Quantitative Ap-proach. Morgan Kaufmann Publishers, Inc  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus  

[26] William Stallings (2006 Computer Organization and Architecture, seventh edition,Prentice Hall.  
» CrossRef   » Google Scholar   » PubMed   » DOAJ   » CAS   » Scopus