{"id":3978,"date":"2012-02-09T20:31:57","date_gmt":"2012-02-09T19:31:57","guid":{"rendered":"http:\/\/www.walkingrandomly.com\/?p=3978"},"modified":"2012-02-13T19:00:11","modified_gmt":"2012-02-13T18:00:11","slug":"optimising-a-correlated-asset-calculation-on-matlab-2-using-the-gpu-via-the-pct","status":"publish","type":"post","link":"https:\/\/walkingrandomly.com\/?p=3978","title":{"rendered":"Optimising a correlated asset calculation on MATLAB #2 – Using the GPU via the PCT"},"content":{"rendered":"

This article is the second part of a series where I look at rewriting a particular piece of MATLAB code using various techniques.\u00a0 The introduction to the series is here<\/a> and the introduction to the larger series of GPU articles for MATLAB on WalkingRandomly is here<\/a>.<\/p>\n

Attempt 1 – Make as few modifications as possible<\/strong><\/p>\n

I took my best CPU-only code from last time (optimised_corr2.m<\/a>) and changed a load of data-types from double<\/strong> to gpuArray<\/strong> in order to get the calculation to run on my laptop’s GPU using the parallel computing toolbox<\/a> in MATLAB 2010b.\u00a0 I also switched to using the GPU versions of various functions such as parallel.gpu.GPUArray.randn<\/strong> instead of randn<\/strong> for example.\u00a0 Functions such as cumprod<\/strong> needed no\u00a0 modifications at all since they are nicely overloaded; if the argument to cumprod is of type double then the calculation happens on the CPU whereas if it is gpuArray then it happens on the GPU.<\/p>\n

The above work took about a minute to do which isn’t bad for a CUDA ‘porting’ effort!\u00a0 The result, which I’ve called GPU_PCT_corr1.m<\/a> is available for you to download and try out.<\/p>\n

How about performance?\u00a0 Let’s do a quick tic and toc using my laptop’s NVIDIA GT 555M GPU<\/a>.<\/p>\n

>> tic;GPU_PCT_corr1;toc\r\nElapsed time is 950.573743 seconds.<\/pre>\n
The CPU version of this code took only 3.42 seconds which means that this GPU version is over 277 times slower!<\/strong> Something has gone horribly, horribly wrong!<\/p>\n
Attempt 2 – Switch from script to function<\/strong><\/p>\n
In general functions should be faster than scripts in MATLAB because more automatic optimisations are performed on functions.\u00a0 I didn’t see any difference in the CPU version of this code (see optimised_corr3.m<\/a> from part 1 for a CPU function version) and so left it as a script (partly so I had an excuse to discuss it here if I am honest).\u00a0 This GPU-version, however, benefits noticeably from conversion to a function.\u00a0 To do this, add the following line to the top of GPU_PCT_corr1.m<\/p>\n
function [SimulPrices] = GPU_PTC_corr2( n,sub_size)<\/pre>\n
Next, you need to delete<\/strong> the following two lines<\/p>\n
n=100000;                       %Number of simulations\r\nsub_size = 125;<\/pre>\n
Finally, add the following to the end of our new function<\/p>\n
end<\/pre>\n
That’s pretty much all I did to get GPU_PCT_corr2.m<\/a>.  Let’s see how that performs using the same parameters as our script (100,000 simulations in blocks of 125).\u00a0 I used script_vs_func.m<\/a> to run both twice after a quick warm-up iteration and the results were:<\/p>\n
Warm up\r\nElapsed time is 1.195806 seconds.\r\nMain event\r\nscript\r\nElapsed time is 950.399920 seconds.\r\nfunction\r\nElapsed time is 938.238956 seconds.\r\nscript\r\nElapsed time is 959.420186 seconds.\r\nfunction\r\nElapsed time is 939.716443 seconds.<\/pre>\n
So, switching to a function has saved us a few seconds but performance is still very bad!
\n<\/strong><\/p>\n
Attempt 3 – One big matrix multiply!
\n<\/strong><\/p>\n
So far all I have done is take a program that works OK on a CPU, and run it exactly as-is on the GPU in the hope that something magical would happen to make it go faster.\u00a0 Of course, GPUs and CPUs are very different beasts with differing sets of strengths and weaknesses so it is rather naive to think that this might actually work.\u00a0 What we need to do is to play to the GPUs strengths more and the way to do this is to focus on this piece of code.<\/p>\n
for i=1:sub_size\r\n     CorrWiener(:,:,i)=parallel.gpu.GPUArray.randn(T-1,2)*UpperTriangle;\r\nend<\/pre>\n
Here, we are performing lots of small matrix multiplications and, as mentioned in part 1, we might hope to get better performance by performing just one large matrix multiplication instead.  To do this we can change the above code to<\/p>\n
%Generate correlated random numbers\r\n%using one big multiplication\r\nrandoms = parallel.gpu.GPUArray.randn(sub_size*(T-1),2);\r\nCorrWiener = randoms*UpperTriangle;\r\nCorrWiener = reshape(CorrWiener,(T-1),sub_size,2);\r\n%CorrWiener = permute(CorrWiener,[1 3 2]); %Can't do this on the GPU in 2011b or below\r\n\r\n%poor man's permute since GPU permute if not available in 2011b\r\nCorrWiener_final = parallel.gpu.GPUArray.zeros(T-1,2,sub_size);\r\nfor s = 1:2\r\n    CorrWiener_final(:, s, :) = CorrWiener(:, :, s);\r\nend<\/pre>\n
The reshape and permute are necessary to get the matrix in the form needed later on.  Sadly, MATLAB 2011b doesn’t support permute on GPUArrays and so I had to use the ‘poor mans permute’ instead.<\/p>\n
The result of the above is contained in GPU_PCT_corr3.m<\/a> so let’s see how that does in a fresh instance of MATLAB.<\/p>\n
>> tic;GPU_PCT_corr3(100000,125);toc\r\nElapsed time is 16.666352 seconds.\r\n>> tic;GPU_PCT_corr3(100000,125);toc\r\nElapsed time is 8.725997 seconds.\r\n>> tic;GPU_PCT_corr3(100000,125);toc\r\nElapsed time is 8.778124 seconds.<\/pre>\n
The first thing to note is that performance is MUCH better so we appear to be on the right track.  The next thing to note is that the first evaluation is much slower than all subsequent ones.  This is totally expected and is due to various start-up overheads.<\/p>\n
Recall that 125 in the above function calls refers to the block size of our monte-carlo simulation.  We are doing 100,000 simulations in blocks of 125– a number chosen because I determined empirically that this was the best choice on my CPU.  It turns out we are better off using much larger block sizes on the GPU:<\/p>\n
>> tic;GPU_PCT_corr3(100000,250);toc\r\nElapsed time is 6.052939 seconds.\r\n>> tic;GPU_PCT_corr3(100000,500);toc\r\nElapsed time is 4.916741 seconds.\r\n>> tic;GPU_PCT_corr3(100000,1000);toc\r\nElapsed time is 4.404133 seconds.\r\n>> tic;GPU_PCT_corr3(100000,2000);toc\r\nElapsed time is 4.223403 seconds.\r\n>> tic;GPU_PCT_corr3(100000,5000);toc\r\nElapsed time is 4.069734 seconds.\r\n>> tic;GPU_PCT_corr3(100000,10000);toc\r\nElapsed time is 4.039446 seconds.\r\n>> tic;GPU_PCT_corr3(100000,20000);toc\r\nElapsed time is 4.068248 seconds.\r\n>> tic;GPU_PCT_corr3(100000,25000);toc\r\nElapsed time is 4.099588 seconds.<\/pre>\n
The above, rather crude, test suggests that block sizes of 10,000 are the best choice on my laptop’s GPU.  Sadly, however, it’s STILL slower than the 3.42 seconds I managed on the i7 CPU and represents the best I’ve managed using pure MATLAB code.  The profiler tells me that the vast majority of the GPU execution time is spent in the cumprod line and in random number generation (over 40% each).
\n<\/strong><\/p>\n
Trying a better GPU<\/strong>
\nOf course now that I have code that runs on a GPU I could just throw it at a better GPU and see how that does.  I have access to MATLAB 2011b on a  Tesla M2070 hooked up to a Linux machine so I ran the code on that.  I tried various block sizes and the best time was 0.8489 seconds with the call GPU_PCT_corr3(100000,20000) which is just over 4 times faster than my laptop’s CPU.<\/p>\n
Ask the Audience<\/strong>
\nCan you do better using just the GPU functionality provided in the Parallel Computing Toolbox (so no bespoke CUDA kernels or Jacket just yet)?  I’ll be looking at how AccelerEyes’ Jacket myself in the next post.<\/p>\n
Results so far<\/strong><\/p>\n