Digital Commons Network^™

Pairing Software-Managed Caching With Decay Techniques To Balance Reliability And Static Power In Next-Generation Caches, Kelly Shaw, Margaret Martonosi

Department of Math & Statistics Technical Report Series

Since array structures represent well over half the area and transistors on-chip, maintaining their ability to scale is crucial for overall technology scaling. Shrinking transistor sizes are resulting in increased probabilities of single events causing single- and multi-bit upsets which require adoption of more complex and power hungry error detection and correction codes (ECC) in hardware. At the same time, SRAM leakage energy is increasing partly due to technology trends and partly due to the increasing number of transistors present.

This paper proposes and evaluates methods of reducing the static power requirements of caches, while also maintaining high reliability. In …

Self-Adaptive Scheduler Parameterization, Barry Lawson, Evgenia Smirni

Department of Math & Statistics Technical Report Series

High-end parallel systems present a tremendous research challenge on how to best allocate their resources to match dynamic workload characteristics and user habits that are often unique to each system. Although thoroughly investigated, job scheduling for production systems remains an inexact science, requiring significant experience and intuition from system administrators to properly configure batch schedulers. State-of-the-art schedulers provide many parameters for their configuration, but tuning these to optimize performance and to appropriately respond to the continuously varying characteristics of the workloads can be very difficult — the effects of different parameters and their interactions are often unintuitive.

In this paper, …

Creating And Modifying Dynamic Animation Sequences Using The Tgt_Toolkit, Ross Gore

Department of Math & Statistics Technical Report Series

Creating and modifying the dynamic animation sequences within the TGT_Toolkit is not for the faint of heart. This report contains advice, guidelines and refers to an example of how I went about constructing the dynamic animation sequences within the Linked Lists Tutorial. I have identified three major areas of that seem to be common to all dynamic animation sequences, but distinct from simply extending TGT_Slide as most other slides do; these areas are: dynamically creating animation configurations, providing "undo" and slide saving functionality and sequencing saved slides once they are properly configured. In these areas "slide saving" and "saved slides" …

Design And Implementation Of Interactive Tutorials For Data Structures, Ross Gore, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

The Tutorial Generation Toolkit (TGT) is a set of Java classes that supports authoring of interactive tutorial applications. This paper describes extensions to the capabilities of the TGT and several new tutorials aimed at the Data Structures course which were built using the toolkit.

An Examination Of Codewords With Optimal Merit Factor, Michael W. Cammarano, Anthony G. Kirilusha

Department of Math & Statistics Technical Report Series

We examine the codewords with best possible merit factor (minimum sum of squares of periodic autocorrelations) for a variety of lengths. Many different approaches were tried in an attempt to find construction methods for such codewords, or for codewords with good but non-optimal merit factors.

Integer Maxima In Power Envelopes Of Golay Codewords, Michael W. Cammarano, Meredith L. Walker

Department of Math & Statistics Technical Report Series

This paper examines the distribution of integer peaks amoung Golay cosets in Ζ_4. It will prove that the envelope power of at least one element of every Golay coset of Ζ₄ of length 2^m (for m-even) will have a maximum at exactly 2^m+1. Similarly it will be proven that one element of every Golay coset of Ζ₄ of length 2^m (for m-odd) will have a maximum at exactly 2^m+1. Observations and partial arguments will be made about why Golay cosets of Ζ₄ of length 2^{m …}

On Agent Communication In Large Groups, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

The problem is fundamental and natural, yet deep - to simulate the simplest possible form of communication that can occur within a large multi-agent system. It would be prohibitive to try and survey all of the research on "communication" in general so we must restrict our focus. We will devote our efforts to synthetic communication occurring within large groups. In particular, we would like to discover a model for communication that will serve as an abstract model, a prototype, for simulating communication within large groups of biological organisms.

Octary Codewords With Power Envelopes Of 3∗2M, Katherine M. Nieswand, Kara N. Wagner

Department of Math & Statistics Technical Report Series

This paper examines codewords of length 2^m in Z₈ with envelope power maxima of 3 ∗ 2^m. Using the general form for Golay pairs as a base, a general form is derived for the set of coset leaders that generate these codewords. From this general form it will be proven that there exists at least one element in the coset that achieves a power of 3 ∗ 2^m for each m-even and m-odd case.

The Set Of Hemispheres Containing A Closed Curve On The Sphere, Mary Kate Boggiano, Mark Desantis

