{"id":"6f235218-0c60-48f2-b27c-f0b7566f04ce","arxiv_id":"2507.20312","paper_version":1,"verdict":"CONDITIONAL","confidence":"MODERATE","novelty_score":6.0,"correctness_risk":"medium","formal_verification":"none","parameter_count":8,"one_line_summary":"RL-based selection (Q-Learn and SARSA) can match or approach an oracle's scheduling choices in OpenMP, but only after 144 exploration steps, and the reward function and expert chunk parameter largely determine whether it pays off.","lead":"This paper compares expert-coded and reinforcement-learning-based methods for choosing which OpenMP loop scheduling algorithm to use while a parallel program runs. It finds that RL can learn good choices but pays a heavy exploration cost, and that mixing in expert-tuned chunk sizes improves both approaches.","discovery_kind":"extension","skeptic_critique":{"model":"deepseek-v4-flash","headline":"Eq. 11's record-based reward and the undefined RL state make the claimed learning order-dependent and unreproducible as written; the released code should settle whether selections are stable.","rationale":"The paper is a large factorial empirical study with a clear central claim, and I read it in good faith. Its strongest support is the 3,600-execution campaign and the per-loop-instance selection plots in Figs. 7 and 8, which do show that Q-Learn with LT reward can match the Oracle after a 144-instance exploration phase on several application-system pairs. Independent support includes released data and scripts [27,28], although these artifacts are not executable from the manuscript text alone. My concern is narrower than 'the results are wrong': the only reward rule (Eq. 11) and the state space in Eqs. 9 and 10 are specified incompletely, and as written the reward is an order-dependent record statistic rather than a stable performance signal. The reader's weakest assumption flagged the non-stationarity of the running min/max; I partially agree and extend that concern to the missing initialization and update rules and to the undefined state representation. Because this concern is checkable from the released code, I do not move the verdict away from CONDITIONAL: the revision should either document and justify the exact min/max and state machinery or replace Eq. 11 with a cleaner reward formulation. If the proposed test shows that reversing the exploration order changes the learned selection, then the claim that RL methods learn high-performing scheduling policies would need substantial re-evaluation.","tokens_in":26808,"tokens_out":8850,"duration_ms":102128,"concrete_test":"Inspect the released code and data [27,28] to extract the actual implementation of Eq. 11 (min/max initialization and update) and the Q-table state encoding. Then run Q-Learn with LT reward on STREAM Triad on Cascade-Lake twice: once with the published explore-first order and once with the reverse explore-first order, keeping all other settings identical. If the post-learning selected algorithm differs, or the total median performance degradation changes by more than the roughly 2% run-to-run variation reported in the paper, Eq. 11's record-based rewards are order-dependent and the claimed learned policy is not stable.","verdict_should_be":"UNCHANGED","load_bearing_attack":"The central claim requires that the Q-Learn and SARSA agents genuinely learn from per-loop rewards, yet the only reward rule given, Eq. 11, is not a normalization: it assigns r+ only when the current loop time or LIB is a new running minimum, r- only when it is a new running maximum, and a fixed neutral value otherwise. Because min and max are taken over already executed loop instances, the same execution time yields different rewards depending on sampling order and on how many records have already been set. With Q-values initialized to 0 and rewards set to +0.01, -2.0, and -4.0, an action that sets a new min receives Q approx 0.005, while a later neutral action receives Q approx -1; the Q-values therefore encode order statistics, not expected performance. The manuscript does not state how min and max are initialized for the first loop instance, how they are updated for non-stationary loops, or what the state s in Eqs. 9 and 10 actually denotes. The only hint, '144 combinations of scheduling algorithms,' suggests state equals the previously selected algorithm, but this is never stated. Without this specification, the post-learning selections reported in Figs. 7 and 8 cannot be attributed to a well-defined learning process. This is load-bearing because a corrected reward or state definition could change which algorithms are selected and therefore weaken the paper's central claim about RL learning high-performing scheduling decisions.","agreement_with_reader":"partial"},"referee_report":{"model":"deepseek-v4-flash","summary":"This paper studies automatic selection of OpenMP loop scheduling algorithms for repeated-loop HPC applications. It compares three expert-based methods from the authors' prior Auto4OMP work (RandomSel, ExhaustiveSel, ExpertSel) with two novel model-free RL methods (Q-Learn and SARSA) embedded in the LB4OMP runtime, using two reward signals (loop time and load-imbalance LIB) with and without an expert chunk parameter. The evaluation is a factorial campaign covering six applications (Mandelbrot, STREAM Triad, Triangle Counting, HACCKernels, LULESH, SPHYNX) on three systems (Broadwell, Cascade-Lake, EPYC), 720 configurations and 3,600 executions with five repetitions. Performance is reported as degradation relative to an Oracle baseline. The main findings are that RL-based selection can match Oracle's choice after an expensive 144-instance explore-first phase when a loop-time reward is used, that LIB rewards perform poorly by over-prioritizing balance, and that combining expert knowledge via expChunk substantially improves both families.","tokens_in":27151,"tokens_out":6852,"duration_ms":66746,"significance":"The experimental campaign is a genuine strength: six diverse applications, three systems, 720 configurations, 3,600 executions, five repetitions, with data and scripts released ([27], [28]). The paper also exposes the exploration-cost trade-off and shows that reward design, not just the RL algorithm, is a first-order factor. If the RL reward and state definitions are clarified and the reported learning behavior is robust, the demonstration that online per-loop schedule selection can approach an oracle in repeated-loop applications is a useful contribution to OpenMP scheduling and algorithm selection.","major_comments":[{"comment":"Equation (11) is not a normalization of the current metric to the observed range; it is a record-statistics reward: r+ is awarded only when x is a new running minimum, r- only when x is a new running maximum, and the fixed neutral r0 otherwise. Because min_t and max_t are taken over already executed loop instances, the same measured loop time or LIB yields different rewards depending on sampling order and on how many records have already been set. The manuscript also does not state how min_t and max_t are initialized for the first loop instance or how they are updated for non-stationary loops. With Q-values initialized to 0 and the stated rewards (+0.01, -2.0, -4.0), an action that sets a first record receives Q approximately 0.005 while a later neutral action receives Q approximately -1, so the Q-values encode order statistics rather than expected performance. Since all RL results in Figs. 7 and 8 depend on this reward, the paper's central claim that the agents 'learn high-performing scheduling decisions' is not supported as written; please either correct the reward definition or provide the exact implementation and show that the selections are insensitive to record order.","section":"Section 3.5, Eq. 11"},{"comment":"The state s used in the Q-learning and SARSA updates is never defined. The only quantitative hint is that the Q-table contains 144 state-action combinations for a 12-algorithm portfolio, which suggests that s is the previously selected scheduling algorithm, but this is not stated anywhere. The description of the explore-first policy ('selects every scheduling algorithm ... considering all possible different orders' requiring 144 loop instances) is ambiguous for the same reason. Without a definition of s and s', Eqs. (9)-(10) cannot be instantiated, the experiment is not reproducible from the manuscript, and the post-learning selections reported in Figs. 7 and 8 cannot be attributed to a well-defined learning process.","section":"Section 3.5, Eqs. 9-10"},{"comment":"The headline comparison in Fig. 5 reports only the median of five repetitions per cell, with no confidence intervals or statistical tests. Several quantitative claims in Section 4.2 rely on small differences, e.g., ExhaustiveSel with expChunk 'surpassed Oracle by 1.4%' for SPHYNX on EPYC, and the statement that 'Q-Learn and SARSA with LT reward and expChunk achieved similar performance.' Given that the same section reports coefficients of variation above 1 for STREAM Triad and LULESH, these differences may be within run-to-run noise. Please add dispersion measures or a statistical analysis (the ANOVA mentioned in Section 7 would be natural) or soften the affected claims.","section":"Section 4.2, Fig. 5"}],"minor_comments":[{"comment":"Table 2 and the surrounding text label Mandelbrot's third loop inconsistently as L2 and L3; unify the notation.","section":"Section 4.1, Table 2"},{"comment":"Equation (11) has a stray closing parenthesis after max_t(x), and the subscripts min_t and max_t are not defined before use.","section":"Section 3.5, Eq. 11"},{"comment":"The color scale in Fig. 5 is clipped at 100% even though many degradation values exceed 100% (e.g., 15,673%); consider a logarithmic or two-scale visualization or annotate clipped cells.","section":"Section 4.2, Fig. 5"},{"comment":"The statement that alpha decay 'prevents agents from ever selecting a single action' is unclear; a decaying learning rate does not by itself prevent convergence, so the intended mechanism should be explained.","section":"Section 3.5"},{"comment":"The definition of Oracle as a manually selected combination 'across ... time-step' should state explicitly whether Oracle is allowed to switch algorithms between time-steps, since Figs. 7 and 8 present it as a fixed selection in some panels.","section":"Section 3.3 and Section 4.2"}],"recommendation":"major_revision","confidential_remarks":null},"author_rebuttal":null,"desk_editor":{"model":"deepseek-v4-flash","letter":"Quick take: this is a real experimental campaign, and the headline findings are probably right—but the RL methods section is under-specified enough that the paper as written is not fully reproducible.\n\nThe new content is the full factorial comparison of expert-based (RandomSel, ExhaustiveSel, ExpertSel) and RL-based (Q-Learn, SARSA) scheduling selection inside the LB4OMP runtime: six applications, three systems, 720 configurations, 3,600 executions, five repetitions per cell. The results that matter: reward choice matters more than the RL variant; LIB as a reward reliably produces bad schedules; explore-first eats 144 of 500 loop instances (28.8%); combining expChunk with RL gives the best of both. These are useful, non-obvious findings for anyone building runtime schedulers. I also give them credit for reporting the exploration cost transparently and for not overclaiming: they explicitly say there is no free lunch and that these methods need repeated loops.\n\nThe soft spots, in rough order of severity. First, Eq. 11 is not a normalization—it assigns rewards based on whether the current value is a new running min or max. The paper does not say how min/max are initialized or updated, and the state s in Eqs. 9-10 is never defined; the \"144 combinations\" hint means \"previous algorithm,\" but it is not stated. So the Q-values encode order statistics, not expected rewards, and the \"learning\" claim is not formally grounded as written. This is the main issue for any reviewer: either the authors fix the description or, if the code does something better, they should say so. They point to released code and data, so this is resolvable, but it should be resolved before publication. Second, the headline heatmap in Fig. 5 shows only medians, with no variance; given five reps per cell and noisy HPC hardware, some of those differences could be noise. Fig. 6 has error bars, so the data exist—move them to Fig. 5. Third, the Oracle is built from the same portfolio and the same experiments, so it is an in-sample upper bound; fine, but the authors should say so more clearly.\n\nNone of this kills the paper. The main empirical message—dynamic selection is viable, RL methods are exploration-hungry, and reward design is the key lever—survives the spec gaps. The RL formalism is the area that needs a careful rewrite, and a serious referee should have access to the artifact.\n\nWho this is for: OpenMP/runtime developers and people in autotuning or algorithm selection. It is an incremental but solid contribution to that community. I would accept it for peer review, with the request that the RL sections be made precise and reproducible.","headline":"Solid empirical comparison of expert- and RL-based OpenMP scheduling selection; main results are believable, but the RL formalization is under-specified enough that the paper needs code inspection and a rewrite of the reward/state description before the learning claim is fully reproducible.","tokens_in":27666,"tokens_out":4986,"would_cite":true,"duration_ms":52159,"reading_group":"maybe","serious_thinker":"yes","would_accept_peer_review":true},"rs_alignment":null,"lean_confirmation":null,"pith_extraction":{"msc":[],"pacs":[],"model":"deepseek-v4-flash","headline":"Reinforcement learning can select the best OpenMP scheduling algorithm at runtime, but the learning phase is costly.","keywords":["OpenMP","loop scheduling","scheduling algorithm selection","reinforcement learning","Q-learning","SARSA","load imbalance","HPC runtime"],"falsifier":"Run Q-Learn with the LT reward on a repeated loop whose execution time drifts across time steps (Mandelbrot's increasing-imbalance loop L1 is a suitable case), logging the online min/max bounds against bounds computed from the complete run. If the agent's selections deviate from the Oracle whenever the online bounds lag the true range, the reward-normalization assumption is the limiting factor; if selections stay near-optimal, the assumption holds.","tokens_in":26639,"feed_emoji":"⚙️","tokens_out":7603,"duration_ms":69252,"temperature":0.7,"pith_summary":"The paper argues that the choice of which OpenMP scheduling algorithm to use for a loop can be automated at runtime, and that machine-learned selectors can approach the performance of an oracle that already knows the best algorithm. Its experiments with six applications and three systems show that Q-learning and SARSA agents, embedded in the OpenMP runtime, learn high-performing scheduling decisions on repeated time-stepping loops. The catch is exploration: the agents must try 144 algorithm combinations before they choose, which can erase the gains on short or memory-bound loops. The reward function is decisive; rewarding low load imbalance (LIB) tends to pick algorithms with heavy overhead, while rewarding low loop time (LT) finds the best algorithm. Combining expert knowledge, in the form of a golden-ratio-based chunk parameter, with RL reduces the cost and improves performance.","feed_headline":"RL learns the best OpenMP loop scheduler—at a steep exploration cost","feed_subtitle":"Six applications and three systems show reward choice decides whether RL beats expert rules.","key_machinery":"The load-bearing mechanism is a per-loop reinforcement-learning agent placed inside the OpenMP runtime. At each execution of a repeated loop the agent chooses one of 12 scheduling algorithms from the LB4OMP portfolio (static, self-scheduling, guided, trapezoid, factoring variants, adaptive weighted factoring variants, adaptive factoring, static steal, and LLVM's auto), receives a reward computed from Eq. (11), and updates a Q-table over 144 state–action pairs using either SARSA (Eq. 9) or Q-Learn (Eq. 10). The reward is normalized by the running minimum and maximum of the measured quantity — loop execution time or load imbalance LIB — so that a result inside the observed range is neutral, below it is positive, and above it is negative. The explore-first policy forces every one of the 144 combinations to be tried before exploitation. The expert counterpart is the golden-ratio chunk parameter, $\\phi = 1.618$, which the paper uses to shrink the chunk-size interval and lower scheduling overhead, and the Oracle baseline supplies the best achievable selection against which every method is measured.","core_discovery":"On the paper's own terms, the central discovery is that model-free reinforcement learning can be made to work for online scheduling-algorithm selection in OpenMP: Q-Learn and SARSA, operating per loop over a 12-algorithm portfolio, converge to selections that match or approach the Oracle baseline once their explore-first learning phase of 144 loop instances is over. The choice of reward is not a detail; rewards based on loop execution time produce near-oracle selections, while rewards based on load-imbalance percentage (LIB) systematically favor fine-grained schedules such as self-scheduling, whose overhead destroys performance. Expert-based selection (ExhaustiveSel, ExpertSel) is cheaper but can miss the optimal algorithm on some systems, and the paper shows that the two paradigms can be combined, for example by using the expert chunk parameter with RL, to achieve better performance than either alone.","pith_inferences":["Editorial inference: warm-starting the Q-table from a prior run on the same system, which the paper names as future work, would largely erase the exploration cost and could make RL selection practical for short-running loops.","Editorial inference: the LIB-reward failure suggests a general autotuning caution — any objective that rewards balance without charging for scheduling overhead drifts toward the finest-grained schedule; a cost-aware imbalance metric that includes overhead per work request is a natural next experiment.","Editorial inference: the min/max reward normalization in Eq. (11) is an online estimation problem; on loops whose workload distribution shifts, the stored bounds may go stale, and an adaptive-bounds variant would directly test whether reward normalization is the true bottleneck.","Editorial inference: if the expChunk-plus-RL combination generalizes beyond the six applications tested, the practical recipe for HPC users is to let expert-derived parameters guide exploration and let RL fine-tune the final algorithm choice, rather than using either approach alone."],"forward_implications":["Per-loop runtime selection can replace a single hard-coded schedule: a loop whose workload changes across time steps can switch scheduling algorithms as the execution evolves.","On time-stepping applications with enough repetitions, RL-based selectors can match or approach the Oracle's choice, so applications can approach best-in-portfolio performance without prior benchmarking.","Rewarding low load imbalance (LIB) misleads the learner into fine-grained schedules with heavy overhead, so future selectors should optimize loop time or a cost-aware proxy rather than balance alone.","The 144-instance explore-first phase makes RL selection worthwhile only when loops repeat many times; for short runs, expert rules or pre-trained Q-tables are needed.","The same per-loop selection mechanism can be extended to MPI-level scheduling whenever a portfolio of distributed-memory scheduling algorithms exists, as the paper anticipates."],"supporting_citations":[{"why":"It supplies the expert-based selection methods (RandomSel, ExhaustiveSel, ExpertSel) and the golden-ratio expChunk parameter that the paper compares against and combines with RL.","marker":"[25]"},{"why":"It provides the LB4OMP library and the 12-algorithm scheduling portfolio every selection method draws from.","marker":"[26]"},{"why":"It defines Q-Learn, one of the two model-free RL agents used for selection.","marker":"[43]"},{"why":"It supplies the SARSA update rule and the RL notation the agents use.","marker":"[38]"},{"why":"It defines the percent load-imbalance metric LIB used by expert rules and as one of the two reward types.","marker":"[16]"},{"why":"It frames the algorithm selection problem that this paper applies to OpenMP scheduling.","marker":"[35]"},{"why":"It defines adaptive factoring, a portfolio algorithm whose overhead behavior matters for the reward comparison.","marker":"[4]"},{"why":"It defines the adaptive weighted factoring variants included in the portfolio.","marker":"[5]"},{"why":"It defines self-scheduling, the fine-grained schedule that wins under LIB rewards but carries the highest overhead.","marker":"[30]"}],"fun_headline_variants":["RL finds best OpenMP scheduler after steep exploration cost","Reward function makes or breaks RL for OpenMP scheduling selection","Hybrid expert+RL OpenMP scheduling beats pure strategies","Q-Learn and SARSA match oracle after 144 OpenMP loop trials","OpenMP scheduling: RL viable but exploration is expensive"],"cache_read_input_tokens":3200,"weakest_assumption_plain":"The RL results rest on the reward normalization in Eq. (11): the running minimum and maximum of past loop execution times (or LIB values) are assumed to provide stable relative rewards, but the paper does not specify how these bounds are initialized or updated when a loop's behavior changes; if the bounds are unrepresentative during early or non-stationary executions, the Q-table updates are distorted.","fun_headline_variants_meta":{"raw":{"variants":["RL finds best OpenMP scheduler after steep exploration cost","Reward function makes or breaks RL for OpenMP scheduling selection","Hybrid expert+RL OpenMP scheduling beats pure strategies","Q-Learn and SARSA match oracle after 144 OpenMP loop trials","OpenMP scheduling: RL viable but exploration is expensive"]},"model":"deepseek-v4-flash","effort":"low","cost_usd":0.000544,"raw_usage":{"total_tokens":2610,"prompt_tokens":956,"completion_tokens":1654,"prompt_tokens_details":{"cached_tokens":384},"prompt_cache_hit_tokens":384,"prompt_cache_miss_tokens":572,"completion_tokens_details":{"reasoning_tokens":1569}},"tokens_in":572,"tokens_out":1654,"duration_ms":13470,"temperature":1.0,"reasoning_tokens":1569,"cache_read_input_tokens":384,"cache_creation_input_tokens":0},"cache_creation_input_tokens":0},"created_at":"2026-08-15T17:45:26.454768+00:00","model_set":{"reader":"deepseek-v4-flash"},"falsifier":"Run Q-Learn with the LT reward on a repeated loop whose execution time drifts across time steps (Mandelbrot's increasing-imbalance loop L1 is a suitable case), logging the online min/max bounds against bounds computed from the complete run. If the agent's selections deviate from the Oracle whenever the online bounds lag the true range, the reward-normalization assumption is the limiting factor; if selections stay near-optimal, the assumption holds.","supporting_citations":[{"cited_title":"H., Eleliemy, A., and Ciorba, F","cited_arxiv_id":null,"evidence_quote":"It supplies the expert-based selection methods (RandomSel, ExhaustiveSel, ExpertSel) and the golden-ratio expChunk parameter that the paper compares against and combines with RL."},{"cited_title":"H., Eleliemy, A., Mohammed, A., and Ciorba, F","cited_arxiv_id":null,"evidence_quote":"It provides the LB4OMP library and the 12-algorithm scheduling portfolio every selection method draws from."},{"cited_title":"J., and Dayan, P","cited_arxiv_id":null,"evidence_quote":"It defines Q-Learn, one of the two model-free RL agents used for selection."},{"cited_title":"S., and Barto, A","cited_arxiv_id":null,"evidence_quote":"It supplies the SARSA update rule and the RL notation the agents use."},{"cited_title":"Detecting application load imbalance on high end massively parallel systems","cited_arxiv_id":null,"evidence_quote":"It defines the percent load-imbalance metric LIB used by expert rules and as one of the two reward types."},{"cited_title":null,"cited_arxiv_id":null,"evidence_quote":"It frames the algorithm selection problem that this paper applies to OpenMP scheduling."},{"cited_title":"Adaptive Factoring: A Dynamic Scheduling Method Tuned to the Rate of Weight Changes","cited_arxiv_id":null,"evidence_quote":"It defines adaptive factoring, a portfolio algorithm whose overhead behavior matters for the reward comparison."},{"cited_title":"On the Scalability of Dynamic Scheduling Scientific Applications with Adaptive Weighted Factoring","cited_arxiv_id":null,"evidence_quote":"It defines the adaptive weighted factoring variants included in the portfolio."},{"cited_title":"Processor Self-Scheduling for Multiple-Nested Parallel Loops","cited_arxiv_id":null,"evidence_quote":"It defines self-scheduling, the fine-grained schedule that wins under LIB rewards but carries the highest overhead."}],"review_version":1}