Search

Although code generation for Convolution Neural Network (CNN) models has been extensively studied, performing efficient data slicing and parallelization for highly-constrained Multicore Neural Processor Units (NPUs) is still a challenging problem. Given the size of convolutions' input/output tensors and the small footprint of NPU on-chip memories, minimizing memory transactions while maximizing parallelism and MAC utilization are central to any effective solution. This paper proposes a TensorFlow XLA/LLVM compiler optimization pass for Multicore NPUs, called Tensor Slicing Optimization (TSO), which: (a) maximizes convolution parallelism and memory usage across NPU cores; and (b) reduces data transfers between host and NPU on-chip memories by using DRAM memory burst time estimates to guide tensor slicing. To evaluate the proposed approach, a set of experiments was performed using the NeuroMorphic Processor (NMP), a multicore NPU containing 32 RISC-V cores extended with novel CNN instructions. Experimental results show that TSO is capable of identifying the best tensor slicing that minimizes execution time for a set of CNN models. Speed-ups of up to 21.7% result when comparing the TSO burst-based technique to a no-burst data slicing approach. To validate the generality of the TSO approach, the algorithm was also ported to the Glow Machine Learning framework. The performance of the models were measured on both Glow and TensorFlow XLA/LLVM compilers, revealing similar results. • A burst-based cost model for Tensor Slicing Optimization. • Reducing data transfer between host and NPU on-chip memories. • Maximizing Convolution parallelism and memory reuse. [ABSTRACT FROM AUTHOR]

This paper investigates the exploitation of heterogeneous DVFS (dynamic voltage frequency scaling) control for improving the energy efficiency of data-parallel applications on ccNUMA shared-memory systems. We propose to adjust the clock frequency individually for the appropriately selected groups of cores, taking into account the diversified costs of parallel computation. This paper aims to evaluate the proposed approach using two different data-parallel applications: solving the 3D diffusion problem, and MPDATA fluid dynamics application. As a result, we observe the energy-savings gains of up to 20 percentage points over the traditional homogeneous frequency scaling approach on the server with two 18-core Intel Xeon Gold 6240. Additionally, we confirm the effectiveness of our strategy using two 64-core AMD EPYC 7773X. This paper also introduces two pruning algorithms that help select the optimal heterogeneous DVFS setups taking into account the energy or performance profile of studied applications. Finally, the cost and efficiency of developed algorithms are verified and compared experimentally against the brute-force search. • Heterogeneous DVFS method for energy efficiency of regular data-parallel applications. • Individually adjusting clock frequency for cores based on workload distribution. • Pruning algorithms for selecting optimal heterogeneous DVFS setups. [ABSTRACT FROM AUTHOR]

In this paper, we describe the first parallel Branch-and-Bound (B&B) algorithm with a history-based domination technique. Although history-based domination substantially speeds up a B&B search, it makes parallelization much more challenging. Our algorithm is the first parallel exact algorithm for the Sequential Ordering Problem using a pure B&B approach. To effectively explore the solution space, we have developed three novel parallelization techniques: thread restart, parallel history domination, and history-table memory management. The proposed algorithm was experimentally evaluated using the SOPLIB and TSPLIB benchmarks on multi-core processors. Using 32 threads with a time limit of one hour, the algorithm gives geometric-mean speedups of 72x and 20x on the medium-difficulty SOPLIB and TSPLIB instances, respectively. On the hard instances, it solves 12 instances that the sequential algorithm does not solve, with geometric-mean speedups of 16x on SOPLIB and 32x on TSPLIB. Super-linear speedups up to 366x are seen on 16 instances. • We propose the first parallel B&B algorithm that involves a history-based domination technique. • The proposed algorithm includes three novel parallelization techniques: thread restart, parallel history-based domination, and history-table memory management. • The proposed algorithm is the first parallel B&B algorithm for the Sequential Ordering Problem, which is an NP-hard sequencing problem with precedence constraints. • We present a thorough experimental evaluation of the proposed parallel algorithm on SOPLIB and TSPLIB. The results show that super-linear speedup is not an anomaly; it can be achieved on many instances. We report a speedup ratio as high as 285 on a 32-core processor. [ABSTRACT FROM AUTHOR]

Convolutional Neural Networks (CNNs) play a crucial role in many image recognition and classification tasks, recommender systems, brain-computer interfaces, etc. As a consequence, there is a notable interest in developing high performance realizations of the convolution operators, which concentrate a significant portion of the computational cost of this type of neural networks. In a previous work, we introduced a portable, high performance convolution algorithm, based on the BLIS realization of matrix multiplication, which eliminates most of the runtime and memory overheads that impair the performance of the convolution operators appearing in the forward training pass, when performed via explicit im2col transform. In this paper, we extend our ideas to the full training process of CNNs on multicore processors, proposing new high performance strategies to tackle the convolution operators that are present in the more complex backward pass of the training process, while maintaining the portability of the realizations. In addition, we conduct a full integration of these algorithms into a framework for distributed training of CNNs on clusters of computers, providing a complete experimental evaluation of the actual benefits in terms of both performance and memory consumption. Compared with baseline implementation, the use of the new convolution operators using pre-allocated memory can accelerate the training by a factor of about 6%–25%, provided there is sufficient memory available. In comparison, the operator variants that do not rely on persistent memory can save up to 70% of memory. • We present DECONVGEMM, an operator integrating the col2im transform and the BLIS GEMM. • We present a reindex transform and a transposed CONVGEMM for gradient computation. • We provide implementation descriptions of the novel CONVGEMM/DECONVGEMM operators. • We integrate our operators in PyDTNN: Python Distributed Training of Neural Networks. • We evaluate the performance and memory savings of the CONVGEMM/DECONVGEMM operators. [ABSTRACT FROM AUTHOR]

The performance of collective communication operations determines the overall performance of MPI applications. Different algorithms have been developed and implemented for each MPI collective operation, but none proved superior in all situations. Therefore, MPI implementations have to solve the problem of selecting the optimal algorithm for the collective operation depending on the platform, the number of processes involved, the message size(s), etc. The current solution method is purely empirical. Recently, an alternative solution method using analytical performance models of collective algorithms has been proposed and proved both accurate and efficient for one-process-per-CPU configurations. The method derives the analytical performance models of algorithms from their code implementation rather than from high-level mathematical definitions, and estimates the parameters of the models separately for each algorithm. The method is network and topology oblivious and uses the Hockney model for point-to-point communications. In this paper, we extend that selection method to the case of clusters of multi-core processors, where each core of the platform runs a process of the MPI application. We present the proposed approach using Open MPI broadcast algorithms, and experimentally validate it on three different clusters of multi-core processors, Grisou, Gros and MareNostrum4. • A novel model-based method for runtime selection of optimal collective algorithms. • Application of the proposed method to the Open MPI broadcast algorithms. • Experimental validation of the method on two modern multi-core clusters. [ABSTRACT FROM AUTHOR]

