VLSI and Circuits, Embedded and Hardware Systems Commons^™

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

Computer Science: Faculty Publications and Other Works

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 …

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 …

Genetic Algorithms Vs. Simulated Annealing: A Comparison Of Approaches For Solving The Circuit Partitioning Problem, Theodore W. Manikas, James T. Cain

Computer Science and Engineering Research

An important stage in circuit design is placement, where components are assigned to physical locations on a chip. A popular contemporary approach for placement is the use of simulated annealing. While this approach has been shown to produce good placement solutions, recent work in genetic algorithms has produced promising results. The purpose of this study is to determine which approach will result in better placement solutions.

A simplified model of the placement problem, circuit partitioning, was tested on three circuits with both a genetic algorithm and a simulated annealing algorithm. When compared with simulated annealing, the genetic algorithm was found …

A Vhdl Design Of A Reconfigurable Cache Memory System, Tiffany M. Brooks

Honors Capstone Projects and Theses

No abstract provided.

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 …

Accelerating Conservative Parallel Simulation Of Vhdl Circuits, Joel F. Hurford

Theses and Dissertations

This research effort considers heuristic and cost model based techniques for the optimal partitioning of VHDL circuits for parallel simulation. Correlation statistics are gathered on a wide variety of graph-based a priori parameters. Linear regression is used to identify significant parameters for inclusion in a representative cost model. Driving a greedy search, this cost model is used to improve upon initial heuristic partitions. The influence of feedback dominated previous research so a no-feedback algorithm is used to create the initial partition The circuits studied range from 1,050 to 4,243 gates.

The Evaluation Of Device Model Dependence In The Design Of A High-Frequency, Analog, Cmos Transconductance-C Filter, Susan Rose Brotman

Dissertations and Theses

It is important to have the ability to predict the effects of device model variation when designing integrated transconductance-C type active filters. Applying these filters to integrated circuit design has become increasingly popular due to its ease of implementation in monolithic form. With the introduction of fully automated design tools, predictable behavior of high-level variables becomes still more important. The purpose of this study is to evaluate the process parameter spread of analog device models to determine the effect on the design parameters of an active filter. This information's significant contribution directly effects the feasibility and realization of automating analog …

Partitioning Structural Vhdl Circuits For Parallel Execution On Hypercubes, Kevin L. Kapp

Theses and Dissertations

Distributing simulations among multiple processors is one approach to reducing VHDL simulation time for large VLSI circuit designs. However, parallel simulation introduces the problem of how to partition the logic gates and system behaviors among the available processors in order to obtain maximum speedup. This research investigates deliberate partitioning algorithms that account for the complex inter-dependency structure of the circuit behaviors. Once an initial partition has been obtained, a border annealing algorithm is used to iteratively improve the partition. In addition, methods of measuring the cost of a partition and relating it to the resulting simulation performance are investigated. Structural …

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 …

A Physics-Based Heterojunction Bipolar Transistor Model For Integrated Circuit Simulation, James A. Fellows

Theses and Dissertations

The purpose of this research effort was to derive a physics-based dc model for a Heterojunction Bipolar Transistor HBT. The dc model was then linearized to arrive at a small-signal model that accurately predicts the devices electrical behavior at microwave frequencies. This new model offers features not found in previous analytical or physics-based HBT models such as consideration of a cylindrical emitter-base geometry and is direct implementation into SPICE Simulation Program with Integrated Circuit Emphasis. The device model parameters were determined from a knowledge of the device material, geometry, and fabrication process. The model was then developed by using semiconductor …

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 …

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

Computer Science: Faculty Publications and Other Works

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.

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.

Version And Transaction Management In Osmagic: An Object-Oriented Database Implementation Of The Magic Vlsi Layout Design Tool, Gary M. Lightner

Theses and Dissertations

