How to code Sparse Tensors for representing multiple layers

Engineering
1

I’m finding that to unit test my opencl code with c++ catch, I need large arrays, or tensors, that are mostly unfilled. I could use dense vectors, but I want to use sparse maps since I’ll eventually be using something like that in opencl for efficiency.

I wrote a small sparse tensor class, but it’s complaining about not having a hash function, so I have to implement that. Also since I’m trying to work with different sizes to mimic the entorhinal cortex (e.g., for my image input, I could have {{800,600}, {400,300}, …}), I need to add a function for dealing with tensors with different sizes of arrays.

Before I get too deep into things though, I thought I’d ask if anyone has worked a lot on building sparse arrays, or at least thought about it. If so, what are some tips for creating sparse arrays on the computer? Any problems you’ve run into? Also, how does my code stack up so far?

Code: https://gist.github.com/SimLeek/808266d917af8d22e54dbe829eb5f876
(SparseTensor is at line 38. Test code is in a comment.)

2

A map as you implemented it is already a pretty good way to associate the few slots-with-a-value, to that value, and considering that any slot not found in the map holds a default value. (exactly as you check for, line 48).

However you’d maybe like to have both an operator const accessor, and an operator write-able accessor.
Here it seems like you’d add default values to your map even when reading the slot, which seems like defeating the purpose of the sparse map in the first place.

Now, insisting on fitting both read/write cases to same operator could be tricky, and solving this kind of concerns in the context of idiomatic c++ templates would maybe require defining things in terms of “iterators” ? Also, here the reference to the held value which is returned by the operator method will be invalidated each time the map instance reorganizes, possibly leaving nasty wrong memory address bugs depending on your use cases. I do not have the time to give it any more thoughts today, though.

[Edit] : I believe “map/unordered_map” implementation itself does not give a try at “fitting both read/write cases to same operator” : for immutable read access, you’ll use find().
So, i’d advise for another method along with operator (operator now being intended used as lhv only) :

const _Tpr& get(ConstructableArray<_Tpi,_Ndim> loc) const {
	auto it=sparse_map.find(loc);
	if(it==sparse_map.end()){
	    return default_value;
	} else {
	    return it->second;
	}
}

You then could use that structure directly for random access read/write, instead of having to convert to a full-valued vector and getting headaches about 2D typing concerns for that conversion (Unless you somehow absolutely need to send your data as a full-valued array, that is) .

“map” instead of “unordered_map” would not require a hash.

3

Also, if my problematic was to initialize a GPU array with sparse data without taking full bandwidth hit of sending the dense array, then here’s how i would do it with regular graphic-oriented stuff, if that makes any sense to you :

  • Final array is set up as a “texture” of the required dimension and size
  • Ask GPU to clear that texture to the “default value” in one go
  • Initialize and send a “vertex” buffer containing, for each non-default valued slot, a struct of its index and value
  • Ask a vertex-to-point “rendering” from that vertex buffer to the texture

Hope that helps,
Guillaume

4

I’m a novice with C++ from scratch (learning still as I go), but have been using it indirectly now for work for the past few months, via OpenCV’s python bindings. I’m much better with Python, though (and the ‘scipy’ universe).

You might have arrived at this idea already, but SDRs can be described in a binary, on-off state, akin to a black/white image. Connection weights for a column could be described as a grayscale image. Once you’re comfortable with it being an image, you can start to save layers out as PNG (lossless, unlikely to be corrupted).

Using OpenCV’s functions can give you an optimized starting place, or at least a reference for striking out on your own. :slight_smile:

I recommend taking a look at OpenCV 3.4, getting familiar with its bitwise operators, and cv::imwrite()/cv::imread() methods. I’d save layers out as PNG (lossless, unlikely to be corrupted). At the very least, checking out their code base might give you some ideas on how to work with matrices for your own project.

My two cents.

Max

5

Ah, well now it’s complaining about lack of a comparison operator. Looks like I need to make something either way. I might go back to unordered_map, actually, since hashes are a little faster.

Thanks for that get function though. That’s probably a better way of keeping things sparse than the idea I had of occasionally checking if values in the tensor were equal to the default value. Maybe something like a shared_ptr could work though, but that seems complicated

The problem here is that I’m not using the GPU to test GPU functions. There are some debuggers, but I haven’t seen much in the way of unit testing for OpenCL.

Besides, if I’m sending an unknown size list of indexes and values to the GPU, I might as well just get started on making a custom heap. This is more to have a stepping stone for that custom heap stuff, since it’s really complicated, and really complicated code has a much better success rate if it’s unit testable.

Thanks, but I was actually going for something with a lot more wiggle room. The templates allow me to test with multiple types, so I could have a uchar* or image_2d, or I could have a uint*, or a float*, or even a struct*.

Besides, I actually am using OpenCVs functions quite a lot. I have to use it for the camera, and I also use it in some cases where I want to use the CPU rather than the GPU.

I’ve worked with OpenCV in C++ though, and it is an option if I can’t get the SparseTensor to work. The matrix formats OpenCV uses would give me more of a full image than anything sparse.

Though, hmm… At that point, just a standard array might be good enough…

Thanks for the advice,
Josh

6

Hmm… I guess an advantage of OpenCV in python is that I can create a Numpy array and specify data types more easily.

I guess, what are the goals for your trying to code sparsity? Memory minimization? Speed?

I’ve been experimenting in a repo using the following setup: (EDIT: Current it’s a single layer pooler)

  1. Spatial pooler class is a list object to store all the column objects (don’t care about order too much)
  2. Each column object then uses:
    a. List to track the mapped indices between the column and the input space (don’t care about order) → tells column where to check in the input space.
    b. Dictionary (hashmap) to track the strengths of each connection to the input space (key = input space index value, values are floats)
  3. input space is sparse boolean array.

If I were to add a layer to my spatial pooler, I’d simply add an additional list object… maybe get mildly crazy by having a primary list to represent to overall pooler; the primary list could then hold each layer’s list of column references.

At that point, the spatial pooler object would just be a list of lists, with each sublist storing references to the column objects… in this whole scheme, the only fully populated tensor is the input space.

It’s fugly, but feel free to take a look and borrow anything that seems useful.