Abstract

Time-sharing, which allows for multiple users to use a shared resource, is an important and fundamental aspect of modern computing systems. However, accelerators such as GPUs, that come without a native operating system do not support time-sharing. The inability of accelerators (such as GPUs) to support time-sharing limits their applicability especially as they get deployed in Platform-as-a-Service (PaaS) and Resource-as-a-Service (RaaS) environments. In the former (PaaS), elastic demands may require preemption where as in the latter (RaaS), fine-grained economic models of service cost can be supported with time-sharing. We extend the concept of time-sharing to the GPGPU computational space using cooperative multitasking approach. Our technique is applicable to any GPGPU program written in Compute Unified Device Architecture (CUDA) API provided for C/C++ programming languages. With minimal support from the programmer, our framework incorporates process scheduling, light-weight memory management, and multi-GPU support. Our framework provides an abstraction where, every workload can use a GPU(s) over a time quantum exclusively. We demonstrate the applicability of our scheduling framework, by running many workloads concurrently in a time-sharing manner. In this context, we explore two scheduling alorithms: Round-Robin(RR) and Shortest Job First(SJF). We demostrate the versatile nature of the framework by running workloads from different domains.

Abstract

Scene Understanding has been a major aspiration of computer vision from its early days. Its root lies in enabling the computer/robot/machine to understand, interpret and manipulate visual data, in similarity to what an average human eye does in front of a natural/artificial localized location/scene. This ennoblement of the machine have a widespread impact ranging from Surveillance, Aerial Imaging, Autonomous Navigation, Smart Cities and thus scene understanding have remained as an active area of research in the last decade. In the last decade, the scope of problems in the scene understanding community has broadened from Image Annotation, Image Captioning, Image Segmentation to Object Detection, Dense Image Captioning, Instance Segmentation etc. Advanced problems like Autonomous Navigation, Panoptic Segmentation, Video Summarization, Multi-Person Tracking in Crowded Scenes have also surfaced in this arena and are being vigorously attempted. Deep Learning has played a major role in this advancement/development. The performance metrics in some of these tasks have more than tripled in the last decade itself but these tasks remain far from solved. Success originating from deep learning can be attributed to the learned features. In simple words, features learned from a Convolutional Neural Network trained for annotation are in general far more suited for captioning then a non-deep learning method trained for captioning. Taking cue from this particular deep learning trend, we dived into the domain of scene understanding with the focus on utilization of prelearned-features from other similar domains. We focus on two tasks in particular: Automatic (multi-label)Image Annotation and (Road)Intersection Recognition. Automatic image annotation is one of the earliest problems in scene understanding and refers to the task of assigning (multiple) labels to an image based on its content. Whereas intersection recognition is the outcome of the new era of problems in scene understanding and it refers to the task of identifying an intersection from varied viewpoints in varied weather and lighting conditions. We focused on this significantly varied task approach to broaden the scope and generalizing capability of the results we compute. Both image annotation and intersection recognition pose some common challenges such as occlusion, perspective variations, distortions etc. While focusing on the image annotation task we further narrowed our domain by focusing on graph based methods. We again chose two different paradigms: a multiple kernel learning based non-deep learning approach and a deep-learning based approach, with a focus on bringing out contrast again. Through quantitative and qualitative results we show slightly boosted performance from the above mentioned paradigms. The intersection recognition task is relatively new in the field. Most of the work in field focuses on Places Recognition which utilized only single images. We focus on temporal information i.e. the traversal of the intersection/places as seen from a camera mounted on a vehicle. Through experiments we show a performance boost in intersection recognition from the inclusion of temporal information

Abstract

