EECS Research Students Symposium - 2016

Procrastination is the fundamental technique used in synchronization mechanisms such as Read-Copy-Update (RCU) where writers, in order to synchronize with readers, defer the freeing of an object until there are no readers referring to the object. The synchronization mechanism determines when the deferred object is safe to reclaim and when it is actually reclaimed. Hence, such memory reclamations are completely oblivious of the memory allocator state. This induces poor memory allocator performance, for instance, when the reclamations are ill-timed. Furthermore, deferred objects provide hints about the future that inform memory regions that are about to be freed. Although useful, hints are not exploited by memory allocators. We introduce Prudence memory allocator that is tightly integrated with the synchronization mechanism to ensure visibility of deferred objects to the memory allocator. Such an integration enables Prudence to (i) identify the safe time to reclaim deferred objects’ memory, (ii) have an inclusive view of the allocated, free and about-to-be-freed objects, and (iii) exploit optimizations based on the hints about the future during important state transitions. Our evaluation in the Linux kernel shows that Prudence integrated with RCU performs 3.9X to 28X better in micro-benchmarks compared to the SLUB allocator. It also improves the overall performance perceptibly (4%-18%) for a mix of widely used synthetic and application benchmarks. Further, it performs better (up to 98%) in terms of various allocator attributes when compared with the SLUB allocator.

Worst Case Execution Time (WCET) is an important metric for programs running on real-time systems, and finding precise estimates of a program's WCET is crucial to avoid wastage of computational resources. Caches have a major impact on a program's execution time, and accurate estimation of a program's cache behavior generally leads to significant reduction of its estimated WCET. However, in multi-path programs the same memory access can exhibit different cache behavior in different execution instances. This issue is further exacerbated in shared caches in a multi-core architecture, where interfering memory accesses from co-running programs on other cores can arrive at any time and modify the cache state. To ensure safe estimation of WCET, traditional cache analysis techniques try to statically find accesses which are guaranteed to hit the cache across all execution instances. However, this introduces significant imprecision in the final WCET estimate.
In our work, we take a fundamentally different approach to cache analysis, by trying to find lower bounds on the number of cache hits guaranteed across all execution instances. For shared cache analysis, we propose an Integer Linear Programming based approach and an algorithmic approach to find worst-case distribution of interfering accesses across a program. For private caches, we first obtain a precise relation between program paths and cache behavior, and then use this information to make precise predictions about number of guaranteed cache hits in a basic block and in the worst-case execution instance of the program.

Efficient memory allocation is crucial for data-intensive applications as a smaller memory footprint ensures better cache performance. Consequently, larger problem sizes can be run given a fixed amount of main memory. The solutions found by existing techniques for automatic optimization of arrays in affine loop-nests are often far from good or optimal. In this talk, we present a new automatic storage optimization framework and techniques which can be used to achieve intra-array as well as inter-array storage reuse within affine loop-nests with a pre-determined schedule.
Over the last two decades, several heuristics have been developed for achieving complex transformations of affine loop-nests using the polyhedral model. However, no comparably strong heuristics exist for tackling the problem of automatic memory footprint optimization. We bridge this gap by formulating the problem of storage optimization as one of finding the right storage partitioning hyperplanes: each storage partition corresponds to a single storage location. Statement-wise storage partitioning hyperplanes are determined that partition a unified global array space so that values with overlapping live ranges are not mapped to the same partition.
Storage reduction factors we report from a polyhedral storage optimizer, SMO, developed using our storage partitioning approach, demonstrate its effectiveness on several benchmarks drawn from the domains of image processing, stencil computations, high-performance computing, and the class of tiled codes in general. The reductions in storage requirement over previous approaches range from constant factors to asymptotic in the loop blocking factor or array extents.

