Search

Presents a two-level memory hierarchy model which analyzes the running time of an algorithm on a computer. Interaction between the main memory and cache of a computer; Importance of computation models in abstracting the complexity of real machines; Features of a cache.

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]

Deep images store multiple fragments perpixel, each of which includes colour and depth, unlike traditional 2D flat images which store only a single colour value and possibly a depth value. Recently, deep images have found use in an increasing number of applications, including ones using transparency and compositing. A step in compositing deep images requires merging per-pixel fragment lists in depth order; little work has so far been presented on fast approaches.This paper explores GPU based merging of deep images using different memory layouts for fragment lists: linked lists, linearised arrays, and interleaved arrays. We also report performance improvements using techniques which leverage GPU memory hierarchy by processing blocks of fragment data using fast registers, following similar techniques used to improve performance of transparency rendering. We report results for compositing from two deep images or saving the resulting deep image before compositing, as well as for an iterated pairwise merge of multiple deep images. Our results show a 2 to 6 fold improvement by combining efficient memory layout with fast register based merging. [ABSTRACT FROM AUTHOR]

Memory performance is often a major bottleneck for high-performance computing (HPC) applications. Deepening memory hierarchies, complex memory management, and non-uniform access times have made memory performance behavior difficult to characterize, and users require novel, sophisticated tools to analyze and optimize this aspect of their codes. Existing tools target only specific factors of memory performance, such as hardware layout, allocations, or access instructions. However, today's tools do not suffice to characterize the complex relationships between these factors. Further, they require advanced expertise to be used effectively. We present MemAxes, a tool based on a novel approach for analytic-driven visualization of memory performance data. MemAxes uniquely allows users to analyze the different aspects related to memory performance by providing multiple visual contexts for a centralized dataset. We define mappings of sampled memory access data to new and existing visual metaphors, each of which enabling a user to perform different analysis tasks. We present methods to guide user interaction by scoring subsets of the data based on known performance problems. This scoring is used to provide visual cues and automatically extract clusters of interest. We designed MemAxes in collaboration with experts in HPC and demonstrate its effectiveness in case studies. [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 PUBLISHER]

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]

Since 2011 the Java runtime library uses a Quicksort variant with two pivot elements. For reasons that remained unclear for years it is faster than the previous Quicksort implementation by more than 10 %; this is not only surprising because the previous code was highlytuned and is used in many programming libraries, but also since earlier theoretical investigations suggested that using several pivots in Quicksort is not helpful. In my dissertation I proved by a comprehensive mathematical analysis of all sensible Quicksort partitioning variants that (a) indeed there is hardly any advantage to be gained from multiway partitioning in terms of the number of comparisons (and more generally in terms of CPU costs), but (b) multiway partitioning does significantly reduce the amount of data to be moved between CPU and main memory. Moreover, this more efficient use of the memory hierarchy is not achieved by any of the other well-known optimizations of Quicksort, but only through the use of several pivots. [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]

Stencil computations are an important class of problems that can benefit from graphics processing units (GPUs). However, given the hierarchical and on-chip blocked memory organization in GPUs, the memory performance degrades for specific data access patterns in stencils. Hence, we need appropriate data layout to effectively use the different levels of the memory to harvest the full potential of GPUs. In this context, a specialized stencil computation problem, namely, Lattice Boltzmann Method, which has a complex neighborhood relationship along with loop carried dependence, is considered as a strong case study. Four different approaches for the lattice Boltzmann method have been developed in this work by exploiting memory hierarchy with new data layouts and kernel organizations. These methods have been developed with the primary aim of increasing the compute to global memory access ratio and reducing the overall read-write latency, even at the expense of additional computations. NVIDIA GPUs TitanX, GTX 960, GTX 740Ti, and GTX 650Ti have been used to test the proposed techniques. The compute to global memory access ratio shows an improvement of 2 to 10 times over the naive solutions in this work. The performance, in terms of time taken per iteration, is improved by up to 3.7 times. The million lattice units per second for both 2DQ9 and 3DQ19 models improve by more than 2 times. [ABSTRACT FROM AUTHOR]

