Computer Engineering Commons^™

Computational Geometry Teaching Tool, Yujie Zhou, Tao Ju

All Computer Science and Engineering Research

When students are taking Computational Geometry course which covers many geometry algorithms, most of them are difficult to follow because these algorithms are very abstract even if authors draw pictures to illustrate. In order to help students to get a better understanding of these algorithms, we decide to design Computational Geometry Teaching Tool. This tool is a web application that covers 8 geometry algorithms : Graham Scan, Quick Hull, Line Segment Intersection, Dual, Line Arrangement, Voronoi Diagram, Incremental Delaunay Triangulation and Kd Tree. First, this tool is developed by using JavaScript so that users don't need to install any software …

Nanopower Analog Frontends For Cyber-Physical Systems, Kenji Aono

McKelvey School of Engineering Theses & Dissertations

In a world that is increasingly dominated by advances made in digital systems, this work will explore the exploiting of naturally occurring physical phenomena to pave the way towards a self-powered sensor for Cyber-Physical Systems (CPS). In general, a sensor frontend can be broken up into a handful of basic stages: transduction, filtering, energy conversion, measurement, and interfacing. One analog artifact that was investigated for filtering was the physical phenomenon of hysteresis induced in current-mode biquads driven near or at their saturation limit. Known as jump resonance, this analog construct facilitates a higher quality factor to be brought about without …

Decoupling Information And Connectivity Via Information-Centric Transport, Hila Ben Abraham, Jyoti Parwatikar, John Dehart, Adam Drescher, Patrick Crowley

Computer Science and Engineering Publications and Presentations

The power of Information-Centric Networking (ICN) architectures lies in their abstraction for communication --- the request for named data. This abstraction promises that applications can choose to operate only in the information plane, agnostic to the mechanisms implemented in the connectivity plane. However, despite this powerful promise, the information and connectivity planes are presently coupled in today's incarnations of leading ICNs by a core architectural component, the forwarding strategy. Presently, this component is not sustainable: it implements both the information and connectivity mechanisms without specifying who should choose a forwarding strategy --- an application developer or the network operator. In …

Self-Powered Time-Keeping And Time-Of-Occurrence Sensing, Liang Zhou

McKelvey School of Engineering Theses & Dissertations

Self-powered and passive Internet-of-Things (IoT) devices (e.g. RFID tags, financial assets, wireless sensors and surface-mount devices) have been widely deployed in our everyday and industrial applications. While diverse functionalities have been implemented in passive systems, the lack of a reference clock limits the design space of such devices used for applications such as time-stamping sensing, recording and dynamic authentication. Self-powered time-keeping in passive systems has been challenging because they do not have access to continuous power sources. While energy transducers can harvest power from ambient environment, the intermittent power cannot support continuous operation for reference clocks. The thesis of this …

Security Services Using Blockchains: A State Of The Art Survey, Maeda Zolanvari, Aiman Erbad, Raj Jain, Mohammed Samaka

All Computer Science and Engineering Research

This article surveys blockchain-based approaches for several security services. These services include authentication, confidentiality, privacy and access control list (ACL), data and resource provenance, and integrity assurance. All these services are critical for the current distributed applications, especially due to the large amount of data being processed over the networks and the use of cloud computing. Authentication ensures that the user is who he/she claims to be. Confidentiality guarantees that data cannot be read by unauthorized users. Privacy provides the users the ability to control who can access their data. Provenance allows an efficient tracking of the data and resources …

Development Of Scalable Simulator For Spiking Neural Network, Jae Sang Ha

McKelvey School of Engineering Theses & Dissertations

A neural network simulator for Spiking Neural Network (SNN) is a useful research tool to model brain functions with a computer. With this tool, different parameters can be explored easily compared to using a real brain. For several decades, researchers have developed many software packages and simulators to accelerate research in computational neuroscience. However, despite their advantages, different neural simulators possess different limitations, such as flexibility of choosing different neuron models and scalability of simulators for large numbers of neurons. This paper demonstrates an efficient and scalable spiking neural simulator that is based on growth transform neurons and runs on …