Android is the fastest growing mobile OS platform, this has made it the sweetest target for the attackers. Finding and removing any programming bug or error in Android apps is quintessential for security. Many works perform program analysis to track and debug such programming errors, but control flow in Android applications, managed by the Android framework is hard to correctly reason about statically, failing which, these analysis' are prone to both being imprecise and unsound. Android developers access system and other critical resources like databases, camera etc. via a set of exposed APIs. These resources have complex API usage protocols which the developers must follow, failing which might lead to error or runtime exceptions. These errors are hard to find and debug, and if undetected they might form attack vectors for various attacks on data and resources. These errors can be tracked via a Typestate analysis against the usage protocols. Here we present a TypeState analysis for Android applications.This is the first Typestate analysis for Android applications and the first static analysis work taking into account the correct asynchronous control flow semantics of Android. We evaluate our analysis on new benchmark apps, related to Typestate properties and we add them to an earlier Android benchmark suite, DroidBench. We compare the results against a typestate analysis built over control flow graph typical of what other static analysis are using. We show empirically that we are more precise and miss lesser violations compared to the model used by other analysis.

The genome of an organism encompasses the unique set of genetic instructions for every individual in a species. Understanding the genome involves determining the order of the constituent bases within the sequence, and the process is widely known as sequencing. Next Generation Sequencing (NGS) massively parallel sequencing of genetic data with high throughput. NGS offers an unparalleled interrogation of the genome, throwing deeper insight into the functional and structural investigation of genetic data. Classified as a complex big data engineering problem, Short Read Mapping (SRM) within the NGS pipeline presents profound technical and computing challenges. Existing solutions for accelerating SRM provide notable performance, while leveraging heuristics. In this context, we need precise, affordable, reliable and actionable results from SRM, to support any application, with uncompromised accuracy and performance. Here, we present a massively parallel and scalable archetype, for accurate alignment of short reads, at a fine grained single nucleotide resolution. The solution offers a complete coverage of the genome, including repeat regions in the reference and the redundancy in short reads. We present AccuRA, the reconfigurable hardware accelerator model for SRM, and GMAccS, the scalable GPGPU model for SRM. With a very efficient lookup algorithm, they offer full coverage for a read, within the repeat regions, as well as for redundant reads, thus reporting all the possible regions of alignment for every short read. The archetypes could successfully scale at multiple levels of granularity, while aligning the smaller archeal, bacterial and fungal genomes, to the much larger mammalian human genomes.

Graph algorithms have been shown to possess enough parallelism to keep several computing resources busy—even hundreds of cores on a GPU. Unfortunately, tuning their implementation for efficient execution on a particular hardware configuration of heterogeneous systems consisting of multicore CPUs and GPUs is challenging, time consuming, and error prone. To address these issues, we propose a domain-specific language (DSL), Falcon, for implementing graph algorithms that (i) abstracts the hardware, (ii) provides constructs to write explicitly parallel programs at a higher level, and (iii) can work with general algorithms that may change the graph structure (morph algorithms). We illustrate the usage of our DSL to implement local computation algorithms (that do not change the graph structure) and morph algorithms such as Delaunay mesh refinement, survey propagation, and dynamic SSSP on GPU and multicore CPUs. Using a set of benchmark graphs, we illustrate that the generated code performs close to the state-of-the-art hand-tuned implementations.

Stream programming based on the synchronous data flow (SDF) model naturally exposes data, task and pipeline parallelism. Statically scheduling stream programs for homogeneous architectures has been an area of extensive research. With graphic processing units (GPUs) now emerging as general purpose co-processors, scheduling and distribution of these stream programs onto heterogeneous architectures (having both GPUs and CPUs) provides for challenging research. Exploiting this abundant parallelism in hardware, and providing a scalable solution is a hard problem.
In this paper we describe a coarse-grained software pipelined scheduling algorithm for stream programs which statically schedules a stream graph onto heterogeneous architectures. We formulate the problem of partitioning the work between the CPU cores and the GPU as a model-checking problem. The partitioning process takes into account the costs of the required buffer layout transformations associated with the partitioning and the distribution of the stream graph. The solution trace result from the model checking provides a map for the distribution of actors across different processors/cores. This solution is then divided into stages, and then a coarse grained software-pipelined code is generated. We use CUDA streams to map these programs synergistically onto the CPU and GPUs. We use a performance model for data transfers to determine the optimal number of CUDA streams on GPUs. Our software-pipelined schedule yields a speedup of upto 55.86X and a geometric mean speedup of 9.62X over a single threaded CPU.

