parallel_foreach.hpp 18.9 KB
Newer Older
Sylvain Thery's avatar
Sylvain Thery committed
1 2 3
/*******************************************************************************
* CGoGN: Combinatorial and Geometric modeling with Generic N-dimensional Maps  *
* version 0.1                                                                  *
4
* Copyright (C) 2009-2012, IGG Team, LSIIT, University of Strasbourg           *
Sylvain Thery's avatar
Sylvain Thery committed
5 6 7 8 9 10 11 12 13 14 15 16 17 18 19
*                                                                              *
* This library is free software; you can redistribute it and/or modify it      *
* under the terms of the GNU Lesser General Public License as published by the *
* Free Software Foundation; either version 2.1 of the License, or (at your     *
* option) any later version.                                                   *
*                                                                              *
* This library is distributed in the hope that it will be useful, but WITHOUT  *
* ANY WARRANTY; without even the implied warranty of MERCHANTABILITY or        *
* FITNESS FOR A PARTICULAR PURPOSE. See the GNU Lesser General Public License  *
* for more details.                                                            *
*                                                                              *
* You should have received a copy of the GNU Lesser General Public License     *
* along with this library; if not, write to the Free Software Foundation,      *
* Inc., 51 Franklin Street, Fifth Floor, Boston, MA  02110-1301 USA.           *
*                                                                              *
20
* Web site: http://cgogn.unistra.fr/                                           *
Sylvain Thery's avatar
Sylvain Thery committed
21 22 23 24 25
* Contact information: cgogn@unistra.fr                                        *
*                                                                              *
*******************************************************************************/
#include <boost/thread.hpp>
#include <boost/thread/barrier.hpp>
sylvain thery's avatar
sylvain thery committed
26
#include <vector>
Sylvain Thery's avatar
Sylvain Thery committed
27

28

