Abstract

Approximate Computing is revolutionizing the way we look at the VLSI design flow from RTL design based micro-architectures to standard cell characterization, by adding a quality relaxation constraint that is born out of the error resilience of modern applications. With the unprecedented increase of data-driven approaches and the need to generalize these approaches over multi-class problems, it is imperative that the traditional methods of delivering consistent precision have to adapt. On the other hand, this does not give us a complete free reign over the chip design flow, as unless an acceptable quality is maintained, the overall system failure is inevitable. Approaching physical limits in the fabrication at the current technology nodes and the growing reliability concerns in the manufacturing process have not only made the paradigm shift towards approximate computing attractive, but a necessity. Approximate Computing has enabled trade-offs between acceptable level of accuracy with the leakage and dynamic power dissipation, area, critical path delay and energy consumption of the chip. Previous approaches in approximate computing have been targeted towards ad hoc and automated approaches alike. The main contribution of this thesis is improvement in these areas with novel approaches to achieve better quality and other performance metric trade-offs. This thesis explores the following major avenues in approximate computing: 1. Arithmetic circuits are the fundamental blocks in any design or architecture. Particularly, optimizing multipliers can bring about a significant edge in terms of performance, power and area. This is achieved by developing a novel and performance efficient design of an approximate multiplier using the Toom-Cook multiplication algorithm. The N-bit multiplier complexity is reduced to O(Nlogd(2d−1)) from O(N2 ), for order d. As a result, on an average, the proposed multiplier achieves 53%, 18% and 57% improvements in area, delay and power only with less than 1% mean error. 2. Approximating Fast Fourier Transform architecture can accelerate numerous digital signal and image processing application domains. In this respect, a shared memory FFT architecture is developed using the proposed Approximate Toom-Cook multiplier. Since the entire frequency domain output is not usually required, another feature of the design is a supporting function in error correction based on the sparsity patterns. The design synthesized as such shows on average, a 49% and 53% improvement in consumption of area and energy, respectively, with as less error as 0.1% with pruning based on the sparsity patterns. Approximating the Full adder standard cells by pruning transistors have enabled us to achieve cells tuned to a more power-quality optimal point. This is essential as the leakage power has increased substantially with technology scaling and has become a dominant component of power dissipation, limiting the performance of the circuits. Significant leakage reductions up to 67% are obtained through the combined efforts of optimal transistor sizing and approximate computing

Abstract

There are many sub-fields of Artificial Intelligence of which Natural Language Processing (NLP) is the one which deals in providing the knowledge to computers to produce and understand human text and speech. Machine Translation (MT) is an application of NLP that focuses on the automatic translation between languages. It is crucial as it has enabled people all over the world to travel to various countries and interact with each other. With the recent advancement in deep learning, Neural Machine Translation (NMT) has shown indistinguishable translations from translations produced by humans for many language pairs, but driving factors behind the leaps in translation quality is availability of abundant parallel data resources which low resource languages lack like Indian languages. A lot of research has been done to improve the translation quality of low resource via exploiting monolingual data or parallel data involving other language pairs. Recently, Multilingualism has drawn much attention and is gradually becoming ubiquitous in the sense that more and more researchers have successfully shown that using additional languages helps in improving the translation quality. Indian languages are diverse, morphologically rich and use different scripts which make Translation tasks complex and challenging. But despite all this, Indian languages still share a lot of lexical features which we think can be utilized to improve the quality of translation systems. So, we performed a large scale case study on similarity among those languages by considering all the different factors that may impact its value. We have also proposed the techniques for efficient Multilingual Neural Machine Translation (MNMT) particularly for Indian languages mainly focusing on leveraging the lexical similarity of languages and efficient training in terms of time as well as computational resources. For this, we are performing a systematic incremental case study on MNMT where we are investigating the contribution of different languages during the learning process. Based on the facts and conclusion from our study, we devised an algorithm that will select the subset of languages for required for particular multilingual NMT settings. Also languages itself can also have multiple domains, making the available parallel data for particular domains very limited thus to address the problem of data scarcity, we propose the pipeline for efficient multilingual multi-domain systems. This is the first large-scale study specifically devoted to improve the MNMT for Indian languages by utilizing language relatedness to the best of our knowledge.

Abstract

