The fast hartley transform on the hypercube multiprocessors

Xinming Lin; Tony F. Chart; Walter J. Karplus

doi:10.1145/63047.63101

The fast hartley transform on the hypercube multiprocessors

Xinming Lin, Tony F. Chart, Walter J. Karplus

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

2 Scopus citations

Abstract

The Fast Hartley Transform is a promising alternative to the Fast Fourier Transform when the processed data are real numbers. The hypercube implementation of the FHT is largely dependent on the way the computation is partitioned. A partitioning algorithm is presented which generates evenly-loaded tasks on each node and demands only a regular communication topology -The Hartley graph. Mapping from the Hartley graph to the Gray graph (binary n-cube) is straightforward, since the Hartley graph has a similar structure as the Gray graph. However, the communication is not always between the nearest neighbors and thus may take some extra time. Moreover, the slowness of the communication in the presently available architectures imposes a limitation on the speedup when a large number of processors are used.

Original language	English (US)
Title of host publication	Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
Editors	Geoffrey Fox
Publisher	Association for Computing Machinery, Inc
Pages	1451-1454
Number of pages	4
ISBN (Electronic)	0897912780, 9780897912785
DOIs	https://doi.org/10.1145/63047.63101
State	Published - Jan 3 1989
Externally published	Yes
Event	3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 - Pasadena, United States Duration: Jan 19 1988 → Jan 20 1988

Publication series

Name	Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988
Volume	2

Conference

Conference	3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988
Country/Territory	United States
City	Pasadena
Period	01/19/88 → 01/20/88

Bibliographical note

Publisher Copyright:
© ACM 1988 0-89791-278-0/88/0007/1592.

ASJC Scopus subject areas

Hardware and Architecture
Computer Graphics and Computer-Aided Design
Software
Computer Science Applications

Access to Document

10.1145/63047.63101

Cite this

Lin, X., Chart, T. F., & Karplus, W. J. (1989). The fast hartley transform on the hypercube multiprocessors. In G. Fox (Ed.), Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 (pp. 1451-1454). (Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988; Vol. 2). Association for Computing Machinery, Inc. https://doi.org/10.1145/63047.63101

Lin, Xinming ; Chart, Tony F. ; Karplus, Walter J. / The fast hartley transform on the hypercube multiprocessors. Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988. editor / Geoffrey Fox. Association for Computing Machinery, Inc, 1989. pp. 1451-1454 (Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988).

@inproceedings{3194d2da3669446c82e70b5874aa3465,

title = "The fast hartley transform on the hypercube multiprocessors",

abstract = "The Fast Hartley Transform is a promising alternative to the Fast Fourier Transform when the processed data are real numbers. The hypercube implementation of the FHT is largely dependent on the way the computation is partitioned. A partitioning algorithm is presented which generates evenly-loaded tasks on each node and demands only a regular communication topology -The Hartley graph. Mapping from the Hartley graph to the Gray graph (binary n-cube) is straightforward, since the Hartley graph has a similar structure as the Gray graph. However, the communication is not always between the nearest neighbors and thus may take some extra time. Moreover, the slowness of the communication in the presently available architectures imposes a limitation on the speedup when a large number of processors are used.",

author = "Xinming Lin and Chart, {Tony F.} and Karplus, {Walter J.}",

note = "Publisher Copyright: {\textcopyright} ACM 1988 0-89791-278-0/88/0007/1592.; 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988 ; Conference date: 19-01-1988 Through 20-01-1988",

year = "1989",

month = jan,

day = "3",

doi = "10.1145/63047.63101",

language = "English (US)",

series = "Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988",

publisher = "Association for Computing Machinery, Inc",

pages = "1451--1454",

editor = "Geoffrey Fox",

booktitle = "Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988",

}

Lin, X, Chart, TF & Karplus, WJ 1989, The fast hartley transform on the hypercube multiprocessors. in G Fox (ed.), Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988. Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988, vol. 2, Association for Computing Machinery, Inc, pp. 1451-1454, 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988, Pasadena, United States, 01/19/88. https://doi.org/10.1145/63047.63101

The fast hartley transform on the hypercube multiprocessors. / Lin, Xinming; Chart, Tony F.; Karplus, Walter J.
Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988. ed. / Geoffrey Fox. Association for Computing Machinery, Inc, 1989. p. 1451-1454 (Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988; Vol. 2).

Research output: Chapter in Book/Report/Conference proceeding › Conference contribution › peer-review

TY - GEN

T1 - The fast hartley transform on the hypercube multiprocessors

AU - Lin, Xinming

AU - Chart, Tony F.

AU - Karplus, Walter J.

PY - 1989/1/3

Y1 - 1989/1/3

N2 - The Fast Hartley Transform is a promising alternative to the Fast Fourier Transform when the processed data are real numbers. The hypercube implementation of the FHT is largely dependent on the way the computation is partitioned. A partitioning algorithm is presented which generates evenly-loaded tasks on each node and demands only a regular communication topology -The Hartley graph. Mapping from the Hartley graph to the Gray graph (binary n-cube) is straightforward, since the Hartley graph has a similar structure as the Gray graph. However, the communication is not always between the nearest neighbors and thus may take some extra time. Moreover, the slowness of the communication in the presently available architectures imposes a limitation on the speedup when a large number of processors are used.

AB - The Fast Hartley Transform is a promising alternative to the Fast Fourier Transform when the processed data are real numbers. The hypercube implementation of the FHT is largely dependent on the way the computation is partitioned. A partitioning algorithm is presented which generates evenly-loaded tasks on each node and demands only a regular communication topology -The Hartley graph. Mapping from the Hartley graph to the Gray graph (binary n-cube) is straightforward, since the Hartley graph has a similar structure as the Gray graph. However, the communication is not always between the nearest neighbors and thus may take some extra time. Moreover, the slowness of the communication in the presently available architectures imposes a limitation on the speedup when a large number of processors are used.

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

U2 - 10.1145/63047.63101

DO - 10.1145/63047.63101

M3 - Conference contribution

AN - SCOPUS:84944979589

T3 - Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988

SP - 1451

EP - 1454

BT - Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988

A2 - Fox, Geoffrey

PB - Association for Computing Machinery, Inc

T2 - 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988

Y2 - 19 January 1988 through 20 January 1988

ER -

Lin X, Chart TF, Karplus WJ. The fast hartley transform on the hypercube multiprocessors. In Fox G, editor, Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications, C3P 1988. Association for Computing Machinery, Inc. 1989. p. 1451-1454. (Proceedings of the 3rd Conference on Hypercube Concurrent Computers and Applications: Architecture, Software, Computer Systems, and General Issues, C3P 1988). doi: 10.1145/63047.63101

The fast hartley transform on the hypercube multiprocessors

Abstract

Publication series

Conference

Bibliographical note

ASJC Scopus subject areas

Access to Document

Other files and links

Fingerprint

Cite this