We propose a technique for proving absence of data-races due to kernel API's in a real-time operating system (RTOS) that relies on flag-based scheduling and synchronization. The first step in the approach is to model the control-flow and accesses to shared data-structures in an n-task application using these kernel API's, as a model (say M_n) in a model-checking tool like Spin. Next, to remove the dependency on n, as well as to address feasibility issues, we construct a finite number of reduced models M, that together preserve the races in M_n. It is now sufficient to model-check each of these M's in order to exhaustively list out all possible data-races that may occur in any M_n. If all races reported here are benign, we have a proof that the RTOS kernel is free from harmful data-races. We describe our approach in the context of FreeRTOS, a popular RTOS in the embedded domain. We found several races, proposed fixes for them, and obtained a verified race-free version of FreeRTOS.

Event-driven programming is becoming a preferred style of developing efficient and responsive applications like smartphone applications and browsers. This model is multi-threaded and threads communicate through shared objects or by posting asynchronous events. In this concurrency model, unforeseen thread interleavings coupled with non-deterministic reorderings of events can lead to subtle concurrency errors. The existing concurrency analysis techniques are primarily for multi-threaded programs; we extend this to event-driven multi-threaded programs.
Android applications are a popular systems in this concurrency model. We have formalized the concurrency semantics of Android applications and defined corresponding happens-before relation. We have developed a dynamic race detector which uses this relation. Our relation generalizes the so far independently studied happens-before relations for multi-threaded programs and single-threaded event-driven programs. We have implemented a tool called DROIDRACER, which has detected potential races in popular applications like Facebook and Twitter.
A race detector can detect races in only a few thread schedules. However, covering all schedules requires a systematic explorer whose scalability depends on state space reduction techniques like Partial Order Reduction. Existing POR techniques reorder every pair of events handled on the same thread even if reordering them does not lead to different states. We propose a new POR technique called the dependence-covering set, which reorders events handled by the same thread only if necessary. We prove that exploring only dependence-covering sets preserves all deadlock cycles and assertion violations. We demonstrate that our technique explores far lesser transitions compared to exploration based on persistent sets, a popular POR technique.

Programmers want to design highly responsive software, hiding latency from users wherever possible. This has led to the increasing adoption of asynchronous programming models supported by asynchronous APIs and libraries. However, the use of asynchronous events can lead to unforeseen event interleavings, resulting in bugs, and it is difficult for developers to reason about control flow in asynchronous applications.
First, we consider event driven programs where events are dequeued sequentially from an event queue, and processed by invoking their handlers. A handler may itself pause, dequeue more events, and run their handlers in another programmatic event loop. In this case, there can be races between the paused handler and another handler that runs inside the programmatic event loop. We present an efficient happens-before based race detection technique for such programs. We have implemented our technique in an offline race detector for C/C++ programs, called SparseRacer. We discovered 13 new and harmful race conditions in 9 open-source applications including Okular and KOrganizer. Our techniques to improve efficiency resulted in an average speedup of 5X in race detection time.
Mixing synchronous and asynchronous waiting in C#'s asynchronous programming model can result in deadlocks. Finding such deadlocks is challenging owing to the mixture of synchronous and asynchronous calls. We design a static analysis to detect such deadlocks. In preliminary experiments, we applied the analysis to 7 open source benchmarks, and it found deadlocks in all of them.

Random Sampling and Consensus (RANSAC) is an iterative algorithm for robust estimation of model parameters in the presence of outliers in observed data. First proposed by Fischler and Bolles back in 1981, it still is a very popular algorithm among the Computer Vision community. A common practice among researchers while implementing RANSAC is to take a few samples more than the minimum required for estimation of model parameters, but the implications of this heuristic is lacking in literature. In this work we present an analysis of this common heuristic.