Department of Math & Statistics Technical Report Series

Suppose you get in your car and take a drive on the sphere of radius R, so that when you return to your starting point the odometer indicates you've traveled less than 2πR. Does your path, γ, have to lie in some hemisphere?

This question was presented to us by Dr. Robert Foote of Wabash College. Previous authors chose two points, A and B, on γ such that these points divided γ into two arcs of equal length. Then they took the midpoint of the great circle arc joining A and B to be the North Pole and showed that …

Pseudocontinuations And The Backward Shift, Alexandru Aleman, Stefan Richter, William T. Ross

Department of Math & Statistics Technical Report Series

In this paper, we will examine the backward shift operator Lƒ = (ƒ – ƒ(0))/z on certain Banach spaces of analytic functions on the open unit disk D. In particular, for a (closed) subspace M for which LM ⊂ M, we wish to determine the spectrum, the point spectrum, and the approximate point spectrum of L|M. In order to do this, we will use the concept of "pseudocontinuation" of functions across the unit circle ∏.

Using The Quantum Computer To Break Elliptic Curve Cryptosystems, Jodie Eicher, Yaw Opoku

Department of Math & Statistics Technical Report Series

This article gives an introduction to Elliptic Curve Cryptography and Quantum Computing. It includes an analysis of Peter Shor’s algorithm for the quantum computer breakdown of Discrete Log Cryptosystems and an analog to Shor’s algorithm for Elliptic Curve Cryptosystems. An extended example is included which illustrates how this modified Shor’s algorithm will work.

On Quaternionic Pseudo-Random Number Generators, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

There is no dearth of published literature on the design, implementation, analysis, or use of pseudo-random number generators or PRNGs. For example, [6] [7] [14] and the references therein, provide a broad overview and firm grounding for the subject. This report complements and elaborates upon the work of McKeever [9], who investigated PRNGs constructed in a non-commutative setting with the target application being so-called cryptographically secure PRNGs as discussed in [12] or [13]. Novel "solutions" to the problem of designing cryptographically secure PRNGS continue to be proposed [1] [2] [10] [15], so despite the caution and skepticism required, the area …

Secure Trapdoor Hash Functions Based On Public-Key Cryptosystems, Gary R. Greenfield, Sarah Agnes Spence

Department of Math & Statistics Technical Report Series

In this paper we systematically consider examples representative of the various families of public-key cryptosystems to see if it would be possible to incorporate them into trapdoor hash functions, and we attempt to evaluate the resulting strengths and weaknesses of the functions we are able to construct. We are motivated by the following question:

Question 1.2 How likely is it that the discoverer of a heretofore unknown public-key cryptosystem could subvert it for use in a plausible secure trapdoor hash algorithm?

In subsequent sections, our investigations will lead to a variety of constructions and bring to light the non-adaptability of …

Dqdbsim User's Manual, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

DQDBsim is a simulation program for the study of the performance of the Distributed Queue Dual Bus (DQDB) Metropolitan Area Network. The simulation is based on the description of DQDB found in [Ins90]. Only the Queued Arbitrated (QA) service is modeled by DQDBsim the inclusion of Prearbitrated (PA) service is under consideration for inclusion in a future release. This document contains a description of the program instructions for its use details of the formats of input and data files and information on other programs that are used cooperatively with DQDBsim.

A Macro Extension For The Woody Assembly Language, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

We discuss an extension to the Woody Assembly Language [Cha94] which allows new instructions to be defined. The mechanism is similar to the C language's #define macros, allowing a name to be supplied for a piece of code which will be expanded in line. Provisions are made for writing new non-destructive branching instructions as well as instructions which are simply new names for commonly used bits of code.

Bergman Spaces On An Annulus And The Backward Bergman Shift, William T. Ross

Department of Math & Statistics Technical Report Series

In this paper, we will give a complete characterization of the invariant subspaces M (under ƒ → zƒ) of the Bergman space L^p_a(G), 1 < p < 2, G an annulus, which contain the constant function 1. As an application of this result, we will characterize the invariant subspaces of the adjoint of multiplication by z on the Dirichlet spaces D_q, q > 2, as well as the invariant subspaces of the backward Bergman shift ƒ → (ƒ – ƒ(0))/z on L^p_a(𝔻), 1 < p < 2.

Bergman Spaces On Disconnected Domains, Alexandru Aleman, Stefan Richter, William T. Ross

