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

VLSI and Circuits, Embedded and Hardware Systems Commons

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

583 Full-Text Articles 751 Authors 393,861 Downloads 47 Institutions

All Articles in VLSI and Circuits, Embedded and Hardware Systems

Faceted Search

583 full-text articles. Page 7 of 26.

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

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 ...


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

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.


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

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 ...


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

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.


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

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.


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

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 ...


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

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 ...


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

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 ...


Lower Bounds On The Area Of Finite-State Machines, M. J. Foster, Ronald I. Greenberg 2018 Loyola University Chicago

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 2018 Selected Works

Efficient Multi-Layer Channel Routing, Ronald I. Greenberg

Ronald Greenberg

No abstract provided.


Finding A Maximum-Denisty Planar Subset Of A Set Of Nets In A Channel, Ronald I. Greenberg, Jau-Der Shih 2018 Selected Works

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 ...


Efficient Interconnection Schemes For Vlsi And Parallel Computation, Ronald I. Greenberg 2018 Loyola University Chicago

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 ...


An Empirical Comparison Of Area-Universal And Other Parallel Computing Networks, Ronald I. Greenberg, Lee Guan 2018 Selected Works

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 ...


A Systolic Simulation And Transformation System, Ronald I. Greenberg, H.-C. Oh 2018 Selected Works

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.


Toward Biologically-Inspired Self-Healing, Resilient Architectures For Digital Instrumentation And Control Systems And Embedded Devices, Shawkat Sabah Khairullah 2018 Virginia Commonwealth University

Toward Biologically-Inspired Self-Healing, Resilient Architectures For Digital Instrumentation And Control Systems And Embedded Devices, Shawkat Sabah Khairullah

Theses and Dissertations

Digital Instrumentation and Control (I&C) systems in safety-related applications of next generation industrial automation systems require high levels of resilience against different fault classes. One of the more essential concepts for achieving this goal is the notion of resilient and survivable digital I&C systems. In recent years, self-healing concepts based on biological physiology have received attention for the design of robust digital systems. However, many of these approaches have not been architected from the outset with safety in mind, nor have they been targeted for the automation community where a significant need exists. This dissertation presents a new ...


Autonomous Uav Battery Swapping, Reed Jacobsen, Nikolai Ruhe, Nathan Dornback 2018 The University of Akron

Autonomous Uav Battery Swapping, Reed Jacobsen, Nikolai Ruhe, Nathan Dornback

Williams Honors College, Honors Research Projects

One of the main hindrances of unmanned aerial vehicle (UAV) technology are power constraints. One way to alleviate some power constraints would be for two UAVs to exchange batteries while both are in flight. Autonomous mid-air battery swapping will expand the scope of UAV technology by allowing for indefinite flight times and longer missions. A single board computer will control each UAV’s flight software to respond to inputs to align with each other mid-flight. When the two UAVs have joined, mechanical components will exchange a depleted battery on the worker UAV for a freshly charged battery that belongs to ...


An Iterative Signal Fusion Method For Reconstruction Of Inplane Strain Maps From Strain Measurements By Hybrid Dense Sensor Networks, Mohammadkazem Sadoughi, Austin Downey, Chao Hu, Simon Laflamme 2018 Iowa State University

An Iterative Signal Fusion Method For Reconstruction Of Inplane Strain Maps From Strain Measurements By Hybrid Dense Sensor Networks, Mohammadkazem Sadoughi, Austin Downey, Chao Hu, Simon Laflamme

Civil, Construction and Environmental Engineering Conference Presentations and Proceedings

Flexible skin-like membranes have received considerable research interest for the costeffective monitoring of mesoscale (large-scale) structures. The authors have recently proposed a large-area electronic consisting of a soft elastomeric capacitor (SEC) that transduces a structure's change in geometry (i.e. strain) into a measurable change in capacitance. The SEC sensor measures the summation of the orthogonal strain (i.e. εx + εy). It follows that an algorithm is required for the decomposition of the signal into unidirectional strain maps. In this study, a new method enabling such decomposition that leverages a dense sensor network of SECs and resistive strain gauges ...


Ball Oscillating Bouncer, Eric Blok, Daniel Altemese, Ryan Nowacki, Maram Qurban 2018 The University of Akron

Ball Oscillating Bouncer, Eric Blok, Daniel Altemese, Ryan Nowacki, Maram Qurban

Williams Honors College, Honors Research Projects

The purpose of this report is to document the need, objectives, marketing and engineering requirements, as well as validate the design of an autonomous control device capable of continuously bouncing a table tennis ball on a paddle. This includes the design of a self correcting system using lightweight materials, and as few sensors and components as possible to achieve a compact, portable design. To accomplish this, the system is designed to react to a ball falling from as short a distance as 10 centimeters above the paddle, meaning all sensor processing, control processing, and motor drives should be able to ...


Recent Advances On Shm Of Reinforced Concrete And Masonry Structures Enabled By Self-Sensing Structural Materials, Filippo Ubertini, Antonella D’Alessandro, Austin Downey, Enrique García-Macías, Simon Laflamme, Rafael Castro-Triguero 2018 University of Perugia

Recent Advances On Shm Of Reinforced Concrete And Masonry Structures Enabled By Self-Sensing Structural Materials, Filippo Ubertini, Antonella D’Alessandro, Austin Downey, Enrique García-Macías, Simon Laflamme, Rafael Castro-Triguero

Civil, Construction and Environmental Engineering Conference Presentations and Proceedings

Structural Health Monitoring is aimed at transforming civil structures into self-diagnosing systems able to automatically reveal the occurrence of a fault or a damage after a critical event such as an earthquake. While data science is presently experiencing tremendous advances leading to the availability of powerful tools and algorithms for extracting relevant information by effectively fusing data provided by different types of sensors, one of the main bottlenecks still limiting the development of SHM in the field of civil engineering is the general lack of reliable sensing technologies that are scalable at the large scale. A very promising solution to ...


Parameters Affecting The Resistivity Of Lp-Ebid Deposited Copper Nanowires, Gabriel Smith 2018 University of Kentucky

Parameters Affecting The Resistivity Of Lp-Ebid Deposited Copper Nanowires, Gabriel Smith

Theses and Dissertations--Electrical and Computer Engineering

Electron Beam Induced Deposition (EBID) is a direct write fabrication process with applications in circuit edit and debug, mask repair, and rapid prototyping. However, it suffers from significant drawbacks, most notably low purity. Work over the last several years has demonstrated that deposition from bulk liquid precursors, rather than organometallic gaseous precursors, results in high purity deposits of low resistivity (LPEBID). In this work, it is shown that the deposits resulting from LP-EBID are only highly conductive when deposited at line doses below 25μC/cm. When the dose exceeds this value, the resulting structure is highly porous providing a poor ...


Digital Commons powered by bepress