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 incorporate the dependencies among the leakage, the temperature and the supply voltage into the 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 constant speed. In addition, we find that the constant speed schedule is still the optimal one to minimize the peak temperature at the temperature stable status when scheduling a periodic task set. We formulate our conclusions into several theorems with formal proofs. ©2011 IEEE.

World University root node

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

Leakage conscious DVS scheduling for peak temperature minimization

In this paper, we consider the problem of modelling the average delay experienced by an application packets of variable length in a single cell IEEE 802.11 DCF wireless local area network. The packet arrival process at each node i is assumed to be a stationary and independent increment random process with mean ai and second moment ai (2). The packet lengths at node i are assumed to be i.i.d random variables Pi with finite mean and second moment. A closed form expression has been derived for the same. We assume the input arrival process across queues to be uncorrelated Poison processes. As the nodes share a single channel, they have to contend with one another for a successful transmission. The mean delay for a packet has been approximated by modelling the system as a 1-limited Random Polling system with zero switchover times. Extensive simulations are conducted to verify the analytical results. © 2011 IEEE.

2011 National Conference on Communications, NCC 2011

Application delay modelling for variable length packets in single cell IEEE 802.11 WLANs

In this paper, we consider the problem of scheduling in multihop wireless networks subject to interference constraints. We consider a graph based representation of wireless networks, where scheduled links adhere to the K-hop link interference model. We develop a distributed greedy heuristic for this scheduling problem. Further, we show that this distributed greedy heuristic computes the exact same schedule as the centralized greedy heuristic. ©2010 IEEE.

2010 IEEE 7th International Conference on Mobile Adhoc and Sensor Systems, MASS 2010

Distributed greedy scheduling for multihop wireless networks

In this article, we formulate for the first time the notion of a quantum evolutionary algorithm. In fact we define a quantum analogue for any elitist (1+1) randomized search heuristic. The quantum evolutionary algorithm, which we call (1+1) quantum evolutionary algorithm (QEA), is the quantum version of the classical (1+1) evolutionary algorithm (EA), and runs only on a quantum computer. It uses Grover search [13] to accelerate the search for improved offsprings. To understand the speedup of the (1+1) QEA over the (1+1) EA, we study the three well known pseudo-Boolean optimization problems ONEMAX, LEADINGONES, and DISCREPANCY. We show that although there is a speedup in the case of ONEMAX and LEADINGONES in the quantum setting, the speedup is less than quadratic. For DISCREPANCY, we show that the speedup is at best constant. The reason for this inconsistency is due to the difference in the probability of making a successful mutation. On the one hand, if the probability of making a successful mutation is large then quantum acceleration does not help much. On the other hand, if the probabilities of making a successful mutation is small then quantum enhancement indeed helps. Copyright 2010 ACM.

Proceedings of the 12th Annual Genetic and Evolutionary Computation Conference, GECCO '10

Can quantum search accelerate evolutionary algorithms?

In this paper, we consider the problem of modelling the average delay experienced by a packet in a single cell IEEE 802.11 DCF wireless local area network. The packet arrival process at each node i is assumed to be Poisson with rate parameter $\lambda$_i. Since the nodes are sharing a single channel, they have to contend with one another for a successful transmission. The mean delay for a packet has been approximated by modelling the system as a 1-limited Random Polling system with zero switchover time. We show that even for non-homogeneous packet arrival processes, the mean delay of packets across the queues are same and depends on the system utilization factor and the aggregate throughput of the MAC. Extensive simulations are conducted to verify the analytical results.

arXiv arXiv

Delay Modelling for Single Cell IEEE 802.11 WLANs Using a Random Polling System

While the dynamic thermal management problem is closely related to the dynamic power management problem, it has its own distinct features. In this paper, we study the feasibility checking problem for real-time periodic task sets under the peak temperature constraint. We show that the traditional scheduling approach, i.e. to repeat the schedule that is feasible through the range of one hyperperiod, does not apply any more. We then present new necessary and sufficient conditions to check the feasibility of real-time schedules. We further incorporate the close relationship of leakage, temperature, and supply voltage into our feasibility analysis, and develop more elaborated feasibility conditions. Our experiments, based on technical parameters derived from a processor using the 65 nm IC technology, demonstrate the effectiveness of our feasibility conditions and, at the same time, highlight the fact that a power/thermal-aware computing technique becomes ineffective at the submicron scale if the inter dependency of leakage, temperature, and supply voltage is not properly addressed. © 2010 IEEE.

IEEE Transactions on Industrial Informatics

Feasibility analysis for temperature-constraint hard real-time periodic tasks

In this paper we formulate and study the problem of representing groups on graphs. We show that with respect to polynomial time Turing reducibility, both abelian and solvable group representability are all equivalent to graph isomorphism, even when the group is presented as a permutation group via generators. On the other hand, the representability problem for general groups on trees is equivalent to checking, given a group G and n, whether a nontrivial homomorphism from G to S n exists. There does not seem to be a polynomial time algorithm for this problem, in spite of the fact that tree isomorphism has polynomial time algorithms. © 2009 Springer Berlin Heidelberg.

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

Representing groups on graphs

Runtime analysis of evolutionary algorithms has become an important part in the theoretical analysis of randomized search heuristics. The first combinatorial problem where rigorous runtime results have been achieved is the well-known single source shortest path (SSSP) problem. Scharnow, Tin-nefeld and Wegener [PPSN 2002, J. Math. Model. Alg. 2004] proposed a multi-objective approach which solves the problem in expected polynomial time. They also suggest a related single-objective fitness function. However, it was left open whether this does solve the problem efficiently, and, in a broader context, whether multi-objective fitness functions for problems like the SSSP yield more efficient evolutionary algorithms. In this paper, we show that the single objective approach yields an efficient (1+1) EA with runtime bounds very close to those of the multi-objective approach. Copyright 2009 ACM.

Proceedings of the 10th ACM SIGEVO Workshop on Foundations of Genetic Algorithms, FOGA'09

Computing single source shortest paths using single-objective fitness functions

We give an O(N · log N ̇ 2O (log* N )algorithm for multiplying two N-bit integers that improves the O(N · log N · log log N) algorithm by Schönhage-Strassen |10|. Both these algorithms use modular arithmetic. Recently, Fürer |2| gave an O(N · log N ̇ 2O (log* N ) algorithm which however uses arithmetic over complex numbers as opposed to modular arithmetic. In this paper, we use multivariate polynomial multiplication along with ideas fron Fürer's algorithm to achieve this improvement in the modular setting. Our algorithm can also be viewed as a p-adic version of Fürer's algorithm. Thus, we show that the two seemingly different approaches to integer multiplication, modular and complex arithmetic, are similar. Copyright 2008 ACM.

Proceedings of the Annual ACM Symposium on Theory of Computing

Fast integer multiplication using modular arithmetic

Many recent works attempt to index multimedia data based on characteristics such as speaker identify and emo- tional content. In this work, speaker segmentation is performed on movies to extract the shots in which the target actor is speaking. A case of speaker identification on conversational speech under noisy conditions - this work is organized into two phases; an audio classification phase, for the removal of non-speech content, followed by a speaker recognition phase. Along with the speaker models, Gaussian Mixture Models are constructed for sound effects like fight sequences and drum beats to refine the removal of non-speech sounds. Results prove the effectiveness of this deviation from the conventional methods. © 2007 IEEE.