Wavelength assignment for realizing parallel FFT on regular optical networks

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 2 ⁿ nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2^n-1, 2^n-1, 2^{max(k, n-k)-1} and 2 ^{max(k, n-k)-1} respectively. By shift-reversal mapping, the numbers of wavelengths required are max(3 × 2^n-3, 2), 2^n-2, max(3 × 2^{max(k, n-k)-3}, 2) and 2^{max(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.