Codes with Locality for Two Erasures

In this paper, we study codes with locality that can recover from two erasures via a sequence of two local, parity-check computations. By a local parity-check computation, we mean recovery via a single parity-check equation associated with small Hamming weight. Earlier approaches considered recovery in parallel; the sequential approach allows us to potentially construct codes with improved minimum distance. These codes, which we refer to as locally 2-reconstructible codes, are a natural generalization along one direction, of codes with all-symbol locality introduced by Gopalan et al, in which recovery from a single erasure is considered. By studying the generalized Hamming weights of the dual code, we derive upper bounds on the minimum distance of locally 2-reconstructible codes and provide constructions for a family of codes based on Turan graphs, that are optimal with respect to this bound. The minimum distance bound derived here is universal in the sense that no code which permits all-symbol local recovery from 2 erasures can have larger minimum distance regardless of approach adopted. Our approach also leads to a new bound on the minimum distance of codes with all-symbol locality for the single-erasure case.

PLUTO plus : Near-Complete Modeling of Affine Transformations for Parallelism and Locality

Affine transformations have proven to be very powerful for loop restructuring due to their ability to model a very wide range of transformations. A single multi-dimensional affine function can represent a long and complex sequence of simpler transformations. Existing affine transformation frameworks like the Pluto algorithm, that include a cost function for modern multicore architectures where coarse-grained parallelism and locality are crucial, consider only a sub-space of transformations to avoid a combinatorial explosion in finding the transformations. The ensuing practical tradeoffs lead to the exclusion of certain useful transformations, in particular, transformation compositions involving loop reversals and loop skewing by negative factors. In this paper, we propose an approach to address this limitation by modeling a much larger space of affine transformations in conjunction with the Pluto algorithm's cost function. We perform an experimental evaluation of both, the effect on compilation time, and performance of generated codes. The evaluation shows that our new framework, Pluto+, provides no degradation in performance in any of the Polybench benchmarks. For Lattice Boltzmann Method (LBM) codes with periodic boundary conditions, it provides a mean speedup of 1.33x over Pluto. We also show that Pluto+ does not increase compile times significantly. Experimental results on Polybench show that Pluto+ increases overall polyhedral source-to-source optimization time only by 15%. In cases where it improves execution time significantly, it increased polyhedral optimization time only by 2.04x.

Adaptive significance of the Indian caste system: an ecological perspective

Indian society is an agglomeration of several thousand endogamous groups or castes each with a restricted geographical range and a hereditarily determine mode of subsistence. These reproductively isolated castes may be compared to biological species, and the society thought of as a biological community with each caste having its specific ecological niche. In this paper we examine the ecological-niche relationships of castes which are directly dependent on natural resources. Evidence is presented to show that castes living together in the same region had so organized their pattern of resource use as to avoid excessive intercaste competition for limiting resources. Furthermore, territorial division of the total range of the caste regulated intra-caste competition. Hence, a particular plant or animal resource in a given locality was used almost exclusively by a given lineage within a caste generation after generation. This favoured the cultural evolution of traditions ensuring sustainable use of natural resources. This must have contributed significantly to the stability of Indian caste society over several thousand years. The collapse of the base of natural resources and increasing monetarization of the economy has, however, destroyed the earlier complementarity between the different castes and led to increasing conflicts between them in recent years.

A Novel Cache Architecture and Placement Framework for Packet Forwarding Engines

Packet forwarding is a memory-intensive application requiring multiple accesses through a trie structure. With the requirement to process packets at line rates, high-performance routers need to forward millions of packets every second with each packet needing up to seven memory accesses. Earlier work shows that a single cache for the nodes of a trie can reduce the number of external memory accesses. It is observed that the locality characteristics of the level-one nodes of a trie are significantly different from those of lower level nodes. Hence, we propose a heterogeneously segmented cache architecture (HSCA) which uses separate caches for level-one and lower level nodes, each with carefully chosen sizes. Besides reducing misses, segmenting the cache allows us to focus on optimizing the more frequently accessed level-one node segment. We find that due to the nonuniform distribution of nodes among cache sets, the level-one nodes cache is susceptible t high conflict misses. We reduce conflict misses by introducing a novel two-level mapping-based cache placement framework. We also propose an elegant way to fit the modified placement function into the cache organization with minimal increase in access time. Further, we propose an attribute preserving trace generation methodology which emulates real traces and can generate traces with varying locality. Performanc results reveal that our HSCA scheme results in a 32 percent speedup in average memory access time over a unified nodes cache. Also, HSC outperforms IHARC, a cache for lookup results, with as high as a 10-fold speedup in average memory access time. Two-level mappin further enhances the performance of the base HSCA by up to 13 percent leading to an overall improvement of up to 40 percent over the unified scheme.

