-
Notifications
You must be signed in to change notification settings - Fork 0
/
cell_flows.m
339 lines (279 loc) · 13 KB
/
cell_flows.m
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
202
203
204
205
206
207
208
209
210
211
212
213
214
215
216
217
218
219
220
221
222
223
224
225
226
227
228
229
230
231
232
233
234
235
236
237
238
239
240
241
242
243
244
245
246
247
248
249
250
251
252
253
254
255
256
257
258
259
260
261
262
263
264
265
266
267
268
269
270
271
272
273
274
275
276
277
278
279
280
281
282
283
284
285
286
287
288
289
290
291
292
293
294
295
296
297
298
299
300
301
302
303
304
305
306
307
308
309
310
311
312
313
314
315
316
317
318
319
320
321
322
323
324
325
326
327
328
329
330
331
332
333
334
335
336
337
338
339
%function target_tp = cell_flows(targets, sources)
% load all possible simulation scenarios (particular environments, sources,
% targets, etc. that have been saved, such as snub square tesselations, square
% tesselations, parallelogram tesselations, etc.)
init_scenarios;
if ~opt_single
min_sim = 1;
max_sim = length(simulations);
else
min_sim = opt_single;
max_sim = opt_single;
min_run = opt_run;
max_run = opt_run;
end
% main simulation loop over different scenarios to simulate (for allowing
% batch processing and throughput statistics creations)
for iSim = min_sim : max_sim
if ~opt_run
min_run = 1;
max_run = length(simulations(iSim).run);
end
% minor simulation loop over different subscenarios for a given
% environment, e.g., different sources/targets for the same tesselation
for iRun = min_run : max_run
sources = simulations(iSim).run(iRun).sources;
targets = simulations(iSim).run(iRun).targets;
opt_tesselation_type = simulations(iSim).environment;
try
failed = simulations(iSim).run(iRun).failed;
catch
failed = [];
end
try % need to be separate blocks, each can fail independently
faildynamic = simulations(iSim).run(iRun).faildynamic;
catch
faildynamic = [];
end
opt_triangulation = 0; % 0 = don't use delauny triangulation (use a uniformly generated set of vertices instead, for throughput simulations)
placedColors = [];
lockedColors = [];
L = 0.1;
%L = 0.05; % entity radius; for throughput
if opt_tesselation_type == OPT_TESSELATION_TRI || opt_tesselation_type == OPT_TESSELATION_EQTRI_LINE || opt_tesselation_type == OPT_TESSELATION_RTRI_LINE
epsPlot = 0.01;
L = L / 2;
else
epsPlot = 0.25;
end
epsIllegal = 0.0001;
rs = L / 10; % safety radius
d = L + rs;
m = 2; % number of dimension (use this variable when necessary to refer to the dimensions)
F = 0; % number of cells to fail
safeDistance = 3 * L + rs;
% non-batched options
NT = 1; % number of targets
NS = NT; % number of sources
MAX_ROUNDS = simulations(iSim).maxRounds;
% options (potentially per-scenario)
mode_debug = 0;
opt_randic = 0; % random initial condition?
opt_fixedic = 1; % case number for fixed initial conditions (see switch/case statement below); only applies if opt_randic = 0
opt_center_entity = 0; % 1 = place one entity at center of cell at a time, 0 = place (about) numToTryPlacing
%numToTryPlacing = ceil(1/L)/2; % todo: generalize and find side length
numToTryPlacing = 20;
opt_roundsToPlace = 1; % try to place entities every opt_roundsToPlace rounds
opt_display = 1; % don't draw system evolution if 0, draw if 1
%opt_display_update = 10;
opt_display_update = 1;
opt_display_progress = 100; % number of rounds to display a text update on progress if we aren't drawing the system evolution
opt_decimal_tolerance = -4; % decimal tolerance (10^opt_decimal_tolerance)
opt_badCell = 1;
opt_singleEntity = 0;
opt_video = 1; % record video
if opt_video
writerObj = VideoWriter('factory.avi');
writerObj.FrameRate = 5;
open(writerObj);
end
opt_linprog_options=optimset('Display', 'off'); % used to supress messages from linear programming solver
opt_routing_disjoint = 0; % choose routing mode: we may in the future want to implement the disjoint paths algorithm, but for now will not
gcf;
%set(gcf, 'Position', get(0,'Screensize')); % Maximize figure.
axis equal;
set(gcf, 'Position', [1 1 800 800]); % Maximize figure.
set(gca,'nextplot','replacechildren');
set(gcf,'Renderer','zbuffer');
% set failed cells manually
failround = 75;
%failround = -1;
opt_fail_random = 0;
opt_faildynamic = 1; % option to allow failures occurring while running
% initialize environment and partition thereof
init_cell_partitions;
% must be defined after diam (created during environment and partition initialization)
opt_firstFullRound = 2*diam; % first full round to place entities, etc.; in general needs to be 2*N (worst-case diameter)
% set up neighbor graph for triangulated environments
if opt_triangulation
T = (1:N)';
neigh = tr.neighbors(); % set of all neighbors
cc = tr.circumcenters(); % set of all circumcenters
[ic,icr] = tr.incenters(); % set of all incenters with corresponding radii (inscribed circle center and radius)
idx1 = T < neigh(:,1); % modify indexing to make appropriate neighbor graph
idx2 = T < neigh(:,2);
idx3 = T < neigh(:,3);
neigh = [T(idx1) neigh(idx1,1); T(idx2) neigh(idx2,2); T(idx3) neigh(idx3,3)]';
end
% set sources and targets
init_sources_targets;
% initialize other cell variables
init_cell_vars;
% initialize path data structures
init_paths;
% initialize and set failure data structures
init_failures;
% error checking for numbers of sources, targets, failures, etc.
check_sources_targets_failures;
% initialize neighbors
find_neighbors;
% initialize side-to-neighbor data structures
find_sides;
% Initialize all source cells
for i = 1 : length(sources)
Cell(sources(i)).color = i; % set the "color" / type to be equal to the entry in the targets vector, i.e., 1, 2, 3, etc.
end
% Initialize all target cells to be 0 distance away from the target
for i = 1 : length(targets)
Cell(targets(i)).dist(i) = 0; % set the distance to 0 away from this color
Cell(targets(i)).color = i; % set the "color" / type to be equal to the entry in the targets vector, i.e., 1, 2, 3, etc.
end
opt_waitplot = 1; % on = 1, off = 0
waitplot = 0.000001; % wait (in seconds) between plots
indexEntity = 1; % global index for entities (to see if we duplicate, compare them between rounds, etc.)
CellOld = Cell; % copy the current cell information (models communication being delayed a round)
% To model communications, from cell i, any access to
% information of neighbors must be from the CellOld
% variable, which represents what was communicated to i
% from a neighbor at the last round. For the current
% round, update the Cell variable.
locks = [];
overlap = 0;
startOver = ones(NT,1);
% main simulation loop, k is the round index
for k = 2 : MAX_ROUNDS
NF = [1:N];
% updated failed / non-failed cells
for i = 1 : N
if Cell(i).failed
NF = setdiff(NF, i);
end
Cell(i).nfnbrs = Cell(i).nbrs;
% could use NF, but then would need another loop
for j = Cell(i).nbrs
if Cell(j).failed
Cell(i).nfnbrs = setdiff(Cell(i).nfnbrs, j);
end
end
end
for ti = 1 : NT
if isempty(path(ti).int)
placedColors = setdiff(placedColors, ti);
end
end
% compute previous pointers in the routing path
cell_subroutine_prev;
% fail cells dynamically
cell_global_fail_dynamic;
% old version of locking
% for ti = 1 : NT
% for i = NF
% if sources(ti) == i && ~isempty(intersect(placedColors, ti)) % this color already put stuff on the source, block it
% %Cell(i).path(ti).rlock = 1;
% else
% %Cell(i).path(ti).rlock = isempty(Cell(i).Entities);
% end
% end
% end
%
% for ti = 1 : NT
% for i = NF
% if ~(sources(ti) == i && ~isempty(intersect(placedColors, ti))) % this color already put stuff on the source, block it
% for j = Cell(i).nfnbrs
% %Cell(i).path(ti).rlock = Cell(i).path(ti).rlock & Cell(j).path(ti).rlock;
% end
% end
% end
% end
% compute global paths (emulating gossip over all cells)
cell_global_path;
% compute global locks over paths (emulating distributed mutual exclusion
% algorithm over all cells)
cell_global_locks;
% try to place entities safely and without violating assumptions needed
% for liveness
% NOTE: must be performed after computing paths and locks, since this
% is how we enforce the assumptions
cell_place_entities;
% color cells based on entity types
for i = NF
Cell(i).etype = [];
for p = 1 : length(Cell(i).Entities)
if isempty(intersect(Cell(i).etype, Cell(i).Entities(p).color))
Cell(i).etype = [Cell(i).etype Cell(i).Entities(p).color];
end
end
Cell(i).etype = unique(Cell(i).etype); % ensure unique
% if a cell doesn't have a previous entity type yet, go ahead and update
% otherwise, it is only ever updated by the move function when the last entity leaves the cell
if isempty(Cell(i).lastEtype)
Cell(i).lastEtype = Cell(i).etype;
end
for tt = 1 : NT
% see if next pointer is failed, detect failure
np = Cell(i).next(tt);
if isinf(Cell( np ).dist(tt)) && k >= opt_firstFullRound
Cell(i).detectNextFailed = k;
end
end
end
% ROUTING: compute the routing graphs from all cells to targets
cell_subroutine_route;
% LOCKING: compute the paths from all cells with entities to targets
cell_subroutine_path;
% LOCKING: compute the locks for all paths (from all cells with entities to targets)
cell_subroutine_locks;
% SIGNALING: compute the signals for all cells and paths
cell_subroutine_signal;
% MOVING: move entities on cells it is safe to do so for (based on received signal)
cell_subroutine_move;
% runtime monitoring for safety and liveness properties
cell_runtime_monitor;
% reset moved flags for all entities
for i = NF
for p = 1 : length(Cell(i).Entities)
Cell(i).Entities(p).moved = 0;
end
end
% reset signals for all cells and sides
for i = NF
for j = 1 : length(Cell(i).side)
Cell(i).side(j).signal = i;
end
end
CellOld = Cell; % copy for next round
% PLOTTING
if opt_display && mod(k,opt_display_update)==0
clf; % clear the figure
call_plotSystem; % call visualization routine
if opt_waitplot
pause(waitplot); % pause
end
% record each frame into the Movie object; indexing starts at k-1
if opt_video
%Movie(k-1) = getframe(gcf);
frame = getframe;
writeVideo(writerObj,frame);
end
end
if mod(k,opt_display_progress) == 0
['System progressing, at round: ', num2str(k)]
call_plotSystem;
pause(waitplot);
end
%pause % manual update, press a key between each round
end % end main time-step / round loop
% save the video to file
if opt_video
%movie2avi(Movie, 'factory.avi', 'compression', 'none', 'fps', 5);
close(writerObj);
end
% for ti = 1 : NT
% %Cell(targets(ti)).throughput = Cell(targets(ti)).throughput / k; % / MAX_ROUNDS
% %target_tp(ti) = Cell(targets(ti)).throughput;
% end
throughput = throughput ./ k;
simulations(iSim).run(iRun).throughput = throughput;
simulations(iSim).run(iRun).entitiesPlaced = indexEntity;
end
end