Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman
wraparound. The former result is surprising, since it contradicts the prior "folklore " belief that the bisection width is n. We also show that every set of k nodes has at least k 2 log k...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman
Abstract This paper analyzes the effect of virtual channels on the performance of wormhole routing algorithms. We show that in a network in which each edge can emulate up to q virtual channels, it is...
Richard Cole, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal
We consider the problem of extending the analysis of balls and bins processes to cover deletions. In particular, we are interested in the case where the system maintains a fixed load, and deletions...
Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman
Abstract. Modern hardware and software systems promote a view of parallel systems in which interprocessor communications are uniform, and rather expensive, in cost. Such systems demand efficient...
On Trading Task Reallocation for Thread Management in Multiprocessors (2007)
Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman, Where L
Most general-purpose multiprocessors are time-shared among multiple users. When a user arrives, s/he requests a submachine of size appropriate to his/her computation; the processor-allocation...
William I. Gasarch, Ramesh K. Sitaraman, Carl H. Smith, Mahendran Velauthapillai
Putnam [12] was the first to notice that there was no mechanism capable of learning all the computable functions. Gold [6] was the first to formally prove, in full generality, Putnam's...
Designing overlay multicast networks for streaming (2003)
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to...
Designing Overlay Multicast Networks for Streaming (2003)
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to...
Designing overlay multicast networks for streaming (2003)
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to...
Designing overlay multicast networks for streaming (2003)
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to...
Designing Overlay Multicast Networks for Streaming (2003)
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to...
Designing overlay multicast networks for streaming (2003)
Konstantin Andreev, Bruce M. Maggs, Adam Meyerson, Ramesh K. Sitaraman
In this paper we present a polynomial time approximation algorithm for designing a multicast overlay network. The algorithm finds a solution that satisfies capacity and reliability constraints to...
Tree Layout for Internal Network Characterizations in Multicast Networks (2001)
Micah Adler, Tian Bu, Ramesh K. Sitaraman, Don Towsley
There has been considerable activity recently to develop monitoring and debugging tools for a multicast session (tree). With these tools in mind, we focus on the problem of how to lay out multicast...
Optimal clustering of treesweep computations for high-latency parallel environments (1999)
Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman
AbstractÐModern hardware and software systems promote a view of parallel systems in which interprocessor communications are uniform and rather expensive in cost. Such systems demand efficient...
VIRTUAL CHANNELS IN WORMHOLE ROUTERS (1999)
Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman
This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We study wormhole routing on network in which each physical channel, i.e., communication link,...
Richard Cole Bruce, Bruce M. Maggs, Friedhelm Meyer, Heide Michael Mitzenmacher, Andrea W. Richa, Klaus Schroder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
On Balls and Bins with Deletions (1998)
Richard Cole Alan, Bruce M. Maggs, Michael Mitzenmacher, Andr'ea W. Richa, Ramesh K. Sitaraman, Eli Upfal
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Klaus Schröder, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
On Balls and Bins with Deletions (1998)
Richard Cole, Alan Frieze, Bruce M. Maggs, Michael Mitzenmacher, Andréa W. Richa, Andr'ea W. Richa, ...
We consider the problem of extending the analysis of balls and bins processes where a ball is placed in the least loaded of d randomly chosen bins to cover deletions. In particular, we are interested...
Richard Cole, Bruce M. Maggs, Michael Mitzenmacher, Friedhelm Meyer, Heide Michael Mitzenmacher, ...
In this paper we study randomized algorithms for circuit switching on multistage networks related to the butterfly. We devise algorithms that route messages by constructing circuits (or paths) for...
The Reconfigurable Ring of Processors: Fine-Grain Tree-Structured Computations (1997)
Arnold Rosenberg Vittorio, Arnold L. Rosenberg, Vittorio Scarano, Ramesh K. Sitaraman
We study fine-grain computation on the Reconfigurable Ring of Processors (RRP), a parallel architecture whose processing elements (PEs) are interconnected via a multiline reconfigurable bus, each of...
Region-based Call Admission Algorithms for Wireless Cellular Networks (1997)
Kamal K. Kasera, Ramesh K. Sitaraman
Current advances in the area of wireless cellular networks, and the advent of real time services have mandated the need for an efficient network call admission controller. In this paper, we develop...
On the Bisection Width and Expansion of Butterfly Networks (1997)
Claudson Bornstein Ami, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman, Tal Yatzkar
This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. Previously it was known that the bisection width of an n-input butterfly with...
On the Bisection Width and Expansion of Butterfly Networks (1997)
Claudson F. Bornstein, Ami Litman, Bruce M. Maggs, Ramesh K. Sitaraman, Tal Yatzkar
This paper proves tight bounds on the bisection width and expansion of butterfly networks with and without wraparound. We show that the bisection width of an n-input butterfly network is 2( p 2...
The Reconfigurable Ring of Processors: Fine-Grain Tree-Structured Computations (1997)
Arnold Rosenberg, Vittorio Scarano, Ramesh K. Sitaraman
We study fine-grain computation on the Reconfigurable Ring of Processors (RRP), a parallel architecture whose processing elements (PEs) are interconnected via a multiline reconfigurable bus, each of...
Reconfiguring Arrays with Faults Part I: Worst-Case Faults (1997)
Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman
. In this paper we study the ability of array-based networks to tolerate worst-case faults. We show that an N \Theta N two-dimensional array can sustain N 1\Gammaffl worst-case faults, for any fixed...
Reconfiguring Arrays with Faults Part I: Worst-Case Faults (1997)
Richard J. Cole, Bruce M. Maggs, Ramesh K. Sitaraman
In this paper we study the ability of array-based networks to tolerate worstcase faults. We show that an N \Theta N two-dimensional array can sustain N 1\Gammaffl worst-case faults, for any fixed ffl...
The Reconfigurable Ring of Processors: Fine-Grain Tree-Structured Computations (1997)
Arnold L. Rosenberg, Vittorio Scarano, Ramesh K. Sitaraman
Abstract—We study fine-grain computation on the Reconfigurable Ring of Processors (553), a parallel architecture whose processing elements (PEs) are interconnected via a multiline reconfigurable...
Augmented ring networks (1997)
William Aiello, Eep N. Bhatt, Arnold L. Rosenberg, Ramesh K. Sitaraman
AbstractÐWe study four augmentations of ring networks which are intended to enhance a ring's efficiency as a communication medium significantly, while increasing its structural complexity only...
Augmented Ring Networks (1996)
William Aiello Sandeep, Sandeep N. Bhatt, Arnold L. Rosenberg, Ramesh K. Sitaraman
We study three augmentations of ring networks that are intended to decrease a ring's diameter significantly while increasing its structural complexity only modestly. Chordal rings enhance a ring...
Augmented Ring Networks (1996)
William Aiello, Sandeep N. Bhatt, Arnold L. Rosenberg, Ramesh K. Sitaraman
We study three augmentations of ring networks that are intended to decrease a ring's diameter significantly while increasing its structural complexity only modestly. Chordal rings enhance a ring...
On the Benefit of Supporting Virtual Channels in Wormhole Routers (1996)
Richard Cole, Bruce M. Maggs, Ramesh K. Sitaraman
This paper analyzes the impact of virtual channels on the performance of wormhole routing algorithms. We show that in any network in which each physical channel, i.e., communication link, can support...
Optimal Architecture-Independent Scheduling of Fine-Grain Tree-Sweep Computations (1995)
Lixin Gao Arnold, Arnold L. Rosenberg, Ramesh K. Sitaraman
. We present linear-time algorithms for optimally scheduling computations that comprise a sequence of complete up- and/or down-sweeps on a complete binary tree, on parallel architectures in which the...
Optimal Architecture-Independent Scheduling of Fine-Grain Tree-Sweep Computations (1995)
Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman
We present algorithms for optimally scheduling computations that comprise a sequence of complete up- and/or down-sweeps on a complete binary tree, on a parallel architecture in which the...
Ramesh K. Sitaraman, Niraj K. Jha, Senior Member
Abstract-Designing checks to detect or locate errors in the data plays an important role in the design of fault tolerant systems. Recently, the problem of synthesizing the data-check (DC)...
Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (1992)
). The analysis also applies to store-and-forward algorithms that drop packets if they attempt to enter full queues.
Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (1992)
Bruce Maggs, Ramesh K. Sitaraman
This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any greedy queuing protocol, a routing problem in which each of the N...
On the Fault Tolerance of Some Popular Bounded-Degree Networks (1992)
F. Thomson Leighton, Bruce M. Maggs, Ramesh K. Sitaraman
. In this paper, we analyze the fault tolerance of several bounded-degree networks that are commonly used for parallel computation. Among other things, we show that an N-node butterfly network...
Simple Algorithms for Routing on Butterfly Networks with Bounded Queues (1992)
Bruce M. Maggs, Ramesh K. Sitaraman
This paper examines several simple algorithms for routing packets on butterfly networks with bounded queues. We show that for any greedy queuing protocol, a routing problem in which each of the N...