A Petri net model for evaluating packet buffering strategies in a network processor

Previous studies have shown that buffering packets in DRAM is a performance bottleneck. In order to understand the impediments in accessing the DRAM, we developed a detailed Petri net model of IP forwarding application on IXP2400 that models the different levels of the memory hierarchy. The cell based interface used to receive and transmit packets in a network processor leads to some small size DRAM accesses. Such narrow accesses to the DRAM expose the bank access latency, reducing the bandwidth that can be realized. With real traces up to 30% of the accesses are smaller than the cell size, resulting in 7.7% reduction in DRAM bandwidth. To overcome this problem, we propose buffering these small chunks of data in the on chip scratchpad memory. This scheme also exploits greater degree of parallelism between different levels of the memory hierarchy. Using real traces from the internet, we show that the transmit rate can be improved by an average of 21% over the base scheme without the use of additional hardware. Further, the impact of different traffic patterns on the network processor resources is studied. Under real traffic conditions, we show that the data bus which connects the off-chip packet buffer to the micro-engines, is the obstacle in achieving higher throughput.

Generating Efficient Data Movement Code for Heterogeneous Architectures with Distributed-Memory

Programming for parallel architectures that do not have a shared address space is extremely difficult due to the need for explicit communication between memories of different compute devices. A heterogeneous system with CPUs and multiple GPUs, or a distributed-memory cluster are examples of such systems. Past works that try to automate data movement for distributed-memory architectures can lead to excessive redundant communication. In this paper, we propose an automatic data movement scheme that minimizes the volume of communication between compute devices in heterogeneous and distributed-memory systems. We show that by partitioning data dependences in a particular non-trivial way, one can generate data movement code that results in the minimum volume for a vast majority of cases. The techniques are applicable to any sequence of affine loop nests and works on top of any choice of loop transformations, parallelization, and computation placement. The data movement code generated minimizes the volume of communication for a particular configuration of these. We use a combination of powerful static analyses relying on the polyhedral compiler framework and lightweight runtime routines they generate, to build a source-to-source transformation tool that automatically generates communication code. We demonstrate that the tool is scalable and leads to substantial gains in efficiency. On a heterogeneous system, the communication volume is reduced by a factor of 11X to 83X over state-of-the-art, translating into a mean execution time speedup of 1.53X. On a distributed-memory cluster, our scheme reduces the communication volume by a factor of 1.4X to 63.5X over state-of-the-art, resulting in a mean speedup of 1.55X. In addition, our scheme yields a mean speedup of 2.19X over hand-optimized UPC codes.

Parallel Flow-Sensitive Pointer Analysis by Graph-Rewriting

Precise pointer analysis is a problem of interest to both the compiler and the program verification community. Flow-sensitivity is an important dimension of pointer analysis that affects the precision of the final result computed. Scaling flow-sensitive pointer analysis to millions of lines of code is a major challenge. Recently, staged flow-sensitive pointer analysis has been proposed, which exploits a sparse representation of program code created by staged analysis. In this paper we formulate the staged flow-sensitive pointer analysis as a graph-rewriting problem. Graph-rewriting has already been used for flow-insensitive analysis. However, formulating flow-sensitive pointer analysis as a graph-rewriting problem adds additional challenges due to the nature of flow-sensitivity. We implement our parallel algorithm using Intel Threading Building Blocks and demonstrate considerable scaling (upto 2.6x) for 8 threads on a set of 10 benchmarks. Compared to the sequential implementation of staged flow-sensitive analysis, a single threaded execution of our implementation performs better in 8 of the benchmarks.

P-T evolution of Glenelg eclogites, NW Scotland: Did they experience ultrahigh-pressure metamorphism?

Eclogites and their retrogressed equivalents from the eastern unit of the Glenelg-Attadale Inlier in NW Scotland preserve much microstructural evidence that indicates that very high-pressure/temperature eclogite facies conditions were reached, and followed by decompression and hydration during exhumation. Rutile exsolution in garnet and quartz exsolution in omphacite and titanite formed through mineral reactions during high P-T peak metamorphism. Isochemical phase diagrams modeled for samples from three different locations indicate that the outer part of the eastern unit preserves a peak metamorphic condition of c. 850-1000 degrees C at 18-25 kbar, whereas the central part has a similar pressure (c. 23 kbar), but a lower temperature (c. 670 degrees C). Due to the limitations in the phase diagram calculations the estimated P-T conditions represent the minimum conditions attained by the peak metamorphic assemblage, and the pre-exsoived peak assemblage probably stabilized at a higher pressure. This observation is strongly supported by the presence of exsolution microstructures. The present results demonstrate that the eastern unit experienced very high P-T conditions during peak metamorphism and a tight clockwise P-T trajectory and provide the first indication of possible ultrahigh-pressure metamorphism in the Glenelg eclogites. (C) 2009 Elsevier B.V. All rights reserved.

High-temperature, high-pressure granulites (retrogressed eclogites) in the central region of the Lewisian, NW Scotland: Crustal-scale subduction in the Neoarchaean

Eclogites and associated high-pressure (HP) rocks in collisional and accretionary orogenic belts preserve a record of subduction and exhumation, and provide a key constraint on the tectonic evolution of the continents. Most eclogites that formed at high pressures but low temperatures at > 10-11 kbar and 450-650 degrees C can be interpreted as a result of subduction of cold oceanic lithosphere. A new class of high-temperature (HT) eclogites that formed above 900 degrees C and at 14 to 30 kbar occurs in the deep continental crust, but their geodynamic significance and processes of formation are poorly understood. Here we show that Neoarchaean mafic-ultramafic complexes in the central granulite facies region of the Lewisian in NW Scotland contain HP/HT garnet-bearing granulites (retrogressed eclogites), gabbros, Iherzolites, and websterites, and that the HP granulites have garnets that contain inclusions of omphacite. From thermodynamic modeling and compositional isopleths we calculate that peak eclogite-facies metamorphism took place at 24-22 kbar and 1060-1040 degrees C. The geochemical signature of one (G-21) of the samples shows a strong depletion of Eu indicating magma fractionation at a crustal level. The Sm-Nd isochron ages of HP phases record different cooling ages of ca. 2480 and 2330 Ma. We suggest that the layered mafic-ultramafic complexes, which may have formed in an oceanic environment, were subducted to eclogite depths, and exhumed as HP garnet-bearing orogenic peridotites. The layered complexes were engulfed by widespread orthogneisses of tonalite-trondhjemite-granodiorite (TTG) composition with granulite facies assemblages. We propose two possible tectonic models: (1) the fact that the relicts of eclogitic complexes are so widespread in the Scourian can be taken as evidence that a >90 km x 40 km-size slab of continental crust containing mafic-ultramafic complexes was subducted to at least 70 km depth in the late Archaean. During exhumation the gneiss protoliths were retrogressed to granulite facies assemblages, but the mafic-ultramafic rocks resisted retrogression. (2) The layered complexes of mafic and ultramafic rocks were subducted to eclogite-facies depths and during exhumation under crustal conditions they were intruded by the orthogneiss protoliths (TTG) that were metamorphosed in the granulite facies. Apart from poorly defined UHP metamorphic rocks in Norway, the retrogressed eclogites in the central granulite/retrogressed eclogite facies Lewisian region, NW Scotland have the highest crustal pressures so far reported for Archaean rocks, and demonstrate that lithospheric subduction was transporting crustal rocks to HP depths in the Neoarchaean. (C) 2012 International Association for Gondwana Research. Published by Elsevier B.V. All rights reserved.