The thesis talks about our novel architecture about the quasi-static world to formulate real-time object-based monocular Simultaneous Localization and Mapping (SLAM) for objects present in a scene. Here we propose our novel line-based parameterization for category-specific 3D CAD models. Using the vastly available 3D CAD model collection we have created category-level models for objects, which is in contrast with existing approaches that incorporate object-level models. The proposed parameterization associates the 3D category-specific CAD model and the object present in our scene using a dictionary-based RANSAC method that employs object viewpoint as prior and edges detected in the respective intensity image of the scene. The association problem posed here is tackled as a classical geometry problem rather than being dataset driven, thus saving the time and labor that one invests in annotating dataset to train Keypoint Network[25, 26] for different category objects. The proposed approach not only eliminates the need for dataset preparation, collecting a huge amount of object-level models, and annotating them but also speeds up the entire process as this method processes the image only once for all objects, thus eliminating the need of invoking the network for every object in an image across all the frames. A 3D-2D edge association module followed by a resection algorithm for lines is used to recover object poses. The formulation optimizes for the shape and pose of the object, thus aiding in recovering object 3D structure more accurately. Finally, a Factor Graph formulation is used to combine object poses with camera odometry that helps in formulating the optimization as a SLAM problem. The proposed category-level model-based approach has several other applications, such as retrieval of objects, which is an integral part of Augmented Reality applications. The architecture has been evaluated both qualitatively and quantitatively in a variety of indoor real-world environments, infused with several camera and objects motion challenges, depicting the usefulness of an instance independent monocular object SLAM and the advantage it enjoys over existing feature-based SLAM approaches.

Abstract

In 1957, Noam Chomsky’s revolutionary treatise, Syntactic Structures [45], established the foundations for a formal study of natural language syntax. Such a study requires the development of a mathematical paradigm where the grammatical structure of the language can be analyzed sans the semantic conditions responsible for the “possibility” or truth-value of the sentence, hence colourless green ideas sleep furiously. The work of Chomskyian linguistics in differentiating shallow and deep structures perpetuated the ideas of a rigid motif of structural integrity to language, which was often challenged by semanticists. However, it established the path of the study of natural language by the medium of syntax, therefore impressing upon the need to understand the sentence structure as a method of analyzing the language in a typologically uniform and relevant manner. In this thesis, we study the computational and representational offshoot of syntactic structures. The development of formal grammars allows mathematicians to leverage simply typed lambda calculus into the study of constituency grammar. This subsection of mathematical linguistics, known as categorial grammar, aims to study the functions responsible for combining constituents in a grammatical manner, viz with a view towards composition and compositional semantics. Theoretical work in this direction was motivated by theories such as AB-grammars [4, 10], Lambek calculus [76], Combinatory Categorial Grammar [124], Tree Adjoining Grammar [65], and Abstract Categorial Grammars [53]. Hindi has been largely underrepresented in these formal analyses of grammar, partly due to lack of exposure and partly due to the underlying strongly motivated syntactic analysis of the Paninian Grammatical Framework [17]. Therefore in this thesis, I aim to use a simplification of the Lambek calculus framework, known as pregroup grammar [78] in order to understand the syntactic phenomena underlying the language, when considered devoid of semantic considerations. Pregroup grammars are a simple categorial grammars which have been used to study languages like Japanese, Sanskrit and Persian, along with English, French, Hungarian and others, ensuring a diverse body of literature and surrounding operators and operations for representing constituency information. In this thesis, I study the basic syntactic features of the Hindi language in terms of the word order, noun phrase characteristics, verb phrase characteristics, and formalize the agreement rules between them. I explore the representation of these properties in a consistent manner without relying on lexical semantic characteristics as much as possible. I then delve into the interoperability of relatively free word order syntactic constituent representations, their exploration in dependency syntax, and some possible applications of an advancement in constituency representation with the development of a hybrid grammaticality checker

Abstract

