Skip to content
Free planNo credit card requiredStart writing
AI for Research home
AI for Research home
Dashboard
Sign inGet started

Search 250 million research papers

Read the abstract, see who wrote it and who cites it, and get the citation in APA, MLA, Chicago or Harvard.

About 2,252 papers for “irregular programs”

Lonestar: A suite of parallel irregular programs

Milind Kulkarni, Martin Burtscher, Cǎlin Caşcaval et al. · 2009

Until recently, parallel programming has largely focused on the exploitation of data-parallelism in dense matrix programs. However, many important application domains, including meshing, clustering, simulation, and machine learning, have very different algorithmic foundations: they require building, computing with, and modifying large sparse graphs. In the parallel programming literature, these types of applications are usually classified as irregular applications, and relatively little attention has been paid to them. To study and understand the patterns of parallelism and locality in sparse graph computations better, we are in the process of building the Lonestar benchmark suite. In this paper, we characterize the first five programs from this suite, which target domains like data mining, survey propagation, and design automation. We show that even such irregular applications often expose large amounts of parallelism in the form of amorphous data-parallelism. Our speedup numbers demonstrate that this new type of parallelism can successfully be exploited on modern multi-core machines.

Cited by 184

Runtime Support to Parallelize Adaptive Irregular Programs

Yuan-shin Hwang, Bongki Moon, Shamik Sharma et al. · 1994

This paper describes how a runtime support library can be used as compiler runtime support in irregular applications. The CHAOS runtime support library carries out optimizations designed to reduce communication costs by performing software caching, communication coalescing and inspector/executor preprocessing. CHAOS also supplies special purpose routines to support specific types of irregular reduction and runtime support for partitioning data and work between processors. A number of adaptive irregular codes have been parallelized using the CHAOS library and performance results from these codes are also presented in this paper.

Cited by 0

Runtime support to parallelize adaptive irregular programs

Yuan-Shin Hwang, Bongki Moon, Shamik Sharma, Joel Saltz et al. · 1994

This paper describes how a runtime support library can be used as compiler runtime support in irregular applications. The CHAOS runtime support library carries out optimizations designed to reduce communication costs by performing software caching, communication coalescing and inspector/executor preprocessing. CHAOS also supplies special purpose routines to support specific types of irregular reduction and runtime support for partitioning data and work between processors. Anumber of adaptive irregular codes have been parallelized using the CHAOS library and performance results from these codes are also presented in this paper.

Cited by 0

Lonestar: A Suite of Parallel Irregular Programs ∗

Milind Kulkarni A, Martin Burtscher A, Călin Cas¸caval B et al. · 2013

Until recently, parallel programming has largely focused on the exploitation of data-parallelism in dense matrix programs. However, many important application domains, including meshing, clustering, simulation, and machine learning, have very different algorithmic foundations: they require building, computing with, and modifying large sparse graphs. In the parallel programming literature, these types of applications are usually classified as irregular applications, and relatively little attention has been paid to them. To study and understand the patterns of parallelism and locality in sparse graph computations better, we are in the process of building the Lonestar benchmark suite. In this paper, we characterize the first five programs from this suite, which target domains like data mining, survey propagation, and design automation. We show that even such irregular applications often expose large amounts of parallelism in the form of amorphous data-parallelism. Our speedup numbers demonstrate that this new type of parallelism can successfully be exploited on modern multi-core machines. 1

Cited by 0

Processor Allocation for Optimistic Parallelization of Irregular Programs

Versaci, Francesco, Pingali, Keshav · arXiv (Cornell University) · 2012

Optimistic parallelization is a promising approach for the parallelization of irregular algorithms: potentially interfering tasks are launched dynamically, and the runtime system detects conflicts between concurrent activities, aborting and rolling back conflicting tasks. However, parallelism in irregular algorithms is very complex. In a regular algorithm like dense matrix multiplication, the amount of parallelism can usually be expressed as a function of the problem size, so it is reasonably straightforward to determine how many processors should be allocated to execute a regular algorithm of a certain size (this is called the processor allocation problem). In contrast, parallelism in irregular algorithms can be a function of input parameters, and the amount of parallelism can vary dramatically during the execution of the irregular algorithm. Therefore, the processor allocation problem for irregular algorithms is very difficult. In this paper, we describe the first systematic strategy for addressing this problem. Our approach is based on a construct called the conflict graph, which (i) provides insight into the amount of parallelism that can be extracted from an irregular algorithm, and (ii) can be used to address the processor allocation problem for irregular algorithms. We show that this problem is related to a generalization of the unfriendly seating problem and, by extending Turán's theorem, we obtain a worst-case class of problems for optimistic parallelization, which we use to derive a lower bound on the exploitable parallelism. Finally, using some theoretically derived properties and some experimental facts, we design a quick and stable control strategy for solving the processor allocation problem heuristically.

