After working very hard during the last couple of weeks on my study thesis, I finished the last chapters today. In short what I did was to implement a performance efficient spiking neural net simulator from scratch in C++, including interfaces for Octave/Matlab (oh, how ugly can an interface be!) and Ruby.
The time writing reminded me at the time when I was writing the Ruby Developers Guide book back in 2001. At the beginning, you need to force yourself to get some sentences written. But after a while they flow more and more fluent out of your mouth (hands).
Ah, should I mention that I wrote my study thesis in English? I did it mainly to get a wider audience, but also because sometimes it is easier to describe technical aspects in English than it is in German, because a lot of words in computer sciene are already in English. But I have still problems with commats and English grammar :)
It’s really true. Sometimes you (in this case I) are too stupid to see the simplest things. That’s why it is so important to talk about problems. This morning I talked with my dad about the strange performance problems I had with my neural net simulator embedded in Ruby. He came to a simple possible reason that the nets that I simulate might not be identical.
Well, I wrote my own JSON parser in C++. I use reference counting to avoid memory leaks and to allow sharing of objects, while I don’t use this sharing at all. But at least it’s possible. You can spend a lot of time with these issues, just to be sure that you don’t loose any memory. This can even be a performance bottle neck, because C++ strings for example are copied by default to overcome the problem of “who owns the memory”. That’s all ugly and bullshit!
For some reasons I implemented the jsonHash class as a linked list. It was easier at that time. Especially was it easier with this implementation to make sure that the reference counting holds true. But of course, a lookup turned into O(n) ;-).
Then I changed the file format for neural nets. Yeah and there I used a very big hash with 10000’s of entries. In Ruby no problem. But with my O(n) jsonHash C++ implementation this just didn’t worked anymore (O(n^2) runtime). So I had to change the fileformat again, using arrays. The crux is that the Ruby version still used the “old” file format that had this big hash.
Now it is that in Ruby 1.9 hashes retain order, but I think I executed the conversion script with Ruby 1.8 which doesn’t retain order. So the neural net entities were created in a different order, and connected in a different order as well. This made a difference of 10 seconds, not loading the net but simulating the net. 10 seconds seems to be not much, but that’s around 40%!
Yeah, I’m happy ;-)
That’s the topic my study thesis will be about. Don’t mix this up with artificial neuron networks. They are pretty easy to simulate efficiently and easy to implement. Spiking or pulsed neuronal networks are much closer to biological neurons. There are two models of interest: Spike Response Model (SRM) and Leaky Integrate and Fire (LIF). SRM is more general and includes LIF.
I read an interesting paper about how to simulate those networks. At first, you can implent a time-discrete simulator. That is, each second (or any smaller fraction of time) you go through all neurons and calculate their value, synchronously. As the signals might change inbetween a clock cycle, you loose accuracy. To increase accuracy, you have to choose a higher simulation frequency. But this also increases the perfomance impact significantly.
That’s why you want to use a event-discrete simulator. Here, you will only recalculate the outcome of a neuron when there is an incoming signal (a pre-synaptic potential) for this neuron. This is also called an event. If the neuron crosses the firing-threshold, it will trigger an event for another neuron. There is one problem with this approach:
- Delayed firing
It may happen, that this neuron will not cross the firing-threshold immediatly, but after some time. We would loose that spike. So we have to look into the future and calculate when would be the earliest time this neuron could fire (using linear envelopes). We trigger an event for this earliest time, just to see if it really crosses the firing-threshold.
This event list must be ordered earliest event first. In the current implementation of our faculty, this is where most of the time is spend. Sorting the event list. It should be really easy to use a parallel sorting algorithm to solve this problem. Maybe a parallel priority list would be usable as well. Hm, if that’s all, then this study thesis is a piece of cake :). Well, maybe I can do a lot more optimizations. I heard about a paper that parallelizes the simulator to multiple CPUs. I haven’t read it yet, so I can’t say much whether it just parallelizes the event list sorting or the whole simulator. The latter would be more interesting for me ;-)