NDLI: An experimental study of sorting and branch prediction

Please wait, while we are loading the content...

Experimental average-case performance evaluation of online algorithms for routing and wavelength assignment and throughput maximization in WDM optical networks

An experimental study of sorting and branch prediction

Terracost: Computing least-cost-path surfaces for massive grid terrains

A graph approach to the threshold all-against-all substring matching problem

A dictionary implementation based on dynamic perfect hashing

Preface

Engineering a cache-oblivious sorting algorithm

Sum-of-squares heuristics for bin packing and memory allocation

Efficient models for timetable information in public transportation systems

Faster placement of hydrogens in protein structures by dynamic programming

Papers from ALENEX 2005

On the adaptiveness of Quicksort

An experimental study of different approaches to solve the market equilibrium problem

Better external memory suffix array construction

Approximating the true evolutionary distance between two genomes

An experimental study of sorting and branch prediction

Content Provider	ACM Digital Library
Author	Biggar, Paul Nash, Nicholas Williams, Kevin Gregg, David
Copyright Year	2008
Abstract	Sorting is one of the most important and well-studied problems in computer science. Many good algorithms are known which offer various trade-offs in efficiency, simplicity, memory use, and other factors. However, these algorithms do not take into account features of modern computer architectures that significantly influence performance. Caches and branch predictors are two such features and, while there has been a significant amount of research into the cache performance of general purpose sorting algorithms, there has been little research on their branch prediction properties. In this paper, we empirically examine the behavior of the branches in all the most common sorting algorithms. We also consider the interaction of cache optimization on the predictability of the branches in these algorithms. We find insertion sort to have the fewest branch mispredictions of any comparison-based sorting algorithm, that bubble and shaker sort operate in a fashion that makes their branches highly unpredictable, that the unpredictability of shellsort's branches improves its caching behavior, and that several cache optimizations have little effect on mergesort's branch mispredictions. We find also that optimizations to quicksort, for example the choice of pivot, have a strong influence on the predictability of its branches. We point out a simple way of removing branch instructions from a classic heapsort implementation and also show that unrolling a loop in a cache-optimized heapsort implementation improves the predicitability of its branches. Finally, we note that when sorting random data two-level adaptive branch predictors are usually no better than simpler bimodal predictors. This is despite the fact that two-level adaptive predictors are almost always superior to bimodal predictors, in general.
Starting Page	1
Ending Page	39
Page Count	39
File Format	PDF
ISSN	10846654
e-ISSN	10846654
DOI	10.1145/1227161.1370599
Journal	Journal of Experimental Algorithmics (JEA)
Volume Number	12
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	2008-06-12
Publisher Place	New York
Access Restriction	One Nation One Subscription (ONOS)
Subject Keyword	Sorting Branch prediction Caching Pipeline architectures
Content Type	Text
Resource Type	Article
Subject	Theoretical Computer Science

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

A novel architecture for ahead branch prediction

Power-aware branch prediction: characterization and design

OS-Aware Branch Prediction: Improving Microprocessor Control Flow Prediction for Operating Systems

Modulo Path History for the Reduction of Pipeline Overheads in Path-based Neural Branch Predictors

An experimental study of sorting and branch prediction.

Software Trace Cache

On the adaptiveness of Quicksort

Movement prediction based cooperative caching for location dependent information service in mobile ad hoc networks

NTB branch predictor: dynamic branch predictor for high-performance embedded processors

An experimental study of sorting and branch prediction

Similar Documents

A novel architecture for ahead branch prediction

Power-aware branch prediction: characterization and design

OS-Aware Branch Prediction: Improving Microprocessor Control Flow Prediction for Operating Systems

Modulo Path History for the Reduction of Pipeline Overheads in Path-based Neural Branch Predictors

An experimental study of sorting and branch prediction.

Software Trace Cache

On the adaptiveness of Quicksort

Movement prediction based cooperative caching for location dependent information service in mobile ad hoc networks

NTB branch predictor: dynamic branch predictor for high-performance embedded processors

An experimental study of sorting and branch prediction