Search

The popularization of multimedia services has pushed forward the development of 2D/3D video-capable embedded mobile devices. Such devices require efficient energy/memory-management strategies to deal with severe memory/processing requirements and limited energy supply. Therefore, we propose a motion and disparity estimation (ME and DE) system—the most memory/processing demanding encoding steps—for the 3D High Efficiency Video Coding (3D-HEVC) standard. It was designed for low energy consumption, featuring a run-time adaptive memory hierarchy. The processing unit employs flexible coding order and optimizations to reduce the computational effort by exploring the inter-channel and inter-view redundancies. The memory hierarchy features window-based prefetching, data reuse, subsampling, and dynamic voltage scaling controlled by our depth-based dynamic search window resizing algorithm. Memory results demonstrate an average on-chip energy reduction of 79% in comparison to the widely used Level-C solution for a 45-nm technology. The proposed energy-aware ME and DE system dissipates 7.55 W while processing three HD 1080p views (video + depth) at 30 frames per second and presents a mean energy consumption of 0.107 J per access unit. To the best of our knowledge, this is the first work that proposes a real-time ME/DE system for the 3D-HEVC standard with an adaptive memory hierarchy. [ABSTRACT FROM AUTHOR]

Large-scale graph processing requires the high bandwidth of data access. However, as graph computing continues to scale, it becomes increasingly challenging to achieve a high bandwidth on generic computing architectures. The primary reasons include: the random access pattern causing local bandwidth degradation, the poor locality leading to unpredictable global data access, heavy conflicts on updating the same vertex, and unbalanced workloads across processing units. Processing-in-memory (PIM) has been explored as a promising solution to providing high bandwidth, yet open questions of graph processing on PIM devices remain in: 1) how to design hardware specializations and the interconnection scheme to fully utilize bandwidth of PIM devices and ensure locality and 2) how to allocate data and schedule processing flow to avoid conflicts and balance workloads. In this paper, we propose GraphH, a PIM architecture for graph processing on the hybrid memory cube array, to tackle all four problems mentioned above. From the architecture perspective, we integrate SRAM-based on-chip vertex buffers to eliminate local bandwidth degradation. We also introduce reconfigurable double-mesh connection to provide high global bandwidth. From the algorithm perspective, partitioning and scheduling methods like index mapping interval-block and round interval pair are introduced to GraphH, thus workloads are balanced and conflicts are avoided. Two optimization methods are further introduced to reduce synchronization overhead and reuse on-chip data. The experimental results on graphs with billions of edges demonstrate that GraphH outperforms DDR-based graph processing systems by up to two orders of magnitude and $5.12 {\times }$ speedup against the previous PIM design. [ABSTRACT FROM AUTHOR]

Abstract Over the last 30 years, a number of secure processor architectures have been proposed to protect software integrity and confidentiality during its distribution and execution. In such architectures, encryption (together with integrity checking) is used extensively, on any data leaving a defined secure boundary. In this paper, we show how encryption can be achieved at the instruction level using a stream cipher. Thus encryption is more lightweight and efficient, and is maintained deeper in the memory hierarchy than the natural off-chip boundaries considered in most research works. It requires the control flow graph to be used and modified as part of the off-line encryption process, but thanks to the LLVM framework, it can be integrated easily in a compiler pipeline, and be completely transparent to the programmer. We also describe hardware modifications needed to support this encryption method, the latter were added to a 32-bit MIPS soft core. The synthesis performed on a Altera Cyclone V FPGA shows that encryption requires 26% of extra logic, while slowing-down execution time by an average of 48% in the best setting. [ABSTRACT FROM AUTHOR]

Abstract Previous studies proposed several code signatures, with large vector dimensions and time-consuming profiling processes, to detect phase transitions of the overall processor performance. However, there still lacks an effective and efficient method to detect and leverage the phase characteristics of memory access. In this paper, we propose the reuse distance vector (RDV), a new metric that tightly coupled with the cache performance, to summarize the phase behavior in the memory hierarchy. Different from the commonly seen huge dimensionality of other code signatures, RDVs are measured at very low dimensions. Meanwhile, the profiling overhead can be further reduced by our sampling technique. Based on RDVs, we can pick simulation points from the whole program via a clustering method to act as the representative subset to reduce the time consumption of cycle accurate simulations. Using the simulation points found by RDVs, the average relative error of cache miss rate estimation is as low as 1.08%, which outperforms the accuracies of BBVs and EIPVs by 79% and 22% (all compared methods use the same number of simulation points that takes merely 0.4% of the whole program). Meanwhile, the average errors of MLP and the cache miss service time are only 0.9% and 1.8%, respectively. [ABSTRACT FROM AUTHOR]

