Disk interleaving (disk striping) distributes
fragments of a data block across a group
of disks. For applications with regular I/O
reference patterns and requiring large
block transfers, interleaving can speed
data transfers and reduce I/O times. Com
puting fast Fourier transforms is one such
application; the algorithm assumes that
the entire array to be transformed should
fit in the main memory. Occasionally
arrays exceed the capacity of the main
memory and reside in secondary storage.
We have used synchronous and
asynchronous disk striping to compute
very large three-dimensional FFTs. We
present a two-pass algorithm for com
puting data stored on interleaved disks
and analyze the I/O times. A large FFT ex
ample provides a quantitative view of the
advantages of disk interleaving for this
application.
Get full access to this article
View all access options for this article.
References
1.
Agarwal, R.C., and Cooley, J.W.1986. Fourier transform and convolution subroutines for the IBM 3090 Vector Facility. IBM J. Res. Develop. 30(2):145-162.
2.
Boral, H., and DeWitt, D.J.1983. Database machines: An idea whose time has passed? A critique of the future of database machines. In Database machinesNew York: Springer-Verlag, (Proc. IWDM-83), edited by H. Leilch and M. Missikoff.
3.
Bracewell, R.N.1978. The Fourier transform and its applications. New York: McGraw-Hill.
4.
Brenner, N.M.1969. Fast Fourier transform of externally stored data . IEEE Trans. Audio Electroacoust. AU-17(2):128-132.
5.
Cooley, J.W., and Tukey, J.W.1965. An algorithm for the machine calculation of complex Fourier series. Math. Comp.19(90):297-301.
6.
Eklundh, J.O.1972. A fast computer method for matrix transposing. IEEE Trans. Comput.C-21(7):801-803.
7.
Fraser, D.1976. Array permutation by index-digit permutation. J. ACM23(2):298-309.
8.
Johnson, O.G.1984. Three-dimensional wave equation computations on vector computers. Proc. IEEE72(1):90-95.
9.
Kim, M.Y.1986a. Synchronized disk interleaving. IEEE Trans. Comput.C-35(11):978-988.
10.
Kim, M.Y.1986b. A synchronously interleaved disk system with its application to the very large FFTs. Ph.D. dissertation, Polytechnic University, New York.
11.
Kim, M.Y., and Patel, A.1985. Error correcting codes for interleaved disks with minimal redundancy. Comput. Sci. Res. Rep. RC11195. IBM.
12.
Kim, M.Y., and Tantawi, A.N.1987. Asynchronous disk interleaving. Comput. Sci. Res. Rep. RC 12497. IBM.
13.
Lineback, J.R.1985. New features tune Unix for high-end machines. Electronics August 19.
14.
Norton, A., and Silberger, A.1987. Parallelization and performance prediction of the Cooley-Tukey FFT algorithm for shared memory architectures. IEEE Trans. Comput.C-36(5):581-591.
15.
Pfister, G.F., et al. 1985. The IBM research parallel processor prototype (RP3): Introduction and architecture. Proc. Internat. Conf. on Parallel Proc.
16.
Singleton, R.1967. A method for computing the fast Fourier transform with aux. memory and limited high-speed storage. IEEE Trans. Audio Electroacoust. AU-15(2):91-98.
