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

Physical Sciences and Mathematics Commons™

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

2018

Ronald Greenberg

Discipline
Keyword
File Type

Articles 1 - 30 of 46

Full-Text Articles in Physical Sciences and Mathematics

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson Jan 2018

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

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 + lg n lg lg n) with probability 1-O(1/n). The best previous …

Go to article

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh Jan 2018

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Ronald Greenberg

We examine the wormhole routing problem in terms of the "congestion" c and "dilation" d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη + cLηlog P) time, where L is the number of flits in a packet, and η = min {d,L]; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log 3 …

Go to article

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.

Go to article

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg Jan 2018

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

Ronald Greenberg

This paper shows that a fat-pyramid of area Θ(A) requires only O(log A) slowdown to simulate any competing network of area A under very general conditions. The result holds regardless of the processor size (amount of attached memory) and number of processors in the competing networks as long as the limitation on total area is met. Furthermore, the result is valid regardless of the relationship between wire length and wire delay. We especially focus on elimination of the common simplifying assumption that unit time suffices to traverse a wire regardless of its length, since the assumption becomes more and more …

Go to article

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.

Go to article

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/ …

Go to article

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh Jan 2018

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Ronald Greenberg

In this paper, we examine the wormhole routing problem in terms of the “congestion” c and “dilation” d for a set of packet paths. We show, with mild restrictions, that there is a simple randomized algorithm for routing any set of P packets in O(cdη+cLηlogP) time with high probability, where L is the number of flits in a packet, and η=min{d,L}; only a constant number of flits are stored in each queue at any time. Using this result, we show that a fat-tree network of area Θ(A) can simulate wormhole routing on any network of comparable area with O(log^3 A) …

Go to article

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

This paper considers the optimal offset, feasible offset, and optimal placement problems for a more general form of single-layer VLSI channel routing than has usually been considered in the past. Most prior works require that every net has exactly one terminal on each side of the channel. As long as only one side of the channel contains multiple terminals of the same net, we provide linear-time solutions to all three problems. Such results are implausible if the placement of terminals is entirely unrestricted; in fact, the size of the output for the feasible offset problem may be Ω(n^2). The linear-time …

Go to article

Some Applications Of Sophisticated Mathematics To Randomized Computing, Ronald I. Greenberg Jan 2018

Some Applications Of Sophisticated Mathematics To Randomized Computing, Ronald I. Greenberg

Ronald Greenberg

No abstract provided.

Go to article

The Impact Of Meaningful High School Computer Science Experiences In The Chicago Public Schools, Ronald I. Greenberg Jan 2018

The Impact Of Meaningful High School Computer Science Experiences In The Chicago Public Schools, Ronald I. Greenberg

Ronald Greenberg

We report on initial outcomes of the Taste of Computing project, under which a meaningful computer science course has been initiated in many high schools of the Chicago Public Schools system. Surveys of students have shown that they attribute high value to the course and have experienced increases in their understanding and interest regarding the computing field. Data was also collected from teachers participating in professional development regarding their preparation and confidence in teaching the new course. We report on the strengths of various survey responses and their relationships, and we compare student responses by race and gender. The data …

Go to article

Tools For Outreach Presentations, Ronald I. Greenberg, Dale Reed Jan 2018

Tools For Outreach Presentations, Ronald I. Greenberg, Dale Reed

Ronald Greenberg

We present resources we have constructed and culled from the internet that can be used in computing outreach visits in K–12 classrooms, especially high schools. We have used such tools at about 100 schools, reaching several thousand students, and achieving positive attitudinal responses in surveys of several hundred of these students.

Go to article

The Impact Of The Exploring Computer Science Instructional Model In Chicago Public Schools, Ronald I. Greenberg Jan 2018

The Impact Of The Exploring Computer Science Instructional Model In Chicago Public Schools, Ronald I. Greenberg

Ronald Greenberg