The memory performance of data mining applications became crucial due to increasing dataset sizes and multi-level cache hierarchies. Recursive partitioning methods such as decision tree and random forest learning are some of the most important algorithms in this field, and numerous researchers worked on improving the accuracy of model trees as well as enhancing the overall performance of the learning process. Most modern applications that employ decision tree learning favor creating multiple models for higher accuracy by sacrificing performance. In this work, we exploit the flexibility inherent in recursive partitioning based applications regarding performance and accuracy tradeoffs, and propose a framework to improve performance with negligible accuracy losses. This framework employs a data access skipping module (DASM) using which costly cache accesses are skipped according to the aggressiveness of the strategy specified by the user and a heuristic to predict skipped data accesses to keep accuracy losses at minimum. Our experimental evaluation shows that the proposed framework offers significant performance improvements (up to 25%) with relatively much smaller losses in accuracy (up to 8%) over the original case. We demonstrate that our framework is scalable under various accuracy requirements via exploring accuracy changes over time and replacement policies. In addition, we explore NoC/SNUCA systems for similar opportunities of memory performance improvement. [ABSTRACT FROM AUTHOR]

Data compression has been intensively studied to increase the utility of cache, network-on-chip (NoC), and main memory in energy-efficient processors. However, prior solutions to data compression often add remarkable compression and decompression delay to the critical path of memory access, which is thought as the major factor limiting its application to commodity processors. Unlike prior work that deals with memory compression or network compression separately, this paper proposes a unified on-chip distributed data compressor (DISCO), to enable near-zero-latency cache and memory block compression for chip multiprocessors adopting nonuniform cache access. DISCO integrates a multimode cache compressor into the NoC routers and overlaps the de/compression latency with the queuing delay in the network. In addition, cache block evicted to or fetched from the main memory can also be compressed or decompressed during the network queuing time in this unified DISCO compressor. With the support of congestion-awareness, it is shown in the evaluation that DISCO, which unifies the compression solution of the memory hierarchy, dramatically decreases the compression overhead of isolated techniques, and significantly boosts the efficiency of data moving and store. [ABSTRACT FROM AUTHOR]

Compiler based embedded memory is essential for SoC design. A new Contention Free Delayed Keeper (CFDK) topology has been developed in a leading edge 14 nm System-on-Chip (SoC) technology to improve the read performance of register file (RF) memories which can be easily used for both high density (HD) and high performance (HP) RF memory compiler design. This technique never allows contention and this helps to improve V min (minimum operating voltage at which design is functional) significantly compared to a conventional keeper with low area overhead. It does not require fine tuning the keeper delay across the range of the local bit line (LBL) lengths that the compiler supports. It is shown that the proposed technique enhances the circuit evaluation speed by at least 68% while reducing power dissipation by 2.75% as compared to conventional domino logic. It also shows minimum 10% improvement in area with at par or better V min and performance over other delayed keeper techniques. The same technique can be broadly applied to any domino path design including ROM design. [ABSTRACT FROM AUTHOR]

In the paper the author presents a novel kind of the WZ factorization algorithm, namely a block WZ factorization algorithm. The aim of this new algorithm is to utilize the computational power of contemporary computers with hierarchical memory. In the paper, some properties of the matrix Z are given and analyzed. Next, a version of the block WZ factorization is presented. The author shows that such a block WZ factorization exists for strictly diagonally dominant matrices. The computational cost of this block algorithm is presented. The time and the accuracy of proposed block WZ factorization algorithm for random dense square diagonally dominant matrices are reported. The block algorithm turned out to be faster even up to 300 times than the original WZ factorization. [ABSTRACT FROM AUTHOR]

Shared memory architectures have recently experienced a large increase in thread-level parallelism, leading to complex memory hierarchies with multiple cache memory levels and memory controllers. These new designs created a Non-Uniform Memory Access (NUMA) behavior, where the performance and energy consumption of memory accesses depend on the place where the data is located in the memory hierarchy. Accesses to local caches or memory controllers are generally more efficient than accesses to remote ones. A common way to improve the locality and balance of memory accesses is to determine the mapping of threads to cores and data to memory controllers based on the affinity between threads and data. Such mapping techniques can operate at different hardware and software levels, which impacts their complexity, applicability, and the resulting performance and energy consumption gains. In this article, we introduce a taxonomy to classify different mapping mechanisms and provide a comprehensive overview of existing solutions. [ABSTRACT FROM AUTHOR]

An adaptive isogeometric method based on d -variate hierarchical spline constructions can be derived by considering a refine module that preserves a certain class of admissibility between two consecutive steps of the adaptive loop ( Buffa and Giannelli, 2016 ). In this paper we provide a complexity estimate, i.e., an estimate on how the number of mesh elements grows with respect to the number of elements that are marked for refinement by the adaptive strategy. Our estimate is in the line of the similar ones proved in the context of adaptive finite element methods. [ABSTRACT FROM AUTHOR]