The advent of the Internet of Things (IoT) has resulted in the rise of low power wide area networks such as LoRaWAN, Sigfox, and NB-IoT. Among these, LoRaWAN has garnered tremendous attention owing to the low power consumption of end nodes, long range, high resistance to multipath, low cost, and use of license-free sub-GHz bands. Consequently, LoRaWAN is gradually replacing Wi-Fi and Bluetooth in sundry IoT applications including utility metering, smart cities, and localization. Localization, in particular, has already witnessed a surge of alternatives to Global Navigation Satellite System (GNSS), based on Wi-Fi, Bluetooth, Ultra Wide Band, 5G, etc. in indoor and low power domains due to the poor indoor coverage and high power consumption of GNSS. With the need for localization only shooting up with dense IoT deployments, LoRaWAN is seen as a promising solution in this context. Indeed, many attempts employing various techniques such as Time of Arrival (ToA), Time Difference of Arrival (TDoA), and Received Signal Strength Index (RSSI) have been made to achieve localization using LoRaWAN. However, a significant drawback in this scenario is the lack of extensive data on path loss and signal propagation modeling, particularly in Indian cityscapes. Another demerit is the use of GNSS at some stage primarily for time synchronization of gateways. In this work, we attempt to nullify these two disadvantages of LoRaWAN based localization. The first part of this work presents experimental data of LoRaWAN transmissions inside a typical city building to study signal propagation and path loss. The latter part proposes a standalone GNSS-free localization approach using LoRaWAN that is achieved by applying a collaborative, TDoA-based methodology. An additional stationary node is introduced into the network to allow the synchronization of gateways without GNSS. Finally, the distribution of localization error in a triangle of gateways and the effect of timing resolution, time-on-air, and duty cycle constraints on it are investigated

Abstract

Energetically unfavorable Watson-Crick (WC)-like tautomeric forms of nucleobases are known to introduce spontaneous mutations and contribute to replication, transcription and translation errors. Recent NMR relaxation dispersion techniques were able to show that wobble (w) G•U mispair exists in equilibrium with the short-lived, low-population WC-like enolic tautomers. Presently, we have investigated the wG•U → WC-like enolic reaction pathway using various theoretical methods: quantum mechanics (QM), molecular dynamics (MD), and combined quantum mechanics/molecular mechanics (QM/MM). The previous studies on QM gas phase calculations were inconsistent with experimental data. We have performed structural and energetical characterizations of various intermediates and transition states along the reaction pathway. We have also explored the environmental effects on the reaction energies by adding explicit water. While QM-profile clearly becomes endoergic in the presence of water, QM/MM-profile remains consistently endoergic in the presence and absence of water. Hence, by including microsolvation and QM/MM calculations, experimental data can be explained. For G•U enol → G enol•U pathway, the latter appears to be energetically more favorable throughout all computational models. This study can be considered as a benchmark of various computational models of wG•U to WC-like tautomerization pathways with and without the environmental effects and may contribute to further studies of other mispairs as well. The first chapter gives the background on base mispairs. In chapter two, we give a brief introduction to the methods we have used - quantum mechanics, molecular dynamics and combined quantum mechanics/molecular mechanics. Chapter three deals with the results, analysis, and discussion. Finally, chapter four presents the conclusions of the study.

Abstract

In this thesis, we have discussed two microfluidic sensors, microfluidic micropump, and viscosity sensors, for biomedical and industrial applications. We have done simulations, mathematical analysis, and fabrication of the mentioned devices. Micropumps are one of the most important parts of a microfluidic system. In particular, for biomedical applications such as Lab-on-Chip systems, micropumps are used to transport and manipulate test fluids in a controlled manner. In this work, a low-cost, structurally simple, piezoelectrically actuated micropump was simulated and fabricated using poly-dimethylsiloxane (PDMS). The channels in PDMS were fabricated using patterned SU-8 structures. The pump flow rate was measured to be 9.49 µL/min, 14.06 µL/min, 20.87 µL/min for applied voltages of 12 V, 14 V, 16 V respectively. Further, we report finite element analysis (FEA) simulation to confirm the operation of the micropump and compare favorably the experimentally obtained flowrate with the one predicted by simulation. By taking these flow rates as a reference, the chamber pressure was found to be 1.1 to 1.5 kPa from FEA simulations. Viscosity measurement has wide-ranging applications from the oil industry to the pharmaceutical industry. However, measuring viscosity in real-time is not a facile process. This work provides an elaborate mathematical model and study of measurement of viscosity in realtime using pressure sensors. For a given flowrate, a change in liquid viscosity gives rise to a change in pressure difference across a particular section of the pipe. Hence, by recording the pressure 7 change, viscosity can be calculated dynamically. Mathematical modeling as well as finite element analysis (FEA) modeling has been presented. A set of pressure sensors were placed at a fixed distance from each other to get the real-time pressure change. Knowing the flow rate in the channel, the viscosity has been calculated from the pressure difference. For the finite element analysis, the pressure sensors were placed 60 mm away from each other. The radius of the pipe was 19 mm. A different ratio of the mixture of water and glycerol was used to provide variable viscosity, which led to the variation in pressure-difference values.

Abstract

