// Copyright (c) 2015 Carnegie Mellon University. // All Rights Reserved. // Redistribution and use in source and binary forms, with or without modification, are permitted provided that the following conditions are met: // 1. Redistributions of source code must retain the above copyright notice, this list of conditions and the following acknowledgments and disclaimers. // 2. Redistributions in binary form must reproduce the above copyright notice, this list of conditions and the following acknowledgments and disclaimers in the documentation and/or other materials provided with the distribution. // 3. Products derived from this software may not include “Carnegie Mellon University,” "SEI” and/or “Software Engineering Institute" in the name of such derived product, nor shall “Carnegie Mellon University,” "SEI” and/or “Software Engineering Institute" be used to endorse or promote products derived from this software without prior written permission. For written permission, please contact permission@sei.cmu.edu. // ACKNOWLEDGMENTS AND DISCLAIMERS: // Copyright 2015 Carnegie Mellon University // This material is based upon work funded and supported by the Department of Defense under Contract No. FA8721-05-C-0003 with Carnegie Mellon University for the operation of the Software Engineering Institute, a federally funded research and development center. // Any opinions, findings and conclusions or recommendations expressed in this material are those of the author(s) and do not necessarily reflect the views of the United States Department of Defense. // NO WARRANTY. THIS CARNEGIE MELLON UNIVERSITY AND SOFTWARE ENGINEERING INSTITUTE MATERIAL IS FURNISHED ON AN “AS-IS” BASIS. CARNEGIE MELLON UNIVERSITY MAKES NO WARRANTIES OF ANY KIND, EITHER EXPRESSED OR IMPLIED, AS TO ANY MATTER INCLUDING, BUT NOT LIMITED TO, WARRANTY OF FITNESS FOR PURPOSE OR MERCHANTABILITY, EXCLUSIVITY, OR RESULTS OBTAINED FROM USE OF THE MATERIAL. CARNEGIE MELLON UNIVERSITY DOES NOT MAKE ANY WARRANTY OF ANY KIND WITH RESPECT TO FREEDOM FROM PATENT, TRADEMARK, OR COPYRIGHT INFRINGEMENT. // This material has been approved for public release and unlimited distribution. // DM-0002626 // // What is this? // It is a program that performs schedulability analysis and // memory mapping configuration for parallel real-time tasks // scheduled with global Earliest-Deadline-First. // // How do I install it? // First, install Gurobi 6.0. It is free for academic users. // You can download it from www.gurobi.com // Then compile it as follows: // gcc -m64 -g -o parmemconfig parmemconfig.c -I/home/bjorn/gurobi/gurobi600/linux64/include -O3 -lm // Then create a file system.txt which describes the taskset and computer // platform that you want to analyze. // You can run it with a single system as input as follows: // parmemconfig -i system.txt -o result_from_analysis.txt // If the system is deemed schedulable then the file result_from_analysis // contains the memory mapping; otherwise the file result_from_analysis is deleted. // // What is the file format of the input file (e.g. system.txt) ? // You can learn about the format of the input file by studying the function // readsystemfromfile( FILE* f) in this source code file. // The format is as follows: // // 3 // 3600.000000 // // 20 // 4 // 1.000000 // 32 // 16 // 0.250000 // 524288 // 1500000000.000000 // 4.000000 // 20.000000 // 7.000000 // 8.000000 // 5.000000 // 9.000000 // 9.000000 // 9.000000 // 10.000000 // 12 // // 3 // // 0.100000 0.100000 3 // 1 0.001000 17 // 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 // 4 0.030000 17 // 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 1000 // 1 0.001000 17 // 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 // // 0.010000 0.010000 1 // 1 0.002000 17 // 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 // // 0.100000 0.044000 3 // 1 0.002000 17 // 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 // 2 0.006000 17 // 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 // 1 0.002000 17 // 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 100 // // 12 // 1 1 1 0 1 2 1 0 // 1 1 1 1 1 2 2 0 // 1 1 1 2 1 2 3 0 // 1 1 1 3 1 2 4 0 // 1 3 1 0 1 2 1 1 // 1 3 1 1 1 2 2 1 // 1 3 1 2 1 2 3 1 // 1 3 1 3 1 2 4 1 // 3 1 1 0 3 2 1 0 // 3 1 1 1 3 2 2 0 // 3 3 1 0 3 2 1 1 // 3 3 1 1 3 2 2 1 // 970 // // What is the file format of the output file (e.g. result_from_analysis.txt) ? // The format is as follows: // 1 2 1 16 25 13 // ... // The first line means that for task 1, its 2nd stage, its 1st segment, its // page 16 should be mapped to a frame oc cache color 25 and bank color 13. // // How do I generate a default system? // Do the following: // parmemconfig -g // // How do I test many systems (as a form of self-check)? // You can run it in meta mode (generates many systems and analyzes/configures all of them): // parmemconfig -m // // How much memory does this program require? // The program is memory hungry. We recommend that you have at last 16 Gigabyte of main memory to run the analysis/configuration. // If you run the meta mode (with switch -m) then you need this much memory to run the analysis/configuration. // You can run with the mode -m2 and then it runs a smaller system and this consumes less memory. // // How do I know if a solution is found? // If a solution is found then a file is written with the memory mapping. By default, the name of this file is result_from_analysis.txt. // This file contains rows with 6 integers in each row. // An example of what this file may look like is as follows: // 1 1 1 0 5 13 // 1 1 1 1 19 1 // 1 1 1 2 21 15 // 1 1 1 3 12 14 // 1 2 1 0 5 13 // 1 2 1 1 5 13 // ... // The numbers on a line should be read as follows: // the first column is task index (i); the second column is stage index (j); the third column is the segment index (g); // the fourth column is the page index (p); the fifth column is the cache color; the sixth column is the bank color. // Each line specifies that a certain page of a certain segment of a certain stage of a certain task should be mapped // to a cell (cache color and bank color). #define CALLGUROBITHROUGHAPI 0 #define COMPILEMSVS 0 #define COMPILEWIN32 0 #define COMPILEOSX 0 #if COMPILEMSVS #else #include "gurobi_c.h" #endif // We add these in order to do file I/O like in UNIX. And ceil(..) #include #include #include // we add this in order to call the function time( ..) #if COMPILEMSVS #include #endif #include #if COMPILEMSVS #include #endif #include #if COMPILEWIN32 #include #endif #include // this is needed for strcmp #if COMPILEMSVS #include #else #include #endif #include #include #include #if COMPILEWIN32 #include #endif #define MAXNVARS 10000000 // if this is set to 25000000 then we get swapping one some examples #define MAXVARIABLESTRINGLENGTH 25 struct memoryaccessesofstagestruct { int npages; int* MA; }; struct structoftask { double T; double D; int nstages; int* nsegments_of_stage; double* exec_of_stage; struct memoryaccessesofstagestruct* memoryaccessesdescription; }; int method = 3; int K; // the computer platform int nprocessors; // this is the number of processors double s; // this is the speed of processors // the taskset int ntasks; // this is the number of tasks struct structoftask* tasks = NULL; int H; // number of cache colors // first cache set is cache set 0 int B; // number of banks // first bank is bank 0 // double HWSHARE; int MEMCAP; // this is the memory capacity of the entire computer system in terms of the number of frames int CAP; // this is the memory capacity of a cell double Linterpre; double Linteract; double Linterrw; double Lconf; double Lconhits1; double Linter; struct framesharingspecification { int iprime; int jprime; int gprime; int pprime; int iprimeprime; int jprimeprime; int gprimeprime; int pprimeprime; }; double MBCF; int nelements_in_sharedframes; struct framesharingspecification* sharedframes = NULL; int Nre; int INO; // this is the total number of pages accessed during initialization // derived parameters double P; // this is the lcm of Tis. double SCALINGFACTORNACCESSES = 8388608.0; double GUROBITIMEOUTPARAMETER = 3600.0; char inputfilename[2000] = "system.txt"; char outputfilename[2000] = "result_from_analysis.txt"; int meta_mode = 0; int metatwo_mode = 0; int counterforILPsolver; int myGRB_INT_PAR_MIPFOCUS = 1; int myGRB_INT_PAR_AGGREGATE = 0; double myGRB_DBL_PAR_FEASIBILITYTOL = 0.000000001; double myGRB_DBL_PAR_INTFEASTOL = 0.000000001; double myGRB_DBL_PAR_MARKOWITZTOL = 0.5; int myGRB_INT_PAR_QUAD = 1; int myGRB_INT_PAR_NUMERICFOCUS = 3; double myGRB_DBL_PAR_HEURISTICS = 0.5; double myGRB_DBL_PAR_FEASRELAXBIGM = 1000000000000*100; int gurobipathisset = 0; char gurobipath[200]; int generate_one_system_mode = 0; #if CALLGUROBITHROUGHAPI #else FILE* gurobithroughcommandlinelpfile; char gurobithroughcommandlinelpfilename[200]; FILE* gurobithroughcommandlinepyfile; char gurobithroughcommandlinepyfilename[200]; char commandstringwithscript[200]; #endif //clock_gettime is not implemented on OSX, so use this one #ifdef __MACH__ #include int clock_gettime(int clk_id, struct timespec* t) { struct timeval now; int rv = gettimeofday(&now, NULL); if (rv) return rv; t->tv_sec = now.tv_sec; t->tv_nsec = now.tv_usec * 1000; return 0; } #endif // Sleep function that switches on which platform we're running on void my_sleep(int duration) { #if COMPILEWIN32 Sleep(duration); #else sleep(duration); #endif return; } void addcharactertoendofstringifmissing(char* s, char c) { int len; len = strlen(s); if (s[len-1]!=c) { s[len] = c; s[len+1] = '\0'; } } #if CALLGUROBITHROUGHAPI #else void create_Gurobi_command_line_for_executing_script() { #if COMPILEMSVS if (gurobipathisset) { addcharactertoendofstringifmissing(gurobipath,'\\'); sprintf( commandstringwithscript, "%sgurobi.bat %s", gurobipath, gurobithroughcommandlinepyfilename); } else { sprintf( commandstringwithscript, "gurobi.bat %s", gurobithroughcommandlinepyfilename); } #else #if COMPILEWIN32 if (gurobipathisset) { addcharactertoendofstringifmissing(gurobipath,'\\'); sprintf( commandstringwithscript, "%sgurobi.bat %s", gurobipath, gurobithroughcommandlinepyfilename); } else { sprintf( commandstringwithscript, "gurobi.bat %s", gurobithroughcommandlinepyfilename); } #else if (gurobipathisset) { addcharactertoendofstringifmissing(gurobipath,'/'); sprintf( commandstringwithscript, "%sgurobi.sh %s", gurobipath, gurobithroughcommandlinepyfilename); } else { sprintf( commandstringwithscript, "gurobi.sh %s", gurobithroughcommandlinepyfilename); } #endif #endif } #endif int minint2( int t1, int t2) { if (t1t2) { return t1; } else { return t2; } } double mindouble2( double t1, double t2) { if (t1t2) { return t1; } else { return t2; } } double maxdouble3( double t1, double t2, double t3) { double temp; temp = maxdouble2(t1,t2); return maxdouble2( temp, t3 ); } double maxdouble4( double t1, double t2, double t3, double t4) { double temp; temp = maxdouble3(t1,t2,t3); return maxdouble2( temp, t4 ); } double maxdouble5( double t1, double t2, double t3, double t4, double t5) { double temp; temp = maxdouble4(t1,t2,t3,t4); return maxdouble2( temp, t5 ); } int divandceil( int n1, int n2) { if (n1%n2==0) { return (n1/n2); } else { return (n1/n2)+1; } } int divandfloor( int n1, int n2) { return (n1/n2); } double trrd = 4; // measured in cycles double tfaw = 20; // measured in cycles double wl = 7; // measured in cycles double bl = 8; // measured in columns double twtr = 5; // measured in cycles double cl = 9; // measured in cycles double trp = 9; // measured in cycles double trcd = 9; // measured in cycles double twr = 10; // measured in cycles void setmemoryparameters() { Linterpre = 1; Linteract = maxdouble2(trrd,tfaw-3*trrd); Linterrw = maxdouble2(wl+bl/2+twtr,cl+bl/2+2-wl); Lconf = (trp+trcd)+maxdouble2(cl+bl/2+2,wl+bl/2+maxdouble2(twtr,twr)); Lconhits1 = (wl+bl/2+twtr + twr - twtr); Linter = Linterpre + Linteract + Linterrw; } double getLconhitNre() { double temp; temp = divandceil(Nre,2)*(wl+bl/2+twtr) + divandfloor(Nre,2)*cl + (twr-twtr); return temp; } void printmemoryparameters() { printf("Linterpre = %15.10lf\n",Linterpre); printf("Linteract = %15.10lf\n",Linteract); printf("Linterrw = %15.10lf\n",Linterrw); printf("Lconf = %15.10lf\n",Lconf); printf("Lconhits1 = %15.10lf\n",Lconhits1); printf("Linter = %15.10lf\n",Linter); } void makesharedframesempty() { nelements_in_sharedframes = 0; } void allocatemakesharedframesempty(int nelements) { nelements_in_sharedframes = 0; sharedframes = (struct framesharingspecification*) malloc(sizeof(struct framesharingspecification)*nelements); if (sharedframes==NULL) { printf("malloc failure in allocatemakesharedframesempty\n"); exit( -1); } } void freemakesharedframes() { if (sharedframes!=NULL) { free( sharedframes); sharedframes = NULL; } } void addelementtosharedframes( int iprime, int jprime, int gprime, int pprime, int iprimeprime, int jprimeprime, int gprimeprime, int pprimeprime) { sharedframes[nelements_in_sharedframes].iprime = iprime; sharedframes[nelements_in_sharedframes].jprime = jprime; sharedframes[nelements_in_sharedframes].gprime = gprime; sharedframes[nelements_in_sharedframes].pprime = pprime; sharedframes[nelements_in_sharedframes].iprimeprime = iprimeprime; sharedframes[nelements_in_sharedframes].jprimeprime = jprimeprime; sharedframes[nelements_in_sharedframes].gprimeprime = gprimeprime; sharedframes[nelements_in_sharedframes].pprimeprime = pprimeprime; nelements_in_sharedframes = nelements_in_sharedframes + 1; } int is_in_sharedframes(int iprime, int jprime, int gprime, int pprime, int iprimeprime, int jprimeprime, int gprimeprime, int pprimeprime) { int found; int index; found = 0; for (index=0;index0) { t = poweroftwo( temp/2); if (temp%2==0) { return t*t; } else { return t*t*2; } } else { printf("Error in function poweroftwo.\n"); exit(-1); } } void doit_setallMAtozero() { int i; int j; int p; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (p=0;p<=tasks[i].memoryaccessesdescription[j].npages-1;p++) { tasks[i].memoryaccessesdescription[j].MA[p] = 0; } } } } void doit_apply_mult_to_MA(double mult) { int i; int j; int p; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (p=0;p<=tasks[i].memoryaccessesdescription[j].npages-1;p++) { tasks[i].memoryaccessesdescription[j].MA[p] = tasks[i].memoryaccessesdescription[j].MA[p] * mult; } } } } void doit_setsharedframes() { int temp; makesharedframesempty(); for (temp=1;temp<=tasks[1].nsegments_of_stage[2];temp++) { addelementtosharedframes( 1, 1, 1, temp-1, 1, 2, temp, 0); } for (temp=1;temp<=tasks[1].nsegments_of_stage[2];temp++) { addelementtosharedframes( 1, 3, 1, temp-1, 1, 2, temp, 1); } addelementtosharedframes( 3, 1, 1, 0, 3, 2, 1, 0); addelementtosharedframes( 3, 1, 1, 1, 3, 2, 2, 0); addelementtosharedframes( 3, 3, 1, 0, 3, 2, 1, 1); addelementtosharedframes( 3, 3, 1, 1, 3, 2, 2, 1); } double calculateCAP() { if ((H!=0) && (B!=0)) { // CAP = HWSHARE * MEMCAP / (H*B); CAP = MEMCAP / (H*B); } } void setmethod(int newmethod) { method = newmethod; } void setGUROBITIMEOUTPARAMETER(double newGUROBITIMEOUTPARAMETER) { GUROBITIMEOUTPARAMETER = newGUROBITIMEOUTPARAMETER; } void setK(double newK) { K = newK; } void allocateTaskset(int numtasks){ ntasks = numtasks; tasks = (struct structoftask*) malloc(sizeof(struct structoftask)*(ntasks+1)); if (tasks==NULL) { printf("malloc failure in allocateTaskset\n"); exit( -1); } } void deleteTaskset(){ if (tasks!=NULL) { free( tasks); tasks = NULL; } } void setNumProcessors( int newNumProcessors) { nprocessors = newNumProcessors; } void setSpeed( double newspeed) { s = newspeed; } void setH( int newH) { H = newH; calculateCAP(); } void setB( int newB) { B = newB; calculateCAP(); } // void setHWSHARE(double newHWSHARE) // { // HWSHARE = newHWSHARE; // calculateCAP(); // } void setMEMCAP(double newMEMCAP) { MEMCAP = newMEMCAP; calculateCAP(); } void settrrdinbusclockcycles( int newtrrd) { trrd = newtrrd; setmemoryparameters(); } void settfawinbusclockcycles( int newtfaw) { tfaw = newtfaw; setmemoryparameters(); } void setwlinbusclockcycles( int newwl) { wl = newwl; setmemoryparameters(); } void setblinbusclockcycles( int newbl) { bl = newbl; setmemoryparameters(); } void settwtrinbusclockcycles( int newtwtr) { twtr = newtwtr; setmemoryparameters(); } void setclinbusclockcyclessettwtrinbusclockcycles( int newcl) { cl = newcl; setmemoryparameters(); } void settrpinbusclockcycles( int newtrp) { trp = newtrp; setmemoryparameters(); } void settrcdinbusclockcycles( int newtrcd) { trcd = newtrcd; setmemoryparameters(); } void settwrinbusclockcycles( int newtwr) { twr = newtwr; setmemoryparameters(); } void addtask( int taskid, double T, double D, int nstages) { tasks[taskid].T = T; tasks[taskid].D = D; tasks[taskid].nstages = nstages; tasks[taskid].nsegments_of_stage = (int*) malloc(sizeof(int)*(nstages+1)); tasks[taskid].exec_of_stage = (double*) malloc(sizeof(double)*(nstages+1)); tasks[taskid].memoryaccessesdescription = (struct memoryaccessesofstagestruct*) malloc(sizeof(struct memoryaccessesofstagestruct)*(nstages+1)); if (tasks[taskid].nsegments_of_stage==NULL) { printf("malloc failure in addtask\n"); exit( -1); } if (tasks[taskid].exec_of_stage==NULL) { printf("malloc failure in addtask\n"); exit( -1); } if (tasks[taskid].memoryaccessesdescription==NULL) { printf("malloc failure in addtask\n"); exit( -1); } } void deletetask( int taskid) { if (tasks[taskid].nsegments_of_stage!=NULL) { free( tasks[taskid].nsegments_of_stage ); tasks[taskid].nsegments_of_stage = NULL; } if (tasks[taskid].exec_of_stage!=NULL) { free( tasks[taskid].exec_of_stage ); tasks[taskid].exec_of_stage = NULL; } if (tasks[taskid].memoryaccessesdescription!=NULL) { free( tasks[taskid].memoryaccessesdescription ); tasks[taskid].memoryaccessesdescription = NULL; } } void addstage( int taskid, int stageid, int nsegments, double executionrequirement, int np) { tasks[taskid].nsegments_of_stage[stageid] = nsegments; tasks[taskid].exec_of_stage[stageid] = executionrequirement; tasks[taskid].memoryaccessesdescription[stageid].npages = np; tasks[taskid].memoryaccessesdescription[stageid].MA = malloc(sizeof(int)*np); if (tasks[taskid].memoryaccessesdescription[stageid].MA==NULL) { printf("malloc failure in addstage\n"); exit( -1); } } void deletestage( int taskid, int stageid) { if (tasks[taskid].memoryaccessesdescription[stageid].MA!=NULL) { free( tasks[taskid].memoryaccessesdescription[stageid].MA); tasks[taskid].memoryaccessesdescription[stageid].MA = NULL; } } void addMA( int taskid, int stageid, int pageindex, int upper_bound_on_number_of_memory_accesses) { tasks[taskid].memoryaccessesdescription[stageid].MA[pageindex] = upper_bound_on_number_of_memory_accesses; } void setNre(int newNre) { Nre = newNre; } void setINO(int newINO) { INO = newINO; } void deallocatetheentiresystem() { int i; int j; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { deletestage( i,j); } deletetask( i); } deleteTaskset(); freemakesharedframes(); } void setsystem1(int targetnprocessors, double C12, double mult) { setmethod(3); setGUROBITIMEOUTPARAMETER(3600.0); setK(20); allocateTaskset(3); setNumProcessors( targetnprocessors); setSpeed( 1.0); setH(32); setB(16); // setHWSHARE(1.0/4.0); setMEMCAP( 524288); MBCF = 1500000000; settrrdinbusclockcycles( 4); settfawinbusclockcycles( 20); setwlinbusclockcycles( 7); setblinbusclockcycles( 8); settwtrinbusclockcycles( 5); setclinbusclockcyclessettwtrinbusclockcycles( 9); settrpinbusclockcycles( 9); settrcdinbusclockcycles( 9); settwrinbusclockcycles( 10); setNre(12); addtask( 1, 0.100, 0.100, 3); addstage( 1, 1, 1, 0.001, 17); addMA( 1, 1, 0, 100*mult); addMA( 1, 1, 1, 100*mult); addMA( 1, 1, 2, 100*mult); addMA( 1, 1, 3, 100*mult); addMA( 1, 1, 4, 100*mult); addMA( 1, 1, 5, 100*mult); addMA( 1, 1, 6, 100*mult); addMA( 1, 1, 7, 100*mult); addMA( 1, 1, 8, 100*mult); addMA( 1, 1, 9, 100*mult); addMA( 1, 1, 10, 100*mult); addMA( 1, 1, 11, 100*mult); addMA( 1, 1, 12, 100*mult); addMA( 1, 1, 13, 100*mult); addMA( 1, 1, 14, 100*mult); addMA( 1, 1, 15, 100*mult); addMA( 1, 1, 16, 100*mult); addstage( 1, 2, targetnprocessors, C12, 17); addMA( 1, 2, 0, 1000*mult); addMA( 1, 2, 1, 1000*mult); addMA( 1, 2, 2, 1000*mult); addMA( 1, 2, 3, 1000*mult); addMA( 1, 2, 4, 1000*mult); addMA( 1, 2, 5, 1000*mult); addMA( 1, 2, 6, 1000*mult); addMA( 1, 2, 7, 1000*mult); addMA( 1, 2, 8, 1000*mult); addMA( 1, 2, 9, 1000*mult); addMA( 1, 2, 10, 1000*mult); addMA( 1, 2, 11, 1000*mult); addMA( 1, 2, 12, 1000*mult); addMA( 1, 2, 13, 1000*mult); addMA( 1, 2, 14, 1000*mult); addMA( 1, 2, 15, 1000*mult); addMA( 1, 2, 16, 1000*mult); addstage( 1, 3, 1, 0.001, 17); addMA( 1, 3, 0, 100*mult); addMA( 1, 3, 1, 100*mult); addMA( 1, 3, 2, 100*mult); addMA( 1, 3, 3, 100*mult); addMA( 1, 3, 4, 100*mult); addMA( 1, 3, 5, 100*mult); addMA( 1, 3, 6, 100*mult); addMA( 1, 3, 7, 100*mult); addMA( 1, 3, 8, 100*mult); addMA( 1, 3, 9, 100*mult); addMA( 1, 3, 10, 100*mult); addMA( 1, 3, 11, 100*mult); addMA( 1, 3, 12, 100*mult); addMA( 1, 3, 13, 100*mult); addMA( 1, 3, 14, 100*mult); addMA( 1, 3, 15, 100*mult); addMA( 1, 3, 16, 100*mult); addtask( 2, 0.010, 0.010, 1); addstage( 2, 1, 1, 0.002, 17); addMA( 2, 1, 0, 100*mult); addMA( 2, 1, 1, 100*mult); addMA( 2, 1, 2, 100*mult); addMA( 2, 1, 3, 100*mult); addMA( 2, 1, 4, 100*mult); addMA( 2, 1, 5, 100*mult); addMA( 2, 1, 6, 100*mult); addMA( 2, 1, 7, 100*mult); addMA( 2, 1, 8, 100*mult); addMA( 2, 1, 9, 100*mult); addMA( 2, 1, 10, 100*mult); addMA( 2, 1, 11, 100*mult); addMA( 2, 1, 12, 100*mult); addMA( 2, 1, 13, 100*mult); addMA( 2, 1, 14, 100*mult); addMA( 2, 1, 15, 100*mult); addMA( 2, 1, 16, 100*mult); addtask( 3, 0.100, 0.044, 3); addstage( 3, 1, 1, 0.002, 17); addMA( 3, 1, 0, 100*mult); addMA( 3, 1, 1, 100*mult); addMA( 3, 1, 2, 100*mult); addMA( 3, 1, 3, 100*mult); addMA( 3, 1, 4, 100*mult); addMA( 3, 1, 5, 100*mult); addMA( 3, 1, 6, 100*mult); addMA( 3, 1, 7, 100*mult); addMA( 3, 1, 8, 100*mult); addMA( 3, 1, 9, 100*mult); addMA( 3, 1, 10, 100*mult); addMA( 3, 1, 11, 100*mult); addMA( 3, 1, 12, 100*mult); addMA( 3, 1, 13, 100*mult); addMA( 3, 1, 14, 100*mult); addMA( 3, 1, 15, 100*mult); addMA( 3, 1, 16, 100*mult); addstage( 3, 2, 2, 0.006, 17); addMA( 3, 2, 0, 100*mult); addMA( 3, 2, 1, 100*mult); addMA( 3, 2, 2, 100*mult); addMA( 3, 2, 3, 100*mult); addMA( 3, 2, 4, 100*mult); addMA( 3, 2, 5, 100*mult); addMA( 3, 2, 6, 100*mult); addMA( 3, 2, 7, 100*mult); addMA( 3, 2, 8, 100*mult); addMA( 3, 2, 9, 100*mult); addMA( 3, 2, 10, 100*mult); addMA( 3, 2, 11, 100*mult); addMA( 3, 2, 12, 100*mult); addMA( 3, 2, 13, 100*mult); addMA( 3, 2, 14, 100*mult); addMA( 3, 2, 15, 100*mult); addMA( 3, 2, 16, 100*mult); addstage( 3, 3, 1, 0.002, 17); addMA( 3, 3, 0, 100*mult); addMA( 3, 3, 1, 100*mult); addMA( 3, 3, 2, 100*mult); addMA( 3, 3, 3, 100*mult); addMA( 3, 3, 4, 100*mult); addMA( 3, 3, 5, 100*mult); addMA( 3, 3, 6, 100*mult); addMA( 3, 3, 7, 100*mult); addMA( 3, 3, 8, 100*mult); addMA( 3, 3, 9, 100*mult); addMA( 3, 3, 10, 100*mult); addMA( 3, 3, 11, 100*mult); addMA( 3, 3, 12, 100*mult); addMA( 3, 3, 13, 100*mult); addMA( 3, 3, 14, 100*mult); addMA( 3, 3, 15, 100*mult); addMA( 3, 3, 16, 100*mult); int temp; allocatemakesharedframesempty( 2*targetnprocessors+4); makesharedframesempty(); for (temp=1;temp<=tasks[1].nsegments_of_stage[2];temp++) { addelementtosharedframes( 1, 1, 1, temp-1, 1, 2, temp, 0); } for (temp=1;temp<=tasks[1].nsegments_of_stage[2];temp++) { addelementtosharedframes( 1, 3, 1, temp-1, 1, 2, temp, 1); } addelementtosharedframes( 3, 1, 1, 0, 3, 2, 1, 0); addelementtosharedframes( 3, 1, 1, 1, 3, 2, 2, 0); addelementtosharedframes( 3, 3, 1, 0, 3, 2, 1, 1); addelementtosharedframes( 3, 3, 1, 1, 3, 2, 2, 1); setINO(970); } // this is like setsystem1 but with fewer pages (4 pages instead of 16 pages) void setsystem1_smaller(int targetnprocessors, double C12, double mult) { setmethod(3); setGUROBITIMEOUTPARAMETER(3600.0); setK(20); allocateTaskset(3); setNumProcessors( targetnprocessors); setSpeed( 1.0); setH(32); setB(16); // setHWSHARE(1.0/4.0); setMEMCAP( 524288); MBCF = 1500000000; settrrdinbusclockcycles( 4); settfawinbusclockcycles( 20); setwlinbusclockcycles( 7); setblinbusclockcycles( 8); settwtrinbusclockcycles( 5); setclinbusclockcyclessettwtrinbusclockcycles( 9); settrpinbusclockcycles( 9); settrcdinbusclockcycles( 9); settwrinbusclockcycles( 10); setNre(12); addtask( 1, 0.100, 0.100, 3); addstage( 1, 1, 1, 0.001, 4); addMA( 1, 1, 0, 100*mult); addMA( 1, 1, 1, 100*mult); addMA( 1, 1, 2, 100*mult); addMA( 1, 1, 3, 100*mult); addstage( 1, 2, targetnprocessors, C12, 4); addMA( 1, 2, 0, 1000*mult); addMA( 1, 2, 1, 1000*mult); addMA( 1, 2, 2, 1000*mult); addMA( 1, 2, 3, 1000*mult); addstage( 1, 3, 1, 0.001, 4); addMA( 1, 3, 0, 100*mult); addMA( 1, 3, 1, 100*mult); addMA( 1, 3, 2, 100*mult); addMA( 1, 3, 3, 100*mult); addtask( 2, 0.010, 0.010, 1); addstage( 2, 1, 1, 0.002, 4); addMA( 2, 1, 0, 100*mult); addMA( 2, 1, 1, 100*mult); addMA( 2, 1, 2, 100*mult); addMA( 2, 1, 3, 100*mult); addtask( 3, 0.100, 0.044, 3); addstage( 3, 1, 1, 0.002, 4); addMA( 3, 1, 0, 100*mult); addMA( 3, 1, 1, 100*mult); addMA( 3, 1, 2, 100*mult); addMA( 3, 1, 3, 100*mult); addstage( 3, 2, 2, 0.006, 4); addMA( 3, 2, 0, 100*mult); addMA( 3, 2, 1, 100*mult); addMA( 3, 2, 2, 100*mult); addMA( 3, 2, 3, 100*mult); addstage( 3, 3, 1, 0.002, 4); addMA( 3, 3, 0, 100*mult); addMA( 3, 3, 1, 100*mult); addMA( 3, 3, 2, 100*mult); addMA( 3, 3, 3, 100*mult); int temp; allocatemakesharedframesempty( 2*targetnprocessors+4); makesharedframesempty(); for (temp=1;temp<=tasks[1].nsegments_of_stage[2];temp++) { addelementtosharedframes( 1, 1, 1, temp-1, 1, 2, temp, 0); } for (temp=1;temp<=tasks[1].nsegments_of_stage[2];temp++) { addelementtosharedframes( 1, 3, 1, temp-1, 1, 2, temp, 1); } addelementtosharedframes( 3, 1, 1, 0, 3, 2, 1, 0); addelementtosharedframes( 3, 1, 1, 1, 3, 2, 2, 0); addelementtosharedframes( 3, 3, 1, 0, 3, 2, 1, 1); addelementtosharedframes( 3, 3, 1, 1, 3, 2, 2, 1); setINO(970); } void readsystemfromfile( FILE* f) { int i; int j; int p; int temp; int iprime; int jprime; int gprime; int pprime; int iprimeprime; int jprimeprime; int gprimeprime; int pprimeprime; int tempint1; int tempint2; double tempdouble1; double tempdouble2; fscanf(f,"%d", &method); fscanf(f,"%lf", &GUROBITIMEOUTPARAMETER); fscanf(f,"%d", &K); fscanf(f,"%d", &nprocessors); fscanf(f,"%lf", &s); fscanf(f,"%d", &H); fscanf(f,"%d", &B); // fscanf(f,"%lf", &HWSHARE); fscanf(f,"%d", &MEMCAP); // CAP = HWSHARE * MEMCAP / (H*B); CAP = MEMCAP / (H*B); fscanf(f,"%lf", &MBCF); fscanf(f,"%lf", &trrd ); fscanf(f,"%lf", &tfaw ); fscanf(f,"%lf", &wl ); fscanf(f,"%lf", &bl ); fscanf(f,"%lf", &twtr ); fscanf(f,"%lf", &cl ); fscanf(f,"%lf", &trp ); fscanf(f,"%lf", &trcd ); fscanf(f,"%lf", &twr ); setmemoryparameters(); fscanf(f,"%d", &Nre ); fscanf(f,"%d", &tempint1); allocateTaskset( tempint1); for (i=1;i<=ntasks;i++) { fscanf(f,"%lf", &tempdouble1 ); fscanf(f,"%lf", &tempdouble2 ); fscanf(f,"%d", &tempint1 ); addtask( i, tempdouble1, tempdouble2, tempint1); for (j=1;j<=tasks[i].nstages;j++) { fscanf(f,"%d", &tempint1 ); fscanf(f,"%lf", &tempdouble1 ); fscanf(f,"%d", &tempint2 ); addstage( i, j, tempint1, tempdouble1, tempint2); for (p=0;p<=tasks[i].memoryaccessesdescription[j].npages-1;p++) { fscanf(f,"%d", &tempint1 ); addMA( i, j, p, tempint1); } } } fscanf(f,"%d", &tempint1 ); allocatemakesharedframesempty( tempint1); for (temp=1;temp<=tempint1;temp++) { fscanf(f,"%d %d %d %d %d %d %d %d", &iprime, &jprime, &gprime, &pprime, &iprimeprime, &jprimeprime, &gprimeprime, &pprimeprime ); addelementtosharedframes( iprime, jprime, gprime, pprime, iprimeprime, jprimeprime, gprimeprime, pprimeprime ); } fscanf(f,"%d", &INO ); } void printsystemtofile( FILE* f) { int i; int j; int p; int temp; int iprime; int jprime; int gprime; int pprime; int iprimeprime; int jprimeprime; int gprimeprime; int pprimeprime; fprintf(f,"%d \n", method); fprintf(f,"%lf \n", GUROBITIMEOUTPARAMETER); fprintf(f,"\n"); fprintf(f,"%d \n", K); fprintf(f,"%d \n", nprocessors); fprintf(f,"%lf \n", s); fprintf(f,"%d\n", H); fprintf(f,"%d\n", B); // fprintf(f,"%lf\n", HWSHARE); fprintf(f,"%d\n", MEMCAP); fprintf(f,"%lf\n", MBCF ); fprintf(f,"%lf\n", trrd ); fprintf(f,"%lf\n", tfaw ); fprintf(f,"%lf\n", wl ); fprintf(f,"%lf\n", bl ); fprintf(f,"%lf\n", twtr ); fprintf(f,"%lf\n", cl ); fprintf(f,"%lf\n", trp ); fprintf(f,"%lf\n", trcd ); fprintf(f,"%lf\n", twr ); fprintf(f,"%d\n", Nre ); fprintf(f,"\n"); fprintf(f,"%d\n", ntasks); fprintf(f,"\n"); for (i=1;i<=ntasks;i++) { fprintf(f,"%lf ", tasks[i].T ); fprintf(f,"%lf ", tasks[i].D ); fprintf(f,"%d\n", tasks[i].nstages ); for (j=1;j<=tasks[i].nstages;j++) { fprintf(f,"%d %lf %d\n", tasks[i].nsegments_of_stage[j], tasks[i].exec_of_stage[j], tasks[i].memoryaccessesdescription[j].npages); for (p=0;p<=tasks[i].memoryaccessesdescription[j].npages-1;p++) { fprintf(f,"%d ", tasks[i].memoryaccessesdescription[j].MA[p] ); } fprintf(f,"\n"); } fprintf(f,"\n"); } fprintf(f,"%d\n", nelements_in_sharedframes ); for (temp=1;temp<=nelements_in_sharedframes;temp++) { get_element_of_sharedframes( temp-1, &iprime, &jprime, &gprime, &pprime, &iprimeprime, &jprimeprime, &gprimeprime, &pprimeprime ); fprintf(f,"%d %d %d %d %d %d %d %d\n", iprime, jprime, gprime, pprime, iprimeprime, jprimeprime, gprimeprime, pprimeprime ); } fprintf(f,"%d\n", INO ); } void printsystemtofilewithname( char* fn) { FILE* f; f = fopen( fn, "w"); printsystemtofile( f); fclose( f); } void printsystemtofilewithname_and_state_success( char* fn, int success) { FILE* f; f = fopen( fn, "w"); printsystemtofile( f); fprintf( f, "success = %d\n", success); fclose( f); } void readsystem(char* fn) { FILE* f; if (fn==NULL) { setsystem1( 4, 0.005, 0); } else { f = fopen( fn, "r"); readsystemfromfile( f); fclose( f); } compute_derived_parameters(); } void print_task( int i) { int j; printf("T[%d] = %lf\n", i, tasks[i].T); printf("D[%d] = %lf\n", i, tasks[i].D); printf("nstages[%d] = %d\n", i, tasks[i].nstages); for (j=1;j<=tasks[i].nstages;j++) { printf(" nseg[%d][%d] = %d\n", i, j, tasks[i].nsegments_of_stage[j]); printf(" c[%d][%d] = %lf\n", i, j, tasks[i].exec_of_stage[j]); } } void print_platform_parameters() { printf("m = %d, s = %lf\n", nprocessors, s); printf("\n"); } void print_taskset_parameters() { int i; printf("n = %d\n", ntasks); for (i=1;i<=ntasks;i++) { print_task( i); } printf("P = %lf\n", P); } void printsystem() { print_platform_parameters(); print_taskset_parameters(); printmemoryparameters(); } void initializesystem() { readsystem( inputfilename); } #if CALLGUROBITHROUGHAPI GRBenv *env = NULL; GRBmodel *model = NULL; #else #endif int error = 0; double* sol; int nelements_of_constr; int* ind; double* val; char constraint_sense; double constraint_rhs; int nelements_of_obj; double* obj; char* vtype; char** varnames; int optimstatus; double objval; struct myvarstruct { int index; char vtype; char varname[MAXVARIABLESTRINGLENGTH]; }; int nvars_in_myvars; struct myvarstruct* myvars; void allocate_variables_needed_for_interacting_with_Gurobi() { sol = (double*) malloc(sizeof(double)*MAXNVARS); ind = (int*) malloc(sizeof(int)*MAXNVARS); val = (double*) malloc(sizeof(double)*MAXNVARS); obj = (double*) malloc(sizeof(double)*MAXNVARS); vtype = (char*) malloc(sizeof(char)*MAXNVARS); varnames = (char**) malloc(sizeof(char*)*MAXNVARS); myvars = (struct myvarstruct*) malloc(sizeof(struct myvarstruct)*MAXNVARS); if (sol==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. sol\n"); exit( -1); } if (ind==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. ind\n"); exit( -1); } if (val==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. val\n"); exit( -1); } if (obj==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. obj\n"); exit( -1); } if (vtype==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. vtype\n"); exit( -1); } if (varnames==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. varnames\n"); exit( -1); } if (myvars==NULL) { printf("malloc failure in allocate_variables_needed_for_interacting_with_Gurobi. myvars\n"); exit( -1); } } void free_variables_needed_for_interacting_with_Gurobi() { free( sol); free( ind); free( val); free( obj); free( vtype); free( varnames); free( myvars); sol = NULL; ind = NULL; val = NULL; obj = NULL; vtype = NULL; varnames = NULL; myvars = NULL; } int getUBNOMR() { int i; int j; int temp; int local_counter; local_counter = 0; for (i=1;i<=ntasks;i++) { temp = 0; for (j=1;j<=tasks[i].nstages;j++) { temp = maxint2(temp, tasks[i].nsegments_of_stage[j] ); } local_counter = local_counter + temp; } return local_counter; } int getLIMIT1() { int temp; temp = minint2(nprocessors-1,getUBNOMR()-1); return temp; } int getLIMIT2() { int temp; temp = minint2(nprocessors-1,getUBNOMR()-1)+Nre; return temp; } double getmaxD() { int i; double maxD; maxD = tasks[1].D; for (i=1;i<=ntasks;i++) { if (maxD < tasks[i].D) { maxD = tasks[i].D; } } return maxD; } int getnumberofmemoryaccessesofajob(int iprime) { int jprime; int gprime; int pprime; int counter; counter = 0; for (jprime=1;jprime<=tasks[iprime].nstages;jprime++) { for (gprime=1;gprime<=tasks[iprime].nsegments_of_stage[jprime];gprime++) { for (pprime=0;pprime<=tasks[iprime].memoryaccessesdescription[jprime].npages-1;pprime++) { counter = counter + tasks[iprime].memoryaccessesdescription[jprime].MA[pprime]; } } } return counter; } double getmaxnmemoryaccessesofsystem() { int i; int iprime; int largestsofar; int counter; int njobs; largestsofar = 0; for (i=1;i<=ntasks;i++) { counter = 0; for (iprime=1;iprime<=ntasks;iprime++) { njobs = ceil( tasks[i].D/(tasks[iprime].T))+1; counter = counter + njobs * getnumberofmemoryaccessesofajob(iprime); } largestsofar = maxint2( largestsofar, counter); } return largestsofar; } double getBIGparteq69() { return getmaxnmemoryaccessesofsystem()*(1.0/SCALINGFACTORNACCESSES);; } double getBIGparteq70() { return maxdouble2(1.0,Lconf+Linter)*getBIGparteq69(); } double getBIGparteq71() { return (P+getmaxD())*nprocessors*maxdouble2(1,s); } double getBIG() { return maxdouble2( getBIGparteq70(), getBIGparteq71() ); } double getBIGfor_x_and_o_for_a_given_i_and_j(int i, int j) { return ((tasks[i].memoryaccessesdescription[j].npages)* B); } double getBIGfor_util_constraints() { return nprocessors; } void addloadfactorofcells() { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"loadfactorofcells"); nvars_in_myvars = nvars_in_myvars + 1; } void addutilconsideringcont() { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"utilconsideringcont"); nvars_in_myvars = nvars_in_myvars + 1; } void addloadofdeadline(int i) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"loadofdeadline_%d", i); nvars_in_myvars = nvars_in_myvars + 1; } void addmyobj() { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"myobj"); nvars_in_myvars = nvars_in_myvars + 1; } #if CALLGUROBITHROUGHAPI #else void myaddconstr( int nelements_of_constr, int* ind, double* val, char constraint_sense, double constraint_rhs) { int tempindex; int therewasazero; int indexofzero; therewasazero = 1; while (therewasazero) { therewasazero = 0; tempindex = 0; while (tempindex0) { fprintf( gurobithroughcommandlinelpfile, " %20.15lf %s", val[tempindex], myvars[ind[tempindex]].varname ); } else { fprintf( gurobithroughcommandlinelpfile, " - %20.15lf %s", -val[tempindex], myvars[ind[tempindex]].varname ); } } } } else { if (val[tempindex]==1.0) { fprintf( gurobithroughcommandlinelpfile, " + %s", myvars[ind[tempindex]].varname ); } else { if (val[tempindex]==-1.0) { fprintf( gurobithroughcommandlinelpfile, " - %s", myvars[ind[tempindex]].varname ); } else { if (val[tempindex]>0) { fprintf( gurobithroughcommandlinelpfile, " + %20.15lf %s", val[tempindex], myvars[ind[tempindex]].varname ); } else { fprintf( gurobithroughcommandlinelpfile, " - %20.15lf %s", -val[tempindex], myvars[ind[tempindex]].varname ); } } } } } if (constraint_sense=='=') { fprintf( gurobithroughcommandlinelpfile, " = "); } else { if (constraint_sense=='<') { fprintf( gurobithroughcommandlinelpfile, " <= "); } else { if (constraint_sense=='>') { fprintf( gurobithroughcommandlinelpfile, " >= "); } else { printf("Error in myaddconstr\n"); exit(-1); } } } fprintf( gurobithroughcommandlinelpfile, " %20.15lf", constraint_rhs); fprintf( gurobithroughcommandlinelpfile, "\n"); } #endif void addconstraintutilconsideringcont() { int index; char searchstr[200]; int i; nelements_of_constr = 0; for (i=1;i<=ntasks;i++) { sprintf(searchstr,"cu_%d", i); index = locatevariablenameinmyvars(searchstr); ind[nelements_of_constr] = index; val[nelements_of_constr] = (1.0/tasks[i].T)/(nprocessors*s); nelements_of_constr = nelements_of_constr + 1; } sprintf(searchstr,"utilconsideringcont"); index = locatevariablenameinmyvars(searchstr); ind[nelements_of_constr] = index; val[nelements_of_constr] = -1; nelements_of_constr = nelements_of_constr + 1; constraint_sense = GRB_EQUAL; constraint_rhs = 0; #if CALLGUROBITHROUGHAPI error = GRBaddconstr( model, nelements_of_constr, ind, val, constraint_sense, constraint_rhs, NULL ); if (error) printf("Error in addconstraintutilconsideringcont\n"); exit(-1); #else myaddconstr( nelements_of_constr, ind, val, constraint_sense, constraint_rhs ); #endif } void addconstraintloadofdeadline(int i) { int index; char searchstr[200]; int iprime; double num; double denom; nelements_of_constr = 0; for (iprime=1;iprime<=ntasks;iprime++) { sprintf(searchstr,"cu_%d", iprime); index = locatevariablenameinmyvars(searchstr); num = maxdouble2( floor((tasks[i].D - tasks[iprime].D)/tasks[iprime].T)+1, 0); denom = nprocessors * s * tasks[i].D; if (num!=0.0) { ind[nelements_of_constr] = index; val[nelements_of_constr] = num / denom; nelements_of_constr = nelements_of_constr + 1; } } sprintf(searchstr,"loadofdeadline_%d", i); index = locatevariablenameinmyvars(searchstr); ind[nelements_of_constr] = index; val[nelements_of_constr] = -1; nelements_of_constr = nelements_of_constr + 1; constraint_sense = GRB_EQUAL; constraint_rhs = 0; #if CALLGUROBITHROUGHAPI error = GRBaddconstr( model, nelements_of_constr, ind, val, constraint_sense, constraint_rhs, NULL ); if (error) printf("Error in addconstrainloadofdeadline\n"); exit(-1); #else myaddconstr( nelements_of_constr, ind, val, constraint_sense, constraint_rhs ); #endif } void addconstraintlowerboundonmyobj(char* s) { int index; char searchstr[200]; nelements_of_constr = 0; strcpy(searchstr,s); index = locatevariablenameinmyvars(searchstr); ind[nelements_of_constr] = index; val[nelements_of_constr] = 1; nelements_of_constr = nelements_of_constr + 1; sprintf(searchstr,"myobj"); index = locatevariablenameinmyvars(searchstr); ind[nelements_of_constr] = index; val[nelements_of_constr] = -1; nelements_of_constr = nelements_of_constr + 1; constraint_sense = GRB_LESS_EQUAL; constraint_rhs = 0; #if CALLGUROBITHROUGHAPI error = GRBaddconstr( model, nelements_of_constr, ind, val, constraint_sense, constraint_rhs, NULL ); if (error) printf("Error in addconstraintlowerboundonmyobj\n"); exit(-1); #else myaddconstr( nelements_of_constr, ind, val, constraint_sense, constraint_rhs ); #endif } void addconstraintmyobj() { int i; char tempstr[200]; addconstraintlowerboundonmyobj("loadfactorofcells"); addconstraintlowerboundonmyobj("utilconsideringcont"); for (i=1;i<=ntasks;i++) { sprintf(tempstr,"loadofdeadline_%d", i); addconstraintlowerboundonmyobj(tempstr); } } void addcuij() { int i; int j; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"cu_%d_%d", i,j); nvars_in_myvars = nvars_in_myvars + 1; } } } void addcui() { int i; for (i=1;i<=ntasks;i++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"cu_%d", i); nvars_in_myvars = nvars_in_myvars + 1; } } void addetaui() { int i; for (i=1;i<=ntasks;i++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"etau_%d", i); nvars_in_myvars = nvars_in_myvars + 1; } } void addbspuij() { int i; int j; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"bspu_%d_%d", i,j); nvars_in_myvars = nvars_in_myvars + 1; } } } void addspuij() { int i; int j; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"spu_%d_%d", i,j); nvars_in_myvars = nvars_in_myvars + 1; } } } void addtprimes() { int iprime; int qprime; int jprime; int fprime; int k; for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname, "t_%d_%d_%d_%d_%d", iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } void addI() { int i; int q; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (q=0;q<=(P/tasks[i].T);q++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname, "I_%d_%d_%d_%d_%d_%d_%d", i,q,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } } void addr() { int i; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname, "r_%d_%d_%d_%d_%d_%d", i,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } void addaj() { int i; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"aj_%d_%d_%d_%d_%d_%d", i,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } void addwjf() { int i; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname, "wjf_%d_%d_%d_%d_%d_%d", i,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } void addwjsf() { int i; int j; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (j=0;j<=tasks[i].nstages-1;j++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname, "wjsf_%d_%d_%d_%d_%d_%d_%d", i,j,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } } void addwjss() { int i; int j; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (j=0;j<=tasks[i].nstages-1;j++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname, "wjss_%d_%d_%d_%d_%d_%d_%d", i,j,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } } void addwjt() { int i; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname, "wjt_%d_%d_%d_%d_%d_%d", i,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } void addw() { int i; int iprime; int qprime; int jprime; int fprime; int k; for (i=1;i<=ntasks;i++) { for (iprime=1;iprime<=ntasks;iprime++) { for (qprime=1;qprime<=(P/tasks[iprime].T);qprime++) { for (jprime=0;jprime<=tasks[iprime].nstages-1;jprime++) { for (fprime=0;fprime<=1;fprime++) { for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"w_%d_%d_%d_%d_%d_%d", i,iprime,qprime,jprime,fprime,k); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } void addwi() { int k; for (k=1;k<=K;k++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"wi_%d", k); nvars_in_myvars = nvars_in_myvars + 1; } } void addmb() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"mb_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addmmb() { int i; int iprime; int jprime; int gprime; int b; for (i=1;i<=ntasks;i++) { for (iprime=1;iprime<=ntasks;iprime++) { for (jprime=1;jprime<=tasks[iprime].nstages;jprime++) { for (gprime=1;gprime<=tasks[iprime].nsegments_of_stage[jprime];gprime++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"mmb_%d_%d_%d_%d_%d", i,iprime,jprime,gprime,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } void addmmbo() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"mmbo_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addo() { int i; int j; int g; int p; int h; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (p=0;p<=tasks[i].memoryaccessesdescription[j].npages-1;p++) { for (h=0;h<=H-1;h++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"o_%d_%d_%d_%d_%d_%d", i,j,g,p,h,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } } } void addino() { int h; int b; for (h=0;h<=H-1;h++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_INTEGER; sprintf( myvars[nvars_in_myvars].varname,"ino_%d_%d", h,b); nvars_in_myvars = nvars_in_myvars + 1; } } } void addx() { int i; int j; int g; int h; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (h=0;h<=H-1;h++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"x_%d_%d_%d_%d", i,j,g,h); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addcm() { int i; int j; int g; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"cm_%d_%d_%d", i,j,g); nvars_in_myvars = nvars_in_myvars + 1; } } } } void addse() { int i; int j; int g; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"se_%d_%d_%d", i,j,g); nvars_in_myvars = nvars_in_myvars + 1; } } } } void addcoat() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"coat_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addoao() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"oao_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addbc1() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"bc1_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addbc2() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"bc2_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addbc3() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"bc3_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addbc4() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"bc4_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addoat() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_CONTINUOUS; sprintf( myvars[nvars_in_myvars].varname,"oat_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } void addbu() { int i; int j; int g; int b; for (i=1;i<=ntasks;i++) { for (j=1;j<=tasks[i].nstages;j++) { for (g=1;g<=tasks[i].nsegments_of_stage[j];g++) { for (b=0;b<=B-1;b++) { myvars[nvars_in_myvars].index = nvars_in_myvars; myvars[nvars_in_myvars].vtype = GRB_BINARY; sprintf( myvars[nvars_in_myvars].varname,"bu_%d_%d_%d_%d", i,j,g,b); nvars_in_myvars = nvars_in_myvars + 1; } } } } } int locatevariablenameinmyvars(char* searchstr) { int tempindex; for (tempindex=0;tempindex1-0.00001) { printf("Something is a little strange but not necessarily wrong in addconstraintsfromfirstsolution. Place 2. temp=%d sol[temp]=%lf\n", temp, sol[temp]); } else { printf("Something is wrong in addconstraintsfromfirstsolution. Place 3. temp=%d sol[temp]=%lf\n", temp, sol[temp]); exit(-1); } } } } } if (strncmp(varnames[temp],"x_",2)==0) { if (sol[temp]==1.0) { addaconstraint( temp, 1.0); } else { if (sol[temp]==0.0) { addaconstraint( temp, 0.0); } else { if (sol[temp]<0.00001) { printf("Something is a little strange but not necessarily wrong in addconstraintsfromfirstsolution. Place 4. temp=%d sol[temp]=%lf\n", temp, sol[temp]); } else { if (sol[temp]>1-0.00001) { printf("Something is a little strange but not necessarily wrong in addconstraintsfromfirstsolution. Place 5. temp=%d sol[temp]=%lf\n", temp, sol[temp]); } else { printf("Something is wrong in addconstraintsfromfirstsolution. Place 6. temp=%d sol[temp]=%lf\n", temp, sol[temp]); exit(-1); } } } } } if (strncmp(varnames[temp],"ino_",4)==0) { addaconstraint( temp, sol[temp]); } } } #else void addconstraintsfromfirstsolution_onlpfile(char* fn_with_solution) { char tempstr[200]; char tempvarname[200]; double tempvalue; int temp; FILE* f; f = fopen( fn_with_solution, "r"); fgets( tempstr, 200,f ); while (tempstr[0]=='#') { fgets( tempstr, 200, f); } // now we have a string that does not start with # do { sscanf( tempstr, "%s %lf", tempvarname, &tempvalue); temp = locatevariablenameinmyvars(tempvarname); sol[temp] = tempvalue; } while (fgets( tempstr, 200, f)!=NULL); fclose( f); // code below does the same thing as addconstraintsfromfirstsolution for (temp=0;temp1-0.00001) { printf("Something is a little strange but not necessarily wrong in addconstraintsfromfirstsolution. Place 2. temp=%d sol[temp]=%lf\n", temp, sol[temp]); } else { printf("Something is wrong in addconstraintsfromfirstsolution. Place 3. temp=%d sol[temp]=%lf\n", temp, sol[temp]); exit(-1); } } } } } if (strncmp(varnames[temp],"x_",2)==0) { if (sol[temp]==1.0) { addaconstraint( temp, 1.0); } else { if (sol[temp]==0.0) { addaconstraint( temp, 0.0); } else { if (sol[temp]<0.00001) { printf("Something is a little strange but not necessarily wrong in addconstraintsfromfirstsolution. Place 4. temp=%d sol[temp]=%lf\n", temp, sol[temp]); } else { if (sol[temp]>1-0.00001) { printf("Something is a little strange but not necessarily wrong in addconstraintsfromfirstsolution. Place 5. temp=%d sol[temp]=%lf\n", temp, sol[temp]); } else { printf("Something is wrong in addconstraintsfromfirstsolution. Place 6. temp=%d sol[temp]=%lf\n", temp, sol[temp]); exit(-1); } } } } } if (strncmp(varnames[temp],"ino_",4)==0) { addaconstraint( temp, sol[temp]); } } } #endif void setwik() { int temp; for (temp=0;tempMAXNELEMENTSINMYBUFFEROFVALUES) { printf("Error in mybufferofovalues_setup. Too many elements."); exit(-1); } } } fclose( f); } double mybufferofovalues_getvalue( char* searchstr) { int index; int found; double v; found = 0; for (index=0;index=hprimeprime)) { add_constraint_to_break_symmetry_a(iprime,jprime,gprime,hprime,iprimeprime,jprimeprime,gprimeprime,hprimeprime); #if CALLGUROBITHROUGHAPI error = GRBaddconstr( model, nelements_of_constr, ind, val, constraint_sense, constraint_rhs, NULL ); if (error) { printf("Error in addalltheconstraintsofeq50\n"); exit(-1); } #else myaddconstr( nelements_of_constr, ind, val, constraint_sense, constraint_rhs ); #endif } } } } } } } } } } double gettwopowerabove(double tempinput) { double lb; double ub; lb = 1.0; while (tempinputub) { ub = ub*2; } return ub; } void computeSCALINGFACTORNACCESSES() { double t; double t2; double t3; double t4; SCALINGFACTORNACCESSES = 1; if (getBIGparteq69()>0) { t = getBIGparteq70(); t2 = getBIGparteq71(); t3 = t/t2; t4 = gettwopowerabove(t3); SCALINGFACTORNACCESSES = t4; } else { SCALINGFACTORNACCESSES = 8388608; } } #if CALLGUROBITHROUGHAPI #else void write_the_end_of_lp_file( FILE* f) { int tempindex; fprintf( f, "Binaries\n"); for (tempindex=0;tempindex=2) { addalltheconstraints_to_break_symmetry(); } #if CALLGUROBITHROUGHAPI if (method==3) { error = GRBupdatemodel( model); if (error) goto QUIT; error = GRBwrite( model, "temp_intermediate_results_method4.lp"); error = GRBoptimize(model); if (error) goto QUIT; error = GRBupdatemodel( model); if (error) goto QUIT; error = GRBgetintattr( model, GRB_INT_ATTR_STATUS, &optimstatus); if (error) goto QUIT; error = GRBgetdblattr( model, GRB_DBL_ATTR_OBJVAL, &objval); if (error) goto QUIT; if (optimstatus!=GRB_OPTIMAL) { error = GRBgetintattr( model, GRB_INT_ATTR_SOLCOUNT, &localsolcount); if (error) goto QUIT; while (localsolcount==0) { error = GRBoptimize(model); if (error) goto QUIT; error = GRBupdatemodel( model); if (error) goto QUIT; error = GRBgetintattr( model, GRB_INT_ATTR_STATUS, &optimstatus); if (error) goto QUIT; error = GRBgetdblattr( model, GRB_DBL_ATTR_OBJVAL, &objval); if (error) goto QUIT; error = GRBgetintattr( model, GRB_INT_ATTR_SOLCOUNT, &localsolcount); if (error) goto QUIT; } old_optimstatus = optimstatus; old_objval = objval; error = GRBoptimize(model); if (error) goto QUIT; error = GRBupdatemodel( model); if (error) goto QUIT; error = GRBgetintattr( model, GRB_INT_ATTR_STATUS, &optimstatus); if (error) goto QUIT; error = GRBgetdblattr( model, GRB_DBL_ATTR_OBJVAL, &objval); if (error) goto QUIT; while ( (optimstatus!=GRB_OPTIMAL) && (objval=old_objval) // so we do not need to continue with optimization to find a good memory allocation error = GRBsetdblparam( env, GRB_DBL_PAR_TIMELIMIT, GRB_INFINITY); if (error) goto QUIT; error = GRBupdatemodel( model); if (error) goto QUIT; GRBwrite( model, "temp_intermediate_results_method4.sol" ); error = GRBgetdblattrarray( model, GRB_DBL_ATTR_X, 0, nelements_of_obj, sol); if (error) goto QUIT; addconstraintsfromfirstsolution(); } setcoefficientformyobjtozero_in_objectivefunction(); error = GRBupdatemodel( model); if (error) goto QUIT; #else if (method==3) { fclose( gurobithroughcommandlinelpfile); my_sleep( 5); sprintf( tempstr, "cp %s firstphase.lp", gurobithroughcommandlinelpfilename); system( tempstr); FILE* f; f = fopen("firstphase.lp","a"); write_the_end_of_lp_file( f); fclose( f); my_sleep( 5); go_through_file_and_remove_variables_that_are_not_used_in_first_phase_of_method3("firstphase.lp"); my_sleep( 5); gurobithroughcommandlinepyfile = fopen( "firstphase.py", "w"); // this is writing for append at the end of the file fprintf( gurobithroughcommandlinepyfile, "from gurobipy import *\n"); fprintf( gurobithroughcommandlinepyfile, "m = read('firstphase.lp')\n"); fprintf( gurobithroughcommandlinepyfile, "m.setParam('MIPFOCUS',%d)\n", myGRB_INT_PAR_MIPFOCUS ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('AGGREGATE',%d)\n", myGRB_INT_PAR_AGGREGATE ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('FEASIBILITYTOL',%25.15lf)\n", myGRB_DBL_PAR_FEASIBILITYTOL ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('INTFEASTOL',%25.15lf)\n", myGRB_DBL_PAR_INTFEASTOL ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('MARKOWITZTOL',%25.15lf)\n", myGRB_DBL_PAR_MARKOWITZTOL ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('QUAD',%d)\n", myGRB_INT_PAR_QUAD ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('NUMERICFOCUS',%d)\n", myGRB_INT_PAR_NUMERICFOCUS ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('HEURISTICS',%25.15lf)\n", myGRB_DBL_PAR_HEURISTICS ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('FEASRELAXBIGM',%25.15lf)\n", myGRB_DBL_PAR_FEASRELAXBIGM ); fprintf( gurobithroughcommandlinepyfile, "m.setParam('TIMELIMIT',%25.15lf)\n", GUROBITIMEOUTPARAMETER ); fprintf( gurobithroughcommandlinepyfile, "m.optimize()\n"); fprintf( gurobithroughcommandlinepyfile, "m.update()\n"); fprintf( gurobithroughcommandlinepyfile, "if m.status != GRB.status.OPTIMAL:\n"); fprintf( gurobithroughcommandlinepyfile, " while (m.solCount==0):\n"); fprintf( gurobithroughcommandlinepyfile, " m.optimize()\n"); fprintf( gurobithroughcommandlinepyfile, " m.update()\n"); fprintf( gurobithroughcommandlinepyfile, " old_optimstatus = m.status\n"); fprintf( gurobithroughcommandlinepyfile, " old_objval = m.objVal\n"); fprintf( gurobithroughcommandlinepyfile, " m.optimize()\n"); fprintf( gurobithroughcommandlinepyfile, " m.update()\n"); fprintf( gurobithroughcommandlinepyfile, " while ( (m.status!=GRB.status.OPTIMAL) and (m.objVal0) { sigmacur = sigmafornewstage; } else { nextsigma = sigmacur + (schedulability_analysis_without_considering_memory_contention_evalf(sigmacur,t)/(schedulability_analysis_without_considering_memory_contention_evalf(sigmacur,t)-schedulability_analysis_without_considering_memory_contention_evalf(sigmafornewstage,t))) * (sigmafornewstage-sigmacur); foundsigmasought = 1; } } } if (foundsigmasought==1) { *pnextsigma = sigmacur; *pvalidnextsigma = 1; } else { *pvalidnextsigma = 0; } } int schedulability_analysis_without_considering_memory_contention_perform_schedulability_analysis() { double sigma; double t; int foundwitness; int validsigma; double nextt; int validnextt; double nextsigma; int eval; int validnextsigma; schedulability_analysis_without_considering_memory_contention_compute_derived_parameters(); sigma = schedulability_analysis_without_considering_memory_contention_deltamax; t = 0.0; foundwitness = 0; validsigma = (sigma/s<=(nprocessors*s-schedulability_analysis_without_considering_memory_contention_U)/((nprocessors-1)*s)); while ((foundwitness==0) && (validsigma==1)) { schedulability_analysis_without_considering_memory_contention_getnextt( sigma, t, &nextt, &validnextt); eval = 1; while ((validnextt==1) && (eval==1)) { t = nextt; eval = schedulability_analysis_without_considering_memory_contention_evaluate_Eq_14( sigma, t); schedulability_analysis_without_considering_memory_contention_getnextt( sigma, t, &nextt, &validnextt); } if (eval==1) { foundwitness = 1; } else { schedulability_analysis_without_considering_memory_contention_getnextsigma( sigma, t, &nextsigma, &validnextsigma); if ( (validnextsigma==1) && (nextsigma/s<=(nprocessors*s-schedulability_analysis_without_considering_memory_contention_U)/((nprocessors-1)*s)) ) { sigma = nextsigma; validsigma = 1; } else { validsigma = 0; } } } if (foundwitness==1) { printf("Schedulable. Witness: %lf\n", sigma); } else { printf("Unschedulable\n"); } return foundwitness; } void schedulability_analysis_without_considering_memory_contention_getnextt2( double t, double* pnextt, int* pvalidnextt) { double maxttotest; int i; int j; int jobindex; int maxjobindex; double value_of_t; *pvalidnextt = 0; maxttotest = schedulability_analysis_without_considering_memory_contention_getmaxttotest( 0.0); maxttotest = mindouble2( P, maxttotest); for (i=1;i<=ntasks;i++) { maxjobindex = ceil(maxttotest/(tasks[i].T))+1; for (jobindex=1;jobindex<=maxjobindex;jobindex++) { for (j=0;j<=tasks[i].nstages;j++) { value_of_t = (jobindex-1)*(tasks[i].T)+(tasks[i].D)-schedulability_analysis_without_considering_memory_contention_sumCfirststages(i,j); if ((tnprocessors*s) { return 0; } t = 0.0; schedulability_analysis_without_considering_memory_contention_getnextt2( t, &nextt, &validnextt); eval = 1; while ((validnextt==1) && (eval==1)) { t = nextt; eval = schedulability_analysis_without_considering_memory_contention_evaluate_this_point( t); schedulability_analysis_without_considering_memory_contention_getnextt2( t, &nextt, &validnextt); } if (eval==1) { foundwitness = 1; } else { foundwitness = 0; } schedulability_analysis_without_considering_memory_contention_do_freeing_up_memory(); if (foundwitness==1) { printf("Schedulable.\n"); } else { printf("Unschedulable\n"); } return foundwitness; } void generate_figure_5_in_paper() { setsystem1( 4, 0.040, 1.0); compute_derived_parameters(); printsystem(); } #if COMPILEMSVS || COMPILEWIN32 unsigned long long diff_us_timeval(struct timeval *x, struct timeval *y) { unsigned long long amillion = 1000000; unsigned long long u = ((x->tv_sec * amillion) + x->tv_usec); unsigned long long v = ((y->tv_sec * amillion) + y->tv_usec); return u-v; } double diff_s_timeval(struct timeval *x, struct timeval *y){ unsigned long long amillion = 1000000; unsigned long long t; unsigned long long tsec; unsigned long long tusec; double t_as_double_secondpart; double t_as_double_usecondpart; double t_as_double; t = diff_us_timeval( x, y); tsec = t / amillion; tusec = t % amillion; t_as_double_secondpart = tsec; t_as_double_usecondpart = tusec; t_as_double_usecondpart = t_as_double_usecondpart / amillion; t_as_double = t_as_double_secondpart + t_as_double_usecondpart; return t_as_double; } #else unsigned long long diff_ns_timespec(struct timespec *x, struct timespec *y) { unsigned long long abillion = 1000000000; unsigned long long u = ((x->tv_sec * abillion) + x->tv_nsec); unsigned long long v = ((y->tv_sec * abillion) + y->tv_nsec); return u-v; } double diff_s_timespec (struct timespec *x, struct timespec *y){ unsigned long long abillion = 1000000000; unsigned long long t; unsigned long long tsec; unsigned long long tnsec; double t_as_double_secondpart; double t_as_double_usecondpart; double t_as_double; t = diff_ns_timespec( x, y); tsec = t / abillion; tnsec = t % abillion; t_as_double_secondpart = tsec; t_as_double_usecondpart = tnsec; t_as_double_usecondpart = t_as_double_usecondpart / abillion; t_as_double = t_as_double_secondpart + t_as_double_usecondpart; return t_as_double; } #endif #define CLOCK_REALTIME 0 #if COMPILEMSVS || COMPILEWIN32 LARGE_INTEGER getFILETIMEoffset() { SYSTEMTIME s; FILETIME f; LARGE_INTEGER t; s.wYear = 1970; s.wMonth = 1; s.wDay = 1; s.wHour = 0; s.wMinute = 0; s.wSecond = 0; s.wMilliseconds = 0; SystemTimeToFileTime(&s, &f); t.QuadPart = f.dwHighDateTime; t.QuadPart <<= 32; t.QuadPart |= f.dwLowDateTime; return (t); } int my_clock_gettime(int X, struct timeval *tv) { LARGE_INTEGER t; FILETIME f; double microseconds; static LARGE_INTEGER offset; static double frequencyToMicroseconds; static int initialized = 0; static BOOL usePerformanceCounter = 0; if (!initialized) { LARGE_INTEGER performanceFrequency; initialized = 1; usePerformanceCounter = QueryPerformanceFrequency(&performanceFrequency); if (usePerformanceCounter) { QueryPerformanceCounter(&offset); frequencyToMicroseconds = (double)performanceFrequency.QuadPart / 1000000.; } else { offset = getFILETIMEoffset(); frequencyToMicroseconds = 10.; } } if (usePerformanceCounter) QueryPerformanceCounter(&t); else { GetSystemTimeAsFileTime(&f); t.QuadPart = f.dwHighDateTime; t.QuadPart <<= 32; t.QuadPart |= f.dwLowDateTime; } t.QuadPart -= offset.QuadPart; microseconds = (double)t.QuadPart / frequencyToMicroseconds; t.QuadPart = microseconds; tv->tv_sec = t.QuadPart / 1000000; tv->tv_usec = t.QuadPart % 1000000; return (0); } #endif void fillsuccessstring(int thissuccess,char* thissuccessstring) { if (thissuccess==0) { strcpy(thissuccessstring," no"); } else { if (thissuccess==1) { strcpy(thissuccessstring,"yes"); } else { printf("Error in fillsuccessstring\n"); exit(-1); } } } void print_table_txt_file_as_tex(int mselection, char* finfilename, char* foutfilename) { char buf[2000]; FILE* fin; FILE* fout; int thism; double thisC12; double thismult; double thistime; int thissuccess; char thissuccessstring[2000]; fin = fopen( finfilename, "r"); fout = fopen( foutfilename, "w"); fprintf(fout,"\\begin{table}[t!]\n"); fprintf(fout,"\\begin{scriptsize}\n"); fprintf(fout,"\\begin{tabular}{|r|r|r|r|} \\hline\n"); fprintf(fout,"$C_{1,2}$ & mult & Time & \\\\ \n"); fprintf(fout,"(seconds) & $\\mathrm{MA}_{i,j,p}$ & (seconds) & Schedulable \\\\ \\hline \\hline \n"); while (fgets( buf, 2000, fin)!=NULL) { sscanf(buf,"%d %lf %lf %lf %d", &thism, &thisC12, &thismult, &thistime, &thissuccess); if (thism==mselection) { fillsuccessstring(thissuccess,thissuccessstring); fprintf(fout," %6.3lf & %6.3lf & %6.1lf & %s \\\\ \n", thisC12, thismult, thistime, thissuccessstring); } } fprintf(fout,"\\hline\n"); fprintf(fout,"\\end{tabular}\n"); fprintf(fout,"\\end{scriptsize}\n"); fprintf(fout,"\\caption{Results from evaluation ($m=%d$).}\n", mselection); fprintf(fout,"\\label{tab:results_from_evaluation_m%d}\n", mselection); fprintf(fout,"\\end{table}\n"); fclose( fin); fclose( fout); } void print_table_II_as_tex() { print_table_txt_file_as_tex(4,"table2_and_table3_data.txt","table2.tex"); } void print_table_III_as_tex() { print_table_txt_file_as_tex(8,"table2_and_table3_data.txt","table3.tex"); } int number_of_elements_stored_here; double elements_stores_here[10000]; void getthirdnumber(char* buf, double* pt3, int* pflag) { char* p; char* p2; char* p3; *pflag = 0; p = strchr(buf,'&'); if (p!=NULL) { p2 = strchr(p+1,'&'); if (p2!=NULL) { p3 = strchr(p2+1,'&'); if (p3!=NULL) { *p3 = 0; sscanf(p2+1,"%lf", pt3 ); *pflag = 1; } } } } void fillinalldatastoredhere(char* finfilename) { char buf[2000]; char* p; char* p2; char* p3; FILE* fin; double thistime; int flag; number_of_elements_stored_here = 0; fin = fopen( finfilename, "r"); fgets( buf, 2000, fin); while (buf[0]=='\\') { fgets( buf, 2000, fin); } // we have already read first line in header fgets( buf, 2000, fin); // we read second line in header fgets( buf, 2000, fin); // we get real data getthirdnumber( buf, &thistime, &flag); elements_stores_here[number_of_elements_stored_here] = thistime; number_of_elements_stored_here = number_of_elements_stored_here + 1; while ((fgets( buf, 2000, fin)!=NULL) && (flag)) { // we get real data getthirdnumber( buf, &thistime, &flag); elements_stores_here[number_of_elements_stored_here] = thistime; number_of_elements_stored_here = number_of_elements_stored_here + 1; } } void sortdatastoredhere() { int index1; int index2; double temp; for (index1=0;index1