SYNCHRONIZATION BASED ON GLOBAL STATES AS A GENERAL CONTROL METHOD IN PARALLEL PROGRAMS
DOI:
https://doi.org/10.47839/ijc.2.3.223Keywords:
Distributed systems, global states, global predicates, parallel programming, programming tools, visual programmingAbstract
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
How to Cite
Issue
Section
License
International Journal of Computing is an open access journal. Authors who publish with this journal agree to the following terms:• Authors retain copyright and grant the journal right of first publication with the work simultaneously licensed under a Creative Commons Attribution License that allows others to share the work with an acknowledgement of the work's authorship and initial publication in this journal.
• Authors are able to enter into separate, additional contractual arrangements for the non-exclusive distribution of the journal's published version of the work (e.g., post it to an institutional repository or publish it in a book), with an acknowledgement of its initial publication in this journal.
• Authors are permitted and encouraged to post their work online (e.g., in institutional repositories or on their website) prior to and during the submission process, as it can lead to productive exchanges, as well as earlier and greater citation of published work.