Share
مقترح خوارزمية استبدال متعددة المستويات للذاكرة الوسيطة == A Proposed Multilevel Replacement Algorithm for Cache Memory
Author name:
سلام اياد حسين
Supervisor name:
سفانة حيدر عباس
General topic:
Computer Science
Specific topic:
Computer Science
Degree:
Master
University:
Mustansiriyah University - College Of Science - Department Of Computer
Language:
English
University location:
Baghdad
First pages:
28T841 - p.pdf
Abstract:
ان عملية التخزين المؤقت لديها مشكلة رئيسية تكمن في " اي من البيانات يتم اخراجها من الذاكرة الوسيطة في حالة عدم وجود البيانات المطلوبة" لكي تكون الذاكرة قابلة للاستخدام من جديد.هنالك جهد متواصل من الابحاث والدراسات التي اجريت لحل هذه المشكلة من اجل سد الفجوة الزمنية بين وحدة المعالجة المركزية عالية السرعة والذاكرة الرئيسية واطئة السرعة.هذا العمل اقترح خوارزمية استبدال جديدة للذاكرة الوسيطة عن طريق جمع الافكار وافضل المميزات لخوارزميات الاستبدال للاقل حداثة والاقل تكرارا مع هيكل جديد للذاكرة (مثلث ثنائي الابعاد) مع حد عتبة يتناسب مع حجم ذاكرة التخزين المؤقت.ونتيجة لذلك, هذه الدراسة اثبتت ان الخوارزمية المقترحة حصلت على نسبة وجود للبيانات اعلى مقارنة مع خوارزمية الاقل حداثة بنسبة (87.50%) ومع خوارزمية الاقل تكرارا بنسبة (96.00%) وازالت العديد من المساوئ التي كانت الخوارزميات السابقة تعاني منها.واخيرا, هذا العمل استنتج بان الموازنة بين "الحداثة" و"التكرار" مع الهيكل المقترح للذاكرة يوفر العديد من المميزات لم تكن جميعها موجودة في اي من الخوارزميات السابقة. واقترحت استخدام معامل ثالث مثل "مجموعة العمل" من اجل دقة اضافية في قرارات الحذف. | Caching has a major problem in making the decision of ''which blocks to evict from cache memory in case of a cache - miss occurs'' so that the memory can be reused. An ongoing effort of researches and studies have been carried out to solve this problem to bridge the cycle time gap between high speed Central Processing Unit (CPU) and low speed Main Memory (M.M).This work proposes a new cache replacement algorithm by combining ideas and best features from Least Recently Used (LRU) and Least Frequently Used (LFU) algorithms with the new structure (Two - dimensional Triangle) with a threshold that commensurate with the size of cache size. As a result, this study proves that the proposed algorithm has obtained higher hit ratio comparing to (LRU) with a percentage of (87.50%) and comparing to (LFU) with a percentage of (96.00%) and eliminates many disadvantages that the previous algorithms had Experienced. Finally, this thesis concludes that balancing between the 'Recency' and 'Frequency' with the proposed cache structure provides many advantages not all exist with any other previously known algorithm. And suggested to use a third factor such as the Working Set (WS) for additional accuracy in eviction decisions.