We study various algorithms to factorize a symmetric indefinite matrix that does not fit in the core memory of a computer. There are two sources of the data movement into the memory: one needed for selecting and applying pivots and the other needed to update each column of the matrix for the factorization. It is a challenge to obtain high performance of such an algorithm when the pivoting is required to ensure the numerical stability of the factorization. For example, when factorizing each column of the matrix, a diagonal entry, which ensures the stability, may need to be selected as a pivot among the remaining diagonals, and moved to the leading diagonal by swapping both the corresponding rows and columns of the matrix. If the pivot is not in the core memory, then it must be loaded into the core memory. For updating the matrix, the data locality may be improved by partitioning the matrix. For example, a right-looking partitioned algorithm first factorizes the leading columns, called panel, and then uses the factorized panel to update the trailing submatrix. This algorithm only accesses the trailing submatrix after each panel factorization (instead of after each column factorization) and performs most of its floating-point operations (flops) using BLAS-3, which can take advantage of the memory hierarchy. However, because the pivots cannot be predetermined, the whole trailing submatrix must be updated before the next panel factorization can start. When the whole submatrix does not fit in the core memory all at once, loading the block columns into the memory can become the performance bottleneck. Similarly, the left-looking variant of the algorithm would require to update each panel with all of the previously factorized columns. This makes it a much greater challenge to implement an efficient out-of-core symmetric indefinite factorization compared with an out-of-core nonsymmetric LU factorization with partial pivoting, which only requires to swap the rows of the matrix and accesses the trailing submatrix after each in-core factorization (instead of after each panel factorization by the symmetric factorization). To reduce the amount of the data transfer, in this paper we uses the recently proposed left-looking communication-avoiding variant of the symmetric factorization algorithm to factorize the columns in the core memory, and then perform the partitioned right-looking out-of-core trailing submatrix updates. This combination may still require to load the pivots into the core memory, but it only updates the trailing submatrix after each in-core factorization, while the previous algorithm updates it after each panel factorization.Although these in-core and out-of-core algorithms can be applied at any level of the memory hierarchy, we apply our designs to the GPU and CPU memory, respectively. We call this specific implementation of the algorithm a non-GPU-resident implementation. Our performance results on the current hybrid CPU/GPU architecture demonstrate that when the matrix is much larger than the GPU memory, the proposed algorithm can obtain significant speedups over the communication-hiding implementations of the previous algorithms. [ABSTRACT FROM AUTHOR]

All pairs similarity search (APSS) is used in many web search and data mining applications. Previous work has used techniques such as comparison filtering, inverted indexing, and parallel accumulation of partial results. However, shuffling intermediate results can incur significant communication overhead as data scales up. This paper studies a scalable two-phase approach called Partition-based Similarity Search (PSS). The first phase is to partition the data and group vectors that are potentially similar. The second phase is to run a set of tasks where each task compares a partition of vectors with other candidate partitions. Due to data sparsity and the presence of memory hierarchy, accessing feature vectors during the partition comparison phase incurs significant overhead. This paper introduces a cache-conscious design for data layout and traversal to reduce access time through size-controlled data splitting and vector coalescing, and it provides an analysis to guide the choice of optimization parameters. The evaluation results show that for the tested datasets, the proposed approach can lead to an early elimination of unnecessary I/O and data communication while sustaining parallel efficiency with one order of magnitude of performance improvement and it can also be integrated with LSH for approximated APSS. [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]

Using agent-based simulation (ABS) to analyze complex adaptive systems gains growing popularity over the past decades. One of the fundamental issues in ABS is to increase the execution speed. In this paper, we identify two common modules that widely exist in ABS applications, namely, the agent management module and the agent interaction module. Improving the efficiency of these two common modules can significantly speed up the ABS execution in general. GPU architecture, programming model, and memory hierarchy are studied. Effective strategies on GPU are proposed when we design the two modules. The first contribution of this work is to propose an AgentPool data structure to handle agent creation and deletion on GPU. The second contribution is an efficient agent interaction module, which is designed by carefully utilizing the GPU memory hierarchy. To demonstrate effectiveness and generality, the proposed strategies are applied to a range of ABS applications, including game-of-life, flocking boids, prey-and-predator, and the social force-based crowd simulation. The simulation results demonstrate that the proposed strategies achieve better performance than the commonly used CPU and GPU ABS framework, namely, Mason and FLAME, for ABS applications using continuous space. Copyright © 2016 John Wiley & Sons, Ltd. [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 PUBLISHER]

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 PUBLISHER]

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-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]

