IBM Journal of Research and Development
IBM Skip to main content
  Home     Products & services     Support & downloads     My account  

  Select a country  
Journals Home  
  Systems Journal  
Journal of Research
and Development
    Current Issue  
    Recent Issues  
    Papers in Progress  
    Search/Index  
    Orders  
    Description  
    Patents  
    Recent publications  
    Author's Guide  
  Staff  
  Contact Us  
  Related links:  
     IBM Research  

IBM Journal of Research and Development  
Volume 31, Number 4, Page 435 (1987)
Aspects of Computer Performance
  Full article: arrowPDF   arrowCopyright info





   

Performance analysis of the FFT algorithm on a shared-memory parallel architecture

by Z. Cvetanovic
This paper presents a model for the performance prediction of FFT algorithms executed on a shared-memory parallel computer consisting of N processors an the same number of memory modules. The model applies a deterministic analysis to estimate the communication delay through the interconnection network by assuming that all requests arrive at the network in bursts. Our results indicate that the communication delay is significantly affected by the method applied to allocate data to memory modules. For the case in which all data items referenced by a processor during an iteration are allocated to a single memory module, the best-case communication time complexity grows as O[(log N)2/N]. The worst-case communication time complexity for this case, obtained by a different allocation of data to memory modules, is increased to O[(log N)/√N] due to high network contention. For the case in which the data items referenced by different processors during an iteration are allocated to the same memory module, the communication time complexity is further increased to O(log N) since all N requests generated by processors are serialized at a single memory module. The methods developed in this paper can be applied for the performance prediction of other well-structured parallel iterative algorithms.
Related Subjects: Algorithms; Parallel processing; Performance analysis