Clark D. Thompson

FOCS Conference 1990 Conference Paper

Asymptotically Tight Bounds for Computing with Faulty Arrays of Processors (Extended Abstract)

• Christos Kaklamanis
• Anna R. Karlin
• Frank Thomson Leighton
• Victor Milenkovic
• Prabhakar Raghavan
• Satish Rao
• Clark D. Thompson
• A. Tsantilas

The computational power of 2-D and 3-D processor arrays that contain a potentially large number of faults is analyzed. Both a random and a worst-case fault model are considered, and it is proved that in either scenario low-dimensional arrays are surprisingly fault tolerant. It is also shown how to route, sort, and perform systolic algorithms for problems such as matrix multiplication in optimal time on faulty arrays. In many cases, the running time is the same as if there were no faults in the array (up to constant factors). On the negative side, it is shown that any constant congestion embedding of an n*n fault-free array on an n*n array with Theta (n/sup 2/) random faults (or Theta (log n) worst-case faults) requires dilation Theta (log n). For 3-D arrays, knot theory is used to prove that the required dilation is Omega ( square root log n). >

STOC Conference 1985 Conference Paper

Provably Good Routing in Graphs: Regular Arrays

• Prabhakar Raghavan
• Clark D. Thompson

FOCS Conference 1983 Conference Paper

Global Wire Routing in Two-Dimensional Arrays (Extended Abstract)

• Richard M. Karp
• Frank Thomson Leighton
• Ronald L. Rivest
• Clark D. Thompson
• Umesh V. Vazirani
• Vijay V. Vazirani

We examine the problem of routing wires on a VLSI chip, where the pins to be connected are arranged in a regular rectangular array. We obtain tight bounds for the worst-case "channel-width" needed to route an n × n array, and develop provably good heuristics for the general case. An interesting "rounding algorithm" for obtaining integral approximations to solutions of linear equations is used to show the near-optimality of single-turn routings in the worst-case.

STOC Conference 1979 Conference Paper

Area-Time Complexity for VLSI

• Clark D. Thompson

The complexity of the Discrete Fourier Transform (DFT) is studied with respect to a new model of computation appropriate to VLSI technology. This model focuses on two key parameters, the amount of silicon area and time required to implement a DFT on a single chip. Lower bounds on area (A) and time (T) are related to the number of points (N) in the DFT: AT 2 ≥ N 2 /16. This inequality holds for any chip design based on any algorithm, and is nearly tight when T = θ (N 1/2 ) or T = θ (log N). A more general lower bound is also derived: AT x = Ω(N 1+x/2 ), for 0≤×≤2.

STOC Conference 1976 Conference Paper

Sorting on a Mesh-Connected Parallel Computer

• Clark D. Thompson
• H. T. Kung 0001