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

Leakage Temperature Dependency Aware Real-Time Scheduling for Power and Thermal Optimization

With exponentially increased transistor density on multi-core platforms, the power explosion and consequently soaring chip temperature have become critical challenges for system designers. Moreover, the increasing chip temperature results in higher leakage power, hence further aggravates the increment of the overall power consumption [1]. Thus, the dramatically growing power/energy consumption and chip temperature severely affect the cost, reliability and performance of the systems [4].

World University root node

ACM SIGBED Review

Thermal-aware energy minimization for real-time scheduling on multi-core systems

Given a connected outerplanar graph G with pathwidth p, we give an algorithm to add edges to G to get a supergraph of G, which is 2-vertex-connected, outerplanar and of pathwidth O(p). As a consequence, we get a constant factor approximation algorithm to compute a straight line planar drawing of any outerplanar graph, with its vertices placed on a two dimensional grid of minimum height. This settles an open problem raised by Biedl [3]. © 2013 Springer-Verlag Berlin Heidelberg.

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

2-connecting outerplanar graphs without blowing up the pathwidth

We give the first polynomial-time algorithm for checking whether the Galois group Gal ( f ) of an input polynomial f (X) ε f[X] is nilpotent: the running time of our algorithm is bounded by a polynomial in the size of the coefficients of f and the degree of f. Additionally, we give a deterministic polynomial-time algorithm that, when given as input a polynomial f (X) ε f[X] with nilpotent Galois group, computes for each prime factor p of #Gal (f), a polynomial gp(X) ε f[X] whose Galois group of is the p-Sylow subgroup of Gal (f). © 2012 ACM.

ACM Transactions on Algorithms

Testing nilpotence of galois groups in polynomial time

Vertex cover and odd cycle transversal are minimum cardinality sets of vertices of a graph whose deletion makes the resultant graph 1-colorable and 2-colorable, respectively. As a natural generalization of these well-studied problems, we consider the Graph r-Partization problem of finding a minimum cardinality set of vertices whose deletion makes the graph r-colorable. We explore further connections to Vertex Cover by introducing Generalized Above Guarantee Vertex Cover, a variant of Vertex Cover defined as: Given a graph G, a clique cover K of G and a non-negative integer k, does G have a vertex cover of size at most k +Σ CεK(|C| - 1)? We study the parameterized complexity hardness of this problem by a reduction from r-Partization. We then describe sequacious fixed-parameter tractability results for r-Partization, parameterized by the solution size k and the required chromaticity r, in perfect graphs and split graphs. For Odd Cycle Transversal, we describe an O*(2 k) algorithm for perfect graphs and a polynomial-time algorithm for co-chordal graphs. © 2012 Springer-Verlag.

Generalized above guarantee vertex cover and r-partization

arXiv preprint arXiv:1111.

Approximate Aggregate Utility Maximization in Multi-Hop Wireless Networks using Distributed Greedy Scheduling

Over the years, the chip power density has been increased exponentially due to the increasingly complicated circuit architecture as well as the continuous miniaturization of the transistor feature size. High power consumption has directly translated to high chip temperature which adversely affects the system performance/reliability and increases the cooling/packaging costs. Moreover, high chip temperature also elevates the leakage power consumption, which further augments the overall power consumption and thus the operating temperature. In this paper, we incorporate the leakage/temperature dependency as well as the nonnegligible transition overhead into analysis and present a novel real-time speed scheduling algorithm, namely M-Oscillating, that can reduce the peak temperature of a system when executing a hard real-time periodic task set. We analytically prove the correctness of the proposed algorithm based on a processor model that can effectively account for the leakage/temperature relationship. We validate the effectiveness of the proposed algorithm by comparing it with the existing work on two platforms. The first platform is a C/Matlab based chip-level thermal/power simulator, and the second platform is a more practical one built based on a desktop computer running SPEC CPU2000 benchmark programs. The experimental results obtained from both platforms demonstrate the superiority of the proposed M-Oscillating scheme over the existing approach in peak temperature reduction and feasibility improvement. Copyright © 2012 American Scientific Publishers All rights reserved.

Journal of Low Power Electronics

Leakage aware scheduling on maximum temperature minimization for periodic hard real-time systems

The boxicity (cubicity) of a graph G, denoted by box(G) (respectively cub(G)), is the minimum integer k such that G can be represented as the intersection graph of axis parallel boxes (cubes) in ℝk. The problem of computing boxicity (cubicity) is known to be inapproximable in polynomial time even for graph classes like bipartite, co-bipartite and split graphs, within an O(n0.5-ε) factor for any ε &gt; 0, unless NP = ZPP. We prove that if a graph G on n vertices has a clique on n - k vertices, then box(G) can be computed in time n22 O(k2 log k). Using this fact, various FPT approximation algorithms for boxicity are derived. The parameter used is the vertex (or edge) edit distance of the input graph from certain graph families of bounded boxicity - like interval graphs and planar graphs. Using the same fact, we also derive an O(n√log log n/√ log n) factor approximation algorithm for computing boxicity, which, to our knowledge, is the first o(n) factor approximation algorithm for the problem. We also present an FPT approximation algorithm for computing the cubicity of graphs, with vertex cover number as the parameter. © 2012 Springer-Verlag.

Polynomial time and parameterized approximation algorithms for boxicity

Batch codes, introduced by Ishai et al. in [11], are methods for solving the following data storage problem: n data items are to be stored in m servers in such a way that any k of the n items can be retrieved by reading at most t items from each server, and that the total number of items stored in m servers is N. A combinatorial batch code (CBC) is a batch code where each data item is stored without change, i.e., each stored data item is a copy of one of the n data items. One of the basic yet challenging problems is to find optimal CBCs, i.e., CBCs for which total storage (N) is minimal for given values of n, m, k, and t. In [13], Paterson et al. exclusively studied CBCs and gave constructions of some optimal CBCs. In this article, we give a lower bound on the total storage (N) for CBCs. We give explicit construction of optimal CBCs for a range of values of n. For a different range of values of n, we give explicit construction of optimal and almost optimal CBCs. Our results partly settle an open problem of [13]. © 2012 AIMS.

Advances in Mathematics of Communications

Combinatorial batch codes: A lower bound and optimal constructions

As the consequence of the exponentially increased power density on integrated circuits, thermal issues are becoming critical in design of computing systems. Moreover, as both leakage and thermal issues have become more prominent in the deep sub-micron domain, a power and thermal aware design technique becomes less effective if the leakage/temperature dependency is not appropriately addressed. In this paper, we take into account the dependency among the leakage, the temperature, and the supply voltage in our theoretical analysis and explore the fundamental characteristics on how to employ dynamic voltage scaling (DVS) to reduce the peak operating temperature. We find that, for a specific interval, a real-time schedule using the lowest constant speed is not necessarily the optimal choice any more in minimizing the peak temperature. We identify the scenarios when a schedule using two different speeds can outperform the one using the lowest constant speed. In addition, we find that, when scheduling a periodic task set, the constant speed schedule is still the optimal solution for minimizing the peak temperature when the temperature is at its stable status. We formulate our conclusions into several theorems with formal proofs. © 2012 Elsevier B.V. All rights reserved.