Cumulon: Simplified Matrix-Based Data Analytics in the Cloud

Cumulon is a system aimed at simplifying the development and deployment of statistical analysis of big data in public clouds. Cumulon allows users to program in their familiar language of matrices and linear algebra, without worrying about how to map data and computation to specific hardware and cloud software platforms. Given user-specified requirements in terms of time, monetary cost, and risk tolerance, Cumulon automatically makes intelligent decisions on implementation alternatives, execution parameters, as well as hardware provisioning and configuration settings -- such as what type of machines and how many of them to acquire. Cumulon also supports clouds with auction-based markets: it effectively utilizes computing resources whose availability varies according to market conditions, and suggests best bidding strategies for them. Cumulon explores two alternative approaches toward supporting such markets, with different trade-offs between system and optimization complexity. Experimental study is conducted to show the efficiency of Cumulon's execution engine, as well as the optimizer's effectiveness in finding the optimal plan in the vast plan space.

Testing of Interposer-Based 2.5D Integrated Circuits

The unprecedented and relentless growth in the electronics industry is feeding the demand for integrated circuits (ICs) with increasing functionality and performance at minimum cost and power consumption. As predicted by Moore's law, ICs are being aggressively scaled to meet this demand. While the continuous scaling of process technology is reducing gate delays, the performance of ICs is being increasingly dominated by interconnect delays. In an effort to improve submicrometer interconnect performance, to increase packing density, and to reduce chip area and power consumption, the semiconductor industry is focusing on three-dimensional (3D) integration. However, volume production and commercial exploitation of 3D integration are not feasible yet due to significant technical hurdles.

At the present time, interposer-based 2.5D integration is emerging as a precursor to stacked 3D integration. All the dies and the interposer in a 2.5D IC must be adequately tested for product qualification. However, since the structure of 2.5D ICs is different from the traditional 2D ICs, new challenges have emerged: (1) pre-bond interposer testing, (2) lack of test access, (3) limited ability for at-speed testing, (4) high density I/O ports and interconnects, (5) reduced number of test pins, and (6) high power consumption. This research targets the above challenges and effective solutions have been developed to test both dies and the interposer.

The dissertation first introduces the basic concepts of 3D ICs and 2.5D ICs. Prior work on testing of 2.5D ICs is studied. An efficient method is presented to locate defects in a passive interposer before stacking. The proposed test architecture uses e-fuses that can be programmed to connect or disconnect functional paths inside the interposer. The concept of a die footprint is utilized for interconnect testing, and the overall assembly and test flow is described. Moreover, the concept of weighted critical area is defined and utilized to reduce test time. In order to fully determine the location of each e-fuse and the order of functional interconnects in a test path, we also present a test-path design algorithm. The proposed algorithm can generate all test paths for interconnect testing.

In order to test for opens, shorts, and interconnect delay defects in the interposer, a test architecture is proposed that is fully compatible with the IEEE 1149.1 standard and relies on an enhancement of the standard test access port (TAP) controller. To reduce test cost, a test-path design and scheduling technique is also presented that minimizes a composite cost function based on test time and the design-for-test (DfT) overhead in terms of additional through silicon vias (TSVs) and micro-bumps needed for test access. The locations of the dies on the interposer are taken into consideration in order to determine the order of dies in a test path.

To address the scenario of high density of I/O ports and interconnects, an efficient built-in self-test (BIST) technique is presented that targets the dies and the interposer interconnects. The proposed BIST architecture can be enabled by the standard TAP controller in the IEEE 1149.1 standard. The area overhead introduced by this BIST architecture is negligible; it includes two simple BIST controllers, a linear-feedback-shift-register (LFSR), a multiple-input-signature-register (MISR), and some extensions to the boundary-scan cells in the dies on the interposer. With these extensions, all boundary-scan cells can be used for self-configuration and self-diagnosis during interconnect testing. To reduce the overall test cost, a test scheduling and optimization technique under power constraints is described.

In order to accomplish testing with a small number test pins, the dissertation presents two efficient ExTest scheduling strategies that implements interconnect testing between tiles inside an system on chip (SoC) die on the interposer while satisfying the practical constraint that the number of required test pins cannot exceed the number of available pins at the chip level. The tiles in the SoC are divided into groups based on the manner in which they are interconnected. In order to minimize the test time, two optimization solutions are introduced. The first solution minimizes the number of input test pins, and the second solution minimizes the number output test pins. In addition, two subgroup configuration methods are further proposed to generate subgroups inside each test group.

