Efficiency and scalability of barrier synchronization on NoC based many-core architectures

ABSTRACT

Interconnects based on Networks-on-Chip are an appealing solution to address future microprocessor designs where, very likely, hundreds of cores will be connected on a single chip. A fundamental role in highly parallelized applications running on many-core architectures will be played by barrier primitives used to synchronize the execution of parallel processes. This paper focuses on the analysis of the efficiency and scalability of different barrier implementations in many-core architectures based on NoCs. Several message passing barrier implementations based on four algorithms (all-to-all, master-slave, butterfly and tree) have been implemented and evaluated for a single-chip target architecture composed of a variable number of cores (from 4 to 128) and different network topologies (mesh, torus, ring, clustered-ring and fat-tree). Using a cycle-accurate simulator, we show the scalability of each barrier for every NoC topology, analyzing and comparing theoretical with real behaviors. We observed that some barrier algorithms, when implemented in hardware or software, show a different scaling behavior with respect to those theoretically expected. We evaluate the efficiency of each combination topology-barrier, demonstrating that, in many cases, simple network topologies can be more efficient than complex and highly connected topologies.

REFERENCES

• 1: SystemC 2.0 User's Guide⁵.
• 2: K. Asanovic, R. Bodik, B. C. Catanzaro, J. J. Gebis, P. Husbands, K. Keutzer, D. A. Patterson, W. L. Plishker, J. Shalf, S. W. Williams, and K. A. Yelick. The landscape of parallel computing research: A view from berkeley. Technical Report UCB/EECS-2006-183, EECS Department, University of California, Berkeley, Dec 2006.
• 3: Luca Benini , Giovanni De Micheli, Networks on Chips: A New SoC Paradigm, Computer, v.35 n.1, p.70-78, January 2002 [doi>10.1109/2.976921]
• 4: Tobias Bjerregaard , Shankar Mahadevan, A survey of research and practices of Network-on-chip, ACM Computing Surveys (CSUR), v.38 n.1, p.1-es, 2006 [doi>http://doi.acm.org/10.1145/1132952.1132953]
• 5: Cavium. Octeon plus cn58xx multi-core mips64. Available at: http://www.cavium.com/OCTEONPlus_CN58XX.html.
• 6: William J. Dally , Brian Towles, Route packets, not wires: on-chip inteconnection networks, Proceedings of the 38th conference on Design automation, p.684-689, June 2001, Las Vegas, Nevada, United States [doi>10.1145/378239.379048]
• 7: IBM. PowerPC 750 RISC microprocessor technical summary. Available at: http://www-3.ibm.com/chips/techlib/techlib.nsf/techdocs/750_ts.pdf, January 1998.
• 8: Intel. From a few cores to many: A tera-scale computing research overview. Available at: ftp://download.intel.com/research/platform/terascale/terascale_overview_paper.pdf.
• 9: Chun Liu , Anand Sivasubramaniam , Mahmut Kandemir , Mary Jane Irwin, Exploiting Barriers to Optimize Power Consumption of CMPs, Proceedings of the 19th IEEE International Parallel and Distributed Processing Symposium (IPDPS'05) - Papers, p.5.1, April 04-08, 2005 [doi>10.1109/IPDPS.2005.211]
• 10: Andrea Marongiu , Luca Benini , Mahmut Kandemir, Lightweight barrier-based parallelization support for non-cache-coherent MPSoC platforms, Proceedings of the 2007 international conference on Compilers, architecture, and synthesis for embedded systems, September 30-October 03, 2007, Salzburg, Austria [doi>10.1145/1289881.1289908]
• 11: M. Monchiero, G. Palermo, C. Silvano, and O. Villa. Efficient synchronization for embedded on-chip multiprocessors. IEEE Transactions on Very Large Scale Integration (VLSI) Systems, 14(10):1049--1062, October 2006.
• 12: Robert Mullins , Andrew West , Simon Moore, Low-Latency Virtual-Channel Routers for On-Chip Networks, Proceedings of the 31st annual international symposium on Computer architecture, p.188, June 19-23, 2004, München, Germany
• 13: Richard Murphy , Arun Rodrigues , Peter Kogge , Keith Underwood, The implications of working set analysis on supercomputing memory hierarchy design, Proceedings of the 19th annual international conference on Supercomputing, June 20-22, 2005, Cambridge, Massachusetts [doi>10.1145/1088149.1088193]
• 14: G. Palermo and C. Silvano. PIRATE: A framework for power/performance exploration of network-on-chip architectures. In PATMOS-04: Proceedings of International Workshop on Power and Timing Modeling, Optimization and Simulation, September 2004.
• 15: Maurizio Palesi , Rickard Holsmark , Shashi Kumar , Vincenzo Catania, A methodology for design of application specific deadlock-free routing algorithms for NoC systems, Proceedings of the 4th international conference on Hardware/software codesign and system synthesis, October 22-25, 2006, Seoul, Korea [doi>10.1145/1176254.1176289]
• 16: Fabrizio Petrini , Salvador Coll , Eitan Frachtenberg , Adolfy Hoisie, Hardware- and Software-Based Collective Communication on the Quadrics Network, Proceedings of the IEEE International Symposium on Network Computing and Applications (NCA'01), p.24, October 08-10, 2001
• 17: Tilera. Tile64 processor family. Available at: http://www.tilera.com/pdf/ProBrief_Tile64.pdf.
• 18: Barry Wilkinson , Michael Allen, Parallel programming: techniques and applications using networked workstations and parallel computers, Prentice-Hall, Inc., Upper Saddle River, NJ, 1998
• 19: W. Yu, D. Buntinas, R. L. Graham, and D. K. Panda. Efficient and scalable barrier over quadrics and myrinet with a new nic-based collective message passing protocol. ipdps, 09:182b, 2004.

INDEX TERMS

Primary Classification:
  C. Computer Systems Organization
  C.4 PERFORMANCE OF SYSTEMS
      Subjects: Performance attributes

General Terms:
Algorithms, Design, Performance

Keywords:
Manycore, Multicore, NoC, barrier, efficiency, scalability, synchronization