From 95e32dbc5b66eff711d6122088ed29e67c239b87 Mon Sep 17 00:00:00 2001 From: Sven van Haastregt Date: Wed, 14 Dec 2011 10:55:18 +0100 Subject: [PATCH] add Feautrier's scheduling algorithm Offer Feautrier's algorithm as an alternative to isl's default scheduling algorithm. The schedule is extended to a full-dimensional schedule. To select the scheduling algorithm to use, we introduce isl option schedule-algorithm. Signed-off-by: Sven van Haastregt Signed-off-by: Sven Verdoolaege --- doc/user.pod | 30 +++++++++++++++++++------- include/isl/options.h | 5 +++++ isl_options.c | 14 +++++++++++++ isl_options_private.h | 1 + isl_schedule.c | 56 +++++++++++++++++++++++++++++++++++++++++++++++-- isl_test.c | 58 +++++++++++++++++++++++++++++++++++++++------------ 6 files changed, 142 insertions(+), 22 deletions(-) diff --git a/doc/user.pod b/doc/user.pod index 76b6e01e..7384bf7f 100644 --- a/doc/user.pod +++ b/doc/user.pod @@ -4035,16 +4035,22 @@ B The following function can be used to compute a schedule -for a union of domains. The generated schedule respects -all C dependences. That is, all dependence distances -over these dependences in the scheduled space are lexicographically -positive. The generated schedule schedule also tries to minimize -the dependence distances over C dependences. +for a union of domains. +By default, the algorithm used to construct the schedule is similar +to that of C. +Alternatively, Feautrier's multi-dimensional scheduling algorithm can +be selected. +The generated schedule respects all C dependences. +That is, all dependence distances over these dependences in the +scheduled space are lexicographically positive. +The default algorithm tries to minimize the dependence distances over +C dependences. Moreover, it tries to obtain sequences (bands) of schedule dimensions for groups of domains where the dependence distances have only non-negative values. -The algorithm used to construct the schedule is similar to that -of C. +When using Feautrier's algorithm, the C dependence +distances are only minimized during the extension to a +full-dimensional schedule. #include __isl_give isl_schedule *isl_union_set_compute_schedule( @@ -4144,6 +4150,10 @@ A representation of the band can be printed using isl_ctx *ctx, int val); int isl_options_get_schedule_split_parallel( isl_ctx *ctx); + int isl_options_set_schedule_algorithm( + isl_ctx *ctx, int val); + int isl_options_get_schedule_algorithm( + isl_ctx *ctx); =over @@ -4179,6 +4189,12 @@ the scheduling rows for all nodes in the graphs are the same. The constant term is then placed in a separate band and the linear part is simplified. +=item * schedule_algorithm + +Selects the scheduling algorithm to be used. +Available scheduling algorithms are C +and C. + =back =head2 Parametric Vertex Enumeration diff --git a/include/isl/options.h b/include/isl/options.h index 1c14b19f..8c9ec4da 100644 --- a/include/isl/options.h +++ b/include/isl/options.h @@ -35,6 +35,11 @@ int isl_options_get_on_error(isl_ctx *ctx); int isl_options_set_gbr_only_first(isl_ctx *ctx, int val); int isl_options_get_gbr_only_first(isl_ctx *ctx); +#define ISL_SCHEDULE_ALGORITHM_ISL 0 +#define ISL_SCHEDULE_ALGORITHM_FEAUTRIER 1 +int isl_options_set_schedule_algorithm(isl_ctx *ctx, int val); +int isl_options_get_schedule_algorithm(isl_ctx *ctx); + #if defined(__cplusplus) } #endif diff --git a/isl_options.c b/isl_options.c index f43e0bee..ffb5b86c 100644 --- a/isl_options.c +++ b/isl_options.c @@ -71,6 +71,12 @@ static struct isl_arg_choice on_error[] = { {0} }; +static struct isl_arg_choice isl_schedule_algorithm_choice[] = { + {"isl", ISL_SCHEDULE_ALGORITHM_ISL}, + {"feautrier", ISL_SCHEDULE_ALGORITHM_FEAUTRIER}, + {0} +}; + static struct isl_arg_flags bernstein_recurse[] = { {"none", ISL_BERNSTEIN_FACTORS | ISL_BERNSTEIN_INTERVALS, 0}, {"factors", ISL_BERNSTEIN_FACTORS | ISL_BERNSTEIN_INTERVALS, @@ -140,6 +146,9 @@ ISL_ARG_BOOL(struct isl_options, schedule_maximize_band_depth, 0, ISL_ARG_BOOL(struct isl_options, schedule_split_parallel, 0, "schedule-split-parallel", 1, "split non-tilable bands with parallel schedules") +ISL_ARG_CHOICE(struct isl_options, schedule_algorithm, 0, + "schedule-algorithm", isl_schedule_algorithm_choice, + ISL_SCHEDULE_ALGORITHM_ISL, "scheduling algorithm to use") ISL_ARG_VERSION(print_version) ISL_ARGS_END @@ -179,3 +188,8 @@ ISL_CTX_SET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, schedule_outer_zero_distance) ISL_CTX_GET_BOOL_DEF(isl_options, struct isl_options, isl_options_args, schedule_outer_zero_distance) + +ISL_CTX_SET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, + schedule_algorithm) +ISL_CTX_GET_CHOICE_DEF(isl_options, struct isl_options, isl_options_args, + schedule_algorithm) diff --git a/isl_options_private.h b/isl_options_private.h index 6cbd8823..5169096c 100644 --- a/isl_options_private.h +++ b/isl_options_private.h @@ -50,6 +50,7 @@ struct isl_options { int schedule_outer_zero_distance; int schedule_maximize_band_depth; int schedule_split_parallel; + unsigned schedule_algorithm; }; #endif diff --git a/isl_schedule.c b/isl_schedule.c index 8e8a35c3..d7ef8fcc 100644 --- a/isl_schedule.c +++ b/isl_schedule.c @@ -2326,6 +2326,47 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) return compute_next_band(ctx, graph); } +/* Are there any validity edges in the graph? + */ +static int has_validity_edges(struct isl_sched_graph *graph) +{ + int i; + + for (i = 0; i < graph->n_edge; ++i) + if (graph->edge[i].validity) + return 1; + + return 0; +} + +/* Should we apply a Feautrier step? + * That is, did the user request the Feautrier algorithm and are + * there any validity dependences (left)? + */ +static int need_feautrier_step(isl_ctx *ctx, struct isl_sched_graph *graph) +{ + if (ctx->opt->schedule_algorithm != ISL_SCHEDULE_ALGORITHM_FEAUTRIER) + return 0; + + return has_validity_edges(graph); +} + +/* Compute a schedule for a connected dependence graph using Feautrier's + * multi-dimensional scheduling algorithm. + * The original algorithm is described in [1]. + * The main idea is to minimize the number of scheduling dimensions, by + * trying to satisfy as many dependences as possible per scheduling dimension. + * + * [1] P. Feautrier, Some Efficient Solutions to the Affine Scheduling + * Problem, Part II: Multi-Dimensional Time. + * In Intl. Journal of Parallel Programming, 1992. + */ +static int compute_schedule_wcc_feautrier(isl_ctx *ctx, + struct isl_sched_graph *graph) +{ + return carry_dependences(ctx, graph); +} + /* Compute a schedule for a connected dependence graph. * We try to find a sequence of as many schedule rows as possible that result * in non-negative dependence distances (independent of the previous rows @@ -2338,6 +2379,10 @@ static int carry_dependences(isl_ctx *ctx, struct isl_sched_graph *graph) * - try to carry as many dependences as possible and continue with the next * band * + * If Feautrier's algorithm is selected, we first recursively try to satisfy + * as many validity dependences as possible. When all validity dependences + * are satisfied we extend the schedule to a full-dimensional schedule. + * * If we manage to complete the schedule, we finish off by topologically * sorting the statements based on the remaining dependences. * @@ -2357,6 +2402,9 @@ static int compute_schedule_wcc(isl_ctx *ctx, struct isl_sched_graph *graph) if (compute_maxvar(graph) < 0) return -1; + if (need_feautrier_step(ctx, graph)) + return compute_schedule_wcc_feautrier(ctx, graph); + if (ctx->opt->schedule_outer_zero_distance) force_zero = 1; @@ -2457,8 +2505,12 @@ static int compute_schedule(isl_ctx *ctx, struct isl_sched_graph *graph) } /* Compute a schedule for the given union of domains that respects - * all the validity dependences and tries to minimize the dependence - * distances over the proximity dependences. + * all the validity dependences. + * If the default isl scheduling algorithm is used, it tries to minimize + * the dependence distances over the proximity dependences. + * If Feautrier's scheduling algorithm is used, the proximity dependence + * distances are only minimized during the extension to a full-dimensional + * schedule. */ __isl_give isl_schedule *isl_union_set_compute_schedule( __isl_take isl_union_set *domain, diff --git a/isl_test.c b/isl_test.c index 2b21331c..215c0144 100644 --- a/isl_test.c +++ b/isl_test.c @@ -2036,27 +2036,24 @@ int test_one_schedule(isl_ctx *ctx, const char *d, const char *w, return 0; } -int test_special_schedule(isl_ctx *ctx) +int test_special_schedule(isl_ctx *ctx, const char *domain, + const char *validity, const char *proximity, const char *expected_sched) { - const char *str; isl_union_set *dom; - isl_union_map *empty; isl_union_map *dep; + isl_union_map *prox; isl_union_map *sched1, *sched2; isl_schedule *schedule; int equal; - str = "{ S[i,j] : 0 <= i <= 10 }"; - dom = isl_union_set_read_from_str(ctx, str); - str = "{ S[i,j] -> S[i+1,j] : 0 <= i,j <= 10 }"; - dep = isl_union_map_read_from_str(ctx, str); - empty = isl_union_map_read_from_str(ctx, "{}"); - schedule = isl_union_set_compute_schedule(dom, empty, dep); + dom = isl_union_set_read_from_str(ctx, domain); + dep = isl_union_map_read_from_str(ctx, validity); + prox = isl_union_map_read_from_str(ctx, proximity); + schedule = isl_union_set_compute_schedule(dom, dep, prox); sched1 = isl_schedule_get_map(schedule); isl_schedule_free(schedule); - str = "{ S[i, j] -> [j, i] }"; - sched2 = isl_union_map_read_from_str(ctx, str); + sched2 = isl_union_map_read_from_str(ctx, expected_sched); equal = isl_union_map_is_equal(sched1, sched2); isl_union_map_free(sched1); @@ -2073,7 +2070,7 @@ int test_special_schedule(isl_ctx *ctx) int test_schedule(isl_ctx *ctx) { - const char *D, *W, *R, *S; + const char *D, *W, *R, *V, *P, *S; /* Jacobi */ D = "[T,N] -> { S1[t,i] : 1 <= t <= T and 2 <= i <= N - 1 }"; @@ -2240,7 +2237,42 @@ int test_schedule(isl_ctx *ctx) return -1; ctx->opt->schedule_outer_zero_distance = 0; - return test_special_schedule(ctx); + D = "{ S_0[i, j] : i >= 1 and i <= 10 and j >= 1 and j <= 8 }"; + V = "{ S_0[i, j] -> S_0[i, 1 + j] : i >= 1 and i <= 10 and " + "j >= 1 and j <= 7;" + "S_0[i, j] -> S_0[1 + i, j] : i >= 1 and i <= 9 and " + "j >= 1 and j <= 8 }"; + P = "{ }"; + S = "{ S_0[i, j] -> [i + j, j] }"; + ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER; + if (test_special_schedule(ctx, D, V, P, S) < 0) + return -1; + ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL; + + /* Fig. 1 from Feautrier's "Some Efficient Solutions..." pt. 2, 1992 */ + D = "[N] -> { S_0[i, j] : i >= 0 and i <= -1 + N and " + "j >= 0 and j <= -1 + i }"; + V = "[N] -> { S_0[i, j] -> S_0[i, 1 + j] : j <= -2 + i and " + "i <= -1 + N and j >= 0;" + "S_0[i, -1 + i] -> S_0[1 + i, 0] : i >= 1 and " + "i <= -2 + N }"; + P = "{ }"; + S = "{ S_0[i, j] -> [i, j] }"; + ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER; + if (test_special_schedule(ctx, D, V, P, S) < 0) + return -1; + ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL; + + /* Test both algorithms on a case with only proximity dependences. */ + D = "{ S[i,j] : 0 <= i <= 10 }"; + V = "{ }"; + P = "{ S[i,j] -> S[i+1,j] : 0 <= i,j <= 10 }"; + S = "{ S[i, j] -> [j, i] }"; + ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_FEAUTRIER; + if (test_special_schedule(ctx, D, V, P, S) < 0) + return -1; + ctx->opt->schedule_algorithm = ISL_SCHEDULE_ALGORITHM_ISL; + return test_special_schedule(ctx, D, V, P, S); } int test_plain_injective(isl_ctx *ctx, const char *str, int injective) -- 2.11.4.GIT