Global ETD Search
Search theses and dissertations gathered from participating repositories worldwide. Every result links back to the library that holds it. No account is needed.
Results
Showing 1 to 18 of 18 for “"Work-stealing"”.
-
Optimizing work stealing algorithms with scheduling constraints
… has gained popularity in conjunction with work-stealing schedulers. Random work-stealing schedulers have been shown to effectively perform dynamic load balancing, yielding provably-efficient schedules and space bounds on shared-memory architectures with uniform memory models. However, the …
-
Bounds on multithreaded computations by work stealing
… and Leiserson [6] gave the first provably good work-stealing work scheduler for multithreaded computations with dependencies. Their scheduler executes a fully strict (i.e., wellstructured) computation on P processors in expected time [mathematical formula], where T denotes the minimum serial …
-
Dynamic processor allocation for adaptively parallel work-stealing jobs
… Using a combination of trace analysis and network simulation, we demonstrate the feasibility of implementing flowlet-based switching.
-
Provably efficient randomized work stealing with first-class parallel loops
… cache-locality and execution time in randomized work stealing. In particular, two versions of LoopFrames are presented: 1-D LoopFrame and an extension to multi-dimensional (M-D) LoopFrame, for non-nested and nested parallel loops, respectively. This paper mainly contributes the theoretical …
-
Design and Implementation of a Nonblocking Randomized Work Stealing Scheduler
… FLCN (Free of Locks, Cilk is Now), a nonblocking work-stealing runtime scheduler that supports Cilk multithreaded programming. The existing OpenCilk runtime system uses lock-based synchronization and thus suffers from lock contention, does not provide progress guarantees, and can experience …
-
A Work-Stealing For Dynamic Workload Balancing On CPU-GPU Heterogeneous Computing Platforms
<p>Although many general purpose workloads have been accelerated on graphical processing units (gpus) over the last decade, other applications whose runtime behaviors are dynamic and irregular such as ones based on trees and graphs have suffered from serious workload imbalance problem caused by …
-
Improving the Performance of Parallel Loops in OpenCilk
… and contributes an extension to randomized work-stealing for first-class loop support that reduces scheduling overheads. Randomized work-stealing schedulers traditionally execute parallel-for loops using parallel divide-and-conquer recursion, which is theoretically efficient and scalable but …
-
Continuation Stealing in Julia
Work stealing schedulers are widely used by parallel programming platforms to distribute tasks across multiple processors. Memory blowup from scheduling a program with work stealing can be bounded by using continuation stealing when new tasks are spawned. Continuation stealing is opposed to child …
-
Adaptive architecture-transparent policy control in a distributed graph reducer
… a study of adaptive load distribution based on work stealing using history and ancestry information in a distributed graph reducer for a nonstrict functional language. The results contribute to the exploration of more flexible run-time-system-level parallelism control implementing a …
-
Analyzing performance and usability of broadcast-based inter-core communication (ATAC) on manycore architecture
… broadcasting by leveraging an on-chip optical network. I designed the new architecture and API for the new broadcasting feature and implemented them on a multicore simulator called Graphite. I also re-implemented common parallel APIs (barrier and work-stealing) which benet from the cheap …
-
An Efficient Data Structure for Implementing Splitter Hyperobjects in Task-Parallel Systems
… thesis also contains theory and implementation work on other topics related to task-parallel programming and work stealing schedulers. Some parts of this thesis represent joint work with William Kuszmaul.
-
Intelligent scheduling for simultaneous CPU-GPU applications
… has addressed this issue of partitioning the workloads between CPU and GPU from various aspects for regular applications which have high parallelism and little data dependent control flows. However, it is still not clear how irregular applications, which behave differently on different inputs, …
-
Efficient Algorithms and Parallel Implementations for Power Series Multiplication
… Power series multiplication algorithms working based on a prescribed precision, say $n$ (where $n$ is a natural number), take the first $n$ coefficients of the two power series as input, multiply them, and return the first $n$ coefficients of the product. While these algorithms can be …
-
Design and analysis of a nondeterministic parallel breadth-first search algorithm
… search implementation. PBFS achieves high workefficiency by using a novel implementation of a multiset data structure, called a "bag," in place of the FIFO queue usually employed in serial breadth-first search algorithms. For a variety of benchmark input graphs whose diameters are …
-
Improving programmability and performance for scientific applications
… by programmers and scientists alike. In our work, this problem is encountered when developing an optimized framework to best exploit the semantic properties of a finite-element solver. In efforts to address this problem, we explore programming and runtime models which decouple algorithmic …
-
Queuing Model Based Approaches for Extremely High Throughput Wireless Networks with Big Data Transmission
In this work we look at Big Data transmission using wireless networks. The first goal is to model the modern communication node equipped with multibeam antenna working on IEEE 802.11ac/ax (5G/6G) standard. We first model the flow of packets through the node using Queuing theory that reflects the …
-
Productive Programming Systems for Heterogeneous Supercomputers
… of today's scientific and data analytics workloads are still run on relatively energy inefficient, heavyweight, general-purpose processing cores, often referred to in the literature as latency-oriented architectures. The flexibility of these architectures and the programmer aids included …
-
Towards a New Directive-based Tasking API for Distributed Systems
… implementation of the runtime. The goal of this work is to guide the definition of TagHit's concept and semantics and to assess the implementation cost and challenges of creating and scheduling tasks in TagHit. Finally, I present two TagHit benchmarks with results that show the design and …