Department of Electrical Engineering

Numerical algorithms for efficiently solving optimal control problems are important for commonly used advanced control strategies, such as model predictive control (MPC), but can also be useful for advanced estimation techniques, such as moving horizon estimation (MHE). In MPC, the control input is computed by solving a constrained finite-time optimal control (CFTOC) problem on-line, and in MHE the estimated states are obtained by solving an optimization problem that often can be formulated as a CFTOC problem. Common types of optimization methods for solving CFTOC problems are interior-point (IP) methods, sequential quadratic programming (SQP) methods and active-set (AS) methods. In these types of methods, the main computational effort is often the computation of the second-order search directions. This boils down to solving a sequence of systems of equations that correspond to unconstrained finite-time optimal control (UFTOC) problems. Hence, high-performing second-order methods for CFTOC problems rely on efficient numerical algorithms for solving UFTOC problems. Developing such algorithms is one of the main focuses in this thesis. When the solution to a CFTOC problem is computed using an AS type method, the aforementioned system of equations is only changed by a low-rank modification between two AS iterations. In this thesis, it is shown how to exploit these structured modifications while still exploiting structure in the UFTOC problem using the Riccati recursion. Furthermore, direct (non-iterative) parallel algorithms for computing the search directions in IP, SQP and AS methods are proposed in the thesis. These algorithms exploit, and retain, the sparse structure of the UFTOC problem such that no dense system of equations needs to be solved serially as in many other algorithms. The proposed algorithms can be applied recursively to obtain logarithmic computational complexity growth in the prediction horizon length. For the case with linear MPC problems, an alternative approach to solving the CFTOC problem on-line is to use multiparametric quadratic programming (mp-QP), where the corresponding CFTOC problem can be solved explicitly off-line. This is referred to as explicit MPC. One of the main limitations with mp-QP is the amount of memory that is required to store the parametric solution. In this thesis, an algorithm for decreasing the required amount of memory is proposed. The aim is to make mp-QP and explicit MPC more useful in practical applications, such as embedded systems with limited memory resources. The proposed algorithm exploits the structure from the QP problem in the parametric solution in order to reduce the memory footprint of general mp-QP solutions, and in particular, of explicit MPC solutions. The algorithm can be used directly in mp-QP solvers, or as a post-processing step to an existing solution.

System identification is used in engineering sciences to build mathematical models from data. A common issue in system identification problems is that the true inputs to the system are not fully known. In this thesis, existing approaches to unknown input problems are classified and some of their properties are analyzed.

 A new indirect framework is proposed to treat system identification problems with unknown inputs. The effects of the unknown inputs are assumed to be measured through possibly unknown dynamics. Furthermore, the measurements may also be dependent on other known or measured inputs and can in these cases be called indirect input measurements. Typically, these indirect input measurements can arise when a subsystem of a larger system is of interest and only a limited set of sensors is available. Two examples are when it is desired to estimate parts of a mechanical system or parts of a dynamic network without full knowledge of the signals in the system. The input measurements can be used to eliminate the unknown inputs from a mathematical model of the system through algebraic manipulations. The resulting indirect model structure only depends on known and measured signals and can be used to estimate the desired dynamics or properties. The effects of using the input measurements are analyzed in terms of identifiability, consistency and variance properties. It is shown that cancelation of shared dynamics can occur and that the resulting estimation problem is similar to errors-in-variables and closed-loop estimation problems because of the noisy inputs used in the model. In fact, the indirect framework unifies a number of already existing system identification problems that are contained as special cases.

For completeness, an instrumental variable method is proposed as one possibility for estimating the indirect model. It is shown that multiple datasets can be used to overcome certain identifiability issues and two approaches, the multi-stage and the joint identification approach, are suggested to utilize multiple datasets for estimation of models. Furthermore, the benefits of using the indirect model in filtering and for control synthesis are briefly discussed. 

To show the applicability, the framework is applied to the roll dynamics of a ship for tracking of the loading conditions. The roll dynamics is very sensitive to changes in these conditions and a worst-case scenario is that the ship will capsize.  It is assumed that only motion measurements from an inertial measurement unit (IMU) together with measurements of the rudder angle are available. The true inputs are thus not available, but the measurements from the IMU can be used to form an indirect model from a well-established ship model. It is shown that only a subset of the unknown parameters can be estimated simultaneously. Data was collected in experiments with a scale ship model in a basin and the joint identification approach was selected for this application due to the properties of the model. The approach was applied to the collected data and gave promising results.