Speech signal can be considered as a sequence of acoustic events, where each acoustic event can be distinctly characterized by its production mechanism. Acoustic event-based signal pro- cessing techniques have gained vital importance in speech feature representation which is ro-bust to noise. The detection of specific acoustic events that correspond to the unique phonetic features of the speech is important in speech assessment systems and clinical speech analysis.In landmark or acoustic event based speech analysis, the speech signal is processed around specific locations known as events instead of the entire speech signal. Most of the Indian languages are vowel-centric, and hence consonants must be grouped with a vowel following it or preceding it. This process of clustering consonant or consonant cluster with either preceding vowel or next vowel is known as syllabification. The significance of accurate vowel region detection from a continuous speech has many applications that include robust speaker recognition, smart audio filtering, consonant-vowel unit recognition in Indian languages, speech rate manipulation and multimedia synchronization. With this motivation, the thesis explores the use of speech production knowledge in the detection of vowel regions. Further, the vowel region detection techniques are used to detect retroflex approximants and palatalized consonants in the Indian context. The important issues addressed in this thesis are listed below:• A two-stage algorithm is proposed to detect precise vowel regions using dominant spectral peaks of zero frequency filtered speech signal. In post-processing, spurious vowel regions removed based on uniformity of epoch intervals and the positions of vowel on set points, and vowel end-points are corrected using the strength of the excitation of the speech signal.• A technique is proposed for the vowel region detection from the continuous speech using an envelope of the derivative of the speech signal, which is a non-negative, frequency weighted energy operator.• A language identification system using deep neural networks with attention is explored with a vowel region detection scheme incorporated at the front-end. The spectral features extracted from the vowel regions instead of entire speech are used to model the language identification system. • An approach for automatic detection of retroflex approximant in a Tamil continuous speech is proposed using vowel regions and formant dynamics. The formant dynamics are obtained through the Hilbert envelope of the numerator of the group delay function. • A technique is proposed to detect auxiliary palatalization from the continuous Kashmiri speech. These consonants investigated in synchronous with vowel regions, which are spotted using the instantaneous energy computed from the envelope-derivative of the speech signal. • A new speech feature representation is proposed by integrating single frequency filtering technique with higher order nonlinear energy operator for emotion recognition. The performance of the system is evaluated by extracting the speech features in vowel regions instead of entire speech in noisy environments.The final remarks drawn out of this thesis work are as follows: The performance of the proposed vowel region detection methods observed to be better compared to the existing meth- ods under clean and noisy environments. The proposed techniques utilize speech production knowledge in terms of strength of the excitation and uniformity of the epoch intervals of the speech signal. Moreover, vowel region detection technique based on the envelope of the derivative of the speech signal is better compared to the method based on the zero frequency filtering technique. It is mainly due to the capturing of the instantaneous energy of the speech signal in a better manner. A front-end vowel region detection scheme incorporated to the language identification system to use spectral features extracted from the vowel regions instead of the entire speech signal. It exhibited a significant improvement in the recognition rate in noisy environments. A speaker independent retroflex approximant detection approach is proposed to detect the language-specific phonetic feature of Tamil in clean and noisy environments. In an- other study, palatalization in Kashmiri is detected by anchoring vowel regions. The technique for detecting palatalization process in the vowel context is proposed based on set of acous- tic cues. These include a second formant gradient, a measure of the second formant nearing the third formant, and high to low energy ratio derived from the spectral characteristics of the palatalized consonants using the Hilbert envelope of the numerator of the group delay function. The results showed that these acoustic cues capture secondary articulatory changes in palatalized consonants to detect them in continuous speech. Lastly, a new feature representation is proposed for emotion

Abstract

Natural Language Processing deals with the techniques and processes which help computers interpret and process the human languages. There are various NLP applications which help us in daily tasks,namely spellchecker, text auto-correction, machine translation systems, text classification, and text summarization etc.. There is vast information available on the internet, but most of it is available in English.When it comes to Indian languages, the content is much lesser compared to other languages. Most of the Indian people are multilingual and machine translation systems can be utilized to translate from text in one language to a one’s own language. In that way machine translation technology can be helpful to overcome the language barrier. Also, most people in India are not proficient in English, hence machine translation systems can take advantage of the large information available on the internet. The machine translation technology has various approaches out of which main approaches are rule based, data driven and hybrid approach. Each of these approaches have their pros and cons. The hybrid approach utilizes the benefits of both rule based as well as data driven approaches by combining them. The pipeline based hybrid machine translation systems exhibit certain software engineering charac- teristic like heterogeneous nature of architecture, compute and knowledge intensive nature of modules and blackboard architecture. Due to these characteristics, the development and re-engineering of the hybrid MT systems are different from that of traditional software engineering processes. The hybrid MT systems with pipeline based architecture face some issues like lack of efficiency, architecture mismatch, scalability, robustness and performance related challenges in their integration, deployment and engineering. We took Anusaaraka (English to Hindi) and Sampark (Indian language to Indian language) MT systems as our use-cases of pipeline based hybrid machine translation systems. The different modules in both of the systems are developed by different teams. By studying both of the systems, we observed that modules, internally, sometimes use heterogeneous utilities and platforms as well as hard coded knowledge sources which makes them rigid in nature and difficult to manage. This is not in consonance with the larger specifications of the system. These modules are comprised of complex, knowledge and compute intensive NLP modules relying on a bulk of hard-coded knowledge sources. Such modules are typically very unwieldy when we expect to scale the performance of the overall NLP system they are a part of. Additionally, there are NLP applications which either utilize MT systems or support their development processes. Such applications are translation workbenches and resource management systems. We also studied the aspects of MT related applications and found that the translation workbenches as well as resource management systems have performance issues and are developed with heterogeneous modules as mentioned above. Therefore, for making MT systems as well as MT related NLP applications to be utilized by the mass public, these MT applications need to be re-engineered. In this thesis, we aim to propose an approach to re-engineer MT and MT related applications to make them efficient and improve their performance in terms of processing speed. It would facilitate the MT systems to be used as services which can be used in various NLP products and services. We first studied the Anusaaraka MT system and identified the NLP components which can be re-engineered. We proposed the symbiotic software engineering approach followed by micro-services based architecture to re-engineer the system. In this way, each of the NLP modules as well as the complete MT system is proposed as a set of independent microservices. We demonstrate our approach on Anusaaraka MT system in which the performance of the system improves by 87% on execution of 1 sentence. The documentation and test cases are also being prepared for each of the modules as well as the complete system. We also propose the concept of distributed caching which is utilized to improve the performance of compute intensive NLP modules in distributed environment. We performed experiments to analyze the impact of distributed caching on the Sampark MT system. The performance of the Sampark MT system improves additionally by 4-6% when we utilize distributed caching mechanism over normal caching. We then propose the translation workbench-Transzaar with a resource management system- Kunji to aid the translators. The performance of the translators is evaluated in various scenarios when they use Transzaar and Transzaar with resource management system-Kunji. The productivity of the translators improved significantly by 1.35-1.45 times for English-Hindi language pair and 2 times for Hindi-Urdu language pair to that of their initial productivity with Transzaar. Moreover it is also observed th

