Computer Sciences Commons^™

Resizable, Scalable, Concurrent Hash Tables, Josh Triplett, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present algorithms for shrinking and expanding a hash table while allowing concurrent, wait-free, linearly scalable lookups. These resize algorithms allow the hash table to maintain constant-time performance as the number of entries grows, and reclaim memory as the number of entries decreases, without delaying or disrupting readers.

We implemented our algorithms in the Linux kernel, to test their performance and scalability. Benchmarks show lookup scalability improved 125x over readerwriter locking, and 56% over the current state-of-the-art for Linux, with no performance degradation for lookups during a resize.

To achieve this performance, this hash table implementation uses a new concurrent …

Embedding Parallel Computation In A Stochastic Mesh Network: A Morphogenetic Approach, Max Orhai

Anthós

Many basic techniques in computer science have been founded on the assumption that physical computing resources are scarce but orderly, and that the cost of effective direct communication between physically distant parts of a computer system is affordable. In ubiquitous computing systems such as sensor networks, or in the design of nano-scale systems, these familiar assumptions may not hold.

What if we suppose instead that computing capacity is plentiful, but that only local communication is possible, and the exact structure of the communication network is not known in advance? This is the domain of spatial programming.

How can we program …

Hardware Acceleration Of Inference Computing: The Numenta Htm Algorithm, Dan Hammerstrom

Systems Science Friday Noon Seminar Series

In this presentation I will describe the latest version of the Numenta HTM Cortical Learning Algorithm and why it is interesting for doing research into radical new computer architectures. Then I will discuss the hardware acceleration research we are doing, and briefly look at some preliminary applications development.

A Relativistic Enhancement To Software Transactional Memory, Philip William Howard, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Relativistic Programming is a technique that allows low overhead, linearly-scalable concurrent reads. It also allows joint access parallelism between readers and a writer. Unfortunately, it has so far been limited to a single writer so it does not scale on the write side. Software Transactional Memory (STM) is a technique that allows programs to take advantage of disjoint access parallelism on both the read-side and write-side. Unfortunately, STM systems have a higher overhead than many other synchronization mechanisms so although STM scales, STM starts from a lower baseline. We propose combining relativistic programming and software transactional memory in a way …

Higher-Level Application Of Adaptive Dynamic Programming/Reinforcement Learning – A Next Phase For Controls And System Identification?, George G. Lendaris

Systems Science Friday Noon Seminar Series

Humans have the ability to make use of experience while performing system identification and selecting control actions for changing situations. In contrast to current technological implementations that slow down as more knowledge is stored, as more experience is gained, human processing speeds up and has enhanced effectiveness. An emerging experience-based (“higher level”) approach promises to endow our technology with enhanced efficiency and effectiveness.

The notions of context and context discernment are important to understanding this human ability. These are defined as appropriate to controls and system-identification. Some general background on controls, Dynamic Programming, and Adaptive Critic leading to Adaptive Dynamic …

Scalable Correct Memory Ordering Via Relativistic Programming, Josh Triplett, Philip William Howard, Paul E. Mckenney, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We propose and document a new concurrent programming model, relativistic programming. This model allows readers to run concurrently with writers, without blocking or using expensive synchronization. Relativistic programming builds on existing synchronization primitives that allow writers to wait for current readers to finish with minimal reader overhead. Our methodology models data structures as graphs, and reader algorithms as traversals of these graphs; from this foundation we show how writers can implement arbitrarily strong ordering guarantees for the visibility of their writes, up to and including total ordering.

Generalized Construction Of Scalable Concurrent Data Structures Via Relativistic Programming, Josh Triplett, Paul E. Mckenney, Philip W. Howard, Jonathan Walpole

Computer Science Faculty Publications and Presentations

We present relativistic programming, a concurrent programming model based on shared addressing, which supports efficient, scalable operation on either uniform shared-memory or distributed shared- memory systems. Relativistic programming provides a strong causal ordering property, allowing a series of read operations to appear as an atomic transaction that occurs entirely between two ordered write operations. This preserves the simple immutable-memory programming model available via mutual exclusion or transactional memory. Furthermore, relativistic programming provides joint-access parallelism, allowing readers to run concurrently with a writer on the same data. We demonstrate a generalized construction technique for concurrent data structures based on relativistic programming, …

A Comparison Of Relativistic And Reader-Writer Locking Approaches To Shared Data Access, Philip William Howard, Josh Triplett, Jonathan Walpole

Computer Science Faculty Publications and Presentations

This paper explores the relationship between reader-writer locking and relativistic programming approaches to managing accesses to shared data. It demonstrates that by placing certain restrictions on writers, relativistic programming allows more concurrency than reader-writer locking while still providing the same isolation guarantees. Relativistic programming also allows for a straightforward model for reasoning about the correctness of programs that allow concurrent read-write accesses.