As DRAM technology is facing scalability limitations due to its excessive leakage power in nano-scale technologies, various non-volatile memory technologies have been emerged to replace it in memory hierarchy. Among these technologies, Phase Change Memory (PCM) is a promising technology for main memory due to its near-zero leakage power, higher density, non-volatility and soft error immunity. However, its major drawbacks, including high write energy and limited write endurance, have prevented its usage as a drop-in replacement of DRAM technology. In this paper, we propose a technique to swap data between memory lines with goal of reducing bit flips. The proposed swapping technique finds the best place to write a chunk of data among a limited set of lines to minimize number of bit flips. The proposed swapping operation works online i.e, does not require any data profiling. Moreover, it does not require major modifications of existing solutions and works only by the addition of a proposed circuitry. It is remarkable that, this technique is additive to various other architectures aiming at PCM lifetime enhancement. Experimental results carried out on a quad core CMP system show that the proposed technique prolongs PCM main memory lifetime by 48% which is achieved at the price of 1% and 2% overhead in read and write latencies respectively. [ABSTRACT FROM AUTHOR]

On modern multicore machines, the memory management typically combines address interleaving in hardware and random allocation in the operating system (OS) to improve performance of both memory and cache. The conventional solutions, however, are increasingly strained as a wide variety of workloads run on complicated memory hierarchy and cause contention at multiple levels. We describe a new framework (named HVR) in OS memory management to support a flexible policy space for tackling diverse application needs, integrating vertical partitioning across layers, horizontal partitioning and random-interleaved allocation at a single layer. We exhaustively study the performance of these policies for over 2,000 workloads and correlate performance with application characteristics. Based on this correlation we derive several practical rules of memory allocation that we integrate into the unified HVR framework to guide resource partitioning and sharing for dynamic and diverse workloads. We implement our approach in Linux kernel 2.6.32 as a restructured page indexing system plus a series of kernel modules. Experimental results show that our framework consistently outperforms the unmodified Linux kernel, with up to 21 percent performance gains, and outperforms prior solutions at individual levels of the memory hierarchy. [ABSTRACT FROM AUTHOR]

The old virtualization idea and the new multicore technology now make it possible to consolidate multiple workloads on one physical host. This helps reduce the amount of idle resources. In particular, transcendent memory is a recent idea to gather idle memory into a pool that is shared by virtual machines (VMs). It can be viewed as a new level in the memory hierarchy, between main memory and disks. Cleancache is the part of transcendent memory that is used for caching the VMs’ clean pages. This paper shows that a Cache Miss Equation can accurately capture observed cleancache behavior, despite its unusual design. The equation can be used to dynamically size and partition cleancache for the VMs. Experiments with a variety of workloads show that this equation-based allocation can help to drastically reduce disk reads and fairly allocate cleancache space. [ABSTRACT FROM AUTHOR]

On-chip dynamic random access memory (DRAM) cache has been recently employed in the memory hierarchy to mitigate the widening latency gap between high-speed cores and off-chip memory. Two important parameters are the DRAM cache miss rate (D$-MR) and the DRAM cache hit latency (D$-HL), as they strongly influence the performance. These parameters depend upon the DRAM set mapping policy. Recently proposed DRAM set mapping policies are predominantly optimized for either D$-MR or D$-HL. We propose novel DRAM set mapping policies that simultaneously reduce D$-MR (via high associativity) and D$-HL (via improved row buffer hit rates). To further improve the D$-HL, we propose a small and low latency DRAM Tag cache (DTC) structure that can quickly determine whether an access to the DRAM cache will be a hit or a miss. The performance of the proposed DTC depends upon the DTC hit rate. To increase it, we present a novel DTC insertion policy that also increases the DTC hit rate. We investigate the latency and miss rate tradeoffs when designing a DRAM cache hierarchy and analyze the effects of different policies on the overall performance. We evaluate our policies on a wide variety of workloads and compare its performance with three recent proposals for on-chip DRAM caches. For a 16-core system, our set mapping policy along with our DTC and its adaptive DTC insertion policy improve the harmonic mean instruction per cycle throughput by 25.4%, 15.5%, and 7.3% compared to state-of-the-art, while requiring 55% less storage overhead for DRAM cache hit/miss prediction. [ABSTRACT FROM AUTHOR]

We address the nature of information from a systemic structural point of view. Starting from the Natural hierarchy of living systems, we elucidate its decomposition into two partial hierarchies associated with its extant levels and inter-level regions, respectively. External observation of a hierarchical system involves the generation of approximate hyperscalar representations of these two partials, which then reintegrate to give a singular metascalar result. We relate Havel's categories of reality and Peirce's categories of experience to this result, and indicate that the ultimate result of the reintegration of hyperscalar data and context is a sign which is information. [ABSTRACT FROM AUTHOR]

This research aims to design a new phase-change RAM (PRAM)-based main memory structure, supporting the advantages of PRAM while providing performance similar to that of conventional DRAM main memory. To replace conventional DRAMs with non-volatile PRAMs as the main memory components, comparable memory access latency, overall cost, power dissipation, and memory cell endurance should be supported. For these goals, we propose a new main memory system consisting of a DRAM converter and an array of single-level cell (SLC)/multi-level cell (MLC) PRAMs. The DRAM converter consists of an aggressive fetching superblock buffer to assure better use of spatial locality and a selective filtering buffer for better use of temporal locality. The array of the SLC/MLC hybrid PRAM structure includes a combination of SLC and MLC PRAMs to enhance the lifetime of the MLC PRAM main memory and hide asymmetric read/write access latency. The proposed structure is evaluated by a trace-driven simulator using SPEC CPU 2006 and SPLASH-2 traces. Experimental results show that the proposed DRAM converter can reduce the miss rate by ~37% and write count by ~55% in comparison with the uniform buffer case. Also, the SLC/MLC PRAM with DRAM converter shows performance in terms of access latency and power consumption close to that of the conventional memory architecture. Thus, our proposed memory architecture can be used to replace the current DRAM-based main memory system. [ABSTRACT FROM AUTHOR]

