Open Access. Powered by Scholars. Published by Universities.®

Computer Engineering Commons

Open Access. Powered by Scholars. Published by Universities.®

Articles 1 - 9 of 9

Full-Text Articles in Computer Engineering

The Fat-Pyramid: A Robust Network For Parallel Computation, Ronald I. Greenberg Jan 2018

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 Jan 2018

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 Jan 2018

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/n). The ...


Pythagorean Approximations For Lego: Merging Educational Robot Construction With Programming And Data Analysis, Ronald I. Greenberg Jan 2018

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 Jan 2018

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 Jan 2018

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 Jan 2018

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 Jan 2018

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 Jan 2018

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.