[+]Towards Generalizing Expert Programmers’ Suggestions for Novice Programmers
Novice programmers may lack the experience to recognize opportunities to either improve their code or apply unfamiliar programming constructs. Yet, these opportunities are often clear to an experienced programmer. We describe an exploratory study investigating 1) the potential value of the suggestions experienced programmers make to novice programmers and 2) the ways experienced programmers envision identifying other programs that would benefit from the same suggestion. The results of our study suggest that experienced programmers make suggestions that can introduce new programming constructs to novice programmers. The participants in our study most commonly made suggestions that improve the code quality of novice programs, rather than changing their output. Furthermore, experienced programmers could often state a simple heuristic rule to use in identifying other novice programs that would benefit from their suggestion. Participants were able to author the rules in pseudocode, mostly using combinations of iteration and comparison to find patterns of problematic code. However, based on a test implementation of a selected set of rules for these suggestions, we conclude that support for improving rules through review and community input will be valuable.
[+]An Algorithm for Triangulating Multiple 3D Polygons
We present an algorithm for obtaining a triangulation of multiple, non-planar 3D polygons. The output minimizes additive weights, such as the total triangle areas or the total dihedral angles between adjacent triangles. Our algorithm generalizes a classical method for optimally triangulating a single polygon. The key novelty is a mechanism for avoiding non-manifold outputs for two and more input polygons without compromising optimality. For better performance on real-world data, we also propose an approximate solution by feeding the algorithm with a reduced set of triangles. In particular, we demonstrate experimentally that the triangles in the Delaunay tetrahedralization of the polygon vertices offer a reasonable trade off between performance and optimality.
[+]OSC: A High-Throughput Operating System Classifier
Most critical security vulnerabilities depend on the OS. If a hacker finds a machine with a vulnerable OS, then he can attack the system. Network administrators can defend against OS-specific attacks if they can find vulnerable machines before hackers do, but physically checking or actively scanning a large network can take time and resources. This presentation describes a tool that can detect the OS of every machine communicating in a large network. Our tool combines SVMs and memoization to achieve high classification accuracy and throughput on both laboratory-generated and real-world traffic.
In computer vision, we use images to measure aspects of the real world. But, before we can reconstruct scene geometry or measure tree health, we first need to know some important information about the cameras that captured these images. What direction was the camera pointed? How zoomed in was the camera? How did the camera map the true scene colors onto the image? Many researchers have used different image cues, such as the sun position or image vanishing points, to estimate these characteristics.
This talk presents ongoing work to use the appearance of the sky as a camera calibration cue. We hope to recover many camera characteristics by comparing images of real skies to skies rendered using a state-of-the-art sky dome model. Specifically, we hope to estimate some subset of the camera pan, tilt, focal length, color response, image exposures, scene turbidites, and scene ground albedo for a stationary webcam.
Navigation is one of the fundamental tasks in mobile robotics. For robots with reasonable dynamics and operating speeds in indoor environments, efficient collision-free navigation is considered a solved problem from a practical standpoint. However, when humans are introduced into the environment, we must treat them differently than static obstacles by respecting their social norms, thus causing navigation to become more difficult.The focus of my research adds capabilities to the efficient reliable navigation algorithm that allow the robot to integrate additional contexts into the factors that influence the robot's path.
[+]Implicitly Batching Parallel Data Structure Operations
Sequential algorithms and data structures are typically easily composable; one can analyze the runtime of data structure operations and then plug them in to the algorithm analysis. However, concurrent data structures usually don't provide this composability - common techniques such as locking will destroy performance guarantees. Further, designing efficient concurrent data structures is quite complex. Parallel batch data structures can provide performance guarantees by processing groups of operations, limiting arbitrary accesses. Unfortunately, this technique often requires difficult or infeasible restructuring of an algorithm. This presentation describes BATCHER, a runtime scheduler that efficiently executes concurrent data structure operations and can be easily applied to existing algorithms. BATCHER requires only that the data structure include a batch operation that can perform a group of data structure operations. This batch operation need not deal with concurrent accesses, and the individual operations in the batch may or may not execute in parallel. BATCHER provides a provable runtime bound, and we are currently in the process of empirically evaluating its performance.
[+] Scalable Network Architecture in Virtual World Applications
Networked virtual worlds allow people living in different places to meet and interact online. In building a sophisticated virtual world where large numbers of users/objects can interact with each other at the same time, a central requirement is to guarantee the network performance in face of numerous dynamic objects, say, avatars. It is challenging to process large numbers of dynamic objects simultaneously, since the network bandwidth is limited and late object updates may hinder user experience. In this talk, I will present our network architecture for virtual world applications. We achieve scalability by having each host distribute its status updates over multicasts and by gossiping. Each host will subscribe to multicast groups based on location information, and we use coterie structures to reduce the length of the critical path between multicast groups. Analysis shows that our network architecture allows thousands of hosts communicate at the same time, with reasonable speed.
The gap between processing and storage speeds is a concern for system designers as well as application developers. This gap can be reduced by eliminating unnecessary stores, reducing the amount of memory traffic from first-level caches to slower components of memory. This reduction in writes has many benefits including increasing performance, saving power, as well as increasing endurance of memory components that may have limited write cycles. Techniques have been developed and evaluated for eliminating various classes of stores that can be silenced. A relatively unexplored class of such stores are stores of data that can no longer be reached by the program, or dead data. This data may be in cache and marked as needing to be written back.
In this work we explore a technique to discover dead data while it is in cache so that its bytes need not be written to higher levels of memory. The technique we propose is a variant of reference counting that finds a subset of these ''eternally silent'' (dead) stores. Our technique is applied to several popular benchmarks and shows that a significant fraction of writes to memory can be silenced by identifying and removing writes of data that is no longer reachable by the program.
In outdoor images, cast shadows define 3D constraints between the sun, the points casting a shadow, and the surfaces onto which shadows are cast. This cast shadow structure provides a powerful cue for 3D reconstruction, but requires that shadows are tracked over time, and this is difficult as shadows have minimal texture. Thus, we develop a tracking system that enforces geometric consistency across tracks that enforces each track to be consistent with the solar illumination direction and a single occluder. We show 3D reconstruction results on outdoor scenes, including some that show the 3D structure of occluders never directly observed by the camera.
[+] Cache-Conscious Scheduling of Streaming Pipelines in Parallel
Streaming programming models are seen as enablers of high performance computing though we find that cache-efficiency is rarely considered during their design due to the short life-span of data. This work focuses on the scheduling of a subset of streaming applications on a multi-processor systems in order to maximize overall cache-efficiency and throughput. A streaming pipeline is a special case of streaming application where computation modules are chained together via communication channels with special source and sink nodes at either end. Each time a module fires it consumes data from it's input channel and produces data on it's output channel. Our main observation is that there are two main causes for a streaming application to incur cache-misses: when loading in the state of a module and when a module is consuming and producing data on it's input and output channels. Our aim in this ongoing work is to determine a cache-efficient scheduling strategy for streaming pipelines and prove its optimality given constant-factor memory augmentation.
[+]Incorporating Emergency Alarms in Wireless Process Control
Recent years have witnessed significant interests in adopting wireless sensor-actuator networks in process control applications. Many real-world process control systems must handle various emergency alarms under stringent timing constraints in addition to regular feedback control loops. However, despite considerable theoretical studies on wireless and networked control, the problem of incorporating emergency alarms in process control has received little attention in the research community. This paper presents the first systematic study to integrate emergency alarms into wireless process control systems. We design a suite of wireless emergency communication protocols to support emergency control loops along side with regular control loops sharing a same wireless mesh network. We propose two transmission scheduling techniques (periodic server vs. slot stealing), and explore both periodic and event-driven emergency communication approaches. We then conduct a case study on a coupled water tank system controlled by both regular and emergency control loops over a wireless sensor-actuator network. Simulations based on realistic wireless conditions and network protocols demonstrate the feasibility of incorporating emergency alarms in wireless process control systems. The slot stealing protocol can effectively improve the sampling rate and latency of emergency control by stealing back time slots from regular control loops in case of emergencies, while event-driven emergency communication reduces the communication load in the network. By integrating emergency alarms in wireless control design and protocols, this work represents a promising step toward practical wireless process control systems.
[+]#OccupyGPU: Extracting parallelism to maximize GPU Occupancy
The rapid growth in availability of Graphics Processing Units (GPUs) for general-purpose computing has sparked an interest in mapping various algorithms to GPU architectures for high performance gains. Algorithms with regularized computation patterns have yielded the best results thus far, while consistent strategies for algorithms with irregular computation patterns or complex control structures remain elusive. In previous work, we have presented a DNA sequence aligner as a representative example of such an algorithm and shown how to exploit the parallelism of its regularized computational component. In this talk, we will present strategies for exposing the parallelism of its control and work management components, as well as opportunities to tune the granularity of parallelism of the various components.
[+]Understanding Variation in Queue Occupancy in Streaming Systems Given Noisy Environments
Stream compute systems often utilize queues between compute kernels within an application. Many queues can be fully analyzed using analytic or simulation models. Todays systems have multiple abstraction layers within the software stack. Most systems also have multiple processes running at any given moment in order to do routine house-keeping tasks. These factors combine to create a noisy, uncertain environment for determining the parameters of a model. This work leverages uncertainty analysis along with a characterization of workload variation to produce a probability distribution of a models' output response. We'll show how well this method works at both forecasting the reliability of a particular queueing model for a given system, and also how it can be used in conjunction with empirically measured output responses to verify that the system is operating as modeled.
Jonathan Beard is advised by
Roger D. Chamberlain.