Deep Neural Networks (DNNs) have gained widespread popularity in different domain applications due to their dominant performance. Despite the prevalence of massively parallel multi-core processor architectures, adopting large DNN models in embedded systems remains challenging, as most embedded applications are designed with single-core processors in mind. This limits DNN adoption in embedded systems due to inefficient leveraging of model parallelization and workload partitioning. Prior solutions attempt to address these challenges using data and model parallelism. However, they lack in finding optimal DNN model partitions and distributing them efficiently to achieve improved performance. This paper proposes a DNN model parallelism framework to accelerate model training by finding the optimal number of model partitions and resource provisions. The proposed framework combines data and model parallelism techniques to optimize the parallel processing of DNNs for embedded applications. In addition, it implements the pipeline execution of the partitioned models and integrates a task controller to manage the computing resources. The experimental results for image object detection demonstrate the applicability of our proposed framework in estimating the latest execution time and reducing overall model training time by almost 44.87% compared to the baseline AlexNet convolutional neural network (CNN) model. • Parallel Computing. • Machine Learning. • DNN Model Partitioning. • Embedded Systems. • Embedded Software. [ABSTRACT FROM AUTHOR]

In multi-core processor systems, the Network-on-Chip (NoC) serves as a vital communication infrastructure. To ensure chip reliability during potential failures, this paper proposes a two-level topology reconfiguration algorithm with core-level redundancy technology. Initially, a heuristic topology reconfiguration method utilizing a greedy strategy is proposed to perform local replacement of faulty processing elements (PEs) and generate an initial logical topology with shorter interconnection paths between PEs. Then, an intelligent optimization method based on memetic algorithm is introduced to optimize the generated initial topology for better communication performance. The experimental results demonstrate that compared to the current state-of-the-art algorithm, the proposed algorithm achieves an average improvement of 13.92% and 30.83% on various size topologies in terms of distance factor (DF) and congestion factor (CF), which represent communication delay and traffic balance respectively. The proposed algorithm significantly enhances the communication performance of the target topology, mitigating communication latency and potential congestion problems. • The candidate set aids greedy selection for optimal fault-free PE replacements. • Local greedy strategy reduces communication delay, eases congestion issues. • Memetic algorithm further optimizes the target topology in the reconfiguration. • The proposed algorithms show strong stability, adaptability in large-scale arrays. [ABSTRACT FROM AUTHOR]

• Private/shared data classification is proposed to enhance system optimizations. • The block classification removes miss-classification of page granularity schemes. • Optimizations are proposed to reduce the overheads of block-grain classification. • We simulate 15 parallel benchmarks for a 16-core CMP multiprocessor. • The proposed work improves system performance by 8.0% to a page-grain scheme. Shared memory architectures are pervasive in the multicore technology era. Still, sequential and parallel applications use most of the data as private in a multicore system. Recent proposals using this observation and driven by a classification of private/shared memory data can reduce the coherence directory area or the memory access latency. The effectiveness of these proposals depends on the accuracy of the classification. The existing proposals perform the private/shared classification at page granularity, leading to a miss-classification and reducing the number of detected private memory blocks. We propose a mechanism able to accurately classify memory blocks using the existing translation lookaside buffers (TLB), which increases the effectiveness of proposals relying on a private/shared classification. Our experimental results show that the proposed scheme reduces L1 cache misses by 25% compared to a page-grain classification approach, which translates into an improvement in system performance by 8.0% with respect to a page-grain approach. [ABSTRACT FROM AUTHOR]

This research studies the Multi-core Architecture for the Modified Accelerated Overrelaxation (MAOR) scheme for solving the fractional Poisson equation. The equation is discretized using the fractional explicit group (FEG) finite difference method. This research also presents the parallel implementation of the fractional order iterative methods with the chessboard (CB) ordering strategies. The experimental results of the test problems were compared with other well known relaxation schemes to test their feasibility on parallel environment. The parameters that is measured include number of iteration, error, execution time and computational cost for various number of processors. • Fractional derivatives can describe the memory and hereditary characteristics of various materials. • Fractional explicit group iterative method increases the convergent rate. • Parallel computing divides tasks among processors which decreases execution time. • Relaxation scheme accelerates the rate of convergence of the iterative methods. [ABSTRACT FROM AUTHOR]

The K-means algorithm is one of the most popular algorithms in Data Science, and it is aimed to discover similarities among the elements belonging to large datasets, partitioning them in K distinct groups called clusters. The main weakness of this technique is that, in real problems, it is often impossible to define the value of K as input data. Furthermore, the large amount of data used for useful simulations makes impracticable the execution of the algorithm on traditional architectures. In this paper, we address the previous two issues. On the one hand, we propose a method to dynamically define the value of K by optimizing a suitable quality index with special care to the computational cost. On the other hand, to improve the performance and the effectiveness of the algorithm, we propose a strategy for parallel implementation on modern multicore CPUs. • For several problems the number of clusters in the K-means algorithm is unavailable. • Adaptive strategies enhance the performance of the K-means algorithm. • Parallel implementation is mandatory for large clustering problems. [ABSTRACT FROM AUTHOR]

Understanding memory performance in multi-core platforms is a prerequisite to perform optimizations. To this end, this paper presents analytical models based on Stochastic Reward Nets (SRNs) to model and evaluate the memory performance of Non-Uniform Memory Access (NUMA) multi-core architectures. The approach considers the details of the architecture and first proposes a monolithic SRN model that evaluates the memory performance in terms of the mean memory response time. Since the monolithic model incurs a state space explosion with an increasing number of cores and memory controllers, two approximate models are presented that are able to evaluate large-scale NUMA architectures. The SRNs are validated through measurements on two NUMA multi-core platforms, a 64-core AMD Opteron server and a 72-core Intel system. The results demonstrate the ability of the proposed models to accurately compute the mean memory response time on NUMA architectures. The results also provide valuable information that runtime systems and application designers can use to optimize execution of parallel applications on such architectures. • Understanding memory performance in NUMA architectures using stochastic reward nets. • Approximate SRN models to model large scale NUMA architectures with low complexity. • Cross-validation of the proposed SRN models on a real NUMA multi-core system. • Model-based analysis of large scale NUMA memory performance for various applications. [ABSTRACT FROM AUTHOR]

Parallel computations with irregular memory access patterns are often limited by the memory subsystems of multi-core CPUs, though it can be difficult to pinpoint and quantify performance bottlenecks precisely. We present a method for estimating volumes of data traffic caused by irregular, parallel computations on multi-core CPUs with memory hierarchies containing both private and shared caches. Further, we describe a performance model based on these estimates that applies to bandwidth-limited computations. As a case study, we consider two standard algorithms for sparse matrix–vector multiplication, a widely used, irregular kernel. Using three different multi-core CPU systems and a set of matrices that induce a range of irregular memory access patterns, we demonstrate that our cache simulation combined with the proposed performance model accurately quantifies performance bottlenecks that would not be detected using standard best- or worst-case estimates of the data traffic volume. • Method for estimating irregular data traffic in multi-core memory hierarchies. • Detailed performance modelling for bandwidth-limited computations. • Experiments quantifying bottlenecks of sparse matrix–vector multiplication. [ABSTRACT FROM AUTHOR]

