ERA

Download the full-sized PDF of Chopping Up Trees to Improve Spatial Locality in Implicit k-HeapsDownload the full-sized PDF

Analytics

Share

Permanent link (DOI): https://doi.org/10.7939/R3639K82R

Download

Export to: EndNote  |  Zotero  |  Mendeley

Communities

This file is in the following communities:

Computing Science, Department of

Collections

This file is in the following collections:

Technical Reports (Computing Science)

Chopping Up Trees to Improve Spatial Locality in Implicit k-Heaps Open Access

Descriptions

Author or creator
Niewiadomski, Robert
Amaral, Nelson
Additional contributors
Subject/Keyword
tree blocking
implicit k-heaps
Type of item
Report
Language
English
Place
Time
Description
Technical report TR06-06. Research on the performance of implicit k-heaps has shown that aligning data with cache lines and increasing heap arity are effective techniques for improving the data reference locality of heap operations. The technique of tree blocking has long been used to enhance the data reference locality of tree-based search methods. In this paper we propose c-clustered tree blocking, a new tree blocking method designed to further enhance the data reference locality of implicit k-heap operations. We examine the effect of our method on the performance of a traditional aligned implicit 2-heap using internal memory benchmarks based on the Hold model. Our empirical results, reproduced on four contemporary architectures, show that our method produces speedups of up to 2.0 in either benchmark, while reducing data cache misses by up to 85% and TLB misses by up to 65%. For larger heap arities our method matches the performance of traditional implicit k-heaps while improving page level locality.
Date created
2006
DOI
doi:10.7939/R3639K82R
License information
Creative Commons Attribution 3.0 Unported
Rights

Citation for previous publication

Source
Link to related item

File Details

Date Uploaded
Date Modified
2014-04-30T22:57:18.438+00:00
Audit Status
Audits have not yet been run on this file.
Characterization
File format: pdf (Portable Document Format)
Mime type: application/pdf
File size: 275065
Last modified: 2015:10:12 16:39:00-06:00
Filename: TR06-06.pdf
Original checksum: 653bd9c4161ae52829ea877e51ec5457
Well formed: true
Valid: true
Page count: 12
Activity of users you follow
User Activity Date