SYNCHRONIZATION BASED ON GLOBAL STATES AS A GENERAL CONTROL METHOD IN PARALLEL PROGRAMS

Authors

  • J. Borkowski
  • M. Tudruj
  • D. Kopanski

DOI:

https://doi.org/10.47839/ijc.2.3.223

Keywords:

Distributed systems, global states, global predicates, parallel programming, programming tools, visual programming

Abstract

New parallel program synchronization mechanisms are presented. A specialized synchronizer process, or a hierarchy of such processes, gather information about process states and construct Strongly Consistent Global States, using time interval timestamps. Global predicates evaluated by synchronizers can cause synchronization signals to be sent to processes, the signals trigger asynchronous computation activation or cancellation. The proposed framework is integrated with a message passing system - it is added to the GRADE graphical parallel programming environment to enhance its message-passing based features. Architecture and implementation of the enhancement are discussed.

References

[ACP01] M. Apte, S. Chakravarthi, J. Padmanabhan and A. Skjellum, A Synchronized Real-Time Linux Based Myrinet Cluster for Deterministic High Performance Computing and MPI/RT, Ninth International Workshop on Parallel and Distributed Real-Time Systems (WPDRTS 2001), April 2001, San Francisco.

[B00] J. Borkowski, Towards More Powerful and Flexible Synchronization Primitives, in Proc. of Inter. Conf. on Parallel Computing in Electrical Engineering PARELEC 2000, August 2000, Trois-Rivieres, Canada. IEEE PR00759, pp.18-22.

[B01] J. Borkowski, Interrupt and Cancellation as Synchronization Methods, in Proc of 4th Int. Conf. Parallel Processing and Applied Mathematics PPAM 2001, Naleczow, Poland, LNCS 2328, Springer 2001.

[BKT02] J. Borkowski, D. Kopanski, M. Tudruj, „Adding Advanced Synchronization to Processes in GRADE”, in Proceedings of the Int. Conf. on Parallel Processing and Electrical Engineering PARELEC 2002, Warsaw, Poland, IEEE 2002.

[BKT03] J. Borkowski, D. Kopanski, M. Tudruj, Implementing Control in Parallel Programs by Synchronization-Driven Activation and Cancelation, Proc. of the 11-th Euromicro PDP ‘03, Feb. 2003, Genova, Italy, IEEE 2003.

