post google code post

Well nobody bothered to comment about the stuff i removed from google code apart from the one lad or lass who lamented the loss of some javafx demos.

I had comments open+moderated for a few weeks but got hit by spammers a couple of days ago so had to go back to id+moderated. Maybe something got lost in those 500 bits of snot but i don't think so. The spam was quite strange; most mentioned web sites but didn't provide links or weren't very readable so i'm not sure what the point was. Perhaps they're just fishing for open sites or naive moderators they can then exploit. Like the "windows computer department" that keeps calling and calling hoping i'll not tell them to fuck off every time (sigh, no i don't normally say that although i would tonight).

I've still got the subversion clones but i'm not inclined to do much with any of it for the forseeable future and i'm not even sure if i'm going to continue publishing other bits of code i play with going forward.

Desktop Java, OpenCL, ARM assembly language; these things are just not very common in the Free Software world. Server Java is pretty common but that's just, well, `open sauce' companies sharing costs and not hobbyists. So i think all i'm really doing is providing hints or solutions for some student's homework or help for graduate programmers to keep their jobs. And even then it's so niche it wouldn't be many, if any.

As an example of niche, I was looking up some way to communicate with adobe photoshop that doesn't involve psd format and one thing i came across was someone linking to one of my projects for some unfinished experiments with openraster format - on the first page of results. This happens rarely but still too often. Of course it could just be the search engine trying to be smart and tuning results to the user, which is a somewhat terrifying possibility (implications beyond these types searches of course). FWIW I came to the conclusion photoshop is just one of those proprietary relics from the past which intentionally refuses to support other formats so it's idiot users can continue to be arse-reamed by its inflated price.

It's just a hobby

As a hobby i have no desire to work on larger projects of my own or other established projects in my spare time. Occasionally i'll send in a patch to a project but if they want a bunch of fucking around then yeah, ... naah. In hindsight i somewhat regret how we did it on evolution but i think i've mentioned that before. Neither do i need to solicit work or build a portfolio or just gain experience.

I'm not sure how many hobbyists are around; anyone with remotely close to enough skill seems to be jumping into the wild casinos of app-stores or services and expecting to make billion$ and not just doing it for the fun of it. Some of those left over just seem to be arrogant egotistical fuckwits (and some would probably think the same of me). Same as it ever was I guess.

I suppose I will continue to code-drop even if it's just out of habit.

For another hobby I made kumquat marmalade on the weekend. Spent a couple of hours in the sun slicing the tiny fruit and extracting seeds (2-3 cups worth of seeds) and cooked it the next day. Unfortunately after all that effort it looks like it wasn't cooked quite enough and it probably wont set - it's a bit runny but at least it tastes good. Not sure what i'll do with 2-odd litres of the stuff though.

ahh shit, google code is being scrapped

Joy. I guess it's not making google enough money.

I'll make a copy of all my projects and then delete them. Probably sooner rather than later (probably immediately because i'd rather get it out of the way, i have a script going now). I'm keeping all the commit history for now although i never find it particularly useful. Links in old posts may break.

Some of them may or may not appear later somewhere else, or they may just sit on my hdd until i forget about them and delete them by accident or otherwise.

Wherever they end end up though it wont be in one of the other commercial services because i'm not interested in doing this again.

I need to do the same to this blog, ... but that can wait.

Update: So ... it seems someone did notice. Don't worry i've got a full backup of everything. In part I was pissed off with google and in part I wanted to make it immediately obvious it was going away to see if anyone actually noticed. Who could know from the years of feedback i've never received.

