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.

Abstract

Information Retrieval systems like Web search engines are often used by people to find information of their interest. Despite the success of these systems, they are not sophisticated enough to provide precise information for users requests. To address this problem, complex Information Access systems called Question Answering systems have been developed. They aim at finding exact answers to natural language questions in a large collection of documents (such as World Wide Web). One of the most obvious limitations in the performance of many Question Answering systems is their inability to find text passages where candidate answers can be found. Earlier research on the poor performance of passage retrieval highlighted the terminological gap problem i.e., passages holding the answer to a question have semantic alterations of original terms in the question. In this thesis, we proposed two different techniques to reduce this problem. Query expansion is a widely used technique in Information Retrieval to reduce the terminological gap problem. First, we present a novel passage retrieval methodology which expands the query inherently. This methodology leverages Statistical Machine Translation model for Information Retrieval to retrieve a ranked set of passages given a question. The retrieval within this model includes two steps: estimation and ranking. In the estimation step, multiple translation models are constructed using a statistical alignment model. We perceive each such translation model as an answer type profile. During ranking, based on the answer type of the question its corresponding answer type profile is used to retrieve relevant passages. Our experimental analysis on the performance of this retrieval methodology showed significant improvements over different standard retrieval models including TFIDF, Okapi BM25, Indri and KL-divergence. We found that simple statistical alignment models like IBM model 1 are more suited for passage retrieval. We also showed that our methodology addresses the problems of synonymy and polysemy. Previous studies on explicit query expansion methods like pseudo relevance feedback, and methods based on external knowledge sources likeWordNet,Wikipedia or Web have shown to improve the performance of Information Retrieval systems. We proposed a novel query expansion method using Wikipedia. Our methodology uses text content, category structure, and link structure of Wikipedia to generate a set of terms semantically related to the question. As Boolean model allows a finegrained control over query expansion, these semantically related terms are added to the original query to form an expanded Boolean query. Our experimental analysis on the performance of these expanded queries on Lucene, an open source retrieval system, showed significant improvements over seed queries. We also analyzed the performance of expanded queries based on different scoring methods utilized in selecting query expansion terms and for different query expansion lengths. Adding to the above contributions which focused on reducing the terminological gap between query and passage, we explored the necessity of passage priors in ranking passages. Document Retrieval assumes that a document is independent of its relevance, and non-relevance. The same assumption is being carried forward in passage retrieval systems in the context of Question Answering. We relax this assumption and explore the necessity of passage priors being relevant and non relevant in ranking passages given a query. We describe a mutual information measure for estimating these priors and a simple method for identifying relevant and non-relevant text to a question using the Web and AQUAINT corpus as information sources. Our experimental analysis of using passage priors as a re-ranking step on top of language models including Indri and KL-divergence showed that passage priors are necessary in ranking passages.

Abstract

Online shopping has become a very popular web application in the recent times and received lot of attention from both consumers and retail merchants. With this growing popularity, lots of information is generated on many products to assist users across the globe. This has resulted in information explosion with lots of information for the consumers to digest. This has created need for techniques to identify useful and relevant content for the consumers from the huge amounts available. In this thesis, we have explored application of information extraction techniques for extracting relevant product information. We have focused on the following subproblems in the context of products: Attribute Extraction, Attribute Ranking. We have explored algorithms to automatically extract product attributes from text descriptions. We have come up with unsupervised methods which do not require any domain specific information for extraction. Our algorithms are based on the hypothesis that attributes should repeat across descriptions. We have explored two clustering methods in this work for extraction : Noun Phrase(NP) Clustering and Word Clustering. In the first method, clusters of noun phrases are computed so that all the phrases describing an attribute are grouped together and a representative attribute is extracted from each cluster. In the second method, we cluster words appearing in the descriptions such that all the words related to an attribute are grouped together in one cluster. We construct a graph from the word occurrences in descriptions and compute word clusters using a graph clustering algorithm. Attributes are extracted from word clusters using word associations inside a cluster. We have throughly evaluated our methods by conducting various experiments. Our experiments show that the methods are robust and extract product attributes accurately. We have also compared the two algorithms and presented an analysis on the trade offs in the two approaches. We have defined attribute ranking in the context of product comparison and came up new features for ranking the attributes. We have also designed a new kind of summaries called Comparative Summaries that delivers majority of the comparable content found in an input set of documents. We have presented how comparative summaries could be generated for products using our attribute extraction and ranking algorithms. We have carried out experiments to evaluate the performance of our ranking algorithm and showed that it is effective in identifying useful attributes.

Abstract

