Abstract

The computing industry has undergone several paradigm shifts in the last few decades. Fueled by the need of faster computing, larger data and real time processing needs parallel computing has emerged as one of the dominant paradigms. Motivated by the success achieved in distributed computing models and the limitations faced by single core processors, parallel computing is the only alternative for building faster computers. Parallel computing is one of the most challenging areas computer science in the present and developing algorithms and optimization techniques for utilizing the processing power present in a current generation parallel computer is still a very exciting area for research. The parallel computing industry underwent a massive shift with the conventional sequential computers hitting the power wall. It led to the development of multicore and many-core computing chips that had multiple sequential computing cores packed into a single chip. The immediate impact was the need for (re)designing sequential algorithms in order to utilize the computing power of such chips. Combined with the intricate memory and cache structures, parallel algorithms require a higher degree of engineering for the most optimal performance. The many-core revolution started with the release of Graphics Processing Units (GPU) which had a large number of compute cores and offered massive parallelism. With the evolution of the many-core chips, the GPUs found application in graphics, gaming as well as general purpose computation. In the same time frame, the Central Processing Units (CPU) too under went a sea of innovation and emerged as more powerful and mature computing machines. However, the multicore CPUs were mostly ignored in its initial days. With the advancement of accelerator platforms, the CPUs and GPUs are now able to communicate in a more efficient manner. In the recent times there has been quite a few works such as the ones in [79, 91, 43] that shows that hybrid algorithms actually provide better performance and efficiency over conventional accelerator based computing. In this thesis we work towards the development of hybrid multicore computing. Hybrid multicore computing is developing algorithms and optimization strategies for popular computing primitives on an hybrid platform. A hybrid platform is one which contains two or more multicore or many-core devices. There are several challenges towards the efficient algorithm design on hybrid platforms such as that of communication bottlenecks, load balance and synchronization. In this thesis we work towards developing algorithms for some computing primitives such as that of list ranking, sorting and pseudorandomness and some graph algorithms. We experiment on a hybrid platform consisting of a 6-core Intel CPU and Nvidia GPUs of broadly two generations. In our first work we work towards the development of hybrid algorithms for List Ranking. To this end, we explore the algorithmic and analytical issues in hybrid multicore computing. Our case studies involve two different ways of designing hybrid multicore algorithms. The main contribution of this work is to address the issues related to the design of hybrid solutions. We show our hybrid algorithm for list ranking is faster by 50% compared to the best known implementation [139]. This work is followed by a hybrid implementation of comparison sorting. Sorting has been a topic of immense research value since the inception of Computer Science. In this work, we present a hybrid comparison based sorting algorithm which utilizes a many-core GPU and a multi- core CPU to perform sorting. The algorithm is broadly based on splitting the input list according to a large number of splitters followed by creating independent sublists. Sorting the independent sublists results in sorting the entire original list. On a hybrid platform, our algorithm achieves a 20% gain over the current best known comparison sort result that was published by Davidson et. al. [32]. On the above experimental platform, our results are better by 40% on average over a similar GPU-alone algorithm proposed by Leischner et. al. [81]. Our results also show that our algorithm and its implementation scale with the size of the input. We also show that such performance gains can be obtained on other hybrid platforms. The use of many-core architectures and accelerators, such as GPUs, with good programmability has allowed them to be deployed for vital computational work. The ability to use randomness in computation is known to help in several situations. For such computations to be made possible on a general purpose computer, a source of randomness, or in general a pseudo random generator (PRNG), is essential. However, most of the PRNGs currently available on GPUs suffer from some basic drawbacks. It is of high interest to develop a parallel, quality PRNG that also works in an on demand model. In this work, we investigate a hybrid technique to crea

Abstract