Object recognition is a skill we as humans often take for granted. Due to our formidable object learning, recognition and generalisation skills, it is sometimes hard to see the multitude of obstacles that need to be overcome in order to replicate this skill in an artificial system. Object recognition is also one of the classical areas of computer vision, and many ways of approaching the problem have been proposed. Recently, visually capable robots and autonomous vehicles have increased the focus on embodied recognition systems and active visual search. These applications demand that systems can learn and adapt to their surroundings, and arrive at decisions in a reasonable amount of time, while maintaining high object recognition performance. This is especially challenging due to the high dimensionality of image data. In cases where end-to-end learning from pixels to output is needed, mechanisms designed to make inputs tractable are often necessary for less computationally capable embodied systems.Active visual search also means that mechanisms for attention and gaze control are integral to the object recognition procedure. Therefore, the way in which attention mechanisms should be introduced into feature extraction and estimation algorithms must be carefully considered when constructing a recognition system.This thesis describes work done on the components necessary for creating an embodied recognition system, specifically in the areas of decision uncertainty estimation, object segmentation from multiple cues, adaptation of stereo vision to a specific platform and setting, problem-specific feature selection, efficient estimator training and attentional modulation in convolutional neural networks. Contributions include the evaluation of methods and measures for predicting the potential uncertainty reduction that can be obtained from additional views of an object, allowing for adaptive target observations. Also, in order to separate a specific object from other parts of a scene, it is often necessary to combine multiple cues such as colour and depth in order to obtain satisfactory results. Therefore, a method for combining these using channel coding has been evaluated. In order to make use of three-dimensional spatial structure in recognition, a novel stereo vision algorithm extension along with a framework for automatic stereo tuning have also been investigated. Feature selection and efficient discriminant sampling for decision tree-based estimators have also been implemented. Finally, attentional multi-layer modulation of convolutional neural networks for recognition in cluttered scenes has been evaluated. Several of these components have been tested and evaluated on a purpose-built embodied recognition platform known as Eddie the Embodied.

Wireless sensor networks (WSNs) are employed in many applications, such as for monitoring bio-potential signals and environmental information. These applications require high-resolution (> 12-bit) analog-to-digital converters (ADCs) at low-sampling rates (several kS/s). Such sensor nodes are usually powered by batteries or energy-harvesting sources hence low power consumption is primary for such ADCs. Normally, tens or hundreds of autonomously powered sensor nodes are utilized to capture and transmit data to the central processor. Hence it is profitable to fabricate the relevant electronics, such as the ADCs, in a low-cost standard complementary metal-oxide-semiconductor (CMOS) process. The two-stage pipelined successive approximation register (SAR) ADC has shown to be an energy-efficient architecture for high resolution. This thesis further studies and explores the design limitations of the pipelined SAR ADC for high-resolution and low-speed applications.

The first work is a 15-bit, 1 kS/s two-stage pipelined SAR ADC that has been implemented in 0.35-μm CMOS process. The use of aggressive gain reduction in the residue amplifier combined with a suitable capacitive array digital-to-analog converter (DAC) topology in the second-stage simplifies the design of the operational transconductance amplifier (OTA) while eliminating excessive capacitive load and consequent power consumption. A comprehensive power consumption analysis of the entire ADC is performed to determine the number of bits in each stage of the pipeline. Choice of a segmented capacitive array DAC and attenuation capacitorbased DAC for the first and second stages respectively enable significant reduction in power consumption and area. Fabricated in a low-cost 0.35-μm CMOS process, the prototype ADC achieves a peak signal-to-noise-and-distortion ratio (SNDR) of 78.9 dB corresponding to an effective number of bits (ENOB) of 12.8-bit at a sampling frequency of 1 kS/s and provides a Schreier figure-of-merit (FoM) of 157.6 dB. Without any form of calibration, the ADC maintains an ENOB > 12.1-bit up to the Nyquist bandwidth of 500 Hz while consuming 6.7 μW. Core area of the ADC is 0.679 mm².

