-
Notifications
You must be signed in to change notification settings - Fork 5
/
Copy pathheuristics.py
202 lines (178 loc) · 12.9 KB
/
heuristics.py
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
100
101
102
103
104
105
106
107
108
109
110
111
112
113
114
115
116
117
118
119
120
121
122
123
124
125
126
127
128
129
130
131
132
133
134
135
136
137
138
139
140
141
142
143
144
145
146
147
148
149
150
151
152
153
154
155
156
157
158
159
160
161
162
163
164
165
166
167
168
169
170
171
172
173
174
175
176
177
178
179
180
181
182
183
184
185
186
187
188
189
190
191
192
193
194
195
196
197
198
199
200
201
import math
from collections import Counter
import numpy as np
def greedy_solution_bfd_baseline_capacity(scenario, time_slot_index, prev_open_DCs, prev_loaded_apps):
apps_loaded = [[0 for j in range(scenario.num_DCs)] for s in range(scenario.num_apps)]
orig_available_compute_DCs = np.copy(scenario.compute_capacities) * 0.7 # limiting to 70% utilization
orig_available_memory_DCs = np.copy(scenario.mem_capacities) * 0.95 # limiting memory to 95
current_available_compute_DCs = np.copy(orig_available_compute_DCs)
current_available_memory_DCs = np.copy(orig_available_memory_DCs)
# Index 0 for cloud
fraction_assigned = [[[0 for j in range(scenario.num_DCs + 1)] for s in range(scenario.num_apps)] for i in
range(scenario.num_BSs)]
demand = np.array(scenario.demand)
z_j = [0 for _ in range(scenario.num_DCs)]
# Loop through all applications starting with the app with lowest latency requirement
app_latencies = [scenario.max_latency[s] for s in range(scenario.num_apps)]
sorted_app_indices = np.argsort(app_latencies)
for app_index in sorted_app_indices:
demand_per_BS = demand[:, app_index, time_slot_index]
# Loop through each BS, starting with highest demand
base_station_indices = np.argsort(demand_per_BS)[::-1]
for i in base_station_indices:
orig_demand_to_satisfy = demand[i][app_index][time_slot_index]
demand_to_satisfy = demand[i][app_index][time_slot_index]
if demand_to_satisfy == 0:
continue
memory_reqd = [0 for _ in range(scenario.num_DCs)]
compute_reqd = [0 for _ in range(scenario.num_DCs)]
demand_to_assign = [0 for _ in range(scenario.num_DCs)]
remaining_capacity = np.copy(current_available_compute_DCs)
# Calculate remaining memory capacity after packing demand
# for app s from BS i to DC_index
for DC_index in range(scenario.num_DCs):
min_compute = min(current_available_compute_DCs[DC_index],
round(scenario.compute_factor[app_index] * demand_to_satisfy, 2))
demand_that_fits = min_compute // scenario.compute_factor[app_index]
compute_reqd[DC_index] = min_compute
if apps_loaded[app_index][DC_index] == 1:
# App is already loaded, only require memory for processing data
min_memory = min(current_available_memory_DCs[DC_index],
demand_to_satisfy * scenario.input_size[app_index] / scenario.time_slot_in_seconds)
demand_to_assign[DC_index] = min(demand_that_fits,
round(min_memory * scenario.time_slot_in_seconds / scenario.input_size[
app_index], 0))
memory_reqd[DC_index] = demand_to_assign[DC_index] * \
scenario.input_size[app_index] / scenario.time_slot_in_seconds
else:
min_memory = min(current_available_memory_DCs[DC_index],
scenario.mem_factor[app_index] + demand_to_satisfy * scenario.input_size[
app_index] / scenario.time_slot_in_seconds)
demand_to_assign[DC_index] = min(demand_that_fits, round((min_memory - scenario.mem_factor[
app_index]) * scenario.time_slot_in_seconds / scenario.input_size[app_index], 0))
memory_reqd[DC_index] = scenario.mem_factor[app_index] + demand_to_assign[DC_index] * scenario.input_size[
app_index] / scenario.time_slot_in_seconds
remaining_capacity[DC_index] = current_available_compute_DCs[DC_index] - (demand_to_assign[DC_index] *
scenario.compute_factor[app_index])
if remaining_capacity[DC_index] <= 0 or demand_to_assign[DC_index] == 0:
remaining_capacity[DC_index] = math.inf
chosen_DC = np.argmin(remaining_capacity)
# Assign demand to chosen DC
fraction = demand_to_assign[chosen_DC] / orig_demand_to_satisfy
demand_to_satisfy = demand_to_satisfy - demand_to_assign[chosen_DC]
current_available_memory_DCs[chosen_DC] = current_available_memory_DCs[chosen_DC] - memory_reqd[
chosen_DC]
current_available_compute_DCs[chosen_DC] = current_available_compute_DCs[chosen_DC] - compute_reqd[chosen_DC]
apps_loaded[app_index][chosen_DC] = 1
fraction_assigned[i][app_index][chosen_DC + 1] = fraction
z_j[chosen_DC] = 1
# After checking all DCs, if demand remains assign to the cloud
if demand_to_satisfy > 0:
fraction_assigned[i][app_index][0] = demand_to_satisfy / orig_demand_to_satisfy
compute_utilization_DC = (orig_available_compute_DCs - current_available_compute_DCs) / (
orig_available_compute_DCs / 0.7)
for i in range(scenario.num_BSs):
for s in range(scenario.num_apps):
if not math.isclose(fraction_assigned[i][s][0], 0, abs_tol=1e-5):
print("Time slot = {}, i = {}, app = {}, fraction assigned to cloud = {}".format(time_slot_index, i, s,
fraction_assigned[i][
s][0]))
# Check if all demand is assigned
for i in range(scenario.num_BSs):
for s in range(scenario.num_apps):
if demand[i][s][time_slot_index] > 0 and not math.isclose(1.0,
np.sum(fraction_assigned[i][s])):
print("Time slot = {}, All demand for app {} from BS {} not assigned. Fractions = {}".format(time_slot_index,
s, i,
fraction_assigned[i][s]))
print("Exception!")
exit(1)
DCs_open = (compute_utilization_DC > 0).astype(int)
return compute_utilization_DC.tolist(), fraction_assigned, np.array(apps_loaded), DCs_open, np.sum(DCs_open)
def greedy_solution_bfd_baseline_latency(scenario, time_slot_index, prev_open_DCs, prev_loaded_apps):
apps_loaded = [[0 for j in range(scenario.num_DCs)] for s in range(scenario.num_apps)]
orig_available_compute_DCs = np.copy(scenario.compute_capacities) * 0.7 # limiting to 70% utilization
orig_available_memory_DCs = np.copy(scenario.mem_capacities) * 0.95 # limiting memory to 95% 30400
current_available_compute_DCs = np.copy(orig_available_compute_DCs)
current_available_memory_DCs = np.copy(orig_available_memory_DCs)
# Index 0 for cloud
fraction_assigned = [[[0 for j in range(scenario.num_DCs + 1)] for s in range(scenario.num_apps)] for i in
range(scenario.num_BSs)]
demand = np.array(scenario.demand)
z_j = [0 for _ in range(scenario.num_DCs)]
app_latencies = [scenario.max_latency[s] for s in range(scenario.num_apps)]
sorted_app_indices = np.argsort(app_latencies)
for app_index in sorted_app_indices:
demand_per_BS = demand[:, app_index, time_slot_index]
# Loop through each BS, starting with highest demand
base_station_indices = np.argsort(demand_per_BS)[::-1]
for i in base_station_indices:
orig_demand_to_satisfy = demand[i][app_index][time_slot_index]
demand_to_satisfy = demand[i][app_index][time_slot_index]
if demand_to_satisfy == 0:
break
memory_reqd = [0 for _ in range(scenario.num_DCs)]
compute_reqd = [0 for _ in range(scenario.num_DCs)]
demand_to_assign = [0 for _ in range(scenario.num_DCs)]
remaining_capacity = np.copy(current_available_compute_DCs)
# Calculate remaining memory capacity after packing demand
# for app s from BS i to DC_index
for DC_index in range(scenario.num_DCs):
min_compute = min(current_available_compute_DCs[DC_index],
round(scenario.compute_factor[app_index] * demand_to_satisfy, 2))
demand_that_fits = min_compute // scenario.compute_factor[app_index]
compute_reqd[DC_index] = min_compute
if apps_loaded[app_index][DC_index] == 1:
# App is already loaded, only require memory for processing data
min_memory = min(current_available_memory_DCs[DC_index],
demand_to_satisfy * scenario.input_size[app_index] / scenario.time_slot_in_seconds)
demand_to_assign[DC_index] = min(demand_that_fits,
round(min_memory * scenario.time_slot_in_seconds / scenario.input_size[
app_index], 0))
memory_reqd[DC_index] = demand_to_assign[DC_index] * \
scenario.input_size[app_index] / scenario.time_slot_in_seconds
else:
min_memory = min(current_available_memory_DCs[DC_index],
scenario.mem_factor[app_index] + demand_to_satisfy * scenario.input_size[
app_index] / scenario.time_slot_in_seconds)
demand_to_assign[DC_index] = min(demand_that_fits, round((min_memory - scenario.mem_factor[
app_index]) * scenario.time_slot_in_seconds / scenario.input_size[app_index], 0))
memory_reqd[DC_index] = scenario.mem_factor[app_index] + demand_to_assign[DC_index] * scenario.input_size[
app_index] / scenario.time_slot_in_seconds
remaining_capacity[DC_index] = current_available_compute_DCs[DC_index] - (demand_to_assign[DC_index] *
scenario.compute_factor[app_index])
if remaining_capacity[DC_index] <= 0 or demand_to_assign[DC_index] == 0:
remaining_capacity[DC_index] = math.inf
chosen_DC = np.argmin([scenario.latency_DC[i][idx] for idx in range(scenario.num_DCs)])
# Assign demand to chosen DC
fraction = demand_to_assign[chosen_DC] / orig_demand_to_satisfy
demand_to_satisfy = demand_to_satisfy - demand_to_assign[chosen_DC]
current_available_memory_DCs[chosen_DC] = current_available_memory_DCs[chosen_DC] - memory_reqd[
chosen_DC]
current_available_compute_DCs[chosen_DC] = current_available_compute_DCs[chosen_DC] - compute_reqd[chosen_DC]
apps_loaded[app_index][chosen_DC] = 1
fraction_assigned[i][app_index][chosen_DC + 1] = fraction
z_j[chosen_DC] = 1
# After checking all DCs, if demand remains assign to the cloud
if demand_to_satisfy > 0:
fraction_assigned[i][app_index][0] = demand_to_satisfy / orig_demand_to_satisfy
compute_utilization_DC = (orig_available_compute_DCs - current_available_compute_DCs) / (
orig_available_compute_DCs / 0.7)
for i in range(scenario.num_BSs):
for s in range(scenario.num_apps):
if not math.isclose(fraction_assigned[i][s][0], 0, abs_tol=1e-5):
print("Time slot = {}, i = {}, app = {}, fraction assigned to cloud = {}".format(time_slot_index, i, s,
fraction_assigned[i][
s][0]))
# Check if all demand is assigned
for i in range(scenario.num_BSs):
for s in range(scenario.num_apps):
if demand[i][s][time_slot_index] > 0 and not math.isclose(1.0,
np.sum(fraction_assigned[i][s])):
print("Time slot = {}, All demand for app {} from BS {} not assigned. Fractions = {}".format(time_slot_index,
s, i,
fraction_assigned[i][s]))
print("Exception!")
exit(1)
DCs_open = (compute_utilization_DC > 0).astype(int)
return compute_utilization_DC.tolist(), fraction_assigned, np.array(apps_loaded), DCs_open, np.sum(DCs_open)