Bio-Inspired Multi-Spectral And Polarization Imaging Sensors For Image-Guided Surgery, Nimrod Missael Garcia

McKelvey School of Engineering Theses & Dissertations

Image-guided surgery (IGS) can enhance cancer treatment by decreasing, and ideally eliminating, positive tumor margins and iatrogenic damage to healthy tissue. Current state-of-the-art near-infrared fluorescence imaging systems are bulky, costly, lack sensitivity under surgical illumination, and lack co-registration accuracy between multimodal images. As a result, an overwhelming majority of physicians still rely on their unaided eyes and palpation as the primary sensing modalities to distinguish cancerous from healthy tissue. In my thesis, I have addressed these challenges in IGC by mimicking the visual systems of several animals to construct low power, compact and highly sensitive multi-spectral and color-polarization sensors. I …

Easier Parallel Programming With Provably-Efficient Runtime Schedulers, Robert Utterback

McKelvey School of Engineering Theses & Dissertations

Over the past decade processor manufacturers have pivoted from increasing uniprocessor performance to multicore architectures. However, utilizing this computational power has proved challenging for software developers. Many concurrency platforms and languages have emerged to address parallel programming challenges, yet writing correct and performant parallel code retains a reputation of being one of the hardest tasks a programmer can undertake.

This dissertation will study how runtime scheduling systems can be used to make parallel programming easier. We address the difficulty in writing parallel data structures, automatically finding shared memory bugs, and reproducing non-deterministic synchronization bugs. Each of the systems presented depends …

Parallel Real-Time Scheduling For Latency-Critical Applications, Jing Li

McKelvey School of Engineering Theses & Dissertations

In order to provide safety guarantees or quality of service guarantees, many of today's systems consist of latency-critical applications, e.g. applications with timing constraints. The problem of scheduling multiple latency-critical jobs on a multiprocessor or multicore machine has been extensively studied for sequential (non-parallizable) jobs and different system models and different objectives have been considered. However, the computational requirement of a single job is still limited by the capacity of a single core. To provide increasingly complex functionalities of applications and to complete their higher computational demands within the same or even more stringent timing constraints, we must exploit the …

Efficiently And Transparently Maintaining High Simd Occupancy In The Presence Of Wavefront Irregularity, Stephen V. Cole

McKelvey School of Engineering Theses & Dissertations

Demand is increasing for high throughput processing of irregular streaming applications; examples of such applications from scientific and engineering domains include biological sequence alignment, network packet filtering, automated face detection, and big graph algorithms. With wide SIMD, lightweight threads, and low-cost thread-context switching, wide-SIMD architectures such as GPUs allow considerable flexibility in the way application work is assigned to threads. However, irregular applications are challenging to map efficiently onto wide SIMD because data-dependent filtering or replication of items creates an unpredictable data wavefront of items ready for further processing. Straightforward implementations of irregular applications on a wide-SIMD architecture are prone …

Decoupling Information And Connectivity In Information-Centric Networking, Hila Ben Abraham, Jyoti Parwatikar, John Dehart, Adam Drescher, Patrick Crowley

All Computer Science and Engineering Research

This paper introduces and demonstrates the concept of Information-Centric Transport as a mechanism for cleanly decoupling the information plane from the connectivity plane in Information-Centric Networking (ICN) architectures, such as NDN and CICN. These are coupled in today's incarnations of NDN and CICN through the use of forwarding strategy, which is the architectural component for deciding how to forward packets in the presence of either multiple next-hop options or dynamic feedback. As presently designed, forwarding strategy is not sustainable: application developers can only confidently specify strategy if they understand connectivity details, while network node operators can only confidently assign strategies …

