Title :
You Can Get There From Here: Connectivity of Random Graphs on Grids
Author :
Levitan, Steven P.
Author_Institution :
Univ. of Pittsburgh, Pittsburgh
Abstract :
Using random graphs, we address the need for non-local communication channels in emerging nanotechnology interconnection structures. In this model, a grid of radicNtimesradicN processing elements are connected by non-local wires, which are fabricated as a post processing self-assembly step by electro-chemical migration of functionalized carbon nanotubes. We show that under reasonable assumptions, 80% of the cells can be connected into a single spanning tree with only N wires deposited randomly across the surface of the substrate.
Keywords :
integrated circuit interconnections; nanowires; random processes; self-assembly; trees (mathematics); electrochemical migration; functionalized carbon nanotubes; nanotechnology interconnection structures; nonlocal communication channels; nonlocal wires; random graphs; self-assembly; spanning tree; Carbon nanotubes; Chemical elements; Circuit simulation; Coherence; Communication channels; Integrated circuit interconnections; Nanotechnology; Permission; Telecommunication network reliability; Wires; Carbon Nanotubes; Cellular Automata; Design; Nanotechnology; Random Graphs; Reliability; Theory;
Conference_Titel :
Design Automation Conference, 2007. DAC '07. 44th ACM/IEEE
Conference_Location :
San Diego, CA
Print_ISBN :
978-1-59593-627-1
