Marc Snir

TCS Journal 1991 Journal Article

Size-depth trade-offs for monotone arithmetic circuits

• Marc Snir

Consider the problem of computing the product a 1 A (1)⋯ A (t) b, where A (1), …, A (t) are n × n matrices, a and b are vectors. We show that the size s and depth d of monotone arithmetic circuits for this problem are related as s + n3d = Ω(tn3) Thus, a reduction to depth d = o(t) requires an increase from (optimal) size n 2 t to size n 3 t. A similar trade-off is shown for the evaluation of linear recurrences.

TCS Journal 1990 Journal Article

A complexity theory of efficient parallel algorithms

• Clyde P. Kruskal
• Larry Rudolph
• Marc Snir

This paper outlines a theory of parallel algorithms that emphasizes two crucial aspects of parallel computation: speedup the improvement in running time due to parallelism, and efficiency, the ratio of work done by a parallel algorithm to the work done by a sequential algorithm. We define six classes of algorithms in these terms; of particular interest is the class, EP, of algorithms that achieve a polynomial speedup with constant efficiency. The relations between these classes are examined. We investigate the robustness of these classes across various models of parallel computation. To do so, we examine simulations across models where the simulating machine may be smaller than the simulated machine. These simulations are analyzed with respect to their efficiency and to the reduction in the number of processors. We show that a large number of parallel computation models are related via efficient simulations, if a polynomial reduction of the number of processors is allowed. This implies that the classes EP is invariant across all these models. Many open problems motivated by our approch are listed.

TCS Journal 1990 Journal Article

Communication complexity of PRAMs

• Alok Aggarwal
• Ashok K. Chandra
• Marc Snir

We propose a model, LPRAM, for parallel random access machines with local memory that captures both the communication and computational requirements in parallel computation. For this model, we present several interesting results, including the following: Two n × n matrices can be multiplied in 0(n 3/p) computation time and 0(n2/p 2 3 ) communication steps using p processors (for p = 0(n3/log 3 2 n)). Furthermore, these bounds are optimal for arithmetic on semirings (using +, × only). It is shown that any algorithm that uses comparisons only and that sorts n words requires Ω(n log n/(p log(n/p))) communication steps for 1 < p < n. We also provide an algorithm that sorts n words and uses (-)(n log n/p) computation time and (-)(n log n/p log(n/p))) communication steps. These bounds also apply for computing an n-point FFT graph. It is shown that computing any binary tree τ with n nodes and height h requires Ω(n/p + log n + √h) communication steps, and can always be computed in 0(n/p + min(√n, h)) steps. We also present a simple linear-time algorithm that generates a schedule for computing τ in at most 2D opt(τ) steps, where D opt(τ) represents the minimum communication delay for computing τ. It is also shown that various problems that are expressed as DAGs exhibit a communication-delay/computation-time trade-off.

STOC Conference 1990 Conference Paper

Random Walks on Weighted Graphs, and Applications to On-line Algorithms (Preliminary Version)

• Don Coppersmith
• Peter Doyle
• Prabhakar Raghavan
• Marc Snir

TCS Journal 1989 Journal Article

Techniques for parallel manipulation of sparse matrices

• Clyde P. Kruskal
• Larry Rudolph
• Marc Snir

New techniques are presented for the manipulation of sparse matrices on parallel MIMD computers. We consider the following problems: matrix addition, matrix multiplication, row and column permutation, matrix transpose, matrix vector multiplication, and Gaussian elimination.

STOC Conference 1987 Conference Paper

A Model for Hierarchical Memory

• Alok Aggarwal
• Bowen Alpern
• Ashok K. Chandra
• Marc Snir

In this paper we introduce the Hierarchical Memory Model (HMM) of computation. It is intended to model computers with multiple levels in the memory hierarchy. Access to memory location x is assumed to take time ⌈ log x ⌉. Tight lower and upper bounds are given in this model for the time complexity of searching, sorting, matrix multiplication and FFT. Efficient algorithms in this model utilize locality of reference by bringing data into fast memory and using them several times before returning them to slower memory. It is shown that the circuit simulation problem has inherently poor locality of reference. The results are extended to HMM's where memory access time is given by an arbitrary (nondecreasing) function. Tight upper and lower bounds are obtained for HMM's with polynomial memory access time; the algorithms for searching, FFT and matrix multiplication are shown to be optimal for arbitrary memory access time. On-line memory management algorithms for the HMM model are also considered. An algorithm that uses LRU policy at the successive “levels” of the memory hierarchy is shown to be optimal.