In many real life situations, including multiagent systems, agents often need to agree upon a common alternative even if they have different preferences over the available alternatives. Voting is one of the most suitable tools in these scenarios. Common and classic applications of voting in artificial intelligence include collaborative filtering, planning among multiple automated agents etc. Our goal is to study the time, space, and sample complexity of fundamental problems in voting.
The typical setting may be described as follows. An election consists of a set of voters, a set of alternatives, and a voting rule. The vote of any voter can be thought of as a ranking (more precisely, a complete order) of the set of alternatives. A voting profile is just a collection of votes of all voters. Finally, a voting rule is a function that takes a voting profile as input and outputs an alternative, which is regarded as the winner of the election.
In the first part of the thesis, we show tight sample complexity bounds for winner prediction and margin of victory estimation in elections; design optimal algorithms for finding the winner in a stream of votes; prove tight bounds on query cmplexity for preference elicitation for various important domains of preferences; establish parameterized complexity dichotomy for committee selection problem in the presence of outliers.
In the second part of the thesis, we study classical computation complexity and parameterized complexity of various control problems e.g. manipulation detection, possible winner, coalitional manipulation, and bribery.

Hypergraph partitioning lies at the heart of various problems in engineering and science. While partitioning uniform hypergraphs is required in computer vision, non-uniform hypergraph partitioning has applications in database systems, circuit design etc. Hypergraph partitioning is typically a NP-hard problem. Yet, over the last two decades, several efficient heuristics are known in the literature and their empirical success is widely appreciated. In contrast to the extensive studies related to graph partitioning, theoretical guarantees of hypergraph partitioning approaches are not known in the literature. The purpose of our work is to establish, for the first time, the statistical error bounds for spectral algorithms for partitioning uniform and non-uniform hypergraphs.
The mathematical framework is the following. Consider a set of n vertices, which are divided into k classes. A random hypergraph is generated on the n vertices by independently adding subsets of the vertices to the edge set with probabilities depending on the labels of the participating vertices. We provide an upper bound on the number of disagreements between the true class labels, and the labels obtained from spectral algorithms for hypergraph partitioning. We show that under certain conditions, the error is o(n) with high probability. In the literature, such error bounds are only known in the case of graphs, where the model coincides with the popular stochastic block model. Our results are based on matrix concentration inequalities and perturbation bounds, and the derived bounds can be used to comment on the consistency of spectral hypergraph partitioning algorithms.

In this work, we study two problems in information-theoretic security. Firstly, we study a wireless network where two nodes want to securely exchange messages via an honest-but-curious relay. There is no direct link between the user nodes, and all communication must take place through the relay. We give two secure protocols for this problem and study their performance. In the second problem, we consider the scenario where multiple terminals have access to private correlated Gaussian sources and a public noiseless communication channel. The objective is to generate a secret key using these sources and public communication in a way that an eavesdropper having access to the public communication can obtain no information about the key. We give a protocol with polynomial complexity to achieve this under certain assumptions on the sources and characterize its performance.
The key tools used in designing these protocols are nested lattice codes, which have been widely used in several problems of communication and security. We also study lattice constructions that permit polynomial-time encoding and decoding. In this regard, we first look at a class of lattices obtained from low-density parity-check (LDPC) codes, and show that they have several desirable properties. We also give concatenated lattice coding schemes with polynomial-time encoders and decoders that achieve the capacity of the additive white Gaussian noise channel.

Efficient resource planning in energy harvesting wireless sensor networks (WSN) is of immense practical significance. However, it is encumbered by the sheer diversity of parameters that affect the performance of such WSNs. In this paper, we propose a unified framework that can be leveraged to efficiently design and deploy such large-scale networks. To this end, we propose an intuitive utility function to quantify the Quality of Monitoring (QoM). Based on this QoM, we formulate a long-term time-averaged joint resource allocation problem, whose optimal solution serves as a metric to compare different deployment scenarios. This resource allocation problem is subject to energy and capacity constraints inherent to WSNs. The capacity constraints, though very intuitive, require us to enumerate all the maximal independent sets in the network — a well known NP-hard problem. Therefore, for computational tractability, we replace the maximal independent set constraints with clique constraints. We also prove the sufficiency of the clique constraints, and present an algorithm that obtains an ϵ-optimal solution to the original problem. Finally, we present numerical evaluations to validate the correctness of the proposed algorithm.

