NDLI: Comparison of two-dimensional FFT methods on the hypercube

Please wait, while we are loading the content...

What have we learnt from using real parallel machines to solve real problems?

Hypercube data analysis in astronomy: optical interferometry and millisecond pulsar searches

Statistical gravitational lensing on the Mark III hypercube

An O(NlogN) hypercube N-body integrator

Piriform (Olfactory) cortex model on the hypercube

Collective steropsis on the hypercube

Parallel vision techniques on the hypercube computer

Pattern recognition by neural network model on hypercubes

A concurrent on-board vision system for a mobile robot

Region growing on a hypercube multiprocessor

Polymer simulation on the hypercube

Chemical reaction dynamics: integration of coupled sets of ordinary differential equations on the Caltech hypercube

Waveform relaxation for concurrent dynamic simulation of distillation columns

Implementing the beam and warming method on the hypercube

Finite difference time domain solution of electromagnetic scattering on the hypercube

A universal concurrent algorithm for plasma particle-in-cell simulation codes

Logic fault simulation on a vector hypercube multiprocessor

The Flux-corrected transport algorithm on the NCUBE hypercube

Solution of the 3-D Euler equations for the flow about a fighter aircraft configuration using a hypercube parallel processor

An interactive system for seismic velocity analysis

Hypercube performance for 2-D seismic finite-difference modeling

Acoustic wavefield propagation using paraxial extrapolators

Finite element solution of thermal convection on a hypercube concurrent computer

Seismic migration algorithms on parallel computers

Evaluation of a vector hypercube for seismic modelling

A hypercube Ray-tracer

Implementation of Ray tracing on the hypercube

Dynamic computational geometry on parallel computers

Computational geometry on hypercube computers

Implementation and performance analysis of parallel assignment algorithms on a hypercube computer

Multi-sensor integration on the NCUBE hypercube computer

Concurrent multiple target tracking

Implementing a distributed combat simulation on the Time Warp operating system

Lattice gauge theory on the hypercube

QED on the connection machine

Non-local path integral Monte Carlo on the hypercube

Molecular dynamics simulation on an iPSC of defects in crystals

Dynamical simulations of granular materials using the Caltech hypercube

Design and implementation of a concurrent image processing workstation based on the Mark III hypercube

The prime factor non-binary discrete Fourier transform and use of Crystal_Router as a general purpose communication routine

Chess on a hypercube

Large-scale concurrent computing in artificial intelligence research

Parallel expert system search techniques for a real-time application

Blitz: a rule-based system for massively parallel architectures

FCP: a summary of performance results

A distributed hypercube file system

ADAMS interface language

Reliability mechanisms for ADAMS

Concurrent I/O system for the hypercube multiprocessor

Use of the hypercube for symbolic quantum chromodynamics

Shift-register sequence random number generators on the hypercube conurrent computers

Comparison of two-dimensional FFT methods on the hypercube

Portable programming within a message-passing model: the FFT as an example

The fast Hartley transform on the hypercube multiprocessors

Binsorting on hypercubes with d-port communication

Granularity issues for solving polynomial systems via globally convergent algorithms on a hypercube

Hypercube implementation of the simplex algorithm

A concurrent neural network algorithm for the traveling salesman problem

Parallel branch and bound algorithms on hypercube multiprocessors

Best-first branch-and bound on a hypercube

A dynamic load balancer for a parallel branch and bound algorithm

Branch-and-bound algorithms on a hypercube

Process and workload migration for a parallel branch-and-bound algorithm on a hypercube multicomputer

Implemention of a divide and conquer cyclic reduction algorithm on the FPS T-20 hypercube

Prefix algorithms for tridiagonal systems on hypercube multiprocessors

A hybrid hypercube algorithm for the symmetric tridiagonal eigenvalue problem

An analytic model for parallel Gaussian elimination on a binary N-Cube architecture

Block-matrix operations using orthogonal trees

Solving the algebraic Riccati equation on a hypercube multiprocessor

Implementing Gauss Jordan on a hypercube multicomputer

Finding eigenvalues and eigenvectors of unsymmetric matrices using a hypercube multiprocessor

Large-grain pipelining on hypercube multiprocessors

Cholesky downdating on a hypercube

Expressing Boolean cube matrix algorithms in shared memory primitives

Distributed orthogonal factorization

Gauss-Jordan inversion with pivoting on the Caltech Mark II hypercube

LU decomposition of banded matrices and the solution of linear systems on hypercubes

Optimal matrix algorithms on homogeneous hypercubes

