In this paper, we first study in a Hilbertian framework the weak convergence of a general Gradient Projection Algorithm for minimizing a convex function of class C-1 over a convex constraint set. The way of selecting ...
详细信息
In this paper, we first study in a Hilbertian framework the weak convergence of a general Gradient Projection Algorithm for minimizing a convex function of class C-1 over a convex constraint set. The way of selecting the stepsizes corresponds to the one used by Lopez et al. for the particular case of the Split Feasibility Problem. This choice allows us to avoid the computation of operator norms. Afterwards, a relaxed version of the Gradient Projection Algorithm is considered where the feasible set is approximated by half-spaces making the projections explicit. Finally, to get the strong convergence, each step of the general Gradient Projection Method is combined with a viscosity step. This is done by adapting Halpern's algorithm to our problem. The general scheme is then applied to the Split Equality Problem, and also to the Split Feasibility Problem.
Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given n threads and m >= n distinct priority queues, task insertions a...
详细信息
ISBN:
(纸本)9781450392044
Designing and implementing efficient parallel priority schedulers is an active research area. An intriguing proposed design is the Multi-Queue: given n threads and m >= n distinct priority queues, task insertions are performed uniformly at random, while, to delete, a thread picks two queues uniformly at random, and removes the observed task of higher priority. This approach scales well, and has probabilistic rank guarantees: roughly, the rank of each task removed, relative to remaining tasks in all other queues, is O(m) in expectation. Yet, the performance of this pattern is below that of well-engineered schedulers, which eschew theoretical guarantees for practical efficiency. We investigate whether it is possible to design and implement a Multi-Queue-based task scheduler that is both highly-efficient and has analytical guarantees. We propose a new variant called the Stealing Multi-Queue (SMQ), a cache-efficient variant of the Multi-Queue, which leverages both queue affinity-each thread has a local queue, from which tasks are usually removed;but, with some probability, threads also attempt to steal higher-priority tasks from the other queues-and task batching, that is, the processing of several tasks in a single insert / remove step. These ideas are well-known for task scheduling without priorities;our theoretical contribution is showing that, despite relaxations, this design can still provide rank guarantees, which in turn implies bounds on total work performed. We provide a general SMQ implementation which can surpass state-of-the-art schedulers such as OBIM and PMOD in terms of performance on popular graph-processing benchmarks. Notably, the performance improvement comes mainly from the superior rank guarantees provided by our scheduler, confirming that analytically-reasoned approaches can still provide performance improvements for priority task scheduling. The full version of this paper is available in [24].
Many irregular algorithms converge more quickly when they execute tasks in a specific order. When this order is discovered at run time, the algorithm demands a dynamic task scheduler. Scaling a priority scheduler to l...
详细信息
ISBN:
(纸本)9798400704161
Many irregular algorithms converge more quickly when they execute tasks in a specific order. When this order is discovered at run time, the algorithm demands a dynamic task scheduler. Scaling a priority scheduler to large systems with many cores is challenging and while many concurrent priority schedulers (CPS) have been proposed, a general classification of their design space is still lacking. We survey prior work and propose three dimensions for the design of CPSs: the degree of synchrony, the drift of priorities, and the underlying data structure. We use this taxonomy to classify existing schedulers and evaluate their strengths and weaknesses. Building on our observations, we propose the Multi Bucket Queue (MBQ) which targets a promising unexplored point in the design space for concurrent priority scheduling. The MBQ leverages the strengths of the MultiQueue and Multi-Level Bucket Queue, while avoiding their weaknesses, yielding a CPS that keeps threads busy and running useful work, yet with high-effciency queue operations. Our experimental results show that the MBQ is competitive with or outperforms prior work.
暂无评论