Search

Summary: Asymmetric multicore processors (AMPs) couple high‐performance big cores and power‐efficient small ones, all exposing a shared instruction set architecture to software, but with different microarchitectural features. The energy efficiency benefits of AMPs, together with the general‐purpose nature of the various cores, have led hardware manufacturers to build commercial AMP‐based products, first for the mobile and embedded domains, and more recently, for the desktop market segment, as with the Intel Alder Lake processor family. This trend indicates that AMPs may become a solid and more energy efficient replacement for symmetric multicores in a wide range of application domains. Previous research has demonstrated that the system software can substantially improve scheduling—critical to get the most out of heterogeneous cores—by leveraging hardware facilities that are directly managed by the OS, such as performance monitoring counters, or the recently introduced Intel Thread Director technology. Unfortunately, the OS‐level support enabling access to these hardware facilities may often take a long time to be adopted in operating systems, or may come in forms that make its utilization challenging from specific levels of the system software stack, especially in production systems. To fill this gap, we propose PMCSched, an open‐source framework enabling rapid development and evaluation of custom scheduling‐related support in the Linux kernel. PMCSched greatly simplifies the design and implementation of a wide range of scheduling policies for multicore systems that operate at different system software layers without requiring to patch the kernel. To demonstrate the potential of our framework, we conduct a set of experimental case studies on asymmetry‐aware scheduling for Intel Alder Lake processors. [ABSTRACT FROM AUTHOR]

Neural networks (NNs) have been widely adopted in various application domains. Deeper NNs greatly enhance the output accuracy, but complex NNs with more parameters incur intensive memory accesses, and the data usually need to be partitioned since it may exceed the on-chip storage. However, there is no research considering the partition and scheduling co-design of the NNs. In this paper, we propose a sparse NN data partition and loop scheduling scheme. We establish the compression efficiency model of the matrix sparse algorithm and design a partition selection method based on sparsity characteristics analyzed by the compression efficiency model. Further, we design a loop scheduling scheme based on the proper partition size. The experiment results show that the average memory access of each layer can be compressed to 68% of the original, and the throughput of the AlexNet, VGG and VGG19 is increased to an average of 1.66 times.

Many shared‐memory parallel irregular applications, such as sparse linear algebra and graph algorithms, depend on efficient loop scheduling (LS) in a fork‐join manner despite that the work per loop iteration can greatly vary depending on the application and the input. Because of the importance of LS, many different methods (e.g., workload‐aware self‐scheduling) and parameters (e.g., chunk size) have been explored to achieve reasonable performance, and many of these methods require expert prior knowledge about the application and input before runtime. This work proposes a new LS method that requires little to no expert knowledge to achieve speedups close to those of tuned LS methods by self‐managing chunk size based on a heuristic of throughput and using work‐stealing to recover from workload imbalances. This method, named iCh, is implemented into libgomp for testing. It is evaluated against OpenMP's guided, dynamic, and taskloop methods and is evaluated against BinLPT and generic work‐stealing on an array of applications that includes: a synthetic benchmark, breadth‐first search, K‐Means, the molecular dynamics code LavaMD, and sparse matrix‐vector multiplication. On a 28 thread Intel system, iCh is the only method to always be one of the top three LS methods. On average across all applications, iCh is within 5.4% of the best method and is even able to outperform other LS methods for breadth‐first search and K‐Means. [ABSTRACT FROM AUTHOR]

Summary: Many scientific applications consist of large and computationally intensive loops. Dynamic loop self‐scheduling (DLS) techniques are used to parallelize and to balance the load of such applications during execution. Load imbalance arises from variations in the loop iteration (or tasks) execution times, caused by problem, algorithmic, or systemic characteristics. Variations in systemic characteristics are referred to as perturbations. Our hypothesis is that no single DLS technique can achieve the absolute best performance under various perturbations on heterogeneous high‐performance computing (HPC) systems. Therefore, the selection of the most efficient DLS technique is critical to achieve the best application performance. The goal of this work is to solve the algorithm selection problem for the scheduling of computationally intensive applications under perturbations. Existing work only considers perturbations caused by variations in the delivered computational speed of the HPC systems. However, perturbations in available network bandwidth or latency are inevitable on production HPC systems. A simulation‐assisted scheduling algorithm selection (SimAS) approach is introduced herein as a novel control‐theoretic‐inspired approach to select DLS techniques dynamically that improve the performance of applications executing on heterogeneous HPC systems under perturbations. The present work examines the performance of seven applications on a heterogeneous HPC system under all the above system perturbations. SimAS is evaluated using native and simulative experiments. The performance results confirm the original hypothesis that motivates this work. The experimental evaluation shows that the SimAS‐based DLS selection identifies the most efficient technique and improves application performance in most cases. [ABSTRACT FROM AUTHOR]

