An Implementation of a Hopfield Network Kernel on EARTH
Resumo
EARTH is a multithreaded program execution and architecture model that hides communication and synchronization latencies through fine-grain multithreading. EARTH provides a simple synchronization mechanism: a thread is spawned when a pre-specified number of synchronization signals are received in its synchronization slot - signaling the fact that all dependences required for its execution are satisfied. This simple synchronization mechanism is an essential primitive in Threaded-C — a multithreaded language designed to program applications on EARTH. The EARTH synchronization mechanism has been efficiently implemented on a number of computer platforms, and has played an essential role in the support of a large number of parallel applications on EARTH. An interesting open question has been: is such a simple mechanism sufficient to satisfy the synchronization needs of the large set of applications that EARTH can implement? Or could the EARTH programming model benefit from the implementation of more elaborate synchronization mechanism? In such case, what are the benefits and tradeoffs of adding this mechanisms to EARTH? This paper describes the implementation of I-structures under the EARTH execution and architecture model. An I-structure is a data structure that allows for the implementation of a lenient computation model. A read operation can be issued to an element of an I-structure before it is known that the corresponding write operation has produced the value. We also introduce a new parallel kernel based on the Hopfield Network and demonstrate how the I-structure support on EARTH can be utilized. We finish presenting a complete Threaded-C program to solve the Hopfield kernel is also presented.
Referências
J..N. Amaral. Implementation of i-structures as a library of functions in portable threaded-c. Technical Report CAPSL TN04, University of Delaware, Newark, DE, June 1998.
Arvind, Rishiyur S, Nikhil, and Keshav K. Pingali. I-structures: Data structures for parallel computing. ACM TOPLAS, 11(4):598-632, October 1989.
P. S. Barth, R. S. Nikhil, and Arvind. M-structures: Extending a parallel, non-strict, functional language with state. Technical Report CSG-327, Massachusetts Institute of Technology, Cambridge, MA, March 1991. also appear in Proceedings of Functional Programming and Computer Architecture, Cambrideg, MA, August, 1991. (http://csg-www.lcs.mit.edu:8001/cgi-bin/search.pI?author=arvind).
Robert D. Blumofe, Christopher F. Joerg, Bradley C. Kuszmaul, Charles E. Leiserson, Keith H. Randall, and Yuli Zhou. Cilk: An efficient multithreaded runtime system. In Proceedings of the Fifth ACM SIGPLAN Symposium on Principles & Practice of Parallel Programming, pages 207-216, Santa Barbara, California, July 19-21, 1995. SIGPLAN Notices, 30(8), August 1995.
U. Bruening, W. K. Giloi, and W. Schroeder-Preikschat. Latency hiding in message-passing architectures. In Proceedings of the 8th International Parallel Processing Symposium [19], pages 704-709.
Haiying Cai. Dynamic load balancing on the EARTH-SP system. Master's thesis, McGill University, Montréal, Québec, May 1997.
J. B. Dennis and G. R. Gao. Memory models and cache management for a multithreaded program execution model. Technical Report CSG-363, Massachusetts Institute of Technology, Cambridge, MA, October 1994.
Jack B. Dennis and Guang R. Gao. On memory models and cache management for shared-memory multiprocessors. ACAPS Technical Memo 90, School of Computer Science, McGill University, Montréal, Québec, December 1994. In ftp://ftp-acaps.cs.mcgill.ca/pub/doc/memos.
M. Frigo, C. E. Leiserson, and K. H. Randall. The implementation of the cilk-5 multithreaded language. In 1998 ACM SIGPLAN Conference on Programming Language Design and Implementation, Montreal, Canada, June 1998.
Simon Haykin. Neural Networks: A Comprehensive Foundation. Macmillan College Publishing Company, New York, NY, 1994.
J. J. Hopfield. Neural networks and physical systems with emergent collective computational abilities. Proceedings National Academy of Science, 79:2554-2558, Apr. 1982.
J. J. Hopfield and D. W. Tank, Neural computation of decisions in optimization problems. Biological Cybernetics, 52:141-152, 1985.
J. J. Hopfield and D. W. Tank, Simple neural optimization networks: An a/d converter, signal decision circuit, and a linear programming circuit. IEEE Transactions on Circuits and Systems, CAS-33(5):533-541, May 1986.
P. Hudak, S. P. Jones, and P. Wadler, editors. Report on the Programming Language Haskell: A Non-strict Purely Functional Language, volume 27 of ACM Sigplan Notices, May 1992. Version 1.2.
Herbert H. J. Hum, Olivier Maquelin, Kevin B. Theobald, Xinmin Tian, Guang R. Gao, and Laurie J, Hendren. A study of the EARTH-MANNA multithreaded system. International Journal of Parallel Programming, 24(4):319-347, August 1996.
Herbert H. J. 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, Shamir Merali. Shashank S. Prakash Panangaden, Xun Xue, and Yingchun Zhu. A design study of the EARTH multiprocessor. In Lubomir Bic, Wim Bohm, Paraskevas Evripidou, and Jean-Luc Gaudiot, editors, Proceedings of the IFIP WG 10.3 Working Conference on Parallel Architectures and Compilation Techniques, PACT '95, pages 59-68, Limassol, Cyprus, June 27-29, 1995. ACM Press.
Herbert H. J. Hum, Kevin B. Theobald, and Guang R. Gao. Building multithreaded architectures with off-the-shelf micro- processors. In Proceedings of the 8th International Parallel Processing Symposium [19], pages 288-294.
IEEE Computer Society. Proceedings of the 8th International Parallel Processing Symposium, Cancún, Mexico, April 26-29, 1994.
Olivier Maquelin, Guang R. Gao, Herbert H. J. Hum, Kevin B. Theobald, and Xin-Min Tian. Polling Watchdog: Combining, polling and interrupts for efficient message handling. In Proceedings of the 23rd Annual International Symposium on Computer Architecture, pages 178-188, Philadelphia, Pennsylvania, May 22-24, 1996. ACM SIGARCH and IEEE Computer Society. Computer Architecture News, 24(2), May 1996.
D. Ridge, D. Becker, P. Merkey, and T. Sterling. Beowulf:harnessing the power of parallelism in a pile-of-pcs. In Proceedings of IEEE Aerospace, 1997. http://cesdis.gsfe.nasa.gov/beowulf/papers/papers.html.
T. Sterling, D. J. Becker, D. Savarese, M. Berry, and C. Res. Achieving a balanced low-cost architecture for mass storage management through multiple fast ethernet channels on the beowulf parallel workstation. In Proceedings of the International Parallel Processing Symposium, 1996. http://cesdis.gsfe.nasa.gov/beowulf/papers/papers.html.
Kevin B. Theobald, José Nelson Amaral, Gerd Heber, Olivier Maquelin, Xinan Tang, and Guang R. Gao. Overview of the portable threaded-c language. CAPSL Technical Memo 19, University of Delaware, http://www.capsl.udel.edu, April 1998.
