matrixsparse-matrixchapel

Is there a convenient way to fill a sparse array with random values in Chapel?


I am working on comparing matrix multiplication with and without locales and I am trying to use sparse matrices to work with the linear algebra module. I am planning on using blockdist and breaking it out manually with loops, but I want to be able to see if I can get speedup just using something simpler for now. If there is an easy way to work with blockdist that I am overlooking I would appreciate it. Anyway, I am able to get the code to work and to see a speedup when I just fill in the sparse arrays with one value, but filling it with random values does not seem to work:

use LayoutCS;
use Time;
use LinearAlgebra, Norm;
use LinearAlgebra.Sparse;
use Random;
use IO;

writeln("Please type the filename with your matrix dimensions. One matrix on each line. The rows in the second need to match the columns in the first");
var filename: string;
filename = stdin.read(string);

// Open an input file with the specified filename in read mode.
var infile = open(filename, iomode.r);
var reader = infile.reader();

// Read the number of rows and columns in the array in from the file.
var r = reader.read(int), c = reader.read(int);

const parentDom = {1..r, 1..c};
var csrDom: sparse subdomain(parentDom) dmapped CS();
var A: [csrDom] real; 
A = 2; //instead of this I would like to do something like fillRandom(A) but it seems to not work

var X: [1..r, 1..c] real; 
fillRandom(X);

//read in the other matrix
var r1 = reader.read(int), c1 = reader.read(int);

const parentDom1 = {1..r1, 1..c1};
var csrDom1: sparse subdomain(parentDom1) dmapped CS();
var B: [csrDom1] real;
B = 3; //same thing as with matrix A

var Y: [1..r1, 1..c1] real; 
fillRandom(Y);

// Close the file.
reader.close();
infile.close();

var t: Timer; //sets up timer
t.start();

var result: [1..r, 1..c1] real; //sets up matrix for results
  
forall i in 1..r do //goes through rows in 1st
  for j in 1..c1 do //goes through 2nd matrix columns
    for k in 1..c do { //goes through columns in 1st
      result[i, j] += X[i, k] * Y[k, j]; //adds the multiplications to the new slot in results
    }

t.stop();
writeln("multiplication took ", t.elapsed()," seconds");
t.clear();


t.start();
var res = A * B;
t.stop();

writeln("loc multiplication took ", t.elapsed()," seconds");
t.clear();

Does fillRandom not work with sparse arrays or am I doing it incorrectly? Do I need to go through and manually assign each value in the array with a loop? It is also of course possible that I am on the completely wrong path and should look more at blockdist and I would definitely appreciate any advice or tips regarding that as I'm not quite sure how I would work making sure each parallel task is actually running on the correct locale sections created by the blockdist.

Thank you in advance!


Solution

  • Does fillRandom not work with sparse arrays or am I doing it incorrectly?

    Random.fillRandom() does not support sparse arrays in Chapel today (1.22.0). However, I think this would be a reasonable feature request, if you would be interested in filing a GitHub issue on it.

    Even if fillRandom supported sparse arrays, the user would still need to specify which elements are non-zero before filling those non-zero elements with random values. This is done by adding indices as (int, int) tuples (or arrays of (int, int) tuples) to the sparse domain.

    Here is a small example of generating a 100x100 compressed sparse row (CSR) array with 10 non-zero random elements:

    /* Example tested with Chapel 1.22 */
    import LayoutCS.{CS, isCSType};
    import Random;
    
    /* Parent domain dimensions: NxN */
    config const N = 100;
    /* Number of non-zero elements */
    config const nnz = 10;
    
    const parentDom = {1..N, 1..N};
    var csrDom: sparse subdomain(parentDom) dmapped CS();
    var A: [csrDom] real;
    
    populate(A, csrDom, nnz);
    
    // Print non-zero elements
    for (i,j) in csrDom do
      writeln((i,j), ':', A[i, j]);
    
    
    /* Populate sparse matrix with `nnz` random values */
    proc populate(ref A, ref ADom, nnz: int) where isCSType(ADom.dist.type) && isCSType(A.domain.dist.type) {
    
      // Generate array of random non-zero indices
      var indices: [1..nnz] 2*int;
      var randomIndices = Random.createRandomStream(eltType=int);
    
      // Replace any duplicate indices with a new random index
      for idx in indices {
        var newIdx = idx;
        while indices.find(newIdx)(1) {
          newIdx = (randomIndices.getNext(ADom.dim(0).low, ADom.dim(0).high),
                    randomIndices.getNext(ADom.dim(1).low, ADom.dim(1).high));
        }
        idx = newIdx;
      }
    
      // Add the non-zero indices to the CSR domain
      ADom += indices;
    
      // Generate random elements - maybe fillRandom(A) could do this for us some day
      var randomElements = Random.createRandomStream(eltType=A.eltType);
      for idx in ADom {
        A[idx] = randomElements.getNext();
      }
    }