Efficient measurement of data flow enabling communication-aware parallelisation

ABSTRACT

As multicore chips scale to higher processor counts, communication between cores becomes more and more important. Indeed, when a single application is split up among multiple cores, which are connected through a relatively slow network, the amount of communication that is required will have an essential effect on performance. Therefore, if the application can be partitioned in such a way that communication between threads is minimised, or that placement on non-uniform networks can be performed with regards to communication, a significant performance boost can be obtained. But to do this effectively, communication streams inside the application must be known. In this paper, we introduce a profiling tool for Java that can measure data flows between methods. It constructs a communication graph, which combines a traditional call graph with data flow information.

The overhead of profiling is brought down by a factor of 15 through the use of reservoir sampling. We prove that this can be done with a limited decrease in accuracy.

This way, we can quickly estimate communication flows, which forms the critical information that allows an efficient communication-aware parallelisation to be made.

REFERENCES

• 1: Francky Catthoor , Eddy de Greef , Sven Suytack, Custom Memory Management Methodology: Exploration of Memory Organisation for Embedded Multimedia System Design, Kluwer Academic Publishers, Norwell, MA, 1998
• 2: Kim-Hung Li, Reservoir-sampling algorithms of time complexity O(n(1 + log(N/n))), ACM Transactions on Mathematical Software (TOMS), v.20 n.4, p.481-493, Dec. 1994 [doi>10.1145/198429.198435]
• 3: N. Nethercote and A. Mycroft. Redux: A dynamic dataflow tracer. Electronic Notes in Theoretical Computer Science, 89(2):1--22, October 2003.
• 4: SPEC JVM Client98 Suite. Industry-standard benchmark for measuring Java Virtual Machine performance. In http://www.spec.org/, USA, 1998.
• 5: Jeffrey S. Vitter, Random sampling with a reservoir, ACM Transactions on Mathematical Software (TOMS), v.11 n.1, p.37-57, March 1985 [doi>10.1145/3147.3165]
• 6: R. E. Walpole and R. H. Myers. Probability and Statistics for Engineers and Scientists. Prentice Hall, 1993.
• 7: Jianjun Zhao, Multithreaded Dependence Graphs for Concurrent Java Program, Proceedings of the International Symposium on Software Engineering for Parallel and Distributed Systems, p.13, May 17-18, 1999

INDEX TERMS

Primary Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Measurements

Additional Classification:
  D. Software
  D.4 OPERATING SYSTEMS
      D.4.8 Performance
          Subjects: Stochastic analysis; Simulation

Keywords:
data-flow, profiling