Browsing by Author "S C Tay"

Now showing 1 - 1 of 1
  • No Thumbnail Available
    Item
    Parallel Cubic Gridsort with Heap Restoration using Transputers
    (1994-11-01T00:00:00Z) S C Tay; K P Tan; G H Ong
    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.