We derive an expression for throughput of TCP Compound and TCP CUBIC connections with random losses. We consider the case of a single TCP connection with random losses and negligible queuing, i.e., constant round trip time. We consider a sequence of appropriately scaled window size processes, indexed by p, the packet error rate. We show that as p goes to zero, this sequence converges to a limiting Markov chain. We use the stationary distribution of the limiting Markov chain to give an approximation for TCP Compound and TCP CUBIC throughput for small p. We validate our model and approximations through ns2 simulations.

Cognitive radio (CR) is a promising technology that enables reuse of underutilized spectrum and helps mitigate the severe spectrum shortage faced by society today. In underlay mode of CR, a cognitive user can transmit concurrently with a higher priority primary user, but the interference it causes to the primary user must be constrained. These interference constraints severely limit the performance of the cognitive users.
We develop advanced cooperative relaying techniques to address this issue. In it, one among the available cognitive nodes called relays that are in the vicinity of the cognitive users is selected to forward the signals transmitted by the cognitive transmitter to its receiver. We develop novel relay selection rules that are optimized for either maximizing the reliability of communication, which is measured in terms of the uncoded symbol error probability, or the rate of communication, which is measured in terms of the capacity. All these rules satisfy a constraint on the average interference caused to the primary.
The proposed rules determine which relay to select and whether to select none of the relays at all as a function of the channel gains between the various nodes. They outperform several ad hoc relay selection rules proposed in the literature. We also analyze the performance of the proposed rules by deriving closed-form expressions for the average data rate or average symbol error probability. Lastly, we gain several insights by studying the asymptotic regimes of low and high average signal-to-noise ratios, in which these expressions simplify significantly.

Csiszar and Narayan introduced the problem of secret key (SK) generation in the multiterminal source model. The multiterminal source model consists of a set of terminals observing i.i.d. copies of correlated discrete random variables. The terminals are allowed to communicate over a noiseless public channel. The aim is to generate a group key secured from a passive eavesdropper listening to the public channel. Csiszar and Narayan evaluated the SK capacity, i.e., the maximum rate of a secret key. The key capacity was achieved through a communication for omniscience. Here, omniscience refers to each terminal recovering the observations of the remaining terminals. The focus of this work is to characterize the communication complexity of SK generation (R_SK), i.e., the minimum rate of communication required to generate a secret key of maximum rate. The omniscience protocol of Csiszar and Narayan ensures that R_SK\leq R_CO, R_CO being the minimum rate of communication for omniscience. Following the work of Tyagi for two terminals, we obtain a lower bound on R_SK for the case of m\geq 2 terminals. Sufficient conditions for R_SK-maximality, i.e., the case where R_SK=R_CO, are also studied. We further show that these conditions are also necessary for the hypergraphical source, a special case of the multiterminal source model.

In this work, we consider retransmission based point-to-point dual energy harvesting (EH) links, where both transmitter and receiver are energy harvesting nodes (EHNs). The transmitter needs to periodically send a packet to a receiver, and the packet is dropped if it is not delivered within a fixed number of transmission attempts. The goal is to determine the optimal battery size as well as to design retransmission index-based transmit power policy(RIP), which minimizes the packet drop probability (PDP) while maintaining energy neutrality at the nodes. First, we analyze the PDP gap between the PDP of dual EH links with infinite and finite batteries and establish near-optimality of the policies designed to operate in the energy unconstrained regime (EUR), i.e., the regime where the rate of energy use at each EHN is less than the corresponding harvesting rate. Next, the optimal RIPs are designed using the techniques from geometric programming. The numerical results obtained through extensive Monte Carlo simulations show that the proposed RIPs outperforms the state-of-art policies. For example, in case of mono EH links with ARQ over slow as well as fast fading channels, the designed RIP outperforms policies designed using Markov decision process based methods.

