Computer Sciences Commons^™

The Grace Programming Language Draft Specification Version 0.3.1261, Andrew P. Black, Kim B. Bruce, James Noble

Computer Science Faculty Publications and Presentations

This is a specification of the Grace Programming Language. This specification is notably incomplete, and everything is subject to change.

Knowledge Extraction From Survey Data Using Neural Networks, Khan Imran, Arun Kulkarni

Computer Science Faculty Publications and Presentations

Surveys are an important tool for researchers. It is increasingly important to develop powerful means for analyzing such data and to extract knowledge that could help in decision-making. Survey attributes are typically discrete data measured on a Likert scale. The process of classification becomes complex if the number of survey attributes is large. Another major issue in Likert-Scale data is the uniqueness of tuples. A large number of unique tuples may result in a large number of patterns. The main focus of this paper is to propose an efficient knowledge extraction method that can extract knowledge in terms of rules. …

A System For Bidirectional Robotic Pathfinding, Tesca Fitzgerald

Computer Science Faculty Publications and Presentations

The accuracy of an autonomous robot's intended navigation can be impacted by environmental factors affecting the robot's movement. When sophisticated localizing sensors cannot be used, it is important for a pathfinding algorithm to provide opportunities for landmark usage during route execution, while balancing the efficiency of that path. Although current pathfinding algorithms may be applicable, they often disfavor paths that balance accuracy and efficiency needs. I propose a bidirectional pathfinding algorithm to meet the accuracy and efficiency needs of autonomous, navigating robots.

Rsvp: Remote Sensing Visualization Platform For Data Fusion, Vanessa Gertman, Peter Olsoy, Nancy Glenn, Alark Joshi

Computer Science Faculty Publications and Presentations

Remote sensing involves the acquisition of data in terms of images, point clouds and so on. One of the major challenges with remote sensing datasets is managing and understanding the massive amounts of data that is collected. In many instances, scientists acquire data for the same region using varied sensing devices. Scientists would like to fuse and examine this data acquired from different sensing devices to further explore the region under investigation. Immersive visualization has emerged as an ideal solution for three-dimensional exploration of multimodal remote sensing data. The ability to manipulate data interactively in true 3D (using stereo) with …

Patterns As Objects In Grace, Andrew P. Black, Michael Homer, James Noble, David J. Pearce, Kim B. Bruce

Computer Science Faculty Publications and Presentations

Object orientation and pattern matching are often seen as conflicting approaches to program design. Object oriented programs place type-dependent behaviour inside objects and invoke it via dynamic dispatch, while pattern matching programs place type-dependent behaviour outside data structures and invoke it via multiway conditionals (case statements). Grace is a new, dynamic, object-oriented language designed to support teaching: to this end, Grace needs to support both styles. In this paper we explain how this conflict can be resolved gracefully: by modelling patterns and cases as partial functions, reifying those functions as first-class objects, and then building up complex patterns from simpler …

Parallel Sorting On A Spatial Computer, Max Orhai, Andrew P. Black

Computer Science Faculty Publications and Presentations

We describe a parallel sort for a spatial computer that requires minimal communication. We show simulations of the sort in 1 and 2 dimensions.

Presentation slides are located below in the Additional Files

An Overview Of Static Pipelining, Ian Finlayson, Gang-Ryung Uh, David Whalley, Gary Tyson

Computer Science Faculty Publications and Presentations

A new generation of mobile applications requires reduced energy consumption without sacrificing execution performance. In this paper, we propose to respond to these conflicting demands with an innovative statically pipelined processor supported by an optimizing compiler. The central idea of the approach is that the control during each cycle for each portion of the processor is explicitly represented in each instruction. Thus the pipelining is in effect statically determined by the compiler. The benefits of this approach include simpler hardware and that it allows the compiler to perform optimizations that are not possible on traditional architectures. The initial results indicate …

Assessing Metacognitive Skills Using Adaptive Neural Networks, Anderson Justin, Kouider Mokhtari, Arun Kulkarni

Computer Science Faculty Publications and Presentations

The assessment of student's levels of metacognitive knowledge and skills is critical in determining their ability to effectively perform complex cognitive tasks such as solving mathematics or reading comprehension problems. In this paper, we use an adaptive multiplayer perceptron model to categorize participants based on their metacognitive awareness and perceived use of reading strategies while reading. Eight hundred and sixty-five middle school students participated in the study. All participants completed a 30-item instrument- the Metacognitive Awareness-of-Reading Strategies Inventory (MARSI). We used adaptive multi-layer perceptron models to classify participants into three groups based on their metacognitive strategy awareness levels using thirteen …

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

