Simulasi dan Analisis Algoritma Cache Replacement Policy LIRS2 (Low Inter-reference Recency Set 2)

Abdi, M. Iqbal (2023) Simulasi dan Analisis Algoritma Cache Replacement Policy LIRS2 (Low Inter-reference Recency Set 2). Other thesis, Institut Teknologi Sepuluh Nopember.

Text 05111940000151-Undergraduate_Thesis.pdf - Accepted Version Restricted to Repository staff only until 1 October 2025. Download (1MB) | Request a copy

Abstract

Cache merupakan sebuah memori buffer kecil dan berkecepatan tinggi yang terdapat dalam sistem komputer. Fungsinya adalah menyimpan sementara bagian-bagian konten dari memori utama yang akan atau sedang digunakan. Dengan adanya cache, sistem komputer dapat melakukan akses informasi dengan lebih cepat dibandingkan dengan menggunakan memori utama secara langsung. Oleh karena itu, cache menjadi elemen penting dalam perancangan sistem komputer untuk meningkatkan kecepatan dan efisiensi dalam penggunaan memori.
Studi sebelumnya mengamati perilaku umum bahwa sebagian besar blok cache menjadi tidak aktif setelah sejumlah referensi yang dilakukan oleh prosesor. Metode yang digunakan untuk mengatur perilaku cache ini disebut dengan cache replacement policy. Beberapa metode sudah dikembangkan untuk mengatur perilaku ini seperti LIRS (Low Inter-reference Recency Set). Namun, LIRS memiliki kelemahan dalam menangani pola akses zigzag di mana file diakses berulang kali secara alternative order. Untuk mengatasi ini, dikembangkan metode baru bernama LIRS2 (Low Inter-reference Recency Set 2). Pada Tugas Akhir ini akan dilakukan simulasi dan analisis dari algoritma LIRS2 yang akan diujikan dengan trace dari Umass Trace Repository, SNIA Repository dan data sintetis dengan pola akses tertentu untuk melihat performanya dibandingkan dengana algoritma replacement policy LIRS dan LRU. Performa ini akan diukur dengan metrik hit rate dengan ukuran cache yang beragam. Hasil yang didapatkan menunjukkan bahwa LIRS2 dapat mengatasi kelemahan LIRS pada pola akses zigzag serta mempertahankan kemampuan pada pola akses sekuensial. Namun, pada pengujian dengan frekuensi blok unik yang jarang muncul sangat tinggi, LIRS2 memiliki hit ratio yang lebih rendah dibandingkan LRU dan LIRS.
=================================================================================================================================
Cache is a small and high-speed buffer memory contained in a computer system. Its function is to temporarily store parts of the content from main memory that will be or are being used. With the cache, the computer system can access information more quickly than using the main memory directly. Therefore, cache is an important element in designing computer systems to increase speed and efficiency in memory usage. Previous studies observed the common behavior that most cache blocks become inactive after a certain number of references made by the processor. The method used to regulate cache behavior is called a cache replacement policy. Several methods have been developed to manage this behavior such as LIRS (Low Inter-reference Recency Set). However, LIRS has a weakness in dealing with zigzag access patterns where files are accessed repeatedly in alternative orders. To overcome this, a new method called LIRS2 (Low Inter-reference Recency Set 2) was developed. This Final Project will conduct simulations and analysis of the LIRS2 algorithm which will be tested with traces from the Umass Trace Repository, SNIA Repository and synthetic data with certain access patterns to see its performance compared to LIRS and LRU replacement policy algorithms. This performance will be measured by the hit rate metric with various cache sizes. The results obtained show that LIRS2 can overcome LIRS's weaknesses in zigzag access patterns and maintain capabilities in sequential access patterns. However, in testing with a very high frequency of unique blocks that rarely appear, LIRS2 has a lower hit ratio than LRU and LIRS.

Item Type:	Thesis (Other)
Uncontrolled Keywords:	Cache Replacement Policy, Hit ratio, LIRS2.
Subjects:	T Technology > T Technology (General) > T11 Technical writing. Scientific Writing T Technology > T Technology (General) > T57.62 Simulation
Divisions:	Faculty of Intelligent Electrical and Informatics Technology (ELECTICS) > Informatics Engineering > 55201-(S1) Undergraduate Thesis
Depositing User:	M. Iqbal Abdi
Date Deposited:	01 Dec 2023 02:53
Last Modified:	01 Dec 2023 02:53
URI:	http://repository.its.ac.id/id/eprint/103012

Actions (login required)

View Item