If you are interested in particular projects then add a comment about them anywhere on this blog. All comments are moderated so they wont appear till i let them through but there is no need to post more than once (i'll delete any nonsense or spam unless it makes you look like a bit of a wanker). I will see about enabling anonymous comments for the moment if they are not already on. I can then decide what to do depending on the interest.

I will not be using github or sourceforge nor the like.

In a follow-up post i'll see where i'm going with them as well as pondering the future location and shape of the blog itself. I've already written some stuff to take the blogger atom stuff, strip out the posts, download images, and fix the urls.

(in resp to Peter below) I knew the writing was on the wall when google code removed binary hosting: it's kinda useless for it's purpose without it. This is why all my new projects subsequent to that date are hosted differently.

on google

So google have decided to disable downloads on google code.

So I have decided to stop using it.

... although as yet I have no concrete plans or timeline for when this decision will take effect.

Whilst they claim it's about abuse, one can only assume that is just a "likely-sounding excuse" for what in reality is just another straight-up lie from the PR department of a supra-national conglomerate, and it's really just a way to cut costs and promote their 'drive' service (a useless microsoft/apple only service as far as i'm concerned).

Nobody seems to have reported that they have also gimped their POP interface to gmail a couple of days ago. No more UID support. This makes POP a lot less reliable/useful as a mail store (although in honesty it was never designed for that purpose). I proceeded to delete all the mail in gmail to help them free up some disk space.

I guess over-all the writing is on the wall. We all know that at some point 'google account' will mean 'google+', and blogger may be retired at any time.

So it seems my on-going-but-totally-lax search for alternatives to 'everything google for convenience' just got another big kick up the rump-side.

As my projects are all pretty small and low-volume I might look at a local solution because every network based solution faces the same problem. I have a couple of beagleboards doing nothing although getting a running and secure-enough system might be more pain than it's worth.

It's a bit of a pain to have to deal with.

Simple LBP Object Detector

After mucking about getting nowhere with a simple local binary pattern (LBP) object detector algorithm I finally had a bit of a breakthrough. Rather than getting dozens of false positives, i'm finally getting a concise enough answer to be useful for further processing.

Here is an example based on a photo I found on the net with a few faces in it (it's from here - i only found this using an image search, that page is just where i found it but I haven't otherwise read it). The yellow box is their result, the white boxes are mine (i'm not quite centring/scaling it properly yet).

The only tuning is a threshold and the grouping limit.

I'm actually quite surprised some of those faces are even found because this is one of the first tests i've done on more than a couple of images - and it has trouble with Lenna for example (but i suspect that is some aliasing issues with downsampling the larger countenance). I originally started with the eye set (from the OpenCV eye cascade), but was having trouble with false positives - e.g. eyebrows, mouth, dark spots. It seems to work much better with the face data. But most eye detectors on their own seem a bit noisy anyway so perhaps I was expecting too much.

I gave up on the cascade idea and this simply tests every position using the LBP u2 8,1 code (only 59 values) against a binary lookup table, and then each position votes on the outcome - once I get enough positive votes, it's considered a hit. This is similar to the LBP feature test in the OpenCV LBP detector, except that one uses the full 8 bits of LBP code, and of course the code is calculated on regions, not pixels.

I am only using the face and non-face images from the CBCL face dataset available here, which isn't a particularly good quality set of images. The only pre-processing i'm doing is mirroring the faces to double the training set. Training is very fast - after the images are loaded and converted to LBP, it's only taking 0.038s on my machine to `train' the 4858 positive and 4548 negative images (very plain single-threaded Java).

On the CPU the lookup isn't particularly fast (0.4s for the test image above) but I will look at porting it to OpenCL - it should be a very good fit for a GPU. If weighting isn't required, the feature description itself can be made very compact as it only requires 2 integers (64 bits) for each x,y location in the pattern - i.e. under 2K5b for a 17x17 test pattern (e.g. 19x19 training set, as the the LBP requires a 1 pixel border) which can easily fit in the constant cache.

There are still some tuning issues such as that a given threshold doesn't work equally well on all images, but it is still a promising result and there are still plenty of ideas to try.

Update (ok not really an update i hadn't published this yet ...) ... I coded something up in OpenCL and the performance is really very good - kernel time for the scaling (using a mip-map like thing), lbp building, and running the detector is around 2ms (same scales at the cpu example above). But this time doesn't include peak detection, thresholding and grouping. Still, this is pretty favourable compared to the VJ cascade as that does far fewer probes in it's 10ms runtime (and takes a week to train - if you can get that to work). Here i'm doing over 200 000 17x17 probes through 5 scales ...

I also played with a more statistically valid accumulation mechanism (as each test is independent): multiplication rather than addition (statistics isn't my strength by any stretch ... sigh). This leads to much more specific peaks as can be seen by the following picture, although i'm not sure if it leads to a more consistent threshold value (I think it does, and if that's true, I probably don't even need to do peak detection ...).

Both images are normalised.

Update 2: Had a bit more of a play this morning, tried a couple of different kernel topologies and using LDS to reduce memory bandwidth requirements. Got the kernel time of my test case down to 1.3ms, vs the 2.1ms yesterday (on a Radeon HD 7970). I also found the new combination metric is working well - I can use a specific value as the threshold and remove the peak detection stage entirely. It doesn't work too well with the eye data (way too many false positives), but it's pretty good with faces, so far.

Viola & Jones Revisited

So after the last post it got me thinking about just how I did implement the viola-jones haar cascade in socles.

The code runs in a loop, and there is no communications from the CPU to the GPU and only runs about 10-15 loops anyway (depending on the settings): thus the loop overheads are fairly small. But it still does require a 'scale features' step, which is useful on a CPU to avoid excessive calculations but isn't so important on a GPU.

So I tried a slightly different approach - that is, to perform the scaling inside the detector kernel, which allows each kernel to then work on different scales. i.e. to do all scales in one step.

My first attempt at this wasn't much faster - but that's because I was invoking the kernel for too many probes. So then I tried changing the way it works: each work-group still works together solving a single feature test stage together. But instead of calculating it's location and scale from the 2d work coordinates I create a 4 element descriptor with some of the information required and it just uses that. This gives me a bit more flexibility in the work assignment, e.g. I can utilise persistent work-groups and tune the work size to fit the hardware more directly. It requires less temporary memory since the features are scaled in-situ.

This change was definitely worth it, for a given test on the webcamfx code, I got the face detection down to around 13ms total time, vs 19ms - about 4ms overhead is fixed. A stand-alone test of Lenna registers about 8ms vs 19ms, so over 100% improvement.

Comparisons with other hardware are difficult - mostly because it depends a great deal on the subject matter and the settings and i haven't kept track of those - but I was pretty disappointed with the AMD performance up until now and I think this gets it on par with the nvidia hardware at least. Although really the 7970 should do measurably better ...

My guess is that the performance gained is mostly because with the greater amount of work done, it can more efficiently fit the total problem onto the hardware. There is usually a small amount 'modulus' where a given problem wont fill all hardware units leaving some idle, and in this newer version it only happens once rather than 10-15 times. Actually I did some more timing (and updated the numbers above), and 100% seems too much for this. Maybe? Oh I also changed the parallel sum mechanism - but I changed it in both implementations and it made no difference anyway. I changed the region description to a float array too, although that only affects the scaling function in the first instance.

If I run this on a CPU the performance is very poor - around 1.5s for this test case. If I go back to a test CPU version I wrote it's a more reasonable 240ms so i'm still getting a good 30x speedup over an Intel i7 X 980. Given I was getting 90ms before with the cpu driver and the nvidia test case i'm not really sure what's going on there.

I haven't checked the code in yet as it's a bit hacked up.

Update: I checked some stuff in, although left both implementations in-tact for now.

Update 2: So I did some further analysis of the cascades I have: it turns out the way i'm splitting the work is very wasteful of GPU resources. I'm using at least 64 work items per stage - using one work item per feature. But the earlier stages have only a small number of features to test - and the vast majority of probes don't go past the first few stages. e.g. the default cascade only has 9 tests. I tried a few variations to address this but the overheads of multiple kernel calls and the global communication required outweighed any better utilisation.

Update 3: So curiosity kept me poking. First I realised that using fixed scheduling for persistent kernels might not be idea. So I use an atomic to dole out work in a first-some-first-served consumer way. Made a tiny difference.

Then I thought I would try to see if using fewer work-items per feature stage would help. In this case I use 4x16 or 2x32 thread groups to work on 4 or 2 tests concurrently - with all the necessary (messy) logic to ensure all barriers are hit by all threads, etc. This was measurable - the lenna test case I have is now down to around 7ms (unfortunately when using sprofile the algorithm fails for some unknown reason - so this is now time measured with System.nanoTime()).

One big thing left to try is to see if localising the wide work queue would help. e.g. rather than call multiple kernels for each stage and having each work-item busy working on a sub-set of problems, do it within the kernel. e.g. if the stage count is 9, 12, ... do stage 1 with 7 concurrent jobs, if any pass then add them to a local queue. Then do stage 2 with (64/12) = 5 concurrent jobs, if any pass add them to a local queue. etc. Once you get to a stage longer than 32 items, just use 64 threads for all the rest. This way I get good utilisation with small stages as well as with large stages. I'm not sure whether this will be worth all the hassle, and the extra addressing mathematics required (and it's already using a lot of registers); but as i'm really curious to know if it would help I might attempt it.

Given that I now use a work queue, another possibility open is to re-arrange the jobs to see if any locality of reference can be exploited. Given the huge memory load this might help: although the image cache is so small it might not.

Update 4: Curiosity got the better of me, it's been crappy cold weather and I hurt my foot (i don't know how) so I had another look at the complex version this morning ...

Cut a long story short, too many overheads, and although it isn't slow it isn't faster than just using 16 or 32 threads per feature test. Too many dynamic calculations which cannot be optimised out, and so on. It's around 9.5ms on my test case.

Structurally it's quite interesting however ....

1. Find out how many concurrent tests can be executed for stage 0, dequeue that many jobs from the work queue and copy them to a local work queue.
2. If we exceeded the job length, stop.
3. Work out how many jobs can be done for the current stage
4. Process one batch of jobs.
5. Parallel sum the stage sum.
6. If it advances to the next stage, copy to a next-stage queue.
7. Go back to 4 unless finished the in queue.
8. If any are in the next-stage queue, copy them over, advance to the next stage.
9. Go back to 3 if we had any work remaining.
10. If we ran the full stage count, copy any work jobs remaining in the queue to the result list.
11. Go back to 1.

So each stage is fully processed in lock-step, and then advanced. The DEFAULT cascade starts with 9 7 feature tests, so it never has more than 9 7 items in the queue (7 feature tests of 9 elements = 63 work items). As the stages get deeper the number of work-items assigned to solve the problem widens, up to a limit of 64 - i.e. the work item topology dynamically alters as it runs through the stages in an attempt to keep most work-items busy.

There's a lot of messy logic used to make sure every thread in the workgroup executes every barrier, and there are lots of barriers to make sure everything works properly (i'm using locals a lot to communicate global info like the stage and topology information). So the code runs on a CPU (i.e. I got the barriers correct), although very inefficiently.

As is often the case with GPU's, the simpler version works better even if on paper it is less efficient at filling the ALU slots. Although I haven't confirmed this is the case mathematically: apart from stage 0, the more complex method will also have un-even slot fillage - it's one of those discrete maths/Knuth style problems I simply give up on.

AMD Fusion Summit, HSA, etc.

Been looking forward to watching the AMD Fusion summit this year after watching a bunch of very interesting videos last year. I knew they were coming up but this month has gone faster than I thought ...

So far i've just watched the 'programmer' keynote from Phil - it's a pity about the emphasis on C++ which is such a shit language - but what are you gonna do eh? His talk on the viola-jones haar cascade algorithm was interesting, how HSA could be used to split up algorithms to move the problem to where it is most efficiently solved (not sure how it compares to face-detector in socles, as I solved the problem of idle work-items in a different way). But yeah, looking forward to that capability in the future; during my last visit to OpenCL in the last month or so I kept thinking that being able to run stuff on the CPU where it made sense would ... make sense.

I slightly disagree that the problem with the GPU parallel programming is just that it is too hard to write - all good software is hard to write - I think it more has to do with the availability of the platform. e.g. PS3 is hard to write too, but there seems to be plenty of that now because everyone's writing to the same platform. If I was a commercial developer writing software, right now it's only going to be a niche (photoshop is a niche). This is ok - because niche customers are probably already using capable hardware or don't mind buying it - but for mass market adoption it requires mass market availability of stable, quality, compatible platforms. This is still some way off.

The videos are on the summit broadcast site which requires a freely available login.

Update: Blah, ahh well, mostly a bit dull & sparse this year, or maybe they just weren't all put up on the net. The HSA stuff is the most interesting again from a software perspective.

Update 2: Apparently more content will be added over time, I guess last year I didn't spot it for a few months so had a lot more to look at off the bat.

On more reflection the HSA foundation and the HSAIL stuff is pretty big news. People don't seem to understand why it's so important though. It's really about the H in HSA - heterogeneous. Being able to support many CPUs with the same code and even the same compiler. Being able to target the code at run-time to execute on the most efficient hardware available in the current system. And being able to do that in a practical way that isn't tied to some vendor-specific secret sauce using broken proprietary compilers. At the bottom of it, it's just another attempt at 'write once, run everywhere' technology, but this time for computationally intensive processing and not for desktop user applications. I guess time will tell to see how it goes without nvidia and intel though. And the same as to whether this finally allows free software to take part.

The other part of it is coming up with a set of re-usable libraries so that the performance is opened up to non-gun-hackers (or in their terms, non-'ninja'-programmers), although TBH I don't see that is any different to any other modern hierarchical programming environment full of frame-works and tool-kits. This can already be done with OpenCL anyway, but I suppose there is still messy crap to deal with from the idiot-programmer's perspective. e.g separate memory spaces, device-host copy overheads and so on. HSA with code transparently intermingling with plain old host code means the same could be done without the overheads and make it more attractive.

I still think the biggest hurdle for application developers is platform support. Any extra work has to be justifiable if it is only going to benefit a part of your customer base.

Update: I never got around to seeing the actual talks at the time but I just found that Stream Computing have a nice index of all the OpenCL specific talks. I'm not a regular reader of their blog but every now and then I do a search in which it turns up and I do a catch up ...

Idle minds ...

So it turns out I have a bit of a break between contracts again - i'm always happy to have extra time off, so there's nothing to complain about there!

I sat down on the weekend and yesterday to play with some socles code, but so far it's been really slow going. I just don't feel like getting too much into it and it's easier just to put it down if i hit a problem; I guess I really do need a bit of a break. I also have tons of crap to do in the back yard, shed, and even around the house as well; but i've been a bit lazy on that front the last year or so, as such I doubt much will happen there.

But yeah, I guess eventually over this break I will get the opencl ransac stuff sorted out in socles, and probably then re-visit jjmpeg to at least check in the code I've already done on the android stuff.

I tried the 12.6 beta catalyst driver yesterday - and thankfully it seems a lot better than 12.4, so far, touch wood, etc. At least it doesn't keep throwing up OUT_OF_HOST_MEM errors after a half a dozen code runs, AND the xinerama twin-screen desktop is back up to decent performance. So after finally getting a GCN GPU I would like to have a play with that and see what I can get out of it. I should probably try and come up with a specific application I want to try to implement and work toward it as well, rather than just poking in random algorithms to socles. The thing is, computers mostly just do what I need them to do (run emacs and a terminal in overlapping windows?), so i'm not particularly driven at this point.

I'm keeping an eye on the ARM stuff; the rhombus tech guys, the open pandora (who knows if i'll ever get the one i ordered - at least an email confirming the order and address once a year would be nice), but with a bunch of beagleboards sitting idle already it doesn't seem much point in me getting another dev board to poke at. Just not enough hours to look at everything that is interesting ...

On the RANSAC code, I pretty much have it done - it's just that messy testing to go. In this version I tried to do most work in the one kernel - I will see if that added complexity makes it slower, or the lower memory demands help it overall. I also tried to parallelise absolutely everything, from coordinate normalisation/result denormalisation to matrix setup. So far i'm getting a strange result in that just the SVD is somewhat slower than just the SVD I had before: although for all intents they are the same design. Once I have it going I will try double arithmetic to see if that generates better results.

Oooh, faster

Well, after a hair-pulling week (well I need a haircut, and i'm having a break for a few weeks next week) I'm finally getting somewhere with the HD7970. Not just having it crash the machine on me every test run makes for a much better day.

Some of that time was spent trying to track down crashes inside the clsurf code ... but they were all because I didn't notice that it needed images rounded up to 16 pixels wide ... sigh. Oops. Most of the rest was some barrier issues with my new code - it's been a while and I forgot some of the finer points. Getting it working on a CPU driver was a good help there because if you get the barriers wrong you just get nonsense results.

There was also a lot of time wasted rebooting - not only because of the code that crashes the driver, but because it still decides to start returning CL_OUT_OF_HOST_MEMORY all of a sudden. And I didn't realise till last night I can just log out of/back into X to fix this until it happens again. And time wasted verifying my drivers were ok too - which probably was wasted (and now i have a broken dependency map and catalyst libraries splatted over lib64 to boot). And finally I think I found a bug in the AMD driver as well, it's getting a divide-by-zero signal (which causes the jvm to abort!) when using a local worksize < 64 - this isn't something I normally do, but the occasional algorithm benefits from it. It's not too difficult to work around at least.

AAaaaaaanyway ...

I finally have some RANSAC code working on the new card. And it's a screamer.

I'm getting around 2-3x total performance boost compared to the HD6950 for one run of the RANSAC code. Although I can up the number of RANSAC random probes by 4x and still run about 2x faster (this was not the case with the 6950, 2x probes meant 2x time taken) (so it's about 8x faster then). I thought i'd make a plot of the scalability to see how it does.

The stuff below 40 is pretty much 1.0ms, the ups and down are just sampling noise.

In this case, the number of work-groups per compute unit means the number of jobs queued would mean that many work-groups (wave-fronts) per compute unit. The 7970 has 32 compute units, each work-group does 7 matrices concurrently, so that means 40 on the X axis equates to 8960 RANSAC probes, i.e. solving 8960 9x9 matrices using SVD, and forming the homographic matrix with a couple of 3x3 matrix multiplies on the result takes about 1ms.

So, anything under 9000 checks is wasting resources on this machine.

So whilst writing this post and after doing all the timing i revisited a tiny part of the algorithm - the heaviest bit of the SVD is the error calculation which involves 3 sums of products across all 8 rows. For the HD 6950 I got a 2x speedup by using a simple loop vs a parallel sum - calculate the products in parallel but sum them in series directly in registers, but only in 1 thread of 9. I just noticed the ALU usage was a bit low on the 7970, and I turned back on the parallel sum. Well what do you know, ALU instruction count dropped from 9500 to 5900 and reduced the biggest case above from 2.3ms to 1.7ms (which is closer to a linear scaling anyway).

Sigh, now to debug some older and far more complex code that is not working 100%.

OpenCL SURF

Over the weekend I ported the clsurf code to socles. I had a bit of a play with a few other things as well although they didn't make much of a difference to the execution time (well, maybe 10% maximum kernel time). I guess one thing to try will be to change it so that it doesn't need to communicate with the host at all: it should be possible with some 'persistent' kernels and forcing a hard-limit on the feature point count.

I put a few more details over on the project page.

oooh fast

Well I had a frustrating yet productive day today following on from yesterday's progress.

I ported the Jacobi SVD code to OpenCL and managed to paralleise most of it. I'm using 9 threads per SVD column which lets me paralleise all of the rotations. The code itself is somewhat simpler than the LU decomposition I worked on earlier, and it parallelises more easily. Actually having 9 threads also allows me to implement a 3x3 matrix multiply in 4 lines of code as well so it all fits nicely. I'm using 63 threads per local work group so the few times I do need barriers are just compiled out anyway. I also removed some of the code I don't need: e.g. fixing up the singular values and the U matrix at the end. The only bit which isn't totally parallel is the error calculation of the columns, but even there I was able to utilise a parallel sum to help.

I'm not really sure of the numerical stability; it works for my test cases.

So yeah, it's pretty fast - I'm currently doing batch sizes of 2000 homographies, and the SVD calculation and generation of the homography matrix is taking about 3.5-4ms - somewhat better than the 200ms or so from the CUDA RANSAC code (although that does a bit more work as well). I'm still doing the randomising and setup of the input matrix on the CPU, but that's the next candidate to move to the GPU. The GPU code to check for inliers is in the range of a 140uS as well. Once I re-arrange the code a little I will be able to keep all the data on the GPU - e.g. from SURF generation all the way through to final homography matrix.

I had thought real-time was going to be impossible, but now i'm not so sure.

The 3x3 matrix multiply fell out very simply - having 9 threads already assigned to each column of the SVD meant I had 1 thread per 3x3 matrix cell as well. I haven't had to look too much into matrix stuff on the GPU so far, so it was satisfying that such a neat solution presented itself when I did.

void mult3x3_gl(uint lid, uint cid, uint ar, uint ac,
    global float *a11, local float *b11, local float *lwork, local float *r11) {
 lwork[lid + LSTRIDE * 0] = a11[lid - cid + ac + 0] * b11[lid];
 lwork[lid + LSTRIDE * 1] = a11[lid - cid + ac + 3] * b11[lid];
 lwork[lid + LSTRIDE * 2] = a11[lid - cid + ac + 6] * b11[lid];
 barrier(CLK_LOCAL_MEM_FENCE);
 r11[lid] = lwork[lid - ac + LSTRIDE * ac + 0]
  + lwork[lid - ac + LSTRIDE * ac + 1]
  + lwork[lid - ac + LSTRIDE * ac + 2];
 barrier(CLK_LOCAL_MEM_FENCE); 
}

Here lid = local id, ac = lid % 3, cid = lid % 9 (base of matrix for this work item), LSTRIDE=64. With a worksize of 63 it means this does 7 3x3 multiplies at once and the barriers vanish.

It's nice when everything totally parallelises and there are no special cases.

The most frustrating part in all of this was getting the addressing right. For the SVD I came up with a complex addressing scheme where 9x9 matrices are stored in groups of 7 side-by-side. A few more grey hairs and a hoarse voice over trying to get that to work.

Also spotted a strange problem with the AMD driver: If I use printf, then I cannot use a cached binary or it simply crashes. If I just add a space to the code to force a re-compile (my cache uses the whole source as the key) it works ok.

SURF, RANSAC, OTHERALLCAPSSTUFF

With the prototype out of the way I'm back to looking at algorithms again, at least for a couple of weeks. It seemed a good opportunity to finally try and nut-out RANSAC for building homographies for mapping between images. I've previously looked into it but got no-where because it was all totally matlabotomised code and difficult to decipher.

I thought i'd start with this CUDA RANSAC implementation since at least it had all the right structure in place.

Of course, then i needed to get SURF going ... which I had previously played with (half-heartedly) and failed, but now with clsurf around, I just ported that to JOCL (which was thankfully a simple task as the code structure is similar to the way I write stuff). And that pretty much 'just worked', so all good so far.

Porting the CUDA RANSAC code wasn't much work, but I wasn't getting great results, nor great preformance so I ported that to Java to gain a deeper understanding. After a bit of searching I found EJML which I used for the SVD this time just to make sure.

Another implementation ...

I still wasn't grokking it - although by now RANSAC itself was starting to make some sense - so I kept searching. I found this interesting homework solution which had a complete, readable, and well explained RANSAC algorithm. At last. So finally i was getting reliable results - a bit slow mind you - but reliable if I let it run long enough.

One issue I had is that I seemed to need a great number of iterations to get a quality result - several 10s of thousands. i.e. a bit slow. Something like 20s for one of the data sets I had. I found out that much of the time was taken up with in-lier check, which is quite simple and although it processes many points should've been faster. It seems the E of efficient in EJML doesn't quite stretch to small matrices. Hand-coding that, and simplifying the test to only check the forward transform sped it up considerably. With a bit more tweaking the test-case is down to around 1s - for single-threaded java code.

I also found this site which has a bunch of matlab scripts and one is for a more complex version of the homography calculator which uses less FLOPs (I started with the paper 'Computation of Homographies' by Harker and O'Leary - but for whatever reason the site I downloaded it from seems to have removed it since). That seemed worth looking into, so I created an implementation of that as well. It didn't seem much faster at first but on further investigation it seemed worth looking into. It gets most of it's speed from running two smaller SVD's (4x2 and 8x3) rather than one larger one (8x9).

I was thinking at this point I might just forget about the SVD stuff on a GPU - i can find other work for it to do and the SVD code I was looking at (in EJML) is very complex. But with the fixes to the inlier check now it was taking about 50% of the time; which meant that even with multi-threading I probably couldn't keep the GPU very busy with in-lier checks. My first attempt at this generated a single result on the CPU then double-buffered the matrices to the GPU for it to perform the inlier check. Unfortunately the driver overhead was too great; I got it down to about 4s (for 10K iterations), but most of that time was in the driver synchronisation. After thinking about it a bit more I was going to do a whole batch instead, but then I did some more profiling and realised it was only going to give me at best a 2x performance boost, so I thought i'd go for some higher-hanging fruit first.

So I revisited the thought of creating a fully-GPU implementation. So as it happens I ended up back with the GSL version of the SVD code which was in the CUDA_RANSAC stuff. I dropped that back to Java and got it working. I noticed the code almost always does operations on columns, and indeed, copies the columns around a couple of times just for good measure. So I transposed the data and operate on rows instead: which means I can parallelise some of the internal loops as well. With a few more tweaks this is now the fastest version, 50K iterations take about 0.85s.

I'm still working on implementing a version of the 'optimised' homography algorithm at the moment, as it needs some more work - e.g. an implementation of pinv. But given I have the basic version working I should probably try to port that to OpenCL first, to see if I will get much benefit.

I probably need to investigate trying to reduce the iterations required. At the moment I am doing a simple nearest-neighbour match using an L2 measure, so this could probably be improved (but given results as below, it is doing a fair job).

This is a display of the inliers. There are 249 inliers from 571 putative matching feature points.

This is the result after running clsurf to find feature points, running a sum of squares match against the feature points to find the putative matches, and then running RANSAC for 50K iterations to find the homography.

SURF and the nearest neighbour match are running on the GPU (in ~50ms total) with the RANSAC entirely on the CPU in single-threaded java - in about 0.95s for the 'unoptimised' homography calculator.

This is the image after the homography is applied to each corresponding picture. i.e. the source right-hand image has the inverse homography applied to generate the output left-hand image. And visa versa.

Filter Graph

This morning I threw together an implementation of some of the ideas I mentioned in the last few posts for a filter/processing graph and checked them into socles.

I had a pretty good result applying the same ideas to my work stuff and I want to eventually use them elsewhere and experiment as well. The main thing I'm trying to resolve is the memory management and scheduling issues. Well I guess the other thing which is also pretty `main' is that by having a component framework it is easier to encapsulate functionality into re-usable connectible parts: i.e. less code, more functionality.

At the moment I have a dummy graph executor (it executes jobs in the right order, but not with any event management), and I still need to play with the queuing. But simple examples work because it's always using the same queue, and the climage-to-java-image conversion is necessarily synchronous. If I get it all working right, separating the graph execution from the nodes will allow me to try out different ideas - e.g. multiple queues, even multiple devices(?) without having to change the underlying code.

Actually one of the biggest hassles was attempting to support Java2D images as much as possible. I've tried to ensure images never lose any bits, although they may need format conversion (e.g. there are no 3-channelx8 bit image formats). I haven't tested all the formats as yet so quite likely the channel orderings are broken for the colour images (it's usually easier to just run it and tweak it till it works rather than try to grok all the endian-ness issues and ordering nomenclature of every library involved). I've got a feeling it was a bit of overkill - Greyscale/RGBA, UNORM_INT8/FLOAT are probably the only formats one really needs to handle at this level. Given that there are efficiency issues, it may be that I throw some of the code away so they can be addressed with less work.

Anyway, a simple example shows that even at this stage it can be used to create useful code: SimpleFilter.java. (at this stage it's not doing resource management, but most of the skeleton is there to handle it).

Eventually I want to be able to do similar things with video sequences (via jjmpeg).

(To what end? Who knows?)

Processing Graphs 3

So based on the stuff in my previous post I decided to ditch the stuff I had already done for work and start with the stuff I worked on in socles on my hack-day as a baseline.

I had to fill out the event management stuff, and then I had to port the few processing nodes I had already ported to my other half-arsed attempt - which apart from a couple of cases was fairly straightforward. I kept the getInputX/getOutputX stuff, implemented some image converters, and wrote a video frame source node (which turned out a bit more involved than I wanted).

Some of the code is a bit messier, and now i've implemented the event stuff I had to go back and fill that out: which was a bit tedious. The 'source' interfaces are a bit of extra mess too but aren't any worse than implementing bound properties and in some cases I can sub-class the implementation.

The graph executor is nice and simple, it visits all nodes and runs every one once in the right order based on the graph. Each execution produces a CLEvent, and takes a CLEventList of the all events from pre-requisite incoming nodes. Each node takes a queue, a CLEventList of conditions, and a CLEventList to which to add it's (one-and-always-one) event output. It wont handle all cases but it will do what I need.

Because input/outputs use simple component-ised syntax, I can auto-connect some of the sources as well using some simple reflective code: this is only run once per graph so isn't expensive.

Possibly I want to allow individual 'source' instances to be able to feed off their own valid-data events too: although I think that's just adding too much complication. If nodes produce partial results the nodes themselves can always be split.

So after all of that (it's been a long day for unrelated reasons), I think it's an improvement ... at least the individual nodes are more re-usable, although some of the glue code to make the stuff I have work is a bit shit. I still have a bunch of cpu-synchronous code because I can't tie in user events with the api I have (I need to update my jocl for that), but with the api i've chosen I should be able to retro-fit that, or other possible design changes later on (e.g. multiple devices? multiple queues?) without needing to change the node code.

Actually I wish I had had more time to play with it in socles before I went with it, because there are always things you don't notice until you try it out. And things are a lot simpler and easier to test in the 'WebcamFX' demo than in a large application. This is also just a side-issue which is keeping me from the main game, so I want to get clear of it ASAP, whereas in socles it's just another idea to play with.

Processing Graphs 2

So, I looked into implementing the graph idea on Friday.

I came up with a really simple bit of code that runs everything in the right order, and a few 'nodes' which wrap some of the stuff in socles in re-usable components. I'm working on a simple component architecture that could let a GUI for example auto-query some of the node capabilities and data i/o ports.

I changed my idea on the data format stuff, and now the components explicitly import and export a given type: so either the application can know what is needed to interface disparate functions, or potentially graph code could just add it in as needed.

For example, something that might take two images and blend them together might have:

 ImageSouce getOutputImage();
 void setInputA(ImageSource);
 void setInputB(ImageSource);
 void setInputFactor(ValueSource);

The *Source types are interfaces which let you retrieve the actual data or value (and perhaps meta-data thereof). Reflection can be used based on the names (setInput/setOutput) and/or the argument/returns (instanceof Source) in order to auto-create GUI or auto-connect parts.

Although I didn't quite get that far I pretty much worked out the event generation stuff too: each node takes a CLEventList condition, and CLEventList events (these are the way all CL calls are synchronised) and honours/updates them as if it were a single call. i.e. waits on the condition, and then sets a single event on events either via a enqueue call or using user events when it's done. And although the graph is invoked synchronously, this allows for asynchronous operation: i.e. any call that might block (e.g. read-modify-write from gpu) just shuffles it's work off to another thread/work queue and it can sync up later. Well that's the intention anyway. I'd like to be able to automate the parallelisation via queues across the graph paths as well, but I should get something working first.

I hit a bit of a hurdle with JOCL not allowing user events to be added to an event list: which means I couldn't get much further with some of the stuff I wanted to do (allow java code to participate in the OpenCL managed event graph). If JOCL wasn't such a pain to build and then propagate to the various projects I would've added the trivial patch to get it working, but by then it was pretty much the end of the productive day anyway so I left it at that.

As an aside: i'm not sure what possessed me to actually start work on this, but I have previously considered - and dismissed - hacking together another jni binding for opencl (there's little things every now and then that get me thinking about it, but usually my senses kick in before I start). Because there's a lot more involved than just the code it's really not an avenue I want to cycle down. But this morning - complete with hangover - ugh, which still seems to be lingering now at the other end of the day - I started with openal and then looking into opencl. I use gcc and cproto to simplify the stuff I need to parse, filtered further by a few greps in a shell script. Then another big ugly perl script to process these into bindings and classes. Anyway, that stuff probably wont go anywhere. Probably.

Processing Graphs

So, I've been looking into how to re-do the processing graph stuff in my customer's application over the last few days. First reason is I need to change the way it works, from a real-time interface to an interactive/batched one. And the second reason is that thinking about how Aparapi works (or could work with added concurrency) got me thinking that I really could do a better job at simplifying the whole lot, whilst making it more useful.

Currently I have a processing tree, and use threads and multiple queues to feed the data around so the main feeding thread isn't blocked on long-running tasks. There are basically 3 levels of abstraction: the top-level tree which consists of processing nodes which are invoked in the correct order: these might call kernels directly or higher level components. The middle level is only there sometimes, and includes more complex routines which consist of several opencl kernels combined in various ways with it's work data (e.g. something like KLT). And the lowest level is the direct kernel bindings (which usually do not manage their own data) very much the same as the ones in socles. The tree only defines the invocation order; data relationships are statically created/assigned at tree creation time or dynamically synchronised at run-time.

This works ok, but it is pretty messy and none of the top level is re-usable in the least (and there's little middle-level to re-use). It is actually fairly efficient - 'real time' means for some tasks I have plenty of spare time to waste and give up to to background jobs, so small bits of cpu-synchronous code aren't a deal-breaker. Obviously I want to simplify the usage of this, whilst increasing the possibilities for automatic job-level-parallelism.

My first re-cut of this was to take much the same idea, but make a couple of alterations. Firstly to re-arrange the abstraction levels, so that the top-level doesn't do so much direct kernel invocation but move this code to more second-tier components which are hopefully more re-usable. Either way this should be a big plus. And secondly to simplify the data management; use the tree to define data flow, automatic data conversion between stages, plus a bit of double buffering to cope with cpu synchronisation and some cpu parallelism (at least, one-way cpu-to-gpu). But otherwise basically just a synchronous fixed call-tree managed by a single queue.

But I don't think this is going to cut it either. It's not really flexible enough and unless I have lots of batch processes running concurrently (which i wont) the device will be underutilised in many cases.

Last night I started working on a socles version of something similar but quickly got bogged down in the data-conversion issues which get messy pretty fast (I want to be able to mix and match image, array, and java native graph nodes without each having to worry about where the data is coming from). And that was before I got onto the synchronisation stuff.

Yesterday was just a crap day anyway: very little sleep, grumpy as hell, and not able to think straight, so it was flying blind a bit by just not being on the ball ...

Then I realised this morning (i'm sure now that i knew this, and this is one reason I didn't want to do a call-graph interface in the first place; i'd just forgotten about it); opencl already has all of the stuff required to manage the processing graph (and it can handle a graph, not just a tree) (or I would've realised earlier if my searches hadn't have kept pointing to the 1.0 spec). The graph invoker just has to call the processing nodes in the right order, and it can build and maintain the event nodes used to link them all together. User events can be used to synchronise with (asynchronous/mt) java-side processing so I don't need to stop that branch entirely just to do some cpu code. All the processing nodes need to do in addition to their work is use the standard opencl condition/event set to ensure synchronisation. I can possible even manage queue stuff automatically. The data conversion stuff will still be a pain - but it's just a pain anyway and just can't be avoided.

Representing the graph in a simple way and turning that into an invocation sequence with events is another issue, but at least it gives me something new (to me) and useful to learn about.

socles denoise/sharpen

This morning I ported the ImageZ denoise & sharpen stuff to soclesdemo now that I have the QWT code (mostly?) working.


I still get occasional GPU hangs, but it is completely random: maybe it's code bugs, maybe it's driver bugs ...

It scales fairly well: I tried a 4288x2848 pic, and it was still interactively-quick (swing stuffed up visually since it isn't in a scroll-pane, so I couldn't see how long it was taking), and much of that time was to/fro java/swing/X. For a 1546x1178 image it was about 8ms for a the full wavelet processing (kernel times). It's only greyscale. This 1-2 orders of magnitude faster than a contemporary high-end cpu, so is well worth it: and it makes real-time 1080P processing possible.

But for an interactive application however you would only need to perform the forward transform once and just apply the thresholding and inverse with each change. So in that case it could be quite a bit faster.

Source

• The GUI driver code.
  
• The soft-thresholding + scale kernel which implements the smooth/sharpen on the quaternion wavelet values directly.

QWT

Since I haven't done any work in OpenCL for a while I thought on my hacking-day today I'd poke around socles for something different.

I managed to mostly get the quaternion wavelet transform code I started pre-xmas working, at least for the forward transform. It is based on the code I have in ImageZ, which i've mentioned before. This can then be used to form a dual-tree complex-wavelet-transform 'on the fly' as I do in ImageZ, or by copying to another structure (these both have some fairly interesting properties, so far i've only done work with denoise/sharpen, but there are also other applications such as registration).

It was actually a bit of a ramp-up to remember where the code was at. And then to decipher what it was supposed to do. For what consists a fairly simple algorithm (dual-convolution - the difficulty in wavelets is the filter design) there is a lot of very fiddly addressing and mucking about. Implementing upfirdn which is essentially what it uses is a pain even with such simple ratios as 1:2 and 2:1.

Although I seem to be getting an ok result, sometimes when I execute it on my GPU I end up having to hit the reset button ... so it's stuck on the CPU for now. Probably just some bounds checking errors. I'm not really on the ball today, pretty tired and grumpy, and I spent the better part of the day working on it so far; bit shit considering I already had a working Java implementation and most of the OpenCL scaffolding done. I guess not every day can be a super-productive one.

As above, i've only worked on the forward transform so far. Most of the tricky stuff is in the DWTGenerator which started as a copy of the convolution generator class, although QWT.forward() is a lot hairier than it looks too. I also managed to improve on the ImageZ code a tad: the redundant copies and vertical transforms aren't needed as I in-lined the sub-routines and have simpler data management.

Update: Well I just kept poking at it, and eventually ended up with getting the inverse transform working: sometimes it just takes perseverance. Unfortunately the forward transform still crashes my GPU quite regularly and I haven't traced that down yet.

Between the resets I did manage to get a couple of runs through sprofile: it's about 350uS per transform for a 512x512 depth=1 transform, on a Radeon HD 6950. There are some LDS bank conflicts in the X convolutions, although the main bottleneck is the Y convolution since it cannot benefit from LDS and relies on coalesced reads and the global cache. I'm reasonably happy with that, and i'm not sure I can get much more out of it.

socles updated for jogamp 2

Just to show that it's not all angry rants around here ...

Continuing my mirror of the news items on my projects, I just updated socles to include jogamp 2.0 - fortunately the API was the same so it was just changing the included libraries in the build.

I still have a JOAL patch outstanding but just haven't been in the right mood to work on it for a while. Getting back to work last week was a bit of a shock to the system; but i'm slowly getting back into the groove and will eventually have time and energy left over for hacking.

I've been doing a bit of video stuff which is helping to harden and clean up jjmpeg a bit more, and I have a few minor patches pending for that. I've also been poking very tenatively at a slideshow creator/video compositor: but there's a lot of crap I don't really want to have to write (ugh, timeline anyone) so i'm not exactly making any headway yet.

DTCWT denoising

So I poked at the wavelet code enough to get it to work, and included it in ImageZ. It still fails with certain sized images, but oh well ...

It's based on the dual-tree quaternion wavelet, and does a quaternion-to-complex translation during the thresholding which produces a cleaner de-noised result (i.e. it is still using a dual-tree-complex-wavelet-transform ...). I haven't particularly tried to optimise it much - but it's already about 3-4x faster than the DCT Denoising algorithm I implemented earlier (for which there is little opportunity for further improvement). It also implements the sharpen algorithm I developed, which I wasn't able to get to work with the DCT code.

I've started working on the OpenCL version for socles as well, but it's got a way to go yet.

The de-noising isn't my primary interest in this stuff, it's just a freebie to test some of the algorithms and is interesting nonetheless.

Update: Yes it's been a long time between drinks, but I finally poked at the socles GPU version again nearly 3 months later, see this follow-up post.

socles demos

I finally got off my fat arse - or is that sat on it further enlargening[sic] it - and tied up some of the test driver code I have for socles into a set of demos.

I also implemented the colour mode for the DCT denoising algorithm. Over-all it's a little slow still - i.e. not fast enough for real-time video. One of these days i'll get around to the complex wavelet version, that should be a lot faster and can also sharpen. I haven't been able to suss out DCT sharpening and so far my attempts add too many artefacts to be useful (i.e. pixel-level chess pattern).

The demos so far are:

AdaptiveBlur

An interactive window that shows an experimental algorithm I came up with some time ago for de-noising. It uses sobel filter to detect edges, then uses that to progressively blend between a blurred and non-burred image. Works ok sometimes.

ConvolveNonSeparable

Simple non-separable convolution that blurs an image.

ConvolveSeparable

Separable convolution to do the same thing (and demonstrates the code is broken atm - demo was broken, fixed)

DCT8x8Mono, DCT8x8Colour

Interactive DCT based denoise demo for mono/colour images.

WebcamFX

Another old interactive demo I wrote which uses Video4Linux to access a webcam and apply a bunch of effects including KLT motion detection and viola-jones face detect. It also shows the first half of a low-overhead video display path: the GPU does the colour conversion from raw frames. Well as low as possible with v4l4j anyway.

They're in the soclesdemo sub-module in socles' cvs.

Hmm, another week nearly down. I've been reading lots of papers and trying to suss out some fiddly crap for work, so this stuff has been a nice distraction. That's finally going somewhere so might keep me busy for a bit.