The goal of this thesis was to study the feasibility of using an object-oriented database management system to provide the functionality and performance needed to support a complex computer-aided design tool. We do this by modifying OSMagic, a prototype system of the Magic very large scale integrated (VLSI) circuit design tool implemented on the ObjectStore object- oriented database management system. OSMagic was changed to support three different interfaces to ObjectStore and to work in a networking environment. We then designed and examined the use of version and transaction management models as a means of addressing the weaknesses of the prototype …

A Generic Template Extractor (Gentex) In C For Vlsi Design Verification, Kenneth J. Mcclellan Jr.

Theses and Dissertations

The problem of VLSI design verification through circuit extraction was analyzed. The problems of creating a simple template format, the permutability of pins, maintaining connectivity, and performance were focused on. A generic template extractor (GENTEX) was developed in the C programming language for use as a testbed to find solutions to these problems. Six different extraction algorithms were tested with GENTEX and compared based on performance. EDIF translation programs were used to interface with GENTEX on both the input and output sides. One translation program converted an EDIF representation of a schematic into the template format used by GENTEX. The …

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.

Design And Development Of A High-Speed Winograd Fast Fourier Transform Processor Board, James F. Herron

Theses and Dissertations

Since 1985, the Air Force Institute of Technology has pursued a project to develop a 4080-point Discrete Fourier Transform processor using the Winograd Fourier Transform Algorithm (WFTA) and Good-Thomas Prime Factoring Algorithm (PFA). In the first attempt to build a working system, this research effort designed and constructed, in part, a modified single processor architecture in order to demonstrate the proof of concept of the WFTA system design. This prototype architecture is simpler in implementation but uses the same principles and procedures as those of the 4080-point WFTA design. The design developed in this thesis was validated using the Very …

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

Computer Science: Faculty Publications and Other Works

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.

Experimental Evaluation Of Incorporating Digital And Analog Integrated Circuit Die On A Common Substrate Utilizing Silicon-Hybrid Wafer-Scale Integration Technology, Philip C. Reamy

Theses and Dissertations

The objective of this research effort was to investigate the implementation of analog circuits in a wafer scale integration system. A test circuit composed of analog and digital subsystems was designed and tested through simulation. IC die containing this test circuit were utilized in the WSI system fabrication. Preliminary investigations were conducted to evaluate the potential improvements to the IC die mounting procedure, a key step in fabricating functional WSI systems. These investigations demonstrated a procedure which produced repeatable results in achieving acceptable planarization of IC die and host substrate surfaces. These investigations also demonstrated the successful application of a …

Hardware-Verification Through Logic Extraction, Michael A. Dukes

Theses and Dissertations

A Prolog-based system is described which employs logic-extraction to perform hardware-verification. The extraction rules are built automatically from hierarchical structural VHDL models, enabling the equivalence of a structural VHDL description and a layout specification to be verified. Pin-to-pin critical- path analysis is performed within the logic-extraction process; many noncritical paths are pruned early, making pin-to-pin critical path analysis of large circuits feasible. It is demonstrated that a design methodology based on logic extraction, VHDL, and a layout tool can provide a fabricated functionally- correct IC design without circuit-level or switch-level simulation. This methodology is shown to be practical for VLSI …

Design And Analysis Of Electrical Circuits That Produce Fractional-Order Differentiation, Richard N. Hughes

Theses and Dissertations

Two half-order differentiator circuit designs were investigated and their electrical performance evaluated (Oldham and Oldfield). Initially, each circuit design was computer modelled and simulated using the HSPICE computer analysis program. Then, each circuit design (Oldham and Oldfield) was fabricated with two different component technologies. This resulted in four circuits, realized on printed circuit boards, to be evaluated--Oldham discrete component; Oldham hybrid component; Oldfield discrete component; and Oldfield surface mount component. The characterizations of each circuit's electrical performance is documented with time, phase, gain, noise and spectrum responses. A comparison of each circuit's performance versus the design criteria and computer model …

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 …

An Object-Oriented Database Implementation Of The Magic Vlsi Layout Design System, Timothy M. Jacobs

Theses and Dissertations

