Search For:

Displaying 1-50 out of 73 total
Bounded-Collision Memory-Mapping Schemes for Data Structures with Applications to Parallel Memories
Found in: IEEE Transactions on Parallel and Distributed Systems
By Gennaro Cordasco, Vittorio Scarano, Arnold L. Rosenberg
Issue Date:July 2007
pp. 973-982
<p><b>Abstract</b>—Techniques are developed for mapping structured data to an ensemble of parallel memory modules in a way that limits the number of <it>conflicts</it>, i.e., simultaneous accesses by distinct processors to the...
 
On Optimal Strategies for Cycle-Stealing in Networks of Workstations
Found in: IEEE Transactions on Computers
By Sandeep N. Bhatt, Fan R.K. Chung, F. Thomson Leighton, Arnold L. Rosenberg
Issue Date:May 1997
pp. 545-557
<p><b>Abstract</b>—We study the parallel scheduling problem for a new modality of parallel computing: having one workstation
 
On Scheduling Mesh-Structured Computations for Internet-Based Computing
Found in: IEEE Transactions on Computers
By Arnold L. Rosenberg
Issue Date:September 2004
pp. 1176-1186
Advances in technology have rendered the Internet a viable medium for employing multiple independent computers collaboratively in the solution of a single computational problem. A variety of mechanisms—e.g., Web-based computing, peer-to-peer computing, and...
 
Optimal Schedules for Cycle-Stealing in a Network of Workstations with a Bag-of-Tasks Workload
Found in: IEEE Transactions on Parallel and Distributed Systems
By Arnold L. Rosenberg
Issue Date:February 2002
pp. 179-191
<p><b>Abstract</b>—We refine the model underlying our prior work on scheduling bag-of-tasks (“embarrassingly parallel”) workloads via cycle-stealing in networks of workstations obtaining a model wherein the scheduling guidelines of produc...
 
The Reconfigurable Ring of Processors: Fine-Grain Tree-Structured Computations
Found in: IEEE Transactions on Computers
By Arnold L. Rosenberg, Vittorio Scarano, Ramesh K. Sitaraman
Issue Date:October 1997
pp. 1119-1131
<p><b>Abstract</b>—We study fine-grain computation on the Reconfigurable Ring of Processors <tmath>$({\cal RRP}),$</tmath> a parallel architecture whose processing elements (PEs) are interconnected via a multiline reconfigurab...
 
Limited random access turing machines
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Michael J. Fischer, Arnold L. Rosenberg
Issue Date:October 1968
pp. 356-367
The model of an online multitape Turing machine is generalized by adding a bounded number of repositioning operations to the shift repertoire. It is proved that any such limited random access Turing machine can be effectively replaced by an equivalent conv...
 
On n-type finite state acceptors
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Arnold L. Rosenberg
Issue Date:November 1964
pp. 76-81
Certain properties of three variants of the multi-tape automata of Rabin and Scott are proved. Closure properties of the defined sets of n-tuples are found, and the nature of projections of the defined sets of n-tuples on one coordinate is studied. Some ne...
 
Guidelines for Scheduling Some Common Computation-Dags for Internet-Based Computing
Found in: IEEE Transactions on Computers
By Arnold L. Rosenberg, Matthew Yurkewych
Issue Date:April 2005
pp. 428-438
A
 
On Bufferless Routing of Variable Length Messages in Leveled Networks
Found in: IEEE Transactions on Computers
By Sandeep N. Bhatt, Gianfranco Bilardi, Geppino Pucci, Abhiram Ranade, Arnold L. Rosenberg, Eric J. Schwabe
Issue Date:June 1996
pp. 714-729
<p><b>Abstract</b>—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, which we call <it&g...
 
Statistical predictors of computing power in heterogeneous clusters
Found in: Parallel and Distributed Processing Workshops and PhD Forum, 2011 IEEE International Symposium on
By Ron C. Chiang,Anthony A. Maciejewski,Arnold L. Rosenberg,Howard Jay Siegel
Issue Date:April 2010
pp. 1-9
If cluster C
 