In prior works, stochastic dual coordinate ascent (SDCA) has been parallelized in a multi-core environment where the cores communicate through shared memory, or in a multi-processor distributed memory environment where the processors communicate through message passing. In this paper, we propose a hybrid SDCA framework for multi-core clusters, the most common high performance computing environment that consists of multiple nodes each having multiple cores and its own shared memory. We distribute data across nodes where each node solves a local problem in an asynchronous parallel fashion on its cores, and then the local updates are aggregated via an asynchronous across-node update scheme. The proposed double asynchronous method converges to a global solution for L -Lipschitz continuous loss functions, and at a linear convergence rate if a smooth convex loss function is used. Extensive empirical comparison has shown that our algorithm scales better than the best known shared-memory methods and runs faster than previous distributed-memory methods. Big datasets, such as one of 280 GB from the LIBSVM repository, cannot be accommodated on a single node and hence cannot be solved by a parallel algorithm. For such a dataset, our hybrid algorithm takes less than 30 s to achieve a duality gap of 1 0 − 5 on 16 nodes each using 12 cores, which is significantly faster than the best known distributed algorithms, such as CoCoA+, that take more than 160 s on 16 nodes. • A novel and practical framework for solving optimization problems in machine learning using modern high performance computing platforms. • Double asynchronous updates both at the inter-core level within a node and at the inter-node level enable better utilization of modern multicore clusters. • Global solution has provable theoretical convergence. • Experimental results show more than 10x improvements on big datasets. [ABSTRACT FROM AUTHOR]

An important concept in finite state machine based testing is synchronization which is used to initialize an implementation to a particular state. Usually, synchronizing sequences are used for this purpose and the length of the sequence used is important since it determines the cost of the initialization process. Unfortunately, the shortest synchronization sequence problem is NP-Hard. Instead, heuristics are used to generate short sequences. However, the cubic complexity of even the fastest heuristic algorithms can be a problem in practice. In order to scale the performance of the heuristics for generating short synchronizing sequences, we propose algorithmic improvements together with a parallel implementation of the cheapest heuristics existing in the literature. To identify the bottlenecks of these heuristics, we experimented on random and slowly synchronizing automata. The identified bottlenecks in the algorithms are improved by using algorithmic modifications. We also implement the techniques on multicore CPUs and Graphics Processing Units (GPUs) to take benefit of the modern parallel computation architectures. The sequential implementation of the heuristic algorithms are compared to our parallel implementations by using a test suite consisting of 1200 automata. The speedup values obtained depend on the size and the nature of the automaton. In our experiments, we observe speedup values as high as 340x by using a 16-core CPU parallelization, and 496x by using a GPU. Furthermore, the proposed methods scale well and the speedup values increase as the size of the automata increases. • We propose algorithmic improvements together with an efficient parallelization approach for synchronizing sequence heuristics. • We experimented on random and slowly synchronizing automata. • We implement the proposed techniques on multicore CPUs and Graphics Processing Units (GPUs) to take benefit of the modern parallel architectures. • With the proposed techniques, we observe speedup values as high as 340x by using a 16-core CPU parallelization, and 496x by using a GPU. • The proposed methods scale well and the speedup values increase as the size of the automata increases. [ABSTRACT FROM AUTHOR]

Modern Multi-Processor System-On-Chips (MPSOC) are widely used especially in real-time embedded systems due to their high throughput and low per unit cost. However, bounded latency is vital to guarantee fast response as well as fairness for applications running on multicore processors. In this paper, a new Priority-base Memory Controller for Embedded Systems (P M S M C) that prioritizes concurrently running applications by assigning uneven quota for each requestor is proposed. Each requestor quota is accompanied by a timer to control the dispatch rate to prevent starvation. Moreover, P M S M C can monitor the real-time application memory activity to assist the request scheduling to achieve efficient utilization of the shared DRAM resource while keeping the timing bounded. Hence, P M S M C can serve both multimedia real-time applications and hard real-time applications concurrently. For 8-core processors, P M S M C is able to achieve an overall performance speedup of 24% and 16% compared to the recently proposed WCAD and TRB-SP memory controllers, respectively. For the Energy-Delay Product (EDP) metric which combines both performance and energy consumption, P M S M C achieves lower EDPs of 25% and 60% compared to the recently proposed WCAD and TRB-SP memory controllers, respectively. • Priority-based Multi-requestor Scheduling Memory Controller PMSMC is developed that support both HRT & NHRT. • PMSMC is a multi-requestor scheduler that utilizes memory bandwidth efficiently. • PMSMC handles both Mem. intensive and Mem. Non-intensive applications effectively. • PMSMC achieves an overall performance speedup of 45% for 4-core systems. • PMSMC achieves Energy-Delay Product (EDP) reduction of 25% for 8-core systems. [ABSTRACT FROM AUTHOR]

Spectral clustering is widely used in data mining, machine learning and other fields. It can identify the arbitrary shape of a sample space and converge to the global optimal solution. Compared with the traditional k -means algorithm, the spectral clustering algorithm has stronger adaptability to data and better clustering results. However, the computation of the algorithm is quite expensive. In this paper, an efficient parallel spectral clustering algorithm on multi-core processors in the Julia language is proposed, and we refer to it as juPSC. The Julia language is a high-performance, open-source programming language. The juPSC is composed of three procedures: (1) calculating the affinity matrix, (2) calculating the eigenvectors, and (3) conducting k -means clustering. Procedures (1) and (3) are computed by the efficient parallel algorithm, and the COO format is used to compress the affinity matrix. Two groups of experiments are conducted to verify the accuracy and efficiency of the juPSC. Experimental results indicate that (1) the juPSC achieves speedups of approximately 14 × ∼ 18 × on a 24-core CPU and that (2) the serial version of the juPSC is faster than the Python version of scikit-learn. Moreover, the structure and functions of the juPSC are designed considering modularity, which is convenient for combination and further optimization with other parallel computing platforms. • A Julia-based parallel algorithm of the spectral clustering is designed. • The parallel algorithm implements spectral clustering in the form of compression. • The parallel algorithm is designed considering modularity. • The parallel algorithm achieves speedups of approximately 18 × on a 24-core CPU. [ABSTRACT FROM AUTHOR]

Three parallel sorting applications and two list output protocols for the first phase of an external sort execute on a fine-grained many-core processor array that contains no algorithm-specific hardware acting as a co-processor with a variety of array sizes. Results are generated using a cycle-accurate model based on measured data from a fabricated many-core chip, and simulated for different processor array sizes. The data shows most energy efficient first-phase many-core sort requires over 65 × lower energy than GNU C++ standard library sort performed on an Intel laptop-class processor and over 105 × lower energy than a radix sort running on an Nvidia GPU. In addition, the highest first-phase throughput many-core sort is over 9.8 × faster than the std::sort and over 14 × faster than the radix sort. Both phases of a 10 GB external sort require 6.2 × lower energy × time energy delay product than the std::sort and over 13 × lower energy × time than the radix sort. • Many-core processors can serve as a high-performance energy-efficient co-processor. • A massive array of simple processors can efficiently perform large modular sorts. • These sorts easily scale with different sized general purpose processing arrays. • A first-phase many-core sort requires 105x less energy than a radix sort on a GPU. • A 10 GB many-core external sort requires 6.2x lower EDP than std::sort on a laptop. [ABSTRACT FROM AUTHOR]

