An Optimal Parallel Radix Sorting Algorithm on Two and Three Dimensional Meshes for VLSI Computation = An Optimal Parallel Radix Sorting Algorithm on Two and Three Dimensional Meshes for VLSI Computation

다국어 초록 (Multilingual Abstract)

We consider radix sorting problems on two-dimensional mesh and three-dimensional mesh. By employing the radix sorting, we removed the necessity of comparators. Compared with previous sorting algorithms on the meshes which perform sorting based on comparison, our algorithm can be implemented on a simpler mesh since each processing element does not include the logic circuits for comparison. By replacing the comparison with the radix sorting, our algorithm removes the unrealistic assumption found in previous research that the comparion can be performed in O(1) time regardless of the size of the numbers to be compared. This has been a major obstacle in realizing their sorting algorithm using current VLSI technology. In contrast, our algorithm is suitable for VLSI implementation. The time complexity of radix sorting of N numbers on a (two-dimensional) mesh of size N^(1/2)×N^(1/2) is O(N^(1/2)). We also extend our algorithm to be implemented on a 3-dimensional mesh. It is shown that it takes O(N^(1/3)) time to sort N numbers on a 3-dimensional mesh of size N^(1/3)× N^(1/3) × N^(1/3) also without comparators.

목차 (Table of Contents)

• Abstract
  
• Ⅰ. Introduction
  
• Ⅱ. The architecture and the problem definition
  
• Ⅲ. The sorting algorithm
  
• Ⅳ. Mapping onto a 3-dimensional mesh
  
• Ⅴ. Conclusion
  
• Acknowledgement
  
• References
  
• 저자소개