Nowadays, many real-time applications are very complex and as the complexity and the requirements of those systems become more demanding, more hardware processing capacity is necessary. Unfortunately, the correct functioning of real-time systems depends not only on the logically correct response but also on the time when it is produced. General-purpose processor design fails to deliver analyzability due to their nondeterministic behavior caused by the use of cache memories, dynamic branch prediction, speculative execution, and out-of-order pipelines. In this article, we investigate the pipeline performance of Very Long Instruction Word (VLIW) architectures for real-time systems with an in-order pipeline considering Worst- Case Execution Time (WCET) performance. Techniques on obtaining the WCET of VLIW machines are also considered and we make a quantification on how important are hardware techniques such as static branch prediction, predication, and pipeline speed of complex operations such as memory access and multiplication for high-performance real-time systems. The memory hierarchy is out of the scope of this article and we used a classic deterministic structure formed by a direct mapped instruction cache and a data scratchpad memory. A VLIW prototype was implemented in VHDL from scratch considering the HP VLIW ST231 ISA. We also show some compiler insights and we use a representative subset of the Malardalen's WCET benchmarks for validation and performance quantification. [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]

Scaling the memory hierarchy is a major challenge when we scale the number of cores in a multicore processor. Software Managed Multicore (SMM) architectures come up as one of the promising solutions. In an SMM architecture, there are no caches, and each core has only a local scratchpad memory [Banakar et al. 2002]. As the local memory usually is small, large applications cannot be directly executed on it. Code and data of the task mapped to each core need to be managed between global memory and local memory. This article solves the problem of efficiently managing code on an SMM architecture. The primary requirement of generating efficient code assignments is a correct management cost model. In this article, we address this problem by proposing a cost calculation graph. In addition, we develop two heuristics CMSM (Code Mapping for Software Managed multicores) and CMSM-advanced that result in efficient code management execution on the local scratchpad memory. Experimental results collected after executing applications from the MiBench suite [Guthaus et al. 2001] demonstrate that merely by adopting the correct management cost calculation, even using previous code assignment schemes, we can improve performance by an average of 12%. Combining the correct management cost model and a more optimized code mapping algorithm together, our heuristics can reduce runtime in more than 80% of the cases, and by up to 20% on our set of benchmarks, compared to the state-of-the-art code assignment approach [Jung et al. 2010]. When compared with Instruction-level Parallelism (ILP) results, CMSM-advanced performs an average of 5% worse.We also simulate the benchmarks on a cache-based system, and find that the code management overhead on SMM core with our code management is much less than memory latency of a cache-based 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]

Efficient resource utilization requires that emerging datacenter interconnects support both high performance communication and efficient remote resource sharing. These goals require that the network be more tightly coupled with the CPU chips. Designing a new interconnection technology thus requires considering not only the interconnection itself, but also the design of the processors that will rely on it. In this paper, we study memory hierarchy implications for the design of high-speed datacenter interconnects - particularly as they affect remote memory access - and we use PCIe as the vehicle for our investigations. To that end, we build three complementary platforms: a PCIe-interconnected prototype server with which we measure and analyze current bottlenecks; a software simulator that lets us model microarchitectural and cache hierarchy changes; and an FPGA prototype system with a streamlined switchless customized protocol Thunder with which we study hardware optimizations outside the processor. We highlight several architectural modifications to better support remote memory access and communication, and quantify their impact and limitations. [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]

Nowadays, service providers offer a lot of IT services in the public or private cloud. Clients can buy various kinds of services, such as SaaS, PaaS, etc. Recently, Backup as a Service (BaaS), a variety of SaaS, was introduced there. At the moment, there are several different BaaS's available to archive data in the cloud, but they provide only a basic level of service quality. In this paper, we propose a model which ensures QoS for BaaS and some methods for management of storage resources aimed at achieving the required SLA. This model introduces a set of parameters responsible for an SLA level which can be offered at the basic or higher level of quality. The storage systems (typically HSM), which are distributed between several Data Centers, are built based on disk arrays, VTL's, and tape libraries. The RSMM model does not assume bandwidth reservation or control, but rather is focused on management of storage resources. [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]