Department of Math & Statistics Technical Report Series

For a bounded region G ⊂ ℂ and a compact set K ⊂G , with area measure zero, we will characterize the invariant subspaces M (under ƒ → z ƒ) of the Bergman space L^p_a(G\K), 1 ≤ p < ∞, which contain L<sup>p_a(G) and with dim(M/(z-⋋)M) = 1 for all ⋋ ∈ G\K. When G\K is connected, we will see that dim(M/(z-⋋)M) = 1 for all ⋋ ∈ G\K and this in this case we will have a complete …

Netsim User's Manual, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

NetSim is a simulation program for the study of Local Area Network (LAN ) protocol performance. This document contains a description of the program instructions for its use details of the formats of input and data files and information on other programs that are used cooperatively with NetSim. Less verbose directions for using this program can be found in the UNIX main page netsim(1). This manual describes version 2.4 of the program.

A Topology-Aware Collision Resolution Algorithm, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

A new collision resolution algorithm called the Space Division Multiple Access protocol (SDMA) is presented. SDMA gains a performance advantage over similar protocols by using information about the positions of stations on the network. The protocol can operate asynchrononsly on a broadcast bus, allowing variable sized packet traffic. Through simulation the protocol is demonstrated to have better performance than Ethernet and the Capetanakis Tree protocol, a similar collision resolution protocol, under some traffic conditions. In particular, under heavy loads, SDMA displays better average throughput and lower variance of delay than Ethernet. The protocol demonstrates a performance bias based on the …

An Algorithmic Palette Tool, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Our algorithmic tool follows the model of RGB percentage curves, but now the control of these curves is though algorithms that indirectly, and more abstractly, create, evolve, and modify such curves. To fully explain our methods we must first introduce the topic "mutating expressions." This is done in Section Two. In Section Three we document the user-interface problems we dealt with, and finally in Section Four discuss conclusions and suggest ideas for future exploration. Before commencing with the technical details however, we wish to emphasize the nature of the "colorization" problem that led to the conception and development of our …

Merlin's Magic Square Enhanced, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

This paper first considers questions about games related to Merlin's Magic Square from the point of view of group actions. At this juncture, little beyond the formal model is new, but the exposition sets the stage for considering certain "enhanced" versions of these games. The analysis of enhanced games, with the aid of semigroup actions, is carried out in complete detail for an ostensibly simpler (k = 3) game before turning to a Merlin ( k = 4) game. Concluding sections discuss various ways to generalize our games.

To review the solution to Merlin's Magic Square, we begin by introducing …

Simulated Annealing And Optimal Codes, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Following standard notation, an (n, m, d) code C denotes a binary code C which has length n, size m, and Hamming distance d. According to Hill [6] the “main coding theory problem” is to optimize one of these three parameters when the other two are held fixed. The usual version of this optimization problem is to find the largest code for a given length and given minimum distance. This is the problem we shall consider, thus making it clear what we mean by an “optimal code.”

Graphical Evolution Experiments In Artificial Life, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

Larry Yaeger's alife simulation running on a Silicon Graphics Iris Workstation is called Poly World. Our description of PolyWorld is based on notes taken during an oral presentation and video demonstration given in the Artificial Life Panel Session of SIGGRAPH '92: In PolyWorld the visual organisms roam on a bounded two dimensional grid. The organisms "brains" are small neural nets enabling the organisms to control their external visual appearance and to perceive the external world by processing pixmaps. The simulation controls for total energy while striving to explore competition and self-organization. Genes present are for size, strength, maximum speed, mutation …

Netsim: A Network Performance Simulator, Lewis Barnett Iii

Department of Math & Statistics Technical Report Series

The performance of computer communication networks is often given only cursory treatment in undergraduate Networking or Computer Communication courses. A simulation package for the investigation of many aspects of Local Area Network (LAN) performance is introduced. Its use as a tool for allowing undergraduate Networking students to investigate the performance of a popular networking system is discussed.

On Uniform And Relative Distribution In The Brauer Group, Gary R. Greenfield

Department of Math & Statistics Technical Report Series

In this progress/technical report our objective is twofold. First, to formalize and expand upon remarks appearing in [7] concerning the relativization of the fundamental identity in the setting of the Brauer group of a ring, and second to exhibit a construction which shows how to interpret uniform distribution as a homological phenomenon.