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 network function virtualization (NFV), the placement of the virtual network function (VNF) significantly affects the load on switches and the efficiency of bandwidth utilization. Suboptimal placement of VNFs in service chains increases the flow rules in the switches and the ping-pong traffic among the VNFs. This paper presents LightChain, an efficient polynomial run time approach for optimizing VNF placement and service chaining in NFV. LightChain forms the directed acyclic graph of the given service chains and applies topological sorting to the graph. The significance of the proposed approach is as follows: 1) The minimum hop-count in each service chain, 2) Reduction of flow rules on SDN switches, and 3) Elimination of ping-pong traffic. Evaluation results show that LightChain can determine the placement locations of the VNFs in a reasonably short time. Our comparison results with other approach show that LightChain installs a lower number of flow rules in the switches. © 2016 IEEE.

World University root node

IEEE NETSOFT 2016 - 2016 IEEE NetSoft Conference and Workshops: Software-Defined Infrastructure for Networks, Clouds, IoT and Services

LightChain: A lightweight optimisation of VNF placement for service chaining in NFV

Technology scaling has enabled fast increase in the number of cores integrated in many-core systems. However, feature size shrinking also makes large-scale many-core systems vulnerable to thermal failures. Thermal-aware task scheduling is an efficient technique to reduce the run-time temperatures of many-core processors. Most existing thermal-aware task scheduling algorithms leverage centralized scheduling schemes to gather the overall information and generate the task schedule at a center scheduler. Although that scheme can achieve the optimal temperature reduction, however, it faces severe computation bottleneck and communication congestion when the many-core processors evolve to large-scale with hundreds or thousands of cores. In this paper, we propose a decentralized thermal-aware scheduling algorithm to address this problem in large-scale systems. Experiment results on various benchmarks show that our decentralized algorithm achieves significant improvement on scalability (up to 84.3% reduction in monitoring traffic) and similar benefits on temperature reduction (by 5%) when compared with the state-of-the-art thermal-aware scheduling algorithm. © 2015 IEEE.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems

Decentralized Thermal-Aware Task Scheduling for Large-Scale Many-Core Systems

Three-dimensional network-on-chip (3D-NoC) emerges as a potential multi-core architecture delivering high performance, high energy efficiency and great scalability. However, 3D-NoC suffers from severe thermal problems due to its high power density. To solve this problem, thermal-aware scheduling is an effective solution. However, the high complexity of the thermal model of 3D-NoC becomes a major hurdle for developing efficient thermal-aware scheduling algorithms for 3D-NoC. In this paper, we propose a novel thermal-aware task scheduling scheme named as the Bottom-to-Top (B2T) approach to address this challenge. This heuristic-based method performs task allocation on processing units to efficiently minimize the peak temperature and improve the execution time of the tasks with low complexity. The algorithm is first designed for two-layer 3D-NoC and then extended to 3D-NoC with an arbitrary number of layers. When compared to traditional thermal-aware scheduling algorithms designed for 2D-NoC, our B2T algorithm can achieve significant peak temperature reduction (up to 11.9C) and performance improvement (up to 4%) on two-layer 3D-NoC. The improvement becomes more significant as the number of layers in 3D-NoC increases. For four-layer 3D-NoC, the improvement is up to 13.23C peak temperature reduction. © 2016 World Scientific Publishing Company.

Journal of Circuits, Systems and Computers

Thermal-Aware Task Scheduling for 3D-Network-on-Chip: A Bottom to Top Scheme

