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

Fabless semiconductor industry and government agencies have raised serious concerns about tampering with inserting hardware Trojans (HTs) in an integrated circuit supply chain in recent years. In this paper, a low hardware overhead acceleration method of the detection of HTs based on the insertion of 2-to-1 MUXs as test points is proposed. In the proposed method, the fact that one logical gate has a significant impact on the transition probability of the logical gates in its logical fan-out cone is utilized to optimize the number of the inserted MUXs. The nets which have smaller transition probability than the user-specified threshold and minimal logical depth from the primary inputs are selected as the candidate nets. As for each candidate net, only its input net with smallest signal probability is required to be inserted the MUXs-based test points. The procedure repeats until the minimal transition probability of the entire circuit is not smaller than the threshold value. In order to further optimize the number of required insertions and reduce the overhead, the weighted random pattern technique is also applied. Experiment results on ISCAS'89 benchmark circuits show that our proposed method can achieve remarkable improvement of transition probability with on average 9.50% power, 2.37% delay, and 10.26% area penalty. © 1982-2012 IEEE.

World University root node

IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems

Cost-efficient Acceleration of Hardware Trojan Detection Through Fan-Out Cone Analysis and Weighted Random Pattern Technique

The boxicity (cubicity) of a graph G is the minimum natural number k such that G can be represented as an intersection graph of axis-parallel rectangular boxes (axis-parallel unit cubes) in Rk. In this article, we give estimates on the boxicity and the cubicity of Cartesian, strong and direct products of graphs in terms of invariants of the component graphs. In particular, we study the growth, as a function of d, of the boxicity and the cubicity of the dth power of a graph with respect to the three products. Among others, we show a surprising result that the boxicity and the cubicity of the dth Cartesian power of any given finite graph is, respectively, in O(log. d/log. log. d) and Θ (d/log. d). On the other hand, we show that there cannot exist any sublinear bound on the growth of the boxicity of powers of a general graph with respect to strong and direct products. © 2015 Elsevier Ltd.

European Journal of Combinatorics

Boxicity and cubicity of product graphs

The partial list colouring conjecture due to Albertson, Grossman, and Haas [1] states that for every s-choosable graph G and every assignment of lists of size t, 1 ≤ t ≤ s, to the vertices of G there is an induced subgraph of G on at least (formula presented) vertices which can be properly coloured from these lists. In this paper, we show that the partial list colouring conjecture holds true for certain classes of graphs like claw-free graphs, graphs with chromatic number at least (formula presented), chordless graphs, and series-parallel graphs. © 2015 Australian National University. All rights reserved.

Fulltext

Electronic Journal of Combinatorics

Partial list colouring of certain graphs

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. © 2015 ACM.

ACM Transactions on Architecture and Code Optimization

Falcon: A graph manipulation language for heterogeneous systems

arXiv preprint arXiv:1510.

Fundamental results for a generic implementation of barriers using optical interconnects

Indian Statistical Institute, Kolkata

Some Results on Combinatorial Batch Codes and Permutation Binomials over Finite Fields

Multiple cores are preferred to meet the ever increasing computation demand of embedded systems. A multi-core system is communication intensive with on-chip wire delays and on-chip interconnects accounting for half the dynamic power dissipation. A three-dimensional (3D) stacking of dies enables low intra-chip distances for signal transmission and helps to overcome the interconnect bottleneck of multi-core systems. The 3D integration by through silicon via (TSV) can significantly improve memory-logic communication bandwidth of multi-core systems. However, the 3D multi-core system has poor heat removal capability due to position of the heat-sink. In this paper, we made a study on the thermal profile of DRAM memory layers of 3-D multi-core system. In this study, workloads are distributed to memory layers based on its thermal efficiency such that work load of heavier applications is allocated to the memory layer having highest thermal efficiency and those of lighter applications is allocated to the memory layer with lower thermal efficiency. Experimental result shows that with selective work load distribution, the average peak temperature of the 3D multi-core system is reduced than randomly allocated work load to the memory layers. A memory controller could be designed for run-time distribution of work load to the memory layers which will be addressed in the future work. © 2015 IEEE.

International Conference on Digital Signal Processing, DSP

Memory-access aware work-load distribution for peak-temperature reduction of 3D multi-core embedded systems