K-Ar ages of biotite and muscovite from Pangong metamorphic complex, Shyok suture zone, India: Implications for the youngest post-collision metamorphic event in Ladakh Himalaya

The garnet-kyanite-staurolite and garnet-biotite-staurolite gneisses were collected from a locality within Lukung area that belongs to the Pangong metamorphic complex in Shyok valley, Ladakh Himalaya. The kyanite-free samples have garnet and staurolite in equilibrium, where garnets show euhedral texture and have flat compositional profile. On the other hand, the kyanite-bearing sample shows equilibrium assemblage of garnet-kyanite-staurolite along with muscovite and biotite. In this case, garnet has an inclusion rich core with a distinct grain boundary, which was later overgrown by inclusion free euhedral garnet. Garnet cores are rich in Mn and Ca, while the rims are poor in Mn and rich in Fe and Mg, suggesting two distinct generations of growth. However, the compositional profiles and textural signature of garnets suggests the same stage of P -T evolution for the formation of the inclusion free euhedral garnets in the kyanite-free gneisses and the inclusion free euhedral garnet rims in the kyanite-bearing gneiss. Muscovites from the four samples have consistent K-Ar ages, suggesting the cooling age (∼ 10 Ma) of the gneisses. These ages make a constraint on the timing of the youngest post-collision metamorphic event that may be closely related to an activation of the Karakoram fault in Pangong metamorphic complex.

Why we must empower people to conserve Biodiversity

Conserving blodiversity has in recent years become a concern of the global elite because of the commercial potential of the emerging biotechnologies. But much of this blodiversity resides In the Third World tropics which are currently being drained of their biological and mineral wealth. This process goes on because the costs of the resultant degradation are entirely passed on to the poor of the Third World countryside who perforce have to depend on resources gathered or produced with their own labour from their surroundings. The elite have always found a substitute whenever a particular resource, or a particular locality, has been exploited to exhaustion. Indeed, given their record, commercial interests are likely to abandon the new found concern for conservation once they acquire control over adequate levels of genetic resources in ex situ storages. Long term conservation of biodiversity must therefore be attempted through empowering and suitably rewarding people of the Third World countryside whose well being is linked to the sustainable use of biological resources and conservation of the biodiversity in their own localities.

Present status of Gottigere Tank : Indicator of Decision maker’s apathy