Rate adaptation and scheduling have become indispensable in current and next generation cellular systems since they improve the spectral efficiency by adapting the user the base station (BS) transmits to and the transmit rate depending on the channel conditions. To do so, the BS needs the downlink channel state information (CSI). Hence, the users must feed them back to the BS, which expends uplink radio resources. Since this feedback could overwhelm the uplink, several reduced feedback schemes have been proposed in the literature that trades off between feedback overhead and the loss in throughput due to reduced CSI.
For the practically important best-M scheme, in which each user feeds back only its M strongest subchannels and their indices to the BS, we develop minimum mean square error (MMSE) and throughput-optimal approaches that enable the BS to transmit reliably even on subchannels not fed back by any user. In the former, an MMSE estimate of the SNR is generated at the BS for subchannels not reported by a user. In the latter, the user and its transmit rate are selected so as to maximize the throughput. This approach provides a fundamental limit on the achievable throughput. The novelty of these approaches lies in their exploitation of the structure of the best-M feedback information and the correlation among subchannel gains. In terms of system-level impact, the proposed approaches improve the throughput compared to several conventional approaches – without requiring any additional feedback – for uncorrelated and correlated subchannels.

In a distributed storage system, a data file comprising of information symbols data symbols drawn from a finite alphabet, is encoded using an error-correcting code and the resulting code symbols are stored in nodes in a network. A desirable attribute in a distributed storage system is the efficiency in carrying out repair of failed nodes. Among many others, two important metrics to characterize efficiency of node repair are repair bandwidth, i.e., the amount of data download in the case of a node failure and repair degree, i.e., the number of helper nodes accessed for node repair. While ``regenerating codes'' aim to minimize the repair bandwidth, ``codes with locality'' seek to minimize the repair degree. In our work, we study the fundamental performance limits of these classes of codes, and present code constructions designed to meet these limits.

This paper presents the development of a passive infra-red sensor tower platform along with a classification algorithm to distinguish between human intrusion, animal intrusion and clutter arising from wind-blown vegetative movement in an outdoor environment. The research was aimed at exploring the potential use of wireless sensor networks as an early-warning system to help mitigate human-wildlife conflicts occurring at the edge of a forest. There are three important features to the development. Firstly, the sensor platform employs multiple sensors arranged in the form of a two-dimensional array to give it a key spatial-resolution capability that aids in classification. Secondly, given the challenges of collecting data involving animal intrusion, an Animation-based Simulation tool for Passive Infra-Red sEnsor (ASPIRE) was developed that simulates signals corresponding to human and animal intrusion and some limited models of vegetative clutter. This speeded up the process of algorithm development by allowing us to test different hypotheses in a time-efficient manner. Finally, a chirplet-based model for intruder signal was developed significantly helped boost classification accuracy despite drawing data from a smaller number of sensors. An SVM-based classifier was used which made use of chirplet, energy and signal cross-correlation-based features. The average accuracy obtained for intruder detection and classification on real-world and simulated data sets was in excess of 97%.

We focus on design and analysis of multi-hop wireless sensor networks (WSN) under the IEEE 802.15.4 PHY and MAC for IoT applications. In particular, we address the broad problem of designing a multi-hop WSN at minimum deployment cost, i.e., by placing as few additional relay nodes and base stations as possible, to convey sensed data from a set of given source locations to at least one base station location, while satisfying given Quality of Service (QoS) objectives.
First, we consider very low data rate applications where the contention due to CSMA is negligible; we show that the problems reduce to graph design problems with various topological constraints, and the resulting problems are NP-hard. We propose fast, polynomial time heuristics to obtain good solutions. We also provide worst case and average case approximation guarantees for our proposed algorithms.
Next, we deal with low to moderate data rate applications where the inter-node contention must be taken into account to accurately predict the network performance. We first develop an approximate, but accurate fixed point analysis for multi-hop tree networks that takes into account collision due to CSMA contention, hidden node effects, etc. We then provide a simplification of this analysis for the case of no hidden nodes in a low discard probability regime, and use this simplified model to derive explicit conditions on the topology, and the arrival rate vector to satisfy given QoS objectives, which in turn, yield simple design rules for throughput optimal network design.

