Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Keyword
-
- Computer science (5)
- Channel routing (4)
- Area-universal networks (3)
- Parallel computation (3)
- Randomized routing (3)
-
- Wormhole routing (3)
- Fat-trees (2)
- Interconnection network (2)
- Interconnection networks (2)
- Latency (2)
- Layout algorithms (2)
- Lower bounds (2)
- Queueing theory (2)
- Single-layer channel routing (2)
- Single-layer routing (2)
- Throughput (2)
- VLSI (2)
- VLSI layout (2)
- 2D-mesh (1)
- Algorithms (1)
- Analysis of algorithms (1)
- Area-universality (1)
- Artificial intelligence (1)
- Bijections (1)
- Bioinformatics (1)
- Biomolecular sequence analysis (1)
- Butterfly fat-tree (1)
- Combinatorial problems (1)
- Computational complexity (1)
- Computational thinking (1)
- Publication Year
Articles 1 - 26 of 26
Full-Text Articles in Physical Sciences and Mathematics
Directed Acyclic Graph-Based Neural Networks For Tunable Low-Power Computer Vision, Abhinav Goel, Caleb Tung, Nick Eliopoulos, Xiao Hu, George K. Thiruvathukal, James C. Davis, Yung-Hisang Lu
Directed Acyclic Graph-Based Neural Networks For Tunable Low-Power Computer Vision, Abhinav Goel, Caleb Tung, Nick Eliopoulos, Xiao Hu, George K. Thiruvathukal, James C. Davis, Yung-Hisang Lu
Computer Science: Faculty Publications and Other Works
Processing visual data on mobile devices has many applications, e.g., emergency response and tracking. State-of-the-art computer vision techniques rely on large Deep Neural Networks (DNNs) that are usually too power-hungry to be deployed on resource-constrained edge devices. Many techniques improve DNN efficiency of DNNs by compromising accuracy. However, the accuracy and efficiency of these techniques cannot be adapted for diverse edge applications with different hardware constraints and accuracy requirements. This paper demonstrates that a recent, efficient tree-based DNN architecture, called the hierarchical DNN, can be converted into a Directed Acyclic Graph-based (DAG) architecture to provide tunable accuracy-efficiency tradeoff options. We …
Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg
Educational Magic Tricks Based On Error-Detection Schemes, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
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.
Hash-Map-Eradicator: Filtering Non-Target Sequences From Next Generation Sequencing Reads, Jonathon Brenner, Catherine Putonti
Hash-Map-Eradicator: Filtering Non-Target Sequences From Next Generation Sequencing Reads, Jonathon Brenner, Catherine Putonti
Bioinformatics Faculty Publications
Contemporary DNA sequencing technologies are continuously increasing throughput at ever decreasing costs. Moreover, due to recent advances in sequencing technology new platforms are emerging. As such computational challenges persist. The average read length possible has taken a giant leap forward with the PacBio and Nanopore solutions. Regardless of the platform used, impurities within the DNA preparation of the sample - be it from unintentional contaminants or pervasive symbiots - remains an issue. We have developed a new tool, HAsh-MaP-ERadicator (HAMPER), for the detection and removal of non-target, contaminating DNA sequences. Integrating hash-based and mapping-based strategies, HAMPER is both memory and …
Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg
Fast And Space-Efficient Location Of Heavy Or Dense Segments In Run-Length Encoded Sequences, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
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 …
On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan
On The Area Of Hypercube Layouts, Ronald I. Greenberg, Lee Guan
Computer Science: Faculty Publications and Other Works
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 …
Modeling And Comparison Of Wormhole Routed Mesh And Torus Networks, Ronald I. Greenberg, Lee Guan
Modeling And Comparison Of Wormhole Routed Mesh And Torus Networks, Ronald I. Greenberg, Lee Guan
Computer Science: Faculty Publications and Other Works
2D-mesh and torus networks have often been proposed as the interconnection pattern for parallel computers. In addition, wormhole routing has increasingly been advocated as a method of reducing latency. Most analysis of wormhole routed networks, however, has focused on the torus and the broader class of k-ary n-cubes to which it belongs. This paper presents a performance model for the wormhole routed mesh, and it compares the performance of the mesh and torus based on theoretical and empirical analyses.
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
Computer Science: Faculty Publications and Other Works
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.
Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih
Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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.
Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih
Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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 …
Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih
Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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 …
Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh
Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh
Computer Science: Faculty Publications and Other Works
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 …
Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg
Finding Connected Components On A Scan Line Array Processor, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
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.
The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg
The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
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 …
Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh
Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh
Computer Science: Faculty Publications and Other Works
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 …
Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih
Parallel Algorithms For Single-Layer Channel Routing, Ronald I. Greenberg, Shih-Chuan Hung, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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 …
Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih
Feasible Offset And Optimal Offset For Single-Layer Channel Routing, Ronald I. Greenberg, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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 …
Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih
Minimizing Channel Density With Movable Terminals, Ronald I. Greenberg, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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.
On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy
On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy
Computer Science: Faculty Publications and Other Works
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.
Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh
Packet Routing In Networks With Long Wires, Ronald I. Greenberg, H.-C. Oh
Computer Science: Faculty Publications and Other Works
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 N packets in O((Clg^ε(Nd)+Dlg(Nd))/lglg(Nd)) time, where C is the maximum congestion and D is the length of the longest path, both taking wire delays into account, and d is the longest path in terms of number of wires. We also …
Finding A Maximum-Density Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih
Finding A Maximum-Density Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih
Computer Science: Faculty Publications and Other Works
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 …
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
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 …
Efficient Multi-Layer Channel Routing, Ronald I. Greenberg
Efficient Multi-Layer Channel Routing, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
No abstract provided.
Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson
Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson
Computer Science: Faculty Publications and Other Works
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 …
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
Computer Science: Faculty Publications and Other Works
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.
Euclidean Traveling Salesman Heuristics, Ron Greenberg, Cindy Phillips, Joel Wein
Euclidean Traveling Salesman Heuristics, Ron Greenberg, Cindy Phillips, Joel Wein
Computer Science: Faculty Publications and Other Works
No abstract provided.
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Randomized Routing On Fat-Trees, Ronald I. Greenberg
Computer Science: Faculty Publications and Other Works
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/ …