Choose Language Hide Translation Bar
Highlighted
vince_faller
Super User

Understanding Parallel Assign

I'm trying to understand parallel assign to try and speed up some small operations.  I run the following script (warning it ran out of memory for me and locked me up) and I'm seeing it get exponentially slower with the number of rows in a vector.  

for(i=1, i<=5, i++, 
	t = [59760, 71220, 79380, 83820, 3300, 11400, 27900, 39060, 43500, 51300,56220, 60];
	t = repeat(t, 10^i);

	n = nitems(t);
	diff = t[2::n]-t[1::(n-1)];
	day_v = diff < 0;
	
	st = HPTime();
	day_cum = cumulative Sum([0]|/day_v);
	tot_cum = HPTIme() - st;

	st= HPTime();

	day_break = loc(day_v); // this will give you last row of the day
	// make a matrix n x number of day breaks
	m = J(n, nitems(day_break), -1);
	parallel assign({db = day_break}, 
		// make the item a 1 if it's row is higher than the corresponding row
		m[a, b] = a > db[b];
	);
	m;
	// now just sum the matrix
	day = VSum(m`); // +1; // if you want the day to start at 1

	tot_pa = HPTime() - st;
	show(n, tot_pa, tot_cum);
);

I don't expect it to be faster to do the parallel assign than the cumulativesum() but I'm curious on how the parallel assign is working.  

I've read this and I'm guessing it's because it's creating copies of very large matrices for each thread?  

 

Does anyone have any other insights into how this might operate and maybe some basic dos and don'ts for parallel assign?

Vince Faller - Predictum
0 Kudos
1 ACCEPTED SOLUTION

Accepted Solutions
Highlighted
Craige_Hales
Staff (Retired)

Re: Understanding Parallel Assign

Parallel Assign is doing an amazing job! I think the size of the array m is the actual issue: it is growing by leaps and bounds, or 100X on each iteration.

 

initems(m)Seconds_in_Parallel_AssignSeconds_in_Nested_Loops
12,400too small for tickseconds().18
2240,000.03319
324,000,0003.31951
42,400,000,000338gave up waiting

 

That script, 

 

 

m[a, b] = a > db[b];

 

 

is executed about 7 million times per second (4-CPU 17.5G VirtualBox). I also ran out of memory, and that means paging. Paging will cause a dramatic slow-down, perhaps at i==5.

Column 4, the nested-loop comparison, was made like this (screen capture...computer busy trying to get to 1900 seconds on row 3):

 

Capture.PNG

 

This is the kind of problem parallel assign was designed for. Part of the speed comes from C++ loops rather than JSL loops, and part from threading.

Craige

View solution in original post

3 REPLIES 3

Re: Understanding Parallel Assign

Hi Vince,
I'm not fully sure how Parallel Assign split the tasks and how it copies the matrices. but in general multithreading and parallel computing usually only benefits if the operation to do is more effort than the overhead to split tasks and join the subcalculations results. You asked for dos and don't's and I believe the same thing as for parallel compunting and multithreading applies here:

Multithreading is a bad idea when the problem you are trying to solve is not parallelizable, or when the problem you are trying to compute is so small, that spawning threads will cost more time than computing in a single thread.

If your problem can be broken into parts that can run in parallel, it might be a good idea to do so, but it depends on how much can run in parallel and how easy it is to join the sub problem results. If your algorithm would require multiple joins (to one thread) to break up into new sub problems on new threads, it have to be very computation intensive to be worth the effort to parallelise, if your result, on the other hand, just is a list of the sub problem results joined once, then there is potential.

Of course if you have iterative operations or tasks that depend on the previous task usually you do not gain benefit, more over you block threads with fast tasks sitting there and waiting for the other threads to end to be able to join back the results and use them further.
Highlighted
Craige_Hales
Staff (Retired)

Re: Understanding Parallel Assign

Parallel Assign is doing an amazing job! I think the size of the array m is the actual issue: it is growing by leaps and bounds, or 100X on each iteration.

 

initems(m)Seconds_in_Parallel_AssignSeconds_in_Nested_Loops
12,400too small for tickseconds().18
2240,000.03319
324,000,0003.31951
42,400,000,000338gave up waiting

 

That script, 

 

 

m[a, b] = a > db[b];

 

 

is executed about 7 million times per second (4-CPU 17.5G VirtualBox). I also ran out of memory, and that means paging. Paging will cause a dramatic slow-down, perhaps at i==5.

Column 4, the nested-loop comparison, was made like this (screen capture...computer busy trying to get to 1900 seconds on row 3):

 

Capture.PNG

 

This is the kind of problem parallel assign was designed for. Part of the speed comes from C++ loops rather than JSL loops, and part from threading.

Craige

View solution in original post

Highlighted
vince_faller
Super User

Re: Understanding Parallel Assign

Good point, I didn't think about my example not being an apples to apples comparison.  Thanks @Craige_Hales , this is really useful.  

Vince Faller - Predictum
0 Kudos