Finally, the dissertation presents a programmable method for shift-clock stagger assignment to reduce power supply noise during SoC die testing in 2.5D ICs. An SoC die in the 2.5D IC is typically composed of several blocks and two neighboring blocks that share the same power rails should not be toggled at the same time during shift. Therefore, the proposed programmable method does not assign the same stagger value to neighboring blocks. The positions of all blocks are first analyzed and the shared boundary length between blocks is then calculated. Based on the position relationships between the blocks, a mathematical model is presented to derive optimal result for small-to-medium sized problems. For larger designs, a heuristic algorithm is proposed and evaluated.

In summary, the dissertation targets important design and optimization problems related to testing of interposer-based 2.5D ICs. The proposed research has led to theoretical insights, experiment results, and a set of test and design-for-test methods to make testing effective and feasible from a cost perspective.

Hyperspectral Image Classification with Nonlinear Methods

This thesis introduces two related lines of study on classification of hyperspectral images with nonlinear methods. First, it describes a quantitative and systematic evaluation, by the author, of each major component in a pipeline for classifying hyperspectral images (HSI) developed earlier in a joint collaboration [23]. The pipeline, with novel use of nonlinear classification methods, has reached beyond the state of the art in classification accuracy on commonly used benchmarking HSI data [6], [13]. More importantly, it provides a clutter map, with respect to a predetermined set of classes, toward the real application situations where the image pixels not necessarily fall into a predetermined set of classes to be identified, detected or classified with.

The particular components evaluated are a) band selection with band-wise entropy spread, b) feature transformation with spatial filters and spectral expansion with derivatives c) graph spectral transformation via locally linear embedding for dimension reduction, and d) statistical ensemble for clutter detection. The quantitative evaluation of the pipeline verifies that these components are indispensable to high-accuracy classification.

Secondly, the work extends the HSI classification pipeline with a single HSI data cube to multiple HSI data cubes. Each cube, with feature variation, is to be classified of multiple classes. The main challenge is deriving the cube-wise classification from pixel-wise classification. The thesis presents the initial attempt to circumvent it, and discuss the potential for further improvement.

Background Traffic Modeling for Large-Scale Network Simulation

Network simulation is an indispensable tool for studying Internet-scale networks due to the heterogeneous structure, immense size and changing properties. It is crucial for network simulators to generate representative traffic, which is necessary for effectively evaluating next-generation network protocols and applications. With network simulation, we can make a distinction between foreground traffic, which is generated by the target applications the researchers intend to study and therefore must be simulated with high fidelity, and background traffic, which represents the network traffic that is generated by other applications and does not require significant accuracy. The background traffic has a significant impact on the foreground traffic, since it competes with the foreground traffic for network resources and therefore can drastically affect the behavior of the applications that produce the foreground traffic. This dissertation aims to provide a solution to meaningfully generate background traffic in three aspects. First is realism. Realistic traffic characterization plays an important role in determining the correct outcome of the simulation studies. This work starts from enhancing an existing fluid background traffic model by removing its two unrealistic assumptions. The improved model can correctly reflect the network conditions in the reverse direction of the data traffic and can reproduce the traffic burstiness observed from measurements. Second is scalability. The trade-off between accuracy and scalability is a constant theme in background traffic modeling. This work presents a fast rate-based TCP (RTCP) traffic model, which originally used analytical models to represent TCP congestion control behavior. This model outperforms other existing traffic models in that it can correctly capture the overall TCP behavior and achieve a speedup of more than two orders of magnitude over the corresponding packet-oriented simulation. Third is network-wide traffic generation. Regardless of how detailed or scalable the models are, they mainly focus on how to generate traffic on one single link, which cannot be extended easily to studies of more complicated network scenarios. This work presents a cluster-based spatio-temporal background traffic generation model that considers spatial and temporal traffic characteristics as well as their correlations. The resulting model can be used effectively for the evaluation work in network studies.

Vertical Handoff Target Selection in a Heterogeneous Wireless Network Using Fuzzy ELECTRE

Global connectivity is on the verge of becoming a reality to provide high-speed, high-quality, and reliable communication channels for mobile devices at anytime, anywhere in the world. In a heterogeneous wireless environment, one of the key ingredients to provide efficient and ubiquitous computing with guaranteed quality and continuity of service is the design of intelligent handoff algorithms. Traditional single-metric handoff decision algorithms, such as Received Signal Strength (RSS), are not efficient and intelligent enough to minimize the number of unnecessary handoffs, decision delays, call-dropping and blocking probabilities. This research presents a novel approach for of a Multi Attribute Decision Making (MADM) model based on an integrated fuzzy approach for target network selection.