This thesis attempts to prove that the commercially available Object Store data management system provide the performance and functionality necessary to support a complex engineering design system. This is accomplished by modifying the Magic VLSI circuit layout design system to eliminate its current Unix file data management system and replace it with Object Store. The approach to this research effort includes a design recovery of the Magic system and identification of its ket data management functions. These functions are then modified to take advantage of the database management facilities of Object Store. Additional code is added to instrument performance measurement …

An Investigation Of A Design For A Finite-Difference Time Domain (Fdtd) Hardware Accelerator, James R. Marek

Theses and Dissertations

This study investigated increasing the speed of Finite-Difference Time Domain (FDTD) cell calculations through a special purpose architecture using Very Large Scale Integration (VLSI). These FDTD cell equations model inhomogeneous, isotropic, lossy magnetic and dielectric materials. Special attention was given to simplicity and performance, using the fastest components generally available in AFIT VLSI programs, while attempting to minimize component count. A VHSIC Hardware Description Language simulation of the proposed chip established design feasibility and provided performance estimates: 350 ns to generate the first cell value, 200 ns thereafter (30 MFLOPS maximum double-precision). This study also implemented boundary conditions in hardware …

A Prolog System For Converting Vhdl-Based Models To Generalized Extraction System (Ges) Rules, Michael A. Dukes, Frank M. Brown, Joanne E. Degroat

AFIT Documents

With the advent of VHDL accurate documentation of hardware designs is a practical reality. In the past, schematics were typically used for documentation of hardware designs. However, these schematics would usually become obsolete as the hardware design was being constructed. Deviations in the hardware design would sometimes not be reflected in the schematics. For design groups, failure to update schematics could lead to different parts of a hardware design becoming incompatible. A system to ensure compliance of hardware with its VHDL documentation is presented in this paper. The system, vhdl2ges, is meant to help guide the development of hardware by …

A Vision System Model, Erik J. Fretheim

Theses and Dissertations

This dissertation provides four major contributions to the field of vision research. The first contribution is a general vision system model. The model, which blends biological as well as technological methods into a coherent approach to vision, will provide a basis for implementing vision systems. The second contribution of this dissertation is to demonstrate particular implementations of portions of the model. These implementations will include methods for using Gabor wavelets in edge detection, in preprocessing images for use as feature vectors in backpropagation neural networks, and as basis functions in a recognition/reconstruction network, as well as methods for integrating color …

A Robotic Tactile Sensor Incorporating Silicon Planar Technology: A Piezoelectric Polyvinylidene Fluoride Film, And On-Chip Signal Processing, Robert C. Fitch Jr.

Theses and Dissertations

This research effort pursued the design, fabrication, and test of a robotic tactile sensor. The VLSI integrated circuit (IC) portion of the sensor included a 7 x 7 array of metal electrodes which were individually connected to identical MOSFET amplifiers. A 25 micrometers thick patch (6 mm x 6 mm) of piezoelectric polyvinylidene fluoride (PVDF) film was attached to the array with a non-conductive adhesive, thereby creating an array of taxels. Charge, generated by the PVDF film, was detected by the amplifiers. The outputs of these amplifiers were connected to onchip signal circuitry designed to produce a single stream of …

Design And Fabrication Of An Implantable Cortical Semiconductor Integrated Circuit Electrode Array, Pierre K. Lefevre

Theses and Dissertations

This research furthered the processing steps of the AFIT 16 by 16 implantable cortical semiconductor integrated circuit electrode array, or brain chip. The areas of interest include the brain chip electron ics, metallization, ionic permeation, and implantation. The electronics and metallization are heavily covered. A high speed, single clock divide-by-two circuit was modified with a reset transistor and cascaded to form a ripple counter. This device had stable operation at specific source voltage and clock voltage and frequency. A 7-stage inverter with 10 unmodified divide-by-two circuits cascaded operated between 1.7 and 8 volts, and between 39 Khz and 1 Mhz, …

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

Computer Science: Faculty Publications and Other Works

No abstract provided.