1function comparisonData = compare(trials, percent_to_keep, plot_outliers, use_weights) 2 if (nargin < 1 || trials < 1) 3 trials = 5; 4 end 5 if (nargin < 2 || percent_to_keep <= 0) 6 percent_to_keep = 60; 7 end 8 if (nargin < 3) 9 plot_outliers = 0; 10 end 11 if (nargin < 4) 12 use_weights = 0; 13 end 14 15 index = ssget; 16 j = 1; 17 18 comparisonData = struct('avg_mongoose_times', [], ... 19 'avg_metis_times', [], ... 20 'rel_mongoose_times', [], ... 21 'avg_mongoose_imbalance', [], ... 22 'avg_metis_imbalance', [], ... 23 'avg_mongoose_cut_weight', [], ... 24 'avg_mongoose_cut_size', [], ... 25 'avg_metis_cut_weight', [], ... 26 'avg_metis_cut_size', [], ... 27 'rel_mongoose_cut_size', [], ... 28 'problem_id', [], ... 29 'problem_name', [], ... 30 'problem_kind', [], ... 31 'problem_nnz', [], ... 32 'problem_n', []); 33 for i = 1:length(index.nrows) 34 if (index.isReal(i)) 35 36 % For comparing graph performance 37 % if (~index.isGraph(i)) 38 % continue; 39 % end 40 % use_weights = 1; 41 42 Prob = ssget(i); 43 A = Prob.A; 44 45 % If matrix is unsymmetric, form the augmented system 46 if (index.numerical_symmetry(i) < 1) 47 [m_rows, n_cols] = size(A); 48 A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)]; 49 end 50 51 % Make matrix binary - matrix values are not necessarily edge weights 52 %A = sign(abs(A)); 53 A = abs(A); % Edit for graph comparison 54 55 % Sanitize the matrix (remove diagonal, make symmetric) 56 A = sanitize(A, ~use_weights); 57 58 % If the sanitization removed all vertices, skip this matrix 59 if nnz(A) < 2 60 continue 61 end 62 63 fprintf('Computing separator for %d: %s\n', i, Prob.name); 64 65 [~, n_cols] = size(A); 66 comparisonData(j).problem_id = Prob.id; 67 comparisonData(j).problem_name = Prob.name; 68 comparisonData(j).problem_kind = Prob.kind; 69 comparisonData(j).problem_nnz = nnz(A); 70 comparisonData(j).problem_n = n_cols; 71 72 % Run Mongoose with default options to partition the graph. 73 O = edgecut_options(); 74 O.randomSeed = 123456789; 75 for k = 1:trials 76 tic; 77 partition = edgecut(A,O); 78 t = toc; 79 fprintf('Mongoose: %0.2f\n', t); 80 mongoose_times(j,k) = t; 81 part_A = find(partition); 82 part_B = find(1-partition); 83 perm = [part_A part_B]; 84 p = length(part_A); 85 A_perm = A(perm, perm); 86 mongoose_cut_weight(j,k) = sum(sum(A_perm((p+1):n_cols, 1:p))); 87 mongoose_cut_size(j,k) = sum(sum(sign(A_perm((p+1):n_cols, 1:p)))); 88 mongoose_imbalance(j,k) = abs(0.5-(length(part_A)/(length(part_A) + length(part_B)))); 89 end 90 91 % Run METIS to partition the graph. 92 for k = 1:trials 93 tic; 94 [part_A,part_B] = metispart(A, 0, 123456789); 95 t = toc; 96 fprintf('METIS: %0.2f\n', t); 97 metis_times(j,k) = t; 98 p = length(part_A); 99 perm = [part_A part_B]; 100 A_perm = A(perm, perm); 101 metis_cut_weight(j,k) = sum(sum(A_perm((p+1):n_cols, 1:p))); 102 metis_cut_size(j,k) = sum(sum(sign(A_perm((p+1):n_cols, 1:p)))); 103 metis_imbalance(j,k) = abs(0.5-(length(part_A)/(length(part_A) + length(part_B)))); 104 end 105 j = j + 1; 106 end 107 end 108 109 n = length(mongoose_times); 110 111 for i = 1:n 112 % Compute trimmed means - trim lowest and highest 20% 113 comparisonData(i).avg_mongoose_times = trimmean(mongoose_times(i,:), 100-percent_to_keep); 114 comparisonData(i).avg_mongoose_cut_weight = trimmean(mongoose_cut_weight(i,:), 100-percent_to_keep); 115 comparisonData(i).avg_mongoose_cut_size = trimmean(mongoose_cut_size(i,:), 100-percent_to_keep); 116 comparisonData(i).avg_mongoose_imbalance = trimmean(mongoose_imbalance(i,:), 100-percent_to_keep); 117 118 comparisonData(i).avg_metis_times = trimmean(metis_times(i,:), 100-percent_to_keep); 119 comparisonData(i).avg_metis_cut_weight = trimmean(metis_cut_weight(i,:), 100-percent_to_keep); 120 comparisonData(i).avg_metis_cut_size = trimmean(metis_cut_size(i,:), 100-percent_to_keep); 121 comparisonData(i).avg_metis_imbalance = trimmean(metis_imbalance(i,:), 100-percent_to_keep); 122 123 % Compute times relative to METIS 124 comparisonData(i).rel_mongoose_times = (comparisonData(i).avg_mongoose_times / comparisonData(i).avg_metis_times); 125 126 % Compute cut weight relative to METIS 127 comparisonData(i).rel_mongoose_cut_weight = (comparisonData(i).avg_mongoose_cut_weight / comparisonData(i).avg_metis_cut_weight); 128 129 % Compute cut size relative to METIS 130 comparisonData(i).rel_mongoose_cut_size = (comparisonData(i).avg_mongoose_cut_size / comparisonData(i).avg_metis_cut_size); 131 132 % Check for outliers 133 prob_id = comparisonData(i).problem_id; 134 outlier = 0; 135 136 if (comparisonData(i).rel_mongoose_times > 2) 137 disp(['Outlier! Mongoose time significantly worse. ID: ', num2str(prob_id)]); 138 outlier = 1; 139 comparisonData(i).outlier.time = 1; 140 end 141 if (comparisonData(i).rel_mongoose_times < 0.5) 142 disp(['Outlier! METIS time significantly worse. ID: ', num2str(prob_id)]); 143 outlier = 1; 144 comparisonData(i).outlier.time = -1; 145 end 146 147 if (comparisonData(i).rel_mongoose_cut_size > 2) 148 disp(['Outlier! Mongoose cut size significantly worse. ID: ', num2str(prob_id)]); 149 outlier = 1; 150 comparisonData(i).outlier.cut_size = 1; 151 end 152 if (comparisonData(i).rel_mongoose_cut_size < 0.5) 153 disp(['Outlier! METIS cut size significantly worse. ID: ', num2str(prob_id)]); 154 outlier = 1; 155 comparisonData(i).outlier.cut_size = -1; 156 end 157 158 if (comparisonData(i).avg_mongoose_imbalance > 2*comparisonData(i).avg_metis_imbalance) 159 disp(['Outlier! Mongoose imbalance significantly worse. ID: ', num2str(prob_id)]); 160 comparisonData(i).outlier.imbalance = 1; 161 outlier = 1; 162 end 163 if (comparisonData(i).avg_metis_imbalance > 2*comparisonData(i).avg_mongoose_imbalance) 164 disp(['Outlier! METIS imbalance significantly worse. ID: ', num2str(prob_id)]); 165 comparisonData(i).outlier.imbalance = -1; 166 outlier = 1; 167 end 168 169 if (outlier && plot_outliers) 170 plotGraphs(prob_id); 171 end 172 end 173 174 % Sort metrics 175 sorted_rel_mongoose_times = sort([comparisonData.rel_mongoose_times]); 176 sorted_rel_mongoose_cut_weight = sort([comparisonData.rel_mongoose_cut_weight]); 177 sorted_rel_mongoose_cut_size = sort([comparisonData.rel_mongoose_cut_size]); 178 sorted_avg_mongoose_imbalance = sort([comparisonData.avg_mongoose_imbalance]); 179 sorted_avg_metis_imbalance = sort([comparisonData.avg_metis_imbalance]); 180 181 % Get the Git commit hash for labeling purposes 182 [error, commit] = system('git rev-parse --short HEAD'); 183 git_found = ~error; 184 commit = strtrim(commit); 185 186 %%%%% Plot performance profiles %%%%% 187 188 % Plot timing profiles 189 figure; 190 semilogy(1:n, sorted_rel_mongoose_times, 'Color', 'b'); 191 hold on; 192 semilogy(1:n, ones(1,n), 'Color','r'); 193 axis([1 n min(sorted_rel_mongoose_times) max(sorted_rel_mongoose_times)]); 194 xlabel('Matrix'); 195 ylabel('Wall Time Relative to METIS'); 196 hold off; 197 198 plt = Plot(); 199 plt.LineStyle = {'-', '--'}; 200 plt.Legend = {'Mongoose', 'METIS'}; 201 plt.LegendLoc = 'SouthEast'; 202 plt.BoxDim = [6, 5]; 203 204 filename = ['Timing' date]; 205 if(git_found) 206 title(['Timing Profile - Commit ' commit]); 207 filename = ['Timing-' commit]; 208 end 209 210 plt.export([filename '.png']); 211 212 % Plot separator weight profiles 213 figure; 214 semilogy(1:n, sorted_rel_mongoose_cut_weight, 'Color', 'b'); 215 hold on; 216 semilogy(1:n, ones(1,n), 'Color','r'); 217 axis([1 n min(sorted_rel_mongoose_cut_weight) max(sorted_rel_mongoose_cut_weight)]); 218 xlabel('Matrix'); 219 ylabel('Cut Weight Relative to METIS'); 220 hold off; 221 222 plt = Plot(); 223 plt.LineStyle = {'-', '--'}; 224 plt.Legend = {'Mongoose', 'METIS'}; 225 plt.LegendLoc = 'SouthEast'; 226 plt.BoxDim = [6, 5]; 227 228 filename = ['SeparatorWeight' date]; 229 if(git_found) 230 title(['Separator Weight Profile - Commit ' commit]); 231 filename = ['SeparatorWeight-' commit]; 232 end 233 plt.export([filename '.png']); 234 235 % Plot separator size profiles 236 figure; 237 semilogy(1:n, sorted_rel_mongoose_cut_size, 'Color', 'b'); 238 hold on; 239 semilogy(1:n, ones(1,n), 'Color','r'); 240 axis([1 n min(sorted_rel_mongoose_cut_size) max(sorted_rel_mongoose_cut_size)]); 241 xlabel('Matrix'); 242 ylabel('Cut Size Relative to METIS'); 243 hold off; 244 245 plt = Plot(); 246 plt.LineStyle = {'-', '--'}; 247 plt.Legend = {'Mongoose', 'METIS'}; 248 plt.LegendLoc = 'SouthEast'; 249 plt.BoxDim = [6, 5]; 250 251 filename = ['SeparatorSize' date]; 252 if(git_found) 253 title(['Separator Size Profile - Commit ' commit]); 254 filename = ['SeparatorSize-' commit]; 255 end 256 plt.export([filename '.png']); 257 258 % Plot imbalance profiles 259 figure; 260 plot(1:n, sorted_avg_mongoose_imbalance, 'Color', 'b'); 261 hold on; 262 plot(1:n, sorted_avg_metis_imbalance, 'Color','r'); 263 axis([1 n 0 max([sorted_avg_metis_imbalance sorted_avg_mongoose_imbalance])]); 264 xlabel('Matrix'); 265 ylabel('Imbalance'); 266 hold off; 267 268 plt = Plot(); 269 plt.LineStyle = {'-', '--'}; 270 plt.Legend = {'Mongoose', 'METIS'}; 271 plt.LegendLoc = 'NorthWest'; 272 plt.BoxDim = [6, 5]; 273 274 filename = ['Imbalance' date]; 275 if(git_found) 276 title(['Imbalance Profile - Commit ' commit]); 277 filename = ['Imbalance-' commit]; 278 end 279 280 plt.export([filename '.png']); 281 282 %% Plot only big matrices to compare 283 284 285 286 %% Write data to file for future comparisons 287 if(git_found) 288 writetable(struct2table(comparisonData), [commit '.txt']); 289 end 290end 291 292function plotGraphs(prob_id) 293 index = ssget; 294 Prob = ssget(prob_id); 295 A = Prob.A; 296 if (index.numerical_symmetry(prob_id) < 1) 297 [m_rows, n_cols] = size(A); 298 A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)]; 299 end 300 A = mongoose_sanitizeMatrix(A); 301 302 % Compute partitioning using Mongoose 303 partition = mongoose_computeEdgeSeparator(A); 304% part_A = find(partition); 305% part_B = find(1-partition); 306% perm = [part_A part_B]; 307% p = length(partition); 308% A_perm = A(perm, perm); 309% subplot(1,2,1); 310% hold on; 311% spy(A); 312% subplot(1,2,2); 313% spy(A_perm); 314% hold off; 315 mongoose_separator_plot(A, partition, 1-partition, ['mongoose_' num2str(prob_id)]); 316 317 % Compute partitioning using METIS 318 [perm, ~] = metispart(A, 0, 123456789); 319 [m, ~] = size(A); 320 partition = zeros(m,1); 321 for j = 1:m 322 partition(j,1) = sum(sign(find(j == perm))); 323 end 324 mongoose_separator_plot(A, partition, 1-partition, ['metis_' num2str(prob_id)]); 325end 326 327function plotMatrix(prob_id) 328 index = ssget; 329 Prob = ssget(prob_id); 330 A = Prob.A; 331 if (index.numerical_symmetry(prob_id) < 1) 332 [m_rows, n_cols] = size(A); 333 A = [sparse(m_rows,m_rows) A; A' sparse(n_cols,n_cols)]; 334 end 335 A = mongoose_sanitizeMatrix(A); 336 337 % Compute partitioning using Mongoose 338 partition = mongoose_computeEdgeSeparator(A); 339 part_A = find(partition); 340 part_B = find(1-partition); 341 perm = [part_A part_B]; 342 A_perm = A(perm, perm); 343 subplot(1,2,1); 344 hold on; 345 spy(A); 346 subplot(1,2,2); 347 spy(A_perm); 348 hold off; 349end 350