Digital geometric-sequence control technique for bidirectional dual active bridge DC-DC converters used in future electric vehicles

Bidirectional DC-DC converters are widely used in different applications such as energy storage systems, Electric Vehicles (EVs), UPS, etc. In particular, future EVs require bidirectional power flow in order to integrate energy storage units into smart grids. These bidirectional power converters provide Grid to Vehicle (V2G)/ Vehicle to Grid (G2V) power flow capability for future EVs. Generally, there are two control loops used for bidirectional DC-DC converters: The inner current loop and The outer loop. The control of DAB converters used in EVs are proved to be challenging due to the wide range of operating conditions and non-linear behavior of the converter. In this thesis, the precise mathematical model of the converter is derived and non-linear control schemes are proposed for the control system of bidirectional DC-DC converters based on the derived model. The proposed inner current control technique is developed based on a novel Geometric-Sequence Control (GSC) approach. The proposed control technique offers significantly improved performance as compared to one for conventional control approaches. The proposed technique utilizes a simple control algorithm which saves on the computational resources. Therefore, it has higher reliability, which is essential in this application. Although, the proposed control technique is based on the mathematical model of the converter, its robustness against parameter uncertainties is proven. Three different control modes for charging the traction batteries in EVs are investigated in this thesis: the voltage mode control, the current mode control, and the power mode control. The outer loop control is determined by each of the three control modes. The structure of the outer control loop provides the current reference for the inner current loop. Comprehensive computer simulations have been conducted in order to evaluate the performance of the proposed control methods. In addition, the proposed control have been verified on a 3.3 kW experimental prototype. Simulation and experimental results show the superior performance of the proposed control techniques over the conventional ones.

SINGLE STAGE LED DRIVER TECHNOLOGY WITH LOW FREQUENCY RIPPLE CANCELLATION

Because of high efficacy, long lifespan, and environment-friendly operation, LED lighting devices become more and more popular in every part of our life, such as ornament/interior lighting, outdoor lightings and flood lighting. The LED driver is the most critical part of the LED lighting fixture. It heavily affects the purchasing cost, operation cost as well as the light quality. Design a high efficiency, low component cost and flicker-free LED driver is the goal. The conventional single-stage LED driver can achieve low cost and high efficiency. However, it inevitably produces significant twice-line-frequency lighting flicker, which adversely affects our health. The conventional two-stage LED driver can achieve flicker-free LED driving at the expenses of significantly adding component cost, design complexity and low the efficiency. The basic ripple cancellation LED driving method has been proposed in chapter three. It achieves a high efficiency and a low component cost as the single-stage LED driver while also obtaining flicker-free LED driving performance. The basic ripple cancellation LED driver is the foundation of the entire thesis. As the research evolving, another two ripple cancellation LED drivers has been developed to improve different aspects of the basic ripple cancellation LED driver design. The primary side controlled ripple cancellation LED driver has been proposed in chapter four to further reduce cost on the control circuit. It eliminates secondary side compensation circuit and an opto-coupler in design while at the same time maintaining flicker-free LED driving. A potential integrated primary side controller can be designed based on the proposed LED driving method. The energy channeling ripple cancellation LED driver has been proposed in chapter five to further reduce cost on the power stage circuit. In previous two ripple cancellation LED drivers, an additional DC-DC converter is needed to achieve ripple cancellation. A power transistor has been used in the energy channeling ripple cancellation LED driving design to successfully replace a separate DC-DC converter and therefore achieved lower cost. The detailed analysis supports the theory of the proposed ripple cancellation LED drivers. Simulation and experiment have also been included to verify the proposed ripple cancellation LED drivers.

Processing the Intracardiac Electrogram for Atrial Fibrillation Ablation

Atrial fibrillation (AF) is a major global health issue as it is the most prevalent sustained supraventricular arrhythmia. Catheter-based ablation of some parts of the atria is considered an effective treatment of AF. The main objective of this research is to analyze atrial intracardiac electrograms (IEGMs) and extract insightful information for the ablation therapy. Throughout this thesis we propose several computationally efficient algorithms that take streams of IEGMs from different atrial sites as the input signals, sequentially analyze them in various domains (e.g., time and frequency), and create color-coded three-dimensional map of the atria to be used in the ablation therapy.

