Overview
Examples
Screenshots
Comparisons
Applications
Download
Documentation
Tutorials
Bazaar
Status & Roadmap
FAQ
Authors & License
Forums
Funding Ultimate++
Search on this site
Search in forums












SourceForge.net Logo
Home » Community » U++ community news and announcements » New parallelization pattern with CoWork
New parallelization pattern with CoWork [message #49143] Tue, 26 December 2017 11:44 Go to next message
mirek is currently offline  mirek
Messages: 11843
Registered: November 2005
Ultimate Member
While trying to parallelize Painter, I have found that there is a set of algorithms that are 'too short' to parallelize with CoWork operator& and 'too unstable' to parallelize with CoPartition. 'too short', because the cost of creating Event (which is about 80ns) is too large compared to the work done by job in parallel. 'too unstable' means that the time taken by single job highly unpredictable, so assigning regularly sized chunks of work to threads tends to some threads ending early and one thread going for long time.

Thinking about the issue, I have found a new parallelization pattern (and implemented it with CoWork):

CONSOLE_APP_MAIN
{
	SeedRandom(0);
	Vector<String> data;
	for(int i = 0; i < 1000; i++) {
		int n = Random(7);
		data.Add();
		for(int j = 0; j < n; j++)
			data.Top() << Random() << ' ';
	}
	
	double sum = 0;
	CoWork co;
	co * [&] {
		double m = 0;
		int i;
		while((i = co.Next()) < data.GetCount()) {
			CParser p(data[i]);
			while(!p.IsEof())
				m += p.ReadDouble();
		}
		CoWork::FinLock();
		sum += m;
	};

	RDUMP(sum);
}


operator* schedules all CoWork threads to run a single routine. 'co.Next' then atomically returns increasing numbers (from 0), which are used to distribute the work.

So in this 'outside-in' approach, just a single lambda is created and only a handful of jobs have to be started for things to work and management overhead is thus greatly reduced...
Re: New parallelization pattern with CoWork [message #49148 is a reply to message #49143] Wed, 27 December 2017 00:36 Go to previous messageGo to next message
Oblivion is currently offline  Oblivion
Messages: 556
Registered: August 2007
Location: Turkey
Contributor
Hello Mirek,

This is good news. Thanks for your efforts!
U++ MT is really improved over time.

My initial impression: It looks and works good.

Here's another example (a visually more pleasing, and more concrete one I hope) Smile
This is to give some basic idea about it's possible usage to our fellow U++ users and newcomers.

void Mandelbrot::DrawFractal(const Rectf& r, int ix, int wcount)
{
	// This method draws the famous Mandelbrot fractal, using the escape time algorithm (slow).
	// Important note: Imagebuffer is accessed without using any locking mechansim.
	// While it is OK here, do not do this in real life unless you know what you're doing!
	
	auto sz = GetSize();
	Vector<Rect> regions;
	Sizef scale = iscale(sz, Sizef(1.0, 1.0), r.GetSize());
	
	for(int i = 0, cx = sz.cx / wcount, mod = sz.cx % wcount; i < wcount; i++) {
		auto x = i * cx;
		regions.Add(Rect(x, 0, x + cx + (i == wcount - 1 ? mod : 0), sz.cy));
	}
	ImageBuffer canvas(sz);
	
	if(CoWork::GetPoolSize() < wcount)
		CoWork::SetPoolSize(wcount);
	CoWork co;
	{
		RTIMING("Mandelbrot calculation with CoWork");
		co * [&] {
			int j = 0;
			while((j = co.Next()) < regions.GetCount()) {
				const auto& rr = regions[j];
				for(auto y = rr.top; y < rr.bottom; y++) {
					RGBA *pixel = canvas[y];
					for(auto x = rr.left; x < rr.right; x++) {
						Complex c(r.left + x / scale.cx, r.top + y / scale.cy);
						auto z = c;
						auto i = 0;
						while(abs(z) < 2 && i < ix) {
							z = z * z + c;
							i++;
						}
						if(i < ix) {
							 double jj = i + 1 - log(log2(abs(z)));
							 *(pixel + x) = HsvColorf(jj / double(ix),  1.0, (double(ix) / 256.0) * 1.888);
						}
						else *(pixel + x) = Black();
					}
				}
			}
		};
	}
	img = canvas;
	Refresh();
}





index.php?t=getfile&id=5468&private=0

Best regards,
Oblivion

[Updated on: Wed, 27 December 2017 00:51]

Report message to a moderator

Re: New parallelization pattern with CoWork [message #49149 is a reply to message #49148] Wed, 27 December 2017 11:15 Go to previous messageGo to next message
koldo is currently offline  koldo
Messages: 2948
Registered: August 2008
Veteran
Hello Mirek

How would it be better to include parallel routines into U++ classes ?
- Just to include them directly
- Adding an option to choose the parallel version or not


Best regards
Iñaki
Re: New parallelization pattern with CoWork [message #49150 is a reply to message #49149] Wed, 27 December 2017 16:19 Go to previous messageGo to next message
mirek is currently offline  mirek
Messages: 11843
Registered: November 2005
Ultimate Member
koldo wrote on Wed, 27 December 2017 11:15
Hello Mirek

How would it be better to include parallel routines into U++ classes ?
- Just to include them directly
- Adding an option to choose the parallel version or not


Not sure what you mean.

We have parallel algos

here

and I am adding support where possible, like with Painter...

Anyway, generic tools are definitely needed, one way or another.
Re: New parallelization pattern with CoWork [message #49151 is a reply to message #49150] Wed, 27 December 2017 21:58 Go to previous messageGo to next message
koldo is currently offline  koldo
Messages: 2948
Registered: August 2008
Veteran
Hi Mirek

For example ScatterCtrl uses either Draw or Painter.
Painter is much better, but Draw is faster.
In case of Painter, what could be the best way to do it?:
- If MT is chosen, to use CoWork directly
- Use CoWork just if it is explicitly indicated


Best regards
Iñaki
Re: New parallelization pattern with CoWork [message #49153 is a reply to message #49151] Thu, 28 December 2017 08:40 Go to previous messageGo to next message
mirek is currently offline  mirek
Messages: 11843
Registered: November 2005
Ultimate Member
koldo wrote on Wed, 27 December 2017 21:58
Hi Mirek

For example ScatterCtrl uses either Draw or Painter.
Painter is much better, but Draw is faster.
In case of Painter, what could be the best way to do it?:
- If MT is chosen, to use CoWork directly
- Use CoWork just if it is explicitly indicated


Add 'Co' method to ScatterCtrl that activates 'Co' method of Painter.

BTW, the problem with Painter::Co is that sometimes it slows it down.
Re: New parallelization pattern with CoWork [message #49154 is a reply to message #49153] Thu, 28 December 2017 09:57 Go to previous messageGo to next message
koldo is currently offline  koldo
Messages: 2948
Registered: August 2008
Veteran
OK Mirek

I will see how and when the performance is improved.


Best regards
Iñaki
Re: New parallelization pattern with CoWork [message #49196 is a reply to message #49143] Sat, 06 January 2018 12:17 Go to previous message
Didier is currently offline  Didier
Messages: 476
Registered: November 2008
Location: France
Senior Member
Hi,

looks very interesting and most importantly very easy and handy to use

Good job
Previous Topic: Happy new year 2018 for all U++ users
Next Topic: BufferPainter now MT optimized
Goto Forum:
  


Current Time: Thu Apr 25 04:03:26 CEST 2019

Total time taken to generate the page: 0.01200 seconds