Open Access. Powered by Scholars. Published by Universities.®
Physical Sciences and Mathematics Commons™
Open Access. Powered by Scholars. Published by Universities.®
- Institution
- Publication
- Publication Type
Articles 1 - 4 of 4
Full-Text Articles in Physical Sciences and Mathematics
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 …
Low-Degree Spanning Trees Of Small Weight, Samir Khuller, Balaji Raghavachari, Neal Young
Low-Degree Spanning Trees Of Small Weight, Samir Khuller, Balaji Raghavachari, Neal Young
Dartmouth Scholarship
Given n points in the plane, the degree-K spanning-tree problem asks for a spanning tree of minimum weight in which the degree of each vertex is at most K. This paper addresses the problem of computing low-weight degree-K spanning trees for $K > 2$. It is shown that for an arbitrary collection of n points in the plane, there exists a spanning tree of degree 3 whose weight is at most 1.5 times the weight of a minimum spanning tree. It is shown that there exists a spanning tree of degree 4 whose weight is at most 1.25 times …
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
Unsupervised Algorithms For Learning Emergent Spatio-Temporal Correlations, Chaitanya Tumuluri
Electrical Engineering and Computer Science - Technical Reports
Many applications require the extraction of spatiotemporal correlations among dynamically emergent features of non-stationary distributions. In such applications it is not possible to obtain an a priori analytical characterization of the emergent distribution. This paper extends the Growing Cell Structures (GCS) network and presents two novel (GIST and GEST) networks, which combine unsupervised feature-extraction and Hebbian learning, for tracking such emergent correlations. The networks were successfully tested on the challenging Data Mapping problem, using an execution driven simulation of their implementation in hardware. The results of the simulations show the successful use of the GIST and GEST networks for extracting …
Torus Routing In The Presence Of Multicasts, Hiroki Ishibashi
Torus Routing In The Presence Of Multicasts, Hiroki Ishibashi
Theses Digitization Project
No abstract provided.