NDLI: A Model for the Effect of Caching on Algorithmic Efficiency in Radix based Sorting

Content Provider	IEEE Xplore Digital Library
Author	Maus, A. Gjessing, S.
Copyright Year	2007
Description	Author affiliation: Univ. of Oslo, Oslo (Maus, A.; Gjessing, S.)
Abstract	This paper demonstrates that the algorithmic performance of end user programs may be greatly affected by the two or three level caching scheme of the processor, and we introduce a general but simple model that estimates this effect with good accuracy. Using 4 different processors and two simple tests, we demonstrate that a number of random reads and writes in an array can have a penalty factor of 40-70 compared to the exact same number of sequential array accesses. These effects from cache misses first occur when a randomly accessed array is larger than the L1 cache and even more so when the array does not fit in the much larger L2 cache. A similar but much smaller effect between sequential reads and writes in large arrays compared with smaller arrays is also reported. In the second part of this paper three versions of the well known Radix algorithm is used to demonstrate that the 'artificial' results from the first part definitely occur in practice. These versions use one, two and three digits, and hence one, two or three full passes to sort an array. For small arrays the two and three digit Radix algorithms of course are much slower than the one digit version, but for larger arrays the former outperform the latter. For comparison, the radix sorting execution times are compared to Quicksort and Flashsort, a different one-digit sorting algorithm, both of which are outperformed by the two and three digit Radix algorithms. Finally, a simple model based on the penalty of cache misses is introduced, and we use this model to explain the demonstrated differences in algorithmic efficiency.
Starting Page	33
Ending Page	33
File Size	314280
Page Count	1
File Format	PDF
ISBN	0769529372
DOI	10.1109/ICSEA.2007.6
Language	English
Publisher	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Publisher Date	2007-08-25
Publisher Place	France
Access Restriction	Subscribed
Rights Holder	Institute of Electrical and Electronics Engineers, Inc. (IEEE)
Subject Keyword	Sorting Informatics Sequential analysis Testing Performance evaluation Predictive models Prediction algorithms Algorithm design and analysis Bridges Cache memory sorting caches cache models cache friendly algorithms radix
Content Type	Text
Resource Type	Article

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in

Efficient sorting using registers and caches (2000)

Predictive Caching in Computer Grids

Efficient Sorting Using Registers and Caches (2002)

An evaluation of search tree techniques in the presence of caches

SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures

Fema: A Fairness and Efficiency Caching Management Algorithm in Shared Cache

An energy saving cache algorithm

The Design, Implementation, and Evaluation of a Predictive Caching File System (1996)

Improved Evaluation Algorithm for Performance Prediction with Error Analysis

A Model for the Effect of Caching on Algorithmic Efficiency in Radix based Sorting

Similar Documents

Efficient sorting using registers and caches (2000)

Predictive Caching in Computer Grids

Efficient Sorting Using Registers and Caches (2002)

An evaluation of search tree techniques in the presence of caches

SIMD- and Cache-Friendly Algorithm for Sorting an Array of Structures

Fema: A Fairness and Efficiency Caching Management Algorithm in Shared Cache

An energy saving cache algorithm

The Design, Implementation, and Evaluation of a Predictive Caching File System (1996)

Improved Evaluation Algorithm for Performance Prediction with Error Analysis

A Model for the Effect of Caching on Algorithmic Efficiency in Radix based Sorting