Cited by 0Open access

Parallel programming frameworks for irregular and regular programs

Lee, Hochan, 0000-0001-7158-6633 · Texas Digital Library (University of Texas) · 2024

Developing efficient parallel programs is challenging because it demands a comprehensive understanding spanning from algorithms, such as computation types, dependencies between computations, and memory operation patterns, to architectures, such as memory hierarchy, computing devices, and a hardware topology. Further, selecting and exploiting suitable programming abstractions is essential. One effective strategy to manage these complexities and parallelizing programs is to categorize programs based on the main data structures that they use. Parallel programs can be classified into irregular and regular programs. Irregular programs typically involve unstructured and sparse data structures such as graphs, trees, or priority queues, which necessitate irregular and sparse memory access patterns. In many irregular programs, computation depends on dynamic data dependencies, posing challenges for predicting and efficiently planning parallel execution. Examples of irregular programs include graph analytics programs, such as single-source shortest path, page-rank, and community detection. On the other hand, regular programs exploit structured and dense data structures such as matrices and arrays. These programs exhibit more structured and dense memory access patterns with static data dependencies, leading predictable execution. Linear algebraic programs such as Cholesky factorization and computational simulations such as radioactive heat transfer simulation are examples of the regular programs. Given the distinct properties, irregular and regular programs demand different approaches to achieve high parallel execution, and many parallel programming frameworks have been proposed, each with different programming model and runtime designs for their target workloads. This dissertation advances the current state-of-the-art in parallel programming frameworks by enhancing programming models and designing optimizations for high-parallelism on modern architectures, addressing both irregular and regular workloads. Our first contribution is in studying performance of programming abstractions for graph analytics. Traditionally, parallel graph analytics algorithms have been implemented in systems like Pregel, Galois, and Ligra that support graph data structures and operations directly. An alternative approach expresses graph algorithms in terms of sparse matrix kernels such as sparse matrix-vertex and matrix-matrix multiplication. How does matrix-based abstraction perform compared to graph-based abstraction? To study it, we implemented a matrix API for graph analytics on top of Galois. Experiments on a 56 core CPU show that the matrix-based runtime and API is 5× slower on the average than the graph-based runtime and API. Our in-depth study identified inherent performance and expressiveness limitations of the matrix-based programming abstraction for graph analytics workloads. Our second contribution is in distributed programming frameworks for graph analytics. Recent distributed graph analytics systems such as Gemini and Gluon solely support adjacent-vertex algorithms in which nodes are updated iteratively using properties of adjacent neighbors of those nodes. However, there are many algorithms such as Shiloach-Vishkin for connected components and Louvain for community detection, that cannot be expressed in this model. These algorithms may produce better quality output or may be more efficient than adjacent-vertex algorithms. We call these algorithms trans-vertex algorithms. In this dissertation, we present Kimbap, a distributed graph analytics system efficiently supporting both adjacent- and trans-vertex algorithms. Kimbap permits the computation at a node to read and write properties of any node in the graph. Kimbap’s programming model allows programmers to write high-level iterative graph analytics programs, while the Kimbap compiler automatically generates high performance and scalable distributed code. The underlying system uses a distributed node-property map optimized for highly concurrent sparse reads and reductions on arbitrary node properties. Experiments on CPU clusters with up to 256 machines, roughly 12000 threads total, show 4x faster performance than the state-of-the-art hand-optimized trans-vertex programs, and matches or outperforms the state-of-the-art distributed graph analytics system on adjacent-vertex programs. Our last contribution is in task-based parallel programming frameworks. Python has been a reasonable choice for developing scientific applications, supported by its rapidly expanding infrastructure such as Jupyter and a rich set of scientific libraries such as NumPy and CuPy optimized for modern architectures. However, existing Python-based task parallel programming systems in this area are often monolithic in the sense that they assume that most of the codebase is written within their frameworks. It prevents programmers from leveraging rapidly evolving, highly-optimized libraries and implementations developed in different programming models, runtime systems, or architectures. To address these limitations, we propose Parla. Parla is a Python-based task-parallel programming framework for a heterogeneous shared-memory machine. The main contribution of Parla is gradual adoption that enables programmers to easily migrate, integrate, and parallelize existing sequential Python programs. Parla allows external library calls within tasks without any modification. Parla efficiently parallelizes tasks within a single process, utilizing resource aware task mapping, scheduling, and execution. By internally managing device resources such as GPU context, memory, and computation units, Parla alleviates complexity of heterogeneous architecture programming and allows programmers to transform existing sequential programs into highly parallelized versions with ease. Lastly, it is highly optimized for NVIDIA GPU architectures by leveraging device-specific features including CUDA’s event mechanism. Parla is funded by a DOE PSAAP grant, and several graduate students are involved in its implementation. My contributions are designing and implementing resource management and task scheduling mechanisms and policies in the Parla runtime system. We show that Parla achieves competitive performance with state-of-the-art implementations while simplifying parallel programming.

