Abstract
Routing and wavelength assignment (RWA) is a central issue to increase efficiency and reduce cost in Wavelength Division Multiplexing (WDM) optical networks. In this paper, we address the problem of wavelength assignment for realizing parallel FFT on a class of regular optical WDM networks. We propose two methods for sequential mapping and shift-reversal mapping of FFT communication pattern to the optical WDM networks concerned. By sequential mapping, the numbers of wavelengths required to realize parallel FFT with 2n nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2n − 1, 2n − 1, 2max (k,n − k) − 1 and 2max (k,n − k) − 1 respectively. By shift-reversal mapping, the numbers of wavelengths required are max (3× 2n − 3,2), 2n − 2, max (3× 2max (k,n − k) − 3,2) and 2max (k,n − k) − 2. These results show that shift-reversal mapping outperforms sequential mapping. Our results have a clear significance for applications because FFT represents a common computation pattern shared by a large class of scientific and engineering problems and WDM optical networks as a promising technology in networking has an increasing popularity.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Rami A. AL-Na’mneh, W. David Pan, and B. Earl Wells. Two parallel implementations for one dimension FFT on symmetric multiprocessors. In ACM Southeast Regional Conference, ACM Press, New York, NY, USA, pp. 273–278, 2004.
A. Averbuch, E. Gabber, B. Gordissky, and Y. Medan. A parallel FFT on an MIMD machine. Parallel Computing, 15(1–3):61–74, 1990.
D. H. Bailey. FFTs in external or hierarchical memory. The Journal of Supercomputing, 4(1):23–35, 1990.
Thomas L. Casavant, Pavel Tvrdík and František Plášil. Parallel Computers Theory and Practice. IEEE Computer Society Press, p. 168, 1996.
J. W. Cooley and J. W. Tukey. An algorithm for the machine calculation of complex Fourier series. Mathematics of Computation, 19(90):297–301, 1965.
F. T. Leighton. Introduction to Parallel Algorithms and Architectures: Arrays, Trees, Hypercubes. Morgan Kaufmann Publishers, Inc., 1992.
Keqin Li, Pan Yi, and Siqing Zheng. Parallel Computing Using Optical Interconnection. Kluwer Academic Press, Boston, 1998.
Fangai Liu and Yawen Chen. Wavelength assignment of parallel FFT communication pattern on a class of regular optical WDM networks. In Proceedings of the IEEE International Symposium on Parallel Architectures, Algorithms, and Networks. IEEE Computer Society. Hong Kong, pp. 495–500, 2004.
Antonino Mazzeo and Umberto Villano. Parallel 1D-FFT Computation on constant-valence multicomputers. Software Practice and Experience, 25(6):681–704, 1995.
Asuman E. Ozdaglar and Dimitri P. Bertsekas. Routing and wavelength assignment in optical networks. IEEE/ACM Transactions on Networking, 11(2):259–272, 2003.
Chunming Qiao and Yousong Mei. Off-line permutation embedding and scheduling in multiplexed optical networks with regular topologies. IEEE/ACM Transaction on Networking, 7(2):241–250, 1999.
H. Shen, Y. Pan, J. Sum, and S. Horiguchi. Multicasting in multihop optical WDM networks with limited wavelength conversion. IEICE Transactions on Information and Systems, E86–D(1):3–14, 2003.
Barry Wilkinson and Michael Allen. Parallel Programming: Techniques and Applications Using Networked Workstations. Prentice Hall, 1999.
Yuan X and Melhcm R. Optimal routing and channel assignments for hypercube communication on optical mesh-like processor arrays. In Proceedings of the 5th International Conference on Massively Parallel Processing Using Optical Interconnection. IEEE Computer Society. Las Vegas, NV, pp. 110–118, 1998.
Yuanyuan Yang and Jianchao Wang. Cost-effective designs of WDM optical interconnects. IEEE Transactions on Parallel and Distributed Systems, 16(1):51–66, 2005.
Hui Zang, Jason P. Jue, and Biswanath Mukherjee. A review of routing and wavelength assignment approaches for wavelength-routed optical WDM networks. SPIE Optical Networks Magazine, 1(1):47–60, 2000.
Chunling Zhou and Yuanyuan Yang. Wide-Sense nonblocking multicast in a class of regular optical WDM networks. IEEE Transactions on Communications, 50(1):126–134, 2002.
Author information
Authors and Affiliations
Corresponding author
Rights and permissions
About this article
Cite this article
Chen, Y., Shen, H. & Liu, F. Wavelength Assignment for Realizing Parallel FFT on Regular Optical Networks. J Supercomput 36, 3–16 (2006). https://doi.org/10.1007/s11227-006-2962-z
Issue Date:
DOI: https://doi.org/10.1007/s11227-006-2962-z