The aim of this paper is to present new high-performance implementations of Marsa-LFIB4 which is an example of high-quality multiple recursive pseudorandom number generators. We propose an algorithmic approach that combines language-based vectorization techniques together with a new divide-and-conquer parallel method that exploits a special sparse structure of the matrix obtained from the recursive formula that defines the generator. Our portable OpenACC implementation achieves the performance comparable to those achieved by our CUDA-based and OpenMP-based implementations on GPUs and multicore CPUs, respectively. • New algorithmic approach for vectorization and parallelization of recursive PRNGs. • Methodology and guidelines for optimizing recursive computations on GPUs. • Case study how to use shared memory to reduce references to global memory. • Comparison of language-based optimization techniques available in CUDA and OpenACC. • Our CUDA and OpenACC implementations achieve excellent performance on modern GPUs. [ABSTRACT FROM AUTHOR]

In this paper, we consider two O (n 4) RNA folding algorithms, Zuker's recurrence and the maximum expected accuracy prediction (MEA), which are challenging dynamic programming tasks to optimize because they are computationally intensive and have a large number of non-uniform dependences. We apply our previously published approach to automatically tile and parallelize each loop in the studied algorithms by means of the polyhedral model. First, for each loop nest statement, rectangular tiles are formed within the iteration space of the loop nest. Then, those tiles are corrected to honor all dependences exposed for the original loop nest. Correction is based on applying the exact transitive closure of a dependence graph. We implemented our approach as a part of the source-to-source TRACO compiler, generated target code, and compare the performance and energy consumption of generated code with those of code obtained with the state-of-the-art PluTo compiler based on the affine transformation framework as well as with those of code generated by means of the manual cache-efficient Transpose method. Experiments were carried out on a modern multi-core processor to achieve the significant locality improvement and energy saving for generated code. • Dynamic programming code can be represented with the polyhedral model. • Tile correction increases parallelism, code locality and performance. • Tiling all loops for NPDP problem code is possible. • Energy efficiency is achieved due to applying tile correction for NPDP codes. [ABSTRACT FROM AUTHOR]

A wealth of important scientific and engineering applications are configured for use on high performance computing architectures using functionality found in the MPI specification. This specification provides application developers with a straightforward means for implementing their ideas for execution on distributed-memory parallel processing computers. OpenMP directives provide a means for operating on shared-memory regions of those computers. With the advent of machines composed of many-core processors, the strict synchronisation required by the bulk synchronous parallel (BSP) communication model can hinder performance increases. This is due to the complexity to handle load imbalances, to reduce serialisation imposed by blocking communication patterns, to overlap communication with computation and, finally, to deal with increasing memory overheads. The MPI specification provides advanced features such as non-blocking calls or shared memory to mitigate some of these factors. However, applying these features efficiently usually requires significant changes on the application structure. Task parallel programming models are being developed as a means of mitigating the abovementioned issues but without requiring extensive changes on the application code. In this work, we present a methodology to develop hybrid applications based on tasks called hierarchical domain over-decomposition with tasking (HDOT). This methodology overcomes most of the issues found on MPI-only and traditional hybrid MPI+OpenMP applications. However, by emphasising the reuse of data partition schemes from process-level and applying them to task-level, it enables a natural coexistence between MPI and shared-memory programming models. The proposed methodology shows promising results in terms of programmability and performance measured on a set of applications. • We present HDOT, a top-down approach for productive, hybrid programming. • We identify common patterns for data partitioning, distribution and reduction. • We examine its applicability on three applications. [ABSTRACT FROM AUTHOR]

This paper presents a multi-stage multi-objective evolutionary approach (MS-MOEA) for allocating parallel computations on multi-core processors by joint optimizing performance (P), energy (E), and temperature (T). Evolutionary techniques have been shown to be effective for solving optimization problems, including our own previous work on solving the PET -optimized scheduling (PETOS) problem. There have long been a great many debates and rivalries between various evolutionary approaches, such as the SPEA or NSGA, with regard to their relative matters. The novelty of the proposed MS-MOEA approach is its amalgamation of the basic evolutionary algorithms that are already shown to be highly effective, thereby creating a niche of these techniques. The niche takes advantages of the strengths of each baseline technique for achieving additional enhancement in the precision of the optimization. We propose six multi-stage hybrids, each designed with either niched fitness assignment strategy, or combining populations from multiple MOEAs , or incorporating the problem knowledge into the conventional technique. The experimental results measure the quality of resulting Pareto fronts and demonstrate that the proposed MS-MOEAs yield better optimization for the PETOS problem in achieving three-objective in parallel task-to-core mapping. [ABSTRACT FROM AUTHOR]

We investigate the problem of non-clairvoyant scheduling of independent parallel tasks on single and multiple multicore processors. For a single multicore processor, we derive an asymptotic worst-case performance bound for a non-clairvoyant offline scheduling algorithm called largest task first (LTF). The result improves our previous result on a single parallel computing system. For multiple multicore processors, we derive an asymptotic worst-case performance bound for the LTF algorithm. To the best of our knowledge, there has been little result on scheduling parallel tasks on multiple parallel computing systems. For multiple multicore processors, we also derive an asymptotic average-case performance bound for a non-clairvoyant online scheduling algorithm called random task first (RTF). The result extends our earlier result on a single parallel computing system. Extensive simulation results are also demonstrated. • Worst-case performance bound for offline scheduling on a single multicore processor. • Worst-case performance bound for offline scheduling on multiple multicore processors. • Average-case performance bound for online scheduling on multiple multicore processors. [ABSTRACT FROM AUTHOR]

Distributed embedded systems are increasingly prevalent in numerous applications, and with pervasive network access within these systems, security is also a critical design concern. We present a modeling and optimization framework for distributed embedded systems incorporating heterogeneous resources, including single core processor, asymmetric multicore processors, and FPGAs. A dataflow-based modeling framework for streaming applications integrates models for computational latency, cryptographic security levels, communication latency, and power consumption. We utilize a multi-objective genetic optimization algorithm to optimize security subject to constraints for energy consumption and minimum security level. The presented methodology is evaluated using a video-based object detection and tracking application considering several distributed heterogeneous embedded systems architectures. • ESL methodology for distributed embedded systems to optimize latency, energy, and security. • Modeling framework integrating computation, communication, cryptographic security levels, and energy. • Employs cryptography for communication between all dataflow tasks, including software and hardware. • Multi-objective optimization method supports security-constrained and security-optimized methods. [ABSTRACT FROM AUTHOR]