Motion planning is an important component of robot navigation and manipulation, and it is crucial in applications where the robot operates in full or partial autonomy. Some examples of these are multi-robot exploration, autonomous vehicles, and robot manipulation. In most of these applications, the robot’s state is not directly observable and can only be inferred from erroneous observations. Such situations require the planning algorithms to be robust to the uncertainties in actuation and perception. This thesis investigates the motion planning problem under uncertainty, with specific applications in navigation and path tracking. Applications of these kinds extensively use mathematical routines that solve constraints defined over random variables and are popularly known as chance constraints. Solving for chance constraints is extremely difficult and often intractable. This is primarily due to the fact that non-linear constraints defined over random variables result in a distribution that generally has no parametric form. In this thesis, we focus on constructing mathematical frameworks for solving such intractable optimization routines. This thesis’s key contribution is that we propose a series of formulations that can solve for chance constraints under parametric and non-parametric uncertainties. To achieve this, we construct the mathematical framework systematically over a sequence of stages, wherein each stage improvises over the limitations of the previous. For the first stage, we start with simple sampling-based approaches like the scenario approach. Though conceptually simple, this approach brings an added sample complexity in generating scenarios of the constraint functions. To overcome this limitation of the scenario approach, we proceed to the second stage, where we derive closed-form algebraic equations that would act as a surrogate to the otherwise intractable chance constraint. The novelty in this proposed approach stems from the nature of these surrogate functions, which are simple polynomial functions (mostly quadratic) of control variables and hence greatly simplify complex chance constrained optimization routines. While the proposed framework at this stage did enjoy closed-form algebraic solutions, it relied on the fact that the underlying random variables belonged to parametric forms of distributions (especially Gaussian). Hence we then proceed to the final stage where we solve for chance constraints under non-parametric uncertainties. We construct the proposed algorithm on the possibility of representing arbitrary distributions as functions in Reproducing Kernel Hilbert Space (RKHS). We systematically exploit the kernel trick to reformulate chance constrained optimization routine such that it is tractable and computationally efficient. We detail all the approaches proposed in these three stages over five chapters in this thesis. We primarily apply the proposed formulations on two challenging problems in motion planning: (i) reactive collision avoidance of mobile robots in uncertain dynamic environments and (ii) inverse dynamics based path tracking of manipulators under perception uncertainty. In all these applications, the underlying chance constraints are defined over highly non-linear and non-convex functions of the uncertain parameters, making it highly intractable. We also extend one of the proposed formulations to a multi-robot navigation scenario, where each agent is responsible for computing safe maneuvers, considering perception and ego uncertainty.

Abstract

This work proposes a multi-cloud marketplace model for Infrastructure-as-a-Service (IaaS) layer with multiple cloud providers, intermediate brokers and end users. The brokers service end users subscribed to them by aggregating resources (virtual machines) from cloud providers while maximizing their profits. Similarly cloud providers (producers) allocate their supply of virtual machines to brokers (consumers) so as to maximize their profits. The notion of social welfare in this market structure is defined and two trading schemes are studied. The first scheme involves centralized control which aims at maximizing social welfare. The problem of maximizing the social welfare is formulated as an integer linear programming problem and a greedy algorithm is proposed for the same. However, this scheme may contain unstable producer-consumer pairs who have an incentive to deviate from the current allocation. The second scheme eliminates such unstable pairs by using a generalization of stable matching algorithm but may lead to sub-optimal social welfare. The stable matching algorithm proposed in this work is a particular way of generalizing the original Gale-Shapley deferred acceptance algorithm.

Abstract

Natural Language Generation (NLG) is a research task which addresses the automatic generation of natural language text representative of an input non-linguistic collection of knowledge. Inputs can be of different modalities – databases, structured reports, etc. Traditional NLG systems have been categorized into one of two general approaches: Template based and Pipeline based. In this work, we explore how raw text can be leveraged to automatically extract sub-sentence level templates to generate grammatical sentences. We propose a system for generation of grammatical sentences given a partially ordered partial bagof-words which constrain the generated sentence using a template based approach. As the input, we formulate a lexical level constraint schema as the input constraints which drives the generation process. We view the task as a search problem (a problem of choice) involving combinations of smaller chunk based templates stitched together to construct a complete sentence. To achieve that, we propose a scoring function to determine syntactic correctness of a template sequence which we use in conjunction with an evolutionary algorithm as the search procedure to arrive at a potentially grammatical sentence which satisfies the input constraints.