parallel_foreach.hpp 24.1 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, const FunctorSelect& good, unsigned int currentThread)
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,good,currentThread);
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, const FunctorSelect& good, unsigned int currentThread)
Sylvain Thery's avatar
Sylvain Thery committed
162
{
163
	unsigned int nbth = funcs.size();
164

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

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

172 173 174 175 176 177 178 179 180 181
	AttributeContainer* cont = NULL;
	DartMarker* dmark = NULL;
	CellMarker<ORBIT>* cmark = NULL;
	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)
Sylvain Thery's avatar
Sylvain Thery committed
182
	{
183 184 185 186 187
		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
188
		{
189 190 191 192 193 194 195
			d = quickTraversal->operator[](di);
			if (good(d))
			{
				vd[nb%nbth].push_back(d);
				nb++;
			}
			cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
196 197
		}
	}
198
	else
199
	{
200 201 202 203 204 205 206 207
		if(map.template isOrbitEmbedded<ORBIT>())
		{
			cmark = new CellMarker<ORBIT>(map, currentThread) ;

			d = map.begin();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
208
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
209 210 211 212 213 214 215 216 217 218 219 220 221 222 223
				{
					cmark->mark(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
		else
		{
			dmark = new DartMarker(map, currentThread) ;
			d = map.begin();
			unsigned int nb = 0;
			while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
			{
224
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
225 226 227 228 229 230 231 232
				{
					dmark->markOrbit<ORBIT>(d);
					vd[nb%nbth].push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
233 234
	}

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

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

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

252
	for (unsigned int i = 0; i < nbth; ++i)
253
		tempo[i].reserve(SIZE_BUFFER_THREAD);
Sylvain Thery's avatar
Sylvain Thery committed
254 255


256 257 258
	if (cont)
	{
		while (di != cont->end())
Sylvain Thery's avatar
Sylvain Thery committed
259
		{
260 261 262 263
			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
264
			{
265 266 267 268 269 270 271
				d = quickTraversal->operator[](di);
				if (good(d))
				{
					tempo[nb%nbth].push_back(d);
					nb++;
				}
				cont->next(di);
Sylvain Thery's avatar
Sylvain Thery committed
272
			}
273 274 275 276 277 278 279 280 281 282 283 284 285 286 287
			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) )
			{
288
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
289 290 291 292 293 294 295 296 297 298 299 300 301 302 303 304 305 306 307 308 309 310
				{
					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) )
			{
311
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
312 313 314 315 316 317 318 319 320 321 322
				{
					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
323 324 325 326 327 328 329 330
		}
	}

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

	//wait for all theads to be finished
331
	for (unsigned int i = 0; i < nbth; ++i)
Sylvain Thery's avatar
Sylvain Thery committed
332 333 334 335
	{
		threads[i]->join();
		delete threads[i];
	}
sylvain thery's avatar
sylvain thery committed
336 337 338
	delete[] threads;
	delete[] vd;
	delete[] tempo;
Sylvain Thery's avatar
Sylvain Thery committed
339

340 341
	if (cmark != NULL)
		delete cmark;
Sylvain Thery's avatar
Sylvain Thery committed
342

343 344 345
	if (dmark != NULL)
		delete dmark;
}
Sylvain Thery's avatar
Sylvain Thery committed
346 347 348



349
template <typename MAP>
350
void foreach_dart(MAP& map, FunctorMapThreaded<MAP>& func, unsigned int nbth, bool needMarkers, const FunctorSelect& good)
351 352 353
{
	if (nbth == 0)
		nbth = optimalNbThreads();
354

355 356 357
	std::vector<FunctorMapThreaded<MAP>*> funcs;
	funcs.reserve(nbth);

358 359 360
	FunctorMapThreaded<MAP>* ptr = func.duplicate();
	bool shared = (ptr == NULL);

361
	if (shared)
362
	{
363
		for (unsigned int i = 0; i < nbth; ++i)
364
			funcs.push_back(&func);
365 366 367
	}
	else
	{
368 369
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
370
			funcs.push_back(func.duplicate());
371
	}
Sylvain Thery's avatar
Sylvain Thery committed
372

373
	foreach_dart<MAP>(map,funcs,needMarkers,good);
Sylvain Thery's avatar
Sylvain Thery committed
374

375
	if (!shared)
376
		for (unsigned int i = 0; i < nbth; ++i)
377
			delete funcs[i];
Sylvain Thery's avatar
Sylvain Thery committed
378 379
}

380 381

template <typename MAP>
382
void foreach_dart(MAP& map, std::vector<FunctorMapThreaded<MAP>*> funcs, bool needMarkers, const FunctorSelect& good)
383
{
384
	unsigned int nbth = funcs.size();
385

386 387 388
	std::vector<Dart>* vd = new std::vector<Dart>[nbth];
	boost::thread** threads = new boost::thread*[nbth];

389
	Dart d = map.begin();
390 391

	// nbth new functions, new thread (with good darts !)
392
	for (unsigned int i = 0; i < nbth; ++i)
393
		vd[i].reserve(SIZE_BUFFER_THREAD);
394 395

	// fill each vd buffers with 4096 darts
396
	unsigned int nb = 0;
397
	while ((d != map.end()) && (nb < nbth*SIZE_BUFFER_THREAD) )
398
	{
399
		if (good(d))
400 401 402 403 404 405 406
		{
			vd[nb%nbth].push_back(d);
			nb++;
		}
		map.next(d);
	}

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

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

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

428
	while (d != map.end())
429
	{
430
		for (unsigned int i = 0; i < nbth; ++i)
431 432
			tempo[i].clear();

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

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

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

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


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

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

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

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

	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);
	}

488 489 490 491
	CellMarkerNoUnmark<CELL> cm(map); // for 2 pass front mark / back unmark

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

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

			bool finished=false;
512 513 514 515

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

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

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

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

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

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

			bool finished=false;
566 567 568
			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));

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

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

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

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

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

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

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



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

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

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

627 628 629 630 631 632 633 634 635
	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
	{
636 637
		funcs.push_back(ptr);
		for (unsigned int i = 1; i < nbth; ++i)
638 639 640
			funcs.push_back(funcFront.duplicate());
		for (unsigned int i = 0; i < nbth; ++i)
			funcs.push_back(funcBack.duplicate());
641

642
	}
643

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

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

651 652 653 654 655 656 657 658 659 660 661 662 663 664 665 666 667 668 669 670 671 672 673 674 675 676 677 678 679 680 681 682 683 684 685 686 687 688 689 690 691 692 693 694 695 696 697 698 699 700 701 702 703 704 705 706 707 708 709 710 711 712 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 750 751 752 753 754 755 756 757 758 759 760 761 762 763 764 765 766 767 768 769 770 771 772 773 774 775 776 777 778 779 780 781 782 783 784 785 786 787 788 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 821 822 823 824 825 826 827 828 829 830 831 832 833 834 835 836 837 838 839 840 841 842 843 844 845 846 847 848 849 850 851 852 853 854 855 856 857 858 859 860 861 862 863 864 865 866 867 868 869 870 871 872 873 874 875 876 877 878 879 880 881 882 883 884 885 886 887 888 889 890 891 892 893 894 895 896 897 898 899 900 901 902 903 904 905 906 907 908 909 910 911 912 913 914 915 916 917 918 919 920 921 922 923 924 925 926 927 928 929 930 931 932 933 934 935 936 937 938 939 940 941 942 943 944 945 946 947 948 949 950 951 952 953 954 955 956 957 958 959 960 961 962 963 964 965 966 967 968 969 970 971 972 973 974 975 976 977 978 979 980 981 982 983 984 985 986 987 988 989 990 991 992 993 994 995 996 997 998 999 1000 1001 1002 1003 1004 1005 1006 1007 1008 1009 1010 1011 1012 1013 1014 1015 1016 1017 1018 1019 1020 1021 1022 1023 1024 1025 1026 1027 1028 1029 1030 1031 1032 1033 1034 1035 1036 1037 1038 1039 1040 1041 1042 1043 1044 1045 1046 1047 1048 1049 1050 1051 1052
//
//
//template <typename MAP>
//void Foreach<MAP>::Foreach(MAP& map, unsigned int nbth):
//m_nbth(nbth)
//{
//	if (m_nbth == 0)
//		m_nbth = optimalNbThreads();
//
//	m_funcs.reserve(m_nbth);
//
//	m_vd = new std::vector<Dart>[2*nbth];
//	for (unsigned int i = 0; i < 2*nbth; ++i)
//		m_vd[i].reserve(SIZE_BUFFER_THREAD);
//}
//
//template <typename MAP>
//Foreach<MAP>::~Foreach(MAP& map, unsigned int nbth)
//{
//	delete[] m_vd;
//}
//
//
//template <typename MAP>
//void Foreach<MAP>:: clearFunctors()
//{
//	m_funcs.clear();
//}
//
//template <typename MAP>
//void Foreach<MAP>:: addFunctor(FunctorMapThreaded<MAP>* funcPtr)
//{
//	m_funcs.push_back(funcPtr);
//}
//
//template <typename MAP>
//template<typename T>
//T* Foreach<MAP>::getFunctor(unsigned int i)
//{
//	assert(i < m_funcs.size());
//	return dynamic_cast<T*>(m_funcs[i]);
//}
//
//
//template <typename MAP>
//template <unsigned int ORBIT>
//void Foreach<MAP>::traverseCell<ORBIT>(bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
//{
//	assert(m_funcs.size() ==  m_nbth);
//
//	boost::thread** threads = new boost::thread*[m_nbth];
//
//	AttributeContainer* cont = NULL;
//	DartMarker* dmark = NULL;
//	CellMarker<ORBIT>* cmark = NULL;
//	AttributeMultiVector<Dart>* quickTraversal = m_map.template getQuickTraversal<ORBIT>() ;
//
//	// fill each vd buffers with SIZE_BUFFER_THREAD darts
//	Dart d;
//	unsigned int di=0;
//
//	if(quickTraversal != NULL)
//	{
//		cont = &(m_map.template getAttributeContainer<ORBIT>()) ;
//
//		di = cont->begin();
//		unsigned int nb = 0;
//		while ((di != cont->end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//		{
//			d = quickTraversal->operator[](di);
//			if (good(d))
//			{
//				m_vd[nb%m_nbth].push_back(d);
//				nb++;
//			}
//			cont->next(di);
//		}
//	}
//	else
//	{
//		if(m_map.template isOrbitEmbedded<ORBIT>())
//		{
//			cmark = new CellMarker<ORBIT>(m_map, currentThread) ;
//
//			d = m_map.begin();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
//				{
//					cmark->mark(d);
//					m_vd[nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//		}
//		else
//		{
//			dmark = new DartMarker(m_map, currentThread) ;
//			d = m_map.begin();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
//				{
//					dmark->markOrbit<ORBIT>(d);
//					m_vd[nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//		}
//	}
//
//	boost::barrier sync1(m_nbth+1);
//	boost::barrier sync2(m_nbth+1);
//	bool finished=false;
//	// lauch threads
//	if (needMarkers)
//	{
//		unsigned int nbth_prec = m_map.getNbThreadMarkers();
//		if (nbth_prec < m_nbth+1)
//			m_map.addThreadMarker(m_nbth+1-nbth_prec);
//	}
//
//	for (unsigned int i = 0; i < m_nbth; ++i)
//		threads[i] = new boost::thread(ThreadFunction<MAP>(m_funcs[i], m_vd[i],sync1,sync2, finished,1+i));
//
//
//	if (cont)
//	{
//		while (di != cont->end())
//		{
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[m_nbth+i].clear();
//			unsigned int nb = 0;
//			while ((di != cont->end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				d = quickTraversal->operator[](di);
//				if (good(d))
//				{
//					m_vd[m_nbth + nb%m_nbth].push_back(d);
//					nb++;
//				}
//				cont->next(di);
//			}
//			sync1.wait();
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[i].swap(m_vd[m_nbth+i]);
//			sync2.wait();
//		}
//	}
//	else if (cmark)
//	{
//		while (d != m_map.end())
//		{
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[m_nbth+i].clear();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
//				{
//					cmark->mark(d);
//					m_vd[m_nbth+nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//			sync1.wait();
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[i].swap(m_vd[m_nbth+i]);
//			sync2.wait();
//		}
//	}
//	else
//	{
//		while (d != m_map.end())
//		{
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[m_nbth+i].clear();
//			unsigned int nb = 0;
//			while ((d != m_map.end()) && (nb < m_nbth*SIZE_BUFFER_THREAD) )
//			{
//				if (good(d) && (!m_map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
//				{
//					dmark->markOrbit<ORBIT>(d);
//					m_vd[m_nbth+nb%m_nbth].push_back(d);
//					nb++;
//				}
//				m_map.next(d);
//			}
//			sync1.wait();
//			for (unsigned int i = 0; i < m_nbth; ++i)
//				m_vd[i].swap(m_vd[m_nbth+i]);
//			sync2.wait();
//		}
//	}
//
//	sync1.wait();
//	finished = true;
//	sync2.wait();
//
//	//wait for all theads to be finished
//	for (unsigned int i = 0; i < m_nbth; ++i)
//	{
//		threads[i]->join();
//		delete threads[i];
//	}
//	delete[] threads;
//	delete[] m_vd;
//
//	if (cmark != NULL)
//		delete cmark;
//
//	if (dmark != NULL)
//		delete dmark;
//}
//
//



template <typename MAP, unsigned int ORBIT>
void foreach_cell_all_thread(MAP& map, std::vector<FunctorMapThreaded<MAP>*>& funcs, bool needMarkers, const FunctorSelect& good, unsigned int currentThread)
{
	unsigned int nbth = funcs.size();

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

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

	AttributeContainer* cont = NULL;
	DartMarker* dmark = NULL;
	CellMarker<ORBIT>* cmark = NULL;
	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);
			if (good(d))
			{
				vd.push_back(d);
				nb++;
			}
			cont->next(di);
		}
	}
	else
	{
		if(map.template isOrbitEmbedded<ORBIT>())
		{
			cmark = new CellMarker<ORBIT>(map, currentThread) ;
			d = map.begin();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
				{
					cmark->mark(d);
					vd.push_back(d);
					nb++;
				}
				map.next(d);
			}
		}
		else
		{
			dmark = new DartMarker(map, currentThread) ;
			d = map.begin();
			unsigned int nb=0;
			while ((d != map.end()) && (nb < SIZE_BUFFER_THREAD) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
				{
					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);
				if (good(d))
				{
					tempo.push_back(d);
					nb++;
				}
				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) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!cmark->isMarked(d)))
				{
					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) )
			{
				if (good(d) && (!map.isBoundaryMarked(d)) && (!dmark->isMarked(d)))
				{
					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;
}







1053

1054
} // namespace Parallel
1055

1056
} // namespace Algo
1057

1058
} // namespace CGoGN