Abstract

The structure and dynamics of RNA macromolecules is influenced by myriad of noncovalent inter-actions, among which base pairing and base stacking are the most prominent. Detailed understanding of such interactions in the rapidly growing number of 3D RNA structures necessitates their proper an-notation and classification. Despite previous significant efforts toward classification of base pairing interactions in RNA, analogous scheme for classification of base stacking interactions is currently missing in literature. As a first step towards understanding the role of base stacking in various functional contexts of RNA, the present work provides an unambiguous and detailed classification scheme for RNA base stacks, in which the stacks are classified in terms of the mutual orientation of the interacting nucleobase faces, the mutual glycosidic orientation of the stacked nucleotides and the identity of the interacting rings. Further, an algorithm was developed for automated identification and classification of base stacks occurring in RNA crystal structures, which enabled us to identify exemplars of each stacking type, as well as carry out statistical distribution of different types of stacking contacts. The algorithm was further modified to analyse stacking interactions involving unique post-transcriptionally modified nucleobases. Finally, the utility of out classification scheme as well as automated stacking detection method was demonstrated by analysing the stacking interactions involved in specific structural and functional contexts of RNA. Overall, this study is expected to deepen our understanding of how different physicochemical forces contribute towards shaping the RNA structure-function landscape.

Abstract

Software is finding place in deeply embedded systems to large scale distributed systems of cloud service providers such as Amazon and Google. Due to concurrent and distributed nature of this software, it is hard to test for correctness of such systems in a foolproof manner. Model checking is now a standard technology for verifying large and complex systems. Explicit state model checking is an approach in which we build a model of the system and specify the properties it should hold. Then we construct a state transition system from the model and check if it satisfies the specified properties. There are two kinds of properties of interest: safety and liveness. The scaling of model checking, however, remains a significant challenge. Distributed model checking is an important and promising approach to tackle the problem of scale. In this thesis, we focus our attention on safety properties verification, which involves checking if the states that are generated in the transition system satisfies some predicate formulae specified in the form of assertions. The main problem here is that the number of states in the transition system grows exponentially with the number of bits required to store the state of a model at any given point of time. So the available main memory even in a server class machine is not sufficient to model check non-trivial practical models. One approach to address this problem is by using resources from a distributed collection of machines. We use two different distributed models in order to achieve the above mentioned. Our first implementation is based on vertex centric programming model. It is uses the concept of bulk synchronous parallel computing to synchronize. The second implementation uses Actor Model. We propose asynchronous algorithms for the verification and a simple reduction strategy in this implementation. The main advantage of Actor model is that it comes with a transparent way to scale from a single node to multiple nodes, without having to change any of the implementation.

Abstract

