|08.30 - 08.55
|08.50 - 9.00
|09.00 - 10.40
Session 1: OS, Architecture and HPC (Click to toggle details)
- Aravinda Prasad and K. Gopinath:
Prudent Memory Reclamation in Procrastination - Based Synchronization
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.
- Kartik Nagar and Y. N. Srikant:
Precise analysis of private and shared caches for tight WCET estimates
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
- Somashekaracharya G Bhaskaracharya and Uday Bondhugula:
Automatic Optimization of Arrays in Affine Loop-Nests
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
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.
- Ashish Mishra, Y. N. Srikant and Aditya Kanade:
Typestate Analysis for Android Applications
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.
- Santhi Natarajan, Debnath Pal and S. K. Nandy:
Accelerated and Accurate Alignment of Short Reads in High Throughput Next Generation Sequencing [NGS] Platforms
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.
- Unnikrishnan Cheramangalath, Rupesh Nasre and Y. N. Srikant:
Falcon: A Graph Manipulation Language for Heterogeneous Systems
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.
- Rajesh Thakur and Y. N. Srikant:
Efficient Compilation of Stream Programs for Heterogeneous Architectures: A Model-Checking based Approach
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.
- Suvam Mukherjee and Deepak D'Souza:
Proving Data-Race Freedom of Kernel API's in a Real-Time Operating System
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.
Suparna Bhattacharya (HP),
Matthew Jacob (IISc).
|11.00 - 11.45
||Keynote talk: Pramod Varma,
Chief Architect and Technology Advisor,
Unique Identification Authority of India (UIDAI).
Jayant Haritsa (IISc)
|11.45 - 12.30
||Keynote talk: Vivek Raghavan,
Chief Product Manager & Biometric Architect,
Unique Identification Authority of India (UIDAI).
|12.30 - 12.50
||Faculty talk: Yogesh Simmhan,
Department of Computational and Data Sciences, IISc.
|14.00 - 15.00
Session 2: Programming Languages and Algorithms (Click to toggle details)
- Pallavi Maiya and Aditya Kanade:
Systematic State Space Exploration for Event-driven Multi-threaded Programs.
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
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.
- Anirudh Santhiar and Aditya Kanade:
Concurrency Analysis for Asynchronous APIs.
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.
- Hemanth Sangappa and K. R. Ramakrishnan:
An Analysis of RANSAC Algorithm.
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.
- Palash Dey:
Winner Determination and Manipulation Problems in Algorithmic Social Choice
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
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.
- Debarghya Ghoshdastidar and Ambedkar Dukkipati:
Consistency of spectral algorithms for hypergraphs under planted partition model
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.
Ganesan Ramalingam (Microsoft),
R. Govindarajan (IISc).
|15.00 - 15.20
||Faculty talk: Arpita Patra,
Department of Computer Science and Automation, IISc.
P. Vijay Kumar (IISc)
|15.20 - 15.40
||Faculty talk: Parameshwar P. Iyer ,
Department of Management Studies, IISc.
|16.00 - 16.20
||Faculty talk: Himanshu Tyagi,
Department of Electrical Communication Engineering, IISc.
P. Vijay Kumar (IISc)
|16.20 - 18.35
Session 3: Networks, Communication and Information Theory (Click to toggle details)
- Shashank Vatedka and Navin Kashyap:
Lattice Codes for Secure Communication and Secret Key Generation
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.
- Albert Sunny and Joy Kuri:
A Framework for Designing Multihop Energy Harvesting Sensor Networks
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.
- Sudheer Poojary and Vinod Sharma:
Modeling and Analysis of Networks with High-speed TCP Connections
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.
- Priyanka Das and Neelesh B. Mehta:
Interference-Constrained Cooperative Relaying for Cognitive Radio
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.
- Manuj Mukherjee and Navin Kashyap:
On the Communication Complexity for SK Generation in the Multiterminal Source Model
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.
- Mohit Sharma and Chandra Murthy:
Design of Dual Energy Harvesting Communication Links with Retransmission
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.
- Jobin Francis and Neelesh Mehta:
BS-side Estimation for Reduced Feedback Best-M Scheme in OFDM Systems
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.
- Birenjith and P. Vijay Kumar:
Codes for Distributed Storage
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.
- Raviteja and P. Vijay Kumar:
An Animation and Chirplet-Based Approach to Developing a PIR Sensing Intrusion Detection System for an Outdoor Setting
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%.
- Abhijit Bhattacharya and Anurag Kumar:
Network Design for QoS under IEEE 802.15.4 ("Zigbee") CSMA/CA for Internet of Things Applications
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
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.
- Akhil P. T. and Rajesh Sundaresan:
Separable Convex Optimization with Linear Ascending Constraints
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.
Kumar Sivarajan (Tejas Networks),
H. S. Jamadagni (IISc).
|19.00 - 20.15
Session 4: RF and Electronics (Click to toggle details)
- Arnab Kumar Biswas and S. K. Nandy:
Securing Multiprocessor System-on-Chip
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.
- Keerthan P. and K. J. Vinoy:
Wide-Band Radio Frequency Signal Analysis and Processing Using Cascaded All-Pass Networks
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.
- Nikita Ambasana and Dipanjan Gope:
Intelligent and Fast Electrical Design Space Exploration Techniques for Package-Boards
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.
- Vijayashree Bhat and K. J. Vinoy:
Investigation of Planar Microstrip Capacitive Probe fed Antenna for Time and Frequency Domain Characteristics
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.
- Javed G. S. and Gaurab Banerjee:
Frequency domain CMOS Capacitance Interface
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
- Anuja Chanana and S. Mahapatra:
Investigations of 2D material metal contact using Density Functional Theory
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
Arun Chandrasekhar (Intel),
Soumyendu Raha (IISc).