Negative bias temperature instability (NBTI) has emerged as a critical challenge to lifetime reliability of computing systems. Traditionally, temperature-aware methodologies are used to mitigate the impact of NBTI on aging and degradation of computing systems. However, in the presence of process variation, which is the norm in manycore processors, temperature-aware techniques are inefficient in improving lifetime reliability and can result in poor performance. In this paper, we propose a novel performance constraint-aware task mapping technique to improve lifetime reliability by mitigating NBTI considering on-chip process variation. Our approach consists of two phases, namely design-time and run-time. During design time, we generate Pareto-optimal mappings. Following which, our run-time technique judiciously intervenes to perform workload migration to save the weakest processing core. We compare our approach with performance-greedy and thermal-aware task mapping techniques. The experiment results demonstrate that our approach outperforms other two techniques and improves lifetime reliability of a manycore system as much as 54% without violating the throughput constraint. © 2016 ACM.

Proceedings of the ACM Great Lakes Symposium on VLSI, GLSVLSI

Performance constraint-aware task mapping to optimize lifetime reliability of manycore systems

A D-disc around a vertex v of a graph G = (V,E) is the subgraph induced by all vertices of distance at most D from v. We show that the structure of an outerplanar graph on n vertices is determined, up to modification (insertion or deletion) of at most ϵn edges, by a set of D-discs around the vertices, for D = D(ϵ) that is independent of the size of the graph. Such a result was already known for planar graphs (and any hyperfinite graph class), in the limited case of bounded degree graphs (that is, their maximum degree is bounded by some fixed constant, independent of |V |). We prove this result with no assumption on the degree of the graph. A pure combinatorial consequence of this result is that two outerplanar graphs that share the same local views are close to be isomorphic. We also obtain the following property testing results in the sparse graph model: graph isomorphism is testable for outerplanar graphs by poly(log n) queries. every graph property is testable for outerplanar graphs by poly(log n) queries. We note that we can replace outerplanar graphs by a slightly more general family of k-edgeouterplanar graphs. The only previous general testing results, as above, where known for forests (Kusumoto and Yoshida), and for some power-law graphs that are extremely close to be bounded degree hyperfinite (by Ito).

Leibniz International Proceedings in Informatics, LIPIcs

Every property of outerplanar graphs is testable

Efficient resource planning in energy harvesting wireless sensor networks (WSNs) 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. © 1983-2012 IEEE.

IEEE Journal on Selected Areas in Communications

A framework for designing multihop energy harvesting sensor networks

We study some well-known graph contraction problems in the recently introduced framework of lossy kernelization. In classical kernelization, given an instance (I, k) of a parameterized problem, we are interested in obtaining (in polynomial time) an equivalent instance (I′, k′) of the same problem whose size is bounded by a function in k. This notion however has a major limitation. Given an approximate solution to the instance (I′, k′), we can say nothing about the original instance (I, k). To handle this issue, among others, the framework of lossy kernelization was introduced. In this framework, for a constant α, given an instance (I, k) we obtain an instance (I′, k′) of the same problem such that, for every c &gt; 1, any c-approximate solution to (I′, k′) can be turned into a (cα)-approximate solution to the original instance (I, k) in polynomial time. Naturally, we are interested in a polynomial time algorithm for this task, and further require that |I′|+k′ = kO(1). Akin to the notion of polynomial time approximation schemes in approximation algorithms, a parameterized problem is said to admit a polynomial size approximate kernelization scheme (PSAKS) if it admits a polynomial size α-approximate kernel for every approximation parameter α &gt; 1. In this work, we design PSAKSs for TREE CONTRACTION, STAR CONTRACTION, OUT-TREE CONTRACTION and CACTUS CONTRACTION problems. These problems do not admit polynomial kernels, and we show that each of them admit a PSAKS with running time kf(α)|I|O(1) that returns an instance of size kg(α) where f(α) and g(α) are constants depending on α. © R. Krithika, Pranabendu Misra, Ashutosh Rai, and Prafullkumar Tale.

Lossy kernels for graph contraction problems

