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 3,557 papers for “loop scheduling”

Scheduling Uniform Loop Nests

Alain Darte, Yves Robert, Ecole Normale Superieure de Lyon, 69 (France). Lab. de l'Informatique du Parallelisme et al. · OpenGrey (Institut de l'Information Scientifique et Technique) · 1992

This paper surveys scheduling techniques for uniform loop nests. First we introduce the hyperplane method and related variants. Then we extend it by using a different affine scheduling for each statement within the nest. In both cases we present a new, constructive and efficient method to determine optimal solutions. 1 Introduction Loop nests lie in the heart of supercompilers-parallelizers for supercomputers. On one hand their importance in terms of applications is evident: in many scientific programs, the time spent in the execution of a couple of loops represents a large fraction of the total execution time, while the potential parallelism of these loops is often very important. On the other hand, the regular and repetitive structure of loop nests greatly facilitates the use of dependence analysis techniques and of scheduling and allocation strategies. The general problem of finding the optimal scheduling for a task system on a parallel machine is NP-hard (due to the communications...

Cited by 3

Macro-op scheduling: relaxing scheduling loop constraints

I. Kim, Mikko H. Lipasti · 2004

Ensuring back-to-back execution of dependent instructions in a conventional out-of-order processor requires scheduling logic that wakes up and selects instructions at the same rate as they are executed. To sustain high performance, integer ALU instructions typically have single-cycle latency, consequently requiring scheduling logic with the same single-cycle latency. Prior proposals have advocated the use of speculation in either the wakeup or select phases to enable pipelining of scheduling logic to achieve higher clock frequency. In contrast, this paper proposes macro-op scheduling which systematically removes instructions with single-cycle latency from the machine by combining them into macro-ops, and performs nonspeculative pipelined scheduling of multi-cycle operations. Macro-op scheduling also increases the effective size of the scheduling window by enabling multiple instructions to occupy a single issue queue entry. We demonstrate that pipelined 2-cycle macro-op scheduling performs comparably or even better than atomic scheduling or prior proposals for select-free scheduling.

Cited by 29

Sequential open-loop scheduling strategies. Deterministic and Stochastic Scheduling

P. Nash, R. R. Weber · 1982

For certain scheduling problems wi th pre-emptive processing, a dynamic programming formulation reduces the problem to a sequence of deterministic optimal control problems. Simple necessary and sufficient optimality conditions for these deterministic problems are obtainable from the standard results of optimal control theory, and s 0 met i me s 1ead to a na 1y tic soluti 0 ns. Vlh ere t his doe s not happen, then as with many dynamic programming formulations, computational solution is possible in principle, but infeasible in practice. After a survey of this approach to scheduling problems, this paper discusses a simplification of the method which leads to computationally tractable problems which can be expected to yield good, though sub-optimal, scheduling strategies. This new approach is based on the notion of sequential open-loop control, sometimes used in control engineering to solve stochastic control problems by deterministic means, and is not based on dynamic programming. 1.

Cited by 0

Improving OpenMP Loop Scheduling in AutoPas

Hachicha, Mehdi · mediaTUM (Technical University of Munich) · 2024

Particle simulators commonly loop over particles and compute their interactions pairwise. Indeed, running the computations in parallel threads can significantly speed up the simulations. However, developers should look out for load imbalance: the uneven distribution of tasks between threads, such that some finish early and wait instead of taking up more work. For example, this may occur when tasks differ in complexity. To maintain optimal performance, simulators can thus benefit from load balancing techniques when scheduling their loop iterations to the threads. This thesis improves parallel loop scheduling in AutoPas: a particle simulation library. AutoPas employs OpenMP: a library that provides loop scheduling features via compiler directives. We integrate Auto4OMP, which is an OpenMP extension with advanced load balancing capabilities. To test the new setup, we ran different simulations with various parameters. In general, Auto4OMP performed close to the optimal standard OpenMP schedule, but the impact of its advanced scheduling techniques on non-homogeneous simulations was weaker than expected. That said, it showed promising results with homogeneous simulations.\n\n

Cited by 0Open access

Rotation scheduling: a loop pipelining algorithm

Liang-Fang Chao, Andrea S. LaPaugh, Edwin H.‐M. Sha · IEEE Transactions on Computer-Aided Design of Integrated Circuits and Systems · 1997

We consider the resource-constrained scheduling of loops with interiteration dependencies. A loop is modeled as a data flow graph (DFG), where edges are labeled with the number of iterations between dependencies. We design a novel and flexible technique, called rotation scheduling, for scheduling cyclic DFGs using loop pipelining. The rotation technique repeatedly transforms a schedule to a more compact schedule. We provide a theoretical basis for the operations based on retiming. We propose two heuristics to perform rotation scheduling and give experimental results showing that they have very good performance.

Cited by 124

Energy Optimization on OpenMP Loop Scheduling

Yong Dong, Juan Chen · Journal of Software · 2012

Energy consumption has become a serious problem in high-performance computing (HPC) systems. Parallel loops often occupy a significant part of the execution time of overall parallel programs. Thus, reducing their energy consumption is the key to the reduction in energy consumption of the program. This paper discusses energy optimization in OpenMP loop scheduling, which is a method of optimizing energy consumption of parallel loops within a certain performance loss. OpenMP programming includes Uniform-Sized scheduling unit (US)-based Energy-saving Optimal Static Scheduling algorithm (EOSS), UnUniform-Sized scheduling unit (UUS)-based Energy-oriented Static Scheduling algorithm (ESS). EOSS obtains the maximum energy savings under the ideal condition (US) by combining loop rescheduling and voltage/frequency scaling. ESS optimizes energy consumption under the non-ideal condition (UUS). We evaluate these energy-oriented loop scheduling algorithms through simulations on a multiprocessor system. Taking 160 processors as example, five NPB programs with EOSS can reduce 43.5% energy consumption on the average, which is 2.1% more energy saved than the DVFS-only method. ESS can achieve 54% energy savings with the example code we use.

Cited by 1

Energy-Constrained OpenMP Static Loop Scheduling

Juan Chen, Yong Dong, Xuejun Yang et al. · 2008

In high performance parallel computing, energy optimization for parallel loops becomes one key because the time of loops often takes a significant part of the whole execution time. Energy-constrained problem is one of the important research focuses. This paper studies energy-constrained problem based on OpenMP static loop scheduling. Firstly, we propose energy-constrained static scheduling algorithm (ECSS), which utilizes DVS to scale down voltage/frequency of the light-loaded processors in terms of energy constraint. Secondly, we propose Energy Constraint based Performance-Optimal Static Scheduling algorithm (ECPOSS), which combines loop rescheduling and DVS for the better performance under the same energy constraint. We prove ECPOSS can obtain the best performance under the same energy constraint. Through testing NPB3.2-OMP programs on 20-160 multiprocessor simulation environment, we evaluate the effectiveness of our algorithms. Experimental results show the performance of ECPOSS is better than that of ECSS by 4.81% under the 50% energy constraint on 100 processors.

Cited by 4

The Impact Of Parallel Loop Scheduling . . .

David J. Lilja · 1994

Trace-driven simulations of numerical Fortran programs are used to study the impact of the parallel loop scheduling strategy on data prefetching in a shared memory multiprocessor with private data caches. The simulations indicate that to maximize memory performance it is important to schedule blocks of consecutive iterations to execute on each processor, and then to adaptively prefetch singleword cache blocks to match the number of iterations scheduled. Prefetching multiple single-word cache blocks on a miss reduces the miss ratio by approximately 5 to 30 percent compared to a system with no prefetching. In addition, the proposed adaptive prefetching scheme further reduces the miss ratio while significantly reducing the false sharing among cache blocks compared to nonadaptive prefetching strategies. Reducing the false sharing causes fewer coherence invalidations to be generated, and thereby reduces the total network traffic. The impact of the prefetching and scheduling strategies on the temporal distribution of coherence invalidations also is examined. It is found that invalidations tend to be evenly distributed throughout the execution of parallel loops, but that they tend to be clustered when executing sequential program sections. The distribution of invalidations in both types of program sections is relatively insensitive to the prefetching and scheduling strategy.

Cited by 0

Combining Retiming and Scheduling Techniques for Loop Parallelization and Loop Tiling

Alain Darte, Georges-André Silber, Frédéric Vivien · Parallel Processing Letters · 1997

Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this paper, we overcame this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loan independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.

Cited by 61

Combining retiming and scheduling techniques for loop parallelization and loop tiling.

Laboratoire de l'informatique du parallélisme, Darte, Alain, Silber, Georges-Andre et al. · LARA - Libre Acces aux Rapports scientifiques et techniques · 2006

(eng) Tiling is a technique used for exploiting medium-grain parallelism in nested loops. It relies on a first step that detects sets of permutable nested loops. All algorithms developed so far consider the statements of the loop body as a single block, in other words, they are not able to take advantage of the structure of dependences between different statements. In this report, we overcome this limitation by showing how the structure of the reduced dependence graph can be taken into account for detecting more permutable loops. Our method combines graph retiming techniques and graph scheduling techniques. It can be viewed as an extension of Wolf and Lam's algorithm to the case of loops with multiple statements. Loop independent dependences play a particular role in our study, and we show how the way we handle them can be useful for fine-grain loop parallelization as well.

Cited by 0

A Priori Loop Nest Normalization: Automatic Loop Scheduling in Complex Applications

Lukas Trümper, Philipp Schaad, Berke Ates et al. · 2025

The same computations are often expressed differently across software projects and programming languages. In particular, how computations involving loops are expressed varies due to the many possibilities to permute and compose loops. Since each variant may have unique performance properties, automatic approaches to loop scheduling must support many different optimization recipes. In this paper, we propose a priori loop nest normalization to align loop nests and reduce the variation before the optimization. Specifically, we define and apply normalization criteria, mapping loop nests with different memory access patterns to the same canonical form. Since the memory access pattern is susceptible to loop variations and critical for performance, this normalization allows many loop nests to be optimized by the same optimization recipe. To evaluate our approach, we apply the normalization with optimizations designed for only the canonical form, improving the performance of many different loop nest variants. Across multiple implementations of 15 benchmarks using different languages, we outperform a baseline compiler in C on average by a factor of 21.13, state-of-the-art auto-schedulers such as Polly and the Tiramisu auto-scheduler by 2.31 and 2.89, as well as performance-oriented Python-based frameworks such as NumPy, Numba, and DaCe by 9.04, 3.92, and 1.47. Furthermore, we apply the concept to the CLOUDSC cloud microphysics scheme, an actively used component of the Integrated Forecasting System, achieving a 10% speedup over the highly-tuned Fortran code.

Cited by 0Open access