[BPR01] M. Bertozzi, M. Panella, M. Reggiani, Design of a VIA Based Communication Protocol for LAM/MPI Suite, Ninth Euromicro Workshop on Parallel and Distributed Processing (PDP '01), February 07 - 09, 2001, pp. 27-33.

[CM91] R. Cooper and K. Marzullo, "Consistent detection of global predicates, "Proceedings ACM/ONR Workshop on Parallel Distributed Debugging, pages 163-173, 1991.

[CO94] Cohen W.E., Dietz H.G., Sponaugle, Dynamic Barrier Architecture for Multi-Mode Fine-Grain Parallelism Using Conventional Processors, 1994 Int. Conf. on Parallel Processing, pp. I 93-96.

[DK99] D. Drotos, P. Kacsuk, GRAPNEL To C Translation in the GRADE Environment, Computers and Artificial Intelligence, Vol. 18, No. 4. pp. 415-424, 1999.

[EGE02] J. Elson, L. Girod and D. Estrin, Fine-grained network time synchronization using reference broadcasts, Proceedings of the Fifth Symposium on Operating System Design and Implementation (OSDI 2002), Boston, Massachussetts, USA, December 2002.

[FR95] Eddy Fromentin and Michel Raynal, Characterizing and detecting the set of global states seen by all observers of a distributed computation, Proceedings of the Fifteenth International Conference on Distributed Computing Systems, pp. 431-438, 1995.

[G97] Al Geist Advanced Tutorial on PVM 3.4 New Features and Capabilities, http://www.csm.ornl.gov/pvm/EuroPVM97/

[GM01] V. K. Garg and N. Mittal. On Slicing a Distributed Computation, Proceedings of the 21st IEEE International Conference on Distributed Computing Systems (ICDCS), pages 322-329, Phoenix, Arizona, April 2001.

[GW94] Detection of weak unstable predicates in Distributed programs, V.K Garg, B. Waldecker, IEEE Transactions on Parallel and Distributed Systems, 5(3), pp. 299--307, March 1994.

[GW96] V. K. Garg, B. Waldecker, Detection of Strong Unstable Predicates in Distributed Programs, IEEE Trans. on Parallel and Distrib. Systems, Vol. 7, No. 12, December 1996, pp. 1323-1333.

[HS00] K. Hyakawa, S. Sekiguchi, Design and Implementation of a Synchronization and Communication Controller for Cluster Computing Systems, 4-th Int. Conference on High Performance Computing in Asia-Pacific Region, Vol. 1, May 2000, pp. 76- 81.

[KDF97] Kacsuk, P., Dozsa, G. and Fadgyas, T., GRADE: A Graphical Programming Environment for PVM Applications Proc. of the 5th Euromicro Workshop on Parallel and Distributed Processing, London, 1997, pp. 358-365.

[KDFL99] The GRED Graphical Editor for the GRADE Parallel Program Development Environment P .Kacsuk, G. Dozsa, T. Fadgyas and R. Lovas Future Generation Computer Systems, No. 15 (1999), pp. 443-452.

[M89] F. Mattern. "Virtual Time and Global States in Distributed Systems". Proc. Workshop on Parallel and Distributed, Algorithms, Chateau de Bonas, Oct. 1988, M. Cosnard et al. (eds.), Elsevier / North Holland, pp. 215-226, 1989.

[M95] Mark Minas, Detecting Quantified Global Predicates in Parallel Programs, Europar 95 , Stockholm, Sweden. Proceedings. Lecture Notes in Computer Science, Vol. 966, Springer, pp. 403-414.

[M98] P. J. Mucci, "An Efficient Transport Independent Active Messaging Implementation for PVM", Technical Report UT-CS-98-399, 1998, http://citeseer.nj.nec.com/93955.html

[My03] Myricom Corp. GM 1.6.4 API Performance with PCI64B and PCI64C Myrinet/PCI Interfaces, April 2003, http://www.myri.com/myrinet/performance/index.html

[OL95 ] Olnovitch, H.T., ALLNODE Barrier Synchronization Network, 9-th Int. Parallel Processing Symposium, April, 1995, pp. 265-269.

[PGR] The P-GRADE Visual Parallel Programming Environment, http://www.lpds.sztaki.hu/teaching_materials/P-GRADE/index.htm

[RFC] Request for Comment RFC1305 Network Time Protocol (Version 3) Specification, Implementation and Analysis.

[RG89] R. Gupta, The Fuzzy Barrier: A Mechanizm for High Speed Synchronization of Processors, Proc. of the 3rd ASPLOS Conference, April 1989, pp. 54-63.

[S00] Scott D. Stoller: “Detecting Global Predicates in Distributed Systems with Clocks”. Distributed Computing, Volume 13 Issue 2 (2000) pp 85-98.

[S97] S.D. Stoller, "Detecting Global Predicates in Distributed Systems with Clocks". Proc. 11th International Workshop on Distributed Algorithms (WDAG 97). Lecture Notes in Computer Science, Springer-Verlag, 1997.

[SC96] Scott S. L., Synchronization and Communication in the T3E Multiprocessor, Proceedings of the 7-th ASPLOS Conference, 1996, pp. 26-36.

[SW95] S. Shang, K. Hwang, Distributed Hardwired Barrier Synchronization for Scalable Multiprocessor Clusters, IEEE Trans. On Parallel and Distributed Systems, vol. 6, June 1995, pp. 591 – 605.

[SWP01] P. Shivam, P. Wyckoff, D. Panda, EMP: Zero-copy OS-bypass NIC-driven Gigabit Ethernet Message Passing, Proceedings of Conference on High Performance Networking and Computing, Denver, Colorado, Nov. '01,pp. 57 - 57

[Tal02] N. Tanabe et al., Low Latency Communication on DIMMnet-1 Network Interface Plugged into a DIMM Slot, Proceedings of the Int. Conf. on Parallel Computing in Electrical Eng., Warsaw, Sept. 2002, pp. 9 – 14.

[TG98] A. Tarafdar and V.K. Garg. Predicate Control for Active Debugging of Distributed Programs. Symposium on Distributed and Parallel Debugging, 1998.

[KT98] M. Tudruj, P. Kacsuk, Extending Grade Towards Explicit Process Synchronization in Parallel Programs, Computers and Artificial Intelligence, vol 17, 1998, No. 5 pp 507-516.

Downloads

Published

2014-08-01

How to Cite

Borkowski, J., Tudruj, M., & Kopanski, D. (2014). SYNCHRONIZATION BASED ON GLOBAL STATES AS A GENERAL CONTROL METHOD IN PARALLEL PROGRAMS. International Journal of Computing, 2(3), 12-20. https://doi.org/10.47839/ijc.2.3.223

Issue

Section

Articles