1 | #include "Evaluator.h" |
---|
2 | #include "Genetic.h" |
---|
3 | #include <math.h> |
---|
4 | #include <vector> |
---|
5 | #include <omp.h> |
---|
6 | |
---|
7 | #define DEBUG 0 |
---|
8 | |
---|
9 | using namespace std; |
---|
10 | |
---|
11 | /** |
---|
12 | * the default constructor |
---|
13 | */ |
---|
14 | TaskInfo::TaskInfo(){ |
---|
15 | start = 0; |
---|
16 | end = 0; |
---|
17 | proc_index = -1; |
---|
18 | } |
---|
19 | |
---|
20 | /** |
---|
21 | * the default constructor |
---|
22 | */ |
---|
23 | Evaluator::Evaluator(){} |
---|
24 | |
---|
25 | /** |
---|
26 | * the constructor |
---|
27 | * |
---|
28 | * @param TG the input graph of tasks |
---|
29 | * @param PG the input graph of processors |
---|
30 | */ |
---|
31 | Evaluator::Evaluator(TaskGraf &TG, ProcesorGraf &PG){ |
---|
32 | tasks = TG; |
---|
33 | procs = PG; |
---|
34 | |
---|
35 | proc_time = (int*)calloc(procs.nr_noduri , sizeof(int)); |
---|
36 | task_info = (TaskInfo*)calloc(tasks.nr_noduri , sizeof(TaskInfo));; |
---|
37 | |
---|
38 | } |
---|
39 | |
---|
40 | /** |
---|
41 | * Method that evaluates one chromosome, computing its makespan, fitness, etc |
---|
42 | * |
---|
43 | * @param ch the chromosome we want to evaluate |
---|
44 | */ |
---|
45 | void Evaluator::evaluateIndividual(Chromosome &ch){ |
---|
46 | int i,j; |
---|
47 | Gene g; |
---|
48 | int time,start,end; |
---|
49 | int cost_com, id_proc, id_task; |
---|
50 | tasks.init(); |
---|
51 | procs.init(); |
---|
52 | |
---|
53 | if (DEBUG == 1) |
---|
54 | ch.print(); |
---|
55 | |
---|
56 | |
---|
57 | //initializes the task information |
---|
58 | for (i=0;i<tasks.nr_noduri;i++){ |
---|
59 | task_info[i].start = 0; |
---|
60 | task_info[i].end = 0; |
---|
61 | task_info[i].proc_index = -1; |
---|
62 | } |
---|
63 | //initializes procesor times |
---|
64 | for (i=0;i<procs.nr_noduri;i++) |
---|
65 | proc_time[i]=0; |
---|
66 | |
---|
67 | |
---|
68 | for (i=0;i<tasks.nr_noduri;i++){ |
---|
69 | g = ch[i]; |
---|
70 | time = proc_time[g.proc_index]; |
---|
71 | |
---|
72 | if (DEBUG == 1) printf("P%d : time = %d\n",g.proc_index, time); |
---|
73 | |
---|
74 | if (DEBUG == 1) printf("Predecesori:\n"); |
---|
75 | |
---|
76 | for (j=0;j<tasks.noduri[g.task_index].nr_pred;j++){ |
---|
77 | cost_com = ((Muchie *)(tasks.noduri[g.task_index].predecesori[j]))->cost; |
---|
78 | id_task = ((Muchie *)(tasks.noduri[g.task_index].predecesori[j]))->predecesor->id; |
---|
79 | id_proc = task_info[id_task].proc_index; |
---|
80 | |
---|
81 | if (DEBUG == 1) printf("T%d pe P%d - cost=%d\n",id_task,id_proc,cost_com); |
---|
82 | |
---|
83 | if (id_proc == g.proc_index) |
---|
84 | cost_com = 0; |
---|
85 | else cost_com *= procs.noduri[g.proc_index].cost_comm[id_proc]; |
---|
86 | |
---|
87 | if (DEBUG == 1) printf("Cost comm : %d\n",cost_com); |
---|
88 | |
---|
89 | if (time < cost_com + task_info[id_task].end) |
---|
90 | time = cost_com + task_info[id_task].end; |
---|
91 | |
---|
92 | if (DEBUG == 1) printf("Time : %d\n",time); |
---|
93 | |
---|
94 | } |
---|
95 | start = time; |
---|
96 | time += tasks.noduri[g.task_index].cost * procs.noduri[g.proc_index].cost; |
---|
97 | end = time; |
---|
98 | |
---|
99 | //tasks.noduri[g.task_index].setProcesor(g.proc_index,start,end); |
---|
100 | //procs.noduri[g.proc_index].time = time; |
---|
101 | //procs.noduri[g.proc_index].addTask(g.task_index); |
---|
102 | |
---|
103 | task_info[g.task_index].start = start; |
---|
104 | task_info[g.task_index].end = end; |
---|
105 | task_info[g.task_index].proc_index = g.proc_index; |
---|
106 | proc_time[g.proc_index] = time; |
---|
107 | if (DEBUG == 1) printf("Time update on P%d : %d\n\n",g.proc_index,time); |
---|
108 | } |
---|
109 | |
---|
110 | int makespan = proc_time[0]; |
---|
111 | for (i=1;i<procs.nr_noduri;i++) |
---|
112 | if (proc_time[i] > makespan) |
---|
113 | makespan = proc_time[i]; |
---|
114 | |
---|
115 | if (DEBUG == 2) printf("makespan = %d\n",makespan); |
---|
116 | |
---|
117 | ch.makespan = makespan; |
---|
118 | |
---|
119 | double av = 0; |
---|
120 | double min = 30000; |
---|
121 | |
---|
122 | for (i=0;i<procs.nr_noduri;i++){ |
---|
123 | av+=proc_time[i]; |
---|
124 | if (proc_time[i] < min ) |
---|
125 | min = proc_time[i]; |
---|
126 | } |
---|
127 | |
---|
128 | av = av / procs.nr_noduri; |
---|
129 | |
---|
130 | ch.evalT1 = min / makespan; |
---|
131 | ch.evalT2 = av / makespan ; |
---|
132 | |
---|
133 | double delta = 0; |
---|
134 | for (i=0;i<procs.nr_noduri;i++){ |
---|
135 | delta+= (av - proc_time[i])*(av - proc_time[i]); |
---|
136 | } |
---|
137 | delta = delta / procs.nr_noduri; |
---|
138 | ch.loadBalance = 1 - 1/av * sqrt(delta); |
---|
139 | |
---|
140 | if (DEBUG == 2) printf("T1 = %f T2 = %f LB = %f\n",ch.evalT1, ch.evalT2, ch.loadBalance); |
---|
141 | } |
---|
142 | |
---|
143 | /** |
---|
144 | * Method that evaluates one population's performance |
---|
145 | * |
---|
146 | * @param ch the list of chromosomes |
---|
147 | */ |
---|
148 | void Evaluator::evaluatePopulation(vector<Chromosome> &chs){ |
---|
149 | int i; |
---|
150 | for (i=0;i<(int)chs.size();i++){ |
---|
151 | if (chs[i].fitness == 0) |
---|
152 | evaluateIndividual(chs[i]); |
---|
153 | } |
---|
154 | |
---|
155 | double best = chs[0].makespan; |
---|
156 | |
---|
157 | for (i=0;i<(int)chs.size();i++){ |
---|
158 | if (chs[i].makespan < best) |
---|
159 | best = chs[i].makespan; |
---|
160 | } |
---|
161 | |
---|
162 | for (i=0;i<(int)chs.size();i++){ |
---|
163 | chs[i].evalT3 = best / chs[i].makespan; |
---|
164 | chs[i].fitness = chs[i].evalT1 * chs[i].evalT2 * chs[i].evalT3 * chs[i].evalT3 * chs[i].evalT3 ; |
---|
165 | if (DEBUG == 1) printf("Fit = %f\n",chs[i].fitness); |
---|
166 | } |
---|
167 | |
---|
168 | |
---|
169 | } |
---|