Historically, row store has been the most popular storage layout to store relational data in commercial databases. With the advent of column store, it became possible to improve the efficiency of real world queries by storing and operating on each attribute separately. Traditional row store has the disadvantage of reading irrelevant attributes into main memory, when only a few attributes are queried. Whereas, column store suffers from large “stitching” costs if the number of attributes queried are large. Moreover, traditional row store suffers from a large amount of cache misses whereas column store is cache-efficient since irrelevant attributes are not brought into the cache. Recent years have also witnessed an in-memory revolution in databases, wherein a large part of the data is majorly stored in RAM thereby removing the I/O overhead. Although the concept of in-memory databases has been around for a long time, commercial and practical implementations have been feasible only recently due to the falling prices of RAM coupled with its increasing capacity. However, research has shown that most of the time in such systems is lost due to the cache misses. Most commercial row and column storage systems do not optimize for the layout of data in the available main memory to improve performance. In this thesis, we introduce an intuitive, hybrid combination of row and column storage mechanisms to reduce the I/O cost and cache misses for ad-hoc read-only queries. Our system acts as a commercial off-the-shelf (COTS) solution on top of existing databases. We leverage the concept of vertical fragmentation by analyzing the historical query load and grouping certain related attributes together to form vertical fragments. The attributes within a particular fragment are selected on the basis of their co-occurrence over all queries. These generated fragments are then stored as materialized views in the main memory buffer. The more ”valuable” fragments are given priority when allocating space in the main memory. We also present algorithms to optimally select the required data from these fragments for a given query so as to reduce the total I/O calls to the secondary storage. Moreover, this placement of data in main memory is cache-efficient, thereby improving the performance. We show that on average, FAST executes queries up-to an order of magnitude faster than row storage and as much as twice as fast than column storage for an ad-hoc workload. We demonstrate the superior performance of FAST on TPC-H benchmark queries as well. Our results show superior performance of FAST on multiple TPC- H queries. We also present techniques to automatically adapt the main memory layout to a changing workload Although the framework described by this thesis largely focuses on the main memory and the secondary storage for data layout, our algorithms and techniques have been designed to work for any generic multi-level data storage system. For example, we can leverage our approach in a three level storage model consisting of the main memory, an intermediate SSD layer and the secondary storage. This is possible because we deal with the logical database layer rather than modifying the physical layer to achieve performance gains. Moreover, our storage model is designed to support both OLAP (online analytical processing) and OLTP (online transaction processing) workloads. In fact, one of the advantages of our framework is the ease of implementation on top of existing databases systems. To this end, we apply FAST in the context of distributed databases. We also discuss an in-grained applica- tion of FAST for distributed databases which would result in larger query efficiency gains at the cost of implementation. We hope this discussion to open up new areas of systems research in this direction.

Abstract

Real world images depict varying scenes, actions and multiple objects interacting with each other. We consider the fundamental Computer Vision problem of image annotation, where an image needs to be automatically tagged with a set of discrete labels that best describe its semantics. As more and more digital images become available, image annotation can help in the automatic archival and retrieval of large image collections. Being at the heart of image understanding, image annotation can also assist in other visual learning tasks, such as image captioning, scene recognition, multi-object recognition, etc.. With the advent of deep neural networks, recent research has achieved ground-breaking results in single-label image classification. However, for images representing the real world, containing different objects in varying scales and viewpoints, modelling the semantic relationship between images and all of their associated labels continues to remain a challenging problem. Additional challenges are posed from class-imbalance, incomplete labelling, label-ambiguity and several other issues that are commonly observed in the image annotation datasets. In this thesis, we study the image annotation task from two aspects. First, we bring to attention some of the core issues in the image annotation domain related to dataset properties and evaluation metrics that inherently affect the annotation performance of existing approaches to a significant extent. To examine these key aspects, we evaluate ten benchmark image annotation techniques on five popular datasets using the same baseline features, and perform thorough empirical analyses. With novel experiments, we explore possible reasons behind variations in per-label versus per-image evaluation criteria and discuss when each one of these should be used. We investigate dataset specific biases and propose new quantitative measures to quantify the degree of image and label diversity in a dataset, that can also be useful in developing new image annotation datasets. We believe the conclusions derived in this analysis would be helpful in making systematic advancements in this domain. Second, we attempt to address the annotation task by a CNN-RNN framework that jointly models label dependencies in an image while annotating it. We base our approach on the premise that labels corresponding to different visual concepts in an image share rich semantic relationships among them (e.g., “sky” is related to “cloud”). We follow recent works that have explored the CNN-RNN style models due to RNN’s capacity to model higher-order dependencies, but are limited in their approach to train the RNN in a pre-defined label order sequence. We overcome this limitation and propose a new method to learn multiple label prediction paths. We evaluate our proposed method on a number of popular and relevant datasets and achieve superior results compared to existing CNN-RNN based approaches. We also discuss the scope of the CNN-RNN framework in the context of image annotation.

