Software‎ > ‎

JTransforms

Description

JTransforms is the first, open source, multithreaded FFT library written in pure Java. Currently, four types of transforms are available: Discrete Fourier Transform (DFT), Discrete Cosine Transform (DCT), Discrete Sine Transform (DST) and Discrete Hartley Transform (DHT). The code is derived from General Purpose FFT Package written by Takuya Ooura and from Java FFTPack written by Baoshe Zhang. Here are the projects that use JTransforms:

  • MusicReader - a software that makes reading music easy and convenient.
  • Spectro-Edit - a software for showing the audio visually in a time vs. frequency plot.
  • yaprnn - yet another pattern recognizing neural network.
  • ExpertEyes - an open source eyetracking application.

Features

  • The fastest implementation of DFT, DCT, DST and DHT in pure Java (see benchmark).
  • 1, 2 and 3-dimensional transforms.
  • Arbitrary size of the data.
  • Single and double precision.
  • One-dimensional and multi-dimensional variants of 2D and 3D transforms.
  • Automatic multithreading - threads are used automatically if #CPUs > 1.
  • Optimized FFTs for real input data (40% faster than complex).

Limitations

  • 1D transforms for not power-of-two sizes are sequential (when the mixed-radix is used).
  • 1D transforms for power-of-two sizes can use only 2 or 4 threads.
  • The number of threads must be a power-of-two number.
  • Only in-place transforms are available.
  • Only DCT-II and DCT-III are available.
  • Only DST-II and DST-III are available.
  • Only real DHT is available.

Benchmark

JTransforms 2.0 were benchmarked against FFTW 3.1.2, CUFFT and JCufft. 8 threads were used for the CPU-based algorithms. Only single precision, in-place transforms were computed.
The timings in the tables below are an average among 100 calls of each transform. They
do not incorporate the "warm up phase" (first two calls require more time) for JTransforms.

Benchmark code:

Testbed:

  • 2 x Quad-Core Intel Xeon X5472 (3GHz, 12MB L2 Cache),
  • 32 GB RAM,
  • Nvidia Quadro FX 5600 (1.5GB GDDR3),
  • Ubuntu 8.04 (64-bit),
  • GCC 4.2.3,
  • CUDA 2.0,
  • Sun Java 1.6.0_10 (64-Bit Server VM).
  • Configure flags for FFTW:--enable-threads --enable-float --enable-sse.
  • Java flags: -d64 -server -Xms10g -Xmx10g -XX:+UseParallelGC.
Library \ Size 2^16 2^17 2^18 2^19 2^20 2^21 2^22 2^23
FFTW_MEASURE (1)
0.93 1.80 4.14 16.77 37.74 65.58 113.56 182.50
FFTW_MEASURE (2)
22.20
17.00
44.75
64.29
64.76
335.87
218.50
1066.39
CUFFT (3)
0.16 0.37 1.13 1.66 3.22 8.78 20.98 45.02
CUFFT (4)
0.61 1.30 3.16 4.96 9.75 22.08 47.47 96.75
JCufft 1.57 3.00 6.52 12.62 25.91 53.09 108.01 216.77
JTransforms
2.70 3.35 6.36 13.75 32.05 68.88 153.64 346.13

Average execution time (in milliseconds) for 1D complex forward FFT (powers of two)


Library \ Size 10368 27000 75600 165375 362880 1562500 3211264 6250000
FFTW_MEASURE (1)
0.26
0.58
1.34
5.35
8.10
50.43
106.48
199.71
FFTW_MEASURE (2)
21.01
9.98
27.45
13.20
84.60
85.39
161.19
652.95
CUFFT (3)
0.14 0.24 0.82 1.56 11.25 17.85 22.64 65.61
CUFFT (4)
0.21 0.40 1.24 2.46 13.19 26.86 40.49 100.60
JCufft 0.57
0.85
2.25
4.57
18.10
50.34
87.21
190.62
JTransforms 0.85 1.35 4.54 13.60 24.47 131.82 754.91 542.20

Average execution time (in milliseconds) for 1D complex forward FFT (non-powers of two)