Extending IC-Scheduling via the Sweep Algorithm
Found in: Parallel, Distributed, and Network-Based Processing, Euromicro Conference on
By Gennaro Cordasco, Grzegorz Malewicz, Arnold L. Rosenberg
Issue Date:February 2008
pp. 366-373
Earlier work has developed the rudiments of a scheduling theory for computations having intertask dependencies---modeled via dags---for Internet-based computing.??The goal of the schedules produced is to render tasks eligible for execution as fast as possi...
 
Using Emulations to Enhance the Performance of Parallel Architectures
Found in: IEEE Transactions on Parallel and Distributed Systems
By Bojana Obrenic, Martin C. Herbordt, Arnold L. Rosenberg, Charles C. Weems
Issue Date:October 1999
pp. 1067-1081
<p><b>Abstract</b>—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 algorithms that endow a...
 
Optimal Clustering of Tree-Sweep Computations for High-Latency Parallel Environments
Found in: IEEE Transactions on Parallel and Distributed Systems
By Lixin Gao, Arnold L. Rosenberg, Ramesh K. Sitaraman
Issue Date:August 1999
pp. 813-824
<p><b>Abstract</b>—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 clustering algorithms that aggregate...
 
Guidelines for Data-Parallel Cycle-Stealing in Networks of Workstations, II: On Maximizing Guaranteed Output
Found in: Parallel Processing Symposium, International
By Arnold L. Rosenberg
Issue Date:April 1999
pp. 520
We derive efficient guidelines for scheduling data-parallel computations within a draconian mode of cycle-stealing in networks of workstations wherein an interruption by the owner of the
 
Finite-State Robots in a Warehouse: Achieving Linear Parallel Speedup While Rearranging Objects
Found in: 2013 42nd International Conference on Parallel Processing (ICPP)
By Arnold L. Rosenberg
Issue Date:October 2013
pp. 379-388
We have teams of r identical mobile finite-state machines (FSMs, for short) act as robots that rearrange objects within a
 
On scheduling dags to maximize area
Found in: Parallel and Distributed Processing Symposium, International
By Gennaro Cordasco,Arnold L. Rosenberg
Issue Date:May 2009
pp. 1-12
A new quality metric, called area, is introduced for schedules that execute dags, i.e., computations having intertask dependencies. Motivated by the temporal unpredictability encountered when computing over the Internet, the goal under the new metric is to...
 
Path-robust multi-channel wireless networks
Found in: Parallel and Distributed Processing Symposium, International
By Arnold L. Rosenberg
Issue Date:May 2009
pp. 1-10
A mathematical-plus-conceptual framework is presented for studying problems such as the following. One wants to deploy an n-node multi-channel wireless network N in an environment that is inaccessible for repair and/or that contains malicious adversaries. ...
 
On Clustering Tasks in IC-Optimal Dags
Found in: Parallel Processing, International Conference on
By Mark Sims, Gennaro Cordasco, Arnold L. Rosenberg
Issue Date:September 2008
pp. 381-388
Strategies are developed for
 
Cellular ANTomata: Food-Finding and Maze-Threading
Found in: Parallel Processing, International Conference on
By Arnold L. Rosenberg
Issue Date:September 2008
pp. 528-535
A model for realizing ant-inspired algorithms that coordinate robots within a fixed, geographically constrained environment is proposed and illustrated.??The model, dubbed Cellular ANTomata, inverts the relationship between ant-robots and the environment t...
 
A Comparison of Dag-Scheduling Strategies for Internet-Based Computing
Found in: Parallel and Distributed Processing Symposium, International
By Robert Hall, Arnold L. Rosenberg, Arun Venkataramani
Issue Date:March 2007
pp. 55
A fundamental challenge in Internet computing (IC) is to efficiently schedule computations having complex interjob dependencies, given the unpredictability of remote machines, in availability and time of access. The recent IC Scheduling theory focuses on t...
 
