- 期刊
- OpenAccess
Optimal Algorithm for Matrix Transpose on Wormhole-Switched Meshes
並列摘要
The mesh is an architecture that has many scientific applications, and matrix transpose is an important permutation frequently performed in various techniques involving systems of linear equations. In this paper, we present an optimal algorithm for performing matrix transpose on meshes that support wormhole switching. If N is even, our algorithm takes (The equation is abbreviated) communication steps to perform matrix transpose on an N×N mesh and requires only 3 more steps when the routing is restricted to XY routing, which is supported by most commercial mesh-connected parallel computers. The lower bound is (The equation is abbreviated) and the best previous bound is about N/3.27. The complexity of our algorithm almost matches the lower bound. Furthermore, our algorithm is simple and can be implemented on current mesh-connected parallel computers.
延伸閱讀
- Alibouch, 1., Iazzi, A., Radgui, A., & Rziza, M. (2014). An Adapted Block Thresholding Method for Omnidirectional Image Denoising. Research Journal of Applied Sciences, Engineering and Technology, 8(18), 1966-1972. https://www.airitilibrary.com/Article/Detail?DocID=20407467-201411-201503110021-201503110021-1966-1972
- Chang, J. M., Pai, K. J., Yang, J. S., & Chan, H. C. (2015). Embedding Two Disjoint Multi-Dimensional Meshes into Locally Twisted Cubes. 網際網路技術學刊, 16(3), 541-546. https://doi.org/10.6138/JIT.2015.16.3.20140422d
- Chen, P. Y., Liao, E. C., & Liang, C. W. (2008). The Segmented-Matrix Algorithm for Haar Discrete Wavelet Transform. Journal of Information Science and Engineering, 24(4), 1273-1282. https://doi.org/10.6688/JISE.2008.24.4.18
- Fu, S., Zhang, Y. H., He, S. Y., Chen, X., & Zhu, G. Q. (2015). Creeping Ray Tracing Algorithm for Arbitrary NURBS Surfaces Based on Adaptive Variable Step Euler Method. International Journal of Antennas and Propagation, 2015(), 835-846-182. https://doi.org/10.1155/2015/604861
- Kao, C. K. (2013). Applications of Dynamic 3D Meshes with Progressive Rendering and Stream Transmitting [doctoral dissertation, Chung Yuan Christian University]. Airiti Library. https://doi.org/10.6840/cycu201301100