Department of Computer Science and Engineering

Indian Institute of Technology Palakkad&nbsp;(IIT Palakkad or IIT PKD) is a public autonomous&nbsp;engineering&nbsp;and&nbsp;research&nbsp;institute located in&nbsp;Palakkad,&nbsp;Kerala. It was&nbsp;one of the five new&nbsp;IITs&nbsp;proposed in the&nbsp;2014 Union budget of India. The campus was inaugurated on 3 August 2015. The institute has 94 faculty, 978 students, and 63 non-teaching staffs.

IT Palakkad currently offers four-year Bachelor of Technology (B.Tech) and two years MS programmes in 8 different engineering disciplines including&nbsp;Computer Science, Electrical, Mechanical, Civil among others.

&nbsp;

IIT Palakkad

In this paper, we propose a two-stage thermal-aware task scheduling policy which exploits the application and system architecture characteristics to decouple the mapping of task-graphs for the performance and peak temperature optimization into two stages. At the first stage, the algorithm collects the best mapping of task-graphs exploiting the application and architecture characteristics to minimize the makespan of the task-graphs. At the second stage, a light-weight online algorithm comprised of efficient thermal rank and combined power models is performed to map the task nodes to the real cores for temperature minimization while maintaining the best possible performance achieved in the first stage. Compared to the previous approaches which perform the performance and temperature optimization together, our method can reduce the online mapping algorithm complexity and improve its efficiency. Experiments on real benchmarks show that an average of 6.3°C peak temperature reduction and 6.8% performance improvement can be achieved compared to other existing methods. © 2017 IEEE.

World University root node

Proceedings of the Asia and South Pacific Design Automation Conference, ASP-DAC

Two-stage thermal-aware scheduling of task graphs on 3D multi-cores exploiting application and architecture characteristics

A class domination coloring (also called as cd-coloring) of a graph is a proper coloring such that for every color class, there is a vertex that dominates it. The minimum number of colors required for a cd-coloring of the graph G, denoted by χcd(G), is called the class domination chromatic number (cd-chromatic number) of G. In this work, we consider two problems associated with the cd-coloring of a graph in the context of exact exponential-time algorithms and parameterized complexity. (1) Given a graph G on n vertices, find its cd-chromatic number. (2) Given a graph G and integers k and q, can we delete at most k vertices such that the cd-chromatic number of the resulting graph is at most q? For the first problem, we give an exact algorithm with running time O(2nn4 log n). Also, we show that the problem is FPT with respect to the number of colors q as the parameter on chordal graphs. On graphs of girth at least 5, we show that the problem also admits a kernel with O(q3) vertices. For the second (deletion) problem, we show NP-hardness for each q ≥ 2. Further, on split graphs, we show that the problem is NP-hard if q is a part of the input and FPT with respect to k and q. As recognizing graphs with cd-chromatic number at most q is NP-hard in general for q ≥ 4, the deletion problem is unlikely to be FPT when parameterized by the size of deletion set on general graphs. We show fixed parameter tractability for q ∈ {2, 3} using the known algorithms for finding a vertex cover and an odd cycle transversal as subroutines. © Springer International Publishing AG 2017.

Lecture Notes in Computer Science (including subseries Lecture Notes in Artificial Intelligence and Lecture Notes in Bioinformatics)

Parameterized and exact algorithms for class domination coloring

In this paper, we present a generic plug-and-play controller that ensures fair and efficient operation of IEEE~802.11 infrastructure wireless local area networks with multiple co-channel access points, without any change to hardware/firmware of the network devices. Our controller addresses performance issues of TCP transfers in multi-AP WLANs, by overlaying a coarse time-slicing scheduler on top of a cascaded fair queuing scheduler. The time slices and queue weights, used in our controller, are obtained from the solution of a constrained utility optimization formulation. A study of the impact of coarse time-slicing on TCP is also presented in this paper. We present an improved algorithm for adaptation of the service rate of the fair queuing scheduler and provide experimental results to illustrate its efficacy. We also present the changes that need to be incorporated to the proposed approach, to handle short-lived and interactive TCP flows. Finally, we report the results of experiments performed on a real testbed, demonstrating the efficacy of our controller.

arXiv

ADWISERv2: A Plug-and-play Controller for Managing TCP Transfers in IEEE~ 802.11 Infrastructure WLANs with Multiple Access Points

We consider the problem of distributed scheduling in wireless networks where heterogeneously delayed information about queue lengths and channel states of all links are available at all the transmitters. In an earlier work (by Reddy et al. in Queueing Systems, 2012), a throughput optimal scheduling policy (which we refer to henceforth as the R policy) for this setting was proposed. We study the R policy, and examine its two drawbacks -- (i) its huge computational complexity, and (ii) its non-optimal average per-packet queueing delay. We show that the R policy unnecessarily constrains itself to work with information that is more delayed than that afforded by the system. We propose a new policy that fully exploits the commonly available information, thereby greatly improving upon the computational complexity and the delay performance of the R policy. We show that our policy is throughput optimal. Our main contribution in this work is the design of two fast and near-throughput-optimal policies for this setting, whose explicit throughput and runtime performances we characterize analytically. While the R policy takes a few milliseconds to several tens of seconds to compute the schedule once (for varying number of links in the network), the running times of the proposed near-throughput-optimal algorithms range from a few microseconds to only a few hundred microseconds, and are thus suitable for practical implementation in networks with heterogeneously delayed information.

Networking and Internet Architecture

