 | The ACM Journal of Experimental Algorithmics |
Volume 7, Article 9, 2002
by
and
and
and
http://www.jea.acm.org/2002/WickremesingheSorting/
Abstract:
Modern computer systems have increasingly complex memory systems. Common
machine models for algorithm analysis do not reflect many of the features
of these systems, e.g., large register sets, lockup-free caches, cache
hierarchies, associativity, cache line fetching, and streaming behavior.
Inadequate models lead to poor algorithmic choices and an incomplete
understanding of algorithm behavior on real machines.
A key step toward developing better models is to quantify the performance
effects of features not reflected in the models. This paper explores the
effect of memory system features on sorting performance. We introduce a
new cache-conscious sorting algorithm, R-merge, which achieves
better performance in practice over algorithms that are superior in the
theoretical models. R-merge is designed to minimize memory stall
cycles rather than cache misses by considering features common to many
system designs.
- Sources:
- The LaTeX version of the article;
this is a Unix file that contains the LaTeX source;
note that you must be a subscriber (institutional or individual) to access this file.
- The Postscript
version or PDF
version of the article;
note that you must be a subscriber (institutional or individual) to access
these files.
- The HTML version of the article;
note that you must be a subscriber (institutional or individual) to access
this file.
- The software suite accompanying the
article; this is a small Unix tar file, which includes the source code,
a Makefile, and the test files used in the article.
- The bibliography given in the article.
Received
|
Accepted
|
Final Revision
|
Published
|
|
|
|
|
Last updated and validated May 11, 2002, by editor@jea.acm.org