Scheduling Tree-Dags Using FIFO Queues: A (2008)
Control-memory Tradeo, Sandeep N. Bhatt, F. Thomson Leighton, Arnold L. Rosenberg
Abstract. We study here a combinatorial problem that is motivated by a genre of architecture-independent scheduler for parallel computations. Such schedulers are often used, for instance, when...
Sandeep N. Bhatt, New Brunswick, F. Thomson Leighton, Arnold L. Rosenberg
1 Abstract. We study aspects of the parallel scheduling problem for a new modality of parallel computing: having one workstation “steal cycles ” from another. We focus on a draconian mode of...
Using Emulations to Enhance the Performance of Parallel Architectures (2008)
Bojana Obrenic, Martin C. Herbordt, Arnold L. Rosenberg, Charles C. Weems, Senior Member
AbstractÐWe illustrate the potential of techniques and results from the theory of network emulations to enhance the performance of a parallel architecture. The vehicle for this demonstration is a...
c-Perfect Hashing Schemes for Arrays, with Applications to Parallel Memories (2008)
Gennaro Cordasco, Alberto Negro, Vittorio Scarano, Arnold L. Rosenberg
We study the problem of mapping array-structured data to an ensemble of parallel mem-ory modules, by allowing at most c conflicts (i.e. simultaneous access by up to c processors to the same memory...
Jia-wei Hong, Arnold L. Rosenberg
Abstract. An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H. There are two natural measures of the cost of a graph embedding, namely,...
EFFICIENT EMBEDDINGS OF TREES IN HYPERCUBES* (2008)
Sandeep N. Bhattt, F. Thomson Leighton, Arnold L. Rosenberg
Abstract. The boolean hypercube is a particularly versatile network for parallel computing. It is well known that multidimensional grid machines can be simulated on a hypercube with no communications...
Sharing Bags of Tasks Optimally in Heterogeneous Clusters (2008)
Micah Adler, Ying Gong, Arnold L. Rosenberg, Micah Adler, Ying Gong, Arnold L. Rosenberg
Sandeep N. Bhatt, Gianfranco Bilardi, Abhiram Ranade, Arnold L. Rosenberg, Eric J. Schwabe
Illinois We study the most general communication paradigm on a multiprocessor, wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this...
Authors ' Mailing Addresses (2007)
Sandeep N. Bhatt, Sandeep N. Bhatt, Abhiram Ranade, Abhiram Ranade, Arnold L. Rosenberg, Arnold L. Rosenberg, ...
2
Sandeep N. Bhatt, Gianfranco Bilardi, Abhiram Ranade, Arnold L. Rosenberg, Eric J. Schwabe
We study the most general communication paradigm on a multiprocessor, wherein each processor has a distinct message (of possibly distinct lengths) for each other processor. We study this paradigm,...
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...
Authors ' Mailing Addresses (2007)
Sandeep N. Bhatt, Sandeep N. Bhatt, Abhiram Ranade, Abhiram Ranade, Arnold L. Rosenberg, Arnold L. Rosenberg, ...
2
Sandeep N. Bhatt, F. Thomson Leighton, Arnold L. Rosenberg
Abstract. We study a combinatorial problem that is motivated by "client-server " schedulers for parallel computations. Such schedulers are often used, for instance, when...
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...
2000): Optimal sharing of partitionable workloads in heterogeneous networks of workstations (2007)
Abstract Two problems related to worksharing in a heterogeneous network of workstations (NOW) are formalized and solved optimally. In both problems, one has access to a NOW comprising n workstations...
Planned Object Duplication Strategies in Dynamic PRR Meshes (2007)
Michael K. Bradshaw, Arnold L. Rosenberg, Don Towsley
In recent years there has been considerable research on new Distributed Hash Tables (DHTs), improvements on existing DHTs, and DHT-enabled systems. However, little of it focuses on their...
Efficient trigger-broadcasting in heterogeneous clusters (2005)
Fraigniaud, Pierre, Mans, Bernard, Rosenberg, Arnold L
Broadcasts in parallel computing environments are often used to trigger “personal” computations at the processors (or, nodes) that comprise the system. (The qualifier “personal” means that...
Efficient trigger-broadcasting in heterogeneous clusters (2005)
Fraigniaud, Pierre, Mans, Bernard, Rosenberg, Arnold L
Broadcasts in parallel computing environments are often used to trigger “personal” computations at the processors (or, nodes) that comprise the system. (The qualifier “personal” means that...
On the costineffectiveness of redundancy in commercial P2P computing (2005)
Matthew Yurkewych, Brian N. Levine, Arnold L. Rosenberg
We present a game-theoretic model of the interactions between server and clients in a constrained family of commercial P2P computations (where clients are financially compensated for work). We study...
Comparing the Structure of Power-Law Graphs and the Internet AS graph (2004)
Sharad Jaiswal, Arnold L. Rosenberg, Don Towsley
In this work we devise algorithmic techniques to compare the interconnection structure of the Internet AS Graph with that of graphs produced by topology generators that match the power-law degree...
Using the Compiler to Improve Cache Replacement Decisions (2002)
Zhenlin Wang, Kathryn S. McKinley, Arnold L. Rosenberg, Charles C. Weems
Memory performance is increasingly determining microprocessor performance and technology trends are exacerbating this problem. Most architectures use set-associative caches with LRU replacement...
Using the Compiler to Improve Cache Replacement Decisions (2002)
Zhenlin Wang, Kathryn S. Mckinley, Arnold L. Rosenberg, Charles C. Weems
Memory performance is increasingly determining microprocessor performance and technology trends are exacerbating this problem. Most architectures use set-associative caches with LRU replacement...
We derive efficient guidelines for scheduling dataparallel computations within a draconian mode of cyclestealing in networks of workstations wherein an interruption by the owner of the “borrowed...
Using Emulations to Enhance the Performance of Parallel Architectures (1999)
Bojana Obreni Martin, Martin C. Herbordt, Arnold L. Rosenberg, Charles C. Weems, Senior Member
We illustrate the potential of techniques and results from the theory of network emulations to enhance the performance of a parallel architecture. The vehicle for this demonstration is a suite of...
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...
Optimal Simulations by Butterfly Networks. (1998)
Bhatt, Sandeep N., Chung, Fan R., Hong, Jia-Wei, Leighton, F. T., Rosenberg, Arnold L.
The power of Butterfly-type networks relative to other proposed multicomputer interconnection networks is studied, by considering how efficiently the Butterfly can simulate the other networks....
Guidelines for Data-Parallel Cycle-Stealing in Networks of Workstations (Extended Abstract) (1998)
) Arnold L. Rosenberg # Department of Computer Science University of Massachusetts Amherst, MA 01003 rsnbrg@cs.umass.edu Abstract We derive guidelines for nearly optimally scheduling data-parallel...
Scheduling Time-Constrained Communication in Linear Networks (1998)
Micah Adler, Arnold L. Rosenberg, Ramesh K. Siraraman, Walter Unger
We study the problem of centrally scheduling multiple messages in a linear network, when each message has both a release time and a deadline. We show that the problem of transmitting optimally many...
Theoretical Research on Networks: Models and Methodology (1997)
This note is based on my invited talk at the 4th Intl. Colloq. on Structural Information and Communication Complexity (SIROCCO'97). In it, I discuss a few "meta-issues" concerning...
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...
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...
DIMACS Workshop on Interconnection Networks and Mapping, and Scheduling Parallel Computations (1996)
Hsu Derbiau Frank, Rosenberg, Arnold L, Sotteau, Dominique
The interconnection network is one of the most basic components of a massively parallel computer system. Such systems consist of hundreds or thousands of processors interconnected to work...
An empirical study of dynamic scheduling on rings of processors (1996)
Dawn E. Gregory, Lixin Gao, Arnold L. Rosenberg, Paul R. Cohen
We empirically analyze and compare two distributed, low-overhead policies for scheduling dynamic treestructured computations on rings of identical PEs. Our experiments show that both policies give...
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...
An Empirical Study of Dynamic Scheduling on Rings of Processors (Extended Abstract) (1996)
Dawn E. Gregory, Lixin Gao, Arnold L. Rosenberg, Paul R. Cohen
Dawn E. Gregory Lixin Gao Arnold L. Rosenberg Paul R. Cohen Department of Computer Science, University of Massachusetts Amherst, MA 01003, USA Abstract We empirically analyze and compare two...
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...
Toward Efficient Scheduling of Evolving Computations on Rings of Processors (1996)
Li-Xin Gao, Arnold L. Rosenberg
. We study a simple, low-overhead policy for scheduling dynamically evolving computations in which tasks that spawn produce precisely two offspring, on rings of processors. Such computations include,...
Optimal Emulations by Butterfly-Like Networks (1996)
Sandeep N. Bhatt, Jia-wei Hong, F. Thomson Leighton, Arnold L. Rosenberg, Eric J. Schwabe, ...
The power of butterfly-like networks as multicomputer interconnection networks is studied, by considering how efficiently the butterfly can emulate other networks. Emulations are studied formally via...
Scheduling Tree-Dags Using FIFO Queues: A Control-Memory Tradeoff (1996)
Sandeep N. Bhatt, F. Thomson Leighton, Arnold L. Rosenberg
. We study here a combinatorial problem that is motivated by a genre of architecture-independent scheduler for parallel computations. Such schedulers are often used, for instance, when computations...
On Optimal Strategies for Stealing Cycles (1995)
Sandeep N. Bhatt, New Brunswick, F. Thomson Leighton, Arnold L. Rosenberg
. The growing importance of networked workstations as a computing milieu has created a new modality of parallel computing, namely, the possibility of having one workstation "steal cycles"...
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...
Monochromatic Paths and Triangulated Graphs (1995)
Shimon Even, Ami Litman, Arnold L. Rosenberg
This paper considers two properties of graphs, one geometrical and one topological, and shows that they are strongly related. Let G be a graph with four distinguished and distinct vertices, w 1 ; w 2...
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...
Salvage-embeddings of complete trees (1995)
Sandeep N. Bhatt, F. Thomson Leighton, Arnold L. Rosenberg
Abstract. A salvage-embedding (S-embedding) maps a complete binary tree G into a larger complete binary tree H some fraction of whose leaves have been labeled good. The S-embedding maps leaves of G...
On Balancing Computational Load on Rings of Processors (1994)
Lixin Gao, Arnold L. Rosenberg
. We consider a very simple, deterministic policy for scheduling certain genres of dynamically evolving computations --- specifically, computations in which tasks that spawn produce precisely two...
We study the presence of cycles and long paths in graphs that have been proposed as interconnection networks for parallel architectures. The study surveys and complements known results. 1...
Work-Preserving Emulations of Fixed-Connection Networks (1989)
Richard R. Koch, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Arnold L. Rosenberg, Eric J. Schwabe
In this paper, we study the problem of emulating TG steps of an NG -node guest network, G, on an NH -node host network, H. We call an emulation work-preserving if the time required by the host, TH ,...
Work-Preserving Emulations of Fixed-Connection Networks (1989)
Richard R. Koch, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Arnold L. Rosenberg, Eric J. Schwabe
ing with credit is permitted. To copy otherwise, to republish, to post on servers, to redistribute to lists, or to use any component of this work in other works, requires prior specific permission...
Work-preserving emulations of fixed-connection networks (1989)
Richard R. Koch, F. T. Leighton, Bruce M. Maggs, Satish B. Rao, Arnold L. Rosenberg, Eric J. Schwabe
Abstract. In this paper, we study the problem of emulating T G steps of an N G-node guest network, G, on an N H-node host network, H. We call an emulation work-preserving if the time required by the...
Embedding graphs in books: a layout problem with applications to VLSI design (1987)
Frank Thomson, Arnold L. Rosenberg
Abstract. We study the graph-theoretic problem of embedding a graph in a book with its vertices in a line along the spine of the book and its edges on the pages in such a way that edges residing on...
Cost Trade-offs in Graph Embeddings, with Applications (1983)
Hong, Jia-Wei, Mehlhorn, Kurt, Rosenberg, Arnold L.
An embedding of the graph G in the graph H is a one-to-one association of the vertices of G with the vertices of H. There are two natural measures of the cost of a graph embedding, namely, the...