Gottigere lake with a water spread area of about 14.98 ha is located in the Bellandur Lake catchment of the South Pennar River basin. In recent years, this lake catchment has been subjected to environmental stress mainly due to the rampant unplanned developmental activities in the catchment. The functional ability of the ecosystem is impaired due to structural changes in the ecosystem. This is evident from poor water quality, breeding of disease vectors, contamination of groundwater in the catchment, frequent flooding in the catchment due to topography alteration, decline in groundwater table, erosion in lake bed, etc. The development plans of the region (current as well as the proposed) ignore the integrated planning approaches considering all components of the ecosystem. Serious threats to the sustainability of the region due to lack of holistic approaches in aquatic resources management are land use changes (removal of vegetation cover, etc.), point and non-point sources of pollution impairing water quality, dumping of solid waste (building waste, etc.). Conservation of lake ecosystem is possible only when the physical and chemical integrity of its catchment is maintained. Alteration in the catchment either due to land use changes (leading to paved surface area from vegetation cover), alteration in topography, construction of roads in the immediate vicinity are detrimental to water yield in the catchment and hence, the sustenance of the lake. Open spaces in the form of lakes and parks aid as kidney and lung in an urban ecosystem, which maintain the health of the people residing in the locality. Identification of core buffer zones and conservation of buffer zones (500 to 1000 m from shore) is to be taken up on priority for conservation and sustainable management of Bangalore lakes. Bangalore is located over a ridge delineating four watersheds, viz. Hebbal, Koramangala, Challaghatta and Vrishabhavathi. Lakes and tanks are an integral part of natural drainage and help in retaining water during rainfall, which otherwise get drained off as flash floods. Each lake harvests rainwater from its catchment and surplus flows downstream spilling into the next lake in the chain. The topography of Bangalore has uniquely supported the creation of a large number of lakes. These lakes form chains, being a series of impoundments across streams. This emphasises the interconnectivity among Bangalore lakes, which has to be retained to prevent Bangalore from flooding or from water scarcity. The main source of replenishment of groundwater is the rainfall. The slope of the terrain allows most of the rainwater to flow as run-off. With the steep gradients available in the major valleys of Bangalore, the rainwater will flow out of the city within four to five hours. Only a small fraction of the rainwater infiltrates into the soil. The infiltration of water into the subsoil has declined with more and more buildings and paved road being constructed in the city. Thus the natural drainage of Bangalore is governed by flows from the central ridge to all lower contours and is connected with various tanks and ponds. There are no major rivers flowing in Bangalore and there is an urgent need to sustain these vital ecosystems through proper conservation and management measures. The proposed peripheral ring road connecting Hosur Road (NH 7) and Mysore Road (SH 17) at Gottigere lake falls within the buffer zone of the lake. This would alter the catchment integrity and hence water yield affecting flora, fauna and local people, and ultimately lead to the disappearance of Gottigere lake. Developmental activities in lake catchments, which has altered lake’s ecological integrity is in violation of the Indian Fisheries Act – 1857, the Indian Forest Act – 1927, Wildlife (Protection) Act – 1972, Water (Prevention and Control of Pollution) Act – 1974, Water (Prevention and Control of Pollution) Act – 1977, Forest (Conservation Act) – 1980, Environmental (Protection) Act – 1986, Wildlife (Protection) Amendment Act – 1991 and National Conservation Strategy and Policy Statement on Environment and Development – 1992. Considering 65% decline of waterbodies in Bangalore (during last three decades), decision makers should immediately take preventive measures to ensure that lake ecosystems are not affected. This report discusses the impacts due to the proposed infrastructure developmental activities in the vicinity of Gottigere tank.

Region Based Structure Layout Optimization by Selective Data Copying

As the gap between processor and memory continues to grow Memory performance becomes a key performance bottleneck for many applications. Compilers therefore increasingly seek to modify an application’s data layout to improve cache locality and cache reuse. Whole program Structure Layout [WPSL] transformations can significantly increase the spatial locality of data and reduce the runtime of programs that use link-based data structures, by increasing the cache line utilization. However, in production compilers WPSL transformations do not realize the entire performance potential possible due to a number of factors. Structure layout decisions made on the basis of whole program aggregated affinity/hotness of structure fields, can be sub optimal for local code regions. WPSL is also restricted in applicability in production compilers for type unsafe languages like C/C++ due to the extensive legality checks and field sensitive pointer analysis required over the entire application. In order to overcome the issues associated with WPSL, we propose Region Based Structure Layout (RBSL) optimization framework, using selective data copying. We describe our RBSL framework, implemented in the production compiler for C/C++ on HP-UX IA-64. We show that acting in complement to the existing and mature WPSL transformation framework in our compiler, RBSL improves application performance in pointer intensive SPEC benchmarks ranging from 3% to 28% over WPSL

Emulating Optimal Replacement with a Shepherd Cache

The inherent temporal locality in memory accesses is filtered out by the L1 cache. As a consequence, an L2 cache with LRU replacement incurs significantly higher misses than the optimal replacement policy (OPT). We propose to narrow this gap through a novel replacement strategy that mimics the replacement decisions of OPT. The L2 cache is logically divided into two components, a Shepherd Cache (SC) with a simple FIFO replacement and a Main Cache (MC) with an emulation of optimal replacement. The SC plays the dual role of caching lines and guiding the replacement decisions in MC. Our pro- posed organization can cover 40% of the gap between OPT and LRU for a 2MB cache resulting in 7% overall speedup. Comparison with the dynamic insertion policy, a victim buffer, a V-Way cache and an LRU based fully associative cache demonstrates that our scheme performs better than all these strategies.

Enhancing Speedup in Network Processing Applications by Exploiting Instruction Reuse with Flow Aggregation