Considering application behavior in graph partitioning is an arduous task because of the chicken-and-egg problem: the application behavior depends on how the graph is decomposed while achieving load balance requires the knowledge of how the application utilizes the underlying resources. Advances in multi-core processors further complicate the endeavor by introducing hardware diversity and intra-node contention. As an attempt to quantify performance for partitioning refinement, we propose a model that predicts execution times of iterative mesh-based applications running on heterogeneous multi-core clusters. Apart from considering resource heterogeneity, the model takes into account hierarchical communication characteristics, overlap between computation and communication, as well as performance penalties due to intra-node contention. We present a detailed methodology on how to obtain key parameters from a real system and highlight potential pitfalls of conventional approaches in obtaining the parameters. Experiments were conducted using a synthetic application benchmark solving a partial differential equation. Evaluation shows a good agreement between actual time measurement and the performance model. [ABSTRACT FROM AUTHOR]

The Oracle Sparc M7 processor more than triples the throughput of the Sparc M6 processor, while increasing per-thread performance, power efficiency, and I/O bandwidth. M7 contains 32 8-thread, dual-issue, out-of-order Sparc cores. To minimize L3 cache hit latency, M7 features a partitioned L3 cache, with a novel on-chip network for communication between the cache partitions, coherence control, and memory. Memory bandwidth is more than 3 times that of the Oracle Sparc M6 processor. On-chip accelerators providing query filtering and decompression can provide another order of magnitude performance increase for these tasks. M7 keeps power consumption at a minimum through multiple power-saving techniques. M7 scales to 32-processor shared memory multiprocessing systems (SMPs). Coherent shared memory is also supported between SMPs in a cluster. Such a cluster is robust against both communication and SMP failure. Application data integrity guards against pointer-related software vulnerabilities without slowing the processor. Fine-grained memory migration supports concurrent garbage collection. [ABSTRACT FROM PUBLISHER]

We present a hierarchically blocked one-sided Jacobi algorithm for the singular value decomposition (SVD), targeting both single and multiple graphics processing units (GPUs). The blocking structure reflects the levels of the GPUs' memory hierarchy. The algorithm may outperform MAGMA's dgesvd, while retaining high relative accuracy. To this end, we developed a family of parallel pivot strategies on the GPU's shared address space, but applicable also to inter-GPU communication. Unlike common hybrid approaches, our algorithm in a single-GPU setting needs a CPU for the controlling purposes only, while utilizing the GPU's resources to the fullest extent permitted by the hardware. When required by the problem size, the algorithm, in principle, scales to an arbitrary number of GPU nodes. The scalability is demonstrated by more than twofold speedup for sufficiently large matrices on a Tesla S2050 system with four GPUs versus a single Fermi card. [ABSTRACT FROM AUTHOR]

Menus are a key mechanism for organizing different commands in graphical user interfaces. Nowadays low-cost devices that allow using different interaction techniques in remote interfaces have become widespread. Nevertheless, their corresponding menus are direct adaptations from traditional ones. As a consequence, they are inaccurate and slow, and also produce tiredness. In this paper, we design, implement and evaluate a menu selection technique for remote interfaces, the Body Menu. This technique permits whole-body interaction and is specifically designed to take advantage of the proprioception sense. The Body Menu attaches virtual menu items to different parts of the body and selects them when the users reach these zones with their hands. We use the Microsoft Kinect to implement this system. Additionally, we compared it with the most representative menus, studied the best number of body parts to be used and analyzed how children interact with it. [ABSTRACT FROM AUTHOR]

In this paper, a new methodology for speeding up Matrix-Matrix Multiplication using Single Instruction Multiple Data unit, at one and more cores having a shared cache, is presented. This methodology achieves higher execution speed than ATLAS state of the art library (speedup from 1.08 up to 3.5), by decreasing the number of instructions (load/store and arithmetic) and the data cache accesses and misses in the memory hierarchy. This is achieved by fully exploiting the software characteristics (e.g. data reuse) and hardware parameters (e.g. data caches sizes and associativities) as one problem and not separately, giving high quality solutions and a smaller search space. [ABSTRACT FROM AUTHOR]

