Wire cost and communication analysis of self-assembled interconnect models for Networks-on-Chip

ABSTRACT

Building complex interconnect networks in a bottom-up way, for example by using self-assembling techniques, represents an ultimate challenge for building large-scale emerging computing devices. Due do the general lack of precise control over many self-assembling techniques, such interconnects are expected to be largely unstructured.

In this paper we introduce two simple wire growth models for non-classical self-assembled network topologies. The models generate different unstructured and physically plausible network topologies. We then investigate the design trade-offs of such interconnect networks within a network-on-chip (NoC) simulation framework. In particular, we analyze the network's wiring cost and the communication properties by varying the framework's parameters. Our primary goal is to (1) investigate and understand the characteristics of such self-assembled networks and (2) to ultimately use these insights to tune experimental self-assembly process parameters. The quantitative simulation results show that unstructured NoC topologies obtained by the growth models show specific wire-length distributions that are beneficial for the communication and minimize the wiring cost. To support this result, we have also used an evolutionary optimization framework for the evolution of NoC topologies under given cost and communication requirements. Our results and the evaluation framework have implications for the design of interconnect architectures.

References

1. J. E. Baker. Adaptive selection methods for genetic algorithms. In Proceedings of the 1^st International Conference on Genetic Algorithms, pages 101--111, Hillsdale, NJ, USA, 1985. L. Erlbaum Associates Inc.
2. K. Banerjee and N. Srivastava. Are carbon nanotubes the future of VLSI interconnections? In Proceedings of the 43^rd Annual Conference on Design Automation (DAC '06), pages 809--814, 2006.
3. M. T. Borgström, G. Immink, B. Ketelaars, R. Algra, and E. P. A. M. Bakkers. Synergetic nanowire growth. Nature Nanotechnology, 2:541--544, 2007.
4. J. A. Davis, R. Venkatesan, A. Kaloyeros, M. Beylansky, S. J. Souri, K. Banerjee, K. C. Saraswat, A. Rahman, R. Reif, and J. D. Meindl. Interconnect limits on gigascale integration (GSI) in the 21 ^st century. Proceedings of the IEEE, 89(3):305--324, 2001.
5. G. de Micheli and L. Benini, editors. Networks on Chips: Technology and Tools. Morgan Kauffmann, 2006.
6. V. M. Eguéluz, D. R. Chialvo, G. A. Cecchi, M. Baliki, and A. V. Apkarian. Scale-free brain functional networks. Physical Review Letters, 94:018102, 2005.
7. A. E. Eiben and J. E. Smith. Introduction to Evolutionary Computing. Springer-Verlag, Berlin, Heidelberg, 2003.
8. B. Hellwig. A quantitative analysis of the local connectivity between pyramidal neurons in layers 2/3 of the rat visual cortex. Biological Cybernetics, 82:111--121, 2000.
9. R. Ho, K. W. Mai, and M. A. Horowitz. The future of wires. Proceedings of the IEEE, 89(4):490--504, 2001.
10. R. F. i Cancho, C. Janssen, and R. V. Sole. Topology of technology graphs: Small world patterns in electronic circuits. Physical Review E, 64:046119, 2001.
11. J. K. Kleinberg. Navigation in a small world. Nature, 406:845, 2000.
12. B. Kozma, M. B. Hastings, and G. Korniss. Diffusion processes on power-law small-world networks. Physical Review Letters, 95:018701, 2005.
13. S. P. Levitan. You can get there from here: Connectivity of random graphs on grids. In Proceedings of the Design Automation Conference (DAC 2007), pages 272--273, San Diego, CA, Jun 4--7 2007. ACM.
14. J. D. Meindl. Interconnect opportunities for gigascale integration. IEEE Micro, 23(3):28--35, 2003.
15. P. P. Pande, C. Grecu, M. Jones, A. Ivanov, and R. Saleh. Performance evaluation and design trade-offs for network-on-chip interconnect architectures. IEEE Transactions on Computers, 54(8):1025--1040, 2005.
16. T. Petermann and P. D. L. Rios. Physical realizability of small-world networks. Physical Review E, 73:026114, 2006.
17. O. Sporns, D. R. Chialvo, M. Kaiser, and C. C. Hilgtag. Organization, development, and function of complex brain networks. Trends in Cognitive Sciences, 8(9):418--425, 2004.
18. C. Teuscher. Nature-inspired interconnects for emerging large-scale network-on-chip designs. Chaos, 17(2):026106, 2007.
19. C. Teuscher, N. Gulbahce, and T. Rohlf. Assessing random dynamical network architectures for nanoelectronics. In Proceedings of the 2008 IEEE/ACM International Symposium on Nanoscale Architectures (NANOARCH 2008), pages 16--23. IEEE Press, 2008.
20. C. Teuscher and A. A. Hansson. Non-traditional irregular interconnects for massive scale SoC. In Proceedings of the IEEE International Symposium on Circuits and Systems (ISCAS), pages 2785--2788, 2008.
21. J. Tour, W. L. V. Zandt, C. P. Husband, S. M. Husband, L. S. Wilson, P. D. Franzon, and D. P. Nackashi. Nanocell logic gates for molecular computing. IEEE Transactions on Nanotechnology, 1(2):100--109, 2002.
22. H.-L. Wang, W. Li, E. Akhadov, and Q. Jia. Electrodeless deposition of metals and metal nanoparticle using conducting polymers. Chemistry of Materials, 19:520, 2007.
23. D. J. Watts and S. H. Strogatz. Collective dynamics of 'small-world' networks. Nature, 393:440--442, 1998.
24. S. Wolfram. Cellular automata as models of complexity. Nature, 311:419--424, December 4 1984.
25. Y. Wu, J. Xiang, C. Yang, W. Lu, and C. M. Lieber. Single-crystal metallic nanowires and metal/semiconductor nanowire heterostructures. Nature, 430:61--65, 2004.
26. H. Ye, Z. Gu, T. Yu, and D. H. Gracias. Integrating nanowires with substrates using directed assembly and nanoscale soldering, IEEE Transactions on Nanotechnology, 5(1):62--66, 2006.
27. V. V. Zhirnov and D. J. C. Herr. New frontiers: Self-assembly in nanoelectronics. IEEE Computer, 34:34--43, January 2001.

Index Terms

• Networks

  • Network architectures