Load-balanced switch fabrics offer the promise of very high capacity without the requirement of increased operating rates. We provide a novel solution to the well-known cell reordering problem, which arises in load-balanced switch fabrics if different paths through the switch fabric have different delays. We give a simple sorting circuit, easily implemented in hardware, that can be placed in the final stage of the fabric. This minimizes the delay through the fabric and removes any constraints on operation of the first stage. We show that the sorting circuit can be implemented to operate at a rate of one cell per cycle; we give a probabilistic analysis of required queue occupancies, both at the sorting circuit and at midstage elements; we also briefly discuss congestion control in load-balanced switch fabrics.

Numerous solutions have been proposed in the literature to eliminate reordering in load-balanced switch fabrics. A common approach involves uniform frames, in which every cell of a frame has the same destination. This can achieve 100% throughput with relatively small average traffic delay; however, the worst-case delay may be unbounded. We show that with a slight speedup in the switch fabric we can guarantee satisfactory worst-case delay bounds, without sacrificing other desirable properties. Furthermore, experimental results demonstrate that our scheme improves worst-case delay in realistic traffic scenarios, as compared to previous uniform-frame solutions.

We analyze an iterative algorithm that approximates all roots of a univariate polynomial. The algorithm is based on (hardware) floating-point eigenvalue computation of a generalized companion matrix. With some assumptions, we show that it approximates the roots to floating-point accuracy within about logρ/e X(P) iterations, where ∈ is the relative error of floating-point arithmetic, ρ is the relative separation of the roots, and X(P) is the condition number of the polynomial. Each iteration requires an n × n floating-point eigenvalue computation, n the polynomial degree, and evaluation of the polynomial to floating-point accuracy at n points. On some hard examples of ill-conditioned polynomials, e.g. high-degree Wilkinson polynomials, the algorithm is an order of magnitude faster than the best alternative.

Article Free Access Share on Exact computations of the inertia symmetric integer matrices Author: Steven Fortune Bell Laboratories, Murray Hill, NJ Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims STOC '00: Proceedings of the thirty-second annual ACM symposium on Theory of computingMay 2000 Pages 556–564https://doi.org/10.1145/335305.335374Published:01 May 2000Publication History 2citation348DownloadsMetricsTotal Citations2Total Downloads348Last 12 Months24Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Let P be a polyhedral subdivision in lR3 with a t,otal of n faces.We show ghat t,here is an embedding u of the vertices, edges, and facets of P into a subdivision &, where every vertes coordinate of Q is an integral multiple of 2-p"fian+'l.For each face f of P, the Hausdorff distance in the 1;, metric between f and o(f) is at most, 3/2.The embedding u preserves or collapses vertical order on faces of P. The subdivision Q has O(n4) vertices in the worst, case, and can be computed in the same time.

Article Free Access Share on Average-case ray shooting and minimum weight triangulations Authors: Boris Aronov Computer and Information Science, Polytechnic University, Brooklyn, NY Computer and Information Science, Polytechnic University, Brooklyn, NYView Profile , Steven Fortune Bell Laboratories, Murray Hill, New Jersey Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims SCG '97: Proceedings of the thirteenth annual symposium on Computational geometryAugust 1997 Pages 203–211https://doi.org/10.1145/262839.262972Published:01 August 1997Publication History 6citation248DownloadsMetricsTotal Citations6Total Downloads248Last 12 Months10Last 6 weeks1 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Engineers designing and installing outdoor and indoor wireless communications systems need effective and practical tools to help them determine base station antenna locations for adequate signal coverage. Computer-based radio propagation prediction tools are now often used in designing these systems. We assess the performance of such a propagation tool based on ray-tracing and advanced computational methods. We have compared its predictions with outdoor experimental data collected in Manhattan and Boston (at 900 MHz and 2 GHz). The comparisons show that the computer-based propagation tool can predict signal strengths in these environments with very good accuracy. The prediction errors are within 6 dB in both mean and standard deviation. This shows that simulations, rather than costly field measurements, can lead to accurate determination of the coverage area for a given system design.