In high-performance computing, the application's workload must be evenly balanced among threads to deliver cutting-edge performance and scalability. In OpenMP, the load balancing problem arises when scheduling loop iterations to threads. In this context, several scheduling strategies have been proposed, but they do not take into account the input workload of the application and thus turn out to be suboptimal. In this work, we introduce a design methodology to propose, study, and assess the performance of workload-aware loop scheduling strategies. In this methodology, a genetic algorithm is employed to explore the state space solution of the problem itself and to guide the design of new loop scheduling strategies, and a simulator is used to evaluate their performance. As a proof of concept, we show how the proposed methodology was used to propose and study a new workload-aware loop scheduling strategy named smart round-robin (SRR). We implemented this strategy into GNU Compiler Collection's OpenMP runtime. We carry out several experiments to validate the simulator and to evaluate the performance of SRR. Our experimental results show that SRR may deliver up to 37.89 % and 14.10 % better performance than OpenMP's dynamic loop scheduling strategy in the simulated environment and in a real-world application kernel, respectively. Copyright © 2016 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

The input workload of an irregular application must be evenly distributed among its threads to enable cutting-edge performance. To address this need in OpenMP, several loop scheduling strategies were proposed. While having this ever-increasing number of strategies at disposal is helpful, it has become a non-trivial task to select the best one for a particular application. Nevertheless, this challenge becomes easier to be tackled when existing scheduling strategies are extensively evaluated. Therefore, in this paper, we present a performance and scalability evaluation of the recently-proposed loop scheduling strategy named Smart Round-Robin (SRR). To deliver a comprehensive analysis, we coupled a synthetic kernel benchmarking technique with several rigorous statistical tools, and considered OpenMP’s Static and Dynamic loop schedulers as our baselines. Our results unveiled that SRR performs better on irregular applications with symmetric workloads and coarse-grained parallelization, achieving up to 1.9x and 1.5x speedup over OpenMP’s Static and Dynamic schedulers, respectively. [ABSTRACT FROM AUTHOR]

Manycore accelerators have the potential to significantly improve performance of scientific applications when offloading computationally intensive program portions to accelerators. Directive-based high-level programming models, such as OpenACC and OpenMP, are used to create applications for accelerators through annotating regions of code meant for offloading. OpenACC is an emerging directive-based programming model for programming accelerators that typically enable inexperienced programmers to achieve portable and productive performance within applications. In this paper, we present our research in developing challenges and solutions when creating an open-source OpenACC compiler in an industrial framework (OpenUH as a branch of Open64). We then discuss in detail techniques we developed for loop scheduling reduction operations on general purpose GPUs. The compiler is evaluated with benchmarks from the NAS Parallel Benchmarks suite and self-written micro-benchmarks for reduction operations. This implementation has been designed to serve as a compiler infrastructure for researchers to explore advanced compiler techniques, extend OpenACC to other programming models, and build performance tools used in conjunction with OpenACC programs. Copyright © 2015 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

While multicore/multiprocessor systems achieve significant speedup for many applications by exploiting loop level parallelism, they also suffer from increased reliability problems as a result of ever scaling device size. This paper addresses the reliability of loop dominated applications, aiming to execute parallel loops efficiently in the presence of various types of hardware faults. In this paper, we present a fault tolerant work-stealing scheme which makes parallel loop execution resilient to hardware faults. A lightweight buffer-commit mechanism is applied in the proposed scheme to ensure the correctness of the re-execution of loop iterations. In addition, we split large failing chunks of loop iterations at runtime to improve load balancing, and a worker thread is discarded when faults occur frequently on it. We evaluated our techniques on a multi-socket multicore system, using a set of loop dominated benchmarks. The proposed scheme achieves the minimum overhead of supporting fault tolerance and optimal load balancing. [ABSTRACT FROM AUTHOR]