Emerging big data applications require a significant amount of server computational power. However, the rapid growth in the data yields challenges to process them efficiently using current high-performance server architectures. Furthermore, physical design constraints, such as power and density, have become the dominant limiting factor for scaling out servers. Heterogeneous architectures that combine big Xeon cores with little Atom cores have emerged as a promising solution to enhance energy-efficiency by allowing each application to run on an architecture that matches resource needs more closely than a one-size-fits-all architecture. Therefore, the question of whether to map the application to big Xeon or little Atom in heterogeneous server architecture becomes important. In this paper, through a comprehensive system level analysis, we first characterize Hadoop-based MapReduce applications on big Xeon and little Atom-based server architectures to understand how the choice of big vs little cores is affected by various parameters at application, system and architecture levels and the interplay among these parameters. Second, we study how the choice between big and little core changes across various phases of MapReduce tasks. Furthermore, we show how the choice of most efficient core for a particular MapReduce phase changes in the presence of accelerators. The characterization analysis helps guiding scheduling decisions in future cloud-computing environment equipped with heterogeneous multicore architectures and accelerators. We have also evaluated the operational and the capital cost to understand how performance, power and area constraints for big data analytics affect the choice of big vs little core server as a more cost and energy efficient architecture. • Xeon has a clear performance advantage for the I/O intensive Hadoop applications. • For map phase, energy efficient core is closely decided by the application type. • For the reduce phase, Atom is the favorite choice across all studied applications. • The reliance on a large number of Atom cores can be reduced significantly by fine-tuning the configuration parameters. • Minimum operational and capital cost can be achieved by scheduling a large number of Atom cores. [ABSTRACT FROM AUTHOR]

Abstract Asymmetric multi-cores (AMCs) are a successful architectural solution for both mobile devices and supercomputers. By maintaining two types of cores (fast and slow) AMCs are able to provide high performance under the facility power budget. This paper performs the first extensive evaluation of how portable are the current HPC applications for such supercomputing systems. Specifically we evaluate several execution models on an ARM big.LITTLE AMC using the PARSEC benchmark suite that includes representative highly parallel applications. We compare schedulers at the user, OS and runtime levels, using both static and dynamic options and multiple configurations, and assess the impact of these options on the well-known problem of balancing the load across AMCs. Our results demonstrate that scheduling is more effective when it takes place in the runtime system level as it improves the baseline by 23%, while the heterogeneous-aware OS scheduling solution improves the baseline by 10%. Highlights • Evaluation of high performance applications on asymmetric multi-core systems. • Comparison of three scheduling approaches taking place on different levels of the software stack. • Analysis of results in terms of: performance, energy consumption and power. • Investigation of different runtime scheduling approaches (e.g. loop vs task-based). [ABSTRACT FROM AUTHOR]

Abstract With the skyrocketing advances of process technology, the increased need to process huge amount of data, and the pivotal need for power efficiency, the usage of Graphics Processing Units (GPUs) for General Purpose Computing becomes a trend and natural. GPUs have high computational power and excellent performance per watt, for data parallel applications, relative to traditional multicore processors. GPUs appear as discrete or embedded with Central Processing Units (CPUs), leading to a scheme of heterogeneous computing. Heterogeneous computing brings as many challenges as it brings opportunities. To get the most of such systems, we need to guarantee high GPU utilization, deal with irregular control flow of some workloads, and struggle with far-friendly-programming models. The aim of this paper is to provide a survey about GPUs from two perspectives: (1) architectural advances to improve performance and programmability and (2) advances to enhance CPU–GPU integration in heterogeneous systems. This will help researchers see the opportunities and challenges of using GPUs for general purpose computing, especially in the era of big data and the continuous need of high-performance computing. Highlights • Recent years have been witnessing the emergence of using GPUs for general purpose computing due to their efficient performance/power ratio. • Various issues need be addressed in order to rely on GPGPUs as a compelling general purpose accelerator for the next power-limited big-data era. • Control Divergence, Memory Bandwidth and Limited Parallelism are the three main bottlenecks that limit GPGPU performance. • Enhancing GPGPU programmability is an important feature for future GPUs to simplify GPGPU programming. • The aim of this paper is to provide a survey of architectural advances to improve performance and programmability of GPUs. [ABSTRACT FROM AUTHOR]

Abstract Hybrid Wireless Network on Chip (WNoC) architecture has been proposed as a promising solution for addressing on-chip communication problems in many multicore systems. The choice of infrastructure topology directly affects the performance gain of the architecture. For exploiting the benefits offered by both mesh and tree topologies, we employ Mesh-of-Tree (MoT) topology as a new communication infrastructure for hybrid WNoC architectures. Moreover, long-distance links are effectively added to the MoT topology to form wireless MoT architecture and an appropriate communication routing scheme is presented to employ this paradigm. The performance and the system cost of the proposed WNoC architecture have been evaluated and compared with other notable WNoC architectures through comprehensive network-level simulations. Experimental results demonstrate the effectiveness of this wireless MoT architecture under both synthetic and realistic traffic patterns in terms of network throughput, latency, and power consumption. The results demonstrate that the proposed architecture can approximately achieve 35% improvement in saturation throughput, 58% reduction in transmission latency, and 43% improvement in power consumption over a wireline MoT-NoC, on average. Highlights • We propose a novel Mesh-of-Tree WNoC architecture for multicore systems. • We introduce an effective wireless MAC and routing mechanisms for the proposed architecture. • We conduct a series of experiments to evaluate the MoT topology for WNoC architectures. • The proposed MoT-WNoC architecture provides an efficient backbone for multicore systems. [ABSTRACT FROM AUTHOR]

Parallel and Distributed Computing (PDC) was traditionally viewed as an advanced subject reserved for elective graduate courses. The last decade has seen two areas with rapid growth, whose synergy is demanding new skills for software engineers in a modern multi-core world. The first has been society’s increasing demand for software engineering solutions, evident in the integral role that software plays in daily life. Unlike traditional PDC applications in the scientific and engineering domains, modern software applications are interacting directly with millions of users on mainstream laptops, smartphones and tablets. The second trend is that of multi-core processors powering such devices, which is further fueling the potential of software applications. This paper proposes a Modern Parallel Programming Framework that recognizes that successful software engineering in this domain involves a combination of hard skills and soft skills. A course dedicated to this goal is presented and evaluated, incorporating a research-infused, problem-based and active learning approach. [ABSTRACT FROM AUTHOR]

Since multicore processors are now the architectural standard and parallel computing is in the core CS curriculum, CS educators must create pedagogical materials and tools to help their students master parallel abstractions and concepts. This paper describes the thread safe graphics library (TSGL), a tool by which an educator can add graphics calls to a working multithreaded program in order to make visible the underlying parallel behavior. Using TSGL, an instructor (or student) can create parallel visualizations that clearly show the parallel patterns or techniques a given program is using, allowing students to see the parallel behavior in near real-time as the program is running. TSGL includes many examples that illustrate its use; this paper presents a representative sample, that can be used either in a lecture or a self-paced lab format. We also present evidence that such visualizations improve student understanding of abstract parallel concepts. [ABSTRACT FROM AUTHOR]