The nonverbal speech sounds such as emotional speech, paralinguistic sounds and expressive voices produced by human beings are different from normal speech. Whereas, the normal speech conveys linguistic message and has clear articulatory description, these nonverbal sounds also carry nonlinguistic information but without any clear description of articulation. Also, these sounds are mostly unusual, irregular, spontaneous and nonsustainable. Examples of emotional speech are shouts, happy, anger, sad etc., and of paralinguistic sounds laughter, cry, cough etc. Besides, the expressive voices like Noh voice or opera singing are trained voices to convey intense emotions. Emotional speech, paralinguistic sounds and expressive voices differ in the degree of pitch changes. Another categorisation based upon voluntary control and involuntary changes in the speech production mechanism is also possible. Production of nonverbal sounds occurs in short bursts of time and involves significant changes in the glottal source of excitation. Hence, production characteristics of these sounds differ from those of normal speech, mostly in the vibration characteristics of the vocal folds. Associated changes in the characteristics of the vocal tract system are also possible. In some cases of normal speech such as trills or emotional speech like shouts, the glottal vibration characteristics are also affected by the acoustic loading of the vocal tract system and system-source coupling. Hence, characteristics of these nonverbal sounds need to be studied from the speech production and perception points of view, to understand better their differences from normal speech. Excitation impulse sequence representation of the excitation source component of speech signal has been of considerable interest in speech research, in past three decades. Presence of secondary impulses within a pitch period was also observed in some studies. This impulse-sequence representation was mainly aimed at achieving low bit-rates of speech coding and higher voice quality of synthesized speech. But, its advantages and role in the analysis of nonverbal speech sounds have not been explored much. The differences in the locations of these excitation impulse-like pulses in the sequence and their relative amplitudes, possibly cause differences in various categories of acoustic sounds. In the case of nonverbal speech sounds, these impulse-like pulses occur also at rapidly changing or nearly random intervals, along with rapid or sudden changes in their amplitudes. Aperiodicity in the excitation component may be considered as an important feature of the expressive voices like ‘Noh voice’. Characterizing changes in the pitch perception that could be rapid in the case of expressive voices, and extracting F0 especially in the regions of aperiodicity are major challenges, which need to be investigated in detail. In this research work, the production characteristics of nonverbal speech sounds are examined from both the electroglottograph and acoustic signals. These sounds are examined in four categories, which differ in the periodicity (or aperiodicity) of glottal excitation and rapidness of changes in pitch perception. These categories are: (a) normal speech in modal voicing that includes study of trill, lateral, fricative and nasal sounds, (b) emotional speech that includes four loudness level variations in speech, namely, soft, normal, loud and shouted speech, (c) paralinguistic sounds like laughter in speech, and (d) expressive voices like Noh singing voice. The effects of source-system coupling and acoustic loading of the vocal tract system on the glottal excitation are also examined. The signal processing methods like zero-frequency filtering, zero-time liftering, Hilbert transform and group delay function are used for feature extraction. Existing methods like linear prediction (LP) coefficients, Mel-frequency cepstral coefficients and short-time Fourier spectrum are also used. New signal processing methods such as modified zero-frequency filtering (modZFF), dominant frequencies (FD) computation using LP spectrum or group delay function and saliency computation (a measure for pitch perception) are proposed in this work. A time-domain impulse sequence representation of the excitation source is proposed, which also takes into account the pitch perception and aperiodicity in expressive voices. Using this representation, a method is proposed for extracting F0 even in the regions of subharmonics and aperiodicity, which otherwise is a challenging task. Validation of results is carried out using spectrograms, saliency measure, perceptual studies and synthesis. The efficacy of the signal processing methods proposed in this work, and the features and parameters derived, is also demonstrated through some applications. Three prototype systems are developed for automatic detection of trills, shout and laughter in continuous speech. These systems use

Abstract

