Barbara Kreaseck, Dean M. Tullsen, Brad Calder · ACM SIGARCH Computer Architecture News · 2000
Tomorrow's microprocessors will be able to handle multiple flows of control. Applications that exhibit task level parallelism (TLP) and can be decomposed into parallel tasks will perform well on these platforms. TLP arises when a task is independent of its neighboring code. Traditional parallel compilers exploit one variety of TLP, loop level parallelism (LLP), where loop iterations are executed in parallel. LLP can overwhelming be found in numeric, typically FORTRAN programs with regular patterns of data accesses. In contrast, irregular applications, typified by general purpose integer applications, exhibit little LLP as they tend to access data in irregular patterns through pointers. Without pointer disambiguation to analyze data access dependences, traditional parallel compilers cannot parallelize these irregular applications and ensure correct execution.We focus on a different variety of TLP, namely Speculative Task Parallelism (STP). STP arises when a task (either a leaf-procedure, a non-leaf procedure or an entire loop) is control- and memory-independent of its preceding code, and thus could be executed in parallel. Two sections of code are memory-independent when neither contains a store to a memory location that the other accesses. To exploit STP, we assume a hypothetical speculative machine that supports speculative futures (a parallel programming construct that executes a task early on a different thread or processor) with mechanisms for resolving incorrect speculation when the task is not, after all, independent. This allows us to speculatively parallelize code when there is a high probability of independence, but no guarantee.Figure 1 illustrates STP, showing a task Y in the dynamic instruction stream of an irregular application that has no memory access conflicts with a group of instructions, X, that precede Y. The shorter of X and Y determines the overlap of memory-independent instructions as seen in Figures 1(b) and 1(c). In the absence of any register dependences, X and Y may be executed in parallel, resulting in shorter execution time. It is hard for traditional parallel compilers of pointer-based languages to expose this parallelism.The goals of this paper are to identify such regions as X and Y within irregular applications and to find the number of instructions that may thus be removed from the critical path. This number represents the maximum STP when the cost of exploiting STP is zero.Because the biggest barrier to detecting independence in irregular codes is memory disambiguation, we identify memory-independent tasks using a profile-based approach and measure the amount of STP by estimating the amount of memory-independent instructions those tasks expose. We vary the level of control dependence and memory dependence to investigate their effect on the amount of memory-independence we find. We profile at different memory granularities and introduce synchronization to expose higher levels of memory-independence. Across this variety of speculation assumptions, 7 to 22% of dynamic instructions are within tasks that are found to be memory-independent. This was on the SPECint95 benchmarks, a set of irregular applications for which traditional methods of parallelization are ineffective.
Cited by 5
Arturo Gonzalez Escribano, Valentin Cardenoso Payo, Arturo Gonz'alez Escribano et al. · 1997
Recently a new parallel programming model has been presented that imposes synchronization restrictions in order to allow for fully automatic, retargetable program optimization. The motivation for the model is the conjecture that in practice the loss of parallelism due to the inherent synchronization restrictions is less than a factor of 2. In this paper we provide compelling evidence in favor of this conjecture, based on the results of a largely empirical investigation into the ratio between the critical paths of unstructured task graphs and their approximations under the restricted synchronization model. 1 Introduction In high-performance computing performance optimization is clearly a major issue. Currently the only programming methods guaranteed to deliver the huge performance potential of high-performance distributed-memory machines (MPPs, NOWs) are methods that rely on the use of either the data-parallel programming model (provided through languages such as HPF [7]), or simply t...
Cited by 0
Aliaga, José Ignacio, Dolz Zaragozá, Manuel Francisco, Martín Huertas, Alberto Francisco et al. · RECERCAT (Consorci de Serveis Universitaris de Catalunya)
Cited by 0Open access
A. Schoneveld, J.F. de Ronde, P.M.A. Sloot · Lecture notes in computer science · 1997
Cited by 2
Thomas R. Gross, David R. O’Hallaron, Jaspal Subhlok · IEEE Parallel & Distributed Technology Systems & Applications · 1994
Exploiting both data and task parallelism in a single framework is the key to achieving good performance for a variety of applications.
Cited by 88
Remko van Wagensveld, Tobias Wägemann, Niklas Hehenkamp et al. · 2018
Many recent Engine Management Systems (EMSs) have multicore processors. This results in new challenges for the developers of those systems, as most of them are not familiar with multicore programming. Additionally, many of the EMSs have real-time requirements, which need to be met.
Cited by 3
Fengling Yu, Dan Yu · 2023
Pedestrian re-identification technology is widely applied in the fields of pedestrian tracking, criminal investigation, and intelligent image classification. However, pedestrian images obtained from surveillance cameras often suffer from low resolution, lighting variations, visual blur, and complex backgrounds, making pedestrian re-identification challenging. To address these issues, this paper proposes a method that incorporates local branches and segmentation branches into the traditional global recognition framework to compensate for the lack of spatial information in global features and reduce the impact of low-quality images on recognition accuracy. Additionally, this paper applies the random erasing algorithm to alleviate the problem of network overfitting to specific prominent features. Experimental results demonstrate that the proposed method achieves high accuracy on multiple datasets, showing a stable improvement of 2-3 percentage points compared to the baseline algorithm. Meanwhile, this study also conducted a series of comparative experiments using a small-sized network based on ResNet18. The network was applied to a vehicle datasets for validation, and the results demonstrated a significant improvement in accuracy.
Cited by 0
Shankar Ramaswamy, Eugenee W. Hodges IV, Prithviraj Banerjee et al. · 1996
In this paper we suggest a new approach aimed at reducing the effort required to program distributed-memory multicomputers. The key idea in our approach is to automatically convert a program written in a library-based programming language (MATLAB) to a parallel program based on the ScaLAPACK parallel library. In the process of performing this conversion, we apply compiler optimizations that simultaneously exploit task and data parallelism. As our results show, our approach is feasible and practical and our optimization provides significant performance benefits.
Cited by 0
Alejandro Rico, Alex Ramirez, Mateo Valero · SHILAP Revista de lepidopterología · 2009
There is a clear industrial trend towards chip multiprocessors (CMP) as the most power efficient way of further increasing performance. Heterogeneous CMP architectures take one more step along this power efficiency trend by using multiple types of processors, tailored to the workloads they will execute. Programming these CMP architectures has been identified as one of the main challenges in the near future, and programming heterogeneous systems is even more challenging. High-level programming models which allow the programmer to identify parallel tasks, and the runtime management of the inter-task dependencies, have been identified as a suitable model for programming such heterogeneous CMP architectures. In this paper we analyze the performance of Cell Superscalar, a task-based programming model for the Cell Broadband Engine Architecture, in terms of its scalability to higher number of on-chip processors. Our results show that the low performance of the PPE component limits the scalability of some applications to less than 16 processors. Since the PPE has been identified as the limiting element, we perform a set of simulation studies evaluating the impact of out-of-order execution, branch prediction and larger caches on the task management overhead. We conclude that out-of-order execution is a very desirable feature, since it increases task management performance by 50%. We also identify memory latency as a fundamental aspect in performance, while the working set is not that large. We expect a significant performance impact if task management would run using a fast private memory to store the task dependency graph instead of relying on the cache hierarchy.
Cited by 1Open access
James Dinan, Sriram Krishnamoorthy, D. Brian Larkins et al. · 2008
We introduce Scioto, shared collections of task objects, a lightweight framework for providing task management on distributed memory machines under one-sided and global-view parallel programming models. Scioto provides locality aware dynamic load balancing and interoperates with MPI, ARMCI, and global arrays. Additionally, Scioto's task model and programming interface are compatible with many other existing parallel models including UPC, SHMEM, and CAF. Through task parallelism, the Scioto framework provides a solution for overcoming irregularity, load imbalance, and heterogeneity as well as dynamic mapping of computation onto emerging architectures. In this paper, we present the design and implementation of the Scioto framework and demonstrate its effectiveness on the unbalanced tree search (UTS) benchmark and two quantum chemistry codes: the closed shell self-consistent field (SCF) method and a sparse tensor contraction kernel extracted from a coupled cluster computation. We explore the efficiency and scalability of Scioto through these sample applications and demonstrate that is offers low overhead, achieves good performance on heterogeneous and multicore clusters, and scales to hundreds of processors.
Cited by 62
Strout, Michelle Mills · Zenodo (CERN European Organization for Nuclear Research) · 2023
The Chapel programming language provides constructs for expressing a wide range of parallelism patterns, while also remaining easy-to-use. This talk will show usage examples from machine learning, data analytics, aeronautical engineering, hydrology, and other application areas. Perspectives of how existing workflows were adjusted to leverage Chapel and the resulting performance and scaling will also be presented.
Cited by 0Open access
Strout, Michelle Mills · Zenodo (CERN European Organization for Nuclear Research) · 2023
The Chapel programming language provides constructs for expressing a wide range of parallelism patterns, while also remaining easy-to-use. This talk will show usage examples from machine learning, data analytics, aeronautical engineering, hydrology, and other application areas. Perspectives of how existing workflows were adjusted to leverage Chapel and the resulting performance and scaling will also be presented.
Cited by 0Open access
Tongxin Bai, Chen Ding, Pengcheng Li · 2015
To migrate complex sequential code to multicore, profiling is often used on sequential executions to find opportunities for parallelization. In non-scientific code, the potential parallelism often resides in while-loops rather than for-loops. The do-all model used in the past by many studies cannot detect this type of parallelism. A new, task-based model has been used by a number of recent studies and shown safe for general loops and functions. This paper presents a feedback-based compiler that measures the amount of safe task parallelism in a program and ranks the potential candidates. It solves two problems unique for task analysis. The first is the relation between loop parallelism and function parallelism. The second is the effect of the calling context. The new tool is built in the GCC compiler and used to analyze the entire suite of SPEC 2006 integer benchmarks.
Cited by 1
Harold Edwards, Greg Mackey, Stephen L. Olivier et al. · OSTI OAI (U.S. Department of Energy Office of Scientific and Technical Information) · 2016
This report describes a new capability for hierarchical task-data parallelism using Sandia's Kokkos and Qthreads, and evaluation of this capability with sparse matrix Cholesky factor- ization and social network triangle enumeration mini-applications. Hierarchical task-data parallelism consists of a collection of tasks with executes-after dependences where each task contains data parallel operations performed on a team of hardware threads. The collection of tasks and dependences form a directed acyclic graph of tasks - a task DAG . Major chal- lenges of this research and development effort include: portability and performance across multicore CPU; manycore Intel Xeon Phi, and NVIDIA GPU architectures; scalability with respect to hardware concurrency and size of the task DAG; and usability of the application programmer interface (API).
Cited by 2Open access
Abouzied Nasar, Benedict D. Rogers, Georgios Fourtakas et al. · RAS Techniques and Instruments · 2026
ABSTRACT This paper highlights first steps towards enabling graphics processing unit (GPU) acceleration of the task-parallel smoothed particle hydrodynamics (SPH) solver SWIFT. Novel combinations of algorithms are presented, enabling SWIFT to function as a truly heterogeneous software leveraging task-parallelism on CPUs for memory-bound computations concurrently with GPUs for compute-bound computations while minimizing the effects of CPU–GPU communication latency. The proposed algorithms are validated in extensive testing. The GPU acceleration methodology is shown to deliver up to $\sim$3.5 and $\sim 7.5$ speedups for the offloaded computations when including and excluding the time required to prepare and post-process data transfers on the CPU side, respectively. The overall performance of the GPU-accelerated hydrodynamic solver for a full simulation on a single Grace Hopper superchip is 1.8 times faster compared to the superchip’s fully parallelized CPU capabilities. This constitutes an improvement from $\sim$8 million particle updates/s for the full CPU-only baseline ($\sim$115 000 updates per CPU core) to $\sim$15 million updates/s for the GPU-accelerated SPH solver. Moreover, it displays near-perfect strong scaling on 4 Grace Hopper nodes. The GPU-acceleration is also demonstrated to give a 29 per cent improvement in energy efficiency in comparison to CPU-only baselines. Finally, inter-influential bottlenecks in the prototype solver presented in this work are identified: a significant amount of time (up to 80 per cent) of a GPU-offloading cycle is spent on preparing and post-processing particle data on the CPU for the transfer to and from the GPU, respectively. Approaches are suggested to minimize their effects and maximize the solver’s performance in our future work.
Cited by 0Open access
Yonghong Yan, Sanjay Chatterjee, Daniel Orozco et al. · 2010
Manycore architectures –hundreds to thousands of cores per processor – are seen by many as a natural evolution of multicore processors. To take advantage of this massive parallelism in reality requires a productive programming interface for parallel programming, and an efficient execution and thread coordination runtime. Dynamic task parallelism, introduced recently in several programming languages, promises to be an effective approach to parallel programming. Unlike data parallel and SPMD programming models, concurrent tasks can be dynamically created and joined at any time along the execution. A critical prerequisite for an efficient task parallel runtime is a scalable synchronization mechanism to support task coordination in different level of granularity. This paper presents a study of task parallel runtime and synchronization issues in many-core architectures, and provides alternative approaches to low-level hardware synchroniza-tion primitives. To address these issues, we have implemented a high-level synchroniza-tion construct called phasers on a Cyclops64 manycore processor. Phasers support both localized and group synchronization of tasks by allowing threads to register and dereg-ister from groups of synchronizing tasks. Phaser interfaces are much more flexible than the architecture-specific hardware primitives available on manycore processors. We have experimented with several implementations of phasers using software support, hardware support or both to explore their portability, usability and performance. Our results show that phasers provide comparable performance to hardware synchronization primitives, and much better performance than other traditional constructs such as OpenMP barrier for a set of commonly used benchmark applications. 1
Cited by 0
Balaji Devatha Venkatesh, Leo Han, Mark C. Jeffrey · 2025
This project is the convergence of two directions, the first being innovations in belief propagation (BP), an inference algorithm for probabilistic graphical models. These are graphs where random variables form nodes, and a probability mass function forms edges. BP computes the marginal distributions of the nodes. Applications include workplace safety, cancer detection, and healthcare patient experience [1]–[3]. Existing implementations of BP fail to achieve acceptable convergence coverage, convergence rate, and linear scaling with hardware resources [4]–[7]. The second direction is hardware support for priority-ordered algorithms through task-based parallelism. Speculative hardware parallel execution of BP has been simulated and implemented in software, but no cost-effective pure hardware implementation exists [8]–[11]. This work implements BP on an FPGA-based speculative parallel accelerator and demonstrates the possibility of increased performance.
Cited by 0
Timothy G. Armstrong, Justin M. Wozniak, Michael Wilde et al. · 2014
Swift/T is a high-level language for writing concise, deterministic scripts that compose serial or parallel codes implemented in lower-level programming models into large-scale parallel applications. It executes using a data-driven task parallel execution model that is capable of orchestrating millions of concurrently executing asynchronous tasks on homogeneous or heterogeneous resources. Producing code that executes efficiently at this scale requires sophisticated compiler transformations: poorly optimized code inhibits scaling with excessive synchronization and communication. We present a comprehensive set of compiler techniques for data-driven task parallelism, including novel compiler optimizations and intermediate representations. We report application benchmark studies, including unbalanced tree search and simulated annealing, and demonstrate that our techniques greatly reduce communication overhead and enable extreme scalability, distributing up to 612 million dynamically load balanced tasks per second at scales of up to 262,144 cores without explicit parallelism, synchronization, or load balancing in application code.
Cited by 54
Vivek Kumar, Julian Dolby, Stephen M. Blackburn · 2016
Processor design has turned toward parallelism and heterogeneous cores to achieve performance and energy efficiency. Developers find high-level languages attractive as they use abstraction to offer productivity and portability over these hardware complexities. Over the past few decades, researchers have developed increasingly advanced mechanisms to deliver performance despite the overheads naturally imposed by this abstraction. Recent work has demonstrated that such mechanisms can be exploited to attack overheads that arise in emerging high-level languages, which provide strong abstractions over parallelism. However, current implementation of existing popular high-level languages, such as Java, offer little by way of abstractions that allow the developer to achieve performance in the face of extensive hardware parallelism.
Cited by 3
Thomas Brandes · Lecture notes in computer science · 1999
As task parallelism has been proven to be useful for applications like real-time signal processing, branch and bound problems, and multidisciplinary applications, the new standard HPF 2.0 of the data parallel language High Performance Fortran (HPF) provides approved extensions for task parallelism that allow nested task and data parallelism. Unfortunately, these extensions allow the spawning of tasks but do not allow interaction like synchronization and communication between tasks during their execution and therefore might be too restrictive for certain application classes. E.g., they are not suitable for expressing the complex interactions among asynchronous tasks as required by multidisciplinary applications. They do not support any parallel programming style that is based on non-deterministic communication patterns. This paper discusses the extension of the task model provided by HPF 2.0 with a task library that allows interaction between tasks during their lifetime, mainly by message passing with an user-friendly HPF binding. The same library with the same interface can also be used for single processors in the local HPF model. The task model of HPF 2.0 and the task library have been implemented in the ADAPTOR HPF compilation system that is available in the public domain. Some experimental results show the easy use of the concepts and the efficiency of the chosen approach.
Cited by 9Open access