Graph500-0.4.0: Graph500 benchmark-related definitions and data set generator.

G500.Generate

Description

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

Synopsis

# Documentation

Arguments

 :: Int Scale -> Int Edge Factor -> IO (GraphArr, GraphArr)
```%% 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.