Polling watchdog: combining polling and interrupts for efficient message handling

ABSTRACT

Parallel systems supporting multithreading, or message passing in general, have typically used either polling or interrupts to handle incoming messages. Neither approach is ideal; either may lead to excessive overheads or message-handling latencies, depending on the application. This paper investigates a combined approach---Polling Watchdog, where both are used depending on the circumstances. The Polling Watchdog is a simple hardware extension that limits the generation of interrupts to the cases where explicit polling fails to handle the message quickly. As an added benefit, this mechanism also has the potential to simplify the interaction between interrupts and the network accesses performed by the program.We present the resulting performance for the EARTH-MANNA-S system, an implementation of the EARTH (Efficient Architecture for Running THreads) execution model on the MANNA multiprocessor. In contrast to the original EARTH-MANNA system, this system does not use a dedicated communication processor. Rather, synchronization and communication tasks are performed on the same processor as the regular computations. Therefore, an efficient message-handling mechanism is essential to good performance. Simulation results and performance measurements show that the Polling Watchdog indeed performs better than either polling or interrupts alone. In fact, this mechanism allows the EARTH-MANNA-S system to achieve the same level of performance as the original EARTH-MANNA multithreaded system.

REFERENCES

• 1: Anant Agarwal , Ricardo Bianchini , David Chaiken , Kirk L. Johnson , David Kranz , John Kubiatowicz , Beng-Hong Lim , Kenneth Mackenzie , Donald Yeung, The MIT Alewife machine: architecture and performance, Proceedings of the 22nd annual international symposium on Computer architecture, p.2-13, June 22-24, 1995, S. Margherita Ligure, Italy
• 2: Eric A. Brewer , Frederic T. Chong , Lok T. Liu , Shamik D. Sharma , John D. Kubiatowicz, Remote queues: exposing message queues for optimization and atomicity, Proceedings of the seventh annual ACM symposium on Parallel algorithms and architectures, p.42-53, June 24-26, 1995, Santa Barbara, California, United States [doi>10.1145/215399.215416]
• 3: Eugene Brooks, "The attack of the killer micros." Presentation in the Teraflop Computing Panel Discussion at Supercomputing '89, Reno, Nev., Nov. 1989.
• 4: U. Bruening , Wolfgang K. Giloi , Wolfgang Schroeder-Preikschat, Latency Hiding in Message-Passing Architectures, Proceedings of the 8th International Symposium on Parallel Processing, p.704-709, April 01, 1994
• 5: Derek Chiou , Boon Seong Ang , Robert Greiner , Arvind , James C. Hoe , Michael J. Beckerle , James E. Hicks , G. Andrew Boughton, START-NG: Delivering Seamless Parallel Computing, Proceedings of the First International Euro-Par Conference on Parallel Processing, p.101-116, August 29-31, 1995
• 6: David E. Culler , Seth Copen Goldstein , Klaus Erik Schauser , Thorsten von Eicken, TAM—a compiler controlled threaded abstract machine, Journal of Parallel and Distributed Computing, v.18 n.3, p.347-370, July 1993 [doi>10.1006/jpdc.1993.1070]
• 7: Jack B. Dennis and Guang R. Gao, "Multithreaded Architectures: Principles, Projects, and Issues," in Multithreaded Computer Architecture: A Summary of the State of the Art (Robert A. Iannucci, Guang R. Gao, Robert H. Halstead, Jr., and Burton Smith, eds.), ch. 1, pp. 1-72, Norwell, Mass.: Kluwer Academic Pub., 1994.
• 8: Dana S. Henry , Christopher F. Joerg, A tightly-coupled processor-network interface, Proceedings of the fifth international conference on Architectural support for programming languages and operating systems, p.111-122, October 12-15, 1992, Boston, Massachusetts, United States
• 9: Herbert H. J. Hum , Olivier Maquelin , Kevin B. Theobald , Xinmin Tian , Guang R. Gao , Laurie J. Hendren, A study of the EARTH-MANNA multithreaded system, International Journal of Parallel Programming, v.24 n.4, p.319-348, Aug. 1996
• 10: Herbert H. 5. Hum, Olivier Maquelin, Kevin B. Theobald, Xinmin Tian, Xinan Tang, Guang R. Gao, Phil Cupryk, Nasser Elmasri, Laurie J. Hendren, Alberto Jimenez, Shoba Krishnan, Andres Marquez, bhamlr Merall, bhashank ~ emawarkar, Prakash Panangaden, Xun Xue, and Yingchun Zhu, "The Multi-Threaded Architecture Multiprocessor," ACAPS Tech. Memo 88, Sch. of Comp. Sci., McGill U., Montr6al, Qua., Dec. 1994. In ftp://ftpacaps, cs. mcgill, c a/p u b / doc / memos.
• 11: Herbert H. J. Hum , Kevin B. Theobald , Guang R. Gao, Building Multithreaded Architectures with Off-the-Shelf Microprocessors, Proceedings of the 8th International Symposium on Parallel Processing, p.288-294, April 01, 1994
• 12: Yuetsu Kodama , Hirohumi Sakane , Mitsuhisa Sato , Hayato Yamana , Shuichi Sakai , Yoshinori Yamaguchi, The EM-X parallel computer: architecture and basic performance, Proceedings of the 22nd annual international symposium on Computer architecture, p.14-23, June 22-24, 1995, S. Margherita Ligure, Italy
• 13: Olivier Maquelin , Herbert H. J. Hum , Guang R. Gao, Costs and Benefits of Multithreading with Off-the-Shelf RISC Processors, Proceedings of the First International Euro-Par Conference on Parallel Processing, p.117-128, August 29-31, 1995
• 14: Michael D. Noakes , Deborah A. Wallach , William J. Dally, The J-machine multicomputer: an architectural evaluation, Proceedings of the 20th annual international symposium on Computer architecture, p.224-235, May 16-19, 1993, San Diego, California, United States
• 15: Shuichi Sakai , Kazuaki Okamoto , Hiroshi Matsuoka , Hideo Hirono , Yuetsu Kodama , Mitsuhisa Sato, Super-threading: architectural and software mechanisms for optimizing parallel computation, Proceedings of the 7th international conference on Supercomputing, p.251-260, July 19-23, 1993, Tokyo, Japan [doi>10.1145/165939.165976]
• 16: Ellen Spertus , William J. Dally, Evaluating the locality benefits of active messages, Proceedings of the fifth ACM SIGPLAN symposium on Principles and practice of parallel programming, p.189-198, July 19-21, 1995, Santa Barbara, California, United States
• 17: Ellen Spertus , Seth Copen Goldstein , Klaus Erik Schauser , Thorsten von Eicken , David E. Culler , William J. Dally, Evaluation of mechanisms for fine-grained parallel programs in the J-machine and the CM-5, Proceedings of the 20th annual international symposium on Computer architecture, p.302-313, May 16-19, 1993, San Diego, California, United States
• 18: Daniel Stodolsky , J. Bradley Chen , Brian N. Bershad, Fast Interrupt Priority Management in Operating System Kernels, USENIX Microkernels and Other Kernel Architectures Symposium, p.105-110, September 20-23, 1993
• 19: Andrew S. Tanenbaum, Operating systems: design and implementation, Prentice-Hall, Inc., Upper Saddle River, NJ, 1987
• 20: 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:
  C. Computer Systems Organization
  C.5 COMPUTER SYSTEM IMPLEMENTATION

Additional Classification:
  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES

  D. Software
  D.4 OPERATING SYSTEMS
      D.4.4 Communications Management
          Subjects: Message sending

  I. Computing Methodologies
  I.6 SIMULATION AND MODELING
      I.6.8 Types of Simulation
          Subjects: Combined

General Terms:
Management, Measurement, Performance