On The Effect Of Criticality And Topology On Learning In Random Boolean Networks, Alireza Goudarzi

Systems Science Friday Noon Seminar Series

Random Boolean networks (RBN) are discrete dynamical systems composed of N automata with a binary state, each of which interacts with other automata in the network. RBNs were originally introduced as simplified models of gene regulation. In this presentation, I will present recent work done conjointly with Natali Gulbahce (UCSF), Thimo Rohlf (MPI, CNRS), and Christof Teuscher (PSU). We extend the study of learning in feedforward Boolean networks to random Boolean networks (RBNs) and systematically explore the relationship between the learning capability, the network topology, the system size N, the training sample T, and the complexity of the computational task. …

Haskell For The Cloud, Andrew P. Black

Computer Science Faculty Publications and Presentations

We present Cloud Haskell, a domain specific language for developing programs for a distributed-memory computing environment. Implemented as a shallow embedding in Haskell, it provides a message-passing communication model, inspired by Erlang, without introducing incompatibility with Haskell's established sharedmemory concurrency. A key contribution is a method for serializing function closures for transmission across the network. Cloud Haskell has been implemented; we present example code and some preliminary performance measurements.

Relativistic Red-Black Trees, Philip William Howard, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Operating system performance and scalability on sharedmemory many-core systems depends critically on efficient access to shared data structures. Scalability has proven difficult to achieve for many data structures. In this paper we present a novel and highly scalable concurrent red-black tree. Red-black trees are widely used in operating systems, but typically exhibit poor scalability. Our red-black tree has linear read scalability, uncontended read performance that is at least 25% faster than other known approaches, and deterministic lookup times for a given tree size, making it suitable for realtime applications.

The Ordering Requirements Of Relativistic And Reader-Writer Locking Approaches To Shared Data Access, Philip William Howard, Josh Triplett, Jonathan Walpole, Paul E. Mckenney

Computer Science Faculty Publications and Presentations

The semantics of reader-writer locks allow read-side concurrency. Unfortunately, the locking primitives serialize access to the lock variable to an extent that little or no concurrency is realized in practice for small critical sections. Relativistic programming is a methodology that also allows read- side concurrency. Relativistic programming uses dfferent ordering constraints than reader-writer locking. The different ordering constraints allow relativistic readers to proceed without synchronization so relativistic readers scale even for very short critical sections. In this paper we explore the diferences between the ordering constraints for reader-writer locking and relativistic programs. We show how and why the dfferent ordering …

Finding Haystacks With Needles: Ranked Search For Data Using Geospatial And Temporal Characteristics, Veronika Margaret Megler, David Maier

Computer Science Faculty Publications and Presentations

The past decade has seen an explosion in the number and types of environmental sensors deployed, many of which provide a continuous stream of observations. Each individual observation consists of one or more sensor measurements, a geographic location, and a time. With billions of historical observations stored in diverse databases and in thousands of datasets, scientists have difficulty finding relevant observations. We present an approach that creates consistent geospatial-temporal metadata from large repositories of diverse data by blending curated and automated extracts. We describe a novel query method over this metadata that returns ranked search results to a query with …

Can Transportation Researchers Reuse Project Datasets And Programs?, Tyler Hayes, Lois Delcambre, Leonard Shapiro

Computer Science Faculty Publications and Presentations

Data users involved in research and analysis typically invest a lot of eort cleaning and manipu- lating their data as they work. Based on this observation, we have investigated two hypotheses: 1) reuse of datasets and procedures is difficult, and 2) the inability to reuse datasets and procedures is primarily due to a lack of documentation. To test these hypotheses we conducted structured interviews with data users asking questions regarding the struggles in their work pertaining to data, their documentation habits, and the importance of documentation. The interviews revealed that the data users rarely reused data or procedures, frequently encountered …

System Dynamics Modeling As A Potentially Useful Tool In Analyzing Mitigation Strategies To Reduce Overdose Deaths Associated With Pharmaceutical Opioid Treatment Of Chronic Pain, Wayne Wakeland, Teresa D. Schmidt, Aaron Gilson, J. David Haddox, Lynn Webster

Complex Systems Faculty Publications and Presentations

Objective. To illustrate a system-level, simulationbased approach for evaluating mitigation strategies to address the dramatic rise in abuse, addiction, and overdose deaths associated with the use of pharmaceutical opioid analgesics to treat chronic pain.

Simulated Interventions. Making available drug formulations with increased tamper-resistance, prescriber education programs, and programs that reduce rates of medical user-related abuse and addiction.

Simulated Outcome Measure. Number of overdose deaths of medical users of pharmaceutical opioid analgesics, including those who abuse or have become addicted.

Methods. A demonstration system dynamics model is developed, tested, and used to evaluate the impact of candidate mitigation strategies on the …