Applying IC-Scheduling Theory to Familiar Classes of Computations
Found in: Parallel and Distributed Processing Symposium, International
By Gennaro Cordasco, Grzegorz Malewicz, Arnold L. Rosenberg
Issue Date:March 2007
pp. 483
Earlier work has developed the underpinnings of IC-Scheduling theory, an algorithmic framework for scheduling computations having intertask dependencies for Internet-based computing (IC). The Theory aims to produce schedules that render tasks eligible for ...
 
On Scheduling Expansive and Reductive Dags for Internet-Based Computing
Found in: Distributed Computing Systems, International Conference on
By Gennaro Cordasco, Grzegorz Malewicz, Arnold L. Rosenberg
Issue Date:July 2006
pp. 29
Earlier work has developed the underpinnings of a theory of scheduling computations having intertask dependencies - modeled via dags - for Internet-based computing. The goal of the schedules produced is to render tasks eligible for execution at the maximum...
 
Toward a Theory for Scheduling Dags in Internet-Based Computing
Found in: IEEE Transactions on Computers
By Grzegorz Malewicz, Arnold L. Rosenberg, Matthew Yurkewych
Issue Date:June 2006
pp. 757-768
Conceptual and algorithmic tools are developed as a foundation for a theory of scheduling complex computation-dags for Internet-based computing. The goal of the schedules produced is to render tasks eligible for allocation to remote clients (hence, for exe...
 
On Scheduling Complex Dags for Internet-Based Computing
Found in: Parallel and Distributed Processing Symposium, International
By Grzegorz Malewicz, Arnold L. Rosenberg, Matthew Yurkewych
Issue Date:April 2005
pp. 66
Conceptual tools are developed to aid in crafting a theory of scheduling complex computation-dags for Internetbased computing. The goal of the schedules produced is to render tasks eligible for allocation to remote clients (hence for execution) at the maxi...
 
Comparing the Structure of Power-Law Graphs and the Internet AS Graph
Found in: Network Protocols, IEEE International Conference on
By Sharad Jaiswal, Arnold L. Rosenberg, Don Towsley
Issue Date:October 2004
pp. 294-303
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 distribution of the AS graph. We are guided by the existing ...
 
How to Share a Bag of Tasks Optimally in a Heterogeneous Cluster - Three Models, Three Answers
Found in: Simulation Symposium, Annual
By Arnold L. Rosenberg
Issue Date:April 2004
pp. 3
No summary available.
   
An Algorithmic Model for Heterogeneous Clusters: Rationale and Experience
Found in: Parallel and Distributed Processing Symposium, International
By Arnold L. Rosenberg
Issue Date:April 2004
pp. 171b
By adding a computational component to the communication-oriented HiHCoHP model of [6], while specializing that model to a single heterogeneous cluster (HNOW, for short) built upon a single network, we obtain a model suitable for designing algorithms for a...
 
On Scheduling Collaborative Computations on the Internet, I: Mesh-Dags and Their Close Relatives
Found in: Parallel and Distributed Processing Symposium, International
By Arnold L. Rosenberg
Issue Date:April 2003
pp. 6a
Advancing technology has rendered the Internet a viable medium for collaborative computing, via mechanisms such as Web-Based Computing and Grid-Computing. We present a
 
Accountable Web-Computing
Found in: IEEE Transactions on Parallel and Distributed Systems
By Arnold L. Rosenberg
Issue Date:February 2003
pp. 97-106
<p><b>Abstract</b>—Web-Based Computing (WBC) is a modality of collaborative computing wherein “volunteers” register at a website, receiving one (usually compute-intensive) task to compute at each visit and returning the results from that ...
 
Using the Compiler to Improve Cache Replacement Decisions
Found in: Parallel Architectures and Compilation Techniques, International Conference on
By Zhenlin Wang, Kathryn S. McKinley, Arnold L. Rosenberg, Charles C. Weems
Issue Date:September 2002
pp. 199
Memory performance is increasingly determining microprocessor performance and technology trends are exacerbating this problem. Most architectures use set-associative caches with LRU replacement policies to combine fast access with relatively low miss rates...
 
Efficient Pairing Functions - And Why You Should Care
Found in: Parallel and Distributed Processing Symposium, International
By Arnold L. Rosenberg
Issue Date:April 2002
pp. 0144
This paper provides a short tour through the world of pairing functions -bijections between N ? N and N - as models for computational
 
Accountable Web-Computing
Found in: Parallel and Distributed Processing Symposium, International
By Arnold L. Rosenberg
Issue Date:April 2002
pp. 0074
We develop a computationally lightweight scheme for enhancing security when sharing a massive
 
Sharing Partitionable Workloads in Heterogeneous NOWs: Greedier Is Not Better
Found in: Cluster Computing, IEEE International Conference on
By Arnold L. Rosenberg
Issue Date:October 2001
pp. 124
We craft protocols for solving two problems related to sharing a large partitionable bag-of-tasks workload in a heterogeneous network of workstations (NOW) N. In the NOW-Rental Problem, one must complete W units of work and wishes to
 
Augmented Ring Networks
Found in: IEEE Transactions on Parallel and Distributed Systems
By William Aiello, Sandeep N. Bhatt, Fan R.K. Chung, Arnold L. Rosenberg, Ramesh K. Sitaraman
Issue Date:June 2001
pp. 598-609
<p><b>Abstract</b>—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 modestly. <it>Chordal rings&l...
 
HiHCoHP-Toward a Realistic Communication Model for Hierarchical HyperClusters of Heterogeneous Processors
Found in: Parallel and Distributed Processing Symposium, International
By Franck Cappello, Pierre Fraignaud, Bernard Mans, Arnold L. Rosenberg
Issue Date:April 2001
pp. 10042a
A parameterized model of hyperclusters of processors-clusters of clusters of . of clusters of processors-is formulated, under which a hypercluster enjoys generality along three orthogonal axes: (1) Its processors are heterogeneous: they may have different ...
 
Corrections to
Found in: IEEE Transactions on Computers
By Arnold L. Rosenberg, Vittorio Scarano, Ramesh K. Sitaraman
Issue Date:February 1998
pp. 269
No summary available.
 
An AREA-Oriented Heuristic for Scheduling Dags on Volatile Computing Platforms
Found in: IEEE Transactions on Parallel and Distributed Systems
By Gennaro Cordasco,Rosario De Chiara,Arnold L. Rosenberg
Issue Date:August 2014
pp. 1
Many modern computing platforms—notably clouds and desktop grids—exhibit dynamic heterogeneity: the availability and computing power of their constituent resources can change unexpectedly and dynamically, even in the midst of a computation. We introduce a ...
 
Planned Object Duplication Strategies in Dynamic PRR Meshes
Found in: Network Protocols, IEEE International Conference on
By Michael K. Bradshaw, Arnold L. Rosenberg, Don Towsley
Issue Date:November 2003
pp. 50
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 differences [11]. To this purpose we introduce a simple modeling fram...
 
Asymptotically Optimal Worksharing in HNOWs: How Long is
Found in: Simulation Symposium, Annual
By Micah Adler, Ying Gong, Arnold L. Rosenberg
Issue Date:April 2003
pp. 39
We proved in [1] that
 
Real time counter machines
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Patrick C. Fischer, Albert R. Meyer, Arnold L. Rosenberg
Issue Date:October 1967
pp. 148-154
An automaton called the balloon automaton is defined. The balloon automaton comes in four varieties, depending on whether the device is deterministic or nondeterministic, and whether the input head can move in one or two directions. Subsets of the balloon ...
 
Turing machines with several read-write heads
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Albert R. Meyer, Arnold L. Rosenberg, Patrick C. Fischer
Issue Date:October 1967
pp. 117-127
This paper describes some general results about hierarchies of undecidable problems in automata theory, and studies how properties of sets accepted by automata change from decidable to undecidable problems as the memory capacity of the automaton is increas...
 
On multi-head finite automata
Found in: Foundations of Computer Science, Annual IEEE Symposium on
By Arnold L. Rosenberg
Issue Date:October 1965
pp. 221-228
Let mn be the class of languages defined by n-head finite automata. The Boolean and Kleene closure properties of mn are investigated, and a relationship between mn and the class sets of n-tuples of tapes defined by n-tape finite automata is established. Th...
 
On the cost-ineffectiveness of redundancy in commercial P2P computing
Found in: Proceedings of the 12th ACM conference on Computer and communications security (CCS '05)
By Arnold L. Rosenberg, Brian N. Levine, Matthew Yurkewych
Issue Date:November 2005
pp. 280-288
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 the cost of implementing redundant task allocation (redun...
     
Optimal sharing of bags of tasks in heterogeneous clusters
Found in: Proceedings of the fifteenth annual ACM symposium on Parallel algorithms and architectures (SPAA '03)
By Arnold L. Rosenberg, Micah Adler, Ying Gong
Issue Date:June 2003
pp. 1-10
We prove that "FIFO" worksharing protocols provide asymptotically optimal solutions to a problem related to sharing a bag of identically complex tasks in a heterogeneous network of workstations (HNOW) n. In the HNOW-Exploitation Problem, one seeks to accom...
     
Optimal schedules for data-parallel cycle-stealing in networks of workstations (extended abstract)
Found in: Proceedings of the twelfth annual ACM symposium on Parallel algorithms and architectures (SPAA '00)
By Arnold L. Rosenberg
Issue Date:July 2000
pp. 22-29
We refine the model underlying our prior work on scheduling cycle-stealing opportunities in NOWs [5, 16], obtaining a model wherein the scheduling guidelines of [16] produce optimal schedules for every such opportunity. Although computing optimal schedules...
     
Scheduling time-constrained communication in linear networks
Found in: Proceedings of the tenth annual ACM symposium on Parallel algorithms and architectures (SPAA '98)
By Arnold L. Rosenberg, Micah Adler, Ramesh K. Sitaraman, Walter Unger
Issue Date:June 1998
pp. 269-278
We consider the problem of sorting a file of N records on theD-disk model of parallel I/0 [VS94] in which there are two sourcesof parallehsm. Records are transferred to and from diskconcurrently in blocks of B con-tiguous records. In each I/Ooperation, up ...
     
A tight layout of the butterfly network
Found in: Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures (SPAA '96)
By Ami Litman, Arnold L. Rosenberg, Aythan Avior, Shimon Even, Tiziana Calamoneri
Issue Date:June 1996
pp. 170-175
We consider the problem of sorting a file of N records on theD-disk model of parallel I/0 [VS94] in which there are two sourcesof parallehsm. Records are transferred to and from diskconcurrently in blocks of B con-tiguous records. In each I/Ooperation, up ...
     
On trading task reallocation for thread management in partitionable multiprocessors
Found in: Proceedings of the eighth annual ACM symposium on Parallel algorithms and architectures (SPAA '96)
By Arnold L. Rosenberg, Lixin Gao, Ramesh K. Sitaraman
Issue Date:June 1996
pp. 309-317
We consider the problem of sorting a file of N records on theD-disk model of parallel I/0 [VS94] in which there are two sourcesof parallehsm. Records are transferred to and from diskconcurrently in blocks of B con-tiguous records. In each I/Ooperation, up ...
     
Thoughts on parallelism and concurrency in compiling curricula
Found in: ACM Computing Surveys (CSUR)
By Arnold L. Rosenberg
Issue Date:March 1988
pp. 280-283
A multidatabase system (MDBS) is a confederation of preexisting distributed, heterogeneous, and autonomous database systems. There has been a recent proliferation of research suggesting the application of object-oriented techniques to facilitate the comple...
     
The physical mapping problem for parallel architectures
Found in: Journal of the ACM (JACM)
By Arnold L. Rosenberg, Bruce T. Smith, Lenwood S. Heath
Issue Date:January 1988
pp. 603-634
The problem of realizing an idealized parallel architecture on a (possibly fault-laden) physical architecture is studied. Our formulation performs the mapping in the light of the algorithm that one wants to implement on the idealized architecture. A versio...
     
 1  2 Next >>