The internal state of the complex modern processors often needs to be dumped out frequently during postsilicon validation. Since the caches hold most of the state, the volume of data dumped and the transfer time are dominated by the large caches present in the architecture. The limited bandwidth to transfer data present in these large caches off-chip results in stalling the processor for long durations when dumping the cache contents off-chip. To alleviate this, we propose to transfer only those cache lines that were updated since the previous dump. Since maintaining a bit-vector with a separate bit to track the status of individual cache lines is expensive, we propose two methods: 1) where a bit tracks multiple cache lines and 2) an Interval Table which stores only the starting and ending addresses of continuous runs of updated cache lines. Both methods require significantly lesser space compared with a bit-vector, and allow the designer to choose the amount of space to allocate for this design-for-debug feature. The impact of reducing storage space is that some nonupdated cache lines are dumped too. We attempt to minimize such overheads. We propose a scheme to share such cache update tracking hardware (or Update Trackers) across multiple caches in case of physically distributed caches so that they are replicated fewer times, thereby limiting the area overhead. We show that the proposed Update Trackers occupy less than 1% of cache area for both the shared and distributed caches. © 2016 IEEE.

Area-Aware Cache Update Trackers for Postsilicon Validation

Barriers have long been recognized as important performance-critical constructs in parallel applications. As a consequence, researchers have proposed fast implementations of barriers in both traditional electrical networks and in non-conventional networks such as optical NoCs. We prove in this paper that current protocols for barriers in optical NoCs are simplistic and cannot be trivially extended to accommodate for normal events that arise in regular operation such as presence of multiple applications, context switches, thread migrations, and variability in the number of active threads. We propose two generic protocols for barriers that can take all such cases into account, are fast, and try to minimize the number of messages sent over the NoC. One of these protocols is a centralized protocol (suitable for less cores), and the other is a distributed protocol, which is scalable. For a suite of standard benchmarks we found the latter to yield a mean speedup of 30.77% over a design that uses a hardware tree barrier. Our barrier implementation per se is roughly 2X and 20X faster than prior implementations that use transmission lines and electrical links respectively. © 2016 IEEE.

Proceedings of the IEEE International Conference on VLSI Design

A Generic Implementation of Barriers Using Optical Interconnects

We study projective dimension, a graph parameter (denoted by pd(G) for a graph G), introduced by Pudlák and Rödl (1992). For a Boolean function f(on n bits), Pudlák and Rödl associated a bipartite graph Gf and showed that size of the optimal branching program computing f (denoted by bpsize(f)) is at least pd(Gf) (also denoted by pd(f)). Hence, proving lower bounds for pd(f) imply lower bounds for bpsize(f). Despite several attempts (Pudlák and Rödl (1992), Rónyai et.al, (2000)), proving super-linear lower bounds for projective dimension of explicit families of graphs has remained elusive. We observe that there exist a Boolean function f for which the gap between the pd(f) and bpsize(f)) is 2Ω(n). Motivated by the argument in Pudlák and Rödl (1992), we define two variants of projective dimension - projective dimension with intersection dimension 1 (denoted by upd(f)) and bitwise decomposable projective dimension (denoted by bpdim(f)). We show the following results: (a) We observe that there exist a Boolean function f for which the gap between upd(f) and bpsize(f) is 2Ω(n). In contrast, we also show that the bitwise decomposable projective dimension characterizes size of the branching program up to a polynomial factor. That is, there exists a large constant c &gt; 0 and for any function f, bpdim(f)/6 ≤ bpsize(f) ≤ (bpdim(f))c. (b) We introduce a new candidate function family f for showing super-polynomial lower bounds for bpdim(f). As our main result, we demonstrate gaps between pd(f) and the above two new measures for f: pd(f) = O(√n) upd(f) = Ω(n) bpdim(f) = Ω(n1.5/log n). (c) Although not related to branching program lower bounds, we derive exponential lower bounds for two restricted variants of pd(f) and upd(f) respectively by observing that they are exactly equal to well-studied graph parameters - bipartite clique cover number and bipartite partition number respectively. © Krishnamoorthy Dinesh, Sajin Koroth, and Jayalal Sarma.