aboutsummaryrefslogtreecommitdiff
diff options
context:
space:
mode:
authorsinanmohd <sinan@sinanmohd.com>2024-07-24 09:53:41 +0530
committersinanmohd <sinan@sinanmohd.com>2024-07-24 17:51:10 +0530
commit42dcde08c51a781c22613af194f95ef980d03a5b (patch)
tree0fe9729efeae8a658c749a050e808764ac4948cd
parent9d292f7e22e1af751918a5ed002a90b69adf9545 (diff)
solver_highs: init
-rw-r--r--include/evanix.h1
-rw-r--r--include/solver_highs.h4
-rw-r--r--src/evanix.c67
-rw-r--r--src/jobid.c5
-rw-r--r--src/meson.build1
-rw-r--r--src/solver_highs.c216
6 files changed, 274 insertions, 20 deletions
diff --git a/include/evanix.h b/include/evanix.h
index 6832777..34d4918 100644
--- a/include/evanix.h
+++ b/include/evanix.h
@@ -12,6 +12,7 @@ struct evanix_opts_t {
bool solver_report;
bool close_unused_fd;
bool check_cache_status;
+ bool break_evanix;
char *system;
uint32_t max_build;
int (*solver)(struct job **, struct job_clist *, int32_t);
diff --git a/include/solver_highs.h b/include/solver_highs.h
new file mode 100644
index 0000000..89090f9
--- /dev/null
+++ b/include/solver_highs.h
@@ -0,0 +1,4 @@
+#include <jobs.h>
+#include <stdint.h>
+
+int solver_highs(struct job **job, struct job_clist *q, int32_t resources);
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);
+}