From 990ad28a4356f5743bed503fbdcb7e85747f727f Mon Sep 17 00:00:00 2001 From: Tobias Grosser Date: Mon, 12 Dec 2011 17:07:18 +0100 Subject: [PATCH] add option to bound the constant scheduling coefficients If larger coefficients appear as part of the input dependences, the schedule calculation can take a very long time. We observed that the main overhead in this calculation is due to optimizing the constant coefficients. They are misused to increase locality by merging several unrelated dimensions into a single dimension. This unwanted optimization increases the complexity of the code and slows down the generated code. We introduce a new option that bounds the values in the constant dimension by a user defined value. If the right value is choosen, costly overoptimization can be prevented. This solution works, but requires the user to specify the value by which the constants are bound. For the moment, this is our best solution, but we hope to to find a more generic one later on. Signed-off-by: Tobias Grosser Signed-off-by: Sven Verdoolaege --- doc/user.pod | 12 ++++++++++++ include/isl/schedule.h | 3 +++ isl_options.c | 9 +++++++++ isl_options_private.h | 1 + isl_schedule.c | 17 +++++++++++++++++ 5 files changed, 42 insertions(+) diff --git a/doc/user.pod b/doc/user.pod index 25548f8..76b6e01 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -4128,6 +4128,10 @@ A representation of the band can be printed using =head3 Options #include + int isl_options_set_schedule_max_constant_term( + isl_ctx *ctx, int val); + int isl_options_get_schedule_max_constant_term( + isl_ctx *ctx); int isl_options_set_schedule_maximize_band_depth( isl_ctx *ctx, int val); int isl_options_get_schedule_maximize_band_depth( @@ -4144,6 +4148,14 @@ A representation of the band can be printed using =over +=item * max_constant_term + +This option enforces that the constant coefficients in the calculated schedule +are not larger than the maximal constant term. This option can significantly +increase the speed of the scheduling calculation and may also prevent fusing of +unrelated dimensions. A value of -1 means that this option does not introduce +bounds on the constant coefficients. + =item * maximize_band_depth If this option is set, we do not split bands at the point diff --git a/include/isl/schedule.h b/include/isl/schedule.h index 4ff211d..3770b7a 100644 --- a/include/isl/schedule.h +++ b/include/isl/schedule.h @@ -12,6 +12,9 @@ extern "C" { struct isl_schedule; typedef struct isl_schedule isl_schedule; +int isl_options_set_schedule_max_constant_term(isl_ctx *ctx, int val); +int isl_options_get_schedule_max_constant_term(isl_ctx *ctx); + int isl_options_set_schedule_maximize_band_depth(isl_ctx *ctx, int val); int isl_options_get_schedule_maximize_band_depth(isl_ctx *ctx); diff --git a/isl_options.c b/isl_options.c index fd342f0..f43e0be 100644 --- a/isl_options.c +++ b/isl_options.c @@ -124,6 +124,10 @@ ISL_ARG_BOOL(struct isl_options, pip_symmetry, 0, "pip-symmetry", 1, "detect simple symmetries in PIP input") ISL_ARG_CHOICE(struct isl_options, convex, 0, "convex-hull", \ convex, ISL_CONVEX_HULL_WRAP, "convex hull algorithm to use") +ISL_ARG_INT(struct isl_options, schedule_max_constant_term, 0, + "schedule-max-constant-term", "limit", -1, "Only consider schedules " + "where the coefficients of the constant dimension do not exceed " + ". A value of -1 allows arbitrary coefficients.") ISL_ARG_BOOL(struct isl_options, schedule_parametric, 0, "schedule-parametric", 1, "construct possibly parametric schedules") ISL_ARG_BOOL(struct isl_options, schedule_outer_zero_distance, 0, @@ -156,6 +160,11 @@ ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, gbr_only_first) +ISL_CTX_SET_INT_DEF(isl_options, struct isl_options, isl_options_args, + schedule_max_constant_term) +ISL_CTX_GET_INT_DEF(isl_options, struct isl_options, isl_options_args, + schedule_max_constant_term) + ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, schedule_maximize_band_depth) ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, diff --git a/isl_options_private.h b/isl_options_private.h index f49077c..6cbd882 100644 --- a/isl_options_private.h +++ b/isl_options_private.h @@ -45,6 +45,7 @@ struct isl_options { #define ISL_CONVEX_HULL_FM 1 int convex; + int schedule_max_constant_term; int schedule_parametric; int schedule_outer_zero_distance; int schedule_maximize_band_depth; diff --git a/isl_schedule.c b/isl_schedule.c index 9f261e0..8e8a35c 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -1139,6 +1139,9 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph, int parametric; int param_pos; int n_eq, n_ineq; + int max_constant_term; + + max_constant_term = ctx->opt->schedule_max_constant_term; parametric = ctx->opt->schedule_parametric; nparam = isl_space_dim(graph->node[0].dim, isl_dim_param); @@ -1158,6 +1161,9 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph, dim = isl_space_set_alloc(ctx, 0, total); isl_basic_set_free(graph->lp); n_eq += 2 + parametric + force_zero; + if (max_constant_term != -1) + n_ineq += graph->n; + graph->lp = isl_basic_set_alloc_space(dim, 0, n_eq, n_ineq); k = isl_basic_set_alloc_equality(graph->lp); @@ -1204,6 +1210,17 @@ static int setup_lp(isl_ctx *ctx, struct isl_sched_graph *graph, isl_int_set_si(graph->lp->eq[k][pos + j], 1); } + if (max_constant_term != -1) + for (i = 0; i < graph->n; ++i) { + struct isl_sched_node *node = &graph->node[i]; + k = isl_basic_set_alloc_inequality(graph->lp); + if (k < 0) + return -1; + isl_seq_clr(graph->lp->ineq[k], 1 + total); + isl_int_set_si(graph->lp->ineq[k][1 + node->start], -1); + isl_int_set_si(graph->lp->ineq[k][0], max_constant_term); + } + if (add_all_validity_constraints(graph) < 0) return -1; if (add_all_proximity_constraints(graph) < 0) -- 2.7.4