We consider the maximization of a separable concave function subject to linear ascending constraints. The problem arises as the core optimization in several resource allocation scenarios and is a special case of an optimization of a separable concave function over the bases of a polymatroid. The algorithms to maximize a separable concave function over the bases of a polymatroid fall into two broad categories: greedy algorithms and decomposition algorithms. In this work, we present an algorithm that falls in the category of decomposition algorithms. This class of algorithms divides the optimization problem into several sub-problems which are easier to solve. Our algorithm decomposes the optimization over linear ascending constraints into sub-problems with single sum constraint.
We also consider a network utility maximization problem consisting of multiple users sending data over the network specified by linear ascending constraints.The utility maximization problem is formulated as a separable concave maximization problem over the flow constraints imposed by the network. The problem is solved in a distributed manner as in kelly-Maulloo-Tan (J. oper. Res. Soc. 1998) by decomposing it into sub-problems; one for each user and one for the network. Our algorithm has users adapting the prices they are willing to pay and the network allocating rates in tune to the user prices. We also map the solution of the network problem to a geometric problem of finding the concave cover of a set of points in a plane which enables an efficient solution to the network problem.

With Multiprocessor-System-on-Chips (MPSoCs) pervading our lives, security issues are emerging as a serious problem and attacks against these systems are becoming more critical and sophisticated. We have designed and implemented different hardware based solutions to ensure security of an MPSoC. Security assisting modules can be implemented at different abstraction levels of an MPSoC design. We propose solutions both at circuit level and system level of abstractions. At the VLSI circuit level abstraction, we consider the problem of presence of noise voltage in input signal coming from outside world. This noise voltage disturbs the normal circuit operation inside a chip causing false logic reception. If the disturbance is caused intentionally the security of a chip may be compromised causing glitch/transient attack. We propose an input receiver with hysteresis characteristic that can work at voltage levels between 0.9V and 5V. The circuit can protect the MPSoC from glitch/transient attack. At the system level we propose solutions targeting Network-on-Chip (NoC) as the on-chip communication medium. We survey the possible attack scenarios on present-day MPSoCs and investigate a new attack scenario, i.e., router attack targeted toward NoC enabled MPSoC. We propose different monitoring-based countermeasures against routing table-based router attack in an MPSoC having multiple Trusted Execution Environments (TEEs). Software attacks, the most common type of attacks, mainly exploit vulnerabilities like buffer overflow. This is possible if proper access control to memory is absent in the system. We propose four hardware based mechanisms to implement Role Based Access Control (RBAC) model in NoC based MPSoC.

The increasing demand for wireless communication, radar and imaging systems that are aware of the environment and adapt suitably to the operating conditions can be met by real time signal analysis. Emergence of signal analysis in analog domain can be attributed to the development of dispersive delay lines (DDL). In this regard, all-pass networks (APN) have been explored as a potential wide-band, high resolution DDL. An iterative procedure is developed to design APN circuits for monotonous group delay response at radio frequencies. They exhibit linear and non-linear group delay responses with both positive and negative slopes. The design is extended for surface mount device implementation to accommodate mounting pads, component availability, tolerance and finite quality factor. The design frequency range is chosen as [0.5 – 1] GHz. The experimental results are compared with ideal circuit and full wave simulations for validation. The implementation has greatly improved the performance in terms of group delay dispersion with a reduced footprint and lower insertion loss.
Signal propagation through DDL with group delay dispersion is analysed. A quadratic phase approximation is assumed. It is found that the signal experiences expansion of pulse width, reduction of its peak amplitude and a temporal displacement of the spectral components. APN is shown to have wide range of applications. A reconfigurable delay line is developed where the delay of the overall system is made tunable. Time stretch and time compression of the linear frequency modulated waveform is demonstrated. Frequency discriminator is developed with a resolution of 15 MHz.