Underwater Celestial Navigation Using The Polarization Of Light Fields, Samuel Bear Powell

McKelvey School of Engineering Theses & Dissertations

Global-scale underwater navigation presents challenges that modern technology has not solved. Current technologies drift and accumulate errors over time (inertial measurement), are accurate but short-distance (acoustic), or do not sufficiently penetrate the air-water interface (radio and GPS). To address these issues, I have developed a new mode of underwater navigation based on the passive observation of patterns in the polarization of in-water light. These patterns can be used to infer the sun__s relative position, which enables the use of celestial navigation in the underwater environment. I have developed an underwater polarization video camera based on a bio-inspired polarization image sensor …

Multipath And Rate Stability, Junjie Liu, Roch A. Guérin

All Computer Science and Engineering Research

Originally Published In Proc. IEEE Globecom Conference - CQRM: Communication QoS, Reliability & Modeling Symposium

Learning In The Real World: Constraints On Cost, Space, And Privacy, Matt J. Kusner

McKelvey School of Engineering Theses & Dissertations

The sheer demand for machine learning in fields as varied as: healthcare, web-search ranking, factory automation, collision prediction, spam filtering, and many others, frequently outpaces the intended use-case of machine learning models. In fact, a growing number of companies hire machine learning researchers to rectify this very problem: to tailor and/or design new state-of-the-art models to the setting at hand.

However, we can generalize a large set of the machine learning problems encountered in practical settings into three categories: cost, space, and privacy. The first category (cost) considers problems that need to balance the accuracy of a machine learning model …

In-Network Retransmissions In Named Data Networking, Hila Ben Abraham, Patrick Crowley

All Computer Science and Engineering Research

The strategy layer is an important architectural component in both Content-Centric Networking (CCN) and Named Data Networking (NDN). This component introduces a new forwarding model that allows an application to configure its namespace with a forwarding strategy. A core mechanism in every forwarding strategy is the decision of whether to retransmit an unsatisfied Interest or to wait for an application retransmission. While some applications request control of all retransmissions, others rely on the assumption that the strategy will retransmit an Interest when it is not satisfied. Although an application can select the forwarding strategy used in the local host, it …

Mercator (Mapping Enumerator For Cuda) User's Manual, Stephen V. Cole, Jeremy Buhler

All Computer Science and Engineering Research

Welcome to the MERCATOR user's manual! MERCATOR is a CUDA/C++ system designed to assist you in writing efficient CUDA applications by automatically generating significant portions of the GPU-side application code. We hope you find it helpful; please feel free to contact the authors with any questions or feedback.

Grafalgo - A Library Of Graph Algorithms And Supporting Data Structures (Revised), Jonathan Turner

All Computer Science and Engineering Research

This report provides an (updated) overview of Grafalgo, an open-source library of graph algorithms and the data structures used to implement them. The programs in this library were originally written to support a graduate class in advanced data structures and algorithms at Washington University. Because the code's primary purpose was pedagogical, it was written to be as straightforward as possible, while still being highly efficient. Grafalgo is implemented in C++ and incorporates some features of C++11. The library is available on an open-source basis and may be downloaded from https://code.google.com/p/grafalgo/. Source code documentation is at www.arl.wustl.edu/~jst/doc/grafalgo.

Locality-Aware Dynamic Task Graph Scheduling, Jordyn Maglalang, Sriram Krishnamoorthy, Kunal Agrawal

All Computer Science and Engineering Research

Dynamic task graph schedulers automatically balance work across processor cores by scheduling tasks among available threads while preserving dependences. In this paper, we design NabbitC, a provably efficient dynamic task graph scheduler that accounts for data locality on NUMA systems. NabbitC allows users to assign a color to each task representing the location (e.g., a processor core) that has the most efficient access to data needed during that node’s execution. NabbitC then automatically adjusts the scheduling so as to preferentially execute each node at the location that matches its color—leading to better locality because the node is likely to make …