Instruction reuse is a microarchitectural technique that improves the execution time of a program by removing redundant computations at run-time. Although this is the job of an optimizing compiler, they do not succeed many a time due to limited knowledge of run-time data. In this paper we examine instruction reuse of integer ALU and load instructions in network processing applications. Specifically, this paper attempts to answer the following questions: (1) How much of instruction reuse is inherent in network processing applications?, (2) Can reuse be improved by reducing interference in the reuse buffer?, (3) What characteristics of network applications can be exploited to improve reuse?, and (4) What is the effect of reuse on resource contention and memory accesses? We propose an aggregation scheme that combines the high-level concept of network traffic i.e. "flows" with a low level microarchitectural feature of programs i.e. repetition of instructions and data along with an architecture that exploits temporal locality in incoming packet data to improve reuse. We find that for the benchmarks considered, 1% to 50% of instructions are reused while the speedup achieved varies between 1% and 24%. As a side effect, instruction reuse reduces memory traffic and can therefore be considered as a scheme for low power.

Incremental Cycle Detection, Topological Ordering, and Strong Component Maintenance

We present two online algorithms for maintaining a topological order of a directed n-vertex acyclic graph as arcs are added, and detecting a cycle when one is created. Our first algorithm handles m arc additions in O(m(3/2)) time. For sparse graphs (m/n = O(1)), this bound improves the best previous bound by a logarithmic factor, and is tight to within a constant factor among algorithms satisfying a natural locality property. Our second algorithm handles an arbitrary sequence of arc additions in O(n(5/2)) time. For sufficiently dense graphs, this bound improves the best previous bound by a polynomial factor. Our bound may be far from tight: we show that the algorithm can take Omega(n(2)2 root(2lgn)) time by relating its performance to a generalization of the k-levels problem of combinatorial geometry. A completely different algorithm running in Theta (n(2) log n) time was given recently by Bender, Fineman, and Gilbert. We extend both of our algorithms to the maintenance of strong components, without affecting the asymptotic time bounds.

Optimal Linear Codes with a Local-Error-Correction Property

Motivated by applications to distributed storage, Gopalan et al recently introduced the interesting notion of information-symbol locality in a linear code. By this it is meant that each message symbol appears in a parity-check equation associated with small Hamming weight, thereby enabling recovery of the message symbol by examining a small number of other code symbols. This notion is expanded to the case when all code symbols, not just the message symbols, are covered by such ``local'' parity. In this paper, we extend the results of Gopalan et. al. so as to permit recovery of an erased code symbol even in the presence of errors in local parity symbols. We present tight bounds on the minimum distance of such codes and exhibit codes that are optimal with respect to the local error-correction property. As a corollary, we obtain an upper bound on the minimum distance of a concatenated code.

Virtually cool ternary content addressable memory

Fast content addressable data access mechanisms have compelling applications in today's systems. Many of these exploit the powerful wildcard matching capabilities provided by ternary content addressable memories. For example, TCAM based implementations of important algorithms in data mining been developed in recent years; these achieve an an order of magnitude speedup over prevalent techniques. However, large hardware TCAMs are still prohibitively expensive in terms of power consumption and cost per bit. This has been a barrier to extending their exploitation beyond niche and special purpose systems. We propose an approach to overcome this barrier by extending the traditional virtual memory hierarchy to scale up the user visible capacity of TCAMs while mitigating the power consumption overhead. By exploiting the notion of content locality (as opposed to spatial locality), we devise a novel combination of software and hardware techniques to provide an abstraction of a large virtual ternary content addressable space. In the long run, such abstractions enable applications to disassociate considerations of spatial locality and contiguity from the way data is referenced. If successful, ideas for making content addressability a first class abstraction in computing systems can open up a radical shift in the way applications are optimized for memory locality, just as storage class memories are soon expected to shift away from the way in which applications are typically optimized for disk access locality.

Row-buffer reorganization: simultaneously improving performance and reducing energy in DRAMs

In this paper, based on the temporal and spatial locality characteristics of memory accesses in multicores, we propose a re-organization of the existing single large row buffer in a DRAM bank into multiple smaller row-buffers. The proposed configuration helps improve the row hit rates and also brings down the energy required for row-activations. The major contribution of this work is proposing such a reorganization without requiring any significant changes to the existing widely accepted DRAM specifications. Our proposed reorganization improves performance by 35.8%, 14.5% and 21.6% in quad, eight and sixteen core workloads along with a 42%, 28% and 31% reduction in DRAM energy. Additionally, we introduce a Need Based Allocation scheme for buffer management that shows additional performance improvement.