FOCS Conference 1987 Conference Paper

Hierarchical Memory with Block Transfer

• Alok Aggarwal
• Ashok K. Chandra
• Marc Snir

In this paper we introduce a model of Hierarchical Memory with Block Transfer (BT for short). It is like a random access machine, except that access to location x takes time f(x), and a block of consecutive locations can be copied from memory to memory, taking one unit of time per element after the initial access time. We first study the model with f(x) = xα for 0 ≪ α ≪ 1. A tight bound of θ(n log log n) is shown for many simple problems: reading each input, dot product, shuffle exchange, and merging two sorted lists. The same bound holds for transposing a √n × √n matrix; we use this to compute an FFT graph in optimal θ(n log n) time. An optimal θ(n log n) sorting algorithm is also shown. Some additional issues considered are: maintaining data structures such as dictionaries, DAG simulation, and connections with PRAMs. Next we study the model f(x) = x. Using techniques similar to those developed for the previous model, we show tight bounds of θ(n log n) for the simple problems mentioned above, and provide a new technique that yields optimal lower bounds of Ω(n log2n) for sorting, computing an FFT graph, and for matrix transposition. We also obtain optimal bounds for the model f(x)= xα with α ≫ 1. Finally, we study the model f(x) = log x and obtain optimal bounds of θ(n log*n) for simple problems mentioned above and of θ(n log n) for sorting, computing an FFT graph, and for some permutations.

TCS Journal 1986 Journal Article

A unified theory of interconnection network structure

• Clyde P. Kruskal
• Marc Snir

The relationship between the topology of interconnection networks and their functional properties is examined. Graph-theoretical characterizations are derived for delta networks, which have a simple routing scheme, and for bidelta networks, which have the delta property in both directions. Delta networks are shown to have a recursive structure. Bidelta networks are shown to have a unique topology. The definition of bidelta network is used to derive in a uniform manner the labelling schemes that define the omega networks, indirect binary cube networks, flip networks, baseline networks, modified data manipulators and two new networks; these schemes are generalized to arbitrary radices. The labelling schemes are used to characterize networks with simple routing. In another paper (Kruskal/Snir, 1984), we characterize the networks with optimal performance/cost ratio. Only the multistage shuffle-exchange networks have both optimal performance/cost ratio and simple routing. This helps explain why few fundamentally different geometries have been proposed.

TCS Journal 1985 Journal Article

Lower bounds on probabilistic linear decision trees

• Marc Snir

The power of probabilistic linear decision trees is examined. It is shown that the standard arguments used to prove lower bounds on deterministic linear decision trees apply to probabilistic linear decision trees as well. Examples are next given of problems which randomization helps solving.

FOCS Conference 1984 Conference Paper

Applications of Ramsey's Theorem to Decision Trees Complexity (Preliminary Version)

• Shlomo Moran
• Marc Snir
• Udi Manber

Combinatorial techniques for extending lower bounds results for decision trees to general types of queries are presented. We consider problems, which we call order invariant, that are defined by simple inequalities between inputs. A decision tree is called k-bounded if each query depends on at most k variables. We make no further assumptions on the type of queries. We prove that we can replace the queries of any k-bounded decision tree that solves an order invariant problem over a large enough input dornain with k-bounded queries whose outcome depends only on the relative order of the inputs. As a consequence, all existing lower bounds for comparison based algorithms are valid for general k-bounded decision trees, where k is a constant. We also prove an /spl Omega/(n log n) lower bound for the element uniqueness problem and several other problems for any k-bounded decision tree, such that k - )(n/sup c/) and c < 1/2. This lower bound is tight since that there exist n/sup 1/2/-bounded decision trees of complexity 0(n) that solve the element uniqueness problem. All the lower bounds mentioned above are shown to hold for nondeterministic and probabilistic decision trees as well.

TCS Journal 1982 Journal Article

Comparisons between linear functions can help

• Marc Snir

An example is provided of a sorting-type decision problem which can be solved in fewer steps by using comparisons between linear functions of the inputs, rather than comparisons between the inputs themselves. This disproves a conjecture of Yao [14] and Yap [16]. Several extensions are presented.