The MapReduce paradigm has become a popular way of expressing distributed data processing problems that need to deal with large amount of data. MapReduce is used by a number of organizations worldwide for diverse tasks such as application log processing, user behavior analysis, processing scientific data, web crawling and indexing etc. Many organizations utilize cloud computing services to acquire resources needed to process MapReduce jobs on demand. As a result of the popularity of using MapReduce in the cloud, cloud services such as the Amazon Elastic MapReduce have also become available. The Apache Hadoop framework is the leading open source implementation of the MapReduce model. It also provides a distributed file system (HDFS or the Hadoop Distributed File System). Hadoop is also the most popular MapReduce framework, and is being used by more than 75 organizations worldwide. It is designed to be scalable and robust, and runs on small single node clusters, to very large clusters containing several thousand compute and storage nodes. Despite the popularity and stability of Hadoop, it presents many opportunities for researching new resource management algorithms. Admission Control, Task Assignment and Scheduling, Data Local Execution, Speculative Execution and Replica placement are some of the key challenges involved in resource management in Hadoop. Resource management in Hadoop is complicated by the fact that the resources available are dynamic in nature because of frequent node failures. In this thesis, we approach two of the above problems: Admission Control and Task Assignment. Admission Control is the problem of deciding if a new job submission should be accepted for execution on a MapReduce cluster. An admission controller, or the module that handles admission control should make sure that jobs accepted into the cluster do not overload resources. Another important requirement is that the accepted jobs should try to maximize the utility of the service provider, which in this case is the Hadoop cluster owner. We propose an admission control algorithm that selects incoming jobs based on the principle of expected utility hypothesis. Based on this principle, the admission controller always chooses jobs that are expected to provide maximum utility after their successful completion. To predict whether or not the job will be successful, we observe the effects of past decisions made under similar situations and use this knowledge to predict outcome of incoming jobs. For this purpose we use a Nave Bayes classifier that labels incoming jobs as potentially successful or potentially unsuccessful. Out of the jobs that are labeled potentially successful, we chose the job that has the maximum value of utility function at the time of job submission. If none of the incoming jobs are labeled as potentially successful, we do not admit any job into the cluster. Utility functions are supplied by users and express the value earned by users after successful completion of jobs as a function of time taken to complete their requests. We consider a job submission to be successful if it does not overload resources on the cluster. Once the effects of the admission are observed, we update the classifier so that this experience is used while performing next decision. The next problem that we approach is that of Task Assignment. Each MapReduce job is subdivided into a number of map and reduce tasks. The tasks of a job are executed concurrently. Task assignment is the problem of deciding which task should be allocated to a node in the MapReduce cluster. The task assignment algorithm should consider the current state of resources at the concerned node as well as the resources requirements of tasks in the schedulers queue. Given this information, the task assignment algorithm should choose a task that maximizes resource utilization on the concerned node while still making sure that the node is not overloaded. We used a similar approach as that used in the admission controller for task assignment as well. While choosing a task, we first classify the queued tasks into two categories, good and bad. Good tasks do not overload resources at a node during their execution. From the tasks that are labeled good, we choose the task that has the maximum utility, which in this case is the priority of a task. Again, if none of the tasks are classified as good, we do not assign any task to the concerned node. Task priority is set by the cluster administrator, and can be used for policy enforcement. We thus decouple task assignment from policy enforcement. Once a task is assigned, we observe its effects, and if it results in overloading of resources at the concerned node, we conclude that the task assignment decision was incorrect and update the classifier accordingly. This makes sure that chances of assignments that result into overloading are reduced over time. Overload rules are specified by system administrator.

Abstract

Analog to Digital Converter (ADC) is a fundamental component in digital signal processing systems. For high-speed applications, a flash ADC is often used. Resolution, speed, and power consumption are the three key parameters for an analog-to-digital converter (ADC), which cannot be changed once an ADC is designed. While one can use only 8-bit precision from a 10-bit ADC. Such an application is non-optimal, resulting in slower speed and extra power consumption due to full 10-bit internal operation. Flash ADCs architectures commonly use high speed conversion that requires many analog comparators, which in turn cause higher complexity and power dissipation. Moreover, the accuracy of dividing resistors requires high value for reference voltage if the converting resolution is high. In this thesis, a novel architecture for flash ADC is proposed. In this architecture comparators of conventional flash ADC are replaced with CMOS inverters whose threshold can be varied dynamically. A novel peak-detector circuit is employed to achieve variable resolution for the ADC as well as to switch the unused parallel inverters to standby mode. The ADC is capable of operating at 4-bit, 6-bit, and 8-bit precision at a supply voltage of 2.5V, it consumes 21.5mW at 8-bit, 9mW at 6-bit and 3.5mW at 4-bit resolution. The sampling frequency ranges from 0.8 to 1.6 GSPS, and the ADC has a DNL<±0.4LSB, INL<±0.36LSB, SNR of 47dB and SNDR of 46.3dB for 8-bit operation. The proposed ‘inverter-based’ flash ADC operating at 8-bit precision and conventional 8-bit comparator-based flash ADC have been designed, compared and verified for post layout simulations in standard 65nm CMOS technology using thick gate process. It is observed that linear reduction in resolution leads to exponential reduction in power.