Fractal communication in software data dependency graphs

ABSTRACT

Communication is increasingly more costly than computation, but little work has been done on characterising the intrinsic communication behaviour of algorithms. We show that the dynamic data dependency graphs for a wide number of benchmarks exhibit multi-scale fractal communication. This has important implications for the locality of NoC communication in a CMP as well as for temporal locality. Benchmarks that do not exhibit fractal scaling or that have high fractal dimensionality may have poor communication scalability on a CMP.

REFERENCES

• 1: G. Concas, M. Locci, M. Marchesi, S. Pinna, and I. Turnu. Fractal dimension in software networks. EPL (Europhysics Letters), 76(6):1221--1227, 2006.
• 2: Daniel Greenfield , Arnab Banerjee , Jeong-Gun Lee , Simon Moore, Implications of Rent's Rule for NoC Design and Its Fault-Tolerance, Proceedings of the First International Symposium on Networks-on-Chip, p.283-294, May 07-09, 2007 [doi>10.1109/NOCS.2007.26]
• 3: M. R. Guthaus , J. S. Ringenberg , D. Ernst , T. M. Austin , T. Mudge , R. B. Brown, MiBench: A free, commercially representative embedded benchmark suite, Proceedings of the Workload Characterization, 2001. WWC-4. 2001 IEEE International Workshop, p.3-14, December 02-02, 2001 [doi>10.1109/WWC.2001.15]
• 4: A. Hartstein , V. Srinivasan , T. R. Puzak , P. G. Emma, Cache miss behavior: is it √2?, Proceedings of the 3rd conference on Computing frontiers, May 03-05, 2006, Ischia, Italy [doi>10.1145/1128022.1128064]
• 5: Wim Heirman , Joni Dambre , Dirk Stroobandt , Jan Van Campenhout, Rent's rule and parallel programs: characterizing network traffic behavior, Proceedings of the 2008 international workshop on System level interconnect prediction, April 05-08, 2008, Newcastle, United Kingdom [doi>10.1145/1353610.1353628]
• 6: Chi-Keung Luk , Robert Cohn , Robert Muth , Harish Patil , Artur Klauser , Geoff Lowney , Steven Wallace , Vijay Janapa Reddi , Kim Hazelwood, Pin: building customized program analysis tools with dynamic instrumentation, Proceedings of the 2005 ACM SIGPLAN conference on Programming language design and implementation, June 12-15, 2005, Chicago, IL, USA
• 7: Simon Moore , Daniel Greenfield, The next resource war: computation vs. communication, Proceedings of the 2008 international workshop on System level interconnect prediction, April 05-08, 2008, Newcastle, United Kingdom [doi>10.1145/1353610.1353627]
• 8: A. Mycroft. Programming language design and analysis motivated by hardware evolution. In SAS, pages 18--33, 2007.
• 9: A. Mycroft. Programming language design and analysis motivated by hardware evolution. In SAS, pages 18--33, 2007.
• 10: Girish V. Varatkar , Radu Marculescu, On-chip traffic modeling and synthesis for MPEG-2 video applications, IEEE Transactions on Very Large Scale Integration (VLSI) Systems, v.12 n.1, p.108-119, January 2004 [doi>10.1109/TVLSI.2003.820523]

INDEX TERMS

Primary Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING
      D.2.8 Metrics
          Subjects: Complexity measures

Additional Classification:
  B. Hardware
  B.8 Performance and Reliability
      B.8.2 Performance Analysis and Design Aids

  C. Computer Systems Organization
  C.1 PROCESSOR ARCHITECTURES
      C.1.4 Parallel Architectures

General Terms:
Algorithms, Design, Performance

Keywords:
CMP, NoC, communication complexity, fractal