Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Discipline
-
- Engineering (27)
- Theory and Algorithms (22)
- Electrical and Computer Engineering (21)
- VLSI and Circuits, Embedded and Hardware Systems (20)
- Computer Engineering (9)
-
- Education (8)
- Science and Mathematics Education (7)
- Computer and Systems Architecture (6)
- Mathematics (5)
- Secondary Education (5)
- Curriculum and Instruction (4)
- OS and Networks (4)
- Robotics (3)
- Teacher Education and Professional Development (3)
- Applied Mathematics (2)
- Discrete Mathematics and Combinatorics (2)
- Geometry and Topology (2)
- Other Computer Sciences (2)
- Probability (2)
- Statistics and Probability (2)
- Bioinformatics (1)
- Hardware Systems (1)
- Life Sciences (1)
- Numerical Analysis and Computation (1)
- Operations Research, Systems Engineering and Industrial Engineering (1)
- Other Applied Mathematics (1)
- Other Mathematics (1)
- Other Operations Research, Systems Engineering and Industrial Engineering (1)
- Keyword
-
- Computer science education (7)
- Channel routing (6)
- Computer science (6)
- Area-universal networks (4)
- Parallel computation (4)
-
- Randomized routing (4)
- VLSI layout (4)
- Exploring Computer Science (3)
- Robotics (3)
- Wormhole routing (3)
- Algorithms (2)
- Computer programming (2)
- Computer science attitudes (2)
- Computing (2)
- Data analysis (2)
- Fat pyramid (2)
- Fat-trees (2)
- Greedy routing (2)
- High school computer science (2)
- Hypercube (2)
- Interconnection networks (2)
- Layout algorithms (2)
- Lower bounds (2)
- Packet routing (2)
- Single-layer channel routing (2)
- Single-layer routing (2)
- VLSI (2)
- Analysis of algorithms (1)
- Appropriate cost (1)
- Area-universality (1)
Articles 31 - 46 of 46
Full-Text Articles in Physical Sciences and Mathematics
Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg
Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg
Ronald Greenberg
There are certain straightforward algorithms for laying out finite-state machines. This paper shows that these algorithm are optimal in the worst case for machines with fixed alphabets. That is, for any s and k, there is a deterministic finite-state machine with s states and k symbols such that any layout algorithm requires Ω(ks log s) area to lay out its realization. Similarly, any layout algorithm requires Ω(ks^2) area in the worst case for nondeterministic finite-state machines with s states and k symbols.
Efficient Multi-Layer Channel Routing, Ronald I. Greenberg
Efficient Multi-Layer Channel Routing, Ronald I. Greenberg
Ronald Greenberg
No abstract provided.
Ecs Evaluation Survey Instruments, Ronald I. Greenberg, Steven Mcgee
Ecs Evaluation Survey Instruments, Ronald I. Greenberg, Steven Mcgee
Ronald Greenberg
This is a compilation of several surveys used in conjunction with a large-scale implementation of the Exploring Computer Science Curriculum in high schools in the Chicago Public Schools: ECS student presurvey pp. 1--2, ECS student postsurvey pp. 3--4, teacher background survey pp. 5--11, teacher ECS workshop feedback form pp. 12--13, teacher ECS implementation survey pp. 14--24
Evaluation Of The Impacts Computer Science Presentations, Ronald I. Greenberg
Evaluation Of The Impacts Computer Science Presentations, Ronald I. Greenberg
Ronald Greenberg
Recent computer science enrollments have shown positive trends. However, these trends are not evenly distributed by gender and race. Efforts to recruit underrepresented students should focus on providing information that demystifies the field of computer science. This paper reports on such an effort to inform underrepresented high school students about the field and its diversity. The results suggest that increasing awareness in an enjoyable format can increase student interest in pursuing computer science. These results can provide guidance about ways to encourage students to take high school computer science classes as motivation and preparation for college-level computer science.
Finding A Maximum-Denisty Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih
Finding A Maximum-Denisty Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih
Ronald Greenberg
We present efficient algorithms to find a maximum-density planar subset of n 2-pin nets in a channel. The simplest approach is to make repeated usage of Supowit's dynamic programming algorithm for finding a maximum-size planar subset, which leads to O(n^3) time to find a maximum-density planar subset. But we also provide an algorithm whose running time is dependent on other problem parameters and is often more efficient. A simple bound on the running time of this algorithm is O(nlgn+n(t+1)w), where t is the number of two-sided nets, and w is the number of nets in the output. Though the worst-case …
Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg
Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg
Ronald Greenberg
Magic tricks based on computer science concepts help grab student attention and can motivate them to delve more deeply. Error detection ideas long used by computer scientists provide a rich basis for working magic; probably the most well known trick of this type is one included in the CS Unplugged activities. This paper shows that much more powerful variations of the trick can be performed, some in an unplugged environment and some with computer assistance. Some of the tricks also show off additional concepts in computer science and discrete mathematics.
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Ronald Greenberg
This thesis is primarily concerned with two problems of interconnecting components in VLSI technologies. In the first case, the goal is to construct efficient interconnection networks for general-purpose parallel computers. The second problem is a more specialized problem in the design of VLSI chips, namely multilayer channel routing. In addition, a final part of this thesis provides lower bounds on the area required for VLSI implementations of finite-state machines. This thesis shows that networks based on Leiserson's fat-tree architecture are nearly as good as any network built in a comparable amount of physical space. It shows that these "universal" networks …
Feasible Offset And Optimal Offset For General Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih
Feasible Offset And Optimal Offset For General Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih
Ronald Greenberg
This paper provides an efficient method to find all feasible offsets for a given separation in a very large-scale integration (VLSI) channel-routing problem in one layer. The previous 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 )$, the problem can be solved in time $O( n^{1.5} \lg n )$, which improves upon a “naive” $O( cn )$ approach. As a …
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.
Does A Taste Of Computing Increase Computer Science Enrollment?, Steven Mcgee, Randi Mcgee-Tekula, Jennifer Duck, Ronald I. Greenberg, Lucia Dettori, Dale F. Reed, Brenda Wilkerson, Don Yanek, Andrew Rasmussen, Gail Chapman
Does A Taste Of Computing Increase Computer Science Enrollment?, Steven Mcgee, Randi Mcgee-Tekula, Jennifer Duck, Ronald I. Greenberg, Lucia Dettori, Dale F. Reed, Brenda Wilkerson, Don Yanek, Andrew Rasmussen, Gail Chapman
Ronald Greenberg
The Exploring Computer Science (ECS) high school curriculum is designed to foster deep engagement through equitable inquiry around computer science concepts. We have shown that students find ECS courses personally relevant, are increasing their expectancies of success and perceived value for the field of computer science, and are more likely to take another computing course.
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.
An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg
An Investigation Of Montmort's "Probleme De Recontres" And Generalizations, Ronald I. Greenberg
Ronald Greenberg
I have investigated a problem which may be phrased in many ways, such as finding the probability of answering a given number of questions correctly on a randomly-completed matching test which may have a number of extra "dud" answers. I have determined such probabilities, the average number of correct answers, and other allied results. I have also investigated a related problem involving the number of ways of choosing a different element from each of a certain collection of sets.
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.
Does A Taste Of Computing Increase Computer Science Enrollment?, Steven Mcgee, Randi Mcgee-Tekula, Jennifer Duck, Taylor White, Ronald I. Greenberg, Lucia Dettori, Dale F. Reed, Brenda Wilkerson, Don Yanek, Andrew Rasmussen, Gail Chapman
Does A Taste Of Computing Increase Computer Science Enrollment?, Steven Mcgee, Randi Mcgee-Tekula, Jennifer Duck, Taylor White, Ronald I. Greenberg, Lucia Dettori, Dale F. Reed, Brenda Wilkerson, Don Yanek, Andrew Rasmussen, Gail Chapman
Ronald Greenberg
This study investigated the impact of the Exploring Computer Science (ECS) program on the likelihood that students of all races and gender would pursue further computer science coursework in high school. ECS is designed to foster deep engagement through equitable inquiry around computer science concepts. If the course provides a meaningful and relevant experience, it will increase students' expectancies of success as well as increase their perceived value for the field of computer science. Using survey research, we sought to measure whether the relevance of students' course experiences influenced their expectancies and value and whether those attitudes predicted whether students …
An Interval Arithmetic Newton Method For Solving Systems Of Nonlinear Equations, Ronald I. Greenberg, Eldon R. Hansen
An Interval Arithmetic Newton Method For Solving Systems Of Nonlinear Equations, Ronald I. Greenberg, Eldon R. Hansen
Ronald Greenberg
We introduce an interval Newton method for bounding solutions of systems of nonlinear equations. It entails three sub-algorithms. The first is a Gauss-Seidel type step. The second is a real (non-interval) Newton iteration. The third solves the linearized equations by elimination. We explain why each sub-algorithm is desirable and how they fit together to provide solutions in as little as 1/3 to 1/4 the time required by a commonly used method due to Krawczyk.