John E. Savage

TCS Journal 2008 Journal Article

Nanowire addressing with randomized-contact decoders

• Eric Rachlin
• John E. Savage

Methods for assembling crossbars from nanowires (NWs) have been designed and implemented and methods for controlling individual NWs within a crossbar have also been proposed. However, implementation remains a challenge. A NW decoder is a device that controls many NWs with a much smaller number of lithographically produced mesoscale wires (MWs). Unlike traditional demultiplexers, all proposed NW decoders are assembled stochastically. In a randomized-contact decoder (RCD), for example, field-effect transistors are randomly created at about half of the NW/MW junctions. In this paper, we tightly bound the number of MWs required to produce a correctly functioning RCD with high probability. We show that the number of MWs is logarithmic in the number of NWs, even when manufacturing errors occur. We also analyze the overhead associated with controlling a stochastically assembled decoder. As we explain, lithographically-produced control circuitry must store information regarding which MWs control which NWs. This requires more area than the MWs themselves, but has received little attention elsewhere. Finally we analyze several simple testing algorithms for configuring this control circuitry. We demonstrate an unexpected tradeoff between testing time and the number of MWs required by an RCD.

TCS Journal 2001 Journal Article

Generalized scans and tridiagonal systems

• Paul F. Fischer
• Franco P. Preparata
• John E. Savage

Motivated by the analysis of known parallel techniques for the solution of linear tridiagonal system, we introduce generalized scans, a class of recursively defined length-preserving, sequence-to-sequence transformations that generalize the well-known prefix computations (scans). Generalized scan functions are described in terms of three algorithmic phases, the reduction phase that saves data for the third or expansion phase and prepares data for the second phase which is a recursive invocation of the same function on one fewer variable. Both the reduction and expansion phases operate on bounded number of variables, a key feature for their parallelization. Generalized scans enjoy a property, called here protoassociativity, that gives rise to ordinary associativity when generalized scans are specialized to ordinary scans. We show that the solution of positive-definite block tridiagonal linear systems can be cast as a generalized scan, thereby shedding light on the underlying structure enabling known parallelization schemes for this problem. We also describe a variety of parallel algorithms including some that are well known for tridiagonal systems and some that are much better suited to distributed computation.

STOC Conference 1980 Conference Paper

Graph Pebbling with Many Free Pebbles can be Difficult

• David A. Carlson
• John E. Savage