Protein domains are the functional and evolutionary units of protein structure and are independent in their functionality and folding pattern. Over a period of millions of years, they tend to accumulate many mutations which can cause a change in their length and structure thereby increasing their functional diversity. Domain comparisons have shown that structural variation is influenced by the number, length and location of insertions and deletions of residues (indels) and these length variations can range from two-three residues to two-fold of the domain size. Length variations at the protein domain level have been known to cause functional impacts like, increasing structural stability, diversifying substrate specificity etc. In this thesis, I have studied length variations within protein domains from sequence, structure and dynamics perspective. Starting from a seed set of PASS2 database, which contains alignments of distantly related protein domains (grouped as protein superfamilies according to SCOP hierarchy), homologous sequences of the seed set were collected from the sequence space systematically. For running this automated search over 731 superfamilies (~7500 protein domains), a pipeline was developed which gathered and validated homologues having length variations. I have also compared the protein domains across updates of PASS2 database in relation to length variation and objectively classified the superfamilies into length variant groups. The collected sequence homologues were further processed leading to identification of indels and finally in creation of a comprehensive resource of length variant protein domains at superfamily level (LenVarDB) which will help users trace length variations/indels in their protein domain of interest. Thereafter, a set of enzyme superfamilies from LenVarDB were selected and analyzed their indel properties. The structural and functional significance of a twenty residue insert in a unique DNA polymerase, terminal deoxynucleotidyl transferase (TdT), was investigated using modeling and molecular dynamics simulation for an in-depth perspective on effect of length variation at functional level of protein. This thesis attempts to create a knowledgebase and provide pointers regarding presence of indels across various protein domain superfamilies, their effects on the structure and function of proteins which can further help in protein engineering and drug targeting. In addition, I also worked on using remote homology detection protocol on rhomboid and subtilisin serine protease families and analyzed interactions occurring at the interaction interface of protein-RNA complexes.

Abstract

The use of fingerprints is an important method for identification of individuals in today's world. They are also one of the most reliable biometric traits, besides the iris. Fingerprint recognition refers to various tasks that are associated with fingerprint identification, verification, feature extraction, indexing and classification. There are a lot of systems, in a variety of domains, that employ fingerprint recognition. That being a given, precision in fingerprint recognition is essential. Identification using fingerprints is done using a feature extraction step, followed by matching of these features. The features that are extracted to be matched depend on the algorithm being used for identification. In large databases of fingerprints, like government records, fingerprints might be indexed before they are matched. This significantly reduces the time required to identify an individual from records, as comparing his/her prints with every entry in the database will take a enormous amount of time. In either case, feature extraction plays an important role. However, feature extraction is affected directly by the quality of the input image. A noisy or unclear fingerprint image might affect the extraction of features strongly. To counter noise in input images, an extra step of enhancement is introduced before feature extraction and matching are performed. The goal of extraction is to improve quality of ridges and valleys in the fingerprint by making them clearly distinguishable, but in the process, also preserve information. The enhancement algorithm should not only not omit or remove existing information from the fingerprint, but also not introduce any spurious features that were not present in the original image. The considerable research into fingerprint recognition, and in fingerprint enhancement, has contributed to the large number of existing algorithms for image enhancement. These include pixel-wise enhancement, contextual filtering, and Fourier analysis, to name a few. Contextual filtering uses specific filters to convolve the input image with. These parameters are determined by the values of certain features at every pixel in the input image. This requires extraction of pre-defined features from the fingerprint. For instance, the filter used at a point is affected by the ridge orientation at that point. Hence, to decide the filter to be used, the ridge orientation at that point needs to be extracted. A similar case can be observed in other types of algorithms too. In this thesis, we propose that unsupervised feature learning be applied to the fingerprint enhancement problem. We use two different scenarios and models to show that unsupervised feature learning indeed helps improve an existing algorithm, and also when applied directly to greyscale images, can complete with robust contextual filtering and Fourier analysis algorithms. Our motivation lies in the fact that there is vast amount of available data on fingerprints; and with the recent advent in deep learning and unsupervised feature learning, in particular, we can use this available data to learn structures in fingerprint images. For the first model, we show that continuous restricted Boltzmann machines can be used to learn local fingerprint orientation field patterns, after which their learning can be used to correct noisy, local ridge orientations. This extra step is introduced between orientation field estimation and contextual filtering. We show that this step improves the performance of matching done on the enhanced images. In the second model, we use a 3-layered convolutional deep belief network to learn features directly from greyscale fingerprint images. We show that having a deep neural network (3 layers) significantly improves the quantitative and qualitative performance of the enhancement. The deep network helps in predicting noisy regions, that were otherwise not reconstructed by the first layer only. In conclusion, we have explored a new direction to attack the fingerprint enhancement problem. We conjecture that it is possible to extend this work to other problems involving fingerprint recognition too. For instance, synthetic fingerprint generation might be accomplished using the convolutional deep belief network trained on fingerprint features. Our experiments show a several potential experiments for the future which can give promising results. (more...)

Abstract

Many past response analyses of the structures under earthquake excitations revealed that both, the maximum displacements and the number of large-amplitude displacement responses, cause higher damage to the structures. In the present study, a new methodology is proposed for seismic damage assessment of a reinforced concrete framed structure, based on the non-linear energy dissipated by the structure, along the completed displacement path. Three methods are proposed to assess the global damage state of the structure under study, for any deformation in. In the proposed methods, the damage index is expressed, at any instant of deformation, as the ratio of non-linear energy dissipated at an instant to the total non linear energy capacity of the structure. The energy dissipation capacity of a structure is estimated by a non-linear pushover curve. The area under the classic pushover curve, which is the plot of base shear versus roof displacement, lacks the consistent meaning to represent the work done by external forces. To calculate the energy, a pushover curve is redefined as a plot of base shear versus displacement at C.G of external force profile, and the area under the curve represents the energy dissipated by the structure, which is equal to the work done by external forces. To calculate the structure energy dissipation capacity, the pushover curve is considered up to 4% of drift or 2/3 of its ultimate base shear. As mentioned earlier, three methods are proposed to calculate the non-linear energy capacity of a structure and are presented as three types of damage methods. Our results indicate that damage method 3 is more efficient in calculating the global damage state of the structure, at any deformation. Many damage methods exist in the literature, based on deformation where strength is not considered in estimating the damage. When a member is in non linear state, as deformation increases the strength caring capacity reduces. In the present study, damage methods are proposed on energy capacity of the structure, it considers both, non-linear deformation and strength degradation of the structure to calculate the damage. Existing damage models define the damage as „0„ for no damage and „1‟ for total damage, but the intermediate damage state was not addressed properly. The proposed damage methods can be used to calculate the global damage at any intermediate state, for any deformation and estimates the margin left for total collapse. These damage methods are based on non-linear pushover analysis. A quick assessment of damage at less cost is the advantage of the proposed methods. In the present study, the proposed damage methods are applied for 6 and 10 storey RC bare framed structures to calculate the damage state of the structure and are compared with other damage models that exist in the literature. The results were comparable and the proposed methods depicted results closer to real behaviour of the structure in which strength degradation is considered. A numerical study was also carried out for 3 benchmark structures, with an aspect ratio (height to width) of 3, 1 and 0.3, to define damage pattern. Among the three damage methods, damage method-3 exhibited good results comparable to real behaviour. Damage method 3 has been used to represent the deflection profile of the structure. The present study also includes the assessment of energy dissipation capacity of each member for any global damage state, to know the contribution of each member for global performance. The member energy is calculated in terms of non-linear strain energy stored in the member and presented as percentage of global energy dissipated by the structure. One important conclusion from this study is that some beam members, dissipated higher strain energy did not fail but the column with less strain energy failed. The reason can be axial load, but when global damage is estimated by combining local damages with higher weighting factors for high energy dissipated members, leads to incorrect estimation of global damage state. Global damage should be estimated by using global methods not by combining local damages. Selected frames for the analysis to verify the proposed methods have been designed per Indian Standards and pushover analysis was performed using the tool SAP2000. Analysis was performed for two cases: first, considering flexure failure and the second one considers flexure and shear failure together, to identify which failure occurs first. Results indicated that all the members failed under flexure and remained safe in shear, during pushover analysis.

Abstract

Verification of general reachability conditions and controller synthesis satisfying the same can be efficiently performed on finite state automata and timed automata. As such, a standard technique for verification and controller synthesis on non-automata specifications is to abstract the specifications as finite state automata or timed automata. In this thesis, we extend the paradigm of automata based abstraction in the following two directions: • A subset of timed computational tree logic (TCTL), called interval assumptions, is abstracted as a type of timed automata called continuous pure signal input output automata. This abstraction is done for verifying guarantees (or requirements) specified in TCTL for timed automata under environments specified as interval assumptions. The approach is useful for modular verification of manufacturing systems, standard small scale examples of which include the Turntable and Production Cell. This is the first attempt to use a subset of TCTL as assumptions in modular verification. • Near-complete abstraction of bounded input linear control systems as finite state metric transition systems. Near-completeness is a parametrized notion of completeness of an abstraction, introduced in this thesis. The abstraction as a finite state metric transition system allows controller synthesis to be performed on the finite state automaton corresponding to the finite state metric transition system. The novel contributions of this work are defining near-completeness and building near-complete models of bounded input possibly unstable linear control systems. Hitherto approaches for complete abstraction either considered stable systems, or else unstable but unbounded input systems. We extend the extant approaches to unstable plus bounded input systems, while replacing the completeness criterion with the near-completeness criterion.

Abstract

Query optimization in relational database systems is a topic that has been studied at depth, in both stand alone and distributed scenarios. Modern day optimizers became complex with focus on increasing quality of optimization and reduction in query execution times. They employ a wide range of heuristics and considers a set of possible plans called plan space to find the most optimal plan to be executed. However, with the advent of big data, more and more organizations are moving towards map-reduce based processing systems for managing their large databases, since it outperforms all the traditional techniques for processing very huge amounts of data and still runs on commodity hardware thus reducing the maintenance cost. In this thesis, we describe the design and implementation of a query optimizer tailor made for efficient execution of SQL queries over map-reduce framework. We rely on the traditional relational database query optimization principles and extend them to address this problem. Our major contributions can be summarized as follows 1. We proposed a statistics based approach for optimizing SQL queries on top of map-reduce 2. We designed cost formulae to predict the run time of joins before executing the query 3. We extend the traditional plan space to consider the bushy plan space which leverage the massively parallel architecture of map-reduce systems. We designed three algorithms to explore this plan space and use our cost formulae to select the plan with the least execution cost 4. We developed a task scheduler based on max flow min cut algorithm for map-reduce shuffle that minimizes the overall network IO during joins. This algorithm uses the statistics collected from data and formulates the task assignment problem as a max-flow min-cut problem in a flow graph on nodes and solving it we get the overall minimal IO in shuffle phase 5. We show the performance enhancements from the above features using TPCH workload of scales 100 and 300 on both TPCH benchmark queries and synthetic queries Our experiments show run time enhancements of up to 2x improvement in the query execution time and up to 33% reduction in the shuffle network IO during map-reduce jobs.

Abstract

India is a country which is made up of multiple traditions and culture which get reflected in every aspect of life. Brick masonry is the traditional material used for construction of walls which are load bearing and also to enclose in RC moment resisting frames. The use of brick masonry is inevitable due to the ease in construction, availability of material and availability of good workmanship. Along with this, referring to the seismicity of the country, low to high magnitude earthquakes are also inevitable. In this regard, the knowledge of seismic behaviour of brick masonry infill walls is a necessary aspect in order to contribute to the growing technology. This knowledge is must if the structures are present in higher seismic zones. In context with the past earthquake damages to buildings, the strength based design currently presented in design codes is being felt to be insufficient for withstanding the dynamic forces induced hence the focus of research is being shifted to performance based design. The knowledge of seismic vulnerability of the RC frame due to the presence of brick masonry infills is necessary for performance based design. In this respect, with proper literature review on the existing research on modeling and analyses of brick masonry infill walls a set of case studies have been carried out. Reliable numerical model for this study is verified and finalised. Pushover analysis is used as a tool for observing the different parameters of capacity of structure. The AEM analysis is compared with conventional FEM strut modeling to understand the applicability of the method to this study. The variation of global capacity of the structure with the change in number of bays and storeys is observed by proper analysis. The effect of openings on the behaviour of the RC frame is observed. The short column and weak storey effects are dealt by considering a case study. The weak storey is assumed to be located at different floors and four analyses are run. The comparison between structure with and without short columns is studied. The differences between structure with and without soft storey are observed. To verify the provisions of current standard code of practice IS 1893 – 2002 a case study is performed and results are obtained. For all these analysis final conclusions and results interpretations are drawn.

Abstract

In the recent past, the impact of remote sensing on various earth science applications has significantly increased due to the launch of a vast number of satellites. Remote Sensing now provides data at various scale and granularity which has led to its wide applications. Due to physical limitations in sensor design, there is an inherent trade off between spatial and spectral resolution of these images. Hence, most sensors aim at requirements of few specific applications. This has lead to the under use of vast amounts of data available for various research tasks. Multi-sensor data fusion aims at integrating sources with different strengths such that the final or fused product has strengths of all individual sources. Multi-sensor data fusion has allowed more accurate use of remote sensing data and also allowed new applications to exploit remote sensing datasets. Data can be fused at various levels - pixel, feature or decision level depending on the task at hand. Specifically, pixel level image fusion has advantages in that it involves the raw input data itself and returns a more useful fused dataset with better specifications than that of input data. This makes pixel level fusion independent of the domain or research task and hence makes it efficient and easy to implement. Numerous algorithms have been developed for pixel level fusion. Most algorithms only aim at improving overall visual quality and hence lead to distortion of spectral properties of individual bands which leaves the fused image unsuitable for image processing tasks such as classification. Here, we present two algorithms that aim at Image Enhancement while preserving spectral information of the participating bands. First, we present GLSI (GaussianLinear Stretching Image) Enhancement technique which aims at improving spatial resolution of multispectral bands using high resolution panchromatic band. GLSI transfers spatial details into each band independent of each other and thus preserves the spectral distribution of each band. GLSI is a window based technique where the local statistics of the window is used to create linear relationships between the corresponding windows in the two different spatial resolution bands. Second, we present PA, a hyperspectral image enhancement technique that uses multispectral data as high spatial resolution input. This method first simulates multispectral bands using hyperspectral bands. Then spatial detail is transferred at multispectral level by doing enhancement of simulated multispectral bands to generate fused or enhanced multispectral bands. Then, fused hyperspectral bands are generated by doing vector decomposition. Results and comparison with baseline algorithms demonstrate that proposed algorithms have the potential of doing image enhancement while preserving spectral characteristics.

Abstract

Robot manipulation in clutter with objects in physical contact remains a challenging problem till date. The challenge is posed by interaction involved among the objects at various levels of complexity. Understanding positional semantics of the environment plays an important role in such tasks. The interaction with surrounding objects in the environment must be considered in order to perform the task without causing the objects fall or get damaged. In our work, we learn the semantics in terms of support relationship among different objects in a cluttered environment by utilizing various photometric and geometric properties of the scene. To manipulate an object of interest, we use the inferred support relationship to derive a sequence in which its surrounding objects should be removed while causing minimal damage to the environment. We believe, this work can push the boundary of robotic applications in grasping, object manipulation and picking-from-bin, towards objects of generic shape and size and scenarios with physical contact and overlap. In the first part of the thesis, we aim at learning semantic interaction among objects of generic shapes and sizes lying in clutter involving both direct and indirect physical contact. Three types of support relationships are inferred: "Support from below", "Support from side", and "Containment". Subsequently, the learned semantic interaction or support relationship is used to derive a sequence or order in which the objects surrounding the object of interest should be removed without causing damage to the environment. The generated sequence is called Support Order. We have proposed and analysed two alternative approaches for support inference. In the first approach "Multiple Object Support Inference", support relations between all possible pairs are inferred. In the second approach "Hierarchical Support Inference", given an object of interest, its support relationship with other graspable objects is inferred hierarchically. The support relationship is used to predict the "support order" or the order in which the surrounding objects need to be removed in order to manipulate the target object. In the second part of the thesis, we attempt to learn the semantic interaction among different objects in clutter using multiple views. At first, support relationship among objects in each view is inferred. Then the inferred support relationships are combined to define support relationships across multiple views. The combined global support relationship is used to recover missing support relations and predict the support order. Support order is the order in which objects surrounding an object of interest should be removed. The support order predicted using global support relationship incorporates hidden objects and missing spatial support relations. We have created two RGBD datasets consisting of various objects used in day-to-day life present in clutter. In "Indoor dataset for clutter", 50 cluttered scenes are captured from frontal view using 35 objects of different shapes and sizes. In "Indoor multiview dataset", 7 cluttered scene are captured. Each scene each captured from multiple views. In this dataset, total 67 images are captured using 9 objects of different shapes and sizes. The dataset is made publicly available for the research community around the world. We explore many different settings involving different kind of object-object interaction. We successfully learn support relationships and predict support order in these settings. It can play significant role in extending the scope of manipulation to cluttered environment involving both direct and indirect physical contact, and generic objects. Keywords: Robotic Vision, Support Relations, Support Order, RGBD, Semantic Interaction, Clutter, Multiple Views