Due to the nature in dealing only with observed executions of a real system, runtime verification is being pursued as a lightweight verification technique. However, the overhead for analyzing the desired temporal properties usually degrades performance greatly. The reasons are: (1) the low efficiency of the interpretive execution in the analyzing process, and (2) nondeterminism of the automata generated from temporal logic properties. To overcome them, this paper presents a parallel approach to verify full regular temporal properties of a program. With this approach, the program is written in Modeling, Simulation and Verification Language (MSVL), and the property is specified by a Propositional Projection Temporal Logic (PPTL) formula. Execution and verification of a program are carried out at the same time. Specifically, each trace generated from executing a program is divided into several segments which are verified in parallel. Also, in the process of verifying each segment, nondeterministic choices in the relative automaton of a temporal property are also handled in parallel. Finally, verification results of all the segments are merged to form the eventual result as well as the counterexample. Our parallel mechanism takes full advantage of the hardware resources and makes temporal property verification efficient in a multi-core system. Experiments show that our approach is practical in verifying temporal properties of large-scale programs in the real world. [ABSTRACT FROM AUTHOR]

Computer architecture courses typically include lab sessions to reinforce, from a practical perspective, concepts and architectural mechanisms studied in lectures. Lab sessions are mainly based on simulation frameworks because they benefit learning. Reading the source code that models certain processor mechanisms allows students to acquire a sound knowledge of how hardware works. Unfortunately, simulators that model current multicore processors are getting more and more complex, which lengthens the learning phase and complicates their use in time-bounded lab sessions. In this paper, we propose a new approach that complements the use of simulation frameworks in lab sessions of computer architecture courses. This approach is based on performing experiments on current commercial processors, where multiple hardware events related to the performance of the computer components under study are monitored. Then, students analyze the measured events and how they impact the overall performance. Such analysis motivates students and, not only helps reinforcing the theoretical concepts, but also increases their analysis skills. In this paper we present the methodology and scheduling framework that support the proposed approach and discuss five lab sessions, which can be applied in different courses, covering multiple computer architecture topics. [ABSTRACT FROM AUTHOR]

The Branch and Bound algorithm (B&B) is a well known method for solving optimally Combinatorial Optimization Problems. This method is based on intelligent enumeration of all feasible solutions which reduce considerably the search space. Nevertheless, it remains inefficient when using the sequential approach to deal with large problem instances due to its huge resolutions time. However, the execution time can be reduced considerably by using parallel computing architectures. With the huge evolution of the multi-cores CPUs and GPUs, it is quite hard to design schemes that efficiently exploit the different hardware architectures simultaneously. As a result, most of the existing works focus on exploiting one hardware architecture at a time. In this paper, we propose five parallel approaches to accelerate the B&B execution time using Multi and Many-core systems. Our goal is to solve optimally the Blocking Job Shop Scheduling problem (BJSS) which is one of the hardest scheduling problem. The first proposed approach is a multi-search parallelization based on master/worker paradigm, exploiting the multi-Core CPU-processors. The second and the third approaches represent a GPU-based parallelization schemes having different level of parallelism and GPU occupancy. The fourth and fifth approaches represent a hybridization between the Multi-core approach and the GPU-based parallelization approaches. The goal of this hybridization is to benefit from the power of both the CPU-cores and the GPU at the same time. This hybridization is based on concurrent kernels execution provided by Nvidia Multi process Service (MPS) that allows multiple host processes (Master and workers) to use simultaneously the GPU to launch their kernels in order to accelerate the bounding of one or several nodes at a time. Experiments using the well known Taillard instances confirm the efficiency of our proposals and show a relative speedup of 160x as compared to an optimized sequential B&B algorithm. [ABSTRACT FROM AUTHOR]

Directory-based coherence protocols (Directory) are considered the design of choice to provide maximum performance in coherence maintenance for shared-memory many-core CMPs, despite their large memory overhead. New solutions are emerging to achieve acceptable levels of on-chip area overhead and energy consumption such as optimized encoding of block sharers in Directory (e.g., SCD) or broadcast-based coherence (e.g., Hammer). In this work, we propose a novel and efficient solution for the cache coherence problem in many-core systems based on the co-design of the coherence protocol and the interconnection network. Particularly, we propose ECONO , a cache coherence protocol tailored to future many-core systems that resorts on PhotoBNoC , a special lightweight dedicated silicon-photonic subnetwork for efficient delivery of the atomic broadcast coherence messages used by the protocol. Considering a simulated 256-core system, as compared with Hammer, we demonstrate that ECONO+PhotoBNoC reduces performance and energy consumption by an average of 34% and 32%, respectively. Additionally, our proposal lowers the area overhead entailed by SCD by 2 × . [ABSTRACT FROM AUTHOR]

Advances in semiconductor technology have made integration of multiple processing cores into one single die a promising trend towards increasing processing performance, lowering power consumption, and increasing reliability for embedded systems. Multicore processors, due to their intrinsic redundancies, are good choices for critical embedded systems for which the reliability is a crucial component. In this paper, an aging-aware adaptive fault tolerance method for DVFS-enabled multicore processors is presented. The analytical results show 3 to 6 order of magnitude increase in reliability of the system without addition of cores or redundant software. By using an aging-aware approach, the proposed method contributes to less than 0.05% negative shift of the maximum frequency of every core in the processor. Experimental results also show that the method has less than 7% energy overhead as compared to the original mode of operation. [ABSTRACT FROM AUTHOR]

The exploitation of optimistic concurrency in modern multicore architectures via Transactional Memory (TM) is becoming a mainstream programming paradigm. TM features can be leveraged to provide support for speculative parallel execution of irregular applications, characterized by a lack of knowledge about data dependences at compile-time. This work is focused on software TM (STM) solutions and how they can be adapted and optimized to deal efficiently with irregular memory access patterns, mainly those caused by reduction operations. With this aim, ReduxSTM is introduced as a specific STM system designed by combining techniques for speculative execution with TM algorithms. ReduxSTM is based on three main design aspects: a transactional commit order mechanism which is available to guarantee sequential semantics when needed; a specific transactional memory primitive defined for expressing commutative and associative operations (reductions) that leverages the underlying TM privatization mechanism to avoid unnecessary transaction aborts caused by reduction memory patterns; and an enhanced conflict resolution mechanism that takes advantage of the two previous features. [ABSTRACT FROM AUTHOR]

