Physical Sciences and Mathematics Commons^™

Flor Revisited (Again): Eqtl And Mutational Analysis Of Nb-Lrr Mediated Immunity To Powdery Mildew In Barley, Roger P. Wise, Priyanka Surana, Gregory S. Fuerst, Ruo Xu, Divya Mistry, Julie A. Dickerson, Dan Nettleton Dr.

Dan Nettleton

Genes encoding early signaling events in pathogen defense often are identified only by their phenotype. Such genes involved in barley-powdery mildew interactions include Mla, specifying race-specific resistance; Rar1 (Required for Mla12-specified resistance1), and Rom1 (Restoration of Mla-specified resistance1). The HSP90-SGT1-RAR1 complex appears to function as chaperone in MLA-specified resistance, however, much remains to be discovered regarding the precise signaling underlying plant immunity. Genetic analyses of fast-neutron mutants derived from CI 16151 (Mla6) uncovered a novel locus, designated Rar3 (Required for Mla6-specified resistance3). Rar3 segregates independent of Mla6 and Rar1, and rar3 mutants are susceptible to Blumeria graminis f. sp. hordei …

Effects Of Disorder On Thermoelectric Properties Of Semiconducting Polymers, Zlatan Aksamija, Dhandapani Venkataraman, Connor J. Boyle, Meenakshi Upadhyaya

Zlatan Aksamija

Signal Flow Graph Approach To Efficient Dst I-Iv Algorithms, Sirani M. Perera

Sirani Mututhanthrige Perera

In this paper, fast and efficient discrete sine transformation (DST) algorithms are presented based on the factorization of sparse, scaled orthogonal, rotation, rotation-reflection, and butterfly matrices. These algorithms are completely recursive and solely based on DST I-IV. The presented algorithms have low arithmetic cost compared to the known fast DST algorithms. Furthermore, the language of signal flow graph representation of digital structures is used to describe these efficient and recursive DST algorithms having (n􀀀1) points signal flow graph for DST-I and n points signal flow graphs for DST II-IV.

Tailoring The Asymmetric Magnetoimpedance Response In Exchange-Biased Ni - Fe Multilayers, Ufuk Kilic, Carolina Ross, Carlos Garcia

Ufuk Kilic

High Consequence Scenarios For North Korean Atmospheric Nuclear Tests With Policy Recommendations For The U.S. Government, Thomas S. Popik, Jordan T. Kearns, George H. Baker Iii, Henry F. Cooper, William R. Harris

George H Baker

The government of North Korea has declared high-altitude EMP-capability to be a “strategic goal” and has also threatened an atmospheric test of a hydrogen bomb. Atmospheric nuclear tests have the potential to cripple satellites and the undersea cable networks critical to communication, and navigation necessary for trans-Pacific trade among the U.S., China, and other nations. When a nuclear warhead is detonated at high altitude, a series of electromagnetic pulses radiate downward within the line of sight of the blast. These pulses can disable equipment with miniature electronics and long conductors. Electric grid controls and transmission systems are especially vulnerable. Intense …

Damage Analysis Modified Trac Computer Program (Damtrac), George H. Baker Iii, Alan D. Mcnutt, G. Bradford Shea, David M. Rubenstein

George H Baker

A computer program tailored for EMP damage analysis of solid-state circuitry has been developed by modifying the existing TRAC network analysis program. Modification of the TRAC diode and transistor models to include breakdown parameters and the addition of a semiconductor device parameter library have greatly simplified the analyst's task. An added feature is a subroutine that automatically calculates the amplitude and duration of transient power dissipated in electronic circuit components.

Randomized Routing On Fat-Trees, Ronald I. Greenberg, Charles E. Leiserson

Ronald Greenberg

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 …

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, Ronald I. Greenberg

Ronald Greenberg

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 …

Randomized Routing On Fat-Trees, Ronald I. Greenberg

Ronald Greenberg

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/ …

Universal Wormhole Routing, Ronald I. Greenberg, Hyeong-Cheol Oh

Ronald Greenberg

In this paper, 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ηlogP) time with high probability, 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 A) …

Single-Layer Channel Routing And Placement With Single-Sided Nets, Ronald I. Greenberg, Jau-Der Shih

Ronald Greenberg

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 …

Retrospective Data Filter, Richard J. Prengaman, Robert E. Thurber, Joe Phipps, Ronald I. Greenberg, Wai L. Hom, James F. Jaworski, Guy W. Riffle

Ronald Greenberg

In a target detection communication system, apparatus and method for determining the presence of probable targets based on contacts (which can indicate the presence of a target, noise, chatter, or objects not of interest) detected within a predefined position sector or sectors over a specified number of scans. The position of each detected contact, as a contact of interest, is compared with the positions of contacts detected at previous times or scans. Velocity profiles indicate which previous contacts support the likelihood that the contact of interest represents a target having a velocity within a defined band. The likelihood, which can …

On The Difficulty Of Manhattan Channel Routing, Ronald I. Greenberg, Joseph Jaja, Sridhar Krishnamurthy

Ronald Greenberg

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.

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 cut position and a …

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

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 channels …

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

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

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 only one side of …

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 and processor …

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 time bound suffices to find the optimal offset …

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

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

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 …

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 …

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

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.

Carbide-Derived Carbon By Electrochemical Etching Of Vanadium Carbides, Luis G.B. Camargo, Benjamin G. Palazzo, Greg Taylor, Zach A. Norris, Yash K. Patel, Jeffrey D. Hettinger, Lei Yu

Jeffrey Hettinger

Carbide-derived Carbon (CDC) has been demonstrated to be an excellent electrode material for electrochemical devices including supercapacitors due to its chemical and electrochemical stability, large specific surface area and controllable pore size and morphology. Currently, CDC is prepared from metal carbides by chlorination in a chlorine gas atmosphere at temperatures of 350°C or higher. In this paper, conversion using electrochemical methods is reported, which can be achieved by oxidizing vanadium carbides (VC or V2C) in aqueous solutions at room temperature and a mild electrode potential to prepare CDC thin film as electrode materials for “on-chip” supercapacitiors. It was found that …

Evolution And Rationale For United States Department Of Defense Electromagnetic Pulse Protection Standard, George H. Baker Iii

George H Baker

The United States (US) Department of Defense (DoD) Electromagnetic Pulse (EMP) protection standard offers a solid basis for protecting commercial communication, data, and control facilities. Because of the standard’s shielded barrier and test requirements, it is not surprising that there is a strong temptation within industry and government to dismiss the MIL-STD 188-125 approach in favor of less rigorous protection methods. It is important to understand that US DoD EMP protection standard for fixed facilities, MIL-STD-188-125, reflects an evolution by trial and error that spanned a period of decades beginning with the acquisition of the Minuteman Missile System in the …

Proposal For A Dod Combined Battlefield Electromagnetic Environmental Effects (E3) Initiative, George H. Baker Iii

George H Baker

The presentation emphasizes the growing importance of electromagnetic survivability and compatibility. Operation Desert Storm demonstrated the clear military advantage provided by sophisticated electronic weapon and communication systems. In addition, the offensive tactic of taking out the enemy's eyes and ears during the air war paid off, giving our military decisive air superiority. The lessons for the future are clear. High-tech electronics now so dominates the battlefield that the outcome of future conflicts could well be decided by electronics attrition rather than human casualties. Our Desert Storm experience thus accentuates the importance of guaranteeing that our electronic systems will not be …