Compiler-based prefetching algorithm for recursive data structure

Memory latency becoming an increasing important performance bottleneck as the gap between processor and memory speeds continues to grow. While cache hierarchies are an important step toward addressing the latency problem but they are not a complete solution. To further reduce or tolerate memory late...

Full description

Saved in:

Bibliographic Details
Main Author:	Anuar, Nurulhaini
Format:	Thesis
Language:	English
Published:	2007
Subjects:	QA75 Electronic computers Computer science
Online Access:	http://eprints.utm.my/id/eprint/6800/1/NurulhainiAnuarMFSKSM2007.pdf
Tags:	Add Tag No Tags, Be the first to tag this record!

id	my-utm-ep.6800
record_format	uketd_dc
spelling	my-utm-ep.68002018-08-29T07:51:08Z Compiler-based prefetching algorithm for recursive data structure 2007-04 Anuar, Nurulhaini QA75 Electronic computers. Computer science Memory latency becoming an increasing important performance bottleneck as the gap between processor and memory speeds continues to grow. While cache hierarchies are an important step toward addressing the latency problem but they are not a complete solution. To further reduce or tolerate memory latency problem, several techniques have been proposed and evaluated which is responsible to tolerating memory latency and cachemisses. Regarding to this problem, it has become necessary for us to have a better compiler optimization techniques. One of the techniques has recently used was Software Prefetching. Software prefetching relies on the programmer or compiler to insert explicit prefetch instructions into the application code for memory references that are likely to miss in the cache. Software prefetching has been shown to be effective in reducing memory stalls in array-based applications but not in pointer-based applications. This project investigates compiler-based prefetching for pointer based applications particularly those containing Recursive Data Structures (RDS) and designs the proposed algorithm. To designs this propose algorithm, there are two methodology used in this project that are comparative study and lab experiments in order to generates the hypothesis and quantitatively tested to measure the performance. There are three existing techniques that are selected for comparative study that are Greedy Prefetching, Jump History Pointer and Prefetch Array. The results from the comparative study and lab experiment give the best algorithm which is guide to design the proposed algorithm. This best algorithm consists of greedy prefetching and prefetch array algorithms. The proposed algorithm have been implemented and tested in the same environment as existing algorithms and the results shows the better improvement achieved compared from the best algorithm. This improvement results from the lab experiments shows this project have achieved the main objectives and gives better performance of compiler-based prefetching algorithm. 2007-04 Thesis http://eprints.utm.my/id/eprint/6800/ http://eprints.utm.my/id/eprint/6800/1/NurulhainiAnuarMFSKSM2007.pdf application/pdf en public http://dms.library.utm.my:8080/vital/access/manager/Repository/vital:62515 masters Universiti Teknologi Malaysia, Faculty of Computer Science and Information System Faculty of Computer Science and Information System
institution	Universiti Teknologi Malaysia
collection	UTM Institutional Repository
language	English
topic	QA75 Electronic computers Computer science
spellingShingle	QA75 Electronic computers Computer science Anuar, Nurulhaini Compiler-based prefetching algorithm for recursive data structure
description	Memory latency becoming an increasing important performance bottleneck as the gap between processor and memory speeds continues to grow. While cache hierarchies are an important step toward addressing the latency problem but they are not a complete solution. To further reduce or tolerate memory latency problem, several techniques have been proposed and evaluated which is responsible to tolerating memory latency and cachemisses. Regarding to this problem, it has become necessary for us to have a better compiler optimization techniques. One of the techniques has recently used was Software Prefetching. Software prefetching relies on the programmer or compiler to insert explicit prefetch instructions into the application code for memory references that are likely to miss in the cache. Software prefetching has been shown to be effective in reducing memory stalls in array-based applications but not in pointer-based applications. This project investigates compiler-based prefetching for pointer based applications particularly those containing Recursive Data Structures (RDS) and designs the proposed algorithm. To designs this propose algorithm, there are two methodology used in this project that are comparative study and lab experiments in order to generates the hypothesis and quantitatively tested to measure the performance. There are three existing techniques that are selected for comparative study that are Greedy Prefetching, Jump History Pointer and Prefetch Array. The results from the comparative study and lab experiment give the best algorithm which is guide to design the proposed algorithm. This best algorithm consists of greedy prefetching and prefetch array algorithms. The proposed algorithm have been implemented and tested in the same environment as existing algorithms and the results shows the better improvement achieved compared from the best algorithm. This improvement results from the lab experiments shows this project have achieved the main objectives and gives better performance of compiler-based prefetching algorithm.
format	Thesis
qualification_level	Master's degree
author	Anuar, Nurulhaini
author_facet	Anuar, Nurulhaini
author_sort	Anuar, Nurulhaini
title	Compiler-based prefetching algorithm for recursive data structure
title_short	Compiler-based prefetching algorithm for recursive data structure
title_full	Compiler-based prefetching algorithm for recursive data structure
title_fullStr	Compiler-based prefetching algorithm for recursive data structure
title_full_unstemmed	Compiler-based prefetching algorithm for recursive data structure
title_sort	compiler-based prefetching algorithm for recursive data structure
granting_institution	Universiti Teknologi Malaysia, Faculty of Computer Science and Information System
granting_department	Faculty of Computer Science and Information System
publishDate	2007
url	http://eprints.utm.my/id/eprint/6800/1/NurulhainiAnuarMFSKSM2007.pdf
_version_	1747814689081917440

Compiler-based prefetching algorithm for recursive data structure

Similar Items