Abstract

In the pliable index coding (PICOD) problem, a server is to serve multiple clients, each of which possesses a unique subset of the complete message set as side information and requests a new message which it does not have. The goal of the server is to do this using as few transmissions as possible. This work presents a hypergraph coloring approach to the PICOD problem. A textit{conflict-free coloring} of a hypergraph is known from literature as an assignment of colors to its vertices so that each edge of the graph contains one uniquely colored vertex. For a given PICOD problem represented by a hypergraph consisting of messages as vertices and request-sets as edges, we present achievable PICOD schemes using conflict-free colorings of the PICOD hypergraph. Various graph theoretic parameters arising out of such colorings (and some new variants) then give a number of upper bounds on the optimal PICOD length, which we study in this work. Our achievable schemes based on hypergraph coloring include scalar as well as vector linear PICOD schemes. For the scalar case, using the correspondence with conflict-free coloring, we show the existence of an achievable scheme which has length where refers to a parameter of the hypergraph that captures the maximum `incidence' number of other edges on any edge. This result improves upon known achievability results in PICOD literature, in some parameter regimes.

Abstract

We consider the centralized coded caching system where a library of files is available at the server and their subfiles are cached at the clients as prescribed by a placement delivery array (PDA). We are interested in the problem where a specific file in the library is replaced with a new file at the server, the contents of which are correlated with the file being replaced, and this replacement needs to be communicated to the caches. The server loses the original file when the replacement is done and is unaware of the differences between the two files, whereas each cache has access to specific subfiles of the original file as dictated by the PDA. We model the correlation between the two files by assuming that they differ in at the most  subfiles, and aim to reduce the number of bits broadcast by the server to update the caches. We design a new elegant coded transmission strategy for the server to update the caches blindly, and also identify another simple scheme that is based on MDS codes. We then derive converse bounds on the minimum cost ` among all linear strategies. For two well-known families of PDAs – the MaddahAli-Niesen scheme and a scheme by Tang & Ramamoorthy and Yan et al. – we show that our new scheme has cost `when the updates are sufficiently sparse, while the scheme using MDS codes has order-optimal cost when the updates are dense.

Abstract

The problem of data exchange between multiple nodes with (not necessarily uniform) storage and communication capabilities models several current multi-user communication problems like Coded Caching, Data shuffling, Coded Computing, etc. The goal in such problems is to design communication schemes which accomplish the desired data exchange between the nodes with the optimal (minimum) amount of communication load. In this work, we present a converse to such a general data exchange problem between multiple nodes. The expression of the converse depends only on the number of bits to be moved between different subsets of nodes, and does not assume anything further specific about the parameters in the problem. Specific problem formulations, such as those in Coded Caching, Coded Data Shuffling, Coded Distributed Computing, and some of their variants, naturally can be seen as instances of this generic data exchange problem. Applying our generic converse to such problems, we recover known important converses for these settings and some of their variants in a simpler way. Further, for a generic coded caching problem with multiple transmitters, receivers and cache sizes, we show a new general converse which subsumes many existing results. We also employ our bound to obtain a new tight converse bound for the multi-node removal case in the Coded Data Rebalancing problem, in which nodes must exchange information to ‘rebalance’ a storage cluster after some node failures occur.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

Abstract

The performance of replication-based distributed databases is affected due to non-uniform storage across storage nodes (also called data skew) and reduction in the replication factor during operation, particularly due to node additions or removals. Data rebalancing refers to the communication involved between the nodes in correcting this data skew, while maintaining the replication factor. For carefully designed distributed databases, transmitting coded symbols during the rebalancing phase has been recently shown to reduce the communication load of rebalancing. In this work, we look at balanced distributed databases with random placement, in which each data segment is stored in a random subset of r nodes in the system, where r refers to the replication factor of the distributed database. We call these as decentralized databases. For a natural class of such decentralized databases, we propose rebalancing schemes for correcting data skew and the reduction in the replication factor arising due to a single node addition or removal. We give converse arguments which show that our proposed rebalancing schemes are optimal asymptotically in the size of the file.Due to space restrictions, the full version of this paper, containing proofs and additional results, is made available in [1].

Abstract

With the rise in state-of-the-art communication modes for vehicles such as vehicle to vehicle (V2V), vehicle to infrastructure (V2I) and vehicle to cloud (V2C), modern vehicles are increasingly being connected to cloud and fog/edge nodes. These vehicle connectivity modes have enabled the realization of Vehicular Edge Computing (VEC) paradigm, whereby vehicles can leverage fog/edge node resources for storage/computation. In a VEC system, vehicles receive very important and large quantity of data from edge nodes, which is termed as data delivery. In addition, edge nodes can execute some services and send the results back to the vehicle, which is called service delivery. Fast and efficient edge resource allocation for data/service delivery is important in order to serve as many vehicles as possible in the VEC system. However, edge resource allocation is complex with large number of edges and vehicles, while also considering vehicle flow parameters. In this work, we propose Edge-Pairwise Optimal Data/Service Delivery (E-PODS), which is a fast and efficient heuristic for data/service delivery. Through experiments with synthetic and real vehicular traces, we demonstrate that E-PODS is considerably faster than the optimal approach, while making resource allocations that are close to optimal in terms of total edge bandwidth cost and number of serviced vehicles.

Abstract

This paper deals with transistor sizing based static power optimization for multi-stage CMOS circuits using swarm intelligence algorithm. The overall circuit performance is improved by optimizing the individual basic cell performances. Optimized cells are re-used at places with similar circuit scenarios thereby reducing the number of variables to work with. At each stage of execution, the algorithm generates multiple sizing options for basic cells with varying power-delay specifications to choose from. This work proposes a dual sizing approach for critical and non-critical path cells. The overall process has low circuit dependence and has been applied on a wide range of single and multi-stage circuits (including ISCAS benchmark circuits). The approach considers fabrication process parameter variations (for ±3σ design) in addition to a wide range of temperature (-55oC to 125oC) and supply voltage (±10%) variations for robust sizing solutions. Results show leakage reductions up to 63.6%.

Abstract

In this paper, we aim at optimizing the leakage power and propagation delays using optimization algorithms like Glowworm Swarm Optimization and Neighbourhood Cultivation Genetic Algorithm, subjected to variations in Process, Voltage, Temperature and Aging degradation (PVTA) targeting low power or high performance applications. For high performance applications, we synthesize transistor sizes, at which the critical path delay in worst case PVT conditions with 3 years of NBTI aging degradation is optimized below the critical path delay (of initial sizing) at nominal conditions keeping power budget in bound. On the other hand, for low power applications, we obtain transistor sizing where leakage is reduced by more than 50%, keeping a bound on critical path delay. We have also proposed a step by step optimization method for optimizing complex cells. All the pre and post stress simulations are performed using HSPICE for 22nm Metal Gate High-K dielectric model parameters. The temperature range and the supply voltage ranges are -55 °C to 125 °C and 0.72V to 0.88V respectively. The process parameters are considered at ±3σ variation. The ingenuous working of the circuits for the obtained sizing is ensured by Monte Carlo analysis evaluating over entire range of process variations and operating conditions for the intended life time.

Abstract

The paper presents a sub-nW BJT based temperature sensor for ultra-low power microsystems. The sensor is based on amplifying the difference between base-emitter voltages of BJTs using gate-leakage transistors. Implemented in UMC 65nm technology, the sensor occupies an area of 0.005mm 2 . It achieves a maximum non-linearity error of 0.12°C(3σ) over the temperature range of –55°C to 80°C. Without any trimming, a worst case inaccuracy of +0.36°C/ –1.61°C is observed w.r.t process variations, depicting the process-invariant nature of the temperature sensor. It also achieves a low supply sensitivity of 0.56°C/V over a wide supply range of 0.7V-3V. The power consumption of the sensor is 419pW at 27°C and 0.7V supply.

Abstract

This paper proposes low power optimization using a modified swarm intelligence algorithm for the scenariostransistor sizing based static power reduction and low power standard cell generation for approximate computing. In these scenarios, we explore a lower abstraction level and see how standard cells can be tuned to a power-delay-quality optimal point. For transistor sizing, the algorithm considers fabrication process parameter variations (for ±3σ design) in addition to a wide range of temperature (-55oC to 125oC) and supply voltage (±10%) variations to yield PVT aware robust sizing solutions. The approach has been applied on numerous single and multistage circuits (including ISCAS benchmarks) while proposing a dual sizing solution for non-critical and critical path cells. For approximate systems, we present algorithm-generated full adder designs for speech processing systems. The designs vary in terms of accuracy and power. Results show leakage reductions up to 58.2% for conventional and 66.8% with approximation designs for 22nm metal gate high-K (MGK) technology cells.

Abstract

In this paper, we aim at optimizing the leakage power and propagation delays using optimization algorithms like Glowworm Swarm Optimization and Neighbourhood Cultivation Genetic Algorithm, subjected to variations in Process, Voltage, Temperature and Aging degradation (PVTA) targeting low power or high performance applications. For high performance ap­plications, we synthesize transistor sizes, at which the critical path delay in worst case PVT conditions with 3 years of NBTI aging degradation is optimized below the critical path delay (of initial sizing) at nominal conditions keeping power budget in bound. On the other hand, for low power applications, we obtain transistor sizing where leakage is reduced by more than 50%, keeping a bound on critical path delay. All the pre and post stress simulations are performed using HSPICE for 22nm Metal Gate High-K dielectric model parameters. The temperature range and the supply voltage ranges are −55 °C to 125 °C and 0.72V to 0.88V respectively. The process parameters are considered at ±3σ variation. The ingenuous working of the circuits for the obtained sizing is ensured by Monte Carlo analysis evaluating over entire range of process variations and operating conditions for intended life time.