Cited by 0Open access

The Galois System: Optimistic Parallelization of Irregular Programs

Kulkarni, Milind Vidyadhar · eCommons (Cornell University) · 2008

The last several years have seen multicore architectures become ascendant in the computing world. As a result, it is no longer sufficient to rely on increasing single-threaded performance to improve application performance; instead, programmers must turn to parallelization to realize the performance gains of multicore architectures. While much research over the past three decades have focused on parallelizing regular programs which operate over arrays and matrices, much less effort has been focused on irregular programs which operate over pointer-based data structures such as trees and graphs. In fact, it is not even clear that a significant amount of parallelism even exists in these applications. We identify a common type of parallelism that arises in irregular programs that operate over worklists of various kinds, which we call amorphous data-parallelism. Due to the data-dependent nature of these applications, static compiler analysis does not suffice to uncover any parallelism. Instead, successful parallelization requires speculative, or optimistic, parallelization. However, existing speculation techniques, such as thread-level speculation, are too low-level to recognize and extract useful parallelism from these applications. We present the Galois system for optimistic parallelization which uses high-level abstractions to express amorphous data-parallelism in irregular programs, and uses semantic properties of data structures to automatically parallelize such programs. These abstractions allow programs with amorphous data-parallelism to be written in a sequential manner, relying on run-time support to extract parallelism. We then develop abstractions which allow programmers to succinctly capture locality properties of irregular data structures. We show how these abstractions can be used to improve locality, improve speculation performance and reduce speculation overhead. We also present a novel parallel scheduling framework which allows programmers to leverage algorithm semantics to intelligently schedule concurrent computation, improving performance. We demonstrate the utility of the Galois approach, as well as the extensions that we propose, across a wide range of irregular applications demonstrating amorphous data-parallelism. We find that the Galois approach can be used to extract significant parallelism with low programmer overhead.

Cited by 0Open access

Efficient execution of irregular programs on heterogeneous systems

Rashid Kaleem · Texas ScholarWorks (Texas Digital Library) · 2017

Programmable accelerators such as GPUs, FPGAs, and DSPs enable\nmodern systems to provide higher performance for many workloads than is \npossible by using conventional processors alone. \nTraditionally, portability of applications to these accelerators and \nbetween accelerators was a major hurdle in utilizing accelerators \nin a heterogeneous system. With the emergence of standardized programming \nAPIs such as OpenCL, this problem is being ameliorated and \nmany accelerators can now be programmed using a single API.\n\nIn this work, we address the efficient execution of \\emph{irregular}\nprograms on heterogeneous systems. Irregular programs are used extensively\nin problem domains like graph analytics and finite-element methods, and\nthey are characterized by data-dependent control flow and memory accesses \nthat cannot be predicted at compile time. We focus on heterogeneous systems \nthat provide a coherent memory to all devices.\n\nFirst, we describe a set of compiler and runtime techniques to\nsupport efficient execution of irregular programs on heterogeneous\nsystems composed of a CPU and an integrated GPU. The compiler allows \napplications written in C++ to be executed on the GPU without any \nprogrammer effort. The runtime system solves the load imbalance arising \nfrom irregularity in the applications by dynamically assigning work to\neach device.\n\nNext, we present an alternative implementation strategy for\nirregular applications on a system with more heterogeneity. Specifically,\ngraph applications can be expressed as \\textit{producer-consumer}\ncomputations on FPGA+CPU heterogeneous systems. This approach allows for\nbetter utilization of the capabilities of each device and suggests a\nprogramming model for accelerators that goes beyond the \\textit{offload}\nmodel.\n\nFinally, we explore efficient execution of irregular\napplications on accelerators that do not share a\ncoherent memory with the master processor. For discrete GPUs, we explore\nimplementation strategies of graph application, focusing on\nsynchronization tradeoffs and present optimizations that address the\nsynchronization overheads both within and across devices.

