Tech Report CS-03-09

Efficient Data Storage in Large Nanoarrays

Lee-Ad J. Gottlieb, John E. Savage and Arkady Yerukhimovich

August 2003

Abstract:

We explore the storage of data in very large crossbars with dimensions measured in nanometers (nanoarrays) when h-hot addressing is used to bridge the nano/micro gap. In $h$-hot addressing h of b micro-level wires are used to address a single nanowire. Proposed nanotechnologies allow subarrays of 1s (stores) or 0s (restores) to be written. When stores and restores are used, we show exponential reductions in programming time for prototypical problems over stores alone. Under both operations, it is NP-hard to find optimal array programs. Under stores alone it is NP-hard to find good approximations to this problem, a question that is open when restores are allowed. Because of the difficulty of programming multiple rows at once, we explore the programming of single rows under h-hot addressing. We also identify conditions under which good approximations to these problems exist.