You Can Get There From Here: Connectivity of Random Graphs on Grids

Author

Levitan, Steven P.

Author_Institution

Univ. of Pittsburgh, Pittsburgh

fYear

2007

fDate

4-8 June 2007

Firstpage

272

Lastpage

273

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;

fLanguage

English

Publisher

ieee

Conference_Titel

Design Automation Conference, 2007. DAC '07. 44th ACM/IEEE

Conference_Location

San Diego, CA

ISSN

0738-100X

Print_ISBN

978-1-59593-627-1

Type

conf

Filename

4261188