In this paper, a new methodology for speeding up edge and line detection algorithms is presented, achieving improved performance over the state of the art software library OpenCV (speedup from 1.35 up to 2.22) and other conventional implementations, in both general and embedded processors, by reducing the number of load/store and arithmetic instructions, the number of data cache accesses and data cache misses in memory hierarchy and the algorithm memory size. This is achieved by fully exploiting the combination of the software and hardware parameters which are considered simultaneously as one problem and not separately. Furthermore, the edge and line detection algorithms have been simplified for a computer vision application in a Virtex-5 Xilinx FPGA using Microblaze soft processor (detection and measurement of flow fronts in a microfluid device); it achieves speedup up to 660 times in comparison with conventional software implementations. [ABSTRACT FROM AUTHOR]

To improve chip multiprocessor (CMP) performance, recent research has focused on scheduling strategies to mitigate main memory bandwidth contention. Nowadays, commercial CMPs implement multilevel cache hierarchies that are shared by several multithreaded cores. In this microprocessor design, contention points may appear along the whole memory hierarchy. Moreover, this problem is expected to aggravate in future technologies, since the number of cores and hardware threads, and consequently the size of the shared caches increase with each microprocessor generation. This paper characterizes the impact on performance of the different contention points that appear along the memory subsystem. The analysis shows that some benchmarks are more sensitive to contention in higher levels of the memory hierarchy (e.g., shared L2) than to main memory contention. In this paper, we propose two generic scheduling strategies for CMPs. The first strategy takes into account the available bandwidth at each level of the cache hierarchy. The strategy selects the processes to be coscheduled and allocates them to cores to minimize contention effects. The second strategy also considers the performance degradation each process suffers due to contention-aware scheduling. Both proposals have been implemented and evaluated in a commercial single-threaded quad-core processor with a relatively small two-level cache hierarchy. The proposals reach, on average, a performance improvement by 5.38 and 6.64 percent when compared with the Linux scheduler, while this improvement is by 3.61 percent for an state-of-the-art memory contention-aware scheduler under the evaluated mixes. [ABSTRACT FROM AUTHOR]

A highly multithreaded FFT-based direct Poisson solver that makes effective use of the capabilities of the current NVIDIA graphics processing units (GPUs) is presented. Our algorithms carefully manage the multiple layers of the memory hierarchy of the GPUs such that almost all the global memory accesses are coalesced into 128-byte device memory transactions, and all computations are carried out directly on the registers. A new strategy to interleave the FFT computation along each dimension with other computations is used to minimize the total number of accesses to the 3D grid. We illustrate the performance of our algorithms on the NVIDIA Tesla and Fermi architectures for a wide range of grid sizes, up to the largest size that can fit on the device memory ($(512\times 512\times 512)$ on the Tesla C1060/C2050 and $(512\times 256\times 256)$ on the GeForce GTX 280/480). We achieve up to 140 GFLOPS and a bandwidth of 70 GB/s on the Tesla C1060, and up to 375 GFLOPS with a bandwidth of 120GB/s on the GTX 480. The performance of our algorithms is superior to what can be achieved using the CUDA FFT library in combination with well-known parallel algorithms for solving tridiagonal linear systems of equations. [ABSTRACT FROM AUTHOR]

Computer benchmarking is a common method for measuring the parameters of a computational model. It helps to measure the parameters of any computer. With the emergence of multicore computers, the evaluation of computers was brought under consideration. Since these types of computers can be viewed and considered as parallel computers, the evaluation methods for parallel computers may be appropriate for multicore computers. However, because multicore architectures seriously focus on cache hierarchy, there is a need for new and different benchmarks to evaluate them correctly. To this end, this paper presents a method for measuring the parameters of one of the most famous multicore computational models, namely Multi-Bulk Synchronous Parallel (Multi-BSP). This method measures the hardware latency parameters of multicore computers, namely communication latency ( g) and synchronization latency ( L) for all levels of the cache memory hierarchy in a bottom-up manner. By determining the parameters, the performance of algorithms on multicore architectures can be evaluated as a sequence. [ABSTRACT FROM AUTHOR]

File layout of array data is a critical factor that effects the behavior of storage caches, and has so far taken not much attention in the context of hierarchical storage systems. The main contribution of this paper is a compiler-driven file layout optimization scheme for hierarchical storage caches. This approach, fully automated within an optimizing compiler, analyzes a multi-threaded application code and determines a file layout for each disk-resident array referenced by the code, such that the performance of the target storage cache hierarchy is maximized. We tested our approach using 16 I/O intensive application programs and compared its performance against two previously proposed approaches under different cache space management schemes. Our experimental results show that the proposed approach improves the execution time of these parallel applications by 23.7% on average. [ABSTRACT FROM AUTHOR]

Throughout development, working memory is subject to capacity limits that severely constrain short-term storage. However, adults can massively expand the total amount of remembered information by grouping items into chunks. Although infants also have been shown to chunk objects in memory, little is known regarding the limits of this ability. In particular, it remains unknown whether infants can create more complex memory hierarchies, binding representations of chunks into still larger chunks in recursive fashion. Here we tested the limits of early chunking, first measuring the number of items infants can bind into a single chunk and the number of chunks infants can maintain concurrently, and then, critically, whether infants can embed chunked representations into larger units. We tested 14-month-old infants' memory for hidden objects using a manual search task in which we manipulated memory load (the number of objects infants saw hidden) and the chunking cues provided. We found that infants are limited in the number of items they can chunk and in the number of chunks they can remember. However, we also found that infants can bind representations of chunks into 'superchunks'. These results suggest that hierarchically organizing information strongly affects working memory, starting in infancy. [ABSTRACT FROM AUTHOR]

