The Hierarchically Tiled Arrays programming approach

ABSTRACT

In this paper, we show our initial experience with a class of objects, called Hierarchically Tiled Arrays (HTAs), that encapsulate parallelism. HTAs allow the construction of single-threaded parallel programs where a master process distributes tasks to be executed by a collection of servers holding the components (tiles) of the HTAs. The tiled and recursive nature of HTAs facilitates the adaptation of the programs that use them to varying machine configurations, and eases the mapping of data and tasks to parallel computers with a hierarchical organization. We have implemented HTAs as a MATLAB™ toolbox, overloading conventional operators and array functions such that HTA operations appear to the programmer as extensions of MATLAB™. Our experiments show that the resulting environment is ideal for the prototyping of parallel algorithms and greatly improves the ease of development of parallel programs while providing reasonable performance.

REFERENCES

• 1: Nas Parallel Benchmarks. Website. http://www.nas.nasa.gov/Software/NPB/.
• 2: High Performance Fortran Forum. High Performance Fortran Specification Version 2.0, January 1997.
• 3: G. Almasi, L. D. Rose, B. Fraguela, J. Moreira, and D. Padua. Programming for Locality and Parallelism with Hierarchically Tiled Arrays. In Proc. of the 16th International Workshop on Languages and Compilers for Parallel Computing, LCPC 2003, volume 2958 of Lecture Notes in Computer Science, pages 162--176, College Station, Texas, Oct 2003. Springer-Verlag.
• 4: Lynn Elliot Cannon, A cellular computer to implement the kalman filter algorithm, 1969
• 5: W. Carlson, J. Draper, D. Culler, K. Yelick, E. Brooks, and K. Warren. Introduction to UPC and Language Specification. Technical Report CCS-TR-99-157, IDA Center for Computing Sciences, 1999.
• 6: Bradford L. Chamberlain , Sung-Eun Choi , E Christopher Lewis , Lawrence Snyder , W. Derrick Weathersby , Calvin Lin, The Case for High-Level Parallel Programming in ZPL, IEEE Computational Science & Engineering, v.5 n.3, p.76-86, July 1998 [doi>10.1109/99.714604]
• 7: R. A. V. D. Geijn and J. Watts. SUMMA: Scalable Universal Matrix Multiplication Algorithm. 9(4):255--274, Apr. 1997.
• 8: Al Geist , Adam Beguelin , Jack Dongarra , Weicheng Jiang , Robert Manchek , Vaidy Sunderam, PVM: Parallel virtual machine: a users' guide and tutorial for networked parallel computing, MIT Press, Cambridge, MA, 1995
• 9: William Gropp , Ewing Lusk , Anthony Skjellum, Using MPI (2nd ed.): portable parallel programming with the message-passing interface, MIT Press, Cambridge, MA, 1999
• 10: Seema Hiranandani , Ken Kennedy , Chau-Wen Tseng, Compiling Fortran D for MIMD distributed-memory machines, Communications of the ACM, v.35 n.8, p.66-80, Aug. 1992 [doi>10.1145/135226.135230]
• 11: Charles Koelbel, An overview of High Performance Fortran, ACM SIGPLAN Fortran Forum, v.11 n.4, p.9-16, Dec. 1992 [doi>10.1145/140734.140736]
• 12: Robert W. Numrich , John Reid, Co-array Fortran for parallel programming, ACM SIGPLAN Fortran Forum, v.17 n.2, p.1-31, Aug. 1998 [doi>10.1145/289918.289920]
• 13: B. Wager. Hyperquicksort: A Fast Algorithm for Hypercubes. In Hypercube Multiporcessors, pages 292--299, Philadelphia, PA, 1987. SIAM.

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming

Additional Classification:
  D. Software
  D.3 PROGRAMMING LANGUAGES
      D.3.3 Language Constructs and Features

General Terms:
Languages

Keywords:
parallel languages