Proficient Pair of Replacement Algorithms on L1 and L2 Cache for Merge Sort

Details Proficient Pair of Replacement Algorithms on L1 and L2 Cache for Merge Sort Proficient Pair of Replacement Algorithms on L1 and L2 Cache for Merge Sort

2010-03-22

arxiv.org/abs/1003.4088v1

Journal of Computing, Volume 2, Issue 3, March 2010, https://sites.google.com/site/journalofcomputing/

Computer Science

Operating Systems

Scientific paper

Memory hierarchy is used to compete the processors speed. Cache memory is the fast memory which is used to conduit the speed difference of memory and processor. The access patterns of Level 1 cache (L1) and Level 2 cache (L2) are different, when CPU not gets the desired data in L1 then it accesses L2. Thus the replacement algorithm which works efficiently on L1 may not be as efficient on L2. Similarly various applications such as Matrix Multiplication, Web, Fast Fourier Transform (FFT) etc will have varying access pattern. Thus same replacement algorithm for all types of application may not be efficient. This paper works for getting an efficient pair of replacement algorithm on L1 and L2 for the algorithm Merge Sort. With the memory reference string of Merge Sort, we have analyzed the behavior of various existing replacement algorithms on L1. The existing replacement algorithms which are taken into consideration are: Least Recently Used (LRU), Least Frequently Used (LFU) and First In First Out (FIFO). After Analyzing the memory reference pattern of Merge Sort, we have proposed a Partition Based Replacement algorithm (PBR_L1)) on L1 Cache. Furthermore we have analyzed various pairs of algorithms on L1 and L2 respectively, resulting in finding a suitable pair of replacement algorithms. Simulation on L1 shows, among the considered existing replacement algorithms FIFO is performing better than others. While the proposed replacement algorithm PBR_L1 is working about 1.7% to 44 % better than FIFO for various cache sizes.

Affiliated with

Also associated with

No associations

Rating

Proficient Pair of Replacement Algorithms on L1 and L2 Cache for Merge Sort does not yet have a rating. At this time, there are no reviews or comments for this scientific paper.

If you have personal experience with Proficient Pair of Replacement Algorithms on L1 and L2 Cache for Merge Sort, we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Proficient Pair of Replacement Algorithms on L1 and L2 Cache for Merge Sort will most certainly appreciate the feedback.

Rate now

Comments { 0 }

Profile ID: LFWR-SCP-O-206139