Abstract

The advent of indoor personal mobile robots has clearly demonstrated their utility in assisting humans at various places such as workshops, offices, homes, etc. One of the most important cases in such autonomous scenarios is where the robot has to search for certain objects in large rooms. Exploring the whole room would prove to be extremely expensive in terms of both computing power and time. To address this issue, we demonstrate a fast algorithm to reduce the search space by identifying possible object locations as two classes, namely - Support Structures and Clutter. Support Structures are plausible object containers in a scene, such as tables, chairs, sofas, etc. Clutter refers to places where there seem to be several objects but cannot be clearly distinguished. In this thesis, we propose an algorithm to identify potential object locations using a Support Vector Machine(SVM) learned over the features extracted from the depth map and the RGB image of the scene, which further culminates into a densely connected Conditional Random Field(CRF) formulated over the image of the scene. The inference over the CRF leads to the assignment of the labels - support structure, clutter, others to each pixel. Further to this, we also explore deep neural network-based algorithms for detecting objects from far off spaces. Small object detection plays an important role in robot navigation, scene understanding, etc as most of the objects observed are generally small until observed from close. Although current object detection algorithms show state-of-the-art accuracy on multiple datasets, they fail to accurately detect small objects. We propose a deep neural network architecture which is a variant of the SSD network. The proposed architecture uses spatial context to efficiently detect small objects without much reduction in the speed. This is close to mimicking human behavior where we search for small objects in the vicinity of larger related objects. The architecture proposed shows a better accuracy for small object detection compared to the conventional SSD. We also explore the use of a context network-based method to improve the accuracy of small object detection. We formulate this as a label space learning method compared to an end-to-end learning algorithm. We use the state-of-the-art YOLO network and train a context network as an auxiliary task for better localization of the small objects in an image. We demonstrate improvements in the object detection accuracy for small objects compared to the YOLO v2 method.

Abstract

Heme, the second most abundant tetrapyrrole, serves as the cofactor for proteins involved in respiration and metabolism. Heme is synthesized through a well conserved and established heme biosynthetic pathway in all eukaryotes and most prokaryotes. Hydroxymethylbilane synthase (HMBS), also known as porphobilinogen deaminase (HMBS; EC 2.5.1.61), is the third enzyme in the heme biosynthetic pathway. It catalyzes the stepwise polymerization of four molecules of porphobilinogen (PBG) into the linear tetrapyrrole, 1-hydroxymethylbilane (HMB). In yeast, apart from 5-aminolevulinic acid dehydratase (ALAD), HMBS has been proposed to play a rate limiting role in the heme biosynthetic pathway. In humans, mutations of HMBS have been linked to acute intermittent porphyria (AIP). In vitro studies on HMBS have suggested certain residues with catalytic importance, but their specific role in the catalysis and the chain elongation is unclear. In the current thesis, classical and quantum mechanical calculations have been used to understand the structural dynamics and catalytic mechanism of HMBS. Molecular dynamics (MD) simulations of the E. coli HMBS through the different stages of pyrrole chain elongation suggested the importance of domain movements and the active site loop movement in the polymerization of four units of PBG. However, in the human HMBS (hHMBS), an additional 29-residue insert wedged between domains 1 and 3 prevents the domain motions. In hHMBS, the cofactor turn movement along with minor domain motions provides space for the addition of first two PBG moieties to the dipyrromethane cofactor, while the movement of the active-site loop away from the active-site region facilitates the accommodation of the next two PBG moieties. Residues R26, D99 and R167 are proposed to be important for the catalysis based on MD simulations and earlier hypothesis. The findings from MD simulations provide a basis to study the catalytic mechanism using quantum mechanical (QM) and QM/MM calculations. The QM calculations were performed on a cluster model consisting of the active site of hHMBS enzyme. The addition of one molecule of PBG to the cofactor is carried out in four steps: (1) protonation of the PBG substrate; (2) deamination of PBG; (3) electrophilic addition of the deaminated substrate to the terminal pyrrole ring of the enzyme-bound cofactor and (4) deprotonation at the carbon atom at the α-position of the penultimate ring. The rate limiting step for the complete mechanism was found to be the deamination of the PBG moiety. The QM/MM calculations demonstrated the significance of protein environment in obtaining accurate energies for the catalytic mechanism. The findings from this study provide a detailed understanding of the chain elongation mechanism using multi-scale modeling and would assist in future work aimed at modulating the activity of HMBS.