Abstract: Lock synchronization is a key programming primitive for shared-memory many-core CMPs. However, as the number of cores increases, conventional software implementations cannot meet the desirable levels of performance and scalability. Meanwhile, most existing hardware-supported lock proposals require modifications at some level of the memory hierarchy, thus degrading QoS of applications through synchronization traffic. In this paper, we propose GLock, a dedicated network infrastructure and a token-based message-passing protocol to provide a non-intrusive, extremely efficient and fair implementation for highly contended locks. Two implementations of GLock are considered. The first leverages current full-custom G-lines technology, whilst the second uses a cost-effective mainstream industrial toolflow with an advanced 45 nm technology. When compared with the most efficient software-based lock, both alternatives provide significant reductions in execution time, network traffic and power consumption, for a representative set of benchmarks, with negligible area overhead. [Copyright &y& Elsevier]

We present GPU implementations of two different nature-inspired optimization methods for well-known optimization problems. Ant Colony Optimization (ACO) is a two-stage population-based method modelled on the foraging behaviour of ants, while P systems provide a high-level computational modelling framework that combines the structure and dynamic aspects of biological systems (in particular, their parallel and non-deterministic nature). Our methods focus on exploiting data parallelism and memory hierarchy to obtain GPU factor gains surpassing 20x for any of the two stages of the ACO algorithm, and 16x for P systems when compared to sequential versions running on a single-threaded high-end CPU. Additionally, we compare performance between GPU generations to validate hardware enhancements introduced by Nvidia's Fermi architecture. [ABSTRACT FROM AUTHOR]

Abstract: A hash function is a mapping from a key universe U to a range of integers, i.e., , where m is the range''s size. A perfect hash function for some set is a hash function that is one-to-one on S, where . A minimal perfect hash function for some set is a perfect hash function with a range of minimum size, i.e., . This paper presents a construction for (minimal) perfect hash functions that combines theoretical analysis, practical performance, expected linear construction time and nearly optimal space consumption for the data structure. For n keys and m=n the space consumption ranges from to bits, and for it ranges from to bits. This is within a small constant factor from the theoretical lower bounds of bits for m=n and bits for . We combine several theoretical results into a practical solution that has turned perfect hashing into a very compact data structure to solve the membership problem when the key set S is static and known in advance. By taking into account the memory hierarchy we can construct (minimal) perfect hash functions for over a billion keys in 46min using a commodity PC. An open source implementation of the algorithms is available at http://cmph.sf.net under the GNU Lesser General Public License (LGPL). [Copyright &y& Elsevier]

Abstract: This paper introduces a novel methodology for enabling fast yet accurate exploration of memory organizations onto FPGA devices. The proposed methodology is software supported by a new open-source tool framework, named NAROUTO. This framework is the only public available solution for performing architecture-level exploration, as well as application mapping onto FPGA devices with different memory organizations, under a variety of design criteria (e.g. delay improvement, power optimization, area savings, etc.). Experimental results with a number of industrial oriented kernels prove the efficiency of the proposed solution, as compared to similar approaches, since it provides better manipulation of memory blocks, leading to architectures with higher performance in terms of area, power and delay. [Copyright &y& Elsevier]

As technology is reaching physical limits, reducing power consumption is a key issue on our path to sustained performance. In this paper, we study fundamental tradeoffs and limits in efficiency (as measured in energy per operation) that can be achieved for an important class of kernels, namely the level-3 Basic Linear Algebra Subprograms (BLAS). It is well-accepted that specialization is the key to efficiency. This paper establishes a baseline by studying GEneral Matrix-matrix Multiplication (GEMM) on a variety of custom and general-purpose CPU and GPU architectures. Our analysis shows that orders of magnitude improvements in efficiency are possible with relatively simple customizations and fine-tuning of memory hierarchy configurations. We argue that these customizations can be generalized to perform other representative linear algebra operations. In addition to exposing the sources of inefficiencies in current CPUs and GPUs, our results show our prototype Linear Algebra Processor (LAP) implementing Double-precision GEMM (DGEMM) can achieve 600 GFLOPS while consuming less than 25 Watts in standard 45 nm technology, which is up to 50\times more energy efficient than cutting-edge CPUs. [ABSTRACT FROM AUTHOR]

