IIT Madras is a public technical and research university located in Chennai, Tamil Nadu. Founded in 1959, it is recognised as an Institute of National Importance.

IIT Madras has been ranked as the top engineering institute in India for four years in a row by the National Institutional Ranking Framework of the MHRD

It currently offers undergraduate, postgraduate and research degrees across 16 disciplines in Engineering, Sciences, Humanities and Management. About 596 faculty belonging to science and engineering departments and centres of the Institute are engaged in teaching, research and industrial consultancy.

IIT Madras

Multithreaded workloads like SPLASH2 and PARSEC generate heavy network traffic. This traffic consists of different packets injected by various nodes at various points of time. A packet consists of three essential components viz., source, destination and data. In this work, we study the opportunity to increase the efficiency of the underlying network. We come up with novel methods to share various components of the packets present in a router at any time. We provide an analysis of the performance gains over contemporary optimization techniques. We conduct experiments on a 64 node setup as well as a 512 node setup and record the energy consumption, IPC gains, network latency and throughputs. We show that our technique outperforms the contemporary Hamiltonian routing by 8.43% and VCTM routing by 7.7% on an average, in terms of IPC speedup. © 2014 IEEE.

Department of Computer Science and Engineering

Proceedings - 2014 8th IEEE/ACM International Symposium on Networks-on-Chip, NoCS 2014

Using packet information for efficient communication in NoCs

With the advent of multiple cores on a single chip, it is common for the systems to have multi-level caches. Multiple levels of cache reduce the pressure on the memory bandwidth by allowing applications to store their frequently accessed data in them. The levels of cache nearer to the core filter the locality in the application access, which can result in high miss rates at farther levels. This piece of study revolves around one question: are all levels of cache needed by all applications during all phases of their execution? The study observes the effect of 2-level and 3-level cache hierarchies on the performance of different applications. On the basis of this study, this study proposes an application aware cache management policy called 'SkipCache', which allows an application to choose a 2-level or 3-level cache hierarchy during run-time. SkipCache dynamically tracks the applications at shared last-level cache (LLC) to identify the applications that do not obtain advantage by using the LLC. Such applications can completely skip the LLC so that other co-scheduled cache friendly applications can efficiently use it. Evaluation of SkipCache in a 4-core chip multi-processor with multi-programmed workloads shows significant performance improvement. SkipCache is orthogonal to other cache management techniques and can be used along with other optimisation techniques to improve the system performance. © The Institution of Engineering and Technology 2015.

GENERAL

IET Computers and Digital Techniques

SkipCache: Application aware cache management for chip multi-processors

Conventionally, consecutively addressed blocks are mapped onto different sets in cache. In this work, we propose a new block address mapping, Set-First Fill (SFFMap), for pipelined L1 data caches wherein consecutively addressed data blocks are mapped onto the same set. This increases the inter-block spatial locality within the cache set. In order to exploit SFFMap, we propose to store and if possible, access the most recently used set in the cache's pipeline registers. Further, selective access (SSA) and selective update (SSU) techniques are proposed for set-buffer to increase the effectiveness of SFFMap. Our experimental evaluation for in-order and out-of-order processors with an 8-way set-associative data cache shows that SFFMap, together with SSA and SSU, achieves around 27% reduction in dynamic energy and 4-5% performance improvement. The proposed techniques need minor modifications to the existing hardware, making it an adoptable design. © 2014 IEEE.

2014 32nd IEEE International Conference on Computer Design, ICCD 2014

SFFMap: Set-First Fill mapping for an energy efficient pipelined data cache

Cache optimizations and DRAM scheduling play an impor-tant role in determining the performance of a system given that the demand for memory is ever increasing. In this paper we track stores both at cache and main memory and apply three different optimizations, one, at the cache level, so that stores are serviced faster and hence load store queue block cycles are reduced, two, at the miss handling architecture wherein we remove entries containing only store requests thereby reducing the cache stall cycles and three, at the main memory where stores are serviced with lesser priority so that actual reads get serviced faster. These three differ-ent memory optimizations combined together (store aware memory optimization, SAMO framework) on an average in-crease the performance of the system and can be augmented with any previously proposed optimization techniques at the memory. SAMO speeds-up the workloads on 4-and 8-core sys-tems by a geometric mean of 5:0% and 7:4%, respectively, with a maximum speed-up of 21:9% and 17:8% on 4-and 8-core systems, respectively. © 2014 ACM.

Proceedings of the 11th ACM Conference on Computing Frontiers, CF 2014

Samo: store aware memory optimizations

