Parallel Cubic Gridsort with Heap Restoration using Transputers
| dc.contributor.author | S C Tay | en_US |
| dc.contributor.author | K P Tan | en_US |
| dc.contributor.author | G H Ong | en_US |
| dc.date.accessioned | 2004-10-21T14:28:52Z | en_US |
| dc.date.accessioned | 2017-01-23T07:00:33Z | |
| dc.date.available | 2004-10-21T14:28:52Z | en_US |
| dc.date.available | 2017-01-23T07:00:33Z | |
| dc.date.issued | 1994-11-01T00:00:00Z | en_US |
| dc.description.abstract | The proposed parallel cubic gridsort consists of two phases: preprocess and restore. In the preprocessing phase, input data are randomly placed on a cubic grid and sorted in depth-wise order, followed by column-wise order and row-wise order. As each line of data in the preprocessing phase is independent, the line-sorts in the cubic grid can be processed in parallel. In the restoring phase the remaining of the unsorted data are repeatedly moved to their be-sorted position followed by heap restoration. This can be performed in parallel by synchronizing the start time of each data movement and embedding a look-ahead mechanism in the restoration. The transputer's implementation shows that reasonably good speedup can be achieved for sorting reverse-sorted data and sorted data. As for sorting random data, a semi-parallelized cubic gridsort significantly out-performs the fully-parallelized version due to strong data-dependency in restoring phase. | en_US |
| dc.format.extent | 132588 bytes | en_US |
| dc.format.extent | 522269 bytes | en_US |
| dc.format.mimetype | application/pdf | en_US |
| dc.format.mimetype | application/postscript | en_US |
| dc.identifier.uri | https://dl.comp.nus.edu.sg/xmlui/handle/1900.100/1377 | en_US |
| dc.language.iso | en | en_US |
| dc.relation.ispartofseries | TR21/94 | en_US |
| dc.title | Parallel Cubic Gridsort with Heap Restoration using Transputers | en_US |
| dc.type | Technical Report | en_US |
Files
License bundle
1 - 1 of 1