Multi-core processors employ shared Last Level Caches (LLC). This trend will continue in the future with large multi-core processors (16 cores and beyond) as well. At the same time, the associativity of LLC tends to remain in the order of sixteen. Consequently, with large multicore processors, the number of applications or threads that share the LLC becomes larger than the associativity of the cache itself. LLC management policies have been extensively studied for small scale multi-cores (4–8 cores) and associativity degree in the 16 range. However, the impact of LLC management on large multi-cores is essentially unknown, in particular when the associativity degree is smaller than the number of applications. In this study, we introduce Adaptive Discrete and deprioritized Application PrioriTization (ADAPT), an LLC management policy addressing the large multi-cores where the LLC associativity degree is smaller than the number of applications. ADAPT builds on the use of the Footprint-number metric. We propose a monitoring mechanism that dynamically samples cache sets to estimate the Footprint-number of applications and classify them into discrete (distinct and more than two) priority buckets. The cache replacement policy leverages this classification and assigns priorities to cache lines of applications during cache replacement operations. We further find that de-prioritizing certain applications during cache replacement is beneficial to the overall performance. We evaluate our proposal on 16, 20 and 24-core multi-programmed workloads and discuss other aspects in detail. [ABSTRACT FROM AUTHOR]

Memory technology is one of the cornerstones of heterogeneous multi-core system efficiency. Many memory techniques are developed to give good performance within the lowest possible energy budget. These technologies open new opportunities for the memory system architecture that serves as the primary means for data storage and data sharing between multiple heterogeneous cores. In this paper, we study existing state of the art memories, discuss a conventional memory system and propose a novel hardware mechanism for heterogeneous multi-core memory system called Pattern Aware Memory System ( PAMS ). The PAMS supports static and dynamic data structures using descriptors and specialized scratchpad memory. In order to prove the proposed memory system, we implemented and tested it on real-prototype and simulator environments. The benchmarking results on real-prototype hardware show that PAMS achieves a maximum speedup of 12.83x and 1.23x for static and dynamic data structures respectively. When compared to the Baseline System , the PAMS consumes up to 4.8 times less program memory for static and dynamic data structures respectively. The PAMS consumes 4.6% and 1.6 times less dynamic power and energy respectively. The results of simulator environment show that the PAMS transfers data-structures up to 5.12x faster than the baseline system. [ABSTRACT FROM AUTHOR]

Convolutional networks (ConvNets) have become a popular approach to computer vision. Here we consider the parallelization of ConvNet training, which is computationally costly. Our novel parallel algorithm is based on decomposition into a set of tasks, most of which are convolutions or FFTs. Theoretical analysis suggests that linear speedup with the number of processors is attainable. To attain such performance on real shared-memory machines, our algorithm computes convolutions converging on the same node of the network with temporal locality to reduce cache misses, and sums the convergent convolution outputs via an almost wait-free concurrent method to reduce time spent in critical sections. Benchmarking with multi-core CPUs shows speedup roughly equal to the number of physical cores. We also demonstrate 90x speedup on a many-core CPU (Xeon Phi Knights Corner). Our algorithm can be either faster or slower than certain GPU implementations depending on specifics of the network architecture, kernel sizes, and density and size of the output patch. [ABSTRACT FROM AUTHOR]

Virtualized multicore systems represent an emerging computing paradigm in the critical systems industry. Virtualization-based solutions leverage the different cores of the processor to run operating systems and applications within separate partitions, to support the development of parallel mixed-criticality systems, and to improve fault-tolerance by protecting and isolating the operating environments. The critical systems industry is subjected to international standards, which recommend fault injection as a mean to contribute with evidence to safety cases. This paper proposes a framework to inject hardware faults in virtualized multicore systems. Our proposal capitalizes on the error reporting architecture of modern processors and allows injecting faults both at hypervisor- and guest-OS-level. We implement the framework in the context of the widely used Intel Core i7 processor and Xen hypervisor. We demonstrate the use of the framework by means of about 60,000 injection experiments in a Linux-based virtualized multicore system installation. [ABSTRACT FROM AUTHOR]

As the need for multicore-aware programmers rises in both science and industry, Computer Science departments in universities around the USA are having to rethink their parallel computing curriculum. At Rice University, this rethinking took the shape of COMP 322, an introductory parallel programming course that is required for all Bachelors students. COMP 322 teaches students to reason about the behavior of parallel programs, educating them in both the high level abstractions of task-parallel programming as well as the nitty gritty details of working with threads in Java. In this paper, we detail the structure, principles, and experiences of COMP 322, gained from 6 years of teaching parallel programming to second-year undergraduates. We describe in detail two particularly useful tools that have been integrated into the curriculum: the HJlibparallel programming library and the Habanero Autograder for parallel programs. We present this work with the hope that it will help augment improvements to parallel computing education at other universities. [ABSTRACT FROM AUTHOR]

The fast evolution of multicore processors makes it difficult for professors to offer computer architecture courses with updated contents. To deal with this shortcoming that could discourage students, the most appropriate solution is a research-oriented course based on current microprocessor industry trends. Additionally, we also seek to improve the students’ skills by applying active learning methodologies, where teachers act as guiders and resource providers while students take the responsibility for their learning. In this paper, we present the Advanced Multicore Architecture (AMA) course, which follows a research-oriented approach to introduce students in architectural breakthroughs and uses active learning methodologies to enable students to develop practical research skills such as critical analysis of research papers or communication abilities. To this end five main activities are used: (i) lectures dealing with key theoretical concepts, (ii) paper review & discussion, (iii) research-oriented practical exercises, (iv) lab sessions with a state-of-the-art multicore simulator, and (v) paper presentation. An important part of all these activities is driven by active learning methodologies. Special emphasis is put on the practical side by allocating 40% of the time to labs and exercises. This work also includes an assessment study that analyzes both the course contents and the used methodology (both of them compared to other courses). [ABSTRACT FROM AUTHOR]

Thanks to the ubiquity of multicore processors, today’s CS students must be introduced to parallel computing or they will be ill prepared as modern software developers. Professional developers of parallel software think in terms of parallel design patterns , which are markedly different from traditional (sequential) design patterns. It follows that the more we can teach students to think in terms of parallel patterns, the more their thinking will resemble that of parallel software professionals. In this paper, we present patternlets —minimalist, scalable, syntactically correct programs, each designed to introduce students to a particular parallel design pattern. The collection currently includes 44 patternlets (16 MPI, 17 OpenMP, 9 Pthreads, and 2 heterogeneous), of which we present a representative sample. We also present data that indicate the use of patternlets to introduce parallelism in CS2 produced a modest improvement in student understanding of parallel concepts. [ABSTRACT FROM AUTHOR]

The use of programming patterns is considered to be a conceptual aid for programmers for developing understandable and testable concurrent and parallel code which is not only well built but also safe. By using programming patterns and their implementations as computer programs, difficult new concepts can be smoothly taught in lectures to students who before trying this teaching approach would have been reluctant to enroll on Parallel and Concurrent Programming courses. The approach presented in this paper consists in changing the traditional programming teaching and learning model to one where students are first introduced to syntactical constructs through selected introductory program code-patterns. In the theory lessons that follow, through the use of laptops with multi-core processors and access to the Virtual Campus services of our university, the students are easily able to implement and master the new concepts as they are taught. This teaching experiment was implemented to teach a concurrent and real-time programming course which is part of the computer engineering (CE) degree and taught during the third semester of the CE curriculum. Evaluation of the students’ academic performance when they had been taught with this approach revealed a 20.6% improvement in the students’ end-of-course grades. [ABSTRACT FROM AUTHOR]