Package-board design plays a crucial role in determining the performance of high-speed systems. Lack of CAD tools for signal integrity aware design and synthesis lead to longer design cycles and non-optimal package-board interconnect geometries. In this work an end to end system is developed for intelligent and fast electrical design space exploration for package boards.
In the first part of the work, the functional similarities between package-board design and radio-frequency imaging are explored. Qualitative inverse-solution methods are applied to solve multi-objective, multi-variable package design problems. A novel piecewise linear algorithm is developed for an efficient solution in the design space using metric to design sensitivity. The presented algorithm is demonstrated to converge to the desired specifications with fewer forward-solve iterations.
In the second part of the work, we explore learning based modeling techniques that rapidly map frequency domain metrics like differential insertion-loss and cross-talk to time domain metrics like eye-height and eye-width facilitating faster design validation and hence full-factorial design space sweep. Numerical results performed with common learning based models on SATA 3.0 and PCIe Gen 3 channels generate less than 3% average error.
In the third part of the work, we present a mathematical formulation to obtain a Jacobian for a given structure mesh’s electrical properties to the mesh shape parameters for a 2.5D solver. Such a Jacobian enables first order Taylor updates for linear mesh modifications enabling the CAD operator to get real time updates on the change in electrical parameters of the structure with changes in geometry.

In this research, planar microstrip Ultra-Wide Band (UWB) antenna with capacitive probe feed is studied for its time domain (TD) and frequency domain (FD) characteristics. Ultra-wideband antennas are those that have fractional bandwidth of atleast 20% or more than 500 MHz. A UWB antenna has several applications in medical imaging, ground penetrating and imaging radar (GPRI), surveillance, through wall imaging, indoor communications and outdoor handheld devices. Compactness, low profile, low cost makes the planar UWB microstrip antennas more flexible and realizable. The antenna examined in this study has a wide bandwidth of 1 GHz. Investigation of TD characteristics of wideband antenna is done using FD and TD simulations and validated using experimental results. Furthermore, simulation study is established for UWB antenna on FD characteristics such as Scattering parameters (S11=-10dB, BW=3.1 GHz-4.2 GHz), Gain (~7dB), Efficiency (99.1%) and Radiation pattern (single-directional), TD characteristics such as Group Delay (<0.5ns) and Pulse Fidelity Factor (PFF>0.8). In addition, different UWB short pulses and its influence on the antenna characteristics is also explored and single element is optimized for nearly constant phase center using the weighting function as input pulse spectrum. Also, mutual coupling is reduced between antennas to -16 dB and gain improvement is seen in the array elements. Thus, this study on planar antenna with capacitive probe feed for FD and TD characteristics proves to satisfy all requirements for UWB signal and system applications.

A frequency domain capacitance interface system is proposed for a femto-farad capacitance measurement. In this technique, a ring oscillator circuit is used to generate a change in time period, due to a change in the sensor capacitance. The time-period difference of two such oscillators is compared and is read-out using a phase frequency detector and a charge pump. The output voltage of the system, is proportional to the change in the input sensor capacitance. The capacitance sensor interface system was designed and a prototype was implemented in a 0.13 m standard CMOS technology. Experimental and simulation results are presented. It exhibits a maximum sensitivity of 8.1 mV/fF, which is 2x - 10x better over the state-of-the-art.

A low Schottky barrier height (SBH) at source/drain contact is essential for achieving high drive current in atomic layer MoS2-channel-based field effect transistors. Approaches such as choosing metals with appropriate work functions and doping the channel are employed previously to improve the carrier injection from the contact electrodes to the channel and thus mitigate the SBH between the MoS2 and metal. Recent experiments demonstrate significant SBH reduction when graphene layer is inserted between metal slab (Ti and Ni) and MoS2. However, the physical or chemical origin of this phenomenon is not yet clearly understood. In this work, density functional theory simulations are performed, employing pseudopotentials with very high basis sets to get insights of the charge transfer between metal and monolayer MoS2 through the inserted graphene layer. Our atomistic simulations on 16 different interfaces involving five different metals (Ti, Ag, Ru, Au, and Pt) reveal that (i) such a decrease in SBH is not consistent among various metals, rather an increase in SBH is observed in case of Au and Pt; (ii) unlike MoS2-metal interface, the projected dispersion of MoS2 remains preserved in any MoS2-graphene-metal system with shift in the bands on the energy axis. (iii) A proper choice of metal (e.g., Ru) may exhibit ohmic nature in a graphene-inserted MoS2-metal contact. These understandings would provide a direction in developing high-performance transistors involving heteroatomic layers as contact electrodes.