Library \ Size* 2^7 2^8 2^9 2^10 2^11 2^12 2^13 2^14
FFTW_MEASURE (1)
0.32 1.24 4.87 33.42 110.15 349.73 1516.50 13495.92
FFTW_MEASURE (2)
0.96 2.73
9.71
37.28
168.11 637.17
2143.14 20109.10
CUFFT (3)
0.04 0.11 0.61 2.14 16.38 76.59 **
**
CUFFT (4)
0.17 0.54 2.36 8.87 43.48 179.12 **
**
JCufft 0.52 1.41 5.70 24.99 103.97 426.03 **
**
JTransforms (5) 1.01 2.67 9.22 21.23 103.11
330.09 1886.97
7552.05
JTransforms (6) 1.84
2.80
8.46
23.10
91.44
270.28
1985.70
10445.69

Average execution time (in milliseconds) for 2D complex forward FFT (powers of two)


Library \ Size* 260 520 1050 1458 1960 2916 4116 5832
FFTW_MEASURE (1)
1.41
6.29
30.99
61.63
93.51
141.88
194.07
322.89
FFTW_MEASURE (2)
2.86
9.51
45.46
92.53
128.66
246.64
324.07
570.78
CUFFT (3)
0.85
2.84
8.87
27.53
41.48
131.77
362.87
681.26
CUFFT (4)
1.23
4.47
15.26
39.69
63.15
180.01
467.78
881.30
JCufft 2.16
8.04
32.16
71.78
119.27
305.50
721.74
1383.82
JTransforms (5)
2.42
8.27
28.82
54.09
111.03
167.78
437.55
574.94
JTransforms (6)
2.83
9.76
28.11
52.89
111.27
184.12
416.92
619.83

Average execution time (in milliseconds) for 2D complex forward FFT (non-powers of two)


Library \ Size* 2^3 2^4 2^5 2^6 2^7 2^8 2^9 2^10
FFTW_MEASURE (1)
0.14 0.17 0.44 3.43 52.50 183.10 864.21
11834.43
FFTW_MEASURE (2)
0.21
0.33
1.64
8.63
74.68
234.31
1107.26 13066.13
CUFFT (3)
0.05 0.7 1.57 3.60 13.37
75.41 ** **
CUFFT (4)
0.09
0.77
1.78
5.02
24.42
161.62 **
**
JCufft 0.28 1.04 2.29 8.39 55.46 407.58 **
**
JTransforms (5) 0.24 0.40 1.63
7.86
31.03 201.35 2213.02
***
JTransforms (6) 0.18
1.67
2.18
5.17
28.20
212.58 1583.38
16012.05

Average execution time (in milliseconds) for 3D complex forward FFT (powers of two)


Library \ Size* 5 17 30
95
180
270 324 420
FFTW_MEASURE (1)
0.14
0.42
0.64
53.96
102.11
209.47
281.76
502.88
FFTW_MEASURE (2)
0.27
1.71
2.28
81.32
137.49
291.77
357.66
620.17
CUFFT (3)
0.04
0.59
1.13
19.21
58.07
185.85
352.99
2943.38
CUFFT (4)
0.08
0.64
1.29
23.83
88.41
286.76
527.27
3324.72
JCufft 0.11
0.90
1.78
37.30
173.47
575.78
1028.61
4413.28
JTransforms (5) 0.04 1.87
2.22
35.62
141.85
401.36
697.40
1561.33
JTransforms (6) 0.04
2.05
2.55
35.17
192.48 547.65
947.44
2097.11

Average execution time (in milliseconds) for 3D complex forward FFT (non-powers of two)

(1) - timings don't include planning phase
(2) - timings include the planning phase
(3) - timings don't include the time required for data transfer to and from the GPU memory
(4) - timings include the time required for data transfer to and from the GPU memory
(5) - 1D input data
(6) - 2D / 3D input data

*     the size of each dimension
**    the data doesn't fit into GPU memory.
***   the size of the data exceeds 2^31 (1D Java arrays limitation).    

License

JTransforms is distributed under the terms of the MPL/LGPL/GPL tri-license.

Download

The source code distribution, besides Ant build file, contains also Eclipse project files.

version 2.4 (July 30, 2011) Changelog

binary: 

doc: 

source: 

Donations

If you have found this library useful and would like to thank the author, you can make a donation to show your appreciation.

Support This Project

Comments