Sylvain Thery's avatar
Sylvain Thery committed
29 30 31 32 33 34 35 36 37
namespace CGoGN
{

namespace Algo
{

namespace Parallel
{

38
/// internal functor for boost call
39
class ThreadFunctionAttrib
40 41
{
protected:
42
	std::vector<unsigned int>& m_ids;
43 44 45
	boost::barrier& m_sync1;
	boost::barrier& m_sync2;
	bool& m_finished;
46 47 48
	unsigned int m_id;
	FunctorAttribThreaded* m_functor;

49
public:
50 51
	ThreadFunctionAttrib(FunctorAttribThreaded* func, std::vector<unsigned int>& vid, boost::barrier& s1, boost::barrier& s2, bool& finished, unsigned int id):
		m_ids(vid), m_sync1(s1), m_sync2(s2), m_finished(finished), m_id(id), m_functor(func)
52 53 54
	{
	}

55 56
	ThreadFunctionAttrib(const ThreadFunctionAttrib& tf):
		m_ids(tf.m_ids), m_sync1(tf.m_sync1), m_sync2(tf.m_sync2), m_finished(tf.m_finished), m_id(tf.m_id), m_functor(tf.m_functor){}
57 58 59 60 61

	void operator()()
	{
		while (!m_finished)
		{
62
			for (std::vector<unsigned int>::const_iterator it = m_ids.begin(); it != m_ids.end(); ++it)
63
				m_functor->run(*it,m_id);
64 65 66 67
			m_sync1.wait();
			m_sync2.wait();
		}
	}
68 69
};

70

71
/// internal functor for boost call
72 73
template<typename MAP>
class ThreadFunction
Sylvain Thery's avatar
Sylvain Thery committed
74 75
{
protected:
76
	std::vector<Dart>& m_darts;
Sylvain Thery's avatar
Sylvain Thery committed
77 78 79
	boost::barrier& m_sync1;
	boost::barrier& m_sync2;
	bool& m_finished;
80 81
	unsigned int m_id;
	FunctorMapThreaded<MAP>* m_functor;
Sylvain Thery's avatar
Sylvain Thery committed
82
public:
83 84
	ThreadFunction(FunctorMapThreaded<MAP>* func, std::vector<Dart>& vd, boost::barrier& s1, boost::barrier& s2, bool& finished, unsigned int id):
		m_darts(vd), m_sync1(s1), m_sync2(s2), m_finished(finished), m_id(id), m_functor(func)
85 86 87
	{
	}

88 89
	ThreadFunction(const ThreadFunction<MAP>& tf):
		m_darts(tf.m_darts), m_sync1(tf.m_sync1), m_sync2(tf.m_sync2), m_finished(tf.m_finished), m_id(tf.m_id), m_functor(tf.m_functor){}
Sylvain Thery's avatar
Sylvain Thery committed
90 91 92 93 94 95

	void operator()()
	{
		while (!m_finished)
		{
			for (std::vector<Dart>::const_iterator it = m_darts.begin(); it != m_darts.end(); ++it)
96
				m_functor->run(*it,m_id);
Sylvain Thery's avatar
Sylvain Thery committed
97 98 99 100 101 102
			m_sync1.wait();
			m_sync2.wait();
		}
	}
};

103

104 105 106 107 108 109
inline unsigned int nbThreads()
{
	return boost::thread::hardware_concurrency();
}


110
inline unsigned int optimalNbThreads(NbParam p)
Sylvain Thery's avatar
Sylvain Thery committed
111
{
112 113 114 115 116 117 118 119
	if (p==NB_HIGHCOMPUTE)
		return nbThreads();
	if (p==NB_VERYHIGHMEMORY)
		return 2;

 // NB_HIGHMEMORY
	if (NBCORES != 0)
		return NBCORES;
120 121 122 123
	unsigned int nb = nbThreads();
	if (nb>4)
		return nb/2 ;
	return nb;
124

125
}
Sylvain Thery's avatar
Sylvain Thery committed
126 127


128

129
template <typename MAP, unsigned int ORBIT>
130
void foreach_cell(MAP& map, FunctorMapThreaded<MAP>& func, unsigned int nbth, bool needMarkers)
131 132 133
{
	if (nbth == 0)
		nbth = optimalNbThreads();
Sylvain Thery's avatar
Sylvain Thery committed
134

135 136
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);
137

138 139 140
	FunctorMapThreaded<MAP>* ptr = func.duplicate();
	bool shared = (ptr == NULL);

141
	if (shared)
142
	{
143
		for (unsigned int i = 0; i < nbth; ++i)
144
			funcs.push_back(&func);
145 146 147
	}
	else
	{
148 149
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
150
			funcs.push_back(func.duplicate());
151
	}
Sylvain Thery's avatar
Sylvain Thery committed
152

153
	foreach_cell<MAP,ORBIT>(map,funcs,needMarkers);
Sylvain Thery's avatar
Sylvain Thery committed
154

155
	if (!shared)
156
		for (unsigned int i = 0; i < nbth; ++i)
157
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
158 159
}

160
template <typename MAP, unsigned int ORBIT>
161
void foreach_cell(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcs, bool needMarkers)
Sylvain Thery's avatar
Sylvain Thery committed
162
{
163
	unsigned int nbth = funcs.size();
164

sylvain thery's avatar
sylvain thery committed
165
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
Sylvain Thery's avatar
Sylvain Thery committed
166 167

	// nbth new functions, new thread (with good darts !)
168
	for (unsigned int i = 0; i < nbth; ++i)
169
		vd[i].reserve(SIZE_BUFFER_THREAD);
Sylvain Thery's avatar
Sylvain Thery committed
170

171
	AttributeContainer* cont = NULL;
Pierre Kraemer's avatar
Pierre Kraemer committed
172 173
	DartMarker<MAP>* dmark = NULL;
	CellMarker<MAP, ORBIT>* cmark = NULL;
Sylvain Thery's avatar
Sylvain Thery committed
174
	const AttributeMultiVector<Dart>* quickTraversal = map.template getQuickTraversal<ORBIT>() ;
175 176 177 178 179 180

	// fill each vd buffers with SIZE_BUFFER_THREAD darts
	Dart d;
	unsigned int di=0;

	if(quickTraversal != NULL)
Sylvain Thery's avatar
Sylvain Thery committed
181
	{
182 183 184 185 186
		cont = &(map.template getAttributeContainer<ORBIT>()) ;

		di = cont->begin();
		unsigned int nb = 0;
		while ((di != cont->end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
Sylvain Thery's avatar
Sylvain Thery committed
187
		{
188
			d = quickTraversal->operator[](di);
189 190 191 192

			vd[nb%nbth].push_back(d);
			nb++;

193
			cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
194 195
		}
	}
196
	else
197
	{
198 199
		if(map.template isOrbitEmbedded<ORBIT>())
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
200
			cmark = new CellMarker<MAP, ORBIT>(map) ;
201 202 203 204 205

			d = map.begin();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
206
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!cmark->isMarked(d)))
207 208 209 210 211 212 213 214 215 216
				{
					cmark->mark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
		else
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
217
			dmark = new DartMarker<MAP>(map) ;
218 219 220 221
			d = map.begin();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
222
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!dmark->isMarked(d)))
223 224 225 226 227 228 229 230
				{
					dmark->markOrbit<ORBIT>(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
231 232
	}

Sylvain Thery's avatar
Sylvain Thery committed
233 234 235 236
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished=false;
	// lauch threads
237 238
	if (needMarkers)
	{
239 240 241
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
242
	}
243

244 245 246
	boost::thread** threads = new boost::thread*[nbth];
	ThreadFunction<MAP>** tfs = new ThreadFunction<MAP>*[nbth];

247
	for (unsigned int i = 0; i < nbth; ++i)
248 249 250 251 252 253
	{
		tfs[i] = new ThreadFunction<MAP>(funcs[i], vd[i],sync1,sync2, finished,1+i);
		threads[i] = new boost::thread( boost::ref( *(tfs[i]) ) );
	}
//		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd[i],sync1,sync2, finished,1+i));

254

Sylvain Thery's avatar
Sylvain Thery committed
255
	// and continue to traverse the map
sylvain thery's avatar
sylvain thery committed
256 257
	std::vector<Dart>* tempo = new std::vector<Dart>[nbth];

258
	for (unsigned int i = 0; i < nbth; ++i)
259
		tempo[i].reserve(SIZE_BUFFER_THREAD);
Sylvain Thery's avatar
Sylvain Thery committed
260 261


262 263 264
	if (cont)
	{
		while (di != cont->end())
Sylvain Thery's avatar
Sylvain Thery committed
265
		{
266 267 268 269
			for (unsigned int i = 0; i < nbth; ++i)
				tempo[i].clear();
			unsigned int nb = 0;
			while ((di != cont->end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
Sylvain Thery's avatar
Sylvain Thery committed
270
			{
271
				d = quickTraversal->operator[](di);
272 273 274 275

				tempo[nb%nbth].push_back(d);
				nb++;

276
				cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
277
			}
278 279 280 281 282 283 284 285 286 287 288 289 290 291 292
			sync1.wait();
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].swap(tempo[i]);
			sync2.wait();
		}
	}
	else if (cmark)
	{
		while (d != map.end())
		{
			for (unsigned int i = 0; i < nbth; ++i)
				tempo[i].clear();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
293
				if (!map.template isBoundaryMarked<MAP::DIMENSION>(d) && !cmark->isMarked(d))
294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310 311 312 313 314 315
				{
					cmark->mark(d);
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].swap(tempo[i]);
			sync2.wait();
		}
	}
	else
	{
		while (d != map.end())
		{
			for (unsigned int i = 0; i < nbth; ++i)
				tempo[i].clear();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
316
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!dmark->isMarked(d)))
317 318 319 320 321 322 323 324 325 326 327
				{
					dmark->markOrbit<ORBIT>(d);
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].swap(tempo[i]);
			sync2.wait();
Sylvain Thery's avatar
Sylvain Thery committed
328 329 330 331 332 333 334 335
		}
	}

	sync1.wait();
	finished = true;
	sync2.wait();

	//wait for all theads to be finished
336
	for (unsigned int i = 0; i < nbth; ++i)
Sylvain Thery's avatar
Sylvain Thery committed
337 338 339
	{
		threads[i]->join();
		delete threads[i];
340
		delete tfs[i];
Sylvain Thery's avatar
Sylvain Thery committed
341
	}
342
	delete[] tfs;
sylvain thery's avatar
sylvain thery committed
343 344 345
	delete[] threads;
	delete[] vd;
	delete[] tempo;
Sylvain Thery's avatar
Sylvain Thery committed
346

347 348
	if (cmark != NULL)
		delete cmark;
Sylvain Thery's avatar
Sylvain Thery committed
349

350 351 352
	if (dmark != NULL)
		delete dmark;
}
Sylvain Thery's avatar
Sylvain Thery committed
353 354 355



356
template <typename MAP>
357
void foreach_dart(MAP& map, FunctorMapThreaded<MAP>& func, unsigned int nbth, bool needMarkers)
358 359 360
{
	if (nbth == 0)
		nbth = optimalNbThreads();
361

362 363 364
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);

365 366 367
	FunctorMapThreaded<MAP>* ptr = func.duplicate();
	bool shared = (ptr == NULL);

368
	if (shared)
369
	{
370
		for (unsigned int i = 0; i < nbth; ++i)
371
			funcs.push_back(&func);
372 373 374
	}
	else
	{
375 376
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
377
			funcs.push_back(func.duplicate());
378
	}
Sylvain Thery's avatar
Sylvain Thery committed
379

380
	foreach_dart<MAP>(map,funcs,needMarkers);
Sylvain Thery's avatar
Sylvain Thery committed
381

382
	if (!shared)
383
		for (unsigned int i = 0; i < nbth; ++i)
384
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
385 386
}

387 388

template <typename MAP>
389
void foreach_dart(MAP& map, std::vector<FunctorMapThreaded<MAP>*> funcs, bool needMarkers)
390
{
391
	unsigned int nbth = funcs.size();
392

393 394 395
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
	boost::thread** threads = new boost::thread*[nbth];

396
	Dart d = map.begin();
397 398

	// nbth new functions, new thread (with good darts !)
399
	for (unsigned int i = 0; i < nbth; ++i)
400
		vd[i].reserve(SIZE_BUFFER_THREAD);
401 402

	// fill each vd buffers with 4096 darts
403
	unsigned int nb = 0;
404
	while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
405
	{
406 407
		vd[nb%nbth].push_back(d);
		nb++;
408 409 410
		map.next(d);
	}

411 412 413 414
	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished = false;
	// lauch threads
415 416 417 418 419 420 421
	if (needMarkers)
	{
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

422
	for (unsigned int i = 0; i < nbth; ++i)
423
	{
424
		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd[i],sync1,sync2, finished,1+i));
425 426 427 428
	}