As part of the Taste of Computing project, the Exploring Computer Science (ECS) instructional model has been expanded to many high schools in the Chicago Public Schools system. We report on initial outcomes showing that students value the ECS course experience, resulting in increased awareness of and interest in the field of computer science. We compare these results by race and gender. The data provide a good basis for exploring the impact of meaningful computer science instruction on students from groups underrepresented in computing; of several hundred students surveyed, nearly half were female, and over half were Hispanic or African-American.

Go to article

Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle Jan 2018

Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle

Ronald Greenberg

In a target detection communication system, apparatus and method for determining the presence of probable targets based on contacts (which can indicate the presence of a target, noise, chatter, or objects not of interest) detected within a predefined position sector or sectors over a specified number of scans. The position of each detected contact, as a contact of interest, is compared with the positions of contacts detected at previous times or scans. Velocity profiles indicate which previous contacts support the likelihood that the contact of interest represents a target having a velocity within a defined band. The likelihood, which can …

Go to article

Open Source Classroom Polling (Interactive Response) Facility, Ronald I. Greenberg Jan 2018

Open Source Classroom Polling (Interactive Response) Facility, Ronald I. Greenberg

Ronald Greenberg

The contents of the UNIX directory resulting from unzipping the .zip file provide a demonstration of a simple polling facililty that instructors can use in class any time that students have access to a web browser. This is a good way to have students work problems and see to what extent they are converging towards correct answers. Unlike other polling facilities, this one is completely free without any restrictions on number of simultaneous users, etc. It also allows a feature most polling facilities do not in that it may be used for completely free-form answers, and the instructor can still …

Go to article

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy Jan 2018

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Ronald Greenberg

We show that channel routing in the Manhattan model remains difficult even when all nets are single-sided. Given a set of n single-sided nets, we consider the problem of determining the minimum number of tracks required to obtain a dogleg-free routing. In addition to showing that the decision version of the problem isNP-complete, we show that there are problems requiring at least d+Omega(sqrt(n)) tracks, where d is the density. This existential lower bound does not follow from any of the known lower bounds in the literature.

Go to article

On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan Jan 2018

On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan

Ronald Greenberg

This paper precisely analyzes the wire density and required area in standard styles for the hypercube. It shows that the most natural, regular layout of a hypercube of N^2 nodes in the plane, in a NxN grid arrangement, uses floor(2N/3)+1 horizontal wiring tracks for each row of nodes. (In the process, we see that the number of tracks per row can be reduced by 1 with a less regular design, as can also be seen from an independent argument of Bezrukov et al.) This paper also gives a simple formula for the wire density at any cut position and a …

Go to article

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley Jan 2018

Minimum Separation For Single-Layer Channel Routing, Ronald I. Greenberg, F. Miller Maley

Ronald Greenberg

We present a linear-time algorithm for determining the minimum height of a single-layer routing channel. The algorithm handles single-sided connections and multiterminal nets. It yields a simple routability test for single-layer switchboxes, correcting an error in the literature.

Go to article

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 …

Go to article

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli Jan 2018

Mulch: A Multi-Layer Channel Router Using One, Two, And Three Layer Partitions, Ronald I. Greenberg, Alex T. Ishii, Alberto L. Sangiovanni-Vincentelli

Ronald Greenberg

Chameleon, a channel router for three layers of interconnect, has been implemented to accept specification of an arbitrary number of layers. Chameleon is based on a strategy of decomposing the multilayer problem into two- and three-layer problems in which one of the layers is reserved primarily for vertical wire runs and the other layer(s) for horizontal runs. In some situations, however, it is advantageous to consider also layers that allow the routing of entire nets, using both horizontal and vertical wires. MulCh is a multilayer channel router that extends the algorithms of Chameleon in this direction. MulCh can route channels …

Go to article

My Materials Supporting The Exploring Computer Science Curriculum, Ronald I. Greenberg Jan 2018

My Materials Supporting The Exploring Computer Science Curriculum, Ronald I. Greenberg

Ronald Greenberg