The efficiency and effectiveness of an adaptive router in an NoC-based multicore system is evaluated by the performance it achieves under varying inter-core communication traffic. A well-designed selection strategy plays an important role in an adaptive router to act upon dynamic traffic variations. The effectiveness of a selection strategy depends on what metric is used to represent congestion, how precisely this metric captures the actual congestion, and how much cost is involved in capturing the congestion on a real-time scale. Congestion is formed over a period of time due to cumulative and chain reaction effects. We propose novel history-based selection strategies that could be used with any adaptive, deadlock-free,minimal routing in mesh NoCs. Buffer occupancy time and rate of flit flow across reachable ports of neighboring routers in the recent past are captured, propagated, and maintained in a cost-effective way to compute the selection metric. Experimental results on real and synthetic workloads show that our proposed selection strategies significantly outperform state-of-the-Art techniques. © 2014 ACM.

ACM Transactions on Design Automation of Electronic Systems

Implementation and analysis of history-based output channel selection strategies for adaptive routers in mesh NoCs

High-density DRAM devices spend significant time refreshing the DRAM cells, leading to performance drop. The JEDEC DDR4 standard provides a Fine Granularity Refresh (FGR) feature to tackle refresh. Motivated by the observation that in FGR mode, only a few banks are involved, we propose an Enhanced FGR (EFGR) feature that introduces three optimizations to the basic FGR feature and exposes the bank-level parallelism within the rank even during the refresh. The first optimization decouples the nonrefreshing banks. The second and third optimizations determine the maximum number of nonrefreshing banks that can be active during refresh and selectively precharge the banks before refresh, respectively. Our simulation results show that the EFGR feature is able to recover almost 56.6% of the performance loss incurred due to refresh operations. © 2014 ACM.

Fulltext

ACM Transactions on Architecture and Code Optimization

EFGR: An enhanced Fine Granularity Refresh feature for high-performance DDR4 DRAM devices

With the drift from computation centric designs to communication centric designs in the Chip Multi Processor (CMP) era, the interconnect fabric is gaining more importance. An efficient NoC in terms of power, area and average flit latency has a huge impact on the overall performance of a CMP. In the current work, we propose MinBSD - a minimally buffered, single cycle, deflection router. It incorporates different operations (Injection, Ejection, Preemption, Re-injection) in a single module to handle the traffic effectively and ensures smooth flow of flits through router pipeline. It performs overlapped execution of independent operations. These factors not only make MinBSD to operate in a single cycle but also to reduce the critical path latency resulting in a faster interconnect network. Experimental results show that MinBSD reduces the average flit latency on real work loads, reduces die area and power consumption when compared to the existing state-of-the-art minimally buffered deflection routers. © 2014 EDAA.

Proceedings -Design, Automation and Test in Europe, DATE

Minimally buffered single-cycle deflection router

With realization of high density DRAM devices, the amount of time spent in refreshing a DRAM bank is increasing. This reduces the availability of the bank to the requests from the processing cores, leading to degradation in performance. In this work we target to reduce the refresh cycle time of the DRAM device by scattering the rows in a refresh operation to different subarrays and leveraging the available parallelism in their access. Considering 8Gb devices, we show that Scattered Refresh achieves up to 10.2% of overall system performance improvement. Scattered Refresh, being orthogonal to the existing refresh handling techniques, can be employed along with any of them, boosting their effectiveness further. © 2014 IEEE.

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

Scattered refresh: An alternative refresh mechanism to reduce refresh cycle time

Current day multicore processors employ multi-level cache hierarchy with one or two levels of private caches and a shared last-level cache (LLC). Efficient cache replacement policies at LLC are essential for reducing the off-chip memory traffic as well as contention for memory bandwidth. Cache replacement techniques for unicore LLCs may not be efficient for multicore LLCs as multicore LLCs can be shared by applications with varying access behavior, running simultaneously. One application may dominate another by flooding of cache requests and evicting the useful data of the other application. This paper proposes a new cache replacement policy for shared LLC called Application-aware Cache Replacement (ACR). ACR policy prevents victimizing low-access rate application by a high-access rate application. It dynamically keeps track of maximum life-time of cache lines in shared LLC for each concurrent application and helps in efficient utilization of the cache space. Experimental evaluation of ACR technique for 2-core and 4-core systems using SPEC CPU 2000 and 2006 benchmark suites shows significant speed-up improvement over the least recently used and thread-aware dynamic re-reference interval prediction techniques. © 2013 Springer-Verlag.

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

An application-aware cache replacement policy for last-level caches