Computer Science Faculty Publications and Presentations

Presentation focusing on software synchronization, thread locking, transactional memory, and relativistic programming. Hash table algorithms are presented with examples of relativistic list insertion and removal, and related data structures. Existing approaches are compared to new methodologies and future work with relativistic data structures.

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 …

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 …

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

Unified Framework For Development, Deployment And Robust Testing Of Neuroimaging Algorithms, Alark Joshi, Dustin Scheinost, Hirohito Okuda, Dominique Belhachemi, Isabella Murphy, Lawrence H. Staib, Xenophon Papademetris

Computer Science Faculty Publications and Presentations

Developing both graphical and commandline user interfaces for neuroimaging algorithms requires considerable effort. Neuroimaging algorithms can meet their potential only if they can be easily and frequently used by their intended users. Deployment of a large suite of such algorithms on multiple platforms requires consistency of user interface controls, consistent results across various platforms and thorough testing.

We present the design and implementation of a novel object-oriented framework that allows for rapid development of complex image analysis algorithms with many reusable components and the ability to easily add graphical user interface controls. Our framework also allows for simplified yet robust …

Improving Low Power Processor Efficiency With Static Pipelining, Ian Finlayson, Gang-Ryung Uh, David Whalley, Gary Tyson

Computer Science Faculty Publications and Presentations

A new generation of mobile applications requires reduced energy consumption without sacrificing execution performance. In this paper, we propose to respond to these conflicting demands with an innovative statically pipelined processor supported by an optimizing compiler. The central idea of the approach is that the control during each cycle for each portion of the processor is explicitly represented in each instruction. Thus the pipelining is in effect statically determined by the compiler. The benefits of this approach include simpler hardware and that it allows the compiler to perform optimizations that are not possible on traditional architectures. The initial results indicate …

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.

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 …

Water Quality Retrieval From Landsat Tm Imagery, Arun D. Kulkarni

Computer Science Faculty Publications and Presentations

In this paper, the utility of Landsat TM imagery for water quality studies in East Texas is investigated. Remote sensing has an important and effective role in water quality management. Remote sensing satellites measure the amount of solar radiation reflected by surface water and the reflectance of water depend upon the concentration and character of water quality parameters. Three water quality parameters namely the total suspended solids, chlorophyll-a, and turbidity are estimated in this study. In situ water quality parameter measurements from seven ground stations and the corresponding Landsat TM data were used to estimate the water quality parameters. Regression …

Energy-Efficient K-Coverage For Wireless Sensor Networks With Variable Sensing Radii, Jiong Wang, Sirisha Medidi, Muralidhar Medidi

Computer Science Faculty Publications and Presentations

Wireless Sensor Networks (WSNs) consist of spatially-distributed autonomous sensors that can cooperatively monitor physical and environmental conditions. Because of sensors’ resource-constraints in terms of size, power, and bandwidth, one of the fundamental objectives in WSNs is improving energy-efficiency. In this paper, utilizing sensors with variable sensing radii, we propose a group-based technique to obtain energy-efficient k-coverage based on our previous work with the Delaunay-Triangulation-based 1-coverage algorithm. Our sensing-radii optimization technique ensures full coverage and attains nearly-optimal energy consumption in sensing. Furthermore, our ns-2 simulations confirm that the group-based k-coverage reduces sensing energy consumption and maintains a …

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.

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

Is Parallel Programming Hard, And If So, Why?, Paul E. Mckenney, Maged M. Michael, Manish Gupta, Philip William Howard, Josh Triplett, Jonathan Walpole

Computer Science Faculty Publications and Presentations

Of the 200+ parallel-programming languages and environments created in the 1990s, almost all are now defunct. Given that parallel systems are now well within the budget of the typical hobbyist or graduate student, it is not unreasonable to expect a new cohort in excess of several thousand parallel languages and environments to appear in the 2010s. If this expected new cohort is to have more practical impact than did its 1990s counterpart, a robust and widely applicable framework will be required that encompasses exactly what, if anything, is hard about parallel programming. This paper revisits the fundamental precepts of concurrent …