Ready-made handouts and other resources supporting the Exploring Computer Science (introductory high school) curriculum are provided for Units 1 through 3. These materials were based on version 4 of the ECS curriculum but should remain relevant in later versions as well.

Go to article

Motion Planning For Educational Robots, Ronald I. Greenberg, Jeffery M. Karp Jan 2018

Motion Planning For Educational Robots, Ronald I. Greenberg, Jeffery M. Karp

Ronald Greenberg

This paper considers various simple ways of navigating in a 2-dimensional territory with a two-wheeled robot of a type typical in educational robotics. We determine shortest paths under various modes of operation and compare.

Go to article

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We give algorithms to minimize density for channels with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, previous results for running time and space are improved by a factor of L/lg n and L , respectively, where L is the channel length and n is the number of terminals.

Go to article

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

We give algorithms to minimize density for VLSI channel routing problems with terminals that are movable subject to certain constraints. The main cases considered are channels with linear order constraints, channels with linear order constraints and separation constraints, channels with movable modules containing fixed terminals, and channels with movable modules and terminals. In each case, we improve previous results for running time and space by a factor of L/\lgn and L, respectively, where L is the channel length, and n is the number of terminals.

Go to article

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih Jan 2018

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Ronald Greenberg

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that have linear-time sequential solutions rather than limiting attention to the ``river-routing'' context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN/lglgN) time on a CRCW PRAM, both with optimal work (processor-time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor bounds as long as only one side of …

Go to article

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih Jan 2018

Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih

Ronald Greenberg

We provide efficient parallel algorithms for the minimum separation, offset range, and optimal offset problems for single-layer channel routing. We consider all the variations of these problems that are known to have linear- time sequential solutions rather than limiting attention to the "river-routing" context, where single-sided connections are disallowed. For the minimum separation problem, we obtain O(lgN) time on a CREW PRAM or O(lgN / lglgN) time on a (common) CRCW PRAM, both with optimal work (processor- time product) of O(N), where N is the number of terminals. For the offset range problem, we obtain the same time and processor …

Go to article

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh Jan 2018

Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh

Ronald Greenberg

In this paper, we examine the packet routing problem for networks with wires of differing length. We consider this problem in a network independent context, in which routing time is expressed in terms of "congestion" and "dilation" measures for a set of packet paths. We give, for any constant ϵ > 0, a randomized on-line algorithm for routing any set of Npackets in O((C lgϵ(Nd) + D lg(Nd))/lg lg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into …

Go to article

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.

Go to article

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg Jan 2018

Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg

Ronald Greenberg

This paper provides a new approach to labeling the connected components of an n x n image on a scan line array processor (comprised of n processing elements). Variations of this approach yield an algorithm guaranteed to complete in o(n lg n) time as well as algorithms likely to approach O(n) time for all or most images. The best previous solutions require using a more complicated architecture or require Omega(n lg n) time. We also show that on a restricted version of the architecture, any algorithm requires Omega(n lg n) time in the worst case.

Go to article

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih Jan 2018

Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

The paper provides an efficient method to find all feasible offsets for a given separation in a VLSI channel routing problem in one layer. The prior literature considers this task only for problems with no single-sided nets. When single-sided nets are included, the worst-case solution time increases from Theta(n) to Omega(n^2), where n is the number of nets. But, if the number of columns c is O(n), one can solve the problem in time O(n^{1.5}lg n ), which improves upon a `naive' O(cn) approach. As a corollary of this result, the same time bound suffices to find the optimal offset …

Go to article

Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg Jan 2018

Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg

Ronald Greenberg

This paper considers several variations of an optimization problem with potential applications in such areas as biomolecular sequence analysis and image processing. Given a sequence of items, each with a weight and a length, the goal is to find a subsequence of consecutive items of optimal value, where value is either total weight or total weight divided by total length. There may also be a specified lower and/or upper bound on the acceptable length of subsequences. This paper shows that all the variations of the problem are solvable in linear time and space even with non-uniform item lengths and divisible …

Go to article

Next Last