ICAR Research Data Repository for Knowledge Management
DSpace at IIT Bombay
View Archive InfoMetadata
| Field | Value |
| Title | Register efficient mergesorting |
| Names |
RANADE, A
KOTHARI, S UDUPA, R |
| Date Issued | 2001 (iso8601) |
| Abstract | 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. |
| Genre | Article; Proceedings Paper |
| Identifier | HIGH PERFORMANCE COMPUTING - HIPC 2000, PROCEEDINGS,1970,96-103 |