The main challenge for embedded real-time systems, especially for mobile devices, is the trade-off between system performance and energy efficiency. Previous works mainly focused on finding an optimal tasks assignment with the minimum energy under the constraints of time or architecture. In this paper, we propose an Accelerated Search (AS) algorithm based on Dynamic Programming (DP) to obtain a combination of various task schemes which can be completed in a given time with the minimum possible energy by introducing the guaranteed probability and data migration energy. We adopt a DAG (Directed Acyclic Graph) to represent the dependent relation between tasks and develop a Minimum-Energy Model to find the optimal tasks assignment. The heterogeneous multi-core architectures can execute tasks under different voltage levels with DVFS (Dynamic Voltage and Frequency Scaling) which leads to different execution times and different consumption energies. We first design a Minimum Energy Under Probability Constraints (MEUPC) algorithm to assign a proper core and proper voltage level to each task to satisfy the probability constraints with the minimum energy and then a Leaf-Partition (LP) algorithm is used to determine the execution sequence on each core according to the position of the task in DAG. Finally, a Trading Energy For Time (TEFT) algorithm is proposed to explore the opportunity the parallelism of the tasks to reduce the execution time. The experimental results demonstrate that our approach outperforms state-of-the-art algorithms in this field (maximum improvement of 30.7%). [ABSTRACT FROM AUTHOR]

The Worst Case Execution Time (WCET) is one of the most important performance metrics in real-time systems. With multi-core architectures becoming a trend in real-time systems, the WCET analysis is of great challenge, since multiple cores accessing shared hardware resources, such as cache and bus, may result in significant interference on them. In this paper, we propose a finer grained approach to analyze the inter-core interference(bank conflict and bus access interference) on multi-core platforms with the interference-aware bus arbiter(IABA) and bank-column cache partitioning, and our approach can reasonably estimate interference delays based on request timing. Moreover, we optimize bank-to-core mapping to reduce the interference delays, and develop an algorithm for finding the best bank-to-core mapping. The experimental results show that our interference analysis approach can improve the tightness of interference delays by 18.36% on average compared to Upper Bound Delay(UBD) approach, and the optimized bank-to-core mapping can achieve the WCET improvement by 8.93% on average. [ABSTRACT FROM AUTHOR]

Single-ISA asymmetric multicore processors (AMPs), which combine high-performance big cores with low-power small cores, were shown to deliver higher performance per watt than symmetric CMPs (Chip Multi-Processors). Previous work has highlighted that this potential of AMP systems can be realizable via OS scheduling. To date, most existing scheduling schemes for AMPs have been designed to optimize the system throughput, but they are inherently unfair. Although fairness-aware schedulers have been also proposed, they fail to effectively deal with user priorities and do not always ensure that equal-priority applications experience a similar slowdown. To overcome these limitations, we propose ACFS, an asymmetry-aware completely fair scheduler that seeks to optimize fairness while ensuring acceptable throughput. Our evaluation on real AMP hardware and using scheduler implementations in the Linux kernel demonstrates that ACFS achieves an average 23% fairness improvement over two state-of-the-art schemes, while providing higher system throughput. [ABSTRACT FROM AUTHOR]

Power consumption in current high-performance chip multiprocessors (CMPs) has become a major design concern that aggravates with the current trend of increasing the core count. A significant fraction of the total power budget is consumed by on-chip caches which are usually deployed with a high associativity degree (even L1 caches are being implemented with eight ways) to enhance the system performance. On a cache access, each way in the corresponding set is accessed in parallel, which is costly in terms of energy. On the other hand, coherence protocols also must implement efficient directory caches that scale in terms of power consumption. Most of the state-of-the-art techniques that reduce the energy consumption of directories are at the cost of performance, which may become unacceptable for high-performance CMPs. In this paper, we propose an energy-efficient architectural design that can be effectively applied to any kind of cache memory. The proposed approach, called the Tag Filter (TF) Architecture, filters the ways accessed in the target cache set, and just a few ways are searched in the tag and data arrays. This allows the approach to reduce the dynamic energy consumption of caches without hurting their access time. For this purpose, the proposed architecture holds the X least significant bits of each tag in a small auxiliary X-bit -wide array. These bits are used to filter the ways where the least significant bits of the tag do not match with the bits in the X-bit array. Experimental results show that, on average, the TF Architecture reduces the dynamic power consumption across the studied applications up to 74.9 % , 85.9 % , and 84.5 % when applied to L1 caches, L2 caches, and directory caches, respectively. [ABSTRACT FROM AUTHOR]

This paper presents elastic transactions , an appealing alternative to traditional transactions, in particular to implement search structures in shared memory multicore architectures. Upon conflict detection, an elastic transaction might drop what it did so far within a separate transaction that immediately commits, and resume its computation within a new transaction which might itself be elastic. We present the elastic transaction model and an implementation of it, then we illustrate its simplicity and performance on various concurrent data structures, namely double-ended queue , hash table , linked list , and skip list . Elastic transactions outperform classical ones on various workloads, with an improvement of 35% on average. They also exhibit competitive performance compared to lock-based techniques and are much simpler to program with than lock-free alternatives. [ABSTRACT FROM AUTHOR]

Compute platforms are increasingly adopting heterogeneous multicore processing. This paper derives an analytical model to study the benefits and preferred configurations of the single instruction set architecture (ISA) heterogeneous multicore system. We analyze the performance, energy consumption, and energy efficiency of the heterogeneous multicore system under realistic workload based on proposed analytical model. We start by deriving a model for a simple machine that has a single big core (that is high performance) and a single small core (that is energy efficient). Then, we extend our model to deal with machines that have multiple big and small cores. The results obtained using our models show that we can achieve higher performance and lower energy consumption with a heterogeneous multicore system than with a similarly provisioned homogeneous multicore system. Additionally we derive models that assume different practical constraints from ideal heterogeneous multicore model to offer further insights into how to configure given processing cores for optimal efficiency in performance and energy consumption. [ABSTRACT FROM AUTHOR]

We investigate time and energy to solution for the CPU- and GPU-based execution of the compute intensive smoother and grid transfer operators in a geometric multigrid linear solver. We use a hybrid parallel implementation for both shared and distributed memory multi-core host systems comprising CUDA-capable devices. Our numerical experiments are designed to assess the effect of combining an MPI-parallel multigrid framework with OpenMP host threads or CUDA accelerators instead of MPI-only CPU computations for various parallel setups. We present runtime and energy measurements from a quad-CPU test system equipped with two GPUs. We find that using an accelerated asynchronous smoother can yield substantial savings of time and energy to solution over using a host-only Jacobi smoother in small and medium sized host systems with one or two multi-core CPUs. The acceleration of the grid transfer operators also yields a benefit, yet smaller than the benefit from the smoother. For large host systems a hybrid MPI-OpenMP parallelization turns out to be most beneficial with respect to energy consumption, although it is not the fastest option. [ABSTRACT FROM AUTHOR]