Faster Maximium Priority Matchings In Bipartite Graphs, Jonathan Turner

All Computer Science and Engineering Research

A maximum priority matching is a matching in an undirected graph that maximizes a priority score defined with respect to given vertex priorities. An earlier paper showed how to find maximum priority matchings in unweighted graphs. This paper describes an algorithm for bipartite graphs that is faster when the number of distinct priority classes is limited. For graphs with k distinct priority classes it runs in O(kmn1/2) time, where n is the number of vertices in the graph and m is the number of edges.

The Bounded Edge Coloring Problem And Offline Crossbar Scheduling, Jonathan Turner

All Computer Science and Engineering Research

This paper introduces a variant of the classical edge coloring problem in graphs that can be applied to an offline scheduling problem for crossbar switches. We show that the problem is NP-complete, develop three lower bounds bounds on the optimal solution value and evaluate the performance of several approximation algorithms, both analytically and experimentally. We show how to approximate an optimal solution with a worst-case performance ratio of 3/2 and our experimental results demonstrate that the best algorithms produce results that very closely track a lower bound.

Maximum Priority Matchings, Jonathan Turner

All Computer Science and Engineering Research

Let G=(V,E) be an undirected graph with n vertices and m edges, in which each vertex u is assigned an integer priority in [1,n], with 1 being the ``highest'' priority. Let M be a matching of G. We define the priority score of M to be an n-ary integer in which the i-th most-significant digit is the number of vertices with priority i that are incident to an edge in M. We describe a variation of the augmenting path method (Edmonds' algorithm) that finds a matching with maximum priority score in O(mn) time.

Conflict-Aware Real-Time Routing For Industrial Wireless Sensor-Actuator Networks, Chengjie Wu, Dolvara Gunatilaka, Mo Sha, Chenyang Lu

All Computer Science and Engineering Research

Process industries are adopting wireless sensor-actuator networks (WSANs) as the communication infrastructure. WirelessHART is an open industrial standard for WSANs that have seen world-wide deployments. Real-time scheduling and delay analysis have been studied for WSAN extensively. End-to-end delay in WSANs highly depends on routing, which is still open problem. This paper presents the first real-time routing design for WSAN. We first discuss end-to-end delays of WSANs, then present our real-time routing design. We have implemented and experimented our routing designs on a wireless testbed of 69 nodes. Both experimental results and simulations show that our routing design can improve the …

Maximizing Network Lifetime Of Wireless Sensor-Actuator Networks Under Graph Routing, Chengjie Wu, Dolvara Gunatilaka, Abusayeed Saifullah, Mo Sha, Paras Tiwari, Chenyang Lu, Yixin Chen

All Computer Science and Engineering Research

Process industries are adopting wireless sensor-actuator networks (WSANs) as the communication infrastructure. The dynamics of industrial environments and stringent reliability requirements necessitate high degrees of fault tolerance in routing. WirelessHART is an open industrial standard for WSANs that have seen world-wide deployments. WirelessHART employs graph routing schemes to achieve network reliability through multiple paths. Since many industrial devices operate on batteries in harsh environments where changing batteries are prohibitively labor-intensive, WSANs need to achieve long network lifetime. To meet industrial demand for long-term reliable communication, this paper studies the problem of maximizing network lifetime for WSANs under graph routing. We …

Woodstocc: Extracting Latent Parallelism From A Dna Sequence Aligner On A Gpu, Stephen V. Cole, Jacob R. Gardner, Jeremy D. Buhler

All Computer Science and Engineering Research

An exponential increase in the speed of DNA sequencing over the past decade has driven demand for fast, space-efficient algorithms to process the resultant data. The first step in processing is alignment of many short DNA sequences, or reads, against a large reference sequence. This work presents WOODSTOCC, an implementation of short-read alignment designed for Graphics Processing Unit (GPU) architectures. WOODSTOCC translates a novel CPU implementation of gapped short-read alignment, which has guaranteed optimal and complete results, to the GPU. Our implementation combines an irregular trie search with dynamic programming to expose regularly structured parallelism. We first describe this implementation, …

The Edge Group Coloring Problem With Applications To Multicast Switching, Jonathan Turner

All Computer Science and Engineering Research

This paper introduces a natural generalization of the classical edge coloring problem in graphs that provides a useful abstraction for two well-known problems in multicast switching. We show that the problem is NP-hard and evaluate the performance of several approximation algorithms, both analytically and experimentally. We find that for random χ-colorable graphs, the number of colors used by the best algorithms falls within a small constant factor of χ, where the constant factor is mainly a function of the ratio of the number of outputs to inputs. When this ratio is less than 10, the best algorithms produces solutions that …

Grafalgo - A Library Of Graph Algorithms And Supporting Data Structures, Jonathan Turner

All Computer Science and Engineering Research

This report provides an overview of Grafalgo, an open-source library of graph algorithms and the data structures used to implement them. The programs in this library were originally written to support a graduate class in advanced data structures and algorithms at Washington University. Because the code's primary purpose was pedagogical, it was written to be as straightforward as possible, while still being highly efficient. Grafalgo is implemented in C++ and incorporates some features of C++11. The library is available on an open-source basis and may be downloaded from https://code.google.com/p/grafalgo/. Source code documentation is at www.arl.wustl.edu/~jst/doc/grafalgo. While not designed as production …

Data Transport System, Rahav Dor

All Computer Science and Engineering Research

To facilitate the WU Smart Home research [21] we built a system that collects data from sensors and uploads the data to the cloud. The system supports data collection from multiple locations (typically apartments) that are independent from each other, endowing the system with two benefit: distributed data collection and alleviating privacy concerns. Each location is managed by a local micro-server (μServer) that is responsible for receiving data packets from sensors and managing their transient storage. Periodically the μServer triggers a data transport process that moves the data to a cloud server where it is stored in a centralized database. …

Exploring User-Provided Connectivity, Mohammad H. Afrasiabi, Roch Guerin

All Computer Science and Engineering Research

Network services often exhibit positive and negative externalities that affect users' adoption decisions. One such service is "user-provided connectivity" or UPC. The service offers an alternative to traditional infrastructure-based communication services by allowing users to share their "home base" connectivity with other users, thereby increasing their access to connectivity. More users mean more connectivity alternatives, i.e., a positive externality, but also greater odds of having to share one's own connectivity, i.e., a negative externality. The tug of war between positive and negative externalities together with the fact that they often depend not just on how many but also which users …

Migrating To Ipv6 - The Role Of Basic Coordination, Mehdi Nikkhah, Roch Guerin

All Computer Science and Engineering Research

The need for a larger Internet address space was acknowledged early on, and a solution (IPv6) standardized years ago. Its adoption has, however, been anything but easy and still faces significant challenges. The situation begs the questions of "why has it been so difficult?" and "what could have been (or still be) done to facilitate this migration?" There has been significant recent interest in those questions, and the paper builds on a line of work based on technology adoption models to explore them. The results confirm the impact of several known factors, but also provide new insight. In particular, they …

Global Edf Scheduling For Parallel Real-Time Tasks, Jing Li

McKelvey School of Engineering Theses & Dissertations

As multicore processors become ever more prevalent, it is important for real-time programs to take advantage of intra-task parallelism in order to support computation-intensive applications with tight deadlines. In this thesis, we consider the Global Earliest Deadline First (GEDF) scheduling policy for task sets consisting of parallel tasks. Each task can be represented by a directed acyclic graph (DAG) where nodes represent computational work and edges represent dependences between nodes. In this model, we prove that GEDF provides a capacity augmentation bound of 4-2/m and a resource augmentation bound of 2-1/m. The capacity augmentation bound acts as a linear-time schedulability …