TY - JOUR

T1 - Wavelength assignment for realizing parallel FFT on regular optical networks

AU - Chen, Yawen

AU - Shen, Hong

AU - Liu, Fangai

PY - 2006/4

Y1 - 2006/4

N2 - 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 n nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2n-1, 2n-1, 2max(k, n-k)-1 and 2 max(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.

AB - 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 n nodes on WDM linear arrays, rings, 2-D meshes and 2-D tori are 2n-1, 2n-1, 2max(k, n-k)-1 and 2 max(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.

KW - Network embedding

KW - Optical networks

KW - Parallel FFT

KW - Wavelength Division Multiplexing (WDM)

KW - Wavelength assignment

UR - http://www.scopus.com/inward/record.url?scp=33646747481&partnerID=8YFLogxK

U2 - 10.1007/s11227-006-2962-z

DO - 10.1007/s11227-006-2962-z

M3 - Article

AN - SCOPUS:33646747481

SN - 0920-8542

VL - 36

SP - 3

EP - 16

JO - Journal of Supercomputing

JF - Journal of Supercomputing

IS - 1

ER -