Record Details

Register efficient mergesorting

DSpace at IIT Bombay

View Archive Info
 
 
Field Value
 
Title Register efficient mergesorting
 
Creator RANADE, A
KOTHARI, S
UDUPA, R
 
Description We present a register efficient implementation of Mergesort which we call FAME (Finite Automaton MErgesort). FAME is a m-way Mergesort. The m streams are merged by organizing comparison tournaments among the elements at the heads of the streams. The winners of the tournament form the output stream. Many ideas are used to increase efficiency. First, the heads of the streams axe maintained in the register file. Second, the tournaments are evaluated incrementally, i.e. after one winner is output the next tournament uses the results of the comparisons performed in the preceding tournaments and thus minimizes work. Third, to minimize register movement, the state of the tournament is encoded as a finite automaton. We experimented with 8-way and 4-way FAME on an Ultrasparc and a DEC Alpha and found that these algorithms were better than cache-cognizant Quicksort algorithms on the same machines.
 
Publisher SPRINGER-VERLAG BERLIN
 
Date 2011-10-23T13:24:54Z
2011-12-15T09:11:10Z
2011-10-23T13:24:54Z
2011-12-15T09:11:10Z
2001
 
Type Article; Proceedings Paper
 
Identifier HIGH PERFORMANCE COMPUTING - HIPC 2000, PROCEEDINGS,1970,96-103
3-540-41429-0
0302-9743
http://dspace.library.iitb.ac.in/xmlui/handle/10054/15140
http://hdl.handle.net/100/1896
 
Source 7th International Conference on High Performance Computing (HiPC 2000),BANGALORE, INDIA,DEC 17-20, 2000
 
Language English