diff options
Diffstat (limited to 'src')
| -rw-r--r-- | src/evanix.c | 67 | ||||
| -rw-r--r-- | src/jobid.c | 5 | ||||
| -rw-r--r-- | src/meson.build | 1 | ||||
| -rw-r--r-- | src/solver_highs.c | 216 |
4 files changed, 269 insertions, 20 deletions
diff --git a/src/evanix.c b/src/evanix.c index c75bd70..293c8fe 100644 --- a/src/evanix.c +++ b/src/evanix.c @@ -1,11 +1,13 @@ #include <getopt.h> #include <stdlib.h> #include <string.h> +#include <errno.h> #include "build.h" #include "evanix.h" #include "queue.h" #include "solver_greedy.h" +#include "solver_highs.h" #include "util.h" static const char usage[] = @@ -17,11 +19,12 @@ static const char usage[] = "built.\n" " -s, --system System to build for.\n" " -m, --max-build Max number of builds.\n" + " -b, --break-evanix Enable experimental features.\n" " -r, --solver-report Print solver report.\n" " -p, --pipelined <bool> Use evanix build pipeline.\n" " -l, --check_cache-status <bool> Perform cache locality check.\n" " -c, --close-unused-fd <bool> Close stderr on exec.\n" - " -k, --solver greedy Solver to use.\n" + " -k, --solver highs|greedy Solver to use.\n" "\n"; struct evanix_opts_t evanix_opts = { @@ -34,6 +37,7 @@ struct evanix_opts_t evanix_opts = { .solver_report = false, .check_cache_status = true, .solver = solver_greedy, + .break_evanix = false, }; static int evanix_build_thread_create(struct build_thread *build_thread); @@ -122,7 +126,7 @@ out_free: return ret; } -int main(int argc, char *argv[]) +int opts_read(struct evanix_opts_t *opts, char **expr, int argc, char *argv[]) { extern int optind, opterr, optopt; extern char *optarg; @@ -132,6 +136,7 @@ int main(int argc, char *argv[]) {"help", no_argument, NULL, 'h'}, {"flake", no_argument, NULL, 'f'}, {"dry-run", no_argument, NULL, 'd'}, + {"break-evanix", no_argument, NULL, 'b'}, {"solver", required_argument, NULL, 'k'}, {"system", required_argument, NULL, 's'}, {"solver-report", no_argument, NULL, 'r'}, @@ -147,23 +152,28 @@ int main(int argc, char *argv[]) switch (c) { case 'h': printf("%s", usage); - exit(EXIT_SUCCESS); + return -EINVAL; break; case 'f': - evanix_opts.isflake = true; + opts->isflake = true; + break; + case 'b': + opts->break_evanix = true; break; case 'd': - evanix_opts.isdryrun = true; + opts->isdryrun = true; break; case 's': - evanix_opts.system = optarg; + opts->system = optarg; break; case 'r': - evanix_opts.solver_report = true; + opts->solver_report = true; break; case 'k': if (!strcmp(optarg, "greedy")) { - evanix_opts.solver = solver_greedy; + opts->solver = solver_greedy; + } else if (!strcmp(optarg, "highs")) { + opts->solver = solver_highs; } else { fprintf(stderr, "option -%c has an invalid solver " @@ -171,7 +181,7 @@ int main(int argc, char *argv[]) "Try 'evanix --help' for more " "information.\n", c); - exit(EXIT_FAILURE); + return -EINVAL; } break; case 'm': @@ -183,10 +193,10 @@ int main(int argc, char *argv[]) "Try 'evanix --help' for more " "information.\n", c); - exit(EXIT_FAILURE); + return -EINVAL; } - evanix_opts.max_build = ret; + opts->max_build = ret; break; case 'p': ret = atob(optarg); @@ -196,10 +206,10 @@ int main(int argc, char *argv[]) "Try 'evanix --help' for more " "information.\n", c); - exit(EXIT_FAILURE); + return -EINVAL; } - evanix_opts.ispipelined = ret; + opts->ispipelined = ret; break; case 'c': ret = atob(optarg); @@ -209,10 +219,10 @@ int main(int argc, char *argv[]) "Try 'evanix --help' for more " "information.\n", c); - exit(EXIT_FAILURE); + return -EINVAL; } - evanix_opts.close_unused_fd = ret; + opts->close_unused_fd = ret; break; case 'l': ret = atob(optarg); @@ -222,24 +232,43 @@ int main(int argc, char *argv[]) "Try 'evanix --help' for more " "information.\n", c); - exit(EXIT_FAILURE); + return -EINVAL; } - evanix_opts.check_cache_status = ret; + opts->check_cache_status = ret; break; default: fprintf(stderr, "Try 'evanix --help' for more information.\n"); - exit(EXIT_FAILURE); + return -EINVAL; break; } } if (optind != argc - 1) { fprintf(stderr, "evanix: invalid expr operand\n" "Try 'evanix --help' for more information.\n"); - exit(EXIT_FAILURE); + return -EINVAL; + } + + if (opts->solver == solver_highs && !opts->break_evanix) { + fprintf(stderr, + "Running --solver=highs without --break-evanix\n"); + return -EINVAL; } + *expr = argv[optind]; + return 0; +} + +int main(int argc, char *argv[]) +{ + char *expr; + int ret; + + ret = opts_read(&evanix_opts, &expr, argc, argv); + if (ret < 0) + exit(EXIT_FAILURE); + ret = evanix(argv[optind]); if (ret < 0) exit(EXIT_FAILURE); diff --git a/src/jobid.c b/src/jobid.c index d1ca8ab..07f3ea5 100644 --- a/src/jobid.c +++ b/src/jobid.c @@ -3,8 +3,8 @@ #include <stdlib.h> #include <string.h> -#include "jobs.h" #include "jobid.h" +#include "jobs.h" #include "util.h" static int dag_id_assign(struct job *j, struct jobid *jobid); @@ -42,6 +42,9 @@ static int dag_id_assign(struct job *j, struct jobid *jobid) void jobid_free(struct jobid *jid) { + if (jid == NULL) + return; + free(jid->jobs); free(jid); } diff --git a/src/meson.build b/src/meson.build index d4ccec2..b0dac71 100644 --- a/src/meson.build +++ b/src/meson.build @@ -9,6 +9,7 @@ e = executable( 'build.c', 'jobid.c', 'solver_greedy.c', + 'solver_highs.c', ], include_directories: evanix_inc, diff --git a/src/solver_highs.c b/src/solver_highs.c new file mode 100644 index 0000000..722fe27 --- /dev/null +++ b/src/solver_highs.c @@ -0,0 +1,216 @@ +#include <assert.h> +#include <errno.h> +#include <highs/interfaces/highs_c_api.h> +#include <math.h> +#include <stdio.h> +#include <stdlib.h> + +#include "jobid.h" +#include "solver_highs.h" +#include "util.h" + +static int solver_highs_unwrapped(double *solution, struct job_clist *q, + int32_t resources, struct jobid *jobid) +{ + HighsInt precedence_index[2]; + double precedence_value[2]; + struct job *j; + int ret; + + double *col_profit = NULL; + double *col_lower = NULL; + double *col_upper = NULL; + HighsInt *integrality = NULL; + void *highs = NULL; + + HighsInt *constraint_index = NULL; + double *constraint_value = NULL; + + /* set objective */ + col_profit = calloc(jobid->filled, sizeof(*col_profit)); + if (col_profit == NULL) { + print_err("%s", strerror(errno)); + return -errno; + } + for (size_t i = 0; i < jobid->filled; i++) { + if (jobid->jobs[i]->scheduled) + col_profit[i] = 1.0; + } + + col_lower = calloc(jobid->filled, sizeof(*col_lower)); + if (col_lower == NULL) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_col_profit; + } + + col_upper = malloc(jobid->filled * sizeof(*col_lower)); + if (col_upper == NULL) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_col_profit; + } + for (size_t i = 0; i < jobid->filled; i++) + col_upper[i] = 1.0; + + integrality = malloc(jobid->filled * sizeof(*integrality)); + for (size_t i = 0; i < jobid->filled; i++) + integrality[i] = 1; + + highs = Highs_create(); + ret = Highs_setBoolOptionValue(highs, "output_flag", 1); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + ret = Highs_addCols(highs, jobid->filled, col_profit, col_lower, + col_upper, 0, NULL, NULL, NULL); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + + /* set resource constraint */ + constraint_index = malloc(jobid->filled * sizeof(*constraint_index)); + if (constraint_index == NULL) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_col_profit; + } + for (size_t i = 0; i < jobid->filled; i++) + constraint_index[i] = i; + + constraint_value = malloc(jobid->filled * sizeof(*constraint_value)); + if (constraint_value == NULL) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_col_profit; + } + for (size_t i = 0; i < jobid->filled; i++) + constraint_value[i] = 1.0; + + ret = Highs_addRow(highs, 0, resources, jobid->filled + 1, + constraint_index, constraint_value); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + + /* set precedance constraints */ + CIRCLEQ_FOREACH (j, q, clist) { + for (size_t i = 0; i < j->deps_filled; j++) { + /* follow the CSR matrix structure */ + if (j->id < j->deps[i]->id) { + precedence_index[0] = j->id; + precedence_index[1] = j->deps[i]->id; + precedence_value[0] = 1; + precedence_value[1] = -1; + } else { + precedence_index[0] = j->deps[i]->id; + precedence_index[1] = j->id; + precedence_value[0] = -1; + precedence_value[1] = 1; + } + + ret = Highs_addRow(highs, -INFINITY, 0, 2, + precedence_index, precedence_value); + } + } + + /* run milp solver */ + ret = Highs_changeObjectiveSense(highs, kHighsObjSenseMaximize); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + ret = Highs_changeColsIntegralityByMask(highs, integrality, + integrality); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + ret = Highs_run(highs); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + ret = Highs_getSolution(highs, solution, NULL, NULL, NULL); + if (ret != kHighsStatusOk) { + print_err("%s", "highs did not return kHighsStatusOk"); + ret = -EPERM; + goto out_free_col_profit; + } + +out_free_col_profit: + free(col_profit); + free(col_lower); + free(col_upper); + free(integrality); + free(constraint_value); + free(constraint_index); + + return ret; +} + +static int job_get(struct job **job, struct job_clist *q) +{ + struct job *j; + + CIRCLEQ_FOREACH (j, q, clist) { + if (j->stale) + continue; + + *job = j; + return 0; + } + + print_err("%s", "empty queue"); + return -ESRCH; +} + +int solver_highs(struct job **job, struct job_clist *q, int32_t resources) +{ + static bool solved = false; + struct jobid *jobid = NULL; + double *solution = NULL; + int ret = 0; + + if (solved) + goto out_free_jobid; + + ret = jobid_init(q, &jobid); + if (ret < 0) + return ret; + + solution = malloc(jobid->filled * sizeof(*solution)); + if (solution == NULL) { + print_err("%s", strerror(errno)); + ret = -errno; + goto out_free_jobid; + } + + ret = solver_highs_unwrapped(solution, q, resources, jobid); + if (ret < 0) + goto out_free_jobid; + + for (size_t i = 0; i < jobid->size; i++) { + if (solution[i] == 0.0) + job_stale_set(jobid->jobs[i]); + } + + solved = true; +out_free_jobid: + jobid_free(jobid); + free(solution); + + if (ret < 0) + return ret; + else + return job_get(job, q); +} |