Safe Haskell | None |
---|

A generator for Graph500 benchmark. Translated from Graph500 specification in GNU Octave.

# Documentation

%% Original specification in GNU Octave commented by sergueyz (wherever he feels original is too terse). %% %% GNU Octave expressions part of manual: http://sunsite.univie.ac.at/textbooks/octave/octave_9.html function ij = kronecker_generator (SCALE, edgefactor) %% Generate an edgelist according to the Graph500 %% parameters. In this sample, the edge list is %% returned in an array with two rows, where StartVertex %% is first row and EndVertex is the second. The vertex %% labels start at zero. %% %% Example, creating a sparse matrix for viewing: %% ij = kronecker_generator (10, 16); %% G = sparse (ij(1,:)+1, ij(2,:)+1, ones (1, size (ij, 2))); %% spy (G); %% The spy plot should appear fairly dense. Any locality %% is removed by the final permutations. %% Set number of vertices. N = 2^SCALE; %% Set number of edges. M = edgefactor * N; %% Set initiator probabilities. [A, B, C] = deal (0.57, 0.19, 0.19); %% Just a tuple assignment. %% Create index arrays. ij = ones (2, M); %% 2xM of ones. %% Probabilities. ab = A + B; c_norm = C/(1 - (A + B)); a_norm = A/(A + B); %% Loop over each order of bit. for ib = 1:SCALE, %% Compare with probabilities and set bits of indices. ii_bit = rand (1, M) > ab; %% either 0 or 1 jj_bit = rand (1, M) > ( c_norm * ii_bit + a_norm * not (ii_bit) ); %% either 0 or 1. %% please see that ij is one-based. We add current power of two to sums in ij. %% each ij(:,:) lies in range 1..2^SCALE. ij = ij + 2^(ib-1) * [ii_bit; jj_bit]; end %% Permute vertex labels p = randperm (N); %% a column with numbers 1..N. ij = p(ij); %% the most appropriate meaning here is ij(a,b) = p(ij(a,b)). %% please correct me if I am wrong. %% Permute the edge list p = randperm (M); ij = ij(:, p); %% the most appropriate meaning here is ij(a,b) = ij(a,p(b)). %% please correct me if I am wrong. %% Adjust to zero-based labels. ij = ij - 1;