Network and Memory Analysis in Distributed Parallel Generation of Pat Arrays

  • João Paulo W. Kitajima UFMG
  • Berthier Ribeiro UFMG
  • Nívio Ziviani UFMG


The performance of parallel and distributed algorithms for generation of large pat arrays is analyzed. These algorithms are evaluated taking in to account a high-bandwidth network of workstations, a TCP/IP-based network and an heterogeneous network with different memory sizes. In the first case, performance of the parallel versions are significantly better. In the second case, the sequential algorithm is clearly the best. In the third case, different memory sizes will hardly improve execution times significantly.


Thomas Anderson, David Culler, and David Patterson. A case for NOW (network of workstations). IEEE Micro, 15(1):5464, February 1995.

Laurent Azema. Evaluation de stratégies d'ordonnancement statique sur ordinateurs à mémoire distribuée, June 1995. DEA thesis Institut National Polytechnique de Grenoble Grenoble, France.

Gaston H. Gonnet, Ricardo A. Baeza-Yates, and Tim Snider. New indices for text: Pat trees and pat arrays. In Information Retrieval Data Structures & Algorithms, pages 6682. Prentice Hall, 1992.

Jeft'rey Kuskin et al. The stanford FLASH multiprocessor. In Proceedings of the 21st International Symposium on Computer Architecture, pages 302-313, Chicago, IL, April 1994.

Sun Microsystems. Sun WWW home page, March 1996.

Ronald Mraz. Reducing the variance of point-to-point transfers for parallel real-time programs. IEEE Parallel and Distributed Technology, 2(4):20-31, 1994.
KITAJIMA, João Paulo W.; RIBEIRO, Berthier; ZIVIANI, Nívio. Network and Memory Analysis in Distributed Parallel Generation of Pat Arrays. In: INTERNATIONAL SYMPOSIUM ON COMPUTER ARCHITECTURE AND HIGH PERFORMANCE COMPUTING (SBAC-PAD), 8. , 1996, Recife. Anais [...]. Porto Alegre: Sociedade Brasileira de Computação, 1996 . p. 193-202. DOI: