Abstract

The problem of evaluating software architecture is an important problem of software engineering. The purpose of the architecture evaluation of a software system is to analyze the architecture to identify potential risks and to verify that the quality requirements have been addressed in the design. Different techniques have been developed to evaluate a software architecture. Most common among these techniques are model based approaches, metric based methods and scenario based analysis. Service-Oriented Architecture (SOA) is an architectural approach (or style) for constructing complex software-intensive systems from a set of universally interconnected and interdependent building blocks, called services. Services used in composite applications may be brand new service implementations, they may be fragments of old applications that were adapted and wrapped, or they may be combinations of the above. The emergence of SOA as an approach for integrating applications presents many new challenges to organizations resulting in significant risks to their business. Particularly important among those risks are failures to effectively address quality attribute requirements such as performance, availability, security, and modifiability. Hence, it becomes necessary to evaluate a service oriented architecture based application in the context of quality attributes. In this dissertation, our aim is to investigate the limitations of using scenario based software architecture evaluation approaches in SOA paradigms. We investigate that most of the current approaches in the literature of software architecture, do not consider the factors that are more specific in SOA based applications. For example, to the best of our knowledge, current evaluation approaches do not address the quality issues that arises due to a SOA governance lifecycle. There must be a mechanism to investigate how governance policies are impacting the quality attributes (positively or negatively). We show that a governance lifecycle is a critical element of any SOA based application and must be analyzed in the context of quality attributes. Current software architecture evaluation methodologies also have not been studied and used in the areas of modern cloud based services. In brief, we look at the problem from following different angles: (1) evaluating a SOA governance model; (2) analyzing data security risks in cloud based service environments; and (3) evaluating the attack surface and root cause of an attack in an SOA based enterprise application. Security is considered as the most prominent quality attribute in software applications. Therefore, throughout our work, we primarily focus on security analysis, out of all the quality attributes. The impact of SOA governance mechanism on the organization’s quality attributes is largely not studied or evaluated in a structured manner. To overcome this problem, we propose SAGE (Service Oriented Architecture Governance Evaluation) as a quantitative approach, to evaluate the impact of SOA governance policies on prominent quality attributes. Our approach facilitates an exhaustive quantitative impact analysis to evaluate the effectiveness of SOA governance policies. This can be further used to estimate the current maturity level of any SOA based enterprise. To evaluate the data security risks in cloud based services, we did a survey of prominent security issues in current cloud computing environments. Based on these issues, we propose a risk analysis approach for analyzing the data security risks. This approach can be used by any potential service user, before putting his confidential data into a cloud computing environment. As a solution to the security analysis in SOA based enterprise applications, we present an approach to compute the attack surface in a SOA based enterprise application. We also discuss that how we can map an attack surface from a service layer to a business process layer. Further, we present an approach to investigate the root cause of an attack. This approach can be used directly by any SOA based enterprise to evaluate the security and therefore a possible reduction in security attacks. In our work, we attempt to answer the following questions: (1) Are the existing software architecture evaluation approaches sufficient in service oriented paradigms? (2) If no, what are the areas that remain unexplored? (3) How to address these unexplored areas? Our study brings out some interesting results. We show that evaluation of a SOA governance lifecycle is necessary to estimate the quality and dynamic behavior of the composed application. Our work also unveils various security issues in cloud based service environments. The presented work is an initial attempt to make the SOA evaluation and management more structured and effective.

Abstract

Sentence realisation involves generation of a well-formed sentence from a bag-of-words. Sentence realisation has wide range of applications ranging from machine translation to dialogue systems. In this thesis, we present five models for the task of sentence realisation. The five models proposed are sentential language model, subtree-type based language models (STLM), head-word STLM, part-of-speech (POS) based STLM and marked head-POS based LM. The proposed models employ simple and efficient techniques based on N-gram language modeling and use only minimal syntactic information as dependency constraints among the bag-of-words. This enables the models to be used in wide range of applications that require sentence realisation. We have evaluated the proposed models on two different types of input (gold and noisy). In the first input type, dependency constraints among the bag-of-words are extracted from treebank which is manually transcribed and in the second input type, the dependency constraints among the bag-of-words are noisy as they are automatically extracted from a parser. We have evaluated the models on noisy input in order to test the robustness of our models. From the results, we observed that the models performed well even on the noisy input. We have achieved state-of-the-art result for the task of sentence realisation. We have also successfully tested a graph based nearest neighbour algorithm for the task of sentence realization. We have shown that using the graph-based algorithm, the computational complexity can be reduced from factorial to quadratic at a cost of 2% reduction in the overall accuracy. This method makes our module suitable for employment in several practical applications.

Abstract

The field of electronics has undergone tremendous changes in recent times. The innovations in it have been happening in multiple perspectives, among which the growth of portable computing devices has lead to a new wave of miniaturization and low power development. The rise of high bandwidth internal devices like GPUs (Graphic Processing Units), Multicore processors etc has lead to the growth of high frequency busses like PCI (Peripheral Component Interconnect), the Northbridge/Southbridge FSB (Front side bus) etc. Also the increasing use of multimedia streaming and external storage devices has lead to a massive increase in memory-intensive applications. The need for a simpler protocol has made most of them to be block data transfer systems with the final usage in caches, DMA (Direct Memory Access), Video data transfer etc all tending to be block data transfer utilizing some form of a buffer. I/O pads driving external busses dissipate a major portion of this power as they drive large capacitances, and operate at a higher voltage. This forms a good part of the overall power consumption of a system. In this thesis, a novel technique, Transition Inversion, to reduce power consumption of buffered busses is proposed. This work outlines a data coding protocol by which these transitions can be reduced for block data transfer over buses such as DMA, cache lines etc. Block data transfers generally occur through data buffers. The prior knowledge of the data to be transmitted, when it is stored in the buffer, is exploited in serial fashion to reduce transitions on every bus line. The technique considers a buffer of data to be a collection of bitstreams running in parallel over multiple lines. The transitions are counted in a bit serial fashion and used to determine whether the transitions in any given bitstream have to be inverted. This way the data running on any given line sequentially is encoded such a way it will have a reduced number of transitions. The technique is implemented in an optimized fashion using pipelining so that it can be used in practical systems with only a slight compromise in performance. This is achieved by calculating the decision as the data is being loaded on to the buffer and doing the encoding on the fly. This is one aspect which is lacking in most existing algorithms as they are not amenable to low delay implementation. The critical parameter of delay, which limits bandwidth, is reduced by 64% with the proposed technique and the pipelined implementation. Also the proposed technique and implementation does not require any extra bus lines to be used as is wont with most existing techniques. This does away with the rise in PCB (Printed Circuit Board) fabrication costs. Theoretical analysis of transition inversion showed it to be reducing transitions that is, independent of the increase in bus width. Most existing techniques suffer with increasing bus widths, requiring mitigation factors that themselves increase wiring requirements. Also transition inversion scales slower in hardware complexities compared to another comparable technique which makes it suitable for the increasing data widths in modern busses. The analyses showed that the technique is suitable for modern bus architectures in terms of delay, space complexity and the extra overhead power consumed. It was seen that the bandwidth need not be limited and still a good amount of power saving with the overhead was obtained.

Abstract

Ever since the induction of Integrated circuits into mainstream usage, numerous research efforts have been made into optimizing the circuits implemented on silicon with respect to Power, Area, Time (PAT), and most recently reliability. Due to the recent insurgence of mobile devices, low power design techniques are being given more emphasis. Power dissipated can be reduced at the device, circuit, system architecture, or software design levels. The focus of this work is aimed towards the reduction of power dissipation in electronic systems, by way of using inexact logic in implementing systems, where error can be tolerated, and/or neglected. An inexact logic circuit is constructed by selectively converting minterms/maxterms of its Boolean function into don’t cares. The intuition in doing this is that by converting only a small fraction of minterms/maxterms into don’t-cares, an inexact version of the Boolean function can be synthesized with a significantly lower area-power-delay footprint than the exact Boolean function. Decision making circuits, which are generally sensitive to errors, have been chosen as the subject of analysis. Several applications are presented where inexactness can be applied, and their performance, in terms of power and system accuracy is quantified with varying levels of inexactness. This thesis also outlines a set of general guidelines to design inexact circuits, on a per case basis. To simplify the process, a heuristic framework to generate inexact circuits with varying levels of inexactness has been implemented. The above mentioned applications are classified into 3 categories based on the impact of the decision made, on system accuracy. These categories are: No impact, Tolerable impact, and Significant impact, on system accuracy. For applications with no impact, the only deciding criteria in introducing inexactness are the overall improvement in power and speed. For applications under the tolerable impact category, a system accuracy parameter should also be considered in validating an inexact circuit. For applications with significant impact, inexactness is seldom tolerated, as system accuracy is critical. Bus coding, Median Filter based Image blurring, and Non-Modular Redundancy (NMR), falling under the no impact, tolerable impact, and significant impact categories respectively share the majority voter as a common decision circuit used. A Least Recently Used (LRU)-variant replacement algorithm for Translation Lookaside Buffers (TLB), and a DCT threshold based image blurring process, with the former having no impact on system accuracy and the latter having tolerable impact, share a comparator as a decision circuit. Different inexact versions of these decision circuits are generated and their performance parameters with respect to the applications are measured. A comparison has been made with the levels of inexactness and the power dissipation of the system and the system performance. The results obtained promise a drastic reduction in power dissipation, up to 300%, with tolerable deviation in system accuracy. Although critical path delay was not a parameter for optimization, a gain of up to 30% was observed on this front. The chip area and static power dissipation is also reduced significantly. The results obtained validate the use of inexact logic in applications which are either impervious or tolerant to the errors produced due to the inexactness. This provides a new avenue to low power system design, which can be used in congruence to other circuit design, and system level design techniques.

Abstract

Interconnects play a major role in deep submicron (DSM) technologies such as 90nm and below. While gate delay dominated interconnect delay in earlier technologies, it is no longer the case and delays associated with interconnects are becoming increasingly important. This is because in DSM technologies, interconnect can no longer be seen as a simple resistor but the associated parasitics such as capacitance and inductance also need to be considered. Thus any signal propagating through such an interconnect can be expected to be delayed. Buffer insertion is one popular technique to reduce (eliminate) the delay. In this technique, buffers are placed at regular intervals along an interconnect that seeks to restore the signal each time it is affected by the parasitics. However, buffers themselves have certain switching time that contributes to delay. A large number of such buffers along an interconnect can thus contribute to overall delay to signal propagation. Also buffer switching contributes to power dissipation. Further in DSM technologies, leakage power is a major problem and buffers may consume power even when they are not switching. Thus there is an urgent need to evolve techniques that while reducing the overall delay, also consume lesser power, dynamic as well as static. In this thesis, Schmitt trigger as an alternate to buffer to reduce delay and power in interconnects is examined. The most favorable feature of Schmitt trigger is it’s adjustable threshold voltage, and since it can be controlled, the threshold voltage can be chosen to be above or below Vdd=2 a voltage at which buffer normally operate. Thus a Schmitt trigger can be designed to switch faster than a buffer leading to a reduction in delay. Further, the adjustable low-voltage threshold of the schmitt trigger handles more noise and voltage glitches as compared to buffer. Proposed approach is first implemented for linear interconnects of various lengths and then on buses which are groups of interconnects. It is shown that the proposed approach is better in terms of delay, power and crosstalk noise reduction compared to that of buffers.

Abstract

Blind classification of digital modulations finds applications in defense and software defined radio, and higher-order statistics have attracted lot of attention in this regard. Multipath propagation severely degrades the performance of the blind classification algorithms. Recently, some work has been reported on classification in multipath channels where they perform blind channel estimation based on higher-order statistics, and use the channel estimate in computing the features of interest. However, some of these methods are not applicable to PAM and, 8- and 16-PSK modulations. In our thesis, we consider 9-class problem which includes PAM and PSK constellations and use a blind channel estimation method, in which we combine the magnitude response of the channel obtained from second-order statistics with the phase response derived from higher-order statistics. The channel estimate so obtained is used in computing the required features. Combining these features with the distance metric, we develop an algorithm for hierarchical classification of the underlying modulations. We illustrate the effectiveness of our method in different multipath scenarios using simulations. Specifically, we compare the classification performance obtained using our method of channel estimation with that using higher-order statistics based channel estimation. We also briefy bring out why the higher-order statistics based channel estimation methods, proposed in the context of modulation classification, fail in the above cited PAM and PSK constellations.

Abstract

In the future, as communication networks become complicated new innovative techniques are re- quired to improve the performance of these networks. Error correction methods are being used to design transmission schemes which deliver optimal data rate to the users. Retransmissions schemes in the pres- ence of feedback channel are another way to improve the performance of the network. In this thesis we design retransmission schemes for wireless broadcast networks which use simple network coding tech- niques. We analyze simple baseline schemes for retransmission using network coding principles. Two simple feedback channels with different amounts of feedback available are considered and algorithms are designed for them. In particular we consider a wireless system with a shared feedback channel, wherein the number of transmission errors can be estimated by polling. The feedback information is used to develop analytical and statistical models to characterize error correction and employ these results to design efficient retransmission algorithms. Optimization of algorithm is done to maximize the error correction performance for a limited retransmission bandwidth. We compare the performance of these algorithms with the various baseline schemes. Substantial improvement in terms of bandwidth, power required for transmission of data and data rate is achieved that is denoted by the number of retransmis- sions required. Various tradeoffs in the design and performance of these algorithms are discussed and their results are analyzed.

Abstract

Navigational systems play a vital role in transportation services, aviation, ground and maritime operations, tracking and surveillance. Route planning and its application are very important in many domains such as location based services, advanced traveler information systems, and more so in GIS applications. The common applications are shortest path analysis and finding the closest facility. But in the real world, there are many deviations from and constraints to the shortest path between the source and destination, and it is important to consider these while planning the route that has to be traversed. Constraints can be either internal to the road network or external to it. The examples for internal constraints are time dependent one-way streets, road closed for maintenance (though it exists on the road network), etc. External constraints don’t alter the network but affects the route planning or its choice. External constraints are like the fuel (petrol/gas) that can last only till a specified distance and necessitates a visit to another facility (gas station) before proceeding to the destination, or visiting another unplanned facility prior to the closure of the facility (pharmacy or bank). This class of problems is defined as Externally Constrained Routing (ECR) query problems.
We present four solutions, other than the naive approach, for finding the optimal route for a road network that is externally constrained. The solutions are examined with parameters affecting the performance, e.g., number of queries, number of edges, constraint distance, network distribution (sparse vs dense networks) and facility density. The algorithms proposed here also minimize the total route length from the source to the destination, with a stop at the facility enroute. All the five approaches are evaluated based on storage space, computational efficiency and query response time. Our experiments on Synthetic and Real world road network datasets show that among the proposed algorithms, Path dependent facility mapping (PDF) is computationally very efficient than the other approaches, assuming storage space is not a constraint. Also, PDF will result in lower power consumption, a vital issue for mobile devices. Comparing the experimental results of Pair path processing (PPP) and Euclidean range query approach (ERQ), it can be said that though PPP performs much better than ERQ for synthetic datasets, it is similar for real world datasets. In addition, the preprocessing time required in ERQ is much less than PPP. Hence the ERQ can be considered efficient and also a good approximate solution in the current real world networks.
The current approach of treating all the related features as part of the road network (single layer approach, features as vertices) leads to cumbersome updates and query processing approaches for each feature interaction. So, separation of facilities into layers on the road network, as handles by a Geographic Information System (GIS), is needed to improvise query processing and updates to the features database. This work proposes a generalized framework to handle the features as separate GIS layers above the route network layer.

Abstract

Terrains are of great interest in flight simulators, geographic information systems and computer games. In computer graphics, terrain rendering is a special case because of their bulk. They cannot be handled as a single entity like other object models like teapots, cars and crates. Triangulated irregular networks of terrains are typically created by simplifying a dense representation. Such representations are popular in GIS and computational geometry. The recent trend in graphics is to use regular grid representations since they go well with today’s graphics hardware. We explore different representation techniques to render terrains in this thesis. We look into real-time rendering, editing, and physical interaction with external objects on terrains. We also present a representation for efficient rendering of spherical terrains. Apart from rendering terrains realistically, we develop a method to render terrains artistically with painterly abstraction as well. We create a system that exploits the power and flexibility of the modern GPUs to store, render, and manipulate terrains with minimal CPU involvement (CPU load < 4%). The central idea is to use a regular-grid representation, hierarchically divided in fixed size blocks/tiles that change in resolution. The potentially visible portion of the terrain is cached at the highest necessary resolution and is rendered from the GPU. The cache is updated with the viewerpoint. Lower resolutions used for farther areas of the terrain can be constructed from the cache on the GPU. Todays GPUs have a limited capability to generate geometry within itself. Thus, the CPU can send a light geometry template which is expanded to the triangles by GPU. The CPU performs a coarse culling of the tiles with the GPU performing fine culling. Our system enables the terrain to be modified procedurally or edited interactively on the GPU with no CPU involvement. The terrain can also interact with a large number of external objects in real-time with all the physics calculations done on the GPU. Terrains can also be mapped over a sphere for a planetary structure. However, terrains on sphere require a different representation due to the pole singularity of latitude-longitude representation. A 2D grid of height cannot be mapped directly on a sphere with uniform triangle count. Spheres can be rendered uniformly using Hierarchical Triangular Mesh (HTM) but the representation does not fit with 2D grid of heightmaps. We present a unified representation of HTM and clipmapping (flat terrain rendering technique) to render spherical terrains. Our representation works at any distance from the planet/sphere without any scripted work arounds. The regular nature of terrain data also enables us to render the samples in a required order with no overhead of sorting. This introduces the possibility of applications which require sorted ordered vi vii triangles. We explore non photo realisitic rendering of terrains. Artistic painterly appearance and the impression of terrains is created by effectively rendering several translucent brush strokes in a back to front order. The strokes are located in 3D space for frame-to-frame coherence during animation. The strokes are oriented along the slope of terrain analogous to the way artists paint on canvas. We use shaders to render strokes in real-time. A level of detail scheme is used to maintain a uniform stroke density in screen space. Various styles can be achieved with different stroke variations. We achieve real-time painterly rendering with a combination of object space positioning and image space rendering of strokes.

Abstract

The amount of multimedia content produced and made available on Internet and in professional and personal collections is constantly growing. Equally increasing are the needs in terms of efficient and effective ways to manage it. This has led to a great amount of research into content based retrieval and visual recognition. In this thesis, we focus on efficient visual content analysis in images and videos. Efficiency has emerged as one of the key issues with increase in quantity of data. Understanding of a visual content has several aspects associated with it. One can concentrate on recognizing the inherent characteristics of image (independent or from a video) like objects, scene and context. Searching for a sequence of images based on similarity or characterizing the video based on its visual content could be some other aspects. We investigate three different approaches for visual content analysis in this thesis. In the first, we target the detection and classification of different object and scene classes in images and videos. The task of classification is to predict the presence of an object or a specific scene of interest in the test image. Object detection further involves localizing each instance of the object present. We do extensive experimentation over very large and challenging datasets with large number of object and scene categories in it. Our detection as well as classification are based on Random Forest combined with combinations of different visual features describing shape, appearance and color. We exploited the computational efficiency in both training and testing, and other properties of Random Forest for detection and classification. We also proposed enhancements over our baseline model of object detector. Our main contribution here is that we achieve fast object detection with accuracy comparable to the state of art. The second approach is based on processing continuous stream of videos to detect video segments of interest. Our method is example-based where visual content to be detected or filtered is characterized by a set of examples available apriori. We approach the problem of video processing in a manner complimentary to that of video retrieval. We begin with a set of examples (used as queries in retrieval) and index them in the database. The larger video collection, which needs to be processed, is unseen during the off-line indexing phase. We propose an architecture based on trie data structure and bag of words model to simultaneously match multiple example videos in the database with the input large video stream. We demonstrate the application of our architecture for the task of content based copy detection (CBCD). xiii xiv In our third and final approach we apply pattern mining algorithms in videos to characterize the visual content. They are derived out of data mining schemes for efficient analysis of the content in video databases. Two different video mining schemes are employed; both aimed at detecting frequent and representative patterns. For one of our mining approaches, we use an efficient frequent pattern mining algorithm over a quantized feature space. Our second approach uses random forest to represent video data as sequences, and mine the frequent sequences. We experiment on broadcast news videos to detect what we define as video stop-words and extract the contents which are more important such as breaking news. We are also able to characterize the movie videos by automatically identifying the characteristic scenes and main actors of the movie. The ideas proposed in the thesis have been implemented and validated with extensive experimental results. We demonstrate the accuracy, efficiency and scalability of all the three approaches over large and standrad datasets like VOC PASCAL, TRECVID, MUSCLE-VCD as well as movie and news datasets.