FTL: a multithreaded environment for parallel computation

ABSTRACT

The arrival of high-performance "killer micros" and the availability of high-performance networks (e.g., ATM) offer potential for building clusters of workstations with a significantly higher level of scalability than before. A promising approach to exploiting parallel computation on these systems is to use multithreading to overlap computation and communication while offering a simple programming model that smoothly integrates these two functions.This paper describes the design and implementation of a portable software platform for multithreaded computation in distributed memory systems. The goal is to provide a runtime environment that efficiently integrates computation and communication, and runs on off-the-shelf workstations without any hardware or operating system modifications. The target configurations are networked clusters of UNIX workstations, such as workstation farms and high-speed interconnect clusters. The FTL software platform is being implemented as a runtime library that can be used either directly by a programmer, or by a compiler. Portability and programmability are among the important objectives in our design.

REFERENCES

• 1: {1} ACM SIGARCH and IEEE Comp. Soc. Proc. of the 19th Ann. Intl. Symp. on Computer Architecture, Gold Coast, Australia, May 19-21, 1992. Also in Computer Arch. News, 20(2), May 1992.
• 2: Anant Agarwal , Beng-Hong Lim , David Kranz , John Kubiatowicz, APRIL: a processor architecture for multiprocessing, Proceedings of the 17th annual international symposium on Computer Architecture, p.104-114, May 28-31, 1990, Seattle, Washington, United States
• 3: {3} Gail Alverson, Robert Alverson, David Callahan, Brian Koblenz, Allan Porterfield, and Burton Smith. Exploiting heterogeneous parallelism. Presented at Supercomputing 91 in Albuquerque, NM, Nov. 1991.
• 4: {4} Thomas E. Anderson. FastThreads User's Manual. cs-wash, 1990. In the Quartz distribution, available via anon. ftp from ftp.cs.washington.edu.
• 5: Thomas E. Anderson , Brian N. Bershad , Edward D. Lazowska , Henry M. Levy, Scheduler activations: effective kernel support for the user-level management of parallelism, Proceedings of the thirteenth ACM symposium on Operating systems principles, p.95-109, October 13-16, 1991, Pacific Grove, California, United States
• 6: E. Arjomandi , W. O'Farrell , I. Kalas , G. Koblents , F. Ch. Eigler , G. R. Gao, ABC++: concurrency by inheritance in C++, IBM Systems Journal, v.34 n.1, p.120-137, 1995
• 7: {7} Brian N. Bershad. The PRESTO user's manual. Technical Report UWCSE TR 88-01-04, Department of Computer Science, University of Washington, January 1988.
• 8: {8} Eric C. Cooper and Richard P. Draves. C Threads. Technical report, Department of Computer Science, Carnegie Mellon University, September 1990.
• 9: David E. Culler , Anurag Sah , Klaus E. Schauser , Thorsten von Eicken , John Wawrzynek, Fine-grain parallelism with minimal hardware support: a compiler-controlled threaded abstract machine, Proceedings of the fourth international conference on Architectural support for programming languages and operating systems, p.164-175, April 08-11, 1991, Santa Clara, California, United States
• 10: {10} William J. Dally. A Fine-Grain, Message-Passing Processing Node. Plenum, 1988.
• 11: {11} J.B. Dennis and G.R. Gao. The evolution of multithreaded computers. In R. Iannucci et al., editors, Multithreading: a Summary of the State of the Art. Kluwer Publishers, 1993.
• 12: {12} Dawson R. Engler, Gregory R. Andrews, and David K. Lowenthal. Efficient support for fine-grained parallelism. Technical Report TR 93-13, Dept. of Computer Science, University of Arizona, April 1993.
• 13: {13} J.R. Eykholt, S.R. Kleinman, S. Barton, R. Faulkner, and A. Shivalingiah. Beyond multiprocessing ... multithreading the SunOS kernel. In USENIX Summer Conference . USENIX, June 1992.
• 14: Message P Forum, MPI: A Message-Passing Interface Standard, University of Tennessee, Knoxville, TN, 1994
• 15: {15} D. Golub, R. Dean, A. Florin, and R. Rashid. UNIX as an application program. In Proceedings 1990 USENIX Summer Conference, pages 87-95, 1990.
• 16: {16} Herbert H. J. Hum, Kevin B. Theobald, and Guang R. Gao. Building multithreaded architectures with off-the-shelf microprocessors. ACAPS Technical Memo 77, School of Computer Science, McGill University, October 1993.
• 17: {17} IEEE. Threads extension for portable operating systems. Draft 6, February 1992. P1003.4a / D6.
• 18: {18} Y. Kodama, S. Sakai, and Y. Yamaguchi. A prototype of a highly parallel dataflow machine EM-4 and its preliminary evaluation. In Proc. of InfoJapan 90, Oct. 1990.
• 19: R. S. Nikhil , G. M. Papadopoulos , Arvind, T: a multithreaded massively parallel architecture, Proceedings of the 19th annual international symposium on Computer architecture, p.156-167, May 19-21, 1992, Queensland, Australia
• 20: Gregory M. Papadopoulos , Kenneth R. Traub, Multithreading: a revisionist view of dataflow architectures, Proceedings of the 18th annual international symposium on Computer architecture, p.342-351, May 27-30, 1991, Toronto, Ontario, Canada
• 21: {21} Shuichi Sakai, Yuetsu Kodama, and Yoshinori Yamaguchi. Architectural design of a parallel supercomputer EM-5. J. of SPP, 1991.
• 22: Thorsten von Eicken , David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser, Active messages: a mechanism for integrated communication and computation, Proceedings of the 19th annual international symposium on Computer architecture, p.256-266, May 19-21, 1992, Queensland, Australia

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.1 Process Management
          Subjects: Multiprocessing/multiprogramming/multitasking

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures
          Subjects: Distributed architectures

  D. Software
  D.1 PROGRAMMING TECHNIQUES
      D.1.3 Concurrent Programming
          Subjects: Parallel programming

General Terms:
Algorithms, Design, Measurement, Theory