Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Computer programming (2)
- Computer science education (2)
- Data analysis (2)
- Parallel computation (2)
- Robotics (2)
-
- Appropriate cost (1)
- Area-universal networks (1)
- Area-universality (1)
- Butterfly fat-tree (1)
- Communication capability (1)
- Computer science (1)
- Computing (1)
- Educational robotics (1)
- Empirical comparison (1)
- Fat pyramid (1)
- Fat-pyramid (1)
- Fat-tree (1)
- Gener-purpose parallel computing (1)
- Hypercube (1)
- Interconnection network (1)
- Latency (1)
- Mesh (1)
- Message routing algorithms (1)
- Network (1)
- Performance evaluation (1)
- Queueing theory (1)
- Routing strategy (1)
- Shortest paths (1)
- Throughput (1)
- Wormhole routing (1)
Articles 1 - 9 of 9
Full-Text Articles in Computer Engineering
The Fat-Pyramid: A Robust Network For Parallel Computation, Ronald I. Greenberg
The Fat-Pyramid: A Robust Network For Parallel Computation, Ronald I. Greenberg
Ronald Greenberg
This paper shows that a fat-pyramid of area Theta(A) built from processors of size lg A requires only O(lg^2 A) slowdown in bit-times to simulate any network of area A under very general conditions. Specifically, there is no restriction on processor size (amount of attached memory) or number of processors in the competing network, nor is the assumption of unit wire delay required. This paper also derives upper bounds on the slowdown required by a fat-pyramid to simulate a network of larger area in the case of unit wire delay.
Pythagorean Combinations For Lego Robot Building., Ronald I. Greenberg
Pythagorean Combinations For Lego Robot Building., Ronald I. Greenberg
Ronald Greenberg
This paper provides tips for LEGO robot construction involving bracing or gear meshing along a diagonal using standard Botball kits.
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Ronald Greenberg
Fat-trees are a class of routing networks for hardware-efficient parallel computation. This paper presents a randomized algorithm for routing messages on a fat-tree. The quality of the algorithm is measured in terms of the load factor of a set of messages to be routed, which is a lower bound on the time required to deliver the messages. We show that if a set of messages has load factor lambda on a fat-tree with n processors, the number of delivery cycles (routing attempts) that the algorithm requires is O(lambda+lgnlglgn) with probability 1-O(1/ …
Pythagorean Approximations For Lego: Merging Educational Robot Construction With Programming And Data Analysis, Ronald I. Greenberg
Pythagorean Approximations For Lego: Merging Educational Robot Construction With Programming And Data Analysis, Ronald I. Greenberg
Ronald Greenberg
Abstract. This paper can be used in two ways. It can provide reference information for incorporating diagonal elements (for bracing or gear meshing) in educational robots built from standard LEGO kits. Alternatively, it can be used as the basis for an assignment for high school or college students to recreate this information; in the process, students will exercise skills in both computer programming and data analysis. Using the paper in the second way can be an excellent integrative experience to add to an existing course; for example, the Exploring Computer Science high school curriculum concludes with the units “Introduction to …
Motion Planning For Simple Two-Wheeled Robots, Ronald I. Greenberg, Jeffery M. Karp
Motion Planning For Simple Two-Wheeled Robots, Ronald I. Greenberg, Jeffery M. Karp
Ronald Greenberg
This paper considers various simple ways of navigating in a 2-dimensianal territory with a two-wheeled robot of a type typical in educational robotics. We determine shortest paths under various modes of operation and compare.
An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan
An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan
Ronald Greenberg
This paper provides empirical comparison of the communication capabilities of two area-universal networks, the fat-tree and the fat-pyramid, to the popular mesh and hypercube networks for parallel computation. While area-universal networks have been proven capable of simulating, with modest slowdown, any computation of any other network of comparable area, prior work has generally left open the question of how area-universal networks compare to other networks in practice. Comparisons are performed using techniques of throughput and latency analysis that have previously been applied to k-ary n-cube networks and using various existing models to equate the hardware cost of the networks being …
An Improved Analytical Model For Wormhole Routed Networks With Application To Butterfly Fat-Trees, Ronald I. Greenberg, Lee Guan
An Improved Analytical Model For Wormhole Routed Networks With Application To Butterfly Fat-Trees, Ronald I. Greenberg, Lee Guan
Ronald Greenberg
A performance model for wormhole routed interconnection networks is presented and applied to the butterfly fat-tree network. Experimental results agree very closely over a wide range of load rate. Novel aspects of the model, leading to accurate and simple performance predictions, include (1) use of multiple-server queues, and (2) a general method of correcting queuing results based on Poisson arrivals to apply to wormhole routing. These ideas can also be applied to other networks.
An Empirical Comparison Of Networks And Routing Strategies For Parallel Computation, Ronald I. Greenberg, Lee Guan
An Empirical Comparison Of Networks And Routing Strategies For Parallel Computation, Ronald I. Greenberg, Lee Guan
Ronald Greenberg
This paper compares message routing capabilities of important networks proposed for general-purpose parallel computing. All the networks have been proven to have some type of universality property, i.e., an ability to simulate other networks of comparable cost with modest slowdown, using appropriate cost and communication models. But in this paper we seek an empirical comparison of communication capability under typical direct use rather than an analysis of worst-case results for simulating message traffic of another network.
A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh
A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh
Ronald Greenberg
This paper presents a CAD tool, SystSim, to ease the design of systolic systems. Given a high-level, functional description of processors, and a high-level description of their interconnection, SystSim will perform simulations and provide graphical output. SystSim will also perform transformations such as retiming, which eases use of the methodology of Leiserson and Saxe of designing a system with broadcasting and then obtaining a systolic system through retiming.