Sandeep N. Bhatt

TCS Journal 2008 Journal Article

Area-time tradeoffs for universal VLSI circuits

• Sandeep N. Bhatt
• Gianfranco Bilardi
• Geppino Pucci

An area-universal VLSI circuit can be programmed to emulate every circuit of a given area, but at the cost of lower area-time performance. In particular, if a circuit with area-time bounds ( A, T ) is emulated by a universal circuit with bounds ( A u, T u ), we say that the universal circuit has blowup A u / A and slowdown T u / T. A central question in VLSI theory is to investigate the inherent costs and tradeoffs of universal circuit designs. Prior to this work, universal designs were known for area- A circuits with O ( 1 ) blowup and O ( log A ) slowdown. Universal designs for the family of area- A circuits containing O ( A 1 + ϵ log A ) vertices, with O ( A ϵ ) blowup and O ( log log A ) slowdown had also been developed. However, the existence of universal circuits with O ( 1 ) slowdown and relatively small blowup was an open question. In this paper, we settle this question by designing an area-universal circuit U A ϵ with O ( 1 / ϵ ) slowdown and O ( A ϵ ) blowup, for any value of the parameter ϵ, with 4 log log A / log A ≤ ϵ ≤ 1. By varying ϵ, we obtain universal circuits which operate at different points in the spectrum of the slowdown-blowup tradeoff. In particular, when ϵ is chosen to be a constant, our universal circuit yields O ( 1 ) slowdown.

SODA Conference 1991 Conference Paper

Tight Bounds for On-Line Tree Embeddings

• Sandeep N. Bhatt
• David S. Greenberg
• Frank Thomson Leighton
• Pangfeng Liu

STOC Conference 1988 Conference Paper

Optimal Simulations by Butterfly Networks (Preliminary Version)

• Sandeep N. Bhatt
• Fan R. K. Chung
• Jia-Wei Hong
• Frank Thomson Leighton
• Arnold L. Rosenberg

FOCS Conference 1988 Conference Paper

Take a Walk, Grow a Tree (Preliminary Version)

• Sandeep N. Bhatt
• Jin-Yi Cai

A simple randomized algorithm is presented for maintaining dynamically evolving binary trees on hypercube networks. The algorithm guarantees that: (1) nodes adjacent in the tree are within distance O(log log N) in an N-processor hypercube, and (2) with overwhelming probability, no hypercube processor is assigned more than O(1+M/N) tree nodes, where M is the number of nodes in the tree. The algorithm is distributed and does not require any global information. This is the first load-balancing algorithm with provably good performance. The algorithm can be used to parallelize efficiently any tree-based computation. It can also be used to maintain efficiently dynamic data structures such as quadtrees. A technique called tree surgery is introduced to deal with dependencies inherent in trees. Together with tree surgery, the study of random walks is used to analyze the algorithm. >

FOCS Conference 1986 Conference Paper

Optimal Simulations of Tree Machines (Preliminary Version)

• Sandeep N. Bhatt
• Fan R. K. Chung
• Frank Thomson Leighton
• Arnold L. Rosenberg

Universal networks offer the advantage that they can execute programs written for simpler architectures without significant run-time overhead. In this paper we investigate simulations of tree machines; the fact that divide-and-conquer algorithms are programmed naturally on trees motivates our investigation. Among various proposals for parallel computing the boolean hypercube has emerged as a particularly versatile network. It is well known that programs for multidimensional grid machines, for example, can be executed on a hypercube with no communications overhead by embedding the grid as a subgraph of the hypercube. Our first result is that a program for any tree machine can be executed on the hypercube with constant overhead. More precisely, every cycle of a synchronous binary tree can be simulated in O(1) cycles on a hypercube, independent of the shape of the tree. The algorithm to embed the tree within the hypercube runs in polynomial time. We also give efficient simulations of arbitrary binary trees on the complete binary tree, the FFT and shuffle-exchange networks. It is natural to ask if any sparse network can simulate every binary tree efficiently. Somewhat surprisingly, we construct a universal bounded-degree network on N nodes for which every N node binary tree is a spanning tree. In other words, every binary tree can be simulated on our universal network with no overhead. This improves previous bounds on the sizes of universal graphs for trees.

STOC Conference 1983 Conference Paper

An Approximation Algorithm for Manhattan Routing (Extended Abstract)

• Brenda S. Baker
• Sandeep N. Bhatt
• Frank Thomson Leighton

STOC Conference 1982 Conference Paper

How to Assemble Tree Machines (Extended Abstract)

• Sandeep N. Bhatt
• Charles E. Leiserson

Many researchers have proposed that ensembles of processing elements be organized as trees. This paper explores how large tree machines may be assembled efficiently from smaller components. A principal constraint that we consider is the limited number of external connections from an integrated circuit chip. We also explore the emerging capability of restructurable VLSI which allows a chip to be customized after fabrication. We give a linear-area chip of m processors and only four off-chip connections which can be used as the sole building block to construct an arbitrarily large complete binary tree. We also present a restructurable linear-area layout of m processors with O (lg m ) pins that can realize an arbitrary binary tree. This layout is based on a solution to the graph-theoretic problem: Given a tree in which each vertex is either black or white, determine how many edges need be cut in order to bisect the tree into equal-size components, each containing exactly half the black and half the white vertices.