Cited by 0Open access

Optimization techniques for irregular and pointer-based programs

Rafael Asenjo, Francisco Corbera, Eladio Gutiérrez et al. · 2004

Current compilers show inefficiencies when optimizing complex applications, both analyzing dependences and exploiting critical performance issues, like data locality and instruction/thread parallelism. Complex applications usually present irregular and/or dynamic (pointer-based) computational/data structures. By irregular we means applications that arrange data as multidimensional arrays and issue memory references through array indirections. Pointer-based applications, on the other hand, organize data as pointer-based structures (lists, trees, etc.) and issue memory references by means of pointers. We discuss optimization/parallelization and program analysis techniques we have developed to instruct a compiler to generate efficient object code from important classes of irregular and pointer-based applications. These techniques are embodied into a methodology that proceeds in three stages: program structure recognition, data analysis and program optimization/parallelization based on code/data transformations.

Cited by 3

Synchronization Efficient Scheduling of Fine-grained Irregular Programs

Tao Tao · 2023

This paper discusses the theory behind the global rebalancing policy, a new emerging paradigm of scheduling dynamic, irregular programs. According to this policy, task workload is distributed in rebalancing sessions enabled by global thread barriers, while traditional approaches such as work stealing rely on localized, concurrent deque operations. We show that the parallel execution model based on the global rebalancing policy has an amortized running time bound of <tex xmlns:mml="http://www.w3.org/1998/Math/MathML" xmlns:xlink="http://www.w3.org/1999/xlink">$\mathscr{O}(T_{1}/P+T_{\infty})$</tex>, including all synchronization overhead. Based on this result, we further conclude that the global rebalancing policy asymptotically outperforms traditional work stealing as long as the input program is sufficiently parallel. We also present twelve benchmarks to demonstrate the parallel scalability of our system up to 16 processors: All benchmarks scale close to ideal.

Cited by 0

Scheduling strategies for optimistic parallel execution of irregular programs

Milind Kulkarni, Patrick Carribault, Keshav Pingali et al. · 2008

Recent application studies have shown that many irregular applications have a generalized data parallelism that manifests itself as iterative computations over worklists of different kinds. In general, there are complex dependencies between iterations. These dependencies cannot be elucidated statically because they depend on the inputs to the program; thus, optimistic parallel execution is the only tractable approach to parallelizing these applications.

Cited by 62

Repurposing GPU Ray Tracing Architecture for Accelerating Irregular Programs

Mandarapu, Durga Keerthi · Figshare · 2025

With the near-ending of Moore’s law and ever increasing demand for compute power, Domain-Specific Accelerators (DSA) have become a default choice for high-performance workloads. However, developing a custom DSA is an extremely time-consuming and expensive process that only a few organizations can afford. This thesis shows how to repurpose GPU Ray Tracing Architecture, a DSA built for rendering in graphics applications, for non-rendering applications such as k-nearest neighbor search, collision detection in DEM simulations, and spatial queries. The main purpose of Ray Tracing Architecture is to compute intersections between rays and objects in a scene using Euclidean distance. Even though this hardware is capable of computing only the Euclidean distance, Arkade introduces two reductions to compute neighbors according to other distances such as \(L^p\) norms and Cosine distance. Mochi and S-ray further show how to reinterpret ray-object intersection tests to compute intersections between objects for collision detection and spatial query execution.

Cited by 0Open access

Repurposing GPU Ray Tracing Architecture for Accelerating Irregular Programs

Mandarapu, Durga Keerthi · Purdue · 2025

