Electrical computers: arithmetic processing and calculating – Electrical digital calculating computer – Particular function performed
Reexamination Certificate
2004-02-25
2009-06-30
Ngo, Chuong D (Department: 2193)
Electrical computers: arithmetic processing and calculating
Electrical digital calculating computer
Particular function performed
C708S404000
Reexamination Certificate
active
07555509
ABSTRACT:
In a 3-dimensional fast Fourier transformation implemented by using a parallel-processing computer, an overhead caused by transfers of data between processors employed in the computer is reduced for the purpose of increasing the efficiency of processing parallelism. In order to reduce the overhead, data is divided into data elements each having an even X coordinate and data elements each having an odd X coordinate. In processing 34, the date elements each having an even coordinate are subjected to the transformation in the Y direction while the date elements each having an odd X coordinate are being subjected to a process of permutation among the processors at the same time. In processing 35, on the other hand, the data elements each having an odd X coordinate are subjected to the transformation in the X direction while the data elements each having even coordinate are being subjected to the process of permutation among the processors at the same time. As a result, the communication time it takes to carry out the process of permutation among the processors can be concealed behind the processing time so that the efficiency of the processing parallelism can be increased over the processing efficiency of the conventional method.
REFERENCES:
patent: 5548761 (1996-08-01), Balasundaram et al.
patent: 5751616 (1998-05-01), Hegland et al.
patent: 5754438 (1998-05-01), Naono et al.
patent: 5887186 (1999-03-01), Nakanishi
patent: 2002/0065862 (2002-05-01), Nakanishi
patent: 07-271760 (1994-03-01), None
patent: 11-066041 (1997-08-01), None
patent: 2000-200261 (1998-12-01), None
Takahashi, Daisuku, “Parallel FFT Algorithms for the Distributed-Memory Parallel Computer Hitachi SR8000”, Joint Symposium on Parallel Processing 2000, Jun. 1, 2000, pp. 91-93, [CSDB] CS-NG-2001-00293-012, Abstract in English.
G.H. Golub et al, “The Fast Fourier Transform—Matrix Computations”, 3rdEdition, The Johns Hopkins University Press, 1996, pp. 189-192.
V. Kumar et al., Fast Fourier Transform—Introduction to Parallel Computing:, published by The Benjamin/Cummings Publishing company, 1994, pp. 377-406.
Naono Ken
Yamamoto Yusaku
A. Marquez, Esq. Juan Carlos
Hitachi , Ltd.
Ngo Chuong D
Reed Smith LLP
LandOfFree
Parallel fast Fourier transformation method of... does not yet have a rating. At this time, there are no reviews or comments for this patent.
If you have personal experience with Parallel fast Fourier transformation method of..., we encourage you to share that experience with our LandOfFree.com community. Your opinion is very important and Parallel fast Fourier transformation method of... will most certainly appreciate the feedback.
Profile ID: LFUS-PAI-O-4089636