Conditions for the existence of heterochromatic Hamiltonian paths and cycles in edge colored graphs are well investigated in literature. A related problem in this domain is to obtain good lower bounds for the length of a maximum heterochromatic path in an edge colored graph G. This problem is also well explored by now and the lower bounds are often specified as functions of the minimum color degree of G - the minimum number of distinct colors occurring at edges incident to any vertex of G - denoted by θ{symbol} (G). Initially, it was conjectured that the lower bound for the length of a maximum heterochromatic path for an edge colored graph G would be ⌈2θ{symbol}(G)3⌉. Chen and Li (2005) showed that the length of a maximum heterochromatic path in an edge colored graph G is at least θ{symbol} (G) - 1, if 1 ≤ θ{symbol} (G) ≤ 7, and at least ⌈3θ{symbol}(G)5⌉ + 1, if θ{symbol} (G) ≥ 8. They conjectured that the tight lower bound would be θ{symbol} (G) - 1 and demonstrated some examples which achieve this bound. An unpublished manuscript from the same authors (Chen, Li) reported to show that if θ{symbol} (G) ≥ 8, then G contains a heterochromatic path of length at least ⌈2θ{symbol}(G)3⌉ + 1. In this paper, we give lower bounds for the length of a maximum heterochromatic path in edge colored graphs without small cycles. We show that if G has no four cycles, then it contains a heterochromatic path of length at least θ{symbol}(G) - o(θ{symbol}(G)) and if the girth of G is at least 4 log2(θ{symbol}(G)) + 2, then it contains a heterochromatic path of length at least θ{symbol}(G) - 2, which is only one less than the bound conjectured by Chen and Li (2005). Other special cases considered include lower bounds for the length of a maximum heterochromatic path in edge colored bipartite graphs and triangle-free graphs: for triangle-free graphs we obtain a lower bound of ⌊5θ{symbol}(G)6⌋ and for bipartite graphs we obtain a lower bound of ⌈6θ{symbol}(G)-37⌉. In this paper, it is also shown that if the coloring is such that G has no heterochromatic triangles, then G contains a heterochromatic path of length at least ⌊13θ{symbol}(G)17⌋. This improves the previously known ⌈3θ{symbol}(G)4⌉ bound obtained by Chen and Li (2011). We also give a relatively shorter and simpler proof showing that any edge colored graph G contains a heterochromatic path of length at least ⌈2θ{symbol}(G)3⌉. © 2015 Elsevier Ltd.

Heterochromatic paths in edge colored graphs without small cycles and heterochromatic-triangle-free graphs

A rainbow matching of an edge-colored graph G is a matching in which no two edges have the same color. There have been several studies regarding the maximum size of a rainbow matching in a properly edge-colored graph G in terms of its minimum degree δ(G). Wang (2011) asked whether there exists a function f such that a properly edge-colored graph G with at least f(δ(G)) vertices is guaranteed to contain a rainbow matching of size δ(G). This was answered in the affirmative later: the best currently known function Lo and Tan (2014) is f(k)=4k-4, for k≥4 and f(k)=4k-3, for k≤3. Afterwards, the research was focused on finding lower bounds for the size of maximum rainbow matchings in properly edge-colored graphs with fewer than 4δ(G)-4 vertices. Strong edge-coloring of a graph G is a restriction of proper edge-coloring where every color class is required to be an induced matching, instead of just being a matching. In this paper, we give lower bounds for the size of a maximum rainbow matching in a strongly edge-colored graph G in terms of δ(G). We show that for a strongly edge-colored graph G, if |V(G)|≥2⌊3δ(G)4⌋, then G has a rainbow matching of size ⌊3δ(G)4⌋, and if |V(G)|<2⌊3δ(G)4⌋, then G has a rainbow matching of size ⌊|V(G)|2⌋. In addition, we prove that if G is a strongly edge-colored graph that is triangle-free, then it contains a rainbow matching of size at least δ(G). © 2015 Elsevier B.V. All rights reserved.

Discrete Mathematics

Rainbow matchings in strongly edge-colored graphs

Combinatorial Batch Codes (CBCs), replication-based variant of Batch Codes introduced by Ishai et al. in [IKOS04], abstracts the following data distribution problem: n data items are to be replicated among m servers in such a way that any k of the n data items can be retrieved by reading at most one item from each server with the total amount of storage over m servers restricted to N. Given parameters m, c, and k, where c and k are constants, one of the challenging problems is to construct c-uniform CBCs (CBCs where each data item is replicated among exactly c servers) which maximizes the value of n. In this work, we present explicit construction of c-uniform CBCs with Ω(mc − 1+ 1/ k) data items. The construction has the property that the servers are almost regular, i. e., number of data items stored in each server is in the range [nc/m −√n/2 ln(4m), nc/m +√n/2 ln(4m)]. The construction is obtained through better analysis and derandomization of the randomized construction presented in [IKOS04]. Analysis reveals almost regularity of the servers, an aspect that so far has not been addressed in the literature. The derandomization leads to explicit construction for a wide range of values of c (for given m and k) where no other explicit construction with similar parameters, i. e., with n = Ω(mc − 1+ 1/ k), is known. Finally, we discuss possibility of parallel derandomization of the construction. © Springer International Publishing Switzerland 2015.