Loop scheduling on parallel and distributed systems has been thoroughly investigated in the past. However, none of these studies considered the multi-core architecture feature for emerging grid systems. Although there have been many studies proposed to employ the hybrid MPI and OpenMP programming model to exploit different levels of parallelism for a distributed system with multi-core computers, none of them were aimed at parallel loop self-scheduling. Therefore, this paper investigates how to employ the hybrid MPI and OpenMP model to design a parallel loop self-scheduling scheme adapted to the multi-core architecture for emerging grid systems. Three different featured applications are implemented and evaluated to demonstrate the effectiveness of the proposed scheduling approach. The experimental results show that the proposed approach outperforms the previous work for the three applications and the speedups range from 1.13 to 1.75. [ABSTRACT FROM AUTHOR]

With the advent of multi-core processors, desktop application developers must finally face parallel computing and its challenges. A large portion of the computational load in a program rests within iterative computations. In object-oriented languages these are commonly handled using iterators which are inadequate for parallel programming. This paper presents a powerful Parallel Iterator concept to be used in object-oriented programs for the parallel traversal of a collection of elements. The Parallel Iterator may be used with any collection type (even those inherently sequential) and it supports several scheduling schemes which may even be decided dynamically at run-time. Some additional features are provided to allow early termination of parallel loops, exception handling and a solution for performing reductions. With a slight contract modification, the Parallel Iterator interface imitates that of the Java-style sequential iterator. All these features combine together to promote minimal, if any, code restructuring. Along with the ease of use, the results reveal negligible overhead and the expected inherent speedup. [ABSTRACT FROM AUTHOR]

With the shrinking of technology feature sizes, the share of leakage in total power consumption of digital systems continues to grow. Traditional dynamic voltage scaling (DVS) fails to accurately address the impact of scaling on system power consumption as the leakage power increases exponentially. The combination of DVS and adaptive body biasing (ABB) is an effective technique to jointly optimize dynamic and leakage energy dissipation. In this paper, we propose an optimal soft real-time loop scheduling and voltage assignment algorithm, loop scheduling and voltage assignment to minimize energy, to minimize both dynamic and leakage energy via DVS and ABB. Voltage transition overhead has been considered in our approach. We conduct simulations on a set of digital signal processor benchmarks based on the power model of 70 nm technology. The simulation results show that our approach achieves significant energy saving compared to that of the integer linear programming approach. [ABSTRACT FROM AUTHOR]

Loop tiling is an efficient loop transformation, mainly applied to detect coarse-grained parallelism in loops. It is a difficult task to apply n-dimensional non-rectangular tiles to generate parallel loops. This paper offers an efficient scheme to apply non-rectangular n-dimensional tiles in non-rectangular iteration spaces, to generate parallel loops. In order to exploit wavefront parallelism efficiently, all the tiles with equal sum of coordinates are assumed to reside on the same wavefront. Also, in order to assign parallelepiped tiles on each wavefront to different processors, an improved block scheduling strategy is offered in this paper. [ABSTRACT FROM AUTHOR]

Abstract: Many high-performance DSP processors employ multi-bank on-chip memory to improve performance and energy consumption. This architectural feature supports higher memory bandwidth by allowing multiple data memory accesses to be executed in parallel. However, making effective use of multi-bank memory remains difficult, considering the combined effect of performance and energy requirement. This paper studies the scheduling and assignment problem about how to minimize the total energy consumption while satisfying the timing constraint with heterogeneous multi-bank memory for applications with loop. An algorithm, TASL (Type Assignment and Scheduling for Loops), is proposed. The algorithm uses bank type assignment with the consideration of variable partition to find the best configuration for both memory and ALU. The experimental results show that the average improvement on energy-saving is significant by using TASL. [Copyright &y& Elsevier]

Distributed computing systems are a viable and less expensive alternative to parallel computers. However, a serious difficulty in concurrent programming of a distributed system is how to deal with scheduling and load balancing of such a system which may consist of heterogeneous computers. Some distributed scheduling schemes suitable for parallel loops with independent iterations on heterogeneous computer clusters have been designed in the past. In this work we study self-scheduling schemes for parallel loops with independent iterations which have been applied to multiprocessor systems in the past. We extend one important scheme of this type to a distributed version suitable for heterogeneous distributed systems. We implement our new scheme on a network of computers and make performance comparisons with other existing schemes. Copyright © 2005 John Wiley & Sons, Ltd. [ABSTRACT FROM AUTHOR]