Axis Mapping: The Estimation of Surface Orientations and its Applications in Vehicle Localization and Structural Geology

The map representation of an environment should be selected based on its intended application. For example, a geometrically accurate map describing the Euclidean space of an environment is not necessarily the best choice if only a small subset its features are required. One possible subset is the orientations of the flat surfaces in the environment, represented by a special parameterization of normal vectors called axes. Devoid of positional information, the entries of an axis map form a non-injective relationship with the flat surfaces in the environment, which results in physically distinct flat surfaces being represented by a single axis. This drastically reduces the complexity of the map, but retains important information about the environment that can be used in meaningful applications in both two and three dimensions. This thesis presents axis mapping, which is an algorithm that accurately and automatically estimates an axis map of an environment based on sensor measurements collected by a mobile platform. Furthermore, two major applications of axis maps are developed and implemented. First, the LiDAR compass is a heading estimation algorithm that compares measurements of axes with an axis map of the environment. Pairing the LiDAR compass with simple translation measurements forms the basis for an accurate two-dimensional localization algorithm. It is shown that this algorithm eliminates the growth of heading error in both indoor and outdoor environments, resulting in accurate localization over long distances. Second, in the context of geotechnical engineering, a three-dimensional axis map is called a stereonet, which is used as a tool to examine the strength and stability of a rock face. Axis mapping provides a novel approach to create accurate stereonets safely, rapidly, and inexpensively compared to established methods. The non-injective property of axis maps is leveraged to probabilistically describe the relationships between non-sequential measurements of the rock face. The automatic estimation of stereonets was tested in three separate outdoor environments. It is shown that axis mapping can accurately estimate stereonets while improving safety, requiring significantly less time and effort, and lowering costs compared to traditional and current state-of-the-art approaches.

Vibrational Feedback Training System for Use with SEMG Controlled Powered Prostheses

Loss of limb results in loss of function and a partial loss of freedom. A powered prosthetic device can partially assist an individual with everyday tasks and therefore return some level of independence. Powered upper limb prostheses are often controlled by the user generating surface electromyographic (SEMG) signals. The goal of this thesis is to develop a virtual environment in which a user can control a virtual hand to safely grasp representations of everyday objects using EMG signals from his/her forearm muscles, and experience visual and vibrotactile feedback relevant to the grasping force in the process. This can then be used to train potential wearers of real EMG controlled prostheses, with or without vibrotactile feedback. To test this system an experiment was designed and executed involving ten subjects, twelve objects, and three feedback conditions. The tested feedback conditions were visual, vibrotactile, and both visual and vibrotactile. In each experimental exercise the subject attempted to grasp a virtual object on the screen using the virtual hand controlled by EMG electrodes placed on his/her forearm. Two metrics were used: score, and time to task completion, where score measured grasp dexterity. It was hypothesized that with the introduction of vibrotactile feedback, dexterity, and therefore score, would improve and time to task completion would decrease. Results showed that time to task completion increased, and score did not improve with vibrotactile feedback. Details on the developed system, the experiment, and the results are presented in this thesis.

Linear Hyperspectral Unmixing Using L0-norm Approximations and Nonnegative Matrix Factorization

Spectral unmixing (SU) is a technique to characterize mixed pixels of the hyperspectral images measured by remote sensors. Most of the existing spectral unmixing algorithms are developed using the linear mixing models. Since the number of endmembers/materials present at each mixed pixel is normally scanty compared with the number of total endmembers (the dimension of spectral library), the problem becomes sparse. This thesis introduces sparse hyperspectral unmixing methods for the linear mixing model through two different scenarios. In the first scenario, the library of spectral signatures is assumed to be known and the main problem is to find the minimum number of endmembers under a reasonable small approximation error. Mathematically, the corresponding problem is called the $\ell_0$-norm problem which is NP-hard problem. Our main study for the first part of thesis is to find more accurate and reliable approximations of $\ell_0$-norm term and propose sparse unmixing methods via such approximations. The resulting methods are shown considerable improvements to reconstruct the fractional abundances of endmembers in comparison with state-of-the-art methods such as having lower reconstruction errors. In the second part of the thesis, the first scenario (i.e., dictionary-aided semiblind unmixing scheme) will be generalized as the blind unmixing scenario that the library of spectral signatures is also estimated. We apply the nonnegative matrix factorization (NMF) method for proposing new unmixing methods due to its noticeable supports such as considering the nonnegativity constraints of two decomposed matrices. Furthermore, we introduce new cost functions through some statistical and physical features of spectral signatures of materials (SSoM) and hyperspectral pixels such as the collaborative property of hyperspectral pixels and the mathematical representation of the concentrated energy of SSoM for the first few subbands. Finally, we introduce sparse unmixing methods for the blind scenario and evaluate the efficiency of the proposed methods via simulations over synthetic and real hyperspectral data sets. The results illustrate considerable enhancements to estimate the spectral library of materials and their fractional abundances such as smaller values of spectral angle distance (SAD) and abundance angle distance (AAD) as well.