The second work is a 14-bit, tunable bandwidth two-stage pipelined SAR ADC which is suitable for low-power, cost-effective sensor readout circuits. To overcome the high open-loop DC gain requirement of the OTA in the gain-stage, a 3-stage capacitive charge pump (CCP) is utilized to achieve the gain-stage instead of using the switch capacitor (SC) amplifier. Unity-gain OTAs have been used as the analog buffers to prevent the charge sharing between the CCP stages. The detailed design considerations are given in this work. The prototype ADC, designed and fabricated in a low-cost 0.35-μm CMOS process, achieves a peak SNDR of 75.6 dB at a sampling rate of 20 kS/s and 76.1 dB at 200 kS/s while consuming 7.68 μW and 96 μW, respectively. The corresponding Schreier FoM are 166.7 dB and 166.3 dB. Since the bandwidth of CCP is tunable, the ADC maintains a SNDR > 75 dB up

to 260 kHz. The core area occupied by the ADC is 0.589 mm².

As the low-power sensors might be active only for very short time triggered by an external pulse to acquire the data, the third work is a 14-bit asynchronous two-stage pipelined SAR ADC which has been designed and simulated in 0.18-μm CMOS process. A self-synchronous loop based on an edge detector is utilized to generate an internal clock with variable phase. A tunable delay element enables to allocate the available time for the switch capacitor DACs and the gain-stage. Three separate asynchronous clock generators are implemented to create the control signals for two sub-ADCs and the gain-stage between. Aiming to reduce the power consumption of the gain-stage, simple source followers as the analog buffers are implemented in the 3-stage CCP gain-stage. Post-layout simulation results show that the ADC achieves a SNDR of 83.5 dB while consuming 2.39 μW with a sampling rate of 10 kS/s. The corresponding Schreier FoM is 176.7 dB.

In the last ten years, limited clock frequency scaling and increasing power density has shifted IC design focus towards parallelism, heterogeneity and energy efficiency. Improving energy efficiency is by no means simple and it calls for a reevaluation of old design choices in processor architecture, and perhaps more importantly, development of new programming methodologies that exploit the features of modern architectures.

This thesis discusses the design of energy-efficient digital signal processors with application-specific instructions sets, so-called ASIP-DSPs, and their programming tools. Target applications for such processors include, but are not limited to, communications, multimedia, image processing, intelligent vision and radar. These applications are often implemented by a limited set of kernel algorithms, whose performance and efficiency are critical to the application's success. At the same time, the extreme non-recurring engineering cost of system-on-chip designs means that product life-time must be kept as long as possible. Neither general-purpose processors nor non-programmable ASICs can meet both the flexibility and efficiency requirements, and ASIPs may instead be the best trade-off between all the conflicting goals.

Traditional superscalar- and VLIW processor design focus has been to improve the throughput of fine-grained instructions, which results in high flexibility, but also high energy consumption. SIMD architectures, on the other hand, are often restricted by inefficient data access. The result is architectures which spend more energy and/or time on supporting operations rather than actual computing.

This thesis defines the performance limit of an architecture with an N-way parallel datapath as consuming 2N elements of compute data per clock cycle. To approach this performance, this work proposes coarse-grained higher-order functional (HOF) instructions, which encode the most  frequently executed compute-, data access- and control sequences into single many-cycle instructions, to reduce the overheads of instruction delivery, while at the same time maintaining orthogonality. The work further investigates opportunities for operation fusion to improve computing performance, and proposes a flexible memory subsystem for conflict-free parallel memory access with permutation and lookup-table-based addressing, to ensure that high computing throughput can be sustained even in the presence of irregular data access patterns. These concepts are extensively studied by implementing a large kernel algorithm library with typical DSP kernels, to prove their effectiveness and adequacy. Compared to contemporary VLIW DSP solutions, our solution can practically eliminate instruction fetching energy in many scenarios, significantly reduce control path switching, simplify the implementation of kernels and reduce code size, sometimes by as much as 30 times.

The techniques proposed in this thesis have been implemented in the DSP platform ePUMA (embedded Parallel DSP processor with Unique Memory Access), a configurable control-compute heterogeneous platform with distributed memory, optimized for low-power predictable DSP computing. Hardware evaluation has been done with FPGA prototypes. In addition, several VLSI layouts have been created for energy and area estimations. This includes smaller designs, as well as a large design with 73 cores, capable of 1280 integer GOPS or 256 GFLOPS at 500MHz and which measures 45mm2 in 28nm FD-SOI technology.

In addition to the hardware design, this thesis also discusses parallel programming flow for distributed memory architectures and ePUMA application implementation. A DSP kernel programming language and its compiler is presented. This effectively demonstrates how kernels written in a high-level language can be translated into HOF instructions for very high processing efficiency.