Floorplan Design And Yield Enhancement Of 3-D Integrated Circuits, Rajeev Kumar Nain

Dissertations and Theses

We have developed a placement-aware 3-D floorplanning algorithm that enables additional wirelength reduction by planning for 3-D placement of logic gates in selected circuit modules during the floorplanning stage. Thus it also bridges the existing gap between 3-D floorplanning and 3-D placement. To reduce the solution space of 3-D floorplanning which is known to be an NP-hard problem, we derive a set of feasibility conditions on the topological representation of a floorplan. In addition, we have designed a fast module packing algorithm that satisfies a set of constraints for placement-aware 3-D floorplanning. Furthermore, we have designed an efficient evolutionary algorithm …

Random Automata Networks: Why Playing Dice Is Not A Vice, Christof Teuscher

Systems Science Friday Noon Seminar Series

Random automata networks consist of a set of simple compute nodes interacting with each other. In this generic model, one or multiple model parameters, such as the the node interactions and/or the compute functions, are chosen at random. Random Boolean Networks (RBNs) are a particular case of discrete dynamical automata networks where both time and states are discrete. While traditional RBNs are generally credited to Stuart Kauffman (1969), who introduced them as simplified models of gene regulation, Alan Turing proposed unorganized machines as early as 1948. In this talk I will start with Alan Turing's early work on unorganized machines, …

Biologically Inspired Computing: The Darpa Synapse Program & The Hierarchical Temporal Memory, Dan Hammerstrom

Systems Science Friday Noon Seminar Series

This presentation provides an update on biologically inspired computation. In particular, it focuses on two important developments in this area, the DARPA SyNAPSE program (Systems of Neuromorphic Adaptive Plastic Scalable Electronics) and the HTM (Hierarchical Temporal Memory) being developed by Numenta.

The SyNAPSE Program’s ultimate goal is to build a low-power, compact electronic chip combining novel analog circuit design and a neuroscience-inspired architecture that can address a wide range of cognitive abilities: perception, planning, decision making and motor control. According to DARPA program manager Todd Hylton, “Our research progress in this area is unprecedented, No suitable electronic synaptic device that …

Understanding Classification Decisions For Object Detection, Will Landecker, Michael David Thomure, Melanie Mitchell

Systems Science Friday Noon Seminar Series

Computer vision systems are traditionally tested in the object detection paradigm. In these experiments, a vision system is asked whether or not a specific object--for example an animal--occurs in a given image. A system that often answers correctly is said to be very accurate. In this talk, we will discuss some ambiguity that exists in this measure of accuracy. We will also propose a new measure of object-detection accuracy that addresses some of this ambiguity, and apply this measure to the hierarchical "standard model" of visual cortex.

Segmentation Of Thermographic Images Of Hands Using A Genetic Algorithm, Payel Ghosh, Judith Gold, Melanie Mitchell

Computer Science Faculty Publications and Presentations

This paper presents a new technique for segmenting thermographic images using a genetic algorithm (GA). The individuals of the GA also known as chromosomes consist of a sequence of parameters of a level set function. Each chromosome represents a unique segmenting contour. An initial population of segmenting contours is generated based on the learned variation of the level set parameters from training images. Each segmenting contour (an individual) is evaluated for its fitness based on the texture of the region it encloses. The fittest individuals are allowed to propagate to future generations of the GA run using selection, crossover and …

Solving Continuous Linear Least-Squares Problems By Iterated Projection, Ralf Juengling

Computer Science Faculty Publications and Presentations

I present a new divide-and-conquer algorithm for solving continuous linear least-squares problems. The method is applicable when the column space of the linear system relating data to model parameters is “translation invariant”. The central operation is a matrix- vector product, which makes the method very easy to implement. Secondly, the structure of the computation suggests a straightforward parallel implementation.

A complexity analysis for sequential implementation shows that the method has the same asymptotic complexity as well-known algorithms for discrete linear least-squares. For illustration we work out the details for the problem of fitting quadratic bivariate polyno- mials to a piecewise …

Pvw: Designing Virtual World Server Infrastructure, Francis Chang, C. Mic Bowman, Wu-Chi Feng

Computer Science Faculty Publications and Presentations

This paper presents a high level overview of PVW (Partitioned Virtual Worlds), a distributed system architecture for the management of virtual worlds. PVW is designed to support arbitrarily large and complex virtual worlds while accommodating dynamic and highly variable user population and content distribution density. The PVW approach enables the task of simulating and managing the virtual world to be distributed over many servers by spatially partitioning the environment into a hierarchical structure. This structure is useful both for balancing the simulation load across many nodes, as well as features such as geometric simplification and distribution of dynamic content.

Xpu: A Distributed Architecture For Metaverses, Francis Chang, C. Mic Bowman, Wu-Chi Feng

