/* * config.c * * Created on: 03/11/2014 * Author: Pedro */ #include "config.h" #include #include #include #include #include #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) #include #define X_OK 1 /* execute permission - unsupported in windows*/ #else #include #endif #include "bitmaps.h" #include "devices.h" #include "variables.h" #include "kernels/cl_constraints.h" label_heur LABEL_MODE_D = INPUT_ORDER; // argument indicating the default mode for selecting the variable to label assign_heur ASSIGN_MODE_D = INDOMAIN_MIN; // argument indicating the default mode for selecting the value to assign to the variable for labeling work WORK_D = ONE; // argument indicating if one solution, all solutions or optimization is default bool OPTIMIZING = false; // true if optimizing bool FINDING_ONE_SOLUTION = false; // true if finding one solution bool COUNTING_SOLUTIONS = false; // true if counting all the solutions bool PRINT_STATS = false; // True if statistic data should be collected and printed statistics STATS; // statistics data on host label_heur LABEL_MODE = DEFAULT_L; // argument indicating the mode for selecting the variable to label assign_heur ASSIGN_MODE = DEFAULT_A; // argument indicating the mode for selecting the value to assign to the variable for labeling label_heur LABEL_MODE_COM = DEFAULT_L; // argument indicating the mode for selecting the variable to label inserted in command line assign_heur ASSIGN_MODE_COM = DEFAULT_A;// argument indicating the mode for selecting the value to assign to the variable for labeling inserted in command line work WORK = DEFAULT_W; // argument indicating if one solution, all solutions or optimization is wanted opt OPT_MODE = NONE; // if optimization is to reduce a value, or to increase it bool ALL_DEVS = false; // argument if all devices should be used bool VERBOSE = false; // argument indicating if PHACT must print info bool QUIET = false; // argument indicating if PHACT must print only the number of solutions that were found, or the solution or the best solution char *CSP = NULL; // argument indicating the CSP problem to solve char *FZN_FILE_NAME = NULL; // argument indicating the name of the flatzinc file char *MZN_FILE_NAME = NULL; // argument indicating the name of the minizinc file char *DZN_FILE_NAME = NULL; // argument indicating the name of the minizinc file containing the CSP dimensions unsigned int D_MAX = 0; // maximum domain value on CSP variables (start at 0) unsigned int D_MIN = UINT32_MAX; // minimum domain value on variables CSP unsigned int CL_BITS_ = 32; // number of bits to use on devices, calculated after creating all the CSP variables in init_csp_and_d_bits() in config.c unsigned int CL_WORD_ = 0; // number of bits in one word of the bitmap use on devices, calculated after creating all the CSP variables in init_csp_and_d_bits() in config.c unsigned int CL_N_WORDS_; // number of words that compose one bitmap on the devices, calculated after creating all the CSP variables in init_csp_and_d_bits() in config.c unsigned int N_DEVS = 0; // number of devices to use unsigned int N_GPUs = 0; // requested number of GPUs to use unsigned int N_CPUs = 0; // requested number of CPUs to use unsigned int N_ACCs = 0; // requested number of ACCs to use unsigned int N_SS = 0; // optional number of sub-search spaces to create cl_uint VAL_TO_OPT; // current minimum or maximum value to optimize (not yet found) unsigned int VAR_ID_TO_OPT = 0; // ID of the variable to optimize bool PRINT_SOLUTIONS = false; // set to 1 to print all solutions (the value of each CSP variable) when using only one work-item bool PRINT_CSP = false; // set to 1 to print all CSP variables with their domains, and all the constraints with the respective variables identified bool MZN2FZN_ONLY = false; // if the MZN must be converted to FZN, but without solving the CSP bool REV = 0; // set to 1 to propagate the last labeled variable with all the remaining values before backtracking it, or 0 to not int N_VS_TO_LABEL = 0; // Number of variables marked for labeling bool BOOLEAN_VS = 0; // 1 if the CSP use boolean variables unsigned int N_VS_ORIGINAL = 0; // number of CSP variables in the model (before filtering) unsigned int N_CS_ORIGINAL = 0; // number of CSP constraints in the model (before filtering) bool CAN_USE_INTERVALS = 1; // true if variable domains are contiguous bool CS_IGNORE = USE_CS_IGNORE; // 1 to when constraint is fixed or its propagator is unable to propagate more, ignore it in the following propagations // only for bitmap domains (not for intervals) sort_heur SORT_MODE = BY_LABEL; // default heuristic to sort variables d_type DOMAIN_TYPE = BITMAP_; // domain representation to use size_t DOMAIN_SIZE; // size of the domain type used on this device __time_t init_sec; // Seconds when PHACT started __suseconds_t init_usec; // Microseconds when PHACT started bool USE_CS[N_C_TYPES]; // flags for compiling each constraint type in kernel bool USE_CS_REIFI[N_C_TYPES]; // flags for compiling reification for the constraint types that use it bool USE_NON_CS_REIFI[N_C_TYPES]; // flags for printing the stats of used constraints int *CONST_VS_ID; // to store the id of the variables that have only one value on the domain unsigned int N_VS = 256; // number of CSP variables unsigned int N_CS = 256; // number of CSP constraints unsigned int *EXP_VALUES; // Number of values expanded to achieve the required number of sub-search spaces var *VS; // Vector with all the CSP variables var *VS_LOCK; // Vector with temporary CSP variables when optimizing var *VS_LOCK_BEST; // Vector with the current best solution when optimizing var *VS_AUX; // Vector with all the CSP variables for increasing size and sorting var *VS_AUX2; // Vector with all the CSP variables for sorting constr *CS; // Vector with all the CSP constraints constr *CS_AUX; // Vector with all the CSP constraints for increasing size unsigned int V_ID_CNTR = 0; // Unique identifier of each CSP variable unsigned int C_ID_CNTR = 0; // Unique identifier of each CSP constraint device_info DEVICES_INFO[MAX_DEVS]; // Information of the devices to use device_args DEVICES_ARGS[MAX_DEVS]; // Device arguments (buffers, etc.) #if FZN_SEQ label_heur *FZN_SEQ_LABELS; // Ordered list of labeling types to use in FlatZinc seq_search assign_heur *FZN_SEQ_ASSIGNS; // Ordered list of assigning types to use in FlatZinc seq_search #endif int FZN_SEQ_N_LABELS = 0; // Number of elements FZN_SEQ_LABELS /* * Parse execution arguments * argc - PHACT command arguments * argv - PHACT command arguments * csp_dims - will return all the PHACT arguments of the int type, placed by input order * csp_inst_name - name of the CSP instance for some CSPs modeled in C */ void parse_args(int *argc, char *argv[], int *csp_dims, char *csp_inst_name) { int args = *argc; int i, j; int k = 0; int csp_dim_arg_ctr = 0; int params_leng; for (i = 0; i < MAX_DEVS; i++) { DEVICES_INFO[i].n_ss_mult = 1; } for (i = 1; i < args; i++) { if (!strcmp(argv[i], "-COUNT")) { COUNTING_SOLUTIONS = true; WORK = CNT; } else if (!strcmp(argv[i], "-ONE")) { FINDING_ONE_SOLUTION = true; WORK = ONE; } else if (!strcmp(argv[i], "-OPT")) { OPTIMIZING = true; WORK = OPT; } else if (isdigit(*argv[i])) { if (csp_dim_arg_ctr + 1 == MAX_CSP_DIM_ARGS) { printf("\nToo many dimension arguments. Please increase \"MAX_CSP_DIM_ARGS\" value.'\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } csp_dims[csp_dim_arg_ctr++] = atoi(argv[i]); } else if (isdigit(*argv[i])) { if (csp_dim_arg_ctr + 1 == MAX_CSP_DIM_ARGS) { printf("\nToo many dimension arguments. Please increase \"MAX_CSP_DIM_ARGS\" value.'\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } csp_dims[csp_dim_arg_ctr++] = atoi(argv[i]); } else if (!strcmp(argv[i], "-N-SS")) { N_SS = (unsigned int) atoi(argv[++i]); } else if (!strcmp(argv[i], "-E")) { CSP = malloc((strlen(argv[++i]) + 1) * sizeof(char)); strcpy(CSP, argv[i]); } else if (!strcmp(argv[i], "-V")) { VERBOSE = true; } else if (!strcmp(argv[i], "-Q")) { QUIET = true; } else if (!strcmp(argv[i], "-ANTI-FIRST-FAIL")) { LABEL_MODE_COM = ANTI_FIRST_FAIL; } else if (!strcmp(argv[i], "-FIRST-FAIL")) { LABEL_MODE_COM = FIRST_FAIL; } else if (!strcmp(argv[i], "-LARGEST")) { LABEL_MODE_COM = LARGEST; } else if (!strcmp(argv[i], "-INPUT-ORDER")) { LABEL_MODE_COM = INPUT_ORDER; } else if (!strcmp(argv[i], "-MAX-REGRET")) { LABEL_MODE_COM = MAX_REGRET; } else if (!strcmp(argv[i], "-MOST-CONSTRAINED")) { LABEL_MODE_COM = MOST_CONSTRAINED; } else if (!strcmp(argv[i], "-OCCURRENCE")) { LABEL_MODE_COM = OCCURRENCE; } else if (!strcmp(argv[i], "-SMALLEST")) { LABEL_MODE_COM = SMALLEST; } else if (!strcmp(argv[i], "-INDOMAIN-INTERVAL")) { ASSIGN_MODE_COM = INDOMAIN_INTERVAL; } else if (!strcmp(argv[i], "-INDOMAIN-MAX")) { ASSIGN_MODE_COM = INDOMAIN_MAX; } else if (!strcmp(argv[i], "-INDOMAIN-MEDIAN")) { ASSIGN_MODE_COM = INDOMAIN_MEDIAN; } else if (!strcmp(argv[i], "-INDOMAIN-MIDDLE")) { ASSIGN_MODE_COM = INDOMAIN_MIDDLE; } else if (!strcmp(argv[i], "-INDOMAIN-MIN")) { ASSIGN_MODE_COM = INDOMAIN_MIN; } else if (!strcmp(argv[i], "-INDOMAIN-REVERSE-SPLIT")) { ASSIGN_MODE_COM = INDOMAIN_REVERSE_SPLIT; } else if (!strcmp(argv[i], "-INDOMAIN-SPLIT")) { ASSIGN_MODE_COM = INDOMAIN_SPLIT; } else if (!strcmp(argv[i], "-STATS")) { PRINT_STATS = true; } else if (!strcmp(argv[i], "-INTERVALS")) { DOMAIN_TYPE = INTERVAL; } else if (!strcmp(argv[i], "-PRINT-SOLUTIONS")) { PRINT_SOLUTIONS = true; } else if (!strcmp(argv[i], "-PRINT-CSP")) { PRINT_CSP = true; } else if (!strcmp(argv[i], "-MZN2FZN-ONLY")) { MZN2FZN_ONLY = true; } else if (!strcmp(argv[i], "-D")) { N_DEVS++; i++; params_leng = (int) strlen(argv[i]); char *params = malloc(((unsigned long) params_leng + 1) * sizeof(char)); strcpy(params, argv[i]); if (params[0] == 'G') { DEVICES_INFO[k].type = CL_DEVICE_TYPE_GPU; N_GPUs++; } else if (params[0] == 'C') { DEVICES_INFO[k].type = CL_DEVICE_TYPE_CPU; N_CPUs++; } else if (params[0] == 'A') { DEVICES_INFO[k].type = CL_DEVICE_TYPE_ACCELERATOR; N_ACCs++; } else { printf("\nInvalid argument '%s'\n", params); print_help(); free(params); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } DEVICES_INFO[k].dev_type_n = 0; DEVICES_INFO[k].n_wg = 0; DEVICES_INFO[k].n_wi_wg = 0; if (params_leng > 3) { j = 3; // if : get number of device of this type to use (1...) if (j < params_leng && params[j] == ':') { DEVICES_INFO[k].dev_type_n = atoi(params + j + 1); j += 1 + get_int_len(DEVICES_INFO[k].dev_type_n); } // if / use all the devices of this type if (j < params_leng && params[j] == '/') { // if / use the default number of work-groups for this device if (params[j + 1] == '/') { j++; DEVICES_INFO[k].n_wg = 0; // if something else capture the number of work-items per work-group to use if (j < params_leng) { DEVICES_INFO[k].n_wi_wg = (unsigned long) atoi(params + j + 1); } // if nothing use the default number of work-items else { DEVICES_INFO[k].n_wi_wg = 0; } } else { // capture number of work-groups to use DEVICES_INFO[k].n_wg = (unsigned long) atoi(params + j + 1); j += 1 + get_int_len((int) DEVICES_INFO[k].n_wg); // if something else capture the number of work-items per work-group to use if (j + 1 < params_leng) { DEVICES_INFO[k].n_wi_wg = (unsigned long) atoi(params + j + 1); } // if nothing use the default number of work-items else { DEVICES_INFO[k].n_wi_wg = 0; } } } // if nothing use all the devices of this type with default number of work-groups and work-items else if (j == params_leng) { DEVICES_INFO[k].n_wg = 0; DEVICES_INFO[k].n_wi_wg = 0; } else { printf("\nInvalid argument '%s'\n", params); print_help(); free(params); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } k++; free(params); } else if (!strcmp(argv[i], "-H")) { print_help(); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } else if (!strcmp(argv[i], "-FZN")) { FZN_FILE_NAME = malloc((strlen(argv[++i]) + 1) * sizeof(char)); strcpy(FZN_FILE_NAME, argv[i]); } else if (!strcmp(argv[i], "-MZN")) { MZN_FILE_NAME = malloc((strlen(argv[++i]) + 1) * sizeof(char)); strcpy(MZN_FILE_NAME, argv[i]); int len = (int) strlen(argv[++i]); if (len > 4) { const char *last_four = &argv[i][len - 4]; if (strcmp(last_four, ".dzn") == 0) { DZN_FILE_NAME = malloc((strlen(argv[i]) + 1) * sizeof(char)); strcpy(DZN_FILE_NAME, argv[i]); } else { i--; } } else { i--; } } else if (CSP != NULL && strcmp(csp_inst_name, "No name given") == 0) { if ((strlen(argv[i]) + 1) > 20) { printf("\nThe name of the CSP instance is too big, please decrease it to a maximum of 20 characters.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } strcpy(csp_inst_name, argv[i]); } else { printf("\nInvalid argument '%s'\n", argv[i]); print_help(); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } } if (N_DEVS == 0) { ALL_DEVS = true; } if (csp_dim_arg_ctr == 0 && csp_inst_name == NULL) { printf("\n-N must be defined!\n"); print_help(); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } if (QUIET) { VERBOSE = false; } } /* * Prints all accepted arguments with their description */ void print_help() { printf("\nParallel heterogeneous architecture constraint toolkit (PHACT) is a complete\n" "solver, capable of using all the devices compatible with OpenCL of a machine\n" "to solve a CSP.\n" "It can load CSPs implemented in C according to PHACT's interface, or modeled\n" "in MiniZinc or FlatZinc and whose variables domains are constituted by\n" "positive integers or booleans.\n\n" "\nList of accepted arguments:\n" " -D [GPU|CPU|ACC][:n][/[wg]/[wi]] - Select the device/s to use. Examples:\n" " -D CPU:1/64/1 -D GPU:2 -D ACC//1 - Use first CPU with 64 work-groups\n" " and 1 work-item per work-group, second GPU with the default number of\n" " work-groups and of work-items, and all accelerators with default number\n" " of work-groups and one work-item per work-group;\n" " -D CPU:1 -D GPU:1 -INTERVALS - Use first CPU and first GPU with INTERVAL\n" " domains;\n" " -D CPU -D GPU - Use all GPUs and all CPUs with default number of\n" " work-groups and work-items;\n" " If none -D argument is introduced, all the devices compatible with OpenCL\n" " will be used.\n\n" " -E [QUEENS | COSTAS | GOLOMB | SUDOKU | ALL-DIFF | QAP | LANGFORD | STEINER |\n" " LATIN | ALL-INTERVAL | MARKET-SPLIT | SCHURS] - Select one of the sample\n" " CSPs implemented through PHACT's interface;\n" " -FZN /home/user/csp.fzn - Solve the Flatzinc model in the file\n" " \"/home/user/csp.fzn\". If only the mame of the file is given, it\n" " will be searched in src/csps/csp.fzn. Flex and Bison programs are\n" " required;\n" " -MZN /home/user/csp.mzn /home/user/csp.dzn - Solve the Minizinc model\n" " in the files \"/home/user/csp.mzn\" and \"/home/user/csp.dzn\".\n" " If only the mame of the files is given, they will be searched in\n" " src/csps/csp.Xzn. Mzn2fzn, Flex and Bison programs are required.\n\n" " -MZN /home/user/csp.mzn [/home/user/csp.dzn] -MZN2FZN-ONLY - Only\n" " converts the MZN file in \"/home/user/csp.mzn\" and\n" " \"/home/user/csp.dzn\" to the FZN file \"/home/user/csp.fzn\".\n" " If only the mame of the file is given, it will be searched in\n" " src/csps/csp.Xzn. Mzn2fzn program is required.\n\n" " (int) - CSP dimension. \"(int)\" should be replaced by each dimension of the\n" " CSP to solve. Not used when solving a Minizinc or Flatzinc model.\n\n" " [-COUNT|-ONE|-OPT] - Select what must be done with the CSP. When solving\n" " FlatZinc models, it overrides the model selection:\n" " -COUNT - Count all the solutions;\n" " -ONE - Find one solution. Default for CSPs modeled with PHACT C interface;\n" " -OPT - Do optimization.\n\n" " [-INTERVALS] - Use interval representation for domains, instead of bitmaps.\n\n" " [-N-SS n] - Number of sub-search spaces to create. \"n\" should be replaced by\n" " the number of sub-search spaces to create. If not present, the default\n" " number of sub-search spaces will be created;\n\n" " [-ANTI-FIRST-FAIL | -FIRST-FAIL | -INPUT-ORDER | -LARGEST | -MAX-REGRET | \n" " -MOST-CONSTRAINED | -OCCURRENCE | -SMALLEST] - Method to select the variable\n" " to label:\n" " -ANTI-FIRST-FAIL - Select the variable to label that has more values in\n" " its domain;\n" " -FIRST-FAIL - Select the variable to label that has less values in its\n" " domain;\n" " -LARGEST - Select the variable to label that has the largest value in its\n" " domain;\n" " -INPUT-ORDER - Select the variable to label by the order on which they were\n" " created. Default;\n" " -MAX-REGRET - Select the variable to label that has the largest difference\n" " between the two smallest values in its domain;\n" " -MOST-CONSTRAINED - Select the variable to label that has the smallest\n" " domain, breaking ties using the number of constrains;\n" " -OCCURRENCE - Select the variable to label that is more constrained;\n" " -SMALLEST - Select the variable to label that has the smallest value in its\n" " domain.\n\n" " [-INDOMAIN-INTERVAL | -INDOMAIN-MAX | -INDOMAIN-MIDDLE | -INDOMAIN-MEDIAN |\n" " -INDOMAIN-MIN | -INDOMAIN-REVERSE-SPLIT | -INDOMAIN-SPLIT] - Method to\n" " select the value to assign to the variable for labeling:\n" " -INDOMAIN-INTERVAL - Select the first contiguous interval or, if none, select\n" " half of the domain;\n" " -INDOMAIN-MAX - Select the maximum value to assign;\n" " -INDOMAIN-MIDDLE - Select the mean value of the domain bounds;\n" " -INDOMAIN-MEDIAN - Select the median value of the domain values;\n" " -INDOMAIN-MIN - Select the minimum value to assign. Default;\n" " -INDOMAIN-REVERSE-SPLIT - Splits the domain about half and tries the second\n" " half;\n" " -INDOMAIN-SPLIT - Splits the domain about half and tries the first half.\n\n" " -STATS - Print statistics about the solving process;\n" " -PRINT-SOLUTIONS - Print all the solutions (only available when using only\n" " one thread per device);\n" " -PRINT-CSP - Before starting the exploration, prints all the variables with\n" " their domains, the constraints and the relation between them;\n" " -V - Print more information and timings about what is being done by each\n" " device;\n" " -Q - Print only the best solution, the solution, or the number of solutions,\n" " depending if optimizing, searching for one solution or counting the\n" " number of solutions;\n\n" " -H - Show this information.\n\n" "\nNotes on compilation:\n" " To compile PHACT execute one of the following commands on folder\n" " \"PHACT/Debug\":\n" " make all - To solve CSPs with variables whose domains have values between 0\n" " and 1023;\n" " make all CFLAGS=\"-D BITS=n\" - To solve CSPs with variables whose domains\n" " have values between 0 and n. When recompiling PHACT to change\n" " CL_BITS value, please run \"make clean\" before;\n" " make all CFLAGS=\"-D COMPILE_FZN=0\" - Required when the programs mzn2fzn,\n" " flex or bison are not available. Minizinc and Flatzinc interpreter will\n" " not be available.\n\n" "\nNote on execution:\n" " The OpenCL drivers implemented by some vendors for their devices will try to\n" " vectorize the kernel. When using PHACT in some devices, that may result in\n" " crashing the OpenCL compiler, or in a poor performance of PHACT.\n" " For that motive, it is recommended to disable this OpenCL feature by\n" " introducing \"CL_CONFIG_USE_VECTORIZER=false\" at the beginning of PHACT\n" " execution command.\n\n" "\nExecution examples:\n" " For counting the number of solutions of the Costas Array 10 problem using all\n" " the devices compatible with OpenCL on the running machine, execute the\n" " following command on folder \"PHACT/Debug\":\n" " ./PHACT -E COSTAS 10 -COUNT\n\n" " For finding one solution for the n-Queens 30 problem using all the GPUs\n" " compatible with OpenCL on the running machine, execute the following\n" " command on folder \"PHACT/Debug\":\n" " ./PHACT -E QUEENS 30 -D GPU\n\n" " For finding one solution for a new CSP modeled in the file \"/src/csps/CSP.c\"\n" " and using the CPU on the running machine, after recompiling PHACT,execute\n" " the following command on folder \"PHACT/Debug\":\n" " ./PHACT -D CPU\n\n" " For solving the CSP modeled in the FlatZinc file\n" " \"PHACT/Debug/src/csps/CSP.fzn\" file using all the GPUs compatible with\n" " OpenCL on the running machine, execute the following command on folder\n" " \"PHACT/Debug\":\n" " ./PHACT CSP.fzn -D GPU\n\n" " For solving the CSP modeled in the MiniZinc files\n" " \"PHACT/Debug/src/csps/CSP.mzn\" and \"PHACT/Debug/src/csps/CSP.dzn\"\n" " files using all the devices compatible with OpenCL on the running machine,\n" " execute the following command on folder \"PHACT/Debug\":\n" " ./PHACT -MZN CSP.mzn CSP.dzn\n\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif } /* * Initialize number of variables and constraints and bitmap size on devices */ void init_csp_and_d_bits() { if (WORK != OPT && (USE_CS[MAXIMIZE] == 1 || USE_CS[MINIMIZE] == 1)) { printf("\nPHACT is trying to count all the solutions or just finding one solution for a CSP that was modeled as an optimization problem.\n" "For that purpose please remove the \"c_min\" or \"c_max\" constraints.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } if (WORK == OPT && USE_CS[MAXIMIZE] == 0 && USE_CS[MINIMIZE] == 0) { printf("\nPHACT is trying to optimize a CSP that was not modeled as an optimization problem.\n" "For that purpose please use the \"c_min\" or \"c_max\" constraints.\n"); #if defined(WIN32) || defined(_WIN32) || defined(__WIN32) && !defined(__CYGWIN__) printf("\nPress any key to exit\n"); int a = getchar(); #endif exit(0); } // set domain size for usage on kernel if (DOMAIN_TYPE == BITMAP_) { if (D_MAX < 32) { CL_BITS_ = 32; CL_WORD_ = 32; } else if (D_MAX < 64) { CL_BITS_ = 64; CL_WORD_ = 64; } else { CL_BITS_ = D_MAX / 64 * 64 + 64; CL_WORD_ = 64; } CL_N_WORDS_ = CL_BITS_ / CL_WORD_; if (CL_N_WORDS_ == 0) { CL_N_WORDS_ = 1; } DOMAIN_SIZE = CL_N_WORDS_ * CL_WORD_ / 8; } else if (DOMAIN_TYPE == INTERVAL) { DOMAIN_SIZE = sizeof(interval); } N_VS = V_ID_CNTR; N_CS = C_ID_CNTR; } /* * Print all the CSP variables and constraints, including the variables values and ID and * the constraints ID and the ID of the variables that they constrain */ void print_CSP() { unsigned int i; unsigned int prev_val; unsigned int new_val; unsigned int cntr; int j; printf("\n\n--------------------------------\n"); printf("CSP as received by the host:\n"); printf("\nVariables:\n"); for (i = 0; i < V_ID_CNTR; i++) { printf(" ID=%u: Values={", VS[i].v_id); j = 1; prev_val = b_get_nth_val(&VS[i].domain_b, (unsigned int) j++); new_val = prev_val; printf("%u", prev_val); while (new_val < VS[i].max) { cntr = 0; while ((new_val = (unsigned int) b_get_nth_val(&VS[i].domain_b, (unsigned int) j++)) == prev_val + 1 && new_val < VS[i].max) { prev_val = new_val; cntr++; } if (cntr == 0) { printf(",%u", new_val); } else { if (new_val == VS[i].max && new_val == prev_val + 1) { printf("-%u", new_val); } else if (cntr == 1) { printf(",%u,%u", prev_val, new_val); } else { printf("-%u,%u", prev_val, new_val); } } prev_val = new_val; } if (VS[i].to_label) { printf("} Label=true"); } else { printf("} Label=false"); } if (VS[i].boolean) { printf(" boolean=true"); } else { printf(" boolean=false"); } #if FZN_SEQ if (VS[i].to_label) { printf(" label_h=%s assign_hs=%s", get_label_heur(VS[i].label_h), get_assign_heur(VS[i].assign_h)); } #endif if (VS[i].n_cs > 0) { printf(" Constraints={"); for (j = 0; j < VS[i].n_cs - 1; j++) { printf("%u,", VS[i].cs[j]->c_id); } if (VS[i].n_cs > 0) { printf("%u}\n", VS[i].cs[j]->c_id); } else { printf("\n"); } } else { printf("\n"); } } printf("Constraints:\n"); for (i = 0; i < C_ID_CNTR; i++) { printf(" ID=%u: Type=", CS[i].c_id); cs_print_type(&CS[i]); printf(" Variables={"); for (j = 0; j < CS[i].n_c_vs - 1; j++) { printf("%u,", CS[i].c_vs[j]->v_id); } printf("%u}", CS[i].c_vs[j]->v_id); if (CS[i].n_c_consts > 0) { printf(" Constants={"); for (j = 0; j < CS[i].n_c_consts - 1; j++) { printf("%d,", CS[i].c_consts[j]); } if (CS[i].kind == INT_LIN_EQ || CS[i].kind == INT_LIN_NE || CS[i].kind == INT_LIN_LE || CS[i].kind == BOOL_LIN_LE) { printf("%d, %d}", CS[i].c_consts[j], CS[i].constant_val); } else { printf("%d}", CS[i].c_consts[j]); } } else if (CS[i].kind == ELEMENT || CS[i].kind == EXACTLY_VAR || CS[i].kind == INT_LIN_EQ || CS[i].kind == INT_LIN_NE || CS[i].kind == MINUS_EQ || CS[i].kind == MINUS_NE || CS[i].kind == SUM_PROD || CS[i].kind == SUM || CS[i].kind == INT_LIN_LE || CS[i].kind == ARRAY_INT_ELEMENT || CS[i].kind == INT_EQ_C) { printf(" Constants={%d}", CS[i].constant_val); } if (CS[i].ignore) { printf(" ignored"); } if (CS[i].boolean) { printf(" boolean"); } if (CS[i].reified) { printf(" reif_var_ID=%u\n", CS[i].reif_v_id); } else { printf("\n"); } } printf("\n"); printf("--------------------------------\n\n"); } /* * Return the name of the heuristic used for selecting the next variable to label */ char* get_label_heur(label_heur l) { switch (l) { case ANTI_FIRST_FAIL: return "Anti_first_fail"; break; case FIRST_FAIL: return "First_fail"; break; case INPUT_ORDER: return "Input_order"; break; case LARGEST: return "Largest"; break; case MAX_REGRET: return "Max_regret"; break; case MOST_CONSTRAINED: return "Most_constrained"; break; case OCCURRENCE: return "Occurrence"; break; case SMALLEST: return "Smallest"; break; default: return "UNKNOWN"; break; } } /* * Return the name of the heuristic used for selecting the next value to assign */ char* get_assign_heur(assign_heur a) { switch (a) { case INDOMAIN_INTERVAL: return "Indomain_interval"; break; case INDOMAIN_MAX: return "Indomain_max"; break; case INDOMAIN_MEDIAN: return "Indomain_median"; break; case INDOMAIN_MIDDLE: return "Indomain_middle"; break; case INDOMAIN_MIN: return "Indomain_min"; break; case INDOMAIN_REVERSE_SPLIT: return "Indomain_reverse_split"; break; case INDOMAIN_SPLIT: return "Indomain_split"; break; default: return "UNKNOWN"; break; } } /* * Clear CSP variables and constraints memory */ void clear_csp() { unsigned int i; for (i = 0; i < N_DEVS; i++) { free(DEVICES_INFO[i].dev_name); } cs_clear(); vs_clear(); if (WORK == OPT) { free(VS_LOCK); free(VS_LOCK_BEST); } free(VS); free(CS); free(CONST_VS_ID); free(CSP); free(EXP_VALUES); } /* * return the number of characters on an integer * x - integer to count number of characters */ int get_int_len(int x) { if (x >= 1000) return 4; if (x >= 100) return 3; if (x >= 10) return 2; return 1; } /* * Check if program exists on the PATH environment * cmd - command to execute the program */ bool can_run_command(const char *cmd) { if (strchr(cmd, '/')) { // if cmd includes a slash, no path search must be performed, // go straight to checking if it's executable return access(cmd, X_OK) == 0; } const char *path = getenv("PATH"); if (!path) return false; char *buf = malloc(strlen(path) + strlen(cmd) + 3); if (!buf) return false; // loop as path contains something for (; *path; ++path) { // start from the beginning of the buffer char *p = buf; // copy in buf the current path element for (; *path && *path != ':'; ++path, ++p) { *p = *path; } // empty path entries are treated like "." if (p == buf) *p++ = '.'; // slash and command name if (p[-1] != '/') *p++ = '/'; strcpy(p, cmd); // check if it can be executed if (access(buf, X_OK) == 0) { free(buf); return true; } // quit at last cycle if (!*path) break; } // not found free(buf); return false; }