The preconditioned conjugate gradient method on the hypercube

Implementation of the conjugate gradient algorithm on a vector hypercube multiprocessor

An experimental study of methods for parallel preconditioned Krylov methods

A comparison of several methods of integrating stiff ordinary differential equations on parallel computing architectures

An iterative solution to speical linear systems on a vector hypercube

Intrinsically parallel multiscale algorithms for hypercubes

Parallel implementation of domain decomposition techniques on Intel's hypercube

A Schwarz splitting variant of cubic spline collocation methods for elliptic PDEs

Implementing finite element software on hypercube machines

Vectorized dissection on the hypercube

DIME: a programming environment for unstructured triangular meshes on a distributed-memory parallel processor

Comparison of two-dimensional FFT methods on the hypercube

Content Provider	ACM Digital Library
Author	Chu, C. Y.
Abstract	Complex two-dimensional FFTs up to size 256 x 256 points are implemented on the Intel iPSC/System 286 hypercube with emphasis on comparing the effects of data mapping, data transposition or communication needs, and the use of distributed FFTs. Two new implementations of the 2D-FFT include the Local-Distributed method which performs local FFTs in one direction followed by distributed FFTs in the other direction, and a Vector-Radix implementation that is derived from decimating the DFT in two-dimensions instead of one. In addition, the Transpose-Split method involving local FFTs in both directions with an intervening matrix transposition and the Block 2D-FFT involving distributed FFT butterflies in both directions are implemented and compared with the other two methods. Timing results show that on the Intel iPSC/System 286, there is hardly any difference between the methods, with the only differences arising from the efficiency or inefficiency of communication. Since the Intel cannot overlap communication and computation, this forces the user to buffer data. In some of the methods, this causes processor blocking during communication. Issues of vectorization, communication strategies, data storage and buffering requirements are investigated. A model is given that compares vectorization and communication complexity. While timing results show that the Transpose-Split method is in general slightly faster, our model shows that the Block method and Vector-Radix method have the potential to be faster if the communication difficulties were taken care of. Therefore if communication could be “hidden” within computation, the latter two methods can become useful with the Block method vectorizing the best and the Vector-Radix method having 25% fewer multiplications than row-column 2D-FFT methods. Finally the Local-Distributed method is a good hybrid method requiring no transposing and can be useful in certain circumstances. This paper provides some general guidelines in evaluating parallel distributed 2D-FFT implementations and concludes that while different methods may be best suited for different systems, better implementation techniques as well as faster algorithms still perform better when communication become more efficient.
Starting Page	1430
Ending Page	1437
Page Count	8
File Format	PDF
ISBN	0897912780
DOI	10.1145/63047.63099
Language	English
Publisher	Association for Computing Machinery (ACM)
Publisher Date	1989-01-03
Publisher Place	New York
Access Restriction	Subscribed
Content Type	Text
Resource Type	Article

Central Library (ISO-9001:2015 Certified)
Indian Institute of Technology Kharagpur
Kharagpur, West Bengal, India | PIN - 721302

See location in the Map
03222 282435
Mail: support@ndl.gov.in

Sl.	Authority	Responsibilities	Communication Details
1	Ministry of Education (GoI), Department of Higher Education	Sanctioning Authority	https://www.education.gov.in/ict-initiatives
2	Indian Institute of Technology Kharagpur	Host Institute of the Project: The host institute of the project is responsible for providing infrastructure support and hosting the project	https://www.iitkgp.ac.in
3	National Digital Library of India Office, Indian Institute of Technology Kharagpur	The administrative and infrastructural headquarters of the project	Dr. B. Sutradhar bsutra@ndl.gov.in
4	Project PI / Joint PI	Principal Investigator and Joint Principal Investigators of the project	Dr. B. Sutradhar bsutra@ndl.gov.in Prof. Saswat Chakrabarti will be added soon
5	Website/Portal (Helpdesk)	Queries regarding NDLI and its services	support@ndl.gov.in
6	Contents and Copyright Issues	Queries related to content curation and copyright issues	content@ndl.gov.in
7	National Digital Library of India Club (NDLI Club)	Queries related to NDLI Club formation, support, user awareness program, seminar/symposium, collaboration, social media, promotion, and outreach	clubsupport@ndl.gov.in
8	Digital Preservation Centre (DPC)	Assistance with digitizing and archiving copyright-free printed books	dpc@ndl.gov.in
9	IDR Setup or Support	Queries related to establishment and support of Institutional Digital Repository (IDR) and IDR workshops	idr@ndl.gov.in