Towards Mapping of Rock Walls Using a UAV-Mounted 2D Laser Scanner in GPS Denied Environments

In geotechnical engineering, the stability of rock excavations and walls is estimated by using tools that include a map of the orientations of exposed rock faces. However, measuring these orientations by using conventional methods can be time consuming, sometimes dangerous, and is limited to regions of the exposed rock that are reachable by a human. This thesis introduces a 2D, simulated, quadcopter-based rock wall mapping algorithm for GPS denied environments such as underground mines or near high walls on surface. The proposed algorithm employs techniques from the field of robotics known as simultaneous localization and mapping (SLAM) and is a step towards 3D rock wall mapping. Not only are quadcopters agile, but they can hover. This is very useful for confined spaces such as underground or near rock walls. The quadcopter requires sensors to enable self localization and mapping in dark, confined and GPS denied environments. However, these sensors are limited by the quadcopter payload and power restrictions. Because of these restrictions, a light weight 2D laser scanner is proposed. As a first step towards a 3D mapping algorithm, this thesis proposes a simplified scenario in which a simulated 1D laser range finder and 2D IMU are mounted on a quadcopter that is moving on a plane. Because the 1D laser does not provide enough information to map the 2D world from a single measurement, many measurements are combined over the trajectory of the quadcopter. Least Squares Optimization (LSO) is used to optimize the estimated trajectory and rock face for all data collected over the length of a light. Simulation results show that the mapping algorithm developed is a good first step. It shows that by combining measurements over a trajectory, the scanned rock face can be estimated using a lower-dimensional range sensor. A swathing manoeuvre is introduced as a way to promote loop closures within a short time period, thus reducing accumulated error. Some suggestions on how to improve the algorithm are also provided.

Communication-efficient decentralized sequential detection

The problem of decentralized sequential detection is studied in this thesis, where local sensors are memoryless, receive independent observations, and no feedback from the fusion center. In addition to traditional criteria of detection delay and error probability, we introduce a new constraint: the number of communications between local sensors and the fusion center. This metric is able to reflect both the cost of establishing communication links as well as overall energy consumption over time. A new formulation for communication-efficient decentralized sequential detection is proposed where the overall detection delay is minimized with constraints on both error probabilities and the communication cost. Two types of problems are investigated based on the communication-efficient formulation: decentralized hypothesis testing and decentralized change detection. In the former case, an asymptotically person-by-person optimum detection framework is developed, where the fusion center performs a sequential probability ratio test based on dependent observations. The proposed algorithm utilizes not only reported statistics from local sensors, but also the reporting times. The asymptotically relative efficiency of proposed algorithm with respect to the centralized strategy is expressed in closed form. When the probabilities of false alarm and missed detection are close to one another, a reduced-complexity algorithm is proposed based on a Poisson arrival approximation. In addition, decentralized change detection with a communication cost constraint is also investigated. A person-by-person optimum change detection algorithm is proposed, where transmissions of sensing reports are modeled as a Poisson process. The optimum threshold value is obtained through dynamic programming. An alternative method with a simpler fusion rule is also proposed, where the threshold values in the algorithm are determined by a combination of sequential detection analysis and constrained optimization. In both decentralized hypothesis testing and change detection problems, tradeoffs in parameter choices are investigated through Monte Carlo simulations.

Bit-index sort: A fast non-comparison integer sorting algorithm for permutations

This paper describes a fast integer sorting algorithm, herein referred to as Bit-index sort, which does not use comparisons and is intended to sort partial permutations. Experimental results exhibit linear complexity order in execution time. Bit-index sort uses a bit-array to classify input sequences of distinct integers, and exploits built-in bit functions in C compilers, supported by machine hardware, to retrieve the ordered output sequence. Results show that Bit-index sort outperforms quicksort and counting sort algorithms when compared in their execution time. A parallel approach for Bit-index sort using two simultaneous threads is also included, which obtains further speedups of up to 1.6 compared to its sequential case.