Second-Order Know-How Strategies, 2018 Lafayette College

#### Second-Order Know-How Strategies, Pavel Naumov, Jia Tao

*Faculty Research and Reports*

The fact that a coalition has a strategy does not mean that the coalition knows what the strategy is. If the coalition knows the strategy, then such a strategy is called a know-how strategy of the coalition. The paper proposes the notion of a second-order know-how strategy for the case when one coalition knows what the strategy of another coalition is. The main technical result is a sound and complete logical system describing the interplay between the distributed knowledge modality and the second-order coalition know-how modality.

Cora: Commingled Remains And Analytics – An Open Community Ecosystem, 2018 University of Nebraska at Omaha

#### Cora: Commingled Remains And Analytics – An Open Community Ecosystem, Nicole Mcelroy, Ryan Ernst

*Student Research and Creative Activity Fair*

Anthropologists at organizations such as the DPAA (Defense POW/MIA Accounting Agency) have the tough job of sorting through commingled remains of fallen soldiers. Under the direction of Professor Pawaskar at the College of IS&T, Ryan Ernst and I are currently developing a web application for the DPAA that will help them inventory the bones and record all the appropriate associations. After the inventory web application is built we will begin the analysis process using graph theory and other mathematical algorithms. This will ultimately help organizations like the DPAA get closer to the end goal of identifying fallen soldiers ...

Virtualized Cloud Platform Management Using A Combined Neural Network And Wavelet Transform Strategy, 2018 California State University – San Bernardino

#### Virtualized Cloud Platform Management Using A Combined Neural Network And Wavelet Transform Strategy, Chunyu Liu

*Electronic Theses, Projects, and Dissertations*

This study focuses on implementing a log analysis strategy that combines a neural network algorithm and wavelet transform. Wavelet transform allows us to extract the important hidden information and features of the original time series log data and offers a precise framework for the analysis of input information. While neural network algorithm constitutes a powerfulnonlinear function approximation which can provide detection and prediction functions. The combination of the two techniques is based on the idea of using wavelet transform to denoise the log data by decomposing it into a set of coefficients, then feed the denoised data into a neural ...

Information Flow Under Budget Constraints, 2018 Lafayette College

#### Information Flow Under Budget Constraints, Pavel Naumov, Jia Tao

*Faculty Research and Reports*

Although first proposed in the database theory as properties of functional dependencies between attributes, Armstrong's axioms capture general principles of information flow by describing properties of dependencies between sets of pieces of information. This article generalizes Armstrong's axioms to a setting in which there is a cost associated with information. The proposed logical system captures general principles of dependencies between pieces of information constrained by a given budget.

Armstrong's Axioms And Navigation Strategies, 2018 Vassar College

#### Armstrong's Axioms And Navigation Strategies, Kaya Deuser, Pavel Naumov

*Faculty Research and Reports*

The paper investigates navigability with imperfect information. It shows that the properties of navigability with perfect recall are exactly those captured by Armstrong's axioms from database theory. If the assumption of perfect recall is omitted, then Armstrong's transitivity axiom is not valid, but it can be replaced by a weaker principle. The main technical results are soundness and completeness theorems for the logical systems describing properties of navigability with and without perfect recall.

Strategic Coalitions With Perfect Recall, 2018 Lafayette College

#### Strategic Coalitions With Perfect Recall, Pavel Naumov, Jia Tao

*Faculty Research and Reports*

The paper proposes a bimodal logic that describes an interplay between distributed knowledge modality and coalition know-how modality. Unlike other similar systems, the one proposed here assumes perfect recall by all agents. Perfect recall is captured in the system by a single axiom. The main technical results are the soundness and the completeness theorems for the proposed logical system.

Neighborhood Beautification Graph Layout Through Message Passing, 2018 Carnegie Mellon University

#### Neighborhood Beautification Graph Layout Through Message Passing, Severino F. Galan, Ole J. Mengshoel

*Ole J Mengshoel*

Randomized Routing On Fat-Trees, 2018 Loyola University Chicago

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

Universal Wormhole Routing, 2018 Loyola University Chicago

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

*Ronald Greenberg*

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

The Fat-Pyramid And Universal Parallel Computation Independent Of Wire Delay, 2018 Loyola University Chicago

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

Randomized Routing On Fat-Trees, 2018 Selected Works

#### 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*+lg*n*lglg*n*) with probability 1-*O*(1/*n*). The ...

Universal Wormhole Routing, 2018 Selected Works

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

Single-Layer Channel Routing And Placement With Single-Sided Nets, 2018 Selected Works

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

On The Difficulty Of Manhattan Channel Routing, 2018 Loyola University Chicago

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

Minimizing Channel Density With Movable Terminals, 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, 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, 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, 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 ...

Packet Routing In Networks With Long Wires, 2018 Loyola University Chicago

#### Packet Routing In Networks With Long Wires, Ronald I. Greenberg, Hyeong-Cheol Oh

*Ronald Greenberg*

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*((*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 account, and *d* is the ...