Throughput Optimal and Fast Near-Optimal Scheduling with Heterogeneously Delayed Network-State Information (Extended Version)

A linear ordering of the vertices of a graph G separates two edges of G if both the endpoints of one precede both the endpoints of the other in the order. We call two edges {a, b} and {c, d} of G strongly independent if the set of endpoints {a, b, c, d} induces a 2K2 in G. The induced separation dimension of a graph G is the smallest cardinality of a family L of linear orders of V (G) such that every pair of strongly independent edges in G are separated in at least one of the linear orders in L. For each k ∈ ℕ, the family of graphs with induced separation dimension at most k is denoted by ISD(k). In this article, we initiate a study of this new dimensional parameter. The class ISD(1) or, equivalently, the family of graphs which can be embedded on a line so that every pair of strongly independent edges are disjoint line segments, is already an interesting case. On the positive side, we give characterizations for chordal graphs in ISD(1) which immediately lead to a polynomial time algorithm which determines the induced separation dimension of chordal graphs. On the negative side, we show that the recognition problem for ISD(1) is NP-complete for general graphs. We then briefly study ISD(2) and show that it contains many important graph classes like outerplanar graphs, chordal graphs, circular arc graphs and polygon-circle graphs. Finally, we describe two techniques to construct graphs with large induced separation dimension. The first one is used to show that the maximum induced separation dimension of a graph on n vertices is Θ(lg n) and the second one is used to construct AT-free graphs with arbitrarily large induced separation dimension. © Springer-Verlag GmbH Germany 2016.

Induced separation dimension

Separation dimension of a hypergraph H, denoted by π( H) , is the smallest natural number k so that the vertices of H can be embedded in Rk such that any two disjoint edges of H can be separated by a hyperplane normal to one of the axes. We show that the separation dimension of a hypergraph H is equal to the boxicity of the line graph of H. This connection helps us in borrowing results and techniques from the extensive literature on boxicity to study the concept of separation dimension. In this paper, we study the separation dimension of hypergraphs and graphs. © 2015, Springer Science+Business Media New York.

Algorithmica

Separation Dimension of Graphs and Hypergraphs

Using the theory of monoids and monoid actions, we give a unified framework that handles three common pointer manipulation tasks, namely, data serialisation, deserialisation, and memory allocation. Our main theoretical contribution is the formulation of the notion of a twisted functor, a generalisation of the semi-direct product construction for monoids. We show that semi-direct products and twisted functors are particularly well suited as an abstraction for many pointer manipulation tasks. We describe the implementation of these abstractions in the context of a cryptographic library for Haskell. Twisted functors allow us to abstract all pointer arithmetic and size calculations into a few lines of code, significantly reducing the opportunities for buffer overflows. Copyright is held by the owner/author(s).

Haskell 2016 - Proceedings of the 9th International Symposium on Haskell, co-located with ICFP 2016

How to twist pointers without breaking them

Energy harvesting wireless networks have become a reality in recent years. Designing policies that store and utilize the harvested energy, for achieving the desired network performance, remains one of the key challenges in such networks. To this end, based on the quality of monitoring, we formulate a long-Term time-Averaged joint scheduling and sensing allocation problem in wireless sensor networks with finite energy and data buffers, subject to certain data and battery quality-of-service constraints. Relaxing the finite energy buffer assumption, using virtual queues and techniques from Lyapunov optimization, we obtain the JSSA algorithm. We show that by appropriately choosing the control parameter of the JSSA algorithm, we can achieve a performance gap that decays inversely proportional to the battery capacity. The implementation overhead of the JSSA algorithm scales as O(n). Therefore, we also present a low-complexity distributed version of this algorithm whose implementation overhead scales as O(\log n). © 1983-2012 IEEE.

IEEE Journal on Selected Areas in Communications

Joint Scheduling and Sensing Allocation in Energy Harvesting Sensor Networks with Fusion Centers

The boxicity (respectively cubicity) of a graph G is the least integer k such that G can be represented as an intersection graph of axis-parallel k-dimensional boxes (respectively k-dimensional unit cubes) and is denoted by box(G) (respectively cub(G)). It was shown by Adiga and Chandran (2010) that for any graph G, cub(G)?box(G)?log;bsubesub?α(G)?, where α(G) is the maximum size of an independent set in G. In this note we show that cub(G)?2?log;bsubesub(G)?box(G)+χ(G)?log;bsubesub?α(G)?, where χ(G) is the chromatic number of G. This result can provide a much better upper bound than that of Adiga and Chandran for graph classes with bounded chromatic number. For example, for bipartite graphs we obtain cub(G)?2(box(G)+?log;bsubesub?α(G)?). Moreover, we show that for every positive integer k, there exist graphs with chromatic number k such that for every ?>0, the value given by our upper bound is at most (1+?) times their cubicity. Thus, our upper bound is almost tight. ©2015 Published by Elsevier B.V.

Discrete Mathematics

Upper bound on cubicity in terms of boxicity for graphs of low chromatic number

On-chip trace buffers are increasingly being used for at-speed debug during post-silicon validation. However, the activity history captured by these buffers is small due to their limited size. We propose a novel scheme that extends the captured trace history (by upto 162%) by using a portion of the trace buffer to also store summaries of trace messages. We describe an Overlapped trace buffer architecture that uses a reduced number of ports to capture tapered summaries where both detailed and summary versions of traces are stored simultaneously. We demonstrate the usefulness of the proposed methodology for debugging various classes of bugs encountered during post-silicon validation. © 2016 IEEE.