With the near-ending of Moore’s law and ever increasing demand for compute power, Domain-Specific Accelerators (DSA) have become a default choice for high-performance workloads. However, developing a custom DSA is an extremely time-consuming and expensive process that only a few organizations can afford. This thesis shows how to repurpose GPU Ray Tracing Architecture, a DSA built for rendering in graphics applications, for non-rendering applications such as k-nearest neighbor search, collision detection in DEM simulations, and spatial queries. The main purpose of Ray Tracing Architecture is to compute intersections between rays and objects in a scene using Euclidean distance. Even though this hardware is capable of computing only the Euclidean distance, Arkade introduces two reductions to compute neighbors according to other distances such as \(L^p\) norms and Cosine distance. Mochi and S-ray further show how to reinterpret ray-object intersection tests to compute intersections between objects for collision detection and spatial query execution.

Cited by 0Open access

Exploiting Dynamic Regular Patterns in Irregular Programs for Efficient Vectorization

Kelun Lei, Shaokang Du, Xin You et al. · ACM Transactions on Architecture and Code Optimization · 2025

Modern optimizing compilers are able to exploit memory access or computation patterns to generate vectorized codes. However, such patterns in irregular programs are unknown until runtime due to the input dependence. Thus, either compiler’s static optimization or profile-guided optimization cannot represent the patterns for any common input, which leads to suboptimal vectorization. To address the above drawback, we propose DynVec , 1 a framework to automatically exploit regular patterns buried deeply inside irregular programs and apply corresponding optimizations for better vectorization. Due to the integration of workload distribution and the ability to represent instruction features and identify regular patterns with effective feature extraction and data re-arranging methods, DynVec can generate highly efficient vectorized codes for both serial and parallel irregular programs by replacing gather / scatter / reduction operations with optimized operation groups. We evaluate DynVec on optimizing irregular programs such as SpMV and graph programs with representative sparse matrix datasets. The experiment results show that DynVec achieves significant speedup compared to the state-of-the-art implementations across a range of X86 and ARM platforms.

Cited by 1Open access

Compiler Optimization for Irregular Memory Access Patterns in PGAS Programs

Thomas B. Rolinger, Christopher D. Krieger, Alan Sussman · arXiv (Cornell University) · 2023

Irregular memory access patterns pose performance and user productivity challenges on distributed-memory systems. They can lead to fine-grained remote communication and the data access patterns are often not known until runtime. The Partitioned Global Address Space (PGAS) programming model addresses these challenges by providing users with a view of a distributed-memory system that resembles a single shared address space. However, this view often leads programmers to write code that causes fine-grained remote communication, which can result in poor performance. Prior work has shown that the performance of irregular applications written in Chapel, a high-level PGAS language, can be improved by manually applying optimizations. However, applying such optimizations by hand reduces the productivity advantages provided by Chapel and the PGAS model. We present an inspector-executor based compiler optimization for Chapel programs that automatically performs remote data replication. While there have been similar compiler optimizations implemented for other PGAS languages, high-level features in Chapel such as implicit processor affinity lead to new challenges for compiler optimization. We evaluate the performance of our optimization across two irregular applications. Our results show that the total runtime can be improved by as much as 52x on a Cray XC system with a low-latency interconnect and 364x on a standard Linux cluster with an Infiniband interconnect, demonstrating that significant performance gains can be achieved without sacrificing user productivity.

Cited by 0Open access

Dynamic Scheduling of Irregular Stream Programs toward Many-Core Scalability

Changwoo Min, Young Ik Eom · IEEE Transactions on Parallel and Distributed Systems · 2014

The stream programming model has received much interest because it naturally exposes task, data, and pipeline parallelism. However, most priorwork has focused on the static scheduling of regular stream programs. Therefore, irregular applications cannot be handled in static scheduling, and the load imbalance caused by static scheduling faces scalability limitations in many-core systems. In this paper, we introduce the DANBI programming model, which supports irregular stream programs, and propose dynamic scheduling techniques. Scheduling irregular stream programs is very challenging, and the load imbalance becomes a major hurdle to achieving scalability. Our dynamic load-balancing scheduler exploits producer-consumer relationships already expressed in the DANBI program to achieve scalability. Moreover, it effectively avoids the thundering-herd problem and dynamically adapts to load imbalance in a probabilistic manner. It surpasses prior static stream scheduling approaches which are vulnerable to load imbalance and also surpasses prior dynamic stream scheduling approaches which result in many restrictions on supported program types, on the scope of dynamic scheduling, and on data ordering preservation. Our experimental results on a 40-core server show that DANBI achieves an almost linear scalability and outperforms state-of-the-art parallel runtimes by up to 2.8 times.

Cited by 5