In this paper we describe the hardware and software of a system which we have implemented to accelerate the physical design of gate arrays. In contrast to nearly all other reported approaches, our approach to hardware acceleration is to augment a single-user host workstation with a general-purpose microprogrammable slave processor having a large private memory. One or more such slaves can be attached. We have implemented placement improvement on the system, achieving a 20 x speedup vs. a high-level host implementation. We give performance results, which are comparable to those reported elsewhere for mainframe implementations.

A distributed algorithm is presented that constructs the minimum-weight spanning tree in a connected undirected graph with distinct edge weights.A processor exists at each node of the graph, knowing initially only the weights of the adjacent edges.The processors obey the same algorithm and exchange messages with neighbors until the tree is constructed.The total number of messages required for a graph of N nodes and E edges is at most 5N log2N + 2E, and a message contains at most one edge weight plus log28N bits.The algorithm can be initiated spontaneously at any node or at any subset of nodes.

In this paper the problem of sorting multisets is considered. An information theoretic lower bound on the number of three branch comparisons is obtained, and it is shown that this bound is asymptotically attainable. It is shown that the multiplicities of a set can only be obtained by comparisons if the total order is discovered in the process. A lower bound on finding the mode of a multiset as a function of the actual multiplicity is given, and it is demonstrated that the bound can be achieved to within a multiplicative constant. The determination of the intersection of two multisets is also discussed, and partial results, including a generalization of Reingold’s result for determining whether or not two sets have a nonempty intersection, are obtained.

We consider one origin shortest path and minimum spanning tree computations in weighted graphs. We give a lower bound on the number of analytic functions of the input computed by a tree program which solves either of these problems equal to half the number of worst-case comparisons which well-known algorithms attain. We consider the work necessary to update spanning tree and shortest path solutions when the graph is altered after the computation has terminated. Optimal or near-optimal algorithms are attained for the cases considered. The most notable result is that a spanning tree solution can be updated in $O(n)$ when a new node is added to an n-node graph whose minimum spanning tree is known.

We present a new algorithm for finding the shortest path between each pair of nodes in a directed nonnegatively weighted graph. Our algorithm has average running time $O(n^2 \log ^2 n)$ where the graph has n nodes in contrast to previous algorithms in the literature, all of whose average running times are $O(n^3 )$ for this problem.

A (d, r) circuit is a d-valued logical circuit in which each element has fan-in at most r and can compute any r-argument d-valued logical function in unit time. In this paper we review results previously published on the computation time of such circuits for addition and multiplication and for computation of general Boolean functions. We also explicitly state hitherto unpublished but known results on the time necessary to divide in such circuits.

In this note we establish a new upper bound on the time to compute classes of switching functions. As did Shannon and Lupanov in their study of the number of elements necessary to compute switching functions, we base our method on a Shannon expansion about a certain number of variables of the function being computed.

No abstract available.

Winograd has considered the time necessary to perform numerical addition and multiplication and to perform group multiplication by means of logical circuits consisting of elements each having a limited number of input lines and unit delay in computing their outputs. In this paper the same model as he employed is adopted, but a new lower bound is derived for group multiplication—the same as Winograd's for an Abelian group but in general stronger. Also a circuit is given to compute the multiplication which, in contrast to Winograd's, can be used for non-Abelian groups. When the group of interest is Abelian the circuit is at least as fast as his. By paralleling his method of application of his Abelian group circuit, it is possible also to lower the time necessary for numerical addition and multiplication.