	// and continue to traverse the map
	std::vector<Dart>* tempo = new std::vector<Dart>[nbth];
429
	for (unsigned int i = 0; i < nbth; ++i)
430
		tempo[i].reserve(SIZE_BUFFER_THREAD);
431

432
	while (d != map.end())
433
	{
434
		for (unsigned int i = 0; i < nbth; ++i)
435 436
			tempo[i].clear();

437 438
		unsigned int nb =0;
		while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
439
		{
440 441
			tempo[nb%nbth].push_back(d);
			nb++;
442 443 444 445
			map.next(d);
		}

		sync1.wait();
446
		for (unsigned int i = 0; i < nbth; ++i)
447 448 449 450 451 452 453 454
			vd[i].swap(tempo[i]);
		sync2.wait();
	}

	sync1.wait();
	finished = true;
	sync2.wait();

455
	//wait for all theads to be finished
456
	for (unsigned int i = 0; i < nbth; ++i)
457 458 459 460
	{
		threads[i]->join();
		delete threads[i];
	}
461 462 463 464
	
	delete vd;
	delete threads;
	delete tempo;
465 466 467
}


468
// TODO same modification for transparent usage of dart marker / cell marker / quick traversal ??
469

470
template <typename MAP, unsigned int CELL>
471
void foreach_cell2Pass(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcsFrontnBack, unsigned int nbLoops, bool needMarkers)
472
{
473 474
	unsigned int nbth = funcsFrontnBack.size()/2;

475
	std::vector<Dart>* vd = new std::vector<Dart>[2*nbth];
476
	for (unsigned int i = 0; i < nbth; ++i)
477
		vd[i].reserve(SIZE_BUFFER_THREAD);
478

479
	boost::thread** threadsAB = new boost::thread*[2*nbth];
480 481 482 483 484 485 486 487 488

	if (needMarkers)
	{
		// ensure that there is enough threads
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

Pierre Kraemer's avatar
Pierre Kraemer committed
489
	CellMarkerNoUnmark<MAP, CELL> cm(map); // for 2 pass front mark / back unmark
490 491 492

	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
493 494 495 496 497 498

	for (unsigned int loop=0; loop< nbLoops; ++loop)
	{
		// PASS FRONT (A)
		{
			Dart d = map.begin();
499
			// fill each vd buffers with SIZE_BUFFER_THREAD darts
500
			unsigned int nb = 0;
501
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
502
			{
503
				if ((!cm.isMarked(d)))
504 505 506 507 508 509 510 511 512
				{
					cm.mark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}

			bool finished=false;
513 514 515 516

			for (unsigned int i = 0; i < nbth; ++i)
				threadsAB[i] = new boost::thread(ThreadFunction<MAP>(funcsFrontnBack[i], vd[i], sync1, sync2, finished,1+i));

517 518 519
			while (d != map.end())
			{
				for (unsigned int i = 0; i < nbth; ++i)
520
					vd[nbth+i].clear();
521 522

				unsigned int nb = 0;
523
				while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
524
				{
525
					if ((!cm.isMarked(d)))
526 527
					{
						cm.mark(d);
528
						vd[nbth+nb%nbth].push_back(d);
529 530 531 532 533 534 535
						nb++;
					}
					map.next(d);
				}

				sync1.wait();
				for (unsigned int i = 0; i < nbth; ++i)
536
					vd[i].swap(vd[nbth+i]);
537 538 539 540 541 542 543 544 545
				sync2.wait();
			}

			sync1.wait();
			finished = true;
			sync2.wait();

			//wait for all theads to be finished
			for (unsigned int i = 0; i < nbth; ++i)
546
				threadsAB[i]->join();
547 548 549 550 551 552
		}
		// PASS BACK (B)
		{
			for (unsigned int i = 0; i < nbth; ++i)
				vd[i].clear();
			Dart d = map.begin();
553
			// fill each vd buffers with SIZE_BUFFER_THREAD darts
554
			unsigned int nb = 0;
555
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
556
			{
557
				if ((cm.isMarked(d)))
558 559 560 561 562 563 564 565 566
				{
					cm.unmark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}

			bool finished=false;
567 568 569
			for (unsigned int i = 0; i < nbth; ++i)
				threadsAB[nbth+i] = new boost::thread(ThreadFunction<MAP>(funcsFrontnBack[nbth+i], vd[i],sync1,sync2, finished,1+i));

570 571 572 573 574
			// and continue to traverse the map

			while (d != map.end())
			{
				for (unsigned int i = 0; i < nbth; ++i)
575
					vd[nbth+i].clear();
576 577

				unsigned int nb = 0;
578
				while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
579
				{
580
					if ((cm.isMarked(d)))
581 582
					{
						cm.unmark(d);
583
						vd[nbth+nb%nbth].push_back(d);
584 585 586 587 588 589 590
						nb++;
					}
					map.next(d);
				}

				sync1.wait();
				for (unsigned int i = 0; i < nbth; ++i)
591
					vd[i].swap(vd[nbth+i]);
592 593 594 595 596 597 598 599 600
				sync2.wait();
			}

			sync1.wait();
			finished = true;
			sync2.wait();

			//wait for all theads to be finished
			for (unsigned int i = 0; i < nbth; ++i)
601
				threadsAB[nbth+i]->join();
602 603 604 605
		}
	}

	// free buffers and threads
606
	for (unsigned int i = 0; i < 2*nbth; ++i)
607
	{
608
		delete threadsAB[i];
609
	}
610
	delete[] threadsAB;
611 612 613 614 615
	delete[] vd;
}



616
template <typename MAP, unsigned int CELL>
617
void foreach_cell2Pass(MAP& map, FunctorMapThreaded<MAP>& funcFront, FunctorMapThreaded<MAP>& funcBack, unsigned int nbLoops, unsigned int nbth, bool needMarkers)
618 619 620
{
	if (nbth == 0)
		nbth = optimalNbThreads();
621

622 623
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);
624

625 626 627
	FunctorMapThreaded<MAP>* ptr = funcFront.duplicate();
	bool shared = (ptr == NULL);

628 629 630 631 632 633 634 635 636
	if (shared)
	{
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(&funcFront);
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(&funcBack);
	}
	else
	{
637 638
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
639 640 641
			funcs.push_back(funcFront.duplicate());
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(funcBack.duplicate());
642

643
	}
644

645
	foreach_cell2Pass<MAP,CELL>(map,funcs,nbLoops,needMarkers);
646

647
	if (!shared)
648
		for (unsigned int i = 0; i < 2*nbth; ++i)
649 650
			delete funcs[i];
}
651

652 653 654 655



template <typename MAP, unsigned int ORBIT>
656
void foreach_cell_all_thread(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcs, bool needMarkers)
657 658 659 660 661 662 663 664 665
{
	unsigned int nbth = funcs.size();

	boost::thread** threads = new boost::thread*[nbth];

	std::vector<Dart> vd;
	vd.reserve(SIZE_BUFFER_THREAD);

	AttributeContainer* cont = NULL;
Pierre Kraemer's avatar
Pierre Kraemer committed
666 667
	DartMarker<MAP>* dmark = NULL;
	CellMarker<MAP, ORBIT>* cmark = NULL;
668 669 670 671 672 673 674 675 676 677 678 679 680 681
	AttributeMultiVector<Dart>* quickTraversal = map.template getQuickTraversal<ORBIT>() ;

	// fill each vd buffers with SIZE_BUFFER_THREAD darts
	Dart d;
	unsigned int di=0;

	if(quickTraversal != NULL)
	{
		cont = &(map.template getAttributeContainer<ORBIT>()) ;
		di = cont->begin();
		unsigned int nb = 0;
		while ((di != cont->end()) && (nb < SIZE_BUFFER_THREAD) )
		{
			d = quickTraversal->operator[](di);
682 683
			vd.push_back(d);
			nb++;
684 685 686 687 688 689 690
			cont->next(di);
		}
	}
	else
	{
		if(map.template isOrbitEmbedded<ORBIT>())
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
691
			cmark = new CellMarker<MAP, ORBIT>(map) ;
692 693 694 695
			d = map.begin();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
696
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!cmark->isMarked(d)))
697 698 699 700 701 702 703 704 705 706
				{
					cmark->mark(d);
					vd.push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
		else
		{
Pierre Kraemer's avatar
Pierre Kraemer committed
707
			dmark = new DartMarker<MAP>(map) ;
708 709 710 711
			d = map.begin();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
712
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!dmark->isMarked(d)))
713 714 715 716 717 718 719 720 721 722 723 724 725 726 727 728 729 730 731 732 733 734 735 736 737 738 739 740 741 742 743 744 745 746 747 748 749
				{
					dmark->markOrbit<ORBIT>(d);
					vd.push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
	}

	boost::barrier sync1(nbth+1);
	boost::barrier sync2(nbth+1);
	bool finished=false;
	// lauch threads
	if (needMarkers)
	{
		unsigned int nbth_prec = map.getNbThreadMarkers();
		if (nbth_prec < nbth+1)
			map.addThreadMarker(nbth+1-nbth_prec);
	}

	for (unsigned int i = 0; i < nbth; ++i)
		threads[i] = new boost::thread(ThreadFunction<MAP>(funcs[i], vd,sync1,sync2, finished,1+i));

	// and continue to traverse the map
	std::vector<Dart> tempo;
	tempo.reserve(SIZE_BUFFER_THREAD);

	if (cont)
	{
		while (di != cont->end())
		{
			tempo.clear();
			unsigned int nb=0;
			while ((di != cont->end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				d = quickTraversal->operator[](di);
750 751
				tempo.push_back(d);
				nb++;
752 753 754 755 756 757 758 759 760 761 762 763 764 765 766
				cont->next(di);
			}
			sync1.wait();
			vd.swap(tempo);
			sync2.wait();
		}
	}
	else if (cmark)
	{
		while (d != map.end())
		{
			tempo.clear();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
767
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!cmark->isMarked(d)))
768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787
				{
					cmark->mark(d);
					tempo.push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			vd.swap(tempo);
			sync2.wait();
		}
	}
	else
	{
		while (d != map.end())
		{
			tempo.clear();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
788
				if ((!map.template isBoundaryMarked<MAP::DIMENSION>(d)) && (!dmark->isMarked(d)))
789 790 791 792 793 794 795 796 797 798 799 800 801 802 803 804 805 806 807 808 809 810 811 812 813 814 815 816 817 818 819 820
				{
					dmark->markOrbit<ORBIT>(d);
					tempo.push_back(d);
					nb++;
				}
				map.next(d);
			}
			sync1.wait();
			vd.swap(tempo);
			sync2.wait();
		}
	}

	sync1.wait();
	finished = true;
	sync2.wait();

	//wait for all theads to be finished
	for (unsigned int i = 0; i < nbth; ++i)
	{
		threads[i]->join();
		delete threads[i];
	}
	delete[] threads;

	if (cmark != NULL)
		delete cmark;

	if (dmark != NULL)
		delete dmark;
}

821
} // namespace Parallel
822

823
} // namespace Algo
824

825
} // namespace CGoGN