This article discusses the approaches to apply the OpenMP programming model to symmetric multiprocessor (SMP) clusters using software distributed shared memory (SDSM). The major focus of this article is on the challenges that the prior studies faced and on their solution techniques. Exploiting message-passing primitives explicitly for the openMP synchronization and work-sharing directives enables light interprocess synchronizations. The studies on loop scheduling for SMP clusters will promise significant improvement in system performance. Finally, OpenMP is considered as promising programming model [ABSTRACT FROM PUBLISHER]

Feedback Guided Dynamic Loop Scheduling is a recent dynamic method for loop scheduling. The method has been mainly studied for synthetic examples so far and it has always offered the lowest computational times against other dynamic scheduling methods. In this article we show how the method is applied to the shortest path problem and also present some execution times that prove the efficiency. [ABSTRACT FROM AUTHOR]

In this paper, we propose different approaches for the parallel loop scheduling problem on distributed as well as shared memory systems. Specifically, we propose adaptive loop scheduling models in order to achieve load balancing, low runtime scheduling, low synchronization overhead and low communication overhead. Our models are based on an adaptive determination of the chunk size and an exploitation of the processor affinity property, and consider different situations (central or local queues, and dynamic or static loop partition). [ABSTRACT FROM AUTHOR]

Many approaches have been described for the parallel loop scheduling problem for shared-memory systems, but little work has been done on the data-dependent loop scheduling problem (nested loops with loop carried dependencies). In this paper, we propose a general model for the data-dependent loop scheduling problem on distributed as well as shared memory systems. In order to achieve load balancing and low runtime scheduling and communication overhead, our model is based on a loop task graph and the notion of critical path. In addition, we develop a heuristic algorithm based on our model and on genetic algorithms to test the reliability of the model. We test our approach on different scenarios and benchmarks. The results are very encouraging and suggest a future parallel compiler implementation based on our model. [Copyright &y& Elsevier]

Global software pipelining is a complex but efficient compilation technique to exploit instruction-level parallelism for loops with branches. This paper presents a novel global software pipelining technique, called Trace Software Pipelining, targeted to the instruction-level parallel processors such as Very Long Instruction Word (VLIW) and superscalar machines. Trace software pipelining applies a global code scheduling technique to compact the original loop body. The resulting loop is called a trace software pipelined (TSP) code. The trace softwrae pipelined code can be directly executed with special architectural support or can be transformed into a globally software pipelined loop for the current VLIW and superscalar processors. Thus, exploiting parallelism across all iterations of a loop can be completed through compacting the original loop body with any global code scheduling technique. This makes our new technique very promising in practical compilers. Finally, we also present the preliminary experimental results to support our new approach. [ABSTRACT FROM AUTHOR]

This paper uses timed Petri net to model and analyze the problem of instruction-level loop scheduling with resource constraints, which has been proven to be an NP complete problem. First, we present a new timed Petri net model to integrate functional unit allocation, register allocation and spilling into a unified theoretical framework. Then we develop a state subgraph, called Register Allocation Solution Graph, which can effectively describe the major behavior of our new model. The main property of this state subgraph is that the number of all its nodes is polynomial. finally we present and prove that the optimum loop schedules can be found with polynomial computation complexity, for almost all practical loop programs. Our work lightens a new idea of finding the optimum loop schedules. [ABSTRACT FROM AUTHOR]

Load balance is important because it may affect the speedup attained through the concurrent execution of loop iterations on a parallel processor. We study loop load balance in the context of the well-known Perfect benchmarks. Several static and dynamic characteristics of the Perfect benchmark DOALL loops are observed and interpreted. The late arrival of processors is noted as a major source of load imbalance. This observation suggested the idea of processor preallocation. An analytic cost model is presented and the advantages of processor preallocation are demonstrated by experimental evaluation on a CRAY Y-MP8 under the Unicos operating system. [ABSTRACT FROM AUTHOR]

Modulo scheduling theory can be applied successfully to overlap Fortran DO loops on pipelined computers issuing multiple operations per cycle both with and without special loop architectural support. This paper shows that a broader class of loops-REPEAT-UNTIL, WHILE, and loops with more than one exit, in which the trip count is not known beforehand-can also be overlapped efficiently on multiple-issue pipelined machines. The approach is described with respect to a specific machine model, but it can be extended to other models. Special features in the architecture, as well as compiler representations for accelerating these loop constructs, are discussed. Performance results are presented for a few select examples. [ABSTRACT FROM AUTHOR]