Computer Science Faculty Publications and Presentations

A significant problem of designing 3D virtual worlds (such as metaverses) is developing a scalable architecture that can manage millions of simultaneous users in an interactive 3D environment. This paper presents XPU (Extremely Partitioned Universe), a hierarchical client-server architecture for developing highly scalable metaverses. This design addresses the problem of dynamically partitioning the world to manage network and computing resources.

Scalable Event Tracking On High-End Parallel Systems, Kathryn Marie Mohror

Dissertations and Theses

Accurate performance analysis of high end systems requires event-based traces to correctly identify the root cause of a number of the complex performance problems that arise on these highly parallel systems. These high-end architectures contain tens to hundreds of thousands of processors, pushing application scalability challenges to new heights. Unfortunately, the collection of event-based data presents scalability challenges itself: the large volume of collected data increases tool overhead, and results in data files that are difficult to store and analyze. Our solution to these problems is a new measurement technique called trace profiling that collects the information needed to diagnose …

Towards Robot Theatre, Marek Perkowski

Systems Science Friday Noon Seminar Series

The talk will present the idea of futuristic robot theatre and work done towards it at the Intelligent Robotics Laboratory, Department of Electrical and Computer Engineering at PSU. After a short history of robot theatre from antiquity until 2008 we will present recent work on robot theatre in the world and at PSU, including two plays: ancient Korean folk tale "Hahoe Pylyshin" and "What's that? A Schroedinger Cat" or a debate between Einstein and Schroedinger Cat about quantum mechanics - an educational theatre. Several models of robot theatre will be discussed: animatronic theatre, interactive theatre and improvisational theatre. We will …

Holism And Human History, Martin Zwick

Complex Systems Faculty Publications and Presentations

This paper uses a systems-theoretic model to structure an account of human history. According to the model, a process, after its beginning and early development, often reaches a critical stage where it encounters some limitation. If the limitation is overcome, development does not face a comparable challenge until a second critical juncture is reached, where obstacles to further advance are more severe. At the first juncture, continued development requires some complexity-managing innovation; at the second, it needs some event of systemic integration in which the old organizing principle of the process is replaced by a new principle. Overcoming the first …

Operational Verification Of A Relativistic Program, Robert T. Bauer

Computer Science Faculty Publications and Presentations

Engineering eorts to achieve scalable multiprocessor perfor- mance for concurrent reader-writer programs have resulted in a family of algorithms that are non-blocking and that tolerate interprocessor in- terference. Because these algorithms accept a unique frame of reference for each processor's accesses to memory, they typify a concurrent pro- gramming technique for shared memory multicore architectures called relativistic programmming.

Rigorous verification of these algorithms is not possible with existing semantic based approaches because the semantics under approximates multiprocessor behavior and the algorithms rely on abstruse interactions with the operating system that aren't reconciled with language seman- tics.

The Read-Copy Update (RCU) …

The Design And Implementation Of A Safe, Lightweight Haskell Compiler, Timothy Jan Chevalier

Computer Science Faculty Publications and Presentations

Typed programming languages offer safety guarantees that help programmers write correct code, but typical language implementations offer no proof that source-level guarantees extend to executable code. Moreover, typical implementations link programs with unsafe runtime system (RTS) code. I present a compiler for the functional language Haskell that preserves some of the properties of Haskell’s type system. The soundness proof for the combination of the compiler and a verified RTS requires a proof that the compiler emits code that cooperates correctly with the RTS. In particular, the latter proof must address the boundary between the user program and the garbage collector. …

A Framework For Superimposed Applications : Techniques To Represent, Access, Transform, And Interchange Bi-Level Information, Sudarshan Srivivasa Murthy

Dissertations and Theses

Superimposed applications (SAs) superimpose (that is, overlay) new information and structures (such as annotations) on parts (such as sub-documents) of existing base information (BI). In this setting, SA developers and users work with bi-level information, a combination of the superimposed information and the referenced BI parts.

We have designed a framework to assist SAs in the following bi-level-information-management activities: representation, access, transformation, and interchange. This framework defines the abstraction context agent to activate any BI part and to retrieve information from the context of the part. It includes means to represent and access bi-level information in a conceptual model (the …

Reconstructability Analysis In Biomedical Research, Martin Zwick

Complex Systems Faculty Publications and Presentations

This talk explains reconstructability analysis (RA), a graphical modeling methodology based in information theory & graph theory which overlaps more familiar machine learning & statistical methods such as log-linear models & Bayesian networks. The talk reports on the use of RA in a recent bioinformatics study of human gene (SNP) - disease (diabetes) association & epistasis & in some other biomedical applications of RA.

Keywords: Reconstructability Analysis, biomedical research, bioinformatics, categorical data, multivariate statistics, exploratory modeling, confirmatory modeling