Geometric algorithmsare usually described assuming that arithmetic operations are performed exactly on real numbers.A program implemented using a naive substitution of floating-point arithmetic for real arithmetic can fail, since geometric primitives depend upon sign-evaluation and may not be reliable if evaluated approximately.Geometric primitives are reliable if evaluated exactly with integer arithmetic, but this degrades performance since software extended-precision arithmetic is required.We describe static-analysis techniques that reduce the performance cost of exact integer arithmetic used to implement geometric algorithms.We have used the techniques for a number of examples, including line-segment intersection in two dimensions, Delaunay triangulations, and a three-dimensional boundary-based polyhedral modeller.In general, the techniques are appropriate for algorithms that use primitives of relatively low algebraic total degree, e.g., those involving flat objects (points, lines, planes) in two or three dimensions.The techniques have been packaged in a preprocessor for reasonably convenient use.

We experiment with exact integer arithmetic to implement primitives for geometric algorithms. Naive use of exact arithmetic—either modular or multiprecision integer—increases execution time dramatically over the use of floating-point arithmetic. By combining tuned multiprecision integer arithmetic and a floating-point filter based on interval analysis, we can obtain the effect of exact integer arithmetic at a cost close to that of floating-point arithmetic. We describe an experimental expression compiler that conveniently packages our techniques.

We show that two Delaunay triangulation algorithms, a diagonal-flipping algorithm and an incremental algorithm, can be implemented in approxiamte arithmetic. The two algorithms have worst-case running time O(n2) on a set of n sites. The correctness assertion is that the algorithms produce a triangulation of the set of sites so that each triangle has an “almost empty” circumcircle, i.e., a circumscribing pseudocircle slightly contracted from the circumcircle contains no sites in its interior.

We analyze the behavior of two line arrangement algorithms, a sweepline algorithm and an incremental algorithm, in approximate arithmetic.

Geometric algorithms are explored, assuming that arithmetic is done approximately. Stable algorithms are described for two geometric problems. The first algorithm computes two-dimensional convex hulls. The main result is that a triangulation of a set of points in the plane can be maintained stably. The second algorithm deals with line arrangements in the plane.>

Article Free Access Share on The furthest-site geodesic Voronoi diagram Authors: B. Aronov Courant Institute of Mathematical Sciences, NYU Courant Institute of Mathematical Sciences, NYUView Profile , S. Fortune AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile , G. Wilfong AT&T Bell Laboratories, Murray Hill, NJ AT&T Bell Laboratories, Murray Hill, NJView Profile Authors Info & Claims SCG '88: Proceedings of the fourth annual symposium on Computational geometryJanuary 1988 Pages 229–240https://doi.org/10.1145/73393.73417Published:06 January 1988Publication History 2citation531DownloadsMetricsTotal Citations2Total Downloads531Last 12 Months25Last 6 weeks2 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

Article Free Access Share on Planning constrained motion Authors: Steven Fortune AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile , Gordon Wilfong AT&T Bell Laboratories, Murray Hill, New Jersey AT&T Bell Laboratories, Murray Hill, New JerseyView Profile Authors Info & Claims STOC '88: Proceedings of the twentieth annual ACM symposium on Theory of computingJanuary 1988 Pages 445–459https://doi.org/10.1145/62212.62256Published:01 January 1988Publication History 50citation396DownloadsMetricsTotal Citations50Total Downloads396Last 12 Months25Last 6 weeks3 Get Citation AlertsNew Citation Alert added!This alert has been successfully added and will be sent to:You will be notified whenever a record that you have chosen has been cited.To manage your alert preferences, click on the button below.Manage my AlertsNew Citation Alert!Please log in to your account Save to BinderSave to BinderCreate a New BinderNameCancelCreateExport CitationPublisher SiteeReaderPDF

We present a transformation that can be used to compute Voronoi diagrams with a sweepline technique. The transformation is used to obtain simple algorithms for computing the Voronoi diagram of point sites, of line segment sites, and of weighted point sites. All algorithms have O(n log n) worst case running time and use O(n) space.