In achieving high performance on modern architectures it is critical to make effective use of the memory hierarchy. There are compiler-directed locality enhancement techniques that allow the transformation of program to achieve a higher locality: loop transformations, which are constrained by data dependences and data layout transformations, which have a global impact on the program locality. Due to these drawbacks, there must be a unification of the two techniques to achieve the benefits of both. In this paper, a novel unification of these techniques is presented. Using a model based on parameterized polyhedra and introducing new concepts, we propose a data locality optimization algorithm. In comparison with the other approaches, the technique proposed is capable of solving more conflicts and optimizing more references, a subtle way is proposed to optimize incompatible references to the same array, in the same loop, and also references in a cycle in the interference graph. Using parameterized cost functions, our technique estimates the importance of each sub-graph and optimizes data locality. Our experimental results show a significant improvement over the prior approaches. [ABSTRACT FROM AUTHOR]

A novel parallelization of the Lepp-bisection algorithm for triangulation refinement on multicore systems is presented. Randomization and wise use of the memory hierarchy are shown to highly improve algorithm performance. Given a list of selected triangles to be refined, random selection of candidates together with pre-fetching of Lepp-submeshes lead to a scalable and efficient multi-core parallel implementation. The quality of the refinement is shown to be preserved. [ABSTRACT FROM AUTHOR]

Abstract: The split-and-merge method is an algorithm design paradigm sometimes used in the field of parallel computing. It is applied to multilevel algorithms such as the wavelet transforms and some tridiagonal system solvers. In this paper we present the application of the method in the context of general purpose computation on GPUs. The split-and-merge method allows us to efficiently use the CUDA parallel programming model, where a multithreaded program is partitioned into blocks of threads that execute independently from each other. Thus we can solve the data dependency problem at the block boundaries and efficiently take advantage of the memory hierarchy of the GPU. The results obtained show a significant acceleration compared with the direct implementation of the algorithms on the GPU. [Copyright &y& Elsevier]

Memory hierarchy on multi-core clusters has twofold characteristics: vertical memory hierarchy and horizontal memory hierarchy. This paper proposes new parallel computation model to unitedly abstract memory hierarchy on multi-core clusters in vertical and horizontal levels. Experimental results show that new model can predict communication costs for message passing on multi-core clusters more accurately than previous models, only incorporated vertical memory hierarchy. The new model provides the theoretical underpinning for the optimal design of MPI collective operations. Aimed at horizontal memory hierarchy, our methodology for optimizing collective operations on multi-core clusters focuses on hierarchical virtual topology and cache-aware intra-node communication, incorporated into existing collective algorithms in MPICH2. As a case study, multi-core aware broadcast algorithm has been implemented and evaluated. The results of performance evaluation show that the above methodology for optimizing collective operations on multi-core clusters is efficient. [ABSTRACT FROM AUTHOR]

In this paper, the sparse matrix-vector product (SpMV) is evaluated on the FinisTerrae SMP-NUMA supercomputer. Its architecture particularities make the tuning of SpMV especially relevant due to the significant impact on the performance. First, we have estimated the influence of data and thread allocation. Moreover, because of the indirect and irregular memory access patterns of SpMV, we have also studied the influence of the memory hierarchy in the performance. According to the behavior observed in the study, a set of optimizations specially tuned for FinisTerrae were successfully applied to SpMV. Noticeable improvements are obtained in comparison with the SpMV naïve implementation. [ABSTRACT FROM AUTHOR]

This paper gives tight bounds on the cost of cache-oblivious searching. The paper shows that no cache-oblivious search structure can guarantee a search performance of fewer than lg elog N memory transfers between any two levels of the memory hierarchy. This lower bound holds even if all of the block sizes are limited to be powers of 2. The paper gives modified versions of the van Emde Boas layout, where the expected number of memory transfers between any two levels of the memory hierarchy is arbitrarily close to [lg e+ O(lg lg B/lg B)]log N+ O(1). This factor approaches lg e≈1.443 as B increases. The expectation is taken over the random placement in memory of the first element of the structure. Because searching in the disk-access machine (DAM) model can be performed in log N+ O(1) block transfers, this result establishes a separation between the (2-level) DAM model and cache-oblivious model. The DAM model naturally extends to k levels. The paper also shows that as k grows, the search costs of the optimal k-level DAM search structure and the optimal cache-oblivious search structure rapidly converge. This result demonstrates that for a multilevel memory hierarchy, a simple cache-oblivious structure almost replicates the performance of an optimal parameterized k-level DAM structure. [ABSTRACT FROM AUTHOR]

Abstract: In multitasking real-time systems it is required to compute the WCET of each task and also the effects of interferences between tasks in the worst case. This is very complex with variable latency hardware, such as instruction cache memories, or, to a lesser extent, the line buffers usually found in the fetch path of commercial processors. Some methods disable cache replacement so that it is easier to model the cache behavior. The difficulty in these cache-locking methods lies in obtaining a good selection of the memory lines to be locked into cache. In this paper, we propose an ILP-based method to select the best lines to be loaded and locked into the instruction cache at each context switch (dynamic locking), taking into account both intra-task and inter-task interferences, and we compare it with static locking. Our results show that, without cache, the spatial locality captured by a line buffer doubles the performance of the processor. When adding a lockable instruction cache, dynamic locking systems are schedulable with a cache size between 12.5% and 50% of the cache size required by static locking. Additionally, the computation time of our analysis method is not dependent on the number of possible paths in the task. This allows us to analyze large codes in a relatively short time (100KB with paths in less than 3min). [Copyright &y& Elsevier]