The challenge for on-chip networks is to provide low latency communication in a very low power budget. To reduce the latency and maintain the simplicity of a mesh topology, torus topology is proposed. As torus topology has an inherent circular dependency, additional effort is needed to prevent deadlock, even if deadlock free routing algorithms are used. The authors propose a novel flow-control mechanism to address cost/performance constraints in torus networks and ensure deadlock freedom. They achieve flow-control by using a prevention mechanism and ensure deadlock freedom while requiring only a single packet buffer per input port. They simplify the router design by having a simple switch allocator that prioritises inflight packets, and a single packet buffer per input port that eliminates the need for virtual channels. They also propose a mechanism to avoid starvation that can arise because of the prioritised arbitration. Experimental validation reveals that the authors design achieves significant improvement in throughput, as compared with the traditional design, while using significantly fewer buffers. © The Institution of Engineering and Technology 2013.

Prevention slot flow-control mechanism for low latency torus network-on-chip

Network-on-Chip (NoC) provides a scalable communication interface for processing cores in large multicore systems. An efficient NoC router should not only minimize the average packet latency of the network but also have minimum pipeline latency, area, and power. Area and power overheads are affecting the scalability and popularity of traditional input buffered routers. In this context minimally buffered deflection routers are emerging as a cost effective alternative. We propose SLIDER, Smart Late Injection DEflection Router, that uses side buffers for accommodating a fraction of deflected flits. The main contributions of this work are smart late injection and selective flit preemption. In SLIDER the injection stage is kept at the end of the router pipeline. This reduces the contention in the arbitration stage, eliminates unwanted intra-router movement of flits and effectively utilizes the idle output channels. We parallelize independent operations in the router pipeline and reduce the pipeline latency by 25%. Experimental results on synthetic and real workloads show that SLIDER reduces average flit latency, channel wastage, and deflection rate, and increases throughput in the network when compared to the state-of-the-art minimally buffered deflection routers. © 2013 IEEE.

2013 IEEE 31st International Conference on Computer Design, ICCD 2013

SLIDER: Smart Late Injection DEflection Router for mesh NoCs

Energy efficiency of the underlying communication framework plays a major role in the performance of multicore systems. NoCs with buffer-less routing are gaining popularity due to simplicity in the router design, low power consumption, and load balancing capacity. With minimal number of buffers, deflection routers evenly distribute the traffic across links. In this paper, we propose an adaptive deflection router, DeBAR, that uses a minimal set of central buffers to accommodate a fraction of mis-routed flits. DeBAR incorporates a hybrid flit ejection mechanism that gives the effect of dual ejection with a single ejection port, an innovative adaptive routing algorithm, and a selective flit buffering based on flit marking. Our proposed router design reduces the average flit latency and the deflection rate, and improves the throughput with respect to the existing minimally buffered deflection routers without any change in the critical path. © 2013 EDAA.

DeBAR: Deflection based adaptive router with minimal buffering

Propagation delay across long on-chip buses is significant when adjacent wires are transitioning in opposite direction (i.e., crosstalk transitions) as compared to transitioning in the same direction. By exploiting Fibonacci number system, we propose a family of Fibonacci coding techniques for crosstalk avoidance, relate them to some of the existing crosstalk avoidance techniques, and show how the encoding logic of one technique can be modified to generate codewords of the other technique. © 2011 IEEE.

IEEE Transactions on Very Large Scale Integration (VLSI) Systems

Fibonacci codes for crosstalk avoidance

It is common for computers to have multi-level caches. This piece of work revolves around one question: Are all levels needed by all applications during all phases of their execution?, especially in the multi programmed scenario where giving the entire cache to one application and depriving the other might actually increase the performance. Copyright © 2012 by the Association for Computing Machinery, Inc. (ACM).

Parallel Architectures and Compilation Techniques - Conference Proceedings, PACT

SkipCache: Miss-rate aware cache management

The effectiveness of an adaptive router in a Network on Chip (NoC) is evaluated by the selection metric it uses and its impact on overall performance. In this paper, we propose a flit flow history based load balancing selection strategy that can be used in any adaptive routers for output port selection. Using this selection strategy, we propose an adaptive router TRACKER, that keeps track of flow of flits through all its ports and updates this tracked information to its neighbors in a cost effective manner. Routers make use of these flit flow estimates to compute a novel selection metric for output port selection of incoming flits. TRACKER outperforms the baseline adaptive router architectures using odd-even routing model with conventional selection metrics like count of free virtual channels, count of fluid buffers and buffer occupancy time at reachable downstream neighbors. © 2012 ACM.

IEEE/ACM International Conference on Computer-Aided Design, Digest of Technical Papers, ICCAD

TRACKER: A low overhead adaptive NoC router with load balancing selection strategy

