VECTOR CLOCK TRACING AND MODEL BASED PARTITIONING FOR DISTRIBUTED EMBEDDED SYSTEMS

Authors

  • Robert Hoettger
  • Burkhard Igel
  • Erik Kamsties

DOI:

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

Keywords:

Partitioning, event tracing, vector clocks, control engineering, distributed systems, virtual time.

Abstract

Tracking, partitioning and tracing in modern dynamic high performance computing systems are three of the most innovative and important development aspects for performance optimization purposes and state-of-the-art advanced quality. This paper discusses these three aspects with respect to distributed systems and proposes new mechanisms for an advanced utilization of software in this domain. We present a specific tracking mechanism via vector clocks for model and code partitioning purposes and the determination of causality relations. Further, a tracing approach for an effective analysis and thereby utilization of code and the corresponding architecture is introduced. The combination of both approaches leads to a high degree of parallelism and a fine-grained structure of execution units, that further traced, supports a precise analysis of synchronous and asynchronous system’s behavior as well as an optimal load balancing. The mechanisms are introduced with respect to a model based control engineering tool and event diagrams.

References

Autosar – automotive open system architecture, January 2013, http://www.autosar.org.

R. Preis, Analysis and Design of Efficient Graph Partitioning Methods, Ph.D. dissertation, University Paderborn, 2000.

R. Hoettger, B. Igel, and E. Kamsties, A novel partitioning and tracing approach for distributed systems based on vector clocks, Proceedings of the IEEE 7th International Conference on Intelligent Data Acquisition and Advanced Computing Systems, IDAACS’2013, Berlin, 12-14 September 2013, pp. 670–675.

L. Lamport, Time, clocks and the ordering of events in a distributed system, Communications of the ACM, (21) 7 (1978), pp. 558–565.

F. Mattern, Virtual time and global states of distributed systems, Parallel and Distributed Algorithms, M. Cosnard et al. (editors), North-Holland, 1989, pp. 215–226.

C. J. Fidge, Timestamps in message-passing systems that preserve the partial ordering, Proceedings of the 11th Australian Computer Science Conference, 1988, Vol. 10, pp. 56–66.

A. Benveniste and G. Berry, The synchronous approach to reactive and real-time systems, Proceedings of the IEEE, (79) 9 (1991), pp. 1270-1282.

Paulo Sergio Almeida, Carlos Baquero, Victor Fonte, Interval tree clocks: A logical clock for dynamic systems, Proceedings of the 12th International Conference on Principles of Distributed Systems OPODIS'08, Luxor, Egypt, Lecture Notes in Computer Science, Vol. 5401, 2008, pp. 259-274.

I. Foster, Designing and Building Parallel Programs: Concepts and Tools for Parallel Software Engineering, Addison Wesley, 1995.

A. Nadgir and H. Haridas, Data ?ow partitioning schemes, 2003.

Data-flow-oriented modeling with damos, March 2013, http://www.eclipse.org/proposals/tools.damos/.

S. Peluso, P. Romano, F. Quagila, and L. Rodrigues, When scalability meets consistency: Genuine update-serializable partial replication, Proceedings of the IEEE International Conference on Distributed Computing Systems, 2012, pp. 455–464.

G. DeCandia, D. Hastorun, M. Jampani, et al., Dynamo: Amazon’s highly available key-value store, Proceedings of twenty-first ACM SIGOPS symposium on Operating Systems Principles, 2007, pp. 205–220.

L. Krawczyk and E. Kamsties, Hardware models for automated partitioning and mapping in multi-core systems, Proceedings of the IEEE 7th International Conference on Intelligent Data Acquisition and Advanced Computing Systems, IDAACS’2013, Berlin, 12-14 September 2013, Vol. 2, pp. 721–726.

Y. Fong Lee, B. G. Ryder, and M. E. Fiuczynski, Region analysis: A parallel elimination method for data ?ow analysis, IEEE Transactions on Software Engineering, (21) 11 (1995), pp. 913–926.

V. Elling and K. Schwan, Min-cut methods for mapping data?ow graphs, Proceedings of the 5th International Euro-Par Conference on Parallel Processing, ser. Euro-Par’99. Springer-Verlag, London, UK, 1999, pp. 203–212, http://dl.acm.org/citation.cfm?id=646664.701045.

K. E. Schauser, D. E. Culler, and T. V. Eicken, Compiler controlled multithreading for lenient parallel languages, in Proceedings of the 5th ACM Conference on Functional Programming Languages and Computer Architecture, Cambridge, MA, USA, August 26–30, 1991, Lecture Notes in Computer Science, Vol. 523, 1991, pp. 50–72.

Downloads

Published

2014-08-01

How to Cite

Hoettger, R., Igel, B., & Kamsties, E. (2014). VECTOR CLOCK TRACING AND MODEL BASED PARTITIONING FOR DISTRIBUTED EMBEDDED SYSTEMS. International Journal of Computing, 12(4), 324-332. https://doi.org/10.47839/ijc.12.4.612

Issue

Section

Articles