Abstract: With the advent of increasingly complex hardware in real-time embedded systems (processors with performance enhancing features such as pipelines, caches, multiple cores), most embedded processors use a hierarchy of caches. While much research has been devoted to the prediction of Worst-Case Execution Times (WCETs) in the presence of a single level of cache (instruction caches, data caches, impact of cache replacement policies), very little research has focused on WCET estimations in the presence of cache hierarchies. In this paper, we propose a safe static instruction cache analysis method for multi-level caches. Variations of the method are presented to model different cache hierarchy management policies between cache levels: non-inclusive, inclusive and exclusive cache hierarchies. The method supports multiple replacement policies. The proposed method is experimented on medium-size benchmarks and a larger application. We show that the method is tight in the case of non-inclusive caches hierarchies and exclusive caches hierarchies, provided that all cache levels use the Least Recently Used (LRU) replacement policy. We further evaluate the additional pessimism when inclusion is enforced or when a non-LRU replacement policy is used. [Copyright &y& Elsevier]

We consider a number of range reporting problems in two and three dimensions and prove lower bounds on the amount of space used by any cache-oblivious data structure for these problems that achieves the optimal query bound of O(log N+ K/ B) block transfers, where K is the size of the query output. The problems we study are three-sided range reporting, 3-d dominance reporting, and 3-d halfspace range reporting. We prove that, in order to achieve the above query bound or even a bound of f(log N, K/ B), for any monotonically increasing function f(⋅,⋅), the data structure has to use Ω( N(log log N)) space. This lower bound holds also for the expected size of any Las-Vegas-type data structure that achieves an expected query bound of at most f(log N, K/ B) block transfers. The exponent ε depends on the function f(⋅,⋅) and on the range of permissible block sizes. Our result has a number of interesting consequences. The first one is a new type of separation between the I/O model and the cache-oblivious model, as deterministic I/O-efficient data structures with the optimal query bound in the worst case and using linear or O( Nlog N) space are known for the above problems. The second consequence is the non-existence of linear-space cache-oblivious persistent B-trees with optimal 1-d range reporting queries. [ABSTRACT FROM AUTHOR]

Multicore architectures are evolving with the promise of extreme performance for the classes of applications that require high performance and large bandwidth of memory. Irregular reduction is one of important computation patterns for many complex scientific applications, and it typically requires high performance and large bandwidth of memory. In this article, we propose region-based parallelization techniques for irregular reductions on multicore architectures with explicitly managed memory hierarchies. Managing memory hierarchy in software requires a lot of programming efforts and tends to be error-prone. The difficulties are even worse for applications with irregular data access patterns. To relieve the burden of memory management from programmers, we develop abstractions, particularly targeted to irregular reduction, for structuring parallel tasks, mapping the parallel tasks to processing units and scheduling data transfers between the memory hierarchies. Our framework employs iteration reordering based on regions of data along with dynamic scheduling of parallel tasks. We experimentally evaluate the effectiveness of our techniques for irregular reduction kernels on the Cell processor embedded in a Sony PlayStation3. Experimental results show the speedups of 8 to 14 on the six available SPEs. [ABSTRACT FROM AUTHOR]

We describe an efficient implementation of a hierarchy of algorithms for multiplication of dense matrices over the field with two elements (픽2). In particular we present our implementation-- in the M4RI library--of Strassen-Winograd matrix multiplication and the "Method of the Four Russians for Multiplication" (M4RM) and compare it against other available implementations. Good performance is demonstrated on AMD's Opteron processor and particulary good performance on Intel's Core 2 Duo processor. The open-source M4RI library is available as a stand-alone package as well as part of the Sage mathematics system. In machine terms, addition in 픽2 is logical-XOR, and multiplication is logical-AND, thus a machine word of 64 bits allows one to operate on 64 elements of 픽2 in parallel: at most one CPU cycle for 64 parallel additions or multiplications. As such, element-wise operations over 픽2 are relatively cheap. In fact, in this paper, we conclude that the actual bottlenecks are memory reads and writes and issues of data locality. We present our empirical findings in relation to minimizing these and give an analysis thereof. [ABSTRACT FROM AUTHOR]

Today computers have several levels of memory hierarchy. To obtain good performance on these processors it is necessary to design algorithms that minimize I]O traffic to slower memories in the hierarchy. In this article, we study the computation of option pricing using the binomial and trinomial models on processors with a multilevel memory hierarchy. We derive lower bounds on memory traffic between different levels of the hierarchy for these two models. We also develop algorithms for the binomial and trinomial models that have near-optimal memory traffic between levels. We have implemented these algorithms on an UltraSparc IIIi processor with a 4-level of memory hierarchy and demonstrated that our algorithms outperform algorithms without cache blocking by a factor of up to 5 and operate at 70% of peak performance. [ABSTRACT FROM AUTHOR]