We study the problem of planning simultaneous motion for two robot arms that are modeled on the Stanford arm. The arms have two degrees of freedom and must move in a workspace, avoiding obstacles and each other. We develop an O(n2logn) algorithm for planning motion of two arms with tips together, and an O(n3) algorithm for independent but synchronized motion. Here n is the total number of walls of the obstacles.

We study grasps by a robot hand with three spring-loaded fingers. In two dimensions, the hand can grasp any polygon stably. That is, the grip is at a local minimum of the potential energy function defined by the springs of the fingers, ignoring friction. Surprisingly, under some conditions an equilibrium grasp on a circle is unstable even with respect to translation. In three dimensions, the hand can grasp and lift any cylindrical surface with a polygonal cross-section. In contrast we show that a hand with finger angles fixed at 120°, as proposed by Hanafusa and Asada, generally can not achieve a two-dimensional stable grip in the absence of friction.

We study grasps by a robot hand in the absence of friction. In two dimensions, a hand with three spring-loaded fingers and five degrees of freedom can achieve an equilibrium grasp on any object described by a polygon. Furthermore, the grasp is stable, that is, at a local minimum of the potential energy function defined by the springs of the fingers. In three dimensions, the hand can grasp any cylinder. In contrast, if the degrees of freedom of the hand are restricted to correspond to a hand built by Hanafusa and Asada, stable grips on a polygon cannot in general be achieved.

We consider the computation of finite semigroups using unbounded fan-in circuits. There are constant-depth, polynomial size circuits for semigroup product iff the semigroup does not contain a nontrivial group as a subset. In the case that the semigroup in fact does not contain a group, then for any primitive recursive function f, circuits of size O(nf−1(n)) and constant depth exist for the semigroup product of n elements. The depth depends upon the choice of the primitive recursive function f. The circuits not only compute the semigroup product, but every prefix of the semigroup product. A consequence is that the same bounds apply for circuits computing the sum of two n-bit numbers.

Typed lambda (?`-) calculi provtde convement mathematical settings in which to investigate the effects of type structure on the function definmon mechamsm m programming languages.Lambda expressaons mtm~c programs that do not use while loops or carcular function definitions.Two typed ?`-calculi are investigated, the sunply typed ?`-calculus, whose types are similar to Pascal types, and the second-order typed ?,-calculus, which has a type abstractaon mechamsm simdar to that of modern data abstraction languages such as ALPHARD.Two related questions are considered for each calculus: (1) What functaons are definable m the calculus?and (2) How difficult is the proof that all expressions in the calculus are normahzable 0.e., that all computaUons termmate)* The simply typed calculus only defines elementary functtons.Normahzation for this calculus ~s provable using commonplace forms of reasoning formalazable m Peano arithmetic The second-order calculus defines a huge hierarchy of funcuons going far beyond Ackermann's function These funcuons are so rapidly increasing that Peano arithmetic cannot prove that they are total In fact, normalizataon for the second-order calculus cannot be proved even m second-order Peano artthmetic, nor m Peano anthmettc augmented by all true statements Also d~scussed are the lmphcataons of the present ?`-calculusresults for the programming languages PASCAL, ALPHARD, RUSSELL, and MODEL.

Hartmanis and Berman have conjectured that all $NP$-complete sets are polynomial time isomorphic. A consequence of the conjecture is that there are no sparse $NP$-complete sets. We show that the existence of an $NP$-complete set whose complement is sparse implies $P = NP$. We also show that if there is a polynomial time reduction with sparse range to a $PTAPE$-complete set, then $P = PTAPE$.

A model of computation based on random access machines operating in parallel and sharing a common memory is presented. The computational power of this model is related to that of traditional models. In particular, deterministic parallel RAM's can accept in polynomial time exactly the sets accepted by polynomial tape bounded Turing machines; nondeterministic RAM's can accept in polynomial time exactly the sets accepted by nondeterministic exponential time bounded Turing machines. Similar results hold for other classes. The effect of limiting the size of the common memory is also considered.