In order to minimize the conflict miss rate, cache memories can be organized in set-associative manner. The downside of increasing the associativity is increase in the per access energy consumption. In conventional n-way set-associative caches, irrespective of the set-wise demand, each set has n cache ways at its disposal, but cache sets may exhibit nonuniform demand for these cache ways. Exploiting this property, we propose a novel cache architecture, called way sharing cache, wherein by allowing sharing of cache ways among a pair of cache sets, we obtain dynamic energy savings as high as 41% in DL1 cache with negligible performance penalty. © 2012 IEEE.

Proceedings of the IEEE International Conference on VLSI Design

Way sharing set associative cache architecture

Due to technological scaling, process variations have increased significantly, resulting in large variations in the delay of the functional units. Hence, the worst-case approach is becoming increasingly pessimistic in meeting a certain performance yield. The problem therefore is to increase the performance as much as possible while maintaining the desired yield. In this work, we introduce an integer linear programming (ILP) formulation for scheduling and resource binding in high-level synthesis (HLS) which tries to mitigate the effect of timing variations. In the presence of delay variations of resources, as chained resources can give a better latency and performance yield tradeoff, instead of considering them independently, we consider external chaining of resources, that is, two or more resources are connected by external wiring, and exploit operation chaining. Without violating the yield constraints, the proposed ILP formulation chains two consecutive operations and binds these chained operations to chained resources for minimizing the overall latency of the schedule. Our ILP formulation also makes sure that two consecutive operations can be chained over multiple clock cycles so that it becomes possible to access the data in the middle of the chained operations at the start of the clock steps over which the operations are chained. By solving our ILP formulation using ILOG CPLEX, we show that our mechanism achieves lesser latency in most cases, compared to the no-chaining case. Significant performance improvement is achieved even for the 100% yield case, which has never been demonstrated in any published work, to the best of our knowledge. © 2011 ACM.

Timing variation-aware scheduling and resource binding in high-level synthesis

If the route computation operation in an adaptive router returns more than one output channels, the selection strategy chooses one from them based on the congestion metric used. The effectiveness of a selection strategy depends on what metric is used to identify congestion and how precisely that metric captures the actual congestion. The number of cycles a flit stays in a router is a direct indication of the contention level of the output port it desires to move out. We propose buffer Occupancy Factor based Adaptive Router (BOFAR), wherein the history of cycles spent by flits in buffers is used as the congestion metric. BOFAR outperforms the baseline architectures built on minimal odd-even adaptive router model with conventional selection strategies like count of free downstream virtual channels at reachable neighbors, and fluidity of buffers in downstream neighbors. Our experiments on 4x4 mesh NoC with various synthetic traffic patterns show that BOFAR exceeds the performance of best baseline adaptive router with 21% average and 78% maximum latency reduction at saturation load. The reduced average packet latency, increased buffer fluidity fairness, and increased saturation point of BOFAR with minimal overhead in area, power, and wiring makes it a promising alternative to existing adaptive routers in mesh NoCs. © 2011 ACM.

ACM International Conference Proceeding Series

BOFAR: Buffer occupancy factor based adaptive router for mesh NoCs

The challenge for on-chip networks is to provide low latency communication in a very low power budget. To reduce the latency and keep the simplicity of a mesh network, torus network is proposed. As torus networks have inherent circular dependency, additional effort is needed to prevent deadlock, even if deadlock free routing algorithms are used. We describe a novel flow-control mechanism to address cost/performance constraints in torus networks and ensure freedom from deadlock. Flow-control is achieved using a prevention mechanism which uses virtual cut-through switching, and deadlock freedom is achieved by considering only a single packet buffer per input port. We can simplify the router design by having a simple switch allocator, which prioritizes in-flight packets, and a single packet buffer per input port, which eliminates the need for virtual channels. Experimental validation reveals that our design achieves significant improvement in throughput, as compared to the traditional design, using significantly fewer buffers. © 2011 ACM.

NOCS 2011: The 5th ACM/IEEE International Symposium on Networks-on-Chip

Prevention flow-control for low latency torus networks-on-chip

With CMOS process technology scaling to deep submicron level, propagation delay across long on-chip buses is becoming one of the main performance limiting factors in high-performance designs. Propagation delay is very significant when adjacent wires are transitioning in opposite direction as compared to transitioning in the same direction. As opposite transitions on adjacent wires (called as crosstalk transitions) have significant impact on propagation delay, several bus encoding techniques have been proposed in literature to eliminate such transitions. We propose selective shielding technique to eliminate crosstalk transitions. We show that the selective shielding technique requires ⌈3n/2⌉ wires to encode a n-bit bus. SPICE simulations by considering 90nm technology nodes reveal that, for uniformly distributed random data, our technique achieves nearly 39% (21%) delay savings over 10mm-length uncoded 32-bit bus for pipelined (nonpipelined) data transmission at the cost of nearly 7% energy overhead. © 2009 ACM.