Treffer: Adapting radix sort to the memory hierarchy Naila Rahman and Rajeev Raman King's College London
Title:
Adapting radix sort to the memory hierarchy Naila Rahman and Rajeev Raman King's College London
Contributors:
The Pennsylvania State University CiteSeerX Archives
Collection:
CiteSeerX
Subject Terms:
Categories and Subject Descriptors, F.2.2 [Theory of Computation, Analysis of Algorithms and Problem Complexity--Nonnumerical Algorithms and Problems, E.5 [Data, Files--Sorting/searching, D.1.0 [Software, Programming Techniques--General, B.3.2 [Hardware, Memory Structures--Design Styles General Terms, Efficient sorting algorithms, Locality of reference, Radix sort, Memory hierarchy, External-memory algorithms Additional Key Words and Phrases, Cache, Translation-lookaside buffer (TLB
Document Type:
Fachzeitschrift
text
File Description:
application/postscript
Language:
English
Relation:
Availability:
Rights:
Metadata may be used without restrictions as long as the oai identifier remains attached to it.
Accession Number:
edsbas.92ECD065
Database:
BASE
Weitere Informationen
We demonstrate the importance of reducing misses in the translation-lookaside buffer (TLB) for obtaining good performance on modern computer architectures. We focus on least-significantbit first (LSB) radix sort, standard implementations of which make many TLB misses. We give three techniques which simultaneously reduce cache and TLB misses for LSB radix sort: reducing working set size, explicit block transfer and pre-sorting. We note that