Debian Codegraph @

3rdparty/dissection/src/Driver/QueueRuntime.cpp

raw
1 /*! \file QueueRuntime.cpp
2 \brief management of threads for Dissection Matrix
3 \author Atsushi Suzuki, Laboratoire Jacques-Louis Lions
4 \date Jun. 20th 2014
5 \date Jul. 12th 2015
6 \date Nov. 30th 2016
7 \date Apr. 17th 2016
8 */
9
10 // This file is part of Dissection
11 //
12 // Dissection is free software: you can redistribute it and/or modify
13 // it under the terms of the GNU General Public License as published by
14 // the Free Software Foundation, either version 3 of the License, or
15 // (at your option) any later version.
16 //
17 // Linking Dissection statically or dynamically with other modules is making
18 // a combined work based on Disssection. Thus, the terms and conditions of
19 // the GNU General Public License cover the whole combination.
20 //
21 // As a special exception, the copyright holders of Dissection give you
22 // permission to combine Dissection program with free software programs or
23 // libraries that are released under the GNU LGPL and with independent modules
24 // that communicate with Dissection solely through the Dissection-fortran
25 // interface. You may copy and distribute such a system following the terms of
26 // the GNU GPL for Dissection and the licenses of the other code concerned,
27 // provided that you include the source code of that other code when and as
28 // the GNU GPL requires distribution of source code and provided that you do
29 // not modify the Dissection-fortran interface.
30 //
31 // Note that people who make modified versions of Dissection are not obligated
32 // to grant this special exception for their modified versions; it is their
33 // choice whether to do so. The GNU General Public License gives permission to
34 // release a modified version without this exception; this exception also makes
35 // it possible to release a modified version which carries forward this
36 // exception. If you modify the Dissection-fortran interface, this exception
37 // does not apply to your modified version of Dissection, and you must remove
38 // this exception when you distribute your modified version.
39 //
40 // This exception is an additional permission under section 7 of the GNU
41 // General Public License, version 3 ("GPLv3")
42 //
43 // Dissection is distributed in the hope that it will be useful,
44 // but WITHOUT ANY WARRANTY; without even the implied warranty of
45 // MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
46 // GNU General Public License for more details.
47 //
48 // You should have received a copy of the GNU General Public License
49 // along with Dissection. If not, see <http://www.gnu.org/licenses/>.
50 //
51
52 #include <string>
53 #include "Driver/QueueRuntime.hpp"
54 #include "Compiler/DissectionIO.hpp"
55
56
57 #define RATIO_STATIC 0.7 // for slow DGEMM'
58 #define RATIO_QUEUE_GREEDY 0.8
59
60 //#define DEBUG_THREAD_TIME
61 //#define DEBUG_EXEC_THREAD
62 #define DEBUG_DEADLOCK
63
64 // DEBUG_DEADLOCK only works without setting DEBUG_EXEC_THREAD_IDLE
65 #ifdef DEBUG_DEADLOCK
66 #ifdef DEBUG_EXEC_THREAD_IDLE
67 #undef DEBUG_EXEC_THREAD_IDLE
68 #endif // DEBUG_EXEC_THREAD_IDLE
69 #endif // DEBUG_DEADLOCK
70
71 // constructor
72 QueueRuntime::QueueRuntime(int nb_doms, int num_threads, const bool isSym,
73 const bool verbose, FILE *fp)
74 {
75
76 _nb_doms = nb_doms;
77 _num_threads = num_threads;
78 _isSym = isSym;
79 _verbose = verbose;
80 _fp = fp;
81
82 _zone_entered = new int[DIST_TASK_CRITICAL];
83 _zone_finished = new int[DIST_TASK_CRITICAL];
84 _zone_static_assigned = new int[DIST_TASK_CRITICAL];
85
86 allocate_int2d(_begins, num_threads);
87 allocate_int2d(_ends, num_threads);
88
89 allocate_int3d(_group_entered, num_threads);
90 allocate_int3d(_group_finished, num_threads);
91 allocate_int3d(_group_task_ends, num_threads);
92 allocate_int3d(_group_static_assigned, num_threads);
93
94 _group_task_id = new int[num_threads];
95
96 allocate_int3d(_begins_group, num_threads);
97 allocate_int3d(_ends_group, num_threads);
98 allocate_unsigned2d(_group_nops, num_threads);
99 _mutex_group = new QueueRuntime_mutex[num_threads];
100
101 }
102
103
104 QueueRuntime::~QueueRuntime()
105 {
106 // initialize state to controle tasks
107 delete [] _zone_entered;
108 delete [] _zone_finished;
109 delete [] _zone_static_assigned;
110
111 deallocate_int2d(_begins);
112 deallocate_int2d(_ends);
113 deallocate_int3d(_group_entered);
114 deallocate_int3d(_group_finished);
115 deallocate_int3d(_group_task_ends);
116 deallocate_int3d(_group_static_assigned);
117 deallocate_int3d(_begins_group);
118 deallocate_int3d(_ends_group);
119 deallocate_unsigned2d(_group_nops);
120
121 delete [] _group_task_id;
122 delete [] _mutex_group;
123 }
124
125
126 void allocate_int2d(int **&array, const int num_threads)
127 {
128 array = new int*[num_threads];
129 array[0] = new int[num_threads * DIST_TASK_CRITICAL];
130 int p, pp;
131 p = 1;
132 pp = DIST_TASK_CRITICAL;
133 for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
134 array[p] = &array[0][pp];
135 }
136 }
137
138 void allocate_unsigned2d(long **&array, const int num_threads)
139 {
140 array = new long*[num_threads];
141 array[0] = new long[num_threads * DIST_TASK_CRITICAL];
142 int p, pp;
143 p = 1;
144 pp = DIST_TASK_CRITICAL;
145 for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
146 array[p] = &array[0][pp];
147 }
148 }
149
150 void allocate_int3d(int ***&array, const int num_threads)
151 {
152 array = new int**[num_threads];
153 array[0] = new int*[num_threads * DIST_TASK_CRITICAL];
154 array[0][0] = new int[(num_threads *
155 DIST_TASK_CRITICAL * DIST_TASK_CRITICAL)];
156 int p, q, pp;
157 p = 1;
158 pp = DIST_TASK_CRITICAL;
159 for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
160 array[p] = &array[0][pp];
161 }
162 p = 0;
163 pp = 0;
164 for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
165 for (q = 0; q < DIST_TASK_CRITICAL; q++) {
166 if (!((p == 0) && (q == 0))) {
167 array[p][q] = &array[0][0][(q + pp) * DIST_TASK_CRITICAL];
168 }
169 }
170 }
171 }
172
173 void deallocate_int2d(int **&array)
174 {
175 delete [] array[0];
176 delete [] array;
177 }
178
179 void deallocate_unsigned2d(long **&array)
180 {
181 delete [] array[0];
182 delete [] array;
183 }
184
185 void deallocate_int3d(int ***&array)
186 {
187 delete [] array[0][0];
188 delete [] array[0];
189 delete [] array;
190 }
191
192 int IndexTask(vector<C_task *> &queue, int pos)
193 {
194 int j = 0;
195 int pos1 = pos > queue.size() ? queue.size() : pos;
196 for (int i = 0; i < pos1; i++) {
197 j += queue[j]->atomic_size;
198 }
199 return j;
200 }
201
202 // #define DEBUG_NULL_TASK
203 void copytask_list2seq(list<C_task_seq*> &queue_static,
204 list<C_task_seq*> queue_lists,
205 list<C_task *> &queue_null,
206 // list<C_task *> &queue_dummy,
207 string task_name,
208 int task_id,
209 int mutex_id,
210 int parallel_single,
211 int num_threads,
212 int level,
213 int phase)
214 {
215 // #define DEBUG_ASSIGN_TASK
216 #ifdef DEBUG_ASSIGN_TASK
217 cerr << endl << "** " << task_name << " ** " << queue_lists.size() << endl;
218 #endif
219 int num_tasks = 0;
220 for (list<C_task_seq*>::const_iterator it = queue_lists.begin();
221 it != queue_lists.end(); ++it) {
222 // int itmp = 0;
223 for (int j = (*it)->begin; j < (*it)->end; j++) {
224 if (*((*(*it)->queue)[j]->ops_complexity) != 0L) {//cf. -1L : 16 Sep.2014
225 num_tasks++;
226 // itmp++;
227 }
228 else {
229 (*(*it)->queue)[j]->status = TASK_DONE;
230 #ifdef DEBUG_NULL_TASK
231 fprintf(stderr, "%s %d : copytask_list2seq() null task = %s\n",
232 __FILE__, __LINE__, (*(*it)->queue)[j]->task_name);
233 #endif
234 queue_null.push_back((*(*it)->queue)[j]);
235 }
236 }
237 #ifdef DEBUG_ASSIGN_TASK
238 cerr << (*it)->task_id
239 << " [ " << (*it)->end << " " << (*it)->begin << " ] ";
240 #endif
241 }
242 #ifdef DEBUG_ASSIGN_TASK
243 cerr << endl;
244 #endif
245 vector<C_task *> *tasks_tmp = new vector<C_task *>;
246 long nops = 0L;
247 tasks_tmp->resize(num_tasks);
248 // tasks_tmp->reserve(num_tasks);
249 int k = 0;
250 for (list<C_task_seq*>::const_iterator it = queue_lists.begin();
251 it != queue_lists.end(); ++it) {
252 for (int j = (*it)->begin; j < (*it)->end; j++) {
253 if (*((*(*it)->queue)[j]->ops_complexity) != 0L) { //cf. -1L : 16 Sep.2014
254 (*tasks_tmp)[k++] = (*(*it)->queue)[j];
255 if (*((*(*it)->queue)[j]->ops_complexity) > 0L) {
256 nops += *((*(*it)->queue)[j]->ops_complexity);
257 }
258 }
259 }
260 }
261 C_task_seq* seq_tmp = new C_task_seq(task_id,
262 task_name,
263 mutex_id,
264 parallel_single,
265 num_threads,
266 level,
267 phase,
268 tasks_tmp,
269 0, // begin
270 num_tasks, // end
271 nops);
272 queue_static.push_back(seq_tmp);
273 }
274
275 void task_assign_diag1(list<C_task_seq*> * &queue_static,
276 vector<C_task *>* &tasks_queue,
277 list<C_task *> &queue_null,
278 // list<C_task *> &queue_dummy,
279 vector<int> &nrow_DFullLDLt,
280 vector<bool> &isMergedDTRSM,
281 string queue_symbol,
282 int queue_id,
283 int level_id,
284 int num_threads,
285 int level_last,
286 int level,
287 int begdom,
288 int enddom,
289 long *nops_sum,
290 vector<int> starts,
291 list<C_task_seq*>* &queue_lists,
292 bool queue_lists_clear,
293 Dissection::Tree* btree,
294 vector<int>* children)
295 {
296 int num_tmp_shared;
297 list<C_task_seq *> tmp_dynamic;
298 list<C_task_seq *> task_seq_tmp;
299 long nops_block_total;
300 vector<C_task *> *tmp_shared = new vector<C_task *>;
301
302 if (queue_lists_clear) {
303 for (int p = 0; p < num_threads; p++) {
304 #if 1
305 for (list<C_task_seq *>::iterator it = queue_lists[p].begin();
306 it != queue_lists[p].end(); ++it) {
307 delete (*it);
308 (*it) = NULL;
309 }
310 #endif
311 queue_lists[p].clear();
312 }
313 }
314 task_seq_tmp.clear();
315 nops_block_total = 0L;
316 for (int d = begdom; d < enddom; d++) {
317 const int j = btree->selfIndex(d);
318 for (int ic = 0; ic < 2; ic++) {
319 const int jc = children[j][ic];
320 if ((queue_id == C_DTRSM) && (nrow_DFullLDLt[jc] > 2)) {
321 continue;
322 }
323 long nops = 0L;
324 const int begin = starts[jc];
325 int end;
326 if (queue_id == C_DTRSM) {
327 if (!isMergedDTRSM[j]) { // looking the father node
328 end = IndexTask(tasks_queue[jc], tasks_queue[jc][0]->parallel_max);
329 }
330 else {
331 end = tasks_queue[jc].size();
332 }
333 }
334 else {
335 int itmp = tasks_queue[jc][0]->parallel_max;
336 int jtmp = tasks_queue[jc].size();
337 // if (itmp < (_isSym ? 3 : 4)) {
338 if (!isMergedDTRSM[j]) {
339 end = itmp;
340 }
341 else {
342 if (itmp == jtmp) {
343 end = jtmp;
344 }
345 else {
346 end = itmp + tasks_queue[jc][itmp]->parallel_max;
347 }
348 }
349 }
350 if (level == 0) {
351 end = (int)((double)end * RATIO_STATIC);
352 const int ktmp = tasks_queue[jc][end]->atomic_id;
353 end -= ktmp;
354 }
355 for (int i = begin; i < end; i++) {
356 nops += *(tasks_queue[jc][i]->ops_complexity);
357 }
358 string task_name = to_string(jc);
359 if (nops > 0L) {
360 C_task_seq* tmp =
361 new C_task_seq(queue_id,
362 task_name, // for debugging
363 (-1), // mutex_id
364 TASK_SINGLE,
365 1,
366 (level + 1),
367 (level_last - 1 - level) * 6 + level_id,
368 &tasks_queue[jc],
369 begin,
370 end,
371 nops);
372 task_seq_tmp.push_back(tmp);
373 nops_block_total += nops;
374 }
375 else {
376 for (int i = begin; i < end; i++) {
377 queue_null.push_back(tasks_queue[jc][i]);
378 }
379 }
380 } // loop : ic
381 } // loop : j
382 num_tmp_shared = 0;
383 tmp_dynamic.clear();
384
385 if (task_seq_tmp.size() > 0) {
386 task_seq_tmp.sort(C_task_seq_complexity_greater);
387 string queue_name;
388 if (level == 0) {
389 queue_name = queue_symbol + "% ";
390 }
391 else {
392 queue_name = queue_symbol + "* ";
393 }
394 assign_tasks_statically(queue_lists,
395 tmp_dynamic,
396 nops_sum,
397 task_seq_tmp,
398 queue_id,
399 queue_name.c_str(),
400 (level + 1),
401 (level_last - 1 - level) * 6 + level_id,
402 nops_block_total,
403 num_threads);
404 // task_seq_tmp.clear(); moved in assign_tasks_statically
405 if (tmp_dynamic.size() > 0) {
406 num_tmp_shared += tmp_dynamic.size();
407 }
408 }
409 if (level == 0) {
410 for (int d = begdom; d < enddom; d++) {
411 const int j = btree->selfIndex(d);
412 for (int ic = 0; ic < 2; ic++) {
413 const int jc = children[j][ic];
414 int parallel_max;
415 if ((queue_id == C_DTRSM) && (nrow_DFullLDLt[jc] > 2)) {
416 continue;
417 }
418 if (queue_id == C_DTRSM) {
419 if (!isMergedDTRSM[j]) { // looking father node
420 parallel_max = IndexTask(tasks_queue[jc],
421 tasks_queue[jc][0]->parallel_max);
422 }
423 else {
424 parallel_max = tasks_queue[jc].size();
425 }
426 }
427 else {
428 int itmp = tasks_queue[jc][0]->parallel_max;
429 int jtmp = tasks_queue[jc].size();
430 // if (itmp < _isSym ? 3 : 4) {
431 if (!isMergedDTRSM[j]) {
432 parallel_max = itmp;
433 }
434 else {
435 parallel_max = ((itmp == jtmp) ? jtmp :
436 (itmp + tasks_queue[jc][itmp]->parallel_max));
437 }
438 }
439 const int end = (int)((double)parallel_max * RATIO_STATIC);
440 const int ktmp = tasks_queue[jc][end]->atomic_id;
441 num_tmp_shared += parallel_max - end + ktmp;
442 }
443 }
444 }
445 tmp_shared->reserve(num_tmp_shared);
446 if (tmp_dynamic.size() > 0) {
447 long nops = 0L;
448 for (list<C_task_seq *>::iterator mt = tmp_dynamic.begin();
449 mt != tmp_dynamic.end(); ++mt) {
450 nops += (*mt)->ops_complexity;
451 }
452 #ifdef DEBUG_PREPARE_THREAD
453 cout << "static -> dynamic : " << tmp_dynamic.size()
454 << " nops_sum = " << nops << " " ;
455 #endif
456 for (list<C_task_seq *>::iterator mt = tmp_dynamic.begin();
457 mt != tmp_dynamic.end(); ++mt) {
458 for (int i = (*mt)->begin; i < (*mt)->end; i++) {
459 tmp_shared->push_back((*(*mt)->queue)[i]);
460 }
461 delete (*mt);
462 (*mt) = NULL;
463 }
464 #ifdef DEBUG_PREPARE_THREAD
465 cout << endl;
466 #endif
467 } // if (tmp_dynamic.size() > 0)
468 if (level == 0) {
469 for (int d = begdom; d < enddom; d++) {
470 const int j = btree->selfIndex(d);
471 for (int ic = 0; ic < 2; ic++) {
472 const int jc = children[j][ic];
473 int parallel_max;
474 if ((queue_id == C_DTRSM) && (nrow_DFullLDLt[jc] > 2)) {
475 continue;
476 }
477 if (queue_id == C_DTRSM) {
478 if (!isMergedDTRSM[j]) { // looking father node
479 parallel_max = IndexTask(tasks_queue[jc],
480 tasks_queue[jc][0]->parallel_max);
481 }
482 else {
483 parallel_max = tasks_queue[jc].size();
484 }
485 }
486 else {
487 int itmp = tasks_queue[jc][0]->parallel_max;
488 int jtmp = tasks_queue[jc].size();
489 // if (itmp <= (_isSym ? 3 : 4)) {
490 if (!isMergedDTRSM[j]) {
491 parallel_max = itmp;
492 }
493 else {
494 parallel_max = ((itmp == jtmp) ? jtmp :
495 (itmp + tasks_queue[jc][itmp]->parallel_max));
496 }
497 }
498 int end = (int)((double)parallel_max * RATIO_STATIC);
499 const int ktmp = tasks_queue[jc][end]->atomic_id;
500 end -= ktmp;
501 for (int i = end; i < parallel_max; i++) {
502 // exclude null tasks
503 if (*(tasks_queue[jc][i]->ops_complexity) > 0L) {
504 tmp_shared->push_back(tasks_queue[jc][i]);
505 }
506 else {
507 queue_null.push_back(tasks_queue[jc][i]);
508 }
509 // cyclic by index jc is better ?
510 }
511 } // loop : ic
512 }
513 }
514 {
515 string task_name = queue_symbol + " " + to_string(level + 1);
516 for (int p = 0; p < num_threads; p++) {
517 copytask_list2seq(queue_static[p],
518 queue_lists[p],
519 queue_null,
520 // queue_dummy,
521 task_name,
522 queue_id,
523 p,
524 TASK_SINGLE,
525 1,
526 (level + 1),
527 (level_last - 1 - level) * 6 + level_id);
528 for (list<C_task_seq *>::iterator it = queue_lists[p].begin();
529 it != queue_lists[p].end(); ++it) {
530 delete (*it);
531 (*it) = NULL;
532 }
533 }
534 }
535 #ifdef DEBUG_PREPARE_THREAD
536 cout << queue_symbol << num_tmp_shared << " : " << tmp_shared->size()
537 << endl;
538 #endif
539 if (tmp_shared->size() > 0) {
540 string task_name = queue_symbol + "+ " + to_string(level + 1);
541 long nops = 0L;
542 for (vector<C_task *>::const_iterator it = tmp_shared->begin();
543 it != tmp_shared->end(); ++it) {
544 nops += *((*it)->ops_complexity);
545 }
546 C_task_seq* tmp =
547 new C_task_seq(queue_id,
548 task_name,
549 0,
550 TASK_PARALLEL,
551 num_threads,
552 (level + 1),
553 (level_last - 1 - level) * 6 + level_id,
554 tmp_shared,
555 0,
556 tmp_shared->size(),
557 nops);
558 for (int p = 0; p < num_threads; p++) {
559 queue_static[p].push_back(tmp);
560 }
561 } // if (num_tmp_shared > 0)
562 else {
563 delete tmp_shared;
564 }
565 // delete tmp_shared;
566 }
567
568 void task_assign_diag2(list<C_task_seq*> *&queue_static,
569 vector<C_task *>* &tasks_queue,
570 list<C_task *> &queue_null,
571 // list<C_task *> &queue_dummy,
572 vector<bool> &isMergedDTRSM,
573 string queue_symbol,
574 int queue_id,
575 int level_id,
576 int num_threads,
577 int level_last,
578 int level,
579 int begdom,
580 int enddom,
581 long *nops_sum,
582 vector<int> starts,
583 vector<int> starts_sub,
584 list<C_task_seq*>* &queue_lists,
585 bool queue_lists_clear,
586 Dissection::Tree* btree,
587 vector<int>* children)
588
589 {
590 int num_tmp_shared;
591 list<C_task_seq*> tmp_dynamic;
592 list<C_task_seq *>task_seq_tmp;
593 long nops_block_total;
594 vector<C_task *> *tmp_shared = new vector<C_task *>;
595
596 task_seq_tmp.clear();
597 nops_block_total = 0L;
598 if (queue_lists_clear) {
599 for (int p = 0; p < num_threads; p++) {
600 #if 1
601 for (list<C_task_seq *>::iterator it = queue_lists[p].begin();
602 it != queue_lists[p].end(); ++it) {
603 delete (*it);
604 (*it) = NULL;
605 }
606 #endif
607 queue_lists[p].clear();
608 }
609 }
610 for (int d = begdom; d < enddom; d++) {
611 const int j = btree->selfIndex(d);
612 long nops = 0L;
613 const int begin = starts_sub[j];
614 int end;
615 // if (tasks_queue0[j].size() <= 4) {
616 if (!isMergedDTRSM[j]) {
617 end = tasks_queue[j][0]->parallel_max;
618 }
619 else {
620 end = tasks_queue[j].size();
621 }
622 if (level == 0) {
623 end = (int)((double)end * RATIO_STATIC);
624 }
625 for (int i = begin; i < end; i++) {
626 nops += *(tasks_queue[j][i]->ops_complexity);
627 }
628 string task_name = to_string(j);
629 if (nops > 0L) {
630 C_task_seq* tmp =
631 new C_task_seq(queue_id,
632 task_name, // for debugging
633 (-1), // mutex_id
634 TASK_SINGLE,
635 1,
636 (level + 1),
637 (level_last - 1 - level) * 6 + level_id,
638 &tasks_queue[j],
639 begin,
640 end,
641 nops);
642 task_seq_tmp.push_back(tmp);
643 nops_block_total += nops;
644 }
645 else {
646 for (int i = begin; i < end; i++) {
647 queue_null.push_back(tasks_queue[j][i]);
648 }
649 }
650 } // loop : j
651 tmp_dynamic.clear();
652 num_tmp_shared = 0;
653 if (task_seq_tmp.size() > 0) {
654 task_seq_tmp.sort(C_task_seq_complexity_greater);
655 string queue_name;
656 if (level == 0) {
657 queue_name = queue_symbol + "% " ;
658 }
659 else {
660 queue_name = queue_symbol + "* " ;
661 }
662 assign_tasks_statically(queue_lists,
663 tmp_dynamic,
664 nops_sum,
665 task_seq_tmp,
666 queue_id,
667 queue_name.c_str(),
668 (level + 1),
669 (level_last - 1 - level) * 6 + level_id,
670 nops_block_total,
671 num_threads);
672 if (tmp_dynamic.size() > 0) {
673 num_tmp_shared += tmp_dynamic.size();
674 }
675 }
676 if (level == 0) {
677 for (int d = begdom; d < enddom; d++) {
678 const int j = btree->selfIndex(d);
679 const int parallel_max = tasks_queue[j].size();
680 const int end = (int)((double)parallel_max * RATIO_STATIC);
681 num_tmp_shared += parallel_max - end;
682 }
683 }
684 tmp_shared->reserve(num_tmp_shared);
685 if (tmp_dynamic.size() > 0) {
686 long nops = 0L;
687 for (list<C_task_seq *>::const_iterator mt = tmp_dynamic.begin();
688 mt != tmp_dynamic.end(); ++mt) {
689 nops += (*mt)->ops_complexity;
690 }
691 for (list<C_task_seq *>::iterator mt = tmp_dynamic.begin();
692 mt != tmp_dynamic.end(); ++mt) {
693 for (int i = (*mt)->begin; i < (*mt)->end; i++) {
694 tmp_shared->push_back((*(*mt)->queue)[i]);
695 }
696 delete (*mt);
697 (*mt) = NULL;
698 }
699 }
700 if (level == 0) {
701 for (int d = begdom; d < enddom; d++) {
702 const int j = btree->selfIndex(d);
703 int parallel_max;
704 if (!isMergedDTRSM[j]) {
705 parallel_max = tasks_queue[j][0]->parallel_max;
706 }
707 else {
708 parallel_max = tasks_queue[j].size();
709 }
710 const int end = (int)((double)parallel_max * RATIO_STATIC);
711 for (int i = end; i < parallel_max; i++) {
712 if (*(tasks_queue[j][i]->ops_complexity) > 0L) { // exclude null tasks
713 tmp_shared->push_back(tasks_queue[j][i]);
714 }
715 else {
716 queue_null.push_back(tasks_queue[j][i]);
717 }
718 // cyclic by index jc is better ?
719 }
720 }
721 }
722 {
723 string task_name = queue_symbol + " " + to_string(level + 1);
724 for (int p = 0; p < num_threads; p++) {
725 copytask_list2seq(queue_static[p],
726 queue_lists[p],
727 queue_null,
728 // queue_dummy,
729 task_name,
730 queue_id,
731 p,
732 TASK_SINGLE,
733 1,
734 (level + 1),
735 (level_last - 1 - level) * 6 + level_id);
736 // 3 Jul 2016
737 for (list<C_task_seq *>::iterator it = queue_lists[p].begin();
738 it != queue_lists[p].end(); ++it) {
739 delete (*it);
740 (*it) = NULL;
741 }
742 }
743 }
744 #ifdef DEBUG_PREPARE_THREAD
745 cout << queue_symbol << num_tmp_shared << " : " << tmp_shared->size()
746 << endl;
747 #endif
748 if (tmp_shared->size() > 0) {
749 string task_name = queue_symbol + "+ " + to_string(level + 1);
750 long nops = 0L;
751 for (vector<C_task *>::const_iterator it = tmp_shared->begin();
752 it != tmp_shared->end(); ++it) {
753 nops += *((*it)->ops_complexity);
754 }
755 C_task_seq* tmp =
756 new C_task_seq(queue_id,
757 task_name,
758 0,
759 TASK_PARALLEL,
760 num_threads,
761 (level + 1),
762 (level_last - 1 - level) * 6 + level_id,
763 tmp_shared,
764 0,
765 tmp_shared->size(),
766 nops);
767 for (int p = 0; p < num_threads; p++) {
768 queue_static[p].push_back(tmp);
769 }
770 } // if (tmp_shared->size() > 0)
771 else {
772 delete tmp_shared;
773 }
774 }
775
776 void QueueRuntime::generate_queue(C_task_seq* &queue_symb_,
777 list<C_task_seq*>* & queue_static_,
778 vector<C_task_seq *>* &queue_dynamic_,
779 list<C_task *> &queue_null_,
780 // list<C_task *> &queue_dummy_,
781 Dissection::Tree* btree,
782 vector<int>* children,
783 vector<C_task *>* tasks_SparseSymb,
784 vector<C_task *>* tasks_SparseNum,
785 vector<C_task *>* tasks_SparseLocalSchur,
786 vector<C_task *>* tasks_DFillSym,
787 vector<C_task *>* tasks_DFullLDLt,
788 vector<C_task *>* tasks_DTRSMScale,
789 vector<C_task *>* tasks_DGEMM,
790 vector<C_task *>** tasks_Dsub,
791 vector<C_task *>* tasks_deallocLower,
792 vector<C_task *>* tasks_deallocLocalSchur,
793 long **nops_queue,
794 vector<vector<int> > all_fathersIndex,
795 vector<int> nrow_DFullLDLt,
796 vector<bool> isMergedDTRSM,
797 vector<bool> isDividedDTRSM,
798 const int level_last)
799 {
800 // begin : task squence for symmbolic factorization
801 const int num_threads = _num_threads;
802 const int nb_doms_dense = (1U << level_last) - 1;
803
804 { //begin scope : task_name
805 list<C_task_seq*> queue_tmp;
806 string task_name = "l " + to_string(level_last);
807
808 const int begdom = 1U << level_last;
809 const int enddom = begdom * 2;
810
811 for (int d = begdom; d < enddom; d++) {
812 const int j = d - begdom;
813 C_task_seq* tmp =
814 new C_task_seq(C_SPARSESYMBFACT,
815 _null_name, // dummy
816 (-1), // mutex_id
817 TASK_SINGLE,
818 1,
819 level_last,
820 (-1), // phase
821 &tasks_SparseSymb[j],
822 0,
823 1,
824 *(tasks_SparseSymb[j][0]->ops_complexity));
825 queue_tmp.push_back(tmp);
826 }
827 //
828 queue_tmp.sort(C_task_seq_complexity_greater);
829 vector<C_task *> *task_tmp = new vector<C_task *>;
830 task_tmp->resize(begdom);
831 int k = 0;
832 for (list<C_task_seq*>::iterator it = queue_tmp.begin();
833 it != queue_tmp.end(); ++it, k++) {
834 (*task_tmp)[k] = (*it)->queue[0][0];
835 }
836 queue_symb_ = new C_task_seq(C_SPARSESYMBFACT,
837 task_name, // dummy
838 (-1), // mutex_id
839 TASK_SINGLE,
840 1,
841 level_last,
842 (-1), // phase
843 task_tmp,
844 0,
845 begdom,
846 0); // dummy
847 _queue_symb = queue_symb_;
848 for (list<C_task_seq*>::iterator it = queue_tmp.begin();
849 it != queue_tmp.end(); ++it) {
850 delete (*it);
851 (*it) = NULL;
852 }
853 } //end scope : task_name
854 queue_static_ = new list<C_task_seq*>[num_threads];
855 _queue_static = queue_static_;
856 queue_dynamic_ = new vector<C_task_seq*>;
857 _queue_dynamic = queue_dynamic_;
858
859 // end : task squence for symmbolic factorization
860 list<C_task_seq*>* queue_dynamic = new list<C_task_seq*>[level_last + 1];
861 list<C_task_seq*>* queue_dynamic0 = new list<C_task_seq*>;
862 list<C_task_seq*>* queue_dynamic1 = new list<C_task_seq*>[level_last + 1];
863 list<C_task_seq*>* queue_dynamic2 = new list<C_task_seq*>[level_last + 1];
864 // list<C_task_seq*>* queue_dynamic3 = new list<C_task_seq*>[level_last + 1];
865 list<C_task_seq*>* queue_lists = new list<C_task_seq*>[num_threads];
866 list<C_task_seq*> queue_tmp0, queue_tmp1;
867 // assuming that num_leaves(level_last) > num_threads
868 // num_leaves(level_last) = _begLevel[level_last] - _begLevel[level_last + 1]
869 //
870 // Sparse numeric factorization : tasks_SparseNum[] -> _queue_static[]
871 queue_tmp0.clear();
872 #define SPARSE_MERGED
873 #ifdef SPARSE_MERGED
874 {
875 // sparse subdomains : tasks_SparseNum[]
876 // all dense subdomains : tasks_DFillSym[]
877 // the begining of the dense subdomains
878 const int begdom = 1U << (level_last - 1);
879 const int enddom = begdom * 2;
880 for (int d = begdom; d < enddom; d++) {
881 int j;
882 vector<C_task *>* tasks = new vector<C_task *>;
883 j = btree->selfIndex(2 * d);
884 long nops = 0L;
885 tasks->push_back(tasks_SparseNum[j][0]);
886 nops += *(tasks_SparseNum[j][0]->ops_complexity);
887 tasks->push_back(tasks_SparseLocalSchur[j][0]);
888 nops += *(tasks_SparseLocalSchur[j][0]->ops_complexity);
889 j = btree->selfIndex(2 * d + 1);
890 tasks->push_back(tasks_SparseNum[j][0]);
891 nops += *(tasks_SparseNum[j][0]->ops_complexity);
892 tasks->push_back(tasks_SparseLocalSchur[j][0]);
893 nops += *(tasks_SparseLocalSchur[j][0]->ops_complexity);
894 j = btree->selfIndex(d);
895 for (vector<C_task *>::const_iterator it = tasks_DFillSym[j].begin();
896 it != tasks_DFillSym[j].end(); ++it) {
897 tasks->push_back(*it);
898 nops += *((*it)->ops_complexity);
899 }
900 // task complexity of DFillSym[] in higher level is very large
901 int dd;
902 if (d % 2 == 0) {
903 dd = (d - begdom) / 2;
904 }
905 else {
906 dd = begdom - (d - begdom + 1) / 2;
907 }
908 if (dd > 0) {
909 j = btree->selfIndex(dd);
910 for (vector<C_task *>::const_iterator it = tasks_DFillSym[j].begin();
911 it != tasks_DFillSym[j].end(); ++it) {
912 tasks->push_back(*it);
913 nops += *((*it)->ops_complexity);
914 }
915 }
916 C_task_seq* tmp =
917 new C_task_seq(C_SPARSESOLVER,
918 _null_name,
919 (-1), // mutex_id
920 (-1), //TASK_SINGLE,
921 (-1), // 1,
922 (-1), // level_last,
923 (-1), // phase
924 tasks,
925 0,
926 tasks->size(),
927 nops);
928 queue_tmp0.push_back(tmp);
929 } // loop : d(j)
930 string task_name = "z " + to_string(level_last);
931 copytask_list2seq(queue_dynamic[level_last],
932 queue_tmp0,
933 queue_null_,
934 // queue_dummy_,
935 task_name,
936 C_SPARSESOLVER, // C_FILLMATRIX1,
937 0, // shared by all threads
938 TASK_PARALLEL,
939 num_threads,
940 level_last,
941 2);
942 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
943 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
944 it != queue_tmp0.end(); ++it) {
945 delete (*it)->queue; // deallocate a container : tasks in L880
946 delete (*it);
947 (*it) = NULL;
948 }
949 }
950 #else
951 {
952 // sparse subdomains : tasks_SparseNum[]
953 // all dense subdomains : tasks_DFillSym[]
954 // the begining of the dense subdomains
955 const int begdom = 1U << level_last;
956 const int enddom = begdom * 2;
957 queue_tmp0.clear();
958 for (int d = begdom; d < enddom; d++) {
959 const int j = btree->selfIndex(d);
960 C_task_seq* tmp =
961 new C_task_seq(C_SPARSENUMFACT,
962 _null_name,
963 (-1), // mutex_id
964 (-1), //TASK_SINGLE,
965 (-1), // 1,
966 (-1), // level_last,
967 (-1), // phase
968 &tasks_SparseNum[j],
969 0,
970 1,
971 *(tasks_SparseNum[j][0]->ops_complexity));
972 queue_tmp0.push_back(tmp);
973 } // loop : d(j)
974 queue_tmp0.sort(C_task_seq_complexity_greater);
975 {
976 int itmp = 0;
977 for (list<C_task_seq*>::const_iterator it = queue_tmp0.begin();
978 it != queue_tmp0.end(); ++it, itmp++) {
979 queue_lists[itmp % num_threads].push_back(*it);
980 }
981 } // loop : it, itmp
982 {
983 string task_name = "u " + to_string(level_last);
984 for (int p = 0; p < num_threads; p++) {
985 copytask_list2seq(_queue_static[p],
986 queue_lists[p],
987 queue_null_,
988 // queue_dummy_,
989 task_name,
990 C_SPARSENUMFACT,
991 p,
992 TASK_SINGLE,
993 1,
994 level_last,
995 0);
996 }
997 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
998 it != queue_tmp0.end(); ++it) {
999 delete (*it);
1000 (*it) = NULL;
1001 }
1002 }
1003 // Sparse local Schur complement : tasks_SparseLocalSchur[] -> queue_dynamic[]
1004 queue_tmp0.clear();
1005 for (int d = begdom; d < enddom; d++) {
1006 const int j = btree->selfIndex(d);
1007 C_task_seq* tmp =
1008 new C_task_seq(C_SPARSELOCALSCHUR,
1009 _null_name, //(char *)NULL, // dummy
1010 (-1), // mutex_id
1011 (-1), //TASK_SINGLE,
1012 (-1), // 1,
1013 (-1), // level_last,
1014 (-1), // phase
1015 &tasks_SparseLocalSchur[j],
1016 0,
1017 1,
1018 *(tasks_SparseLocalSchur[j][0]->ops_complexity));
1019 queue_tmp0.push_back(tmp);
1020 } // loop : d(j)
1021 queue_tmp0.sort(C_task_seq_complexity_greater);
1022 {
1023 string task_name = "w " + to_string(level_last);
1024
1025 // C_SPARSELOCALSCHUR is simple greedy estimated complexity by
1026 // assuming blocks are dense
1027 // C_SPARSELOCALSCHUR1 uses estimated complexity by C_SPARSENUMFACT
1028 copytask_list2seq(*queue_dynamic0,
1029 queue_tmp0,
1030 queue_null_,
1031 // queue_dummy_,
1032 task_name,
1033 C_SPARSELOCALSCHUR, // C_SPARSELOCALSCHUR1
1034 0, // shared by all threads
1035 TASK_PARALLEL,
1036 num_threads,
1037 level_last,
1038 1); // SparseLDLt : 0
1039 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1040 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1041 it != queue_tmp0.end(); ++it) {
1042 delete (*it);
1043 (*it) = NULL;
1044 }
1045 }
1046 for (int p = 0; p < num_threads; p++) {
1047 for(list<C_task_seq *>::const_iterator it = queue_dynamic0->begin();
1048 it != queue_dynamic0->end(); ++it) {
1049 _queue_static[p].push_back(*it);
1050 }
1051 }
1052 }
1053 // -- C_FILLMATRIX diagonal -
1054 // without using children
1055 queue_tmp0.clear();
1056 {
1057 // sparse subdomains : tasks_SparseNum[]
1058 // all dense subdomains : tasks_DFillSym[]
1059 // the begining of the dense subdomains
1060 const int begdom = 1U << (level_last - 1);
1061 const int enddom = begdom * 2;
1062
1063 for (int p = 0; p < num_threads; p++) {
1064 queue_lists[p].clear();
1065 }
1066 {
1067 string task_name = "v " + to_string(level_last) + " : ";
1068 queue_tmp0.clear();
1069 for (int d = begdom; d < enddom; d++) {
1070 const int j = btree->selfIndex(d);
1071 const int begin = 0; // better that all (diag/offdiag) in greedy
1072 // const int begin = tasks_DFillSym[j][0]->parallel_max;
1073 // -- C_FILLMATRIX offdiagonal --
1074 const int end = tasks_DFillSym[j].size();
1075 if ((end - begin) > 0) { // always true
1076 task_name += to_string(d) + " ";
1077 C_task_seq* tmp =
1078 new C_task_seq(C_FILLMATRIX,
1079 _null_name, // task_name_cstr,
1080 (-1), // mutex_id
1081 (-1), // TASK_PARALLEL,
1082 (-1), // num_threads,
1083 (-1), // level
1084 (-1), // phase
1085 &tasks_DFillSym[j],
1086 begin,
1087 end,
1088 0L // nops;
1089 );
1090 queue_tmp0.push_back(tmp);
1091 }
1092 } // loop : d(j)
1093 // -- C_FILLMATRIX diag/offdiagonal for grand fathers --
1094 for (int d = 1; d < begdom; d++) {
1095 const int j = btree->selfIndex(d);
1096 task_name += to_string(d) + " ";
1097 C_task_seq* tmp =
1098 new C_task_seq(C_FILLMATRIX,
1099 _null_name, // task_name_cstr,
1100 (-1), // mutex_id
1101 (-1), // TASK_PARALLEL,
1102 (-1), // num_threads,
1103 (-1), // level
1104 (-1), // phase
1105 &tasks_DFillSym[j],
1106 0,
1107 tasks_DFillSym[j].size(),
1108 0L // nops;
1109 );
1110 queue_tmp0.push_back(tmp);
1111 } // loop : d(j)
1112 if (queue_tmp0.size() > 0) { // only the last block
1113 copytask_list2seq(queue_dynamic[level_last],
1114 queue_tmp0,
1115 queue_null_,
1116 // queue_dummy_,
1117 task_name,
1118 C_FILLMATRIX, // C_FILLMATRIX1,
1119 0, // shared by all threads
1120 TASK_PARALLEL,
1121 num_threads,
1122 level_last,
1123 2);
1124
1125 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1126 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1127 it != queue_tmp0.end(); ++it) {
1128 delete (*it);
1129 (*it) = NULL;
1130 }
1131 }
1132 }
1133 }
1134 #endif
1135 {
1136 for (int p = 0; p < num_threads; p++) {
1137 for(list<C_task_seq *>::const_iterator it = queue_dynamic[level_last].begin();
1138 it != queue_dynamic[level_last].end(); ++it) {
1139 _queue_static[p].push_back(*it);
1140 }
1141 }
1142 }
1143 // for dense subdomains
1144 for (int level = (level_last - 1); level >=0; level--) {
1145 const int begdom = 1U << level;
1146 const int enddom = begdom * 2;
1147 const int num_leaves = 1 << (level + 1); // 1 << level
1148 if (level < (level_last - 1)) {
1149 // better management by mixed Assignment of blocks of DTRSM/DGEMM
1150 // -- DTRSM offdiagonal --
1151 {
1152 string task_name = "q offdiag " + to_string(level + 1) + " : ";
1153 queue_tmp0.clear();
1154 // off-diagonal parallel block between children and grandfather, ancenstors
1155 for (int d = begdom; d < enddom; d++) {
1156 const int j = btree->selfIndex(d);
1157
1158 for (int ic = 0; ic < 2; ic++) {
1159 const int jc = children[j][ic];
1160 const int end = tasks_DTRSMScale[jc].size();
1161 int begin = tasks_DTRSMScale[jc].size();
1162 if (!isDividedDTRSM[jc] && (end > 0) && !isMergedDTRSM[j]) {
1163 begin = IndexTask(tasks_DTRSMScale[jc],
1164 tasks_DTRSMScale[jc][0]->parallel_max);
1165 }
1166 if ((end - begin) > 0) {
1167 task_name += to_string(jc) + " ";
1168 C_task_seq* tmp =
1169 new C_task_seq(C_DTRSM,
1170 _null_name, // task_name_cstr,
1171 (-1), // mutex_id
1172 (-1), // TASK_PARALLEL,
1173 (-1), // num_threads,
1174 (-1), // level
1175 (-1), // phase
1176 &tasks_DTRSMScale[jc],
1177 begin,
1178 end,
1179 0L // nops;
1180 );
1181 queue_tmp0.push_back(tmp);
1182 } // if ((end - begin) > 0)
1183 } // loop : ic
1184 } // loop : j
1185 if (queue_tmp0.size() > 0) { // only the last block
1186 copytask_list2seq(queue_dynamic[level],
1187 queue_tmp0,
1188 queue_null_,
1189 // queue_dummy_,
1190 task_name,
1191 C_DTRSM1,
1192 0, // shared by all threads
1193 TASK_PARALLEL,
1194 num_threads,
1195 (level + 1),
1196 (level_last - 1 - level) * 6 + 1);
1197 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1198 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1199 it != queue_tmp0.end(); ++it) {
1200 delete (*it);
1201 (*it) = NULL;
1202 }
1203 }
1204 }
1205 // dependency
1206 // -- D_GEMM offdiagonal --
1207 {
1208 string task_name = "r " + to_string(level + 1) + " : ";
1209 queue_tmp0.clear();
1210 for (int d = begdom; d < enddom; d++) {
1211 const int j = btree->selfIndex(d);
1212 for (int ic = 0; ic < 2; ic++) {
1213 const int jc = children[j][ic];
1214 const int end = tasks_DGEMM[jc].size();
1215 if (end > 0) {
1216 int begin;
1217 const int itmp = tasks_DGEMM[jc][0]->parallel_max;
1218 if (!isMergedDTRSM[j]) {
1219 begin = itmp;
1220 }
1221 else {
1222 begin = ((itmp == end) ? end :
1223 (itmp + tasks_DGEMM[jc][itmp]->parallel_max));
1224 }
1225 if ((end - begin) > 0) {
1226 task_name += to_string(jc) + " ";
1227 C_task_seq* tmp =
1228 new C_task_seq(C_DGEMM,
1229 _null_name, // task_name_cstr,
1230 (-1), // mutex_id
1231 (-1), // TASK_PARALLEL,
1232 (-1), // num_threads,
1233 (-1), // (level + 1),
1234 (-1), // (level_last - 1 - level) * 5 + 2,
1235 &tasks_DGEMM[jc],
1236 begin,
1237 end,
1238 0L// nops);
1239 );
1240 queue_tmp0.push_back(tmp);
1241 }
1242 } // if (tasks_DGEMM[jc].size() > 0)
1243 } // loop : ic
1244 } // loop j
1245 if (queue_tmp0.size() > 0) { // only the last part
1246 copytask_list2seq(queue_dynamic[level],
1247 queue_tmp0,
1248 queue_null_,
1249 // queue_dummy_,
1250 task_name,
1251 C_DGEMM1,
1252 0, // shared by all threads
1253 TASK_PARALLEL,
1254 num_threads,
1255 (level + 1),
1256 (level_last - 1 - level) * 6 + 2);
1257 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1258 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1259 it != queue_tmp0.end(); ++it) {
1260 delete (*it);
1261 (*it) = NULL;
1262 }
1263 } // if (queue_tmp0.size() > 0)
1264 } // scope of task_name
1265 } // if (level < (level_last - 1))
1266 // -- DEALLACATE
1267 {
1268 string task_name = "X " + to_string(level + 1) + " : ";
1269 queue_tmp0.clear();
1270 C_task_seq* tmp =
1271 new C_task_seq(C_DEALLOCATE,
1272 _null_name,
1273 (-1), // mutex_id
1274 (-1), //TASK_PARALLEL,
1275 (-1),//num_threads,
1276 (-1),//(level + 1),
1277 (-1),//(level_last - 1 - level) * 5 + 3,
1278 &tasks_deallocLower[level + 1],
1279 0,
1280 tasks_deallocLower[level + 1].size(),
1281 0L// nops);
1282 );
1283 queue_tmp0.push_back(tmp);
1284 copytask_list2seq(queue_dynamic[level],
1285 queue_tmp0,
1286 queue_null_,
1287 // queue_dummy_,
1288 task_name,
1289 C_DEALLOCATE1,
1290 0, // shared by all threads
1291 TASK_PARALLEL,
1292 num_threads,
1293 (level + 1),
1294 (level_last - 1 - level) * 6 + 3);
1295 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1296 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1297 it != queue_tmp0.end(); ++it) {
1298 delete (*it);
1299 (*it) = NULL;
1300 }
1301 }
1302
1303 // -- DSUB offdiagonal --
1304 {
1305 string task_name = "s " + to_string(level + 1) + " : ";
1306 queue_tmp0.clear();
1307 for (int d = begdom; d < enddom; d++) {
1308 const int j = btree->selfIndex(d);
1309 if (!isMergedDTRSM[j]) {
1310 const int end = tasks_Dsub[level + 1][j].size();
1311 if (end > 0) { // to skip non allocated tasks_Dsub[level + 1][j][0]
1312 const int begin = tasks_Dsub[level + 1][j][0]->parallel_max;
1313 if ((end - begin) > 0) {
1314 task_name += to_string(j) + " ";
1315 C_task_seq* tmp =
1316 new C_task_seq(C_DSUB,
1317 _null_name,
1318 (-1), // mutex_id
1319 (-1), //TASK_PARALLEL,
1320 (-1),//num_threads,
1321 (-1),//(level + 1),
1322 (-1),//(level_last - 1 - level) * 5 + 3,
1323 &tasks_Dsub[level + 1][j],
1324 begin,
1325 end,
1326 0L// nops);
1327 );
1328 queue_tmp0.push_back(tmp);
1329 } // if ((end - begin) > 0)
1330 } // if (end > 0)
1331 } // if (!isMergedDTRSM[j])
1332 } // loop : d / j
1333 for (vector<int>::const_iterator it = all_fathersIndex[level].begin();
1334 it != all_fathersIndex[level].end(); ++it) {
1335 const int size = tasks_Dsub[level + 1][*it].size();
1336 if (size > 0) {
1337 task_name += to_string(*it) + " ";
1338 C_task_seq* tmp =
1339 new C_task_seq(C_DSUB,
1340 _null_name,
1341 (-1), // mutex_id
1342 (-1), //TASK_PARALLEL,
1343 (-1), //num_threads,
1344 (-1), //(level + 1),
1345 (-1), //(level_last - 1 - level) * 5 + 3,
1346 &tasks_Dsub[level + 1][*it],
1347 0,
1348 size,
1349 0L// nops);
1350 );
1351 queue_tmp0.push_back(tmp);
1352 }
1353 } // loop : it
1354 if (queue_tmp0.size() > 0) { // only the last part
1355 copytask_list2seq(queue_dynamic[level],
1356 queue_tmp0,
1357 queue_null_,
1358 // queue_dummy_,
1359 task_name,
1360 C_DSUB1,
1361 0, // shared by all threads
1362 TASK_PARALLEL,
1363 num_threads,
1364 (level + 1),
1365 (level_last - 1 - level) * 6 + 4);
1366 // erase temporary C_task_seq whose elements are copied to
1367 // queue_dynamic[]
1368 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1369 it != queue_tmp0.end(); ++it) {
1370 delete (*it);
1371 (*it) = NULL;
1372 }
1373 }
1374 }
1375 // -- DEALLACATE
1376 {
1377 string task_name = "x " + to_string(level + 1) + " : ";
1378 queue_tmp0.clear();
1379 const int begdom1 = 1U << (level + 1);
1380 const int enddom1 = begdom1 * 2;
1381 for (int d = begdom1; d < enddom1; d++) {
1382 const int j = btree->selfIndex(d);
1383 C_task_seq* tmp =
1384 new C_task_seq(C_DEALLOCATE,
1385 _null_name,
1386 (-1), // mutex_id
1387 (-1), //TASK_PARALLEL,
1388 (-1),//num_threads,
1389 (-1),//(level + 1),
1390 (-1),//(level_last - 1 - level) * 5 + 3,
1391 &tasks_deallocLocalSchur[j],
1392 0,
1393 tasks_deallocLocalSchur[j].size(),
1394 0L// nops);
1395 );
1396 queue_tmp0.push_back(tmp);
1397 }
1398 copytask_list2seq(queue_dynamic2[level],
1399 queue_tmp0,
1400 queue_null_,
1401 // queue_dummy_,
1402 task_name,
1403 C_DEALLOCATE1,
1404 0, // shared by all threads
1405 TASK_PARALLEL,
1406 num_threads,
1407 (level + 1),
1408 (level_last - 1 - level) * 6 + 5);
1409 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1410 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1411 it != queue_tmp0.end(); ++it) {
1412 delete (*it);
1413 (*it) = NULL;
1414 }
1415 }
1416
1417 // level == 0 <==> num_leaves = 2
1418 if (num_leaves <= num_threads) {
1419 // trick to merge DFullLDLt into previous stage of DTRSM to follow
1420 // the critical path
1421 long *nops_sum = new long[num_threads];
1422 for (int i = 0; i < num_threads; i++) {
1423 nops_sum[i] = 0L;
1424 }
1425 vector<int> starts(nb_doms_dense, 0);
1426 vector<int> starts_dtrsm(nb_doms_dense, 0);
1427 vector<int> starts_sub(nb_doms_dense, 0);
1428
1429 long nops_block_total = 0L;
1430 // -- STARTING BLOCK : DTSRM + DGEMM + DSUB + DFULLLDLT --
1431 list<vector<C_task *> *> diag_starting;
1432 list<string> task_name_strs;
1433 for (int p = 0; p < num_threads; p++) {
1434 queue_lists[p].clear();
1435 }
1436 for (int d = begdom; d < enddom; d++) {
1437 const int j = btree->selfIndex(d);
1438 #ifdef DEBUG_PREPARE_THREAD
1439 cout << "+ level = " << (level + 1) << " j = " << j << " children = "
1440 << children[j][0] << " " << children[j][1] << " : "
1441 << "# DFullLDLt @ " << level << " : " << j << " / "
1442 << tasks_DFullLDLt[j].size() << endl;
1443 #endif
1444 // 3 * 4 * 5 / 6 + 1 = 11
1445 // 3 * 4 * 5 / 6 + 2 * 3 * 4 / 6 + 3 = 17
1446 // if (tasks_DFullLDLt[j].size() > 4) { // with parallelizing
1447 if(nrow_DFullLDLt[j] > 2) {
1448 vector<C_task *> *tmp = new vector<C_task *>;
1449 tmp->reserve(4 + 2 * (_isSym ? 3 : 6)); // 3 = 2 + 1
1450 for (int ic = 0; ic < 2; ic++) {
1451 const int jj = children[j][ic];
1452 if ((nrow_DFullLDLt[jj] <= 2) && !isMergedDTRSM[jj]) {
1453 // the case DFullLDLt and DTRSMScale are concatenated can be skipped
1454 const int itmp = tasks_DTRSMScale[jj][0]->atomic_size;
1455 for (int k = 0; k < itmp; k++) {
1456 tmp->push_back(tasks_DTRSMScale[jj][k]);
1457 }
1458 if (_isSym) {
1459 starts_dtrsm[jj] = tasks_DTRSMScale[jj][0]->atomic_size;
1460 }
1461 else {
1462 for (int k = 0; k < tasks_DTRSMScale[jj][itmp]->atomic_size;
1463 k++) {
1464 tmp->push_back(tasks_DTRSMScale[jj][itmp + k]);
1465 }
1466 starts_dtrsm[jj] = (itmp +
1467 tasks_DTRSMScale[jj][itmp]->atomic_size);
1468 } // if (_isSym)
1469 } // if ((nrow_DFullLDLt[jj] <= 2) && !isMergedDTRSM[jj])
1470 tmp->push_back(tasks_DGEMM[jj][0]);
1471 starts[jj] = 1;
1472 } // loop : ic
1473 tmp->push_back(tasks_Dsub[level + 1][j][0]); // null for many cases
1474 tmp->push_back(tasks_DFullLDLt[j][0]);
1475 diag_starting.push_back(tmp);
1476
1477 string task_name = "p " + to_string(level + 1) + " " + to_string(j);
1478 task_name_strs.push_back(task_name);
1479 starts_sub[j] = 1;
1480 } // if(nrow_DFullLDLt[j] > 2)
1481 } // loop : d
1482 list<string>::const_iterator kt = task_name_strs.begin();
1483 {
1484 int itmp = 0;
1485 for (list<vector<C_task *> *>::const_iterator it = diag_starting.begin();
1486 it != diag_starting.end(); ++it, ++kt, itmp++){
1487 long nops = 0L;
1488 for (vector<C_task *>::const_iterator jt = (*it)->begin();
1489 jt != (*it)->end(); ++jt) {
1490 nops += *((*jt)->ops_complexity);
1491 }
1492 C_task_seq* tmp =
1493 new C_task_seq(C_DIAG_START,
1494 (*kt),
1495 TASK_SINGLE,
1496 (-1), // mutex_id
1497 1,
1498 (level + 1),
1499 (level_last - 1 - level) * 6 + 1,
1500 (*it),
1501 0,
1502 (*it)->size(),
1503 nops);
1504 queue_lists[itmp % num_threads].push_back(tmp);
1505 nops_sum[itmp % num_threads] = nops;
1506 nops_block_total += nops;
1507 #ifdef DEBUG_PREPARE_THREAD
1508 cout << "ll = " << itmp % num_threads
1509 << " critical path " << *kt << " nops = " << nops << endl;
1510 #endif
1511 } // loop : it, kt, itmp
1512 } // scope of itmp
1513 // -- DTRSM -- diangonal
1514 task_assign_diag1(_queue_static,
1515 tasks_DTRSMScale,
1516 queue_null_,
1517 // queue_dummy_,
1518 nrow_DFullLDLt,
1519 isMergedDTRSM,
1520 "q",
1521 C_DTRSM,
1522 1, // int level_id,
1523 num_threads,
1524 level_last,
1525 level,
1526 begdom,
1527 enddom,
1528 nops_sum,
1529 starts_dtrsm,
1530 queue_lists,
1531 false,
1532 btree,
1533 children);
1534 // erase STL container defined in line 1499
1535 for (list<vector<C_task *> *>::iterator it = diag_starting.begin();
1536 it != diag_starting.end(); ++it) {
1537 delete (*it);
1538 (*it) = NULL;
1539 }
1540 { // begin : scope queue_tmp2
1541 list<C_task_seq *> queue_tmp2;
1542 queue_tmp2.clear();
1543 for (int d = begdom; d < enddom; d++) {
1544 const int j = btree->selfIndex(d);
1545 for (int ic = 0; ic < 2; ic++) {
1546 const int jc = children[j][ic];
1547 long nops = 0L;
1548 if (isDividedDTRSM[jc]) {
1549 const int end = tasks_DTRSMScale[jc].size();
1550 for (int i = 0; i < end; i++) {
1551 nops += *(tasks_DTRSMScale[jc][i]->ops_complexity);
1552 }
1553 C_task_seq* tmp =
1554 new C_task_seq(C_DTRSM,
1555 _null_name,
1556 (-1), // mutex_id
1557 (-1), // TASK_SINGLE,
1558 (-1), // 1,
1559 (-1), // (level + 1),
1560 (-1), // (level_last - 1 - level) * 5 + 1,
1561 &tasks_DTRSMScale[jc],
1562 0,
1563 end,
1564 nops);
1565 queue_tmp2.push_back(tmp);
1566 } // if (isDividedDTRSM[jc])
1567 } // loop : ic
1568 } // loop : d
1569 { // begin : scope task_name
1570 string task_name = "q Offdiag " + to_string(level + 1);
1571 if (queue_tmp2.size() > 0) { // only the last block
1572 copytask_list2seq(queue_dynamic1[level],
1573 queue_tmp2,
1574 queue_null_,
1575 // queue_dummy_,
1576 task_name,
1577 C_DTRSM,
1578 0, // shared by all threads
1579 TASK_PARALLEL,
1580 num_threads,
1581 (level + 1),
1582 (level_last - 1 - level) * 6 + 1);
1583 for (list<C_task_seq*>::iterator it = queue_tmp2.begin();
1584 it != queue_tmp2.end(); ++it) {
1585 delete (*it);
1586 (*it) = NULL;
1587 } // loop : it
1588 } // if (queue_tmp2.size() > 0)
1589 } // end : scope task_name
1590 } // end : scope queue_tmp2
1591 if (level >= 0) {
1592 for (int p = 0; p < num_threads; p++) {
1593 for(list<C_task_seq *>::const_iterator it = queue_dynamic1[level].begin();
1594 it != queue_dynamic1[level].end(); ++it) {
1595 _queue_static[p].push_back(*it);
1596 }
1597 } // loop : p
1598 // the case queue_dynamic consists of only C_task_seq == 'x', copied here
1599 for (int p = 0; p < num_threads; p++) {
1600 for(list<C_task_seq *>::const_iterator it = queue_dynamic2[level + 1].begin();
1601 it != queue_dynamic2[level + 1].end(); ++it) {
1602 _queue_static[p].push_back(*it);
1603 }
1604 } // loop : p
1605 }
1606
1607 // -- DGEMM -- diagonal
1608 vector<int> null_idx;
1609 task_assign_diag1(_queue_static,
1610 tasks_DGEMM,
1611 queue_null_,
1612 // queue_dummy_,
1613 null_idx, // not used
1614 isMergedDTRSM,
1615 "r",
1616 C_DGEMM,
1617 2, // int level_id,
1618 num_threads,
1619 level_last,
1620 level,
1621 begdom,
1622 enddom,
1623 nops_sum,
1624 starts,
1625 queue_lists,
1626 true,
1627 btree,
1628 children);
1629
1630 // -- DSUB -- diagonal
1631 task_assign_diag2(_queue_static,
1632 tasks_Dsub[level + 1],
1633 queue_null_,
1634 // queue_dummy_,
1635 isMergedDTRSM,
1636 //tasks_DFullLDLt,
1637 "s",
1638 C_DSUB,
1639 3, // int level_id,
1640 num_threads,
1641 level_last,
1642 level,
1643 begdom,
1644 enddom,
1645 nops_sum,
1646 starts,
1647 starts_sub,
1648 queue_lists,
1649 true,
1650 btree,
1651 children);
1652
1653 if (level == 0) {
1654 // the case queue_dynamic consists of only C_task_seq == 'x', copied here
1655 for (int p = 0; p < num_threads; p++) {
1656 for(list<C_task_seq *>::const_iterator it = queue_dynamic2[level].begin();
1657 it != queue_dynamic2[level].end(); ++it) {
1658 _queue_static[p].push_back(*it);
1659 }
1660 } // loop : p
1661 }
1662 // -- C_DFULL -- diagonal
1663 queue_tmp0.clear();
1664 queue_tmp1.clear();
1665 for (int p = 0; p < num_threads; p++) {
1666 queue_lists[p].clear();
1667 }
1668 for (int d = begdom; d < enddom; d++) {
1669 const int j = btree->selfIndex(d);
1670 long nops = 0L;
1671 for (int i = starts_sub[j]; i < tasks_DFullLDLt[j].size(); i++) {
1672 nops += *(tasks_DFullLDLt[j][i]->ops_complexity);
1673 }
1674 string task_name = "t& " + to_string(level) + " : " + to_string(j);
1675 C_task_seq* tmp = new C_task_seq(C_DFULL,
1676 task_name,
1677 0, // mutex_id
1678 TASK_SINGLE,
1679 1,
1680 level,
1681 (level_last - level) * 6,
1682 &tasks_DFullLDLt[j],
1683 starts_sub[j],
1684 tasks_DFullLDLt[j].size(),
1685 nops);
1686 if (starts_sub[j] > 0) {
1687 queue_tmp0.push_back(tmp);
1688 }
1689 else {
1690 queue_tmp1.push_back(tmp);
1691 }
1692 }
1693 const int size_task0 = queue_tmp0.size();
1694 const int size_threads = num_threads - queue_tmp1.size();
1695 #ifdef DEBUG_PREPARE_THREAD
1696 cout << "*** C_DFULL : parallel = " << size_task0 << " : serial "
1697 << queue_tmp1.size() << " / ";
1698 #endif
1699 if (size_task0 > 0 && size_threads > 0) {
1700 queue_tmp0.sort(C_task_seq_complexity_greater);
1701 int mm0 = size_threads % size_task0;
1702 const int mm = (size_threads / size_task0) + (mm0 != 0);
1703 if (mm0 == 0) {
1704 mm0 = size_task0;
1705 }
1706 int jj = 0;
1707 for (list<C_task_seq *>::const_iterator it = queue_tmp0.begin();
1708 it != queue_tmp0.end(); ++it, jj++) {
1709
1710 const int multplcty = (jj < mm0) ? mm : (mm - 1);
1711 #ifdef DEBUG_PREPARE_THREAD
1712 cout << (*it)->task_id << " : " << (*it)->task_name
1713 << " : < " << multplcty << " > ";
1714 #endif
1715 const int parallel_single =
1716 (multplcty == 1) ? TASK_SINGLE : TASK_PARALLEL;
1717 // copy raw task into a task sequence whose length is one
1718 list<C_task_seq *> queue_tmp2, queue_tmp3;
1719 queue_tmp2.push_back(*it);
1720 copytask_list2seq(queue_tmp3,
1721 queue_tmp2,
1722 queue_null_,
1723 // queue_dummy_,
1724 (*it)->task_name,
1725 (*it)->task_id,
1726 jj,
1727 parallel_single,
1728 multplcty,
1729 (*it)->level,
1730 (*it)->phase);
1731 // threads share one task (*it)
1732 for (int m = 0; m < mm; m++) {
1733 const int n = jj + m * size_task0;
1734 if (n < size_threads) {
1735 _queue_static[n % num_threads].push_back(queue_tmp3.front());
1736 // _queue_static[n % num_threads].push_back(seq_tmp);
1737 #ifdef DEBUG_PREPARE_THREAD
1738 cout << "[ " << jj << " @ " << n << " : "
1739 << n % num_threads << " ]";
1740 #endif
1741 }
1742 }
1743 } // loop : j
1744 #ifdef DEBUG_PREPARE_THREAD
1745 cout << "/ ";
1746 #endif
1747 jj = size_threads;
1748 for (list<C_task_seq *>::const_iterator it = queue_tmp1.begin();
1749 it != queue_tmp1.end(); ++it, jj++) {
1750 // copy for each thread
1751 list<C_task_seq *> queue_tmp2, queue_tmp3;
1752 queue_tmp2.push_back(*it);
1753 copytask_list2seq(queue_tmp3,
1754 queue_tmp2,
1755 queue_null_,
1756 // queue_dummy_,
1757 (*it)->task_name,
1758 (*it)->task_id,
1759 0,
1760 TASK_SINGLE,
1761 1,
1762 (*it)->level,
1763 (*it)->phase);
1764
1765 _queue_static[jj % num_threads].push_back(queue_tmp3.front());
1766 #ifdef DEBUG_PREPARE_THREAD
1767 cout << jj << " ; " << jj % num_threads << " / ";
1768 #endif
1769 }
1770 #ifdef DEBUG_PREPARE_THREAD
1771 cout << endl;
1772 #endif
1773 // delete original C_task_seq after copying to all threads
1774 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1775 it != queue_tmp0.end(); ++it) {
1776 delete (*it);
1777 (*it) = NULL;
1778 }
1779 for (list<C_task_seq*>::iterator it = queue_tmp1.begin();
1780 it != queue_tmp1.end(); ++it) {
1781 delete (*it);
1782 (*it) = NULL;
1783 }
1784 } // if (size_task0 > 0)
1785 else { // (size_task0 == 0) || (size_threads <= 0)
1786 #ifdef DEBUG_PREPARE_THREAD
1787 cout << endl;
1788 #endif
1789 {
1790 int itmp = 0;
1791 queue_tmp1.sort(C_task_seq_complexity_greater);
1792 for (list<C_task_seq*>::const_iterator it = queue_tmp1.begin();
1793 it != queue_tmp1.end(); ++it, itmp++) {
1794 (*it)->parallel_single = TASK_SINGLE;
1795 queue_lists[itmp % num_threads].push_back(*it);
1796 } // loop : it, itmp
1797 }
1798 {
1799 string task_name = "t " + to_string(level);
1800 for (int p = 0; p < num_threads; p++) {
1801 copytask_list2seq(_queue_static[p],
1802 queue_lists[p],
1803 queue_null_,
1804 // queue_dummy_,
1805 task_name,
1806 C_DFULL,
1807 p,
1808 TASK_SINGLE,
1809 1,
1810 level,
1811 (level_last - level) * 6);
1812 } // loop : p
1813 // (queue_tmp0.size() == 0) ? for safty of non-memory-leak
1814 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1815 it != queue_tmp0.end(); ++it) {
1816 delete (*it);
1817 (*it) = NULL;
1818 }
1819 for (list<C_task_seq*>::iterator it = queue_tmp1.begin();
1820 it != queue_tmp1.end(); ++it) {
1821 delete (*it);
1822 (*it) = NULL;
1823 }
1824 }
1825 } // if (size_task > 0)
1826 if (level > 0) {
1827 for (int p = 0; p < num_threads; p++) {
1828 for(list<C_task_seq *>::const_iterator it = queue_dynamic[level].begin();
1829 it != queue_dynamic[level].end(); ++it) {
1830 _queue_static[p].push_back(*it);
1831 }
1832 }
1833 }
1834 delete [] nops_sum;
1835 } //
1836 else { // if (num_leaves <= num_threads)
1837 if (level < (level_last - 1)) {
1838 // -- DTRSM -- diagonal
1839 queue_tmp0.clear();
1840 for (int p = 0; p < num_threads; p++) {
1841 queue_lists[p].clear();
1842 }
1843 list<C_task_seq *> queue_tmp2;
1844 queue_tmp2.clear();
1845 for (int d = begdom; d < enddom; d++) {
1846 const int j = btree->selfIndex(d);
1847 #ifdef DEBUG_PREPARE_THREAD
1848 cout << "* level = " << (level + 1) << " j = " << j << " children = "
1849 << children[j][0] << " " << children[j][1] << " " << endl;
1850 #endif
1851 for (int ic = 0; ic < 2; ic++) {
1852 const int jc = children[j][ic];
1853 if (tasks_DTRSMScale[jc].size() > 0) {
1854 long nops = 0L;
1855 if (isDividedDTRSM[jc]) {
1856 const int end = tasks_DTRSMScale[jc].size();
1857 for (int i = 0; i < end; i++) {
1858 nops += *(tasks_DTRSMScale[jc][i]->ops_complexity);
1859 }
1860 C_task_seq* tmp =
1861 new C_task_seq(C_DTRSM,
1862 _null_name,
1863 (-1), // mutex_id
1864 (-1), // TASK_SINGLE,
1865 (-1), // 1,
1866 (-1), // (level + 1),
1867 (-1), // (level_last - 1 - level) * 5 + 1,
1868 &tasks_DTRSMScale[jc],
1869 0,
1870 end,
1871 nops);
1872 queue_tmp2.push_back(tmp);
1873 } // if (isDividedDTRSM[jc])
1874 else {
1875 int end;
1876 if (!isMergedDTRSM[j]) { // looking the father node
1877 end = IndexTask(tasks_DTRSMScale[jc],
1878 tasks_DTRSMScale[jc][0]->parallel_max);
1879 }
1880 else {
1881 end = tasks_DTRSMScale[jc].size();
1882 }
1883 for (int i = 0; i < end; i++) {
1884 nops += *(tasks_DTRSMScale[jc][i]->ops_complexity);
1885 }
1886 C_task_seq* tmp =
1887 new C_task_seq(C_DTRSM,
1888 _null_name,
1889 (-1), // mutex_id
1890 (-1), // TASK_SINGLE,
1891 (-1), // 1,
1892 (-1), // (level + 1),
1893 (-1), // (level_last - 1 - level) * 5 + 1,
1894 &tasks_DTRSMScale[jc],
1895 0,
1896 end,
1897 nops);
1898 queue_tmp0.push_back(tmp);
1899 } // if (isDividedDTRSM[jc])
1900 } // if (tasks_DTRSMScale[jc].size() > 0)
1901 } // loop : ic
1902 } // loop : d
1903 queue_tmp0.sort(C_task_seq_complexity_smaller);
1904 { // begin : scope itmp
1905 int itmp = 0;
1906 for (list<C_task_seq*>::const_iterator it = queue_tmp0.begin();
1907 it != queue_tmp0.end(); ++it, itmp++) {
1908 queue_lists[itmp % num_threads].push_back(*it);
1909 } // loop : it
1910 } // end : scope itmp
1911 { // begin : scope task_name
1912 string task_name = "q diag " + to_string(level + 1);
1913 for (int p = 0; p < num_threads; p++) {
1914 copytask_list2seq(_queue_static[p],
1915 queue_lists[p],
1916 queue_null_,
1917 // queue_dummy_,
1918 task_name,
1919 C_DTRSM,
1920 p,
1921 TASK_SINGLE,
1922 1,
1923 (level + 1),
1924 (level_last - 1 - level) * 6 + 1);
1925 }
1926 // erase temporary C_task_seq whose elements are copied to
1927 // queue_static[]
1928 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
1929 it != queue_tmp0.end(); ++it) {
1930 delete (*it);
1931 (*it) = NULL;
1932 }
1933 } // end : scope task_name
1934 { // begin : scope task_name
1935 string task_name = "q Offdiag " + to_string(level + 1);
1936 if (queue_tmp2.size() > 0) { // only the last block
1937 copytask_list2seq(queue_dynamic1[level],
1938 queue_tmp2,
1939 queue_null_,
1940 // queue_dummy_,
1941 task_name,
1942 C_DTRSM,
1943 0, // shared by all threads
1944 TASK_PARALLEL,
1945 num_threads,
1946 (level + 1),
1947 (level_last - 1 - level) * 6 + 1);
1948 // erase temporary C_task_seq whose elements are copied to queue_dynamic[]
1949 for (list<C_task_seq*>::iterator it = queue_tmp2.begin();
1950 it != queue_tmp2.end(); ++it) {
1951 delete (*it);
1952 (*it) = NULL;
1953 }
1954 } // if (queue_tmp2.size() > 0)
1955 } // end : scope task_name
1956 if (level >= 0) {
1957 for (int p = 0; p < num_threads; p++) {
1958 for(list<C_task_seq *>::const_iterator it = queue_dynamic1[level].begin();
1959 it != queue_dynamic1[level].end(); ++it) {
1960 _queue_static[p].push_back(*it);
1961 }
1962 } // loop : p
1963 // C_task_seq == 'x', copied here
1964 for (int p = 0; p < num_threads; p++) {
1965 for(list<C_task_seq *>::const_iterator it = queue_dynamic2[level + 1].begin();
1966 it != queue_dynamic2[level + 1].end(); ++it) {
1967 _queue_static[p].push_back(*it);
1968 }
1969 } // loop : p
1970 } // if (level >= 0)
1971 // -- DGEMM -- diagonal
1972 queue_tmp0.clear();
1973 for (int p = 0; p < num_threads; p++) {
1974 queue_lists[p].clear();
1975 }
1976 for (int d = begdom; d < enddom; d++) {
1977 const int j = btree->selfIndex(d);
1978 for (int ic = 0; ic < 2; ic++) {
1979 const int jc = children[j][ic];
1980 const int tasks_size = tasks_DGEMM[jc].size();
1981 if (tasks_size > 0) {
1982 long nops = 0L;
1983 int end;
1984 int itmp = tasks_DGEMM[jc][0]->parallel_max;
1985 // if (itmp <= (_isSym ? 3 : 4)) {
1986 #if 1
1987 if (!isMergedDTRSM[j]) {
1988 end = itmp;
1989 }
1990 else {
1991 end = ((itmp == tasks_size) ? tasks_size :
1992 itmp + tasks_DGEMM[jc][itmp]->parallel_max);
1993 }
1994 #else
1995 end = ((itmp == tasks_size) ? tasks_size :
1996 itmp + tasks_DGEMM[jc][itmp]->parallel_max);
1997 #endif
1998 for (int i = 0; i < end; i++) {
1999 nops += *(tasks_DGEMM[jc][i]->ops_complexity);
2000 }
2001 C_task_seq* tmp =
2002 new C_task_seq(C_DGEMM,
2003 _null_name,
2004 (-1), // mutex_id
2005 (-1), // TASK_SINGLE,
2006 (-1), //1,
2007 (-1), //(level + 1),
2008 (-1), //(level_last - 1 - level) * 5 + 2,
2009 &tasks_DGEMM[jc],
2010 0,
2011 end,
2012 nops);
2013 queue_tmp0.push_back(tmp);
2014 } // if (tasks_DGEMM[jc].size() > 0)
2015 } // loop : ic
2016 } // loop : d
2017 queue_tmp0.sort(C_task_seq_complexity_greater);
2018 {
2019 int itmp = 0;
2020 for (list<C_task_seq*>::const_iterator it = queue_tmp0.begin();
2021 it != queue_tmp0.end(); ++it, itmp++) {
2022 queue_lists[itmp % num_threads].push_back(*it);
2023 } // loop : it
2024 }
2025 {
2026 string task_name = "r " + to_string(level + 1);
2027 for (int p = 0; p < num_threads; p++) {
2028 copytask_list2seq(_queue_static[p],
2029 queue_lists[p],
2030 queue_null_,
2031 // queue_dummy_,
2032 task_name,
2033 C_DGEMM,
2034 p,
2035 TASK_SINGLE,
2036 1,
2037 (level + 1),
2038 (level_last - 1 - level) * 6 + 2);
2039 }
2040 // erase temporary C_task_seq whose elements are copied to
2041 // queue_static[]
2042 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
2043 it != queue_tmp0.end(); ++it) {
2044 delete (*it);
2045 (*it) = NULL;
2046 }
2047 }
2048 } // if (level == (level_last - 1))
2049 // -- DSUB -- diagonal
2050 queue_tmp0.clear();
2051 for (int p = 0; p < num_threads; p++) {
2052 queue_lists[p].clear();
2053 }
2054 for (int d = begdom; d < enddom; d++) {
2055 const int j = btree->selfIndex(d);
2056 long nops = 0L;
2057 if (tasks_Dsub[level + 1][j].size() > 0) {
2058 int end;
2059 // if (tasks_DFullLDLt[j].size() <= 4) {
2060 // if(nrow_DFullLDLt[j] <= 2) {
2061 if (!isMergedDTRSM[j]) {
2062 end = tasks_Dsub[level + 1][j][0]->parallel_max;
2063 }
2064 else {
2065 end = tasks_Dsub[level + 1][j].size();
2066 }
2067 for (int i = 0; i < end; i++) {
2068 nops += *(tasks_Dsub[level + 1][j][i]->ops_complexity);
2069 }
2070 C_task_seq* tmp =
2071 new C_task_seq(C_DSUB,
2072 _null_name,
2073 (-1), // mutex_id
2074 (-1), // TASK_SINGLE,
2075 (-1), //1,
2076 (-1), //(level + 1),
2077 (-1), //(level_last - 1 - level) * 5 + 3,
2078 &tasks_Dsub[level + 1][j],
2079 0,
2080 end,
2081 // tasks_Dsub[level + 1][j][0]->parallel_max,
2082 nops);
2083 queue_tmp0.push_back(tmp);
2084 }
2085 } // loop : d
2086 queue_tmp0.sort(C_task_seq_complexity_greater);
2087 {
2088 int itmp = 0;
2089 for (list<C_task_seq*>::const_iterator it = queue_tmp0.begin();
2090 it != queue_tmp0.end(); ++it, itmp++) {
2091 queue_lists[itmp % num_threads].push_back(*it);
2092 } // loop : it
2093 }
2094 { // begin : scope for task_name;
2095 string task_name = "s " + to_string(level + 1);
2096 for (int p = 0; p < num_threads; p++) {
2097 copytask_list2seq(_queue_static[p],
2098 queue_lists[p],
2099 queue_null_,
2100 // queue_dummy_,
2101 task_name,
2102 C_DSUB,
2103 p,
2104 TASK_SINGLE,
2105 1,
2106 (level + 1),
2107 (level_last - 1 - level) * 6 + 3);
2108 }
2109 // erase temporary C_task_seq whose elements are copied to
2110 // queue_static[]
2111 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
2112 it != queue_tmp0.end(); ++it) {
2113 delete (*it);
2114 (*it) = NULL;
2115 }
2116 } // end : scope for task_name;
2117 if (level == 0) {
2118 // the case queue_dynamic consists of only C_task_seq == 'x', copied here
2119 for (int p = 0; p < num_threads; p++) {
2120 for(list<C_task_seq *>::const_iterator it = queue_dynamic2[level].begin();
2121 it != queue_dynamic2[level].end(); ++it) {
2122 _queue_static[p].push_back(*it);
2123 }
2124 } // loop : p
2125 }
2126 // -- C_DFULL --
2127 queue_tmp0.clear();
2128 for (int p = 0; p < num_threads; p++) {
2129 queue_lists[p].clear();
2130 }
2131 for (int d = begdom; d < enddom; d++) {
2132 const int j = btree->selfIndex(d);
2133 long nops = 0L;
2134 for (int i = 0; i < tasks_DFullLDLt[j].size(); i++) {
2135 nops += *(tasks_DFullLDLt[j][i]->ops_complexity);
2136 }
2137 string task_name = "t " + to_string(level) + " : " + to_string(j);
2138 C_task_seq* tmp = new C_task_seq(C_DFULL,
2139 task_name,
2140 (-1), // mutex_id
2141 TASK_SINGLE,
2142 1,
2143 level,
2144 (level_last - level) * 6,
2145 &tasks_DFullLDLt[j],
2146 0,
2147 tasks_DFullLDLt[j].size(),
2148 nops);
2149 queue_tmp0.push_back(tmp);
2150 } // loop : d
2151 queue_tmp0.sort(C_task_seq_complexity_greater);
2152 {
2153 int itmp = 0;
2154 for (list<C_task_seq*>::const_iterator it = queue_tmp0.begin();
2155 it != queue_tmp0.end(); ++it, itmp++) {
2156 queue_lists[itmp % num_threads].push_back(*it);
2157 } // loop : it
2158 }
2159 // begin : scope for task_name;
2160 {
2161 string task_name = "t " + to_string(level);
2162 for (int p = 0; p < num_threads; p++) {
2163 copytask_list2seq(_queue_static[p],
2164 queue_lists[p],
2165 queue_null_,
2166 // queue_dummy_,
2167 task_name,
2168 C_DFULL,
2169 p,
2170 TASK_SINGLE,
2171 1,
2172 level,
2173 (level_last - level) * 6);
2174 }
2175 // erase temporary C_task_seq whose elements are copied to
2176 // queue_static[]
2177 for (list<C_task_seq*>::iterator it = queue_tmp0.begin();
2178 it != queue_tmp0.end(); ++it) {
2179 delete (*it);
2180 (*it) = NULL;
2181 }
2182 } // end : scope for task_name
2183 if ((level > 0)) { // && (level < (level_last - 1))) {
2184 for (int p = 0; p < num_threads; p++) {
2185 for(list<C_task_seq *>::const_iterator it = queue_dynamic[level].begin();
2186 it != queue_dynamic[level].end(); ++it) {
2187 _queue_static[p].push_back(*it);
2188 }
2189 } // loop : p
2190 }
2191 // dependency
2192 } // if (num_leaves < num_threads)
2193 } // loop : level
2194 // begin : counting task size
2195 {
2196 for (int p = 0; p < num_threads; p++) {
2197 #ifdef DEBUG_PREPARE_THREAD
2198 cout << "thread = " << p << " @ " << _queue_static[p].size() << " / ";
2199 #endif
2200 for (list<C_task_seq*>::const_iterator it = _queue_static[p].begin();
2201 it != _queue_static[p].end(); ++it) {
2202 if ((*it)->parallel_single == TASK_SINGLE) {
2203 #ifdef DEBUG_PREPARE_THREAD
2204 cout << (*it)->task_name << " [ "
2205 << (*it)->begin << " : " << (*it)->end << " ] ; "
2206 << (*it)->ops_complexity << " / ";
2207 #endif
2208 nops_queue[p][(*it)->level] += (*it)->ops_complexity;
2209 }
2210 if ((*it)->parallel_single == TASK_PARALLEL) {
2211 #ifdef DEBUG_PREPARE_THREAD
2212 cout << (*it)->task_name << " [[ "
2213 << (*it)->begin << " : " << (*it)->end << " ]] ; "
2214 << (*it)->ops_complexity << " / ";
2215 #endif
2216 if (((*it)->num_threads > 0) && ((*it)->task_id == C_DFULL)) {
2217 // cout << "mutex_id = " << (*it)->mutex_id;
2218 nops_queue[p][(*it)->level] +=
2219 (*it)->ops_complexity / (long)(*it)->num_threads;
2220 }
2221 if ((*it)->level == 1) {
2222 nops_queue[num_threads][(*it)->level] += (*it)->ops_complexity;
2223 }
2224 }
2225 }
2226
2227 #ifdef DEBUG_PREPARE_THREAD
2228 cout << endl;
2229 #endif
2230 }
2231 #ifdef DEBUG_PREPARE_THREAD
2232 cout << "shared / ";
2233 #endif
2234 for (int level = level_last; level >=0; level--) {
2235 #ifdef DEBUG_PREPARE_THREAD
2236 cout << "level = " << level << endl;
2237 #endif
2238 for (list<C_task_seq*>::const_iterator it = queue_dynamic[level].begin();
2239 it != queue_dynamic[level].end(); ++it) {
2240 #ifdef DEBUG_PREPARE_THREAD
2241 cout << (*it)->task_name << " [ "
2242 << (*it)->begin << " : " << (*it)->end << " ] ; "
2243 << (*it)->ops_complexity << " / ";
2244 #endif
2245 nops_queue[num_threads][(*it)->level] += (*it)->ops_complexity;
2246 }
2247 #ifdef DEBUG_PREPARE_THREAD
2248 cout << endl;
2249 #endif
2250 }
2251 #ifdef DEBUG_PREPARE_THREAD
2252 for (int level = (level_last + 1); level >= 0; level--) {
2253 cout << "level = " << level << " : ";
2254 for (int j = 0; j <= num_threads; j++) {
2255 cout << nops_queue[j][level] << " ";
2256 }
2257 cout << endl;
2258 }
2259 #endif
2260 }
2261 // end : counting task size
2262 // copy tasks in reverse order
2263 {
2264 int itmp = 0;
2265 for (int i = 0; i <= level_last; i++) {
2266 itmp += queue_dynamic[i].size();
2267 itmp += queue_dynamic1[i].size();
2268 itmp += queue_dynamic2[i].size(); // C_DEALLOCATE
2269 // itmp += queue_dynamic3[i].size(); // C_DEALLOCATE
2270 }
2271 _queue_dynamic->reserve(itmp);
2272 }
2273 for (int i = 0; i <= level_last; i++) {
2274 const int level = level_last - i;
2275 for (list<C_task_seq*>::const_iterator it = queue_dynamic[level].begin();
2276 it != queue_dynamic[level].end(); ++it) {
2277 _queue_dynamic->push_back(*it);
2278 }
2279 for (list<C_task_seq*>::const_iterator it = queue_dynamic1[level].begin();
2280 it != queue_dynamic1[level].end(); ++it) {
2281 _queue_dynamic->push_back(*it);
2282 }
2283 for (list<C_task_seq*>::const_iterator it = queue_dynamic2[level].begin();
2284 it != queue_dynamic2[level].end(); ++it) {
2285 _queue_dynamic->push_back(*it);
2286 }
2287 }
2288 // begin : scope for fout
2289 if (false) {
2290 char fname[256];
2291 int pid = get_process_id();
2292 sprintf(fname, "tasks-created.%d.data", pid);
2293 FILE *fp;
2294 if ((fp = fopen(fname, "a")) != NULL) {
2295 write_dependency(fp);
2296 }
2297 else {
2298 fprintf(stderr,
2299 "%s %d : fail to open %s\n",
2300 __FILE__, __LINE__, fname);
2301 exit(-1);
2302 }
2303 }
2304 queue_dynamic0->clear();
2305 for (int i = 0; i < (level_last + 1); i++) {
2306 queue_dynamic[i].clear();
2307 queue_dynamic1[i].clear();
2308 queue_dynamic2[i].clear();
2309 // queue_dynamic3[i].clear();
2310 }
2311 delete [] queue_dynamic;
2312 delete [] queue_dynamic1;
2313 delete [] queue_dynamic2;
2314 // delete [] queue_dynamic3;
2315 delete queue_dynamic0;
2316 for (int i = 0; i < num_threads; i++) {
2317 queue_lists[i].clear();
2318 }
2319 delete [] queue_lists;
2320 }
2321
2322 void QueueRuntime::write_dependency(FILE *fp)
2323 {
2324 for (int p = 0; p < _num_threads; p++) {
2325 fprintf(fp, "*** thread = %d @ %d ***\n",
2326 p, (int)_queue_static[p].size());
2327 for (list<C_task_seq*>::const_iterator it = _queue_static[p].begin();
2328 it != _queue_static[p].end(); ++it) {
2329 fprintf(fp, "** %d C_task_seq = %d %s %s **\n",
2330 p, (*it)->task_id, (*it)->task_name,
2331 (((*it)->parallel_single == TASK_SINGLE) ? " single " : " shared "));
2332 for (int j = (*it)->begin; j < (*it)->end; j++) {
2333 fprintf(fp, "%s : ", (*(*it)->queue)[j]->task_name);
2334 if ((*(*it)->queue)[j]->atomic_size > 1) {
2335 fprintf(fp, "atomic %d / %d ",
2336 (*(*it)->queue)[j]->atomic_id,
2337 (*(*it)->queue)[j]->atomic_size);
2338 }
2339 // list<C_task *>& parents = *(*(*it)->queue)[j]->parents_work;
2340 list<C_task *>& parents = *(*(*it)->queue)[j]->parents;
2341 fprintf(fp, "parents = %d / ", (int)parents.size());
2342 for (list<C_task *>::const_iterator jt = parents.begin();
2343 jt != parents.end(); ++jt) {
2344 fprintf(fp, "[%p] %s / ", (*jt), (*jt)->task_name);
2345 }
2346 fprintf(fp, "\n");
2347 }
2348 } // loop : it
2349 } // loop : p
2350 fprintf(fp, "*** dynamic : %d ***\n", (int)_queue_dynamic->size());
2351 for (vector<C_task_seq*>::const_iterator it = _queue_dynamic->begin();
2352 it != _queue_dynamic->end(); ++it) {
2353 fprintf(fp, "** C_task_seq = %d : %s [ %d %d] %d **\n",
2354 (*it)->task_id,
2355 (*it)->task_name,
2356 (*it)->begin, (*it)->end,
2357 (*it)->pos);
2358 for (int j = (*it)->begin; j < (*it)->end; j++) {
2359 fprintf(fp, "%s : ", (*(*it)->queue)[j]->task_name);
2360 if ((*(*it)->queue)[j]->atomic_size > 1) {
2361 fprintf(fp, " atomic %d / %d ",
2362 (*(*it)->queue)[j]->atomic_id,
2363 (*(*it)->queue)[j]->atomic_size);
2364 }
2365 // list<C_task *>& parents = *(*(*it)->queue)[j]->parents_work;
2366 list<C_task *>& parents = *(*(*it)->queue)[j]->parents;
2367
2368 fprintf(fp, "parents = %d / ", (int)parents.size());
2369 for (list<C_task *>::const_iterator jt = parents.begin();
2370 jt != parents.end(); ++jt) {
2371 fprintf(fp, "[%p] %s / ", (*jt), (*jt)->task_name);
2372 }
2373 fprintf(fp, "\n");
2374 }
2375 } // loop : it
2376 } // end : scope for fout
2377
2378 void QueueRuntime::exec_symb_fact()
2379 {
2380 const int num_threads = _num_threads;
2381 #ifdef POSIX_THREADS
2382 void* results;
2383 pthread_attr_t th_attr;
2384 #endif
2385 vector<QueueRuntime_thread> threads;
2386 //#else
2387 // vector<std::thread> threads;
2388 //#endif
2389 clock_t t0_cpu, t1_cpu;
2390 elapsed_t t0_elapsed, t1_elapsed;
2391 // struct timespec ts0, ts1;
2392 int ierr;
2393
2394 diss_printf(_verbose, _fp,
2395 "symbolic factorization of sparse matrices with %d threads\n",
2396 num_threads);
2397 #ifdef POSIX_THREADS
2398 // threads = new pthread_t[num_threads];
2399 threads.resize(num_threads);
2400
2401 ierr = pthread_mutex_init(&_mutex_root, NULL);
2402 if (ierr != 0) {
2403 diss_printf(_verbose, _fp,
2404 "%s %d : pthread_mutex_init(&_mutex_root, NULL) : %d\n",
2405 __FILE__, __LINE__, ierr);
2406 }
2407 #endif
2408
2409 #ifdef POSIX_THREADS
2410 #ifdef DEBUG_EXEC_THREAD
2411 ierr = pthread_mutex_init(&_mutex_debug, NULL);
2412 #endif
2413 if (ierr != 0) {
2414 diss_printf(_verbose, _fp,
2415 "%s %d : pthread_mutex_init(&_mutex_debug, NULL) %d\n",
2416 __FILE__, __LINE__, ierr);
2417 }
2418 pthread_attr_init(&th_attr);
2419 pthread_attr_setdetachstate(&th_attr, PTHREAD_CREATE_JOINABLE);
2420 #endif
2421
2422 #ifdef DEBUG_EXEC_THREAD_FILE
2423 {
2424 int pid = get_process_id();
2425 char fname[256];
2426 sprintf(fname, "task-s.%d.data", pid);
2427 _fout.open(fname);
2428 }
2429 #endif
2430 t0_cpu = clock();
2431 get_realtime(&t0_elapsed);
2432 #ifdef POSIX_THREADS
2433 THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
2434 for (int p = 0; p < num_threads; p++) {
2435 params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
2436 int pid = pthread_create(&threads[p], &th_attr,
2437 &thread_queue_symb_factorize_,
2438 (void *)params[p]);
2439 if (pid != 0) {
2440 fprintf(stderr, "bad thread creation ? : %d\n", pid);
2441 exit(0);
2442 }
2443 }
2444 pthread_attr_destroy(&th_attr);
2445 for (int p = 0; p < num_threads; p++) {
2446 int pid = pthread_join(threads[p], &results);
2447 if (pid != 0) {
2448 fprintf(stderr, "bad thread creation ? : %d\n", pid);
2449 exit(0);
2450 }
2451 delete params[p];
2452 }
2453 delete [] params;
2454 #else
2455 THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
2456 for (int p = 0; p < num_threads; p++) {
2457 params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
2458 threads.push_back(std::thread(thread_queue_symb_factorize_,
2459 (void *)params[p]));
2460 }
2461 for (int p = 0; p < num_threads; p++) {
2462 threads[p].join();
2463 delete params[p];
2464 }
2465 delete [] params;
2466 #endif
2467 t1_cpu = clock();
2468 get_realtime(&t1_elapsed);
2469 diss_printf(_verbose, _fp,
2470 "execution of symb queue : cpu time = %.4e elapsed time = %.4e\n",
2471 (double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
2472 convert_time(t1_elapsed, t0_elapsed));
2473 #ifdef DEBUG_EXEC_THREAD_FILE
2474 _fout.close();
2475 #endif
2476
2477 #ifdef DEBUG_THREAD_TIME
2478 {
2479 int pid = get_process_id();
2480 char filename[256];
2481 FILE *fp;
2482 sprintf(filename, "threadtime-symb.%d.data", pid);
2483 if ((fp = fopen(filename, "w")) == NULL) {
2484 fprintf(stderr, "%s %d : fail to open %s\n",
2485 __FILE__, __LINE__, filename);
2486 exit(-1);
2487 }
2488 else {
2489 for (int j = _queue_symb->begin; j < _queue_symb->end; j++) {
2490 fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
2491 (*_queue_symb->queue)[j]->task_name,
2492 (*_queue_symb->queue)[j]->thread_id,
2493 convert_sec((*_queue_symb->queue)[j]->t0),
2494 convert_microsec((*_queue_symb->queue)[j]->t0),
2495 convert_sec((*_queue_symb->queue)[j]->t1),
2496 convert_microsec((*_queue_symb->queue)[j]->t1),
2497 *((*_queue_symb->queue)[j]->ops_complexity));
2498 }
2499 fclose(fp);
2500 } // if fopen()
2501 }
2502 #endif
2503 #ifdef POSIX_THEADS
2504 pthread_mutex_destroy(&_mutex_root);
2505 #ifdef DEBUG_EXEC_THREAD
2506 pthread_mutex_destroy(&_mutex_debug);
2507 #endif
2508 #endif
2509 threads.clear();
2510
2511 }
2512
2513 void QueueRuntime::exec_num_fact_debug()
2514 {
2515 diss_printf(_verbose, _fp,
2516 "numerical factorization with single threads :: DEBUG\n");
2517 int *permute_block = new int[SIZE_B1];
2518 list<C_task_seq*>::const_iterator *its = new list<C_task_seq*>::const_iterator[_num_threads];
2519 diss_printf(_verbose, _fp,
2520 "*** thread = 0 @ %d ***\n", (int)_queue_static[0].size());
2521 for (int p = 0; p < _num_threads; p++) {
2522 its[p] = _queue_static[p].begin();
2523 }
2524 for (list<C_task_seq*>::const_iterator it = _queue_static[0].begin();
2525 it != _queue_static[0].end(); ++it) {
2526 diss_printf(_verbose, _fp, "** C_task_seq = %d : %s, %s **\n",
2527 (*it)->task_id, (*it)->task_name ,
2528 (((*it)->parallel_single == TASK_SINGLE) ? " single " : " shared "));
2529 for (int j = (*it)->begin; j < (*it)->end; j++) {
2530 diss_printf(_verbose, _fp, "%s : ", (*(*it)->queue)[j]->task_name);
2531 if ((*(*it)->queue)[j]->atomic_size > 1) {
2532 diss_printf(_verbose, _fp, "atomic %d / %d ",
2533 (*(*it)->queue)[j]->atomic_id,
2534 (*(*it)->queue)[j]->atomic_size);
2535 }
2536 else {
2537 diss_printf(_verbose, _fp, "\n");
2538 }
2539 execute_task_debug(*it, j, permute_block, 0);
2540 if ((*(*it)->queue)[j]->quit_queue) {
2541 return;
2542 }
2543 } // loop : j
2544 for (int p = 1 ; p < _num_threads; p++) {
2545 diss_printf(_verbose, _fp, "** C_task_seq = %d : %s %s **\n",
2546 (*its[p])->task_id, (*its[p])->task_name,
2547 (((*its[p])->parallel_single == TASK_SINGLE) ? " single " : " shared "));
2548 if ((*its[p])->parallel_single == TASK_SINGLE) {
2549 for (int j = (*its[p])->begin; j < (*its[p])->end; j++) {
2550 diss_printf(_verbose, _fp, "%s : ",
2551 (*(*its[p])->queue)[j]->task_name);
2552 if ((*(*its[p])->queue)[j]->atomic_size > 1) {
2553 diss_printf(_verbose, _fp, " atomic %d / %d\n",
2554 (*(*its[p])->queue)[j]->atomic_id,
2555 (*(*its[p])->queue)[j]->atomic_size);
2556 }
2557 else {
2558 diss_printf(_verbose, _fp, "\n");
2559 }
2560 execute_task_debug(*its[p], j, permute_block, 0);
2561 if ((*(*its[p])->queue)[j]->quit_queue) {
2562 return;
2563 }
2564 } // loop : j
2565 } // if ((*its[p])->parallel_single == TASK_SINGLE)
2566 ++its[p];
2567 } // loop : p > 0
2568 } // loop : it
2569 }
2570
2571 void QueueRuntime::execute_task_debug(C_task_seq *seq, int pos,
2572 int *permute_block,
2573 int pid)
2574 {
2575 C_task *task = (*seq->queue)[pos];
2576 #ifdef DEBUG_CHECKPARENTS_DONE
2577 // debugging
2578 int waiting;
2579 waiting = check_parents_done(task);
2580 if (waiting > 0) {
2581 {
2582 cerr << pid << " parents of task " << task->task_name
2583 << " not finished : ";
2584 for(list<C_task *>::const_iterator nt = task->parents_work->begin();
2585 nt != task->parents_work->end(); ++nt) {
2586 cerr << (*nt)->task_name << " ";
2587 }
2588 cerr << endl;
2589 }
2590 }
2591 //
2592 #endif
2593 // accuessing to unsigned char does not need mutex
2594 task->status = TASK_WORKING;
2595 //
2596 #ifdef DEBUG_THREAD_TIME
2597 get_realtime(&(task->t0));
2598 // clock_gettime(CLOCK_MONOTONIC, &(task->t0));
2599 #endif
2600 // debugging : 13 :Apr.2012 Atsushi
2601 task->func(task->func_arg);
2602 if (task->task_id == C_DFULL_SYM_GAUSS) {
2603 // task->quit_queue = ((C_dfull_gauss_arg*)task->func_arg)->quit;
2604 for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
2605 (*seq->queue)[i]->status = TASK_DONE;
2606 (*seq->queue)[i]->quit_queue = true;
2607 }
2608 }
2609 // accuessing to unsigned char does not neet mutex
2610 task->status = TASK_DONE;
2611 //
2612 }
2613
2614 void QueueRuntime::exec_num_fact(const int called)
2615 {
2616 // unsigned int ui;
2617 const int num_threads = _num_threads;
2618 #ifdef POSIX_THREADS
2619 void* results;
2620 pthread_attr_t th_attr;
2621 vector<pthread_t> threads;
2622 #else
2623 vector<std::thread> threads;
2624 #endif
2625 clock_t t0_cpu, t1_cpu;
2626 elapsed_t t0_elapsed, t1_elapsed;
2627 // struct timespec ts0, ts1;
2628 #ifdef DEBUG_PRINT_TASK
2629 _fps = new FILE*[num_threads];
2630
2631 char fname[256];
2632 for (int p = 0; p < num_threads; p++) {
2633 sprintf(fname, "log.%04d.data", p);
2634 _fps[p] = fopen(fname, "w");
2635 }
2636 #endif
2637 t0_cpu = clock();
2638 get_realtime(&t0_elapsed);
2639 // clock_gettime(CLOCK_REALTIME, &ts0);
2640 diss_printf(_verbose, _fp,
2641 "numerical factorization with %d threads\n", num_threads);
2642 _queue_dynamic_pos_start = (int)((double)(_queue_dynamic->size())
2643 * RATIO_QUEUE_GREEDY);
2644 _queue_dynamic_pos = _queue_dynamic_pos_start;
2645 _queue_dynamic_notcopied = num_threads;
2646
2647 // reset status for numeric queue execution
2648 _waiting_root = 0;
2649 _phase_dynamic = 0;
2650
2651 for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
2652 _zone_entered[i] = 0;
2653 _zone_finished[i] = 0;
2654 }
2655
2656 for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
2657 _zone_static_assigned[i] = 0;
2658 }
2659
2660 for (int p = 0; p < num_threads; p++) {
2661 for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
2662 _begins[p][i] = 0;
2663 _ends[p][i] = 0;
2664 }
2665 for (int q = 0; q < DIST_TASK_CRITICAL; q++) {
2666 for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
2667 _group_entered[p][q][i] = 0;
2668 _group_finished[p][q][i] = 0;
2669 _group_task_ends[p][q][i] = (-1);
2670 _group_static_assigned[p][q][i] = (-1);
2671 }
2672 } // loop : q
2673 } // loop : p
2674 #ifdef POSIX_THREADS
2675 pthread_mutex_init(&_mutex_file, NULL);
2676 pthread_mutex_init(&_mutex_dependency, NULL);
2677
2678 pthread_attr_init(&th_attr);
2679 pthread_attr_setdetachstate(&th_attr, PTHREAD_CREATE_JOINABLE);
2680
2681 for (int p = 0; p < num_threads; p++) {
2682 pthread_mutex_init(&_mutex_group[p], NULL);
2683 }
2684 // threads = new pthread_t[num_threads];
2685 threads.resize(num_threads);
2686
2687 pthread_mutex_init(&_mutex_root, NULL);
2688 pthread_mutex_init(&_mutex_debug, NULL);
2689 pthread_cond_init(&_cond_root, NULL);
2690 #endif
2691
2692 #ifdef DEBUG_EXEC_THREAD_FILE
2693 {
2694 int pid = get_process_id();
2695 char fname[256];
2696 sprintf(fname, "task-n.%d.data", pid);
2697 cerr << "== task log == " << fname << endl;
2698 _fout.open(fname);
2699 }
2700 #endif
2701 #if 1
2702 {
2703 // copy dependency data : parents -> parents_work
2704 for (int p = 0; p < _num_threads; p++) {
2705 for (list<C_task_seq *>::const_iterator it = _queue_static[p].begin();
2706 it != _queue_static[p].end(); ++it) {
2707 vector<C_task *> &queue = *(*it)->queue;
2708 for (int j = (*it)->begin; j < (*it)->end; j++) {
2709 list<C_task *>& parents_work = *(queue[j]->parents_work);
2710 if (parents_work.size() > 0) { // to avoid double free
2711 parents_work.clear();
2712 }
2713 } // loop : j
2714 } // loop : it
2715 }
2716 for (vector<C_task_seq *>::const_iterator it = _queue_dynamic->begin();
2717 it != _queue_dynamic->end(); ++it) {
2718 vector<C_task *> &queue = *((*it)->queue);
2719 for (int j = (*it)->begin; j < (*it)->end; j++) {
2720 list<C_task *>& parents_work = *(queue[j]->parents_work);
2721 if (parents_work.size() > 0) { // to avoid double free
2722 parents_work.clear();
2723 }
2724 } // loop : j
2725 } // loop : it
2726
2727
2728 for (int p = 0; p < _num_threads; p++) {
2729 for (list<C_task_seq *>::const_iterator it = _queue_static[p].begin();
2730 it != _queue_static[p].end(); ++it) {
2731 vector<C_task *> &queue = *(*it)->queue;
2732 for (int j = (*it)->begin; j < (*it)->end; j++) {
2733 queue[j]->quit_queue = false;
2734 list<C_task *>& parents = *(queue[j]->parents);
2735 list<C_task *>& parents_work = *(queue[j]->parents_work);
2736 if (parents_work.size() == 0) {
2737 #ifdef SX_ACE
2738 for (list<C_task *>::const_iterator lt = parents.begin();
2739 lt != parents.end(); ++lt) {
2740 parents_work.push_back(*lt);
2741 }
2742 #else // SX-ACE C++ rev 110 with C++98/03 does not understand back_insertera
2743 std::copy(parents.begin(), parents.end(),
2744 back_inserter(parents_work));
2745 #endif
2746 }
2747 queue[j]->status = TASK_WAITING; // reset status
2748 } // loop : j
2749 (*it)->pos = (*it)->begin;
2750 } // loop : it
2751 }
2752
2753 for (vector<C_task_seq *>::const_iterator it = _queue_dynamic->begin();
2754 it != _queue_dynamic->end(); ++it) {
2755 vector<C_task *> &queue = *((*it)->queue);
2756 for (int j = (*it)->begin; j < (*it)->end; j++) {
2757 queue[j]->quit_queue = false;
2758 list<C_task *>& parents = *(queue[j]->parents);
2759 list<C_task *>& parents_work = *(queue[j]->parents_work);
2760 if (parents_work.size() == 0) {
2761 #ifdef SX_ACE
2762 for (list<C_task *>::const_iterator lt = parents.begin();
2763 lt != parents.end(); ++lt) {
2764 parents_work.push_back(*lt);
2765 }
2766 #else // SX-ACE C++ rev 110 with C++98/03 does not understand back_inserter
2767 std::copy(parents.begin(), parents.end(), back_inserter(parents_work));
2768 #endif
2769 }
2770 queue[j]->status = TASK_WAITING; // reset status
2771 } // loop : j
2772 (*it)->pos = (*it)->begin;
2773 } // loop : it
2774 }
2775 #endif
2776 // begin : scope for fout
2777 if (0) {
2778 char fname[256];
2779 int pid = get_process_id();
2780 sprintf(fname, "tasks-before.%d.%d.data", pid, called);
2781 FILE *fp;
2782 if ((fp = fopen(fname, "a")) != NULL) {
2783 write_dependency(fp);
2784 fclose(fp);
2785 }
2786 else {
2787 fprintf(stderr,
2788 "%s %d : fail to open %s\n",
2789 __FILE__, __LINE__, fname);
2790 exit(-1);
2791 }
2792 } // end : scope for fout
2793
2794 t0_cpu = clock();
2795 get_realtime(&t0_elapsed);
2796 #ifdef POSIX_THREADS
2797 THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
2798 for (int p = 0; p < num_threads; p++) {
2799 params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
2800 int pid = pthread_create(&threads[p], &th_attr,
2801 &thread_queue_num_factorize_,
2802 (void *)params[p]);
2803 if (pid != 0) {
2804 fprintf(_fp, "bad thread creation ? : %d\n", pid);
2805 exit(0);
2806 }
2807 }
2808 pthread_attr_destroy(&th_attr);
2809 for (int p = 0; p < num_threads; p++) {
2810 int pid = pthread_join(threads[p], &results);
2811 if (pid != 0) {
2812 fprintf(_fp, "bad thread creation ? : %d\n", pid);
2813 exit(0);
2814 }
2815 delete params[p];
2816 }
2817 delete [] params;
2818 #else
2819 THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
2820 for (int p = 0; p < num_threads; p++) {
2821 params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
2822 threads.push_back(std::thread(thread_queue_num_factorize_,
2823 (void *)params[p]));
2824 }
2825 for (int p = 0; p < num_threads; p++) {
2826 threads[p].join();
2827 delete params[p];
2828 }
2829 delete [] params;
2830 #endif
2831 t1_cpu = clock();
2832 get_realtime(&t1_elapsed);
2833 diss_printf(_verbose, _fp,
2834 "execution of num queue : cpu time = %.4e elapsed time = %.4e\n",
2835 (double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
2836 convert_time(t1_elapsed, t0_elapsed));
2837 #ifdef DEBUG_EXEC_THREAD_FILE
2838 _fout.close();
2839 #endif
2840
2841 // begin : scope for fout
2842 if (0) {
2843 char fname[256];
2844 int ppid = get_process_id();
2845 sprintf(fname, "tasks-copied.%d.data", ppid);
2846 FILE *fp;
2847 if ((fp = fopen(fname, "a")) != NULL) {
2848 write_dependency(fp);
2849 fclose(fp);
2850 }
2851 else {
2852 fprintf(stderr,
2853 "%s %d : fail to open %s\n",
2854 __FILE__, __LINE__, fname);
2855 exit(-1);
2856 }
2857 }
2858
2859 #ifdef DEBUG_THREAD_TIME
2860 {
2861 int pid = get_process_id();
2862 char filename[256];
2863 FILE *fp;
2864
2865 for (int p = 0; p < num_threads; p++) {
2866 for (list<C_task_seq*>::const_iterator it = _queue_static[p].begin();
2867 it != _queue_static[p].end(); ++it) {
2868 (*it)->status = TASK_WAITING;
2869 }
2870 }
2871 for (vector<C_task_seq*>::const_iterator it = _queue_dynamic->begin();
2872 it != _queue_dynamic->end(); ++it) {
2873 (*it)->status = TASK_WAITING;
2874 }
2875 sprintf(filename, "threadtime-num.%d.data", pid);
2876 if ((fp = fopen(filename, "w")) == NULL) {
2877 fprintf(stderr, "%s %d : fail to open %s\n",
2878 __FILE__, __LINE__, filename);
2879 exit(-1);
2880 }
2881 else {
2882 fprintf(fp, "**** numeric factorization start ****\n");
2883 for (int p = 0; p < num_threads; p++) {
2884 fprintf(fp, "*** thread = %d @ %d ** ", p,
2885 (int)_queue_static[p].size());
2886 for (list<C_task_seq*>::const_iterator it = _queue_static[p].begin();
2887 it != _queue_static[p].end(); ++it) {
2888 fprintf(fp, "** %d C_task_seq = %d : %s %s **\n",
2889 p, (*it)->task_id,
2890 ((*it)->parallel_single == TASK_SINGLE ? "distributed " : "shared "),
2891 (*it)->task_name);
2892 if ((*it)->status == TASK_DONE) {
2893 continue;
2894 }
2895 for (int j = (*it)->begin; j < (*it)->end; j++) {
2896
2897 if ((*(*it)->queue)[j]->task_id == C_SPARSESCHUR) {
2898 elapsed_t t0, t1;
2899 t0 = (*(*it)->queue)[j]->t0;
2900 t1 = ((C_SparseNumFact_arg<double, double> *)(*(*it)->queue)[j]->func_arg)->tt[0];
2901 string task_name = "o0 : ";
2902 fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
2903 task_name.c_str(),
2904 // (*(*it)->queue)[j]->task_name,
2905 (*(*it)->queue)[j]->thread_id,
2906 convert_sec(t0),
2907 convert_microsec(t0),
2908 convert_sec(t1),
2909 convert_microsec(t1), 0L);
2910 for (int i = 0; i < 4; i++) {
2911 string task_name = "o" + to_string(i + 1) + " : ";
2912
2913 t0 = ((C_SparseNumFact_arg<double, double> *)(*(*it)->queue)[j]->func_arg)->tt[i];
2914 t1 = ((C_SparseNumFact_arg<double, double> *)(*(*it)->queue)[j]->func_arg)->tt[i + 1];
2915 fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
2916 task_name.c_str(),
2917 // (*(*it)->queue)[j]->task_name,
2918 (*(*it)->queue)[j]->thread_id,
2919 convert_sec(t0),
2920 convert_microsec(t0),
2921 convert_sec(t1),
2922 convert_microsec(t1), 0L);
2923 }
2924 }
2925 else {
2926 fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
2927 (*(*it)->queue)[j]->task_name,
2928 (*(*it)->queue)[j]->thread_id,
2929 convert_sec((*(*it)->queue)[j]->t0),
2930 convert_microsec((*(*it)->queue)[j]->t0),
2931 convert_sec((*(*it)->queue)[j]->t1),
2932 convert_microsec((*(*it)->queue)[j]->t1),
2933 *((*(*it)->queue)[j]->ops_complexity));
2934 }
2935 //*((C_SparseNumFact_arg<double> *)(*(*it)->queue)[j]->func_arg)->nops :
2936 }
2937 (*it)->status = TASK_DONE;
2938 }
2939 }
2940 fprintf(fp, "*** dynamic : %d ***", (int)_queue_dynamic->size());
2941 for (vector<C_task_seq*>::const_iterator it = _queue_dynamic->begin();
2942 it != _queue_dynamic->end(); ++it) {
2943 fprintf(fp, "** C_task_seq = %s : [%d, %d] %d **\n",
2944 (*it)->task_name,
2945 (*it)->begin, (*it)->end,(*it)->pos);
2946 if ((*it)->status == TASK_DONE) {
2947 continue;
2948 }
2949 for (int j = (*it)->begin; j < (*it)->end; j++) {
2950 fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
2951 (*(*it)->queue)[j]->task_name,
2952 (*(*it)->queue)[j]->thread_id,
2953 convert_sec((*(*it)->queue)[j]->t0),
2954 convert_microsec((*(*it)->queue)[j]->t0),
2955 convert_sec((*(*it)->queue)[j]->t1),
2956 convert_microsec((*(*it)->queue)[j]->t1),
2957 *((*(*it)->queue)[j]->ops_complexity));
2958 }
2959 (*it)->status = TASK_DONE;
2960 }
2961 fprintf(fp, "**** numeric factorization end ****\n");
2962 fclose(fp);
2963 }
2964 } // if fopen()
2965 #endif // DEBUG_THREAD_TIME
2966 #ifdef DEBUG_PRINT_TASK
2967 for (int p = 0; p < num_threads; p++) {
2968 fclose(_fps[p]);
2969 }
2970 delete [] _fps;
2971 #endif
2972
2973 threads.clear();
2974 }
2975
2976 void *thread_queue_symb_factorize_(void *arg)
2977 {
2978 THREAD_QUEUE_EXEC *params = (THREAD_QUEUE_EXEC *)arg;
2979 params->dissectionRuntime->thread_queue_symb_factorize(params->id,
2980 params->num_threads);
2981 #ifdef POSIX_THREADS
2982 pthread_exit(arg);
2983 #endif
2984 return (void *)NULL;
2985 }
2986 void QueueRuntime::thread_queue_symb_factorize(const int pid,
2987 const int num_threads)
2988 {
2989 // const int pid = params->id;
2990 // const int num_threads = params->num_threads;
2991 // greedy -- better to be in seperated function
2992 int pos, end;
2993 C_task_seq* it = _queue_symb;
2994 while(1) {
2995 { // scope of mutex
2996 MUTEX_LOCK(_mutex_root, lck_root);
2997 pos = it->pos;
2998 end = it->end;
2999 if (pos < end) {
3000 it->pos++;
3001 }
3002 MUTEX_UNLOCK(_mutex_root);
3003 } // scope of mutex
3004 if (pos >= end) {
3005 break;
3006 }
3007 C_task *task = (*it->queue)[pos];
3008 task->status = TASK_WORKING;
3009 #ifdef DEBUG_THREAD_TIME
3010 get_realtime(&(task->t0));
3011 // clock_gettime(CLOCK_MONOTONIC, &(task->t0));
3012 #endif
3013 task->func(task->func_arg);
3014 #ifdef DEBUG_THREAD_TIME
3015 get_realtime(&(task->t1));
3016 // clock_gettime(CLOCK_MONOTONIC, &(task->t1));
3017 task->thread_id = pid;
3018 #endif
3019 // accuessing to unsigned char does not neet mutex
3020 task->status = TASK_DONE;
3021
3022 #ifdef DEBUG_EXEC_THREAD
3023 {
3024 MUTEX_LOCK(_mutex_debug, lck_debug);
3025 cerr << "( " << pid << " " << pos << " ) " ;
3026 MUTEX_UNLOCK(_mutex_debug);
3027 }
3028 #endif
3029 } // while (1)
3030 #ifdef DEBUG_EXEC_THREAD
3031 {
3032 MUTEX_LOCK(_mutex_debug, lck_debug);
3033 cerr << pid << " " << it->task_name
3034 << " @ " << it->task_id << " greedy end." << endl;
3035 MUTEX_UNLOCK(_mutex_debug);
3036 }
3037 #endif
3038 }
3039
3040 void *thread_queue_num_factorize_(void *arg)
3041 {
3042 THREAD_QUEUE_EXEC *params = (THREAD_QUEUE_EXEC *)arg;
3043 params->dissectionRuntime->thread_queue_num_factorize(params->id,
3044 params->num_threads);
3045 #ifdef POSIX_THREADS
3046 pthread_exit(arg);
3047 #endif
3048 return (void *)NULL;
3049 }
3050
3051 void QueueRuntime::thread_queue_num_factorize(const int pid,
3052 const int num_threads)
3053 {
3054 int *permute_block = new int[SIZE_B1];
3055
3056 list<C_task_seq*>::const_iterator it = _queue_static[pid].begin();
3057 int zone, zone_idxn, zone_idxp;
3058 bool zone_flag;
3059 int zone_first_entered = 0;
3060 int zone_last_entered = 0;
3061 int zone_first_finished = 0;
3062 int zone_last_finished = 0;
3063 int cnt_cdfull = 0;
3064 //
3065 zone = 0;
3066 while(it != _queue_static[pid].end()) {
3067 #ifdef DEBUG_THREAD_LOOP
3068 {
3069 MUTEX_LOCK(_mutex_debug, lck_debug);
3070 cerr << pid << " : " << (*it)->task_name
3071 << " _phase_dynamic = " << _phase_dynamic << endl;
3072 MUTEX_UNLOCK(_mutex_debug);
3073 }
3074 #endif
3075 //
3076 zone_idxp = (zone + DIST_TASK_CRITICAL - 1) % DIST_TASK_CRITICAL;
3077 zone_idxn = zone % DIST_TASK_CRITICAL;
3078 zone_first_entered = 0;
3079 zone_last_entered = 0;
3080 { // scope of mutex
3081 MUTEX_LOCK(_mutex_root, lck_root);
3082 if (_zone_entered[zone_idxn] == 0) {
3083 zone_first_entered = 1;
3084 _zone_static_assigned[zone_idxn] = 0;
3085 }
3086 _zone_entered[zone_idxn]++;
3087 zone_flag = (_zone_entered[zone_idxn] == num_threads);
3088 if (zone_flag) {
3089 // clear cyclic buffer
3090 _zone_entered[zone_idxp] = 0;
3091 _zone_static_assigned[zone_idxp] = 0; // only for safety
3092 zone_last_entered = 1;
3093 }
3094 MUTEX_UNLOCK(_mutex_root);
3095 } // scope of mutex
3096 zone++;
3097 //
3098 if ((*it)->parallel_single == TASK_PARALLEL) {
3099 switch((*it)->task_id) {
3100 case C_DFULL :
3101 #ifdef DEBUG_EXEC_THREAD
3102 {
3103 MUTEX_LOCK(_mutex_debug, lck_debug);
3104 cerr << pid << " C_DFULL "
3105 << (*it)->task_name << " : " << (*it)->task_id
3106 << " @ " << zone << " : " << zone_flag << " : "
3107 << " zone ( " << zone_first_entered << " : "
3108 << zone_last_entered << " )"
3109 << " : " << (*it)->pos << " " << (*it)->end << endl;
3110 MUTEX_UNLOCK(_mutex_debug);
3111 }
3112 #endif
3113 thread_queue_C_DFULL(pid, num_threads, *it,
3114 permute_block,
3115 cnt_cdfull,
3116 zone_first_entered,
3117 zone_idxn);
3118 #ifdef DEBUG_THREAD_LOOP
3119 {
3120 MUTEX_LOCK(_mutex_debug, lck_debug);
3121 cerr << pid << " C_DFULL "
3122 << (*it)->task_name << " end." << endl;
3123 MUTEX_UNLOCK(_mutex_debug);
3124 }
3125 #endif
3126 break;
3127 case C_SPARSELOCALSCHUR:
3128 case C_DTRSM:
3129 case C_DGEMM:
3130 case C_DSUB:
3131 case C_FILLMATRIX:
3132 case C_DEALLOCATE:
3133 case C_SPARSESOLVER:
3134 #ifdef DEBUG_EXEC_THREAD
3135 {
3136 MUTEX_LOCK(_mutex_debug, lck_debug);
3137 cerr << pid << " remaining diagonal "
3138 << (*it)->task_name << " : " << (*it)->task_id
3139 << " @ " << zone << " : " << zone_flag << " : "
3140 << " zone ( " << zone_first_entered << " : "
3141 << zone_last_entered << " )"
3142 << " : " << (*it)->pos << " " << (*it)->end << endl;
3143 MUTEX_UNLOCK(_mutex_debug);
3144 }
3145 #endif
3146 thread_queue_parallel_dynamic(pid, num_threads, *it,
3147 permute_block,
3148 zone_idxn);
3149 #ifdef DEBUG_THREAD_LOOP
3150 {
3151 MUTEX_LOCK(_mutex_debug, lck_debug);
3152 cerr << pid << " remaining diagonal "
3153 << (*it)->task_name << " end." << endl;
3154 MUTEX_UNLOCK(_mutex_debug);
3155 }
3156 #endif
3157 break;
3158 case C_SPARSELOCALSCHUR1:
3159 case C_DTRSM1:
3160 case C_DGEMM1:
3161 case C_DSUB1:
3162 case C_FILLMATRIX1:
3163 case C_DEALLOCATE1:
3164 #ifdef DEBUG_EXEC_THREAD
3165 {
3166 MUTEX_LOCK(_mutex_debug, lck_debug);
3167 cerr << pid << " remaining off-diagonal "
3168 << (*it)->task_name << " : " << (*it)->task_id
3169 << " @ " << zone << " : " << zone_flag << " : "
3170 << " zone ( " << zone_first_entered << " : "
3171 << zone_last_entered << " )"
3172 << " : " << (*it)->pos << " " << (*it)->end << endl;
3173 MUTEX_UNLOCK(_mutex_debug);
3174 }
3175 #endif
3176 thread_queue_parallel_static(pid, num_threads, *it,
3177 permute_block,
3178 zone_idxp,
3179 zone_idxn,
3180 zone_first_entered,
3181 zone_last_entered);
3182 #ifdef DEBUG_THREADS_LOOP
3183 {
3184 MUTEX_LOCK(_mutex_debug, lck_debug);
3185 cerr << pid << " remaining off-diagonal "
3186 << (*it)->task_name << " end." << endl;
3187 MUTEX_UNLOCK(_mutex_debug);
3188 }
3189 #endif
3190 break;
3191 }
3192 }
3193 else { // if ((*it)->parallel_single == TASK_SINGLE)
3194 #ifdef DEBUG_EXEC_THREAD
3195 {
3196 MUTEX_LOCK(_mutex_debug, lck_debug);
3197 cerr << pid << " single "
3198 << (*it)->task_name << " : " << (*it)->task_id
3199 << " @ " << zone << " : " << zone_flag << " : "
3200 << " zone ( " << zone_first_entered << " : "
3201 << zone_last_entered << " )"
3202 << " : " << (*it)->pos << " " << (*it)->end << endl;
3203 MUTEX_UNLOCK(_mutex_debug);
3204 }
3205 #endif
3206 thread_queue_single(pid, num_threads, *it,
3207 permute_block,
3208 zone_idxn);
3209 #ifdef DEBUG_THREAD_LOOP
3210 {
3211 MUTEX_LOCK(_mutex_debug, lck_debug);
3212 cerr << pid << " single "
3213 << (*it)->task_name << " end." << endl;
3214 MUTEX_UNLOCK(_mutex_debug);
3215 }
3216 #endif
3217 } // if ((*it)->parallel_single == TASK_SINGLE)
3218 int clear_flag = 0;
3219 { // scope of mutex
3220 MUTEX_LOCK(_mutex_root, lck_root);
3221 if (_zone_finished[zone_idxn] == 0) {
3222 zone_first_finished = 1;
3223 }
3224 _zone_finished[zone_idxn]++;
3225 if (_zone_finished[zone_idxn] == num_threads) {
3226 zone_last_finished = 1;
3227 // clear status of cyclic buffer
3228 _zone_finished[zone_idxp] = 0;
3229 // the last task
3230 (*it)->status = TASK_DONE;
3231 if((*it)->task_id == C_DFULL) {
3232 clear_flag = 1;
3233 }
3234 #ifdef DEBUG_THREAD_LOOP
3235 {
3236 MUTEX_LOCK(_mutex_debug, lck_debug);
3237 cerr << pid << " "
3238 << (*it)->task_name << " end." << endl;
3239 MUTEX_UNLOCK(_mutex_debug);
3240 }
3241 #endif
3242 }
3243 MUTEX_UNLOCK(_mutex_root);
3244 } // scope of mutex
3245 // without mutex
3246 if((*it)->task_id == C_DFULL) {
3247 cnt_cdfull = (cnt_cdfull + 1) % DIST_TASK_CRITICAL;
3248 if (clear_flag) {
3249 const int cnt_cdfull_p =
3250 ((cnt_cdfull + DIST_TASK_CRITICAL - 1) % DIST_TASK_CRITICAL);
3251 for (int p = 0; p < num_threads; p++) {
3252 for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
3253 _group_entered[p][cnt_cdfull_p][i] = 0;
3254 _group_finished[p][cnt_cdfull_p][i] = 0;
3255 _group_task_ends[p][cnt_cdfull_p][i] = (-1);
3256 }
3257 }
3258 }
3259 } // if((*it)->task_id == C_DFULL) {
3260 ++it;
3261 } // while (it != _queue_static[pid].end()) {
3262 delete [] permute_block;
3263 }
3264
3265 void QueueRuntime::thread_queue_C_DFULL(const int pid,
3266 const int num_threads,
3267 C_task_seq *it,
3268 int *permute_block,
3269 const int cnt_cdfull,
3270 const int zone_first_entered,
3271 const int zone_idxn)
3272 {
3273 const int pid_g = it->mutex_id;
3274 int group = 0;
3275 int group_first_entered = 0, group_last_entered = 0;
3276 int group_first_finished = 0;
3277 int pos;
3278 int pid0;
3279 int *_grp_entered = _group_entered[pid_g][cnt_cdfull];
3280 int *_grp_finished = _group_finished[pid_g][cnt_cdfull];
3281 int *_grp_task_ends = _group_task_ends[pid_g][cnt_cdfull];
3282 int *_grp_static_assigned = _group_static_assigned[pid_g][cnt_cdfull];
3283 bool zone_flag;
3284
3285 // get status other threads entered the same zone
3286 {
3287 // std::unique_lock<std::mutex>lck_root(_mutex_root);
3288 MUTEX_LOCK(_mutex_root, lck_root);
3289 zone_flag = (_zone_entered[zone_idxn] == num_threads);
3290 MUTEX_UNLOCK(_mutex_root);
3291 }
3292 #ifdef DEBUG_EXEC_THREAD
3293 {
3294 MUTEX_LOCK(_mutex_debug, lck_debug);
3295 cerr << pid << " cnt_cdfull = " << cnt_cdfull << " parallel : c_dfull "
3296 << it->task_name << " pos = " << it->pos << endl;
3297 MUTEX_UNLOCK(_mutex_debug);
3298 }
3299 #endif
3300 { // scope of mutex
3301 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3302 if (_grp_entered[0] == 0) {
3303 // reset flags to keep status of entered/finshed tasks
3304 for (int i = 1; i < DIST_TASK_CRITICAL; i++) {
3305 _grp_entered[i] = 0;
3306 _grp_finished[i] = 0;
3307 }
3308 for (int i = 0; i < it->num_threads; i++) {
3309 _group_nops[pid_g][i] = 0L;
3310 }
3311 group_first_entered = 1;
3312 _grp_static_assigned[0] = 0; // 12 Feb.2013 Atsusti : for safety?
3313 #ifdef DEBUG_EXEC_THREAD
3314 {
3315 MUTEX_LOCK(_mutex_debug, lck_debug);
3316 cerr << pid << " : " << it->pos << endl;
3317 MUTEX_UNLOCK(_mutex_debug);
3318 }
3319 #endif
3320 }
3321 // pid0 is decided by arrived order
3322 pid0 = _grp_entered[0]++;
3323 if (_grp_entered[0] == it->num_threads) {
3324 group_last_entered = 1;
3325 }
3326 MUTEX_UNLOCK(_mutex_group[pid_g]);
3327 } // scope of mutex
3328 //
3329 while (1) { // global loop of task queue
3330 //
3331 const int gidxp = (group + DIST_TASK_CRITICAL - 1) % DIST_TASK_CRITICAL;
3332 const int gidxn = group % DIST_TASK_CRITICAL;
3333 int finish_group = 0;
3334 int skip_flag = 0;
3335 if (group > 0) {
3336 { // scope of mutex
3337 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3338 _begins_group[pid_g][pid0][gidxn] = (-1);
3339 _ends_group[pid_g][pid0][gidxn] = (-1);
3340 group_first_entered = 0;
3341 group_last_entered = 0;
3342 if (_grp_entered[gidxn] == 0) {
3343 group_first_entered = 1;
3344 // assuming other jobs are assiged by static
3345 for (int i = 0; i < it->num_threads; i++) {
3346 _group_nops[pid_g][i] = 0L;
3347 }
3348 #if 1
3349 pos = it->pos;
3350 int jtmp = pos;
3351 for (int i = (*it->queue)[pos]->parallel_id;
3352 i < (*it->queue)[pos]->parallel_max; i++) {
3353 jtmp += (*it->queue)[jtmp]->atomic_size;
3354 }
3355 _grp_task_ends[gidxn] = jtmp;
3356 _grp_task_ends[gidxp] = (-1);
3357 _grp_static_assigned[gidxn] = 0;
3358 #else
3359 _group_task_ends[pid_g][cnt_cdfull][gidxn] = (-1);
3360 #endif
3361 } // if (_grp_entered[gidxn] == 0)
3362 _grp_entered[gidxn]++;
3363 if (_grp_entered[gidxn] == it->num_threads) {
3364 // clear status of cyclic buffer
3365 _grp_entered[gidxp] = 0;
3366 group_last_entered = 1;
3367 }
3368 if ((_grp_finished[gidxn] > 0) && (group_first_finished == 0)) {
3369 _grp_finished[gidxn]++;
3370 if (_grp_finished[gidxn] == it->num_threads) {
3371 // clear status of cyclic buffer
3372 _grp_finished[gidxp] = 0;
3373 _group_task_ends[pid_g][cnt_cdfull][gidxp] = (-1);
3374 }
3375 skip_flag = 1;
3376 } // if ((_grp_finished[gidxn] > 0) && (group_first_finished == 0))
3377 MUTEX_UNLOCK(_mutex_group[pid_g]);
3378 } // scope of mutex
3379 } // if (group > 0)
3380 else {
3381 { // scope of mutex
3382 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3383 if ((_grp_finished[gidxn] > 0) &&
3384 (group_first_finished == 0)) {
3385 _grp_finished[gidxn]++;
3386 if (_grp_finished[gidxn] == it->num_threads) {
3387 // clear status of cyclic buffer
3388 _grp_finished[gidxp] = 0;
3389 _group_task_ends[pid_g][cnt_cdfull][gidxp] = (-1);
3390 }
3391 skip_flag = 1;
3392 }
3393 MUTEX_UNLOCK(_mutex_group[pid_g]);
3394 } // scope mutex
3395 } // if (group > 0)
3396 #ifdef DEBUG_EXEC_THREAD
3397 {
3398 MUTEX_LOCK(_mutex_debug, lck_debug);
3399 cerr << pid << " pid_g = " << pid_g << " pid0 " << pid0
3400 << " group " << group << " entered "
3401 << group_first_entered << " / " << group_last_entered
3402 << " (" << _grp_entered[gidxp] << "@" << gidxp
3403 << ") / (" << _grp_entered[gidxn] << "@" << gidxn
3404 << ") finished "
3405 << " (" << _grp_finished[gidxp] << "@" << gidxp
3406 << ") / ( " << _grp_finished[gidxn] << "@" << gidxn
3407 << ") " << it->pos << " : " << it->end
3408 << " skip_flag = " << skip_flag;
3409 if (skip_flag) {
3410 cerr << " task is already finished : my job is skipped";
3411 }
3412 cerr << " zone_flag = " << zone_flag
3413 << " zone_idxn = " << zone_idxn
3414 << endl;
3415 MUTEX_UNLOCK(_mutex_debug);
3416 }
3417 #endif
3418 group++;
3419 //
3420 if (skip_flag) {
3421 continue;
3422 }
3423 #if 1
3424 // wait until other threads enter the same zone
3425 while (!zone_flag) {
3426 // looking for dynamic queue
3427 int flag = 1;
3428 while ((flag == 1) && (!zone_flag)) {
3429 flag = execute_task_dynamic_buffer(permute_block,
3430 pid,
3431 _mutex_dependency);
3432 { // scope of mutex
3433 // std::unique_lock<std::mutex>lck_root(_mutex_root);
3434 MUTEX_LOCK(_mutex_root, lck_root);
3435 zone_flag = (_zone_entered[zone_idxn] == num_threads);
3436 MUTEX_UNLOCK(_mutex_root);
3437 }
3438 } // while ((flag == 1) && (!zone_flag))
3439 if (zone_flag) {
3440 #ifdef DEBUG_EXEC_THREAD
3441 {
3442 MUTEX_LOCK(_mutex_debug, lck_debug);
3443 cerr << pid << " pid_g = " << pid_g << " pid0 " << pid0
3444 << " zone_idxn = " << zone_idxn
3445 << " zone_flag = " << zone_flag
3446 << endl;
3447 MUTEX_UNLOCK(_mutex_debug);
3448 }
3449 #endif
3450 break;
3451 }
3452 // get tasks with atomic_size from the queue : *it
3453 int itmp, jtmp;
3454 int exit_flag = 0;
3455 { // scope of mutex
3456 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3457 pos = it->pos;
3458 // do not increase queue more than its size
3459 if (pos == it->end) {
3460 exit_flag = 1;
3461 }
3462 else {
3463 // there might be segments with more than 1 automic size
3464 // between parallel_id and parallel_max
3465 itmp = pos + (*it->queue)[pos]->atomic_size;
3466 jtmp = (itmp - 1 + ((*it->queue)[pos]->parallel_max -
3467 (*it->queue)[pos]->parallel_id));
3468 #ifdef DEBUG_EXEC_THREAD
3469 {
3470 MUTEX_LOCK(_mutex_debug, lck_debug);
3471 cerr << pid << " pos = " << pos << " +atomic_size = " << itmp
3472 << " parallel_max " << jtmp << " : " << it->end
3473 << endl;
3474 MUTEX_UNLOCK(_mutex_debug);
3475 }
3476 #endif
3477 if (itmp <= jtmp) {
3478 it->pos = itmp;
3479 }
3480 }
3481 MUTEX_UNLOCK(_mutex_group[pid_g]);
3482 } // scope of mutex
3483 if (exit_flag) {
3484 #ifdef DEBUG_EXEC_THREAD
3485 {
3486 MUTEX_LOCK(_mutex_debug, lck_debug);
3487 cerr << pid << " pod = " << pos << "it->end = " << it->end
3488 << " : " << it->task_name << " already finished.." << endl;
3489 MUTEX_UNLOCK(_mutex_debug);
3490 }
3491 #endif
3492 return;
3493 }
3494 if (itmp == jtmp) {
3495 #ifdef DEBUG_EXEC_THREAD
3496 {
3497 MUTEX_LOCK(_mutex_debug, lck_debug);
3498 cerr << pid << " pos = " << pos << " jtmp = " << jtmp << endl;
3499 MUTEX_UNLOCK(_mutex_debug);
3500 }
3501 #endif
3502 finish_group = 1;
3503 }
3504 // reserve tasks and conunt estimated job size
3505 { // scope of mutex
3506 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3507 for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
3508 _group_nops[pid_g][pid0] +=
3509 *((*it->queue)[pos + i]->ops_complexity);
3510 }
3511 MUTEX_UNLOCK(_mutex_group[pid_g]);
3512 } // scope mutex
3513
3514 #ifdef DEBUG_EXEC_THREAD
3515 {
3516 MUTEX_LOCK(_mutex_debug, lck_debug);
3517 if ((*it->queue)[pos]->atomic_size > 1) {
3518 C_task *kt = (*it->queue)[pos];
3519 cerr << pid << " b-c-a " << pos << " : "
3520 << kt->task_name << " : "
3521 << kt->parents_work->size() << " / ";
3522 for (list<C_task *>::const_iterator mt = kt->parents_work->begin();
3523 mt != kt->parents_work->end(); ++mt) {
3524 cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
3525 }
3526 cerr << "before statically assigned task : with status check."
3527 << endl;
3528 }
3529 MUTEX_UNLOCK(_mutex_debug);
3530 }
3531 #endif
3532 for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
3533 C_task *kt = (*it->queue)[pos + i];
3534 int waiting1 = check_parents_done(kt, _mutex_dependency);
3535
3536 while(waiting1 > 0) {
3537 //
3538 { // scope of mutex
3539 MUTEX_LOCK(_mutex_root, lck_root);
3540 _waiting_root++;
3541 #ifdef DEBUG_DEADLOCK
3542 if (_waiting_root > num_threads) {
3543 fprintf(stderr, "dead lock occured : %s %d\n",
3544 __FILE__, __LINE__);
3545 exit(-1);
3546 }
3547 #endif
3548 #ifdef DEBUG_EXEC_THREAD_IDLE
3549 {
3550 cerr << pid << " " << kt->task_name << " "
3551 << "waiting = "<< waiting1 << " : "
3552 << (int)_waiting_root << " "
3553 << __FILE__ << " " << __LINE__ << " ";
3554 for (list<C_task *>::const_iterator jt = kt->parents_work->begin();
3555 jt != kt->parents_work->end(); ++jt) {
3556 cerr << (*jt)->task_name << " ";
3557 }
3558 cerr << " : sleeping" << endl;
3559 }
3560 #endif
3561 COND_WAIT(_mutex_root, _cond_root, lck_root); //
3562 #ifdef DEBUG_EXEC_THREAD_IDLE
3563 {
3564 cerr << "\t" << pid
3565 << " waked up : _waiting_root = " << (int)_waiting_root
3566 << endl;
3567 }
3568 #endif
3569 _waiting_root--;
3570 // other thread broacast wake up and decreasing _waiting_root
3571 waiting1 = check_parents_done(kt, _mutex_dependency);
3572 MUTEX_UNLOCK(_mutex_root);
3573 } // scope of mutex
3574 //#endif
3575 } // while (waiting > 0)
3576 if (waiting1 == (-1)) {
3577 #ifdef DEBUG_EXEC_THREAD
3578 {
3579 MUTEX_LOCK(_mutex_debug, lck_debug);
3580 cerr << pid << " pod = " << pos << " : "
3581 << (*it->queue)[pos + i]->task_name
3582 << " : " << it->task_name << " quitted..." << endl;
3583 MUTEX_UNLOCK(_mutex_debug);
3584 }
3585 #endif
3586 return;
3587 }
3588 execute_task(it, (pos + i),
3589 permute_block,
3590 pid, _mutex_dependency);
3591 if ((*it->queue)[pos + i]->quit_queue) {
3592 #ifdef DEBUG_EXEC_THREAD
3593 {
3594 MUTEX_LOCK(_mutex_debug, lck_debug);
3595 cerr << pid << " pos = " << pos << " atomic_size= "
3596 << (*it->queue)[pos]->atomic_size
3597 << " : " << it->task_name << " finished..."
3598 << "skip " << (*it->queue)[pos + i]->to_next_task
3599 << " : " << __FILE__ << " : " << __LINE__
3600 << endl;
3601 MUTEX_UNLOCK(_mutex_debug);
3602 }
3603 #endif
3604 pos += (*it->queue)[pos + i]->to_next_task;
3605 return;
3606 }
3607 #ifdef DEBUG_EXEC_THREAD
3608 {
3609 MUTEX_LOCK(_mutex_debug, lck_debug);
3610 cerr << "{ "
3611 << (*it->queue)[pos + i]->task_name << " @ "
3612 << pid << " " << (pos + i) << " }";
3613 MUTEX_UNLOCK(_mutex_debug);
3614 }
3615 #endif
3616 } // loop : i
3617 // static tasks are assigned by other thread
3618 if (finish_group) {
3619 #ifdef DEBUG_EXEC_THREAD
3620 {
3621 MUTEX_LOCK(_mutex_debug, lck_debug);
3622 cerr << pid << " C_FULL : the first greedy end the queue."
3623 << it->pos << endl;
3624 MUTEX_UNLOCK(_mutex_debug);
3625 }
3626 #endif
3627 { // scope of mutex
3628 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3629 pos = it->pos;
3630 for (int p = 0; p < it->num_threads; p++) {
3631 _begins_group[pid_g][p][gidxn] = pos;
3632 _ends_group[pid_g][p][gidxn] = pos;
3633 }
3634 _grp_static_assigned[gidxn] = 1;
3635 MUTEX_UNLOCK(_mutex_group[pid_g]);
3636 } // scope of mutex
3637 continue;
3638 }
3639 { // scope of mutex
3640 MUTEX_LOCK(_mutex_root, lck_root);
3641 zone_flag = (_zone_entered[zone_idxn] == num_threads);
3642 MUTEX_UNLOCK(_mutex_root);
3643 } // scope of mutex
3644 } // while (zone_flag)
3645 #ifdef DEBUG_EXEC_THREAD
3646 {
3647 MUTEX_LOCK(_mutex_debug, lck_debug);
3648 cerr << pid << " pid_g = " << pid_g << " pid0 " << pid0
3649 << " group " << (group - 1) // after increment of group
3650 << " zone_flag = " << zone_flag
3651 << endl;
3652 MUTEX_UNLOCK(_mutex_debug);
3653 }
3654 #endif
3655 #endif
3656 if (group_last_entered) {
3657 //
3658 long nops, nops_total, nops_static, nops_per_thread;
3659 nops = 0L;
3660 nops_total = 0L;
3661 { // scope of mutex
3662 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3663 pos = it->pos;
3664 MUTEX_UNLOCK(_mutex_group[pid_g]);
3665 } // scope of mutex
3666 if (pos == it->end) {
3667 break;
3668 }
3669 const int queue_size = ((*it->queue)[pos]->parallel_max -
3670 (*it->queue)[pos]->parallel_id);
3671 if (queue_size < it->num_threads) {
3672 { // scope of mutex
3673 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3674 pos = it->pos;
3675 for (int p = 0; p < it->num_threads; p++) {
3676 _begins_group[pid_g][p][gidxn] = pos;
3677 _ends_group[pid_g][p][gidxn] = pos;
3678 }
3679 _grp_static_assigned[gidxn] = 1;
3680 MUTEX_UNLOCK(_mutex_group[pid_g]);
3681 } // scope of mutex
3682 }
3683 else {
3684 { // scope of mutex
3685 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3686 pos = it->pos;
3687 int jj = pos;
3688 for (int i = (*it->queue)[pos]->parallel_id;
3689 i < (*it->queue)[pos]->parallel_max; i++) {
3690 // atomic_size
3691 const int itmp = jj;
3692 for (int j = 0; j < (*it->queue)[itmp]->atomic_size;
3693 j++, jj++) {
3694 nops_total += *((*it->queue)[jj]->ops_complexity);
3695 }
3696 }
3697 nops_static = (long)((double)nops_total * RATIO_QUEUE_GREEDY);
3698 nops_per_thread = (nops_static / (long)it->num_threads);
3699 #ifdef DEBUG_EXEC_THREAD
3700 {
3701 MUTEX_LOCK(_mutex_debug, lck_debug);
3702 cerr << pos << " " << _grp_task_ends[gidxn] << " "
3703 << nops_total << " " << nops_per_thread << endl;
3704 MUTEX_UNLOCK(_mutex_debug);
3705 }
3706 #endif
3707 long ntmp = 0L;
3708 for (int p = 0; p < it->num_threads; p++) {
3709 if (ntmp < _group_nops[pid_g][p]) {
3710 ntmp = _group_nops[pid_g][p];
3711 }
3712 }
3713 if (ntmp >= nops_per_thread) { // greedy
3714 #ifdef DEBUG_EXEC_THREAD
3715 {
3716 MUTEX_LOCK(_mutex_debug, lck_debug);
3717 cerr << pos << " max _group_nops[pid_g][] = " << ntmp
3718 << " nops_per_threads = " << nops_per_thread << endl;
3719 MUTEX_UNLOCK(_mutex_debug);
3720 }
3721 #endif
3722 for (int p = 0; p < it->num_threads; p++) {
3723 _begins_group[pid_g][p][gidxn] = pos;
3724 _ends_group[pid_g][p][gidxn] = pos;
3725 }
3726 // _group_task_ends[pid_g][cnt_cdfull][gidxn] = end_queue;
3727 }
3728 else { // if (ntmp < nops_per_thread)
3729 _begins_group[pid_g][0][gidxn] = pos;
3730 // for fail-safe
3731 //_ends_group[pid_g][it->num_threads - 1][gidxn] = end_queue;
3732 _ends_group[pid_g][it->num_threads - 1][gidxn] =
3733 _grp_task_ends[gidxn];
3734 nops = 0L;
3735 int p = 0;
3736 for (int j = pos; j < _grp_task_ends[gidxn]; ) {
3737 for (int k = 0; k < (*it->queue)[j]->atomic_size;
3738 k++) {
3739 nops += *((*it->queue)[j + k]-> ops_complexity);
3740 }
3741 j += (*it->queue)[j]->atomic_size;
3742 // do not devide atomic operation
3743 if (nops > nops_per_thread) {
3744 _ends_group[pid_g][p][gidxn] = j;
3745 p++;
3746 if (p == it->num_threads) {
3747 break;
3748 }
3749 _begins_group[pid_g][p][gidxn] = j;
3750 nops = 0L;
3751 } // if
3752 } // loop : j
3753 if (p < it->num_threads) {
3754 // static assignment is failed.
3755 #ifdef DEBUG_EXEC_THREAD
3756 {
3757 MUTEX_LOCK(_mutex_debug, lck_debug);
3758 cerr << pid << "pid_g = " << pid_g << " gidxn = " << gidxn
3759 << " : pos = " << pos << " static assignment is failed"
3760 << endl;
3761 MUTEX_UNLOCK(_mutex_debug);
3762 }
3763 #endif
3764 for (int j = 0; j < it->num_threads; j++) {
3765 _begins_group[pid_g][j][gidxn] = pos;
3766 _ends_group[pid_g][j][gidxn] = pos;
3767 }
3768 }
3769 it->pos = _ends_group[pid_g][it->num_threads - 1][gidxn];
3770 // cerr << pid << " pos = " << it->pos << endl;
3771 // _group_task_ends[pid_g][cnt_cdfull][gidxn] = end_queue;
3772 } // if (ntmp < nops_per_thread)
3773 _grp_static_assigned[gidxn] = 1;
3774 MUTEX_UNLOCK(_mutex_group[pid_g]);
3775 } // scope of mutex
3776 } // if (queue_size < it->num_threads)
3777 #ifdef DEBUG_EXEC_THREAD
3778 {
3779 MUTEX_LOCK(_mutex_debug, lck_debug);
3780 cerr << pid << " : ";
3781 for (int p = 0; p < it->num_threads; p++) {
3782 cerr << "[ " << _begins_group[pid_g][p][gidxn]
3783 << " : " << _ends_group[pid_g][p][gidxn] << " ] ";
3784 }
3785 cerr << _grp_task_ends[gidxn] << endl;
3786 MUTEX_UNLOCK(_mutex_debug);
3787 }
3788 #endif
3789 } // if (group_last_entered)
3790 else {
3791 int group_task_end, group_static_assigned;
3792 { // scope of mutex
3793 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3794 group_task_end = _grp_task_ends[gidxn];
3795 group_static_assigned = _grp_static_assigned[gidxn];
3796 pos = it->pos;
3797 MUTEX_UNLOCK(_mutex_group[pid_g]);
3798 } // scope of mutex
3799 #ifdef DEBUG_EXEC_THREAD
3800 {
3801 MUTEX_LOCK(_mutex_debug, lck_debug);
3802 cerr << pid << " pos = " << pos << " gidxn = " << gidxn
3803 << " group_task_end " << group_task_end
3804 << " group_static_assigned " << group_static_assigned
3805 << endl;
3806 MUTEX_UNLOCK(_mutex_debug);
3807 }
3808 #endif
3809 if (pos == it->end && (group_static_assigned == 0)) {
3810 // not yet static assigned but queue is exhausted
3811 #ifdef DEBUG_EXEC_THREAD
3812 {
3813 MUTEX_LOCK(_mutex_debug, lck_debug);
3814 cerr << pid << " pod = " << pos << "it->end = " << it->end
3815 << " : " << it->task_name << " finished." << endl;
3816 MUTEX_UNLOCK(_mutex_debug);
3817 }
3818 #endif
3819 return;
3820 }
3821 // include group_static_assigned == (-1) : 21 Jun.2012, Atsushi
3822 while (group_static_assigned != 1) { // greedy
3823 int exit_flag = 0;
3824 // to skip un-necessary access to _dynamic_queue
3825 { // scope of mutex
3826 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3827 pos = it->pos;
3828 if (pos == it->end) {
3829 exit_flag = 1;
3830 }
3831 MUTEX_UNLOCK(_mutex_group[pid_g]);
3832 } // scope of mutex
3833 if (exit_flag) {
3834 #ifdef DEBUG_EXEC_THREAD
3835 {
3836 MUTEX_LOCK(_mutex_debug, lck_debug);
3837 cerr << pid << " pod = " << pos << "it->end = " << it->end
3838 << " : " << it->task_name << " already finished." << endl;
3839 MUTEX_UNLOCK(_mutex_debug);
3840 }
3841 #endif
3842 return;
3843 }
3844 // looking for dynamic queue
3845 int flag = 1;
3846 // include group_static_assigned == (-1) : 21 Jun.2012, Atsushi
3847 while ((flag == 1) && (group_static_assigned != 1)) {
3848 flag = execute_task_dynamic_buffer(permute_block,
3849 pid,
3850 _mutex_dependency);
3851 { // scope of mutex
3852 // std::unique_lock<std::mutex>lck_root(_mutex_group[pid_g]);
3853 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3854 group_static_assigned = _grp_static_assigned[gidxn];
3855 MUTEX_UNLOCK(_mutex_group[pid_g]);
3856 } // scope of mutex
3857 } // while ((flag == 1) && (group_static_assigned != 0))
3858 if (group_static_assigned) {
3859 break;
3860 }
3861 // get tasks with atomic_size from the queue : *it
3862 int itmp, jtmp;
3863 { // scope of mutex
3864 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3865 pos = it->pos;
3866 // do not increase queue more than its size
3867 if (pos == it->end) {
3868 exit_flag = 1;
3869 }
3870 else {
3871 // there might be segments with more than 1 automic size
3872 // between parallel_id and parallel_max
3873 itmp = pos + (*it->queue)[pos]->atomic_size;
3874 jtmp = (itmp - 1 + ((*it->queue)[pos]->parallel_max -
3875 (*it->queue)[pos]->parallel_id));
3876 #ifdef DEBUG_EXEC_THREAD
3877 {
3878 MUTEX_LOCK(_mutex_debug, lck_debug);
3879 cerr << pid << " pos = " << pos << " +atomic_size = " << itmp
3880 << " parallel_max " << jtmp << " : " << it->end
3881 << endl;
3882 MUTEX_UNLOCK(_mutex_debug);
3883 }
3884 #endif
3885 if (itmp <= jtmp) {
3886 it->pos = itmp;
3887 }
3888 }
3889 MUTEX_UNLOCK(_mutex_group[pid_g]);
3890 } // scope of mutex
3891 if (exit_flag) {
3892 #ifdef DEBUG_EXEC_THREAD
3893 {
3894 MUTEX_LOCK(_mutex_debug, lck_debug);
3895 cerr << pid << " pod = " << pos << "it->end = " << it->end
3896 << " : " << it->task_name << " already finished.." << endl;
3897 MUTEX_UNLOCK(_mutex_debug);
3898 }
3899 #endif
3900 return;
3901 }
3902 if (itmp == jtmp) {
3903 #ifdef DEBUG_EXEC_THREAD
3904 {
3905 MUTEX_LOCK(_mutex_debug, lck_debug);
3906 cerr << pid << " pos = " << pos << " jtmp = " << jtmp << endl;
3907 MUTEX_UNLOCK(_mutex_debug);
3908 }
3909 #endif
3910 finish_group = 1;
3911 }
3912 // reserve tasks and conunt estimated job size
3913 { // scope of mutex
3914 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
3915 for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
3916 _group_nops[pid_g][pid0] +=
3917 *((*it->queue)[pos + i]->ops_complexity);
3918 }
3919 MUTEX_UNLOCK(_mutex_group[pid_g]);
3920 } // scope of mutex
3921 #ifdef DEBUG_EXEC_THREAD
3922 {
3923 MUTEX_LOCK(_mutex_debug, lck_debug);
3924 if ((*it->queue)[pos]->atomic_size > 1) {
3925 C_task *kt = (*it->queue)[pos];
3926 cerr << pid << " b-c-a " << pos << " : "
3927 << kt->task_name << " : "
3928 << kt->parents_work->size() << " / ";
3929 for (list<C_task *>::const_iterator mt = kt->parents_work->begin();
3930 mt != kt->parents_work->end(); ++mt) {
3931 cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
3932 }
3933 cerr << "before statically assigned task : with status check."
3934 << endl;
3935 }
3936 MUTEX_UNLOCK(_mutex_debug);
3937 }
3938 #endif
3939
3940 for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
3941 C_task *kt = (*it->queue)[pos + i];
3942 int waiting = check_parents_done(kt, _mutex_dependency);
3943
3944 while(waiting > 0) {
3945 //
3946 { // scope of mutex
3947 // std::unique_lock<std::mutex>lck_root(_mutex_root);
3948 MUTEX_LOCK(_mutex_root, lck_root);
3949 _waiting_root++;
3950 #ifdef DEBUG_DEADLOCK
3951 if (_waiting_root > num_threads) {
3952 fprintf(stderr, "dead lock occured : %s %d\n",
3953 __FILE__, __LINE__);
3954 exit(-1);
3955 }
3956 #endif
3957 #ifdef DEBUG_EXEC_THREAD_IDLE
3958 {
3959 cerr << pid << " " << kt->task_name << " "
3960 << "waiting = "<< waiting << " : "
3961 << (int)_waiting_root << " "
3962 << __FILE__ << " " << __LINE__ << " ";
3963 for (list<C_task *>::const_iterator jt = kt->parents_work->begin();
3964 jt != kt->parents_work->end(); ++jt) {
3965 cerr << (*jt)->task_name << " ";
3966 }
3967 cerr << " : sleeping" << endl;
3968 }
3969 #endif
3970 COND_WAIT(_mutex_root, _cond_root, lck_root); //
3971 #ifdef DEBUG_EXEC_THREAD_IDLE
3972 {
3973 cerr << "\t" << pid
3974 << " waked up : _waiting_root = " << (int)_waiting_root
3975 << endl;
3976 }
3977 #endif
3978
3979 _waiting_root--;
3980 // other thread broacast wake up and decreasing _waiting_root
3981 waiting = check_parents_done(kt, _mutex_dependency);
3982 MUTEX_UNLOCK(_mutex_root);
3983 } // scope of mutex
3984 } // while (waiting > 0)
3985 if (waiting == (-1)) {
3986 #ifdef DEBUG_EXEC_THREAD
3987 {
3988 MUTEX_LOCK(_mutex_debug, lck_debug);
3989 cerr << pid << " pod = " << pos + i << " : "
3990 << (*it->queue)[pos + i]->task_name
3991 << " : " << it->task_name << " quitted..." << endl;
3992 MUTEX_UNLOCK(_mutex_debug);
3993 }
3994 #endif
3995 return;
3996 }
3997 execute_task(it, (pos + i),
3998 permute_block,
3999 pid, _mutex_dependency);
4000 if ((*it->queue)[pos + i]->quit_queue) {
4001 #ifdef DEBUG_EXEC_THREAD
4002 {
4003 MUTEX_LOCK(_mutex_debug, lck_debug);
4004 cerr << pid << " pos = " << pos << " atomic_size= "
4005 << (*it->queue)[pos]->atomic_size
4006 << " : " << it->task_name << " finished..."
4007 << "skip " << (*it->queue)[pos + i]->to_next_task
4008 << " : " << __FILE__ << " : " << __LINE__
4009 << endl;
4010 MUTEX_UNLOCK(_mutex_debug);
4011 }
4012 #endif
4013 pos += (*it->queue)[pos + i]->to_next_task;
4014 return;
4015 // break;
4016 }
4017 #ifdef DEBUG_EXEC_THREAD
4018 {
4019 MUTEX_LOCK(_mutex_debug, lck_debug);
4020 cerr << "{ "
4021 << (*it->queue)[pos + i]->task_name << " @ "
4022 << pid << " " << (pos + i) << " }";
4023 MUTEX_UNLOCK(_mutex_debug);
4024 }
4025 #endif
4026 } // loop : i
4027 // static tasks are assigned by other thread
4028 { // scope of mutex
4029 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
4030 group_static_assigned = _grp_static_assigned[gidxn];
4031 if ((finish_group == 1) && (group_static_assigned == 0)) {
4032 // static task is not assigned but queue becomes empty
4033 for (int p = 0; p < it->num_threads; p++) {
4034 _begins_group[pid_g][p][gidxn] = (-1);
4035 _ends_group[pid_g][p][gidxn] = (-1);
4036 }
4037 _grp_task_ends[gidxn] = jtmp;
4038 }
4039 MUTEX_UNLOCK(_mutex_group[pid_g]);
4040 } // scope of mutex
4041 if (finish_group) {
4042 #ifdef DEBUG_EXEC_THREAD
4043 {
4044 MUTEX_LOCK(_mutex_debug, lck_debug);
4045 cerr << pid << " C_FULL : the first greedy end the queue."
4046 << it->pos << endl;
4047 MUTEX_UNLOCK(_mutex_debug);
4048 }
4049 #endif
4050 { // scope of mutex
4051 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
4052 pos = it->pos;
4053 for (int p = 0; p < it->num_threads; p++) {
4054 _begins_group[pid_g][p][gidxn] = pos;
4055 _ends_group[pid_g][p][gidxn] = pos;
4056 }
4057 _grp_static_assigned[gidxn] = 1;
4058 MUTEX_UNLOCK(_mutex_group[pid_g]);
4059 } // scope of mutex
4060 continue;
4061 }
4062 // just for debugging : group_task_end >=0 <=> braek while ( < 0 )
4063 #ifdef DEBUG_EXEC_THREAD
4064 if (group_static_assigned) {
4065 {
4066 MUTEX_LOCK(_mutex_debug, lck_debug);
4067 cerr << pid << " end the first greedy "
4068 << it->pos << endl;
4069 MUTEX_UNLOCK(_mutex_debug);
4070 }
4071 }
4072 #endif
4073 } // while (group_static_assigned != 1)
4074 } // if (group_last_entered)
4075 // static assignment
4076 int _begin_grp, _end_grp;
4077
4078 if ( _grp_static_assigned[gidxn] == (-1)) {
4079 // this never happen?
4080 _begin_grp = _end_grp = (-1);
4081 #ifdef DEBUG_EXEC_THREAD_21Jun2012
4082 {
4083 MUTEX_LOCK(_mutex_debug, lck_debug);
4084 cerr << pid << ": pid0 = " << pid0 << " gidxn = " << gidxn
4085 << " static assignment is not yet done! "
4086 << endl;
4087 MUTEX_UNLOCK(_mutex_debug);
4088 }
4089 #endif
4090 }
4091 else {
4092 _begin_grp = _begins_group[pid_g][pid0][gidxn];
4093 _end_grp = _ends_group[pid_g][pid0][gidxn];
4094 }
4095
4096 #ifdef DEBUG_EXEC_THREAD
4097 {
4098 MUTEX_LOCK(_mutex_debug, lck_debug);
4099 cerr << pid << ": pid0 = " << pid0 << " gidxn = " << gidxn
4100 << " < " << _begin_grp << " " << _end_grp << " > assigned"
4101 << endl;
4102 MUTEX_UNLOCK(_mutex_debug);
4103 }
4104 #endif
4105 for (int i = _begin_grp; i < _end_grp; i++) {
4106 // no need to check dependency for static assignement
4107 execute_task(it, i, permute_block,
4108 pid);
4109 if ((*it->queue)[i]->quit_queue) {
4110 fprintf(stderr, "%d i = %d : %s finished ... skip %d\n",
4111 pid, i, it->task_name,
4112 (*it->queue)[i]->to_next_task);
4113 i += (*it->queue)[i]->to_next_task;
4114 }
4115 #ifdef DEBUG_EXEC_THREAD
4116 {
4117 MUTEX_LOCK(_mutex_debug, lck_debug);
4118 cerr << "( "
4119 << (*it->queue)[i]->task_name << " @ "
4120 << pid << " " << i << " )";
4121 MUTEX_UNLOCK(_mutex_debug);
4122 }
4123 #endif
4124 } // loop : i
4125 // greedy
4126 while(1) {
4127 int group_task_end;
4128 { // scope of mutex
4129 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
4130 pos = it->pos;
4131 group_task_end = _grp_task_ends[gidxn];
4132 if (pos < group_task_end) {
4133 const int itmp = (it->pos +
4134 (*it->queue)[pos]->atomic_size);
4135 if (itmp <= group_task_end) {
4136 it->pos = itmp;
4137 }
4138 }
4139 MUTEX_UNLOCK(_mutex_group[pid_g]);
4140 } // scope of mutex
4141 if (pos >= group_task_end) {
4142 break;
4143 }
4144 if (_begin_grp < _end_grp) {
4145 // <==> statically assigned block is computed
4146 #ifdef DEBUG_EXEC_THREAD
4147 {
4148 MUTEX_LOCK(_mutex_debug, lck_debug);
4149 if ((*it->queue)[pos]->atomic_size > 1) {
4150 C_task *kt = (*it->queue)[pos];
4151 cerr << pid << " b-c-a " << pos << " : " << kt->task_name << " : "
4152 << kt->parents_work->size() << " / ";
4153
4154 for (list<C_task *>::const_iterator mt = kt->parents_work->begin();
4155 mt != kt->parents_work->end(); ++mt) {
4156 cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
4157 }
4158 cerr << "within statically assigned task : without status check."
4159 << endl;
4160 }
4161 MUTEX_UNLOCK(_mutex_debug);
4162 }
4163 #endif
4164 for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
4165 execute_task(it, (pos + i), permute_block,
4166 pid,
4167 _mutex_group[pid_g]);
4168 if ((*it->queue)[pos + i]->quit_queue) {
4169 #ifdef DEBUG_EXEC_THREAD
4170 {
4171 MUTEX_LOCK(_mutex_debug, lck_debug);
4172 cerr << pid << " pos = " << pos << " atomic_size= "
4173 << (*it->queue)[pos]->atomic_size
4174 << " : " << it->task_name << " finished..."
4175 << "skip " << (*it->queue)[pos + i]->to_next_task
4176 << endl;
4177 MUTEX_UNLOCK(_mutex_debug);
4178 }
4179 #endif
4180 // const int ibegin = pos + i + 1;
4181 pos += (*it->queue)[pos + i]->to_next_task;
4182 return;
4183 // break;
4184 }
4185 #ifdef DEBUG_EXEC_THREAD
4186 {
4187 MUTEX_LOCK(_mutex_debug, lck_debug);
4188 cerr << "( "
4189 << (*it->queue)[pos + i]->task_name << " @ "
4190 << pid << " " << (pos + i) << " )";
4191 MUTEX_UNLOCK(_mutex_debug);
4192 }
4193 #endif
4194 } // loop : i
4195 } // if (_begins_grp == _ends_grp)
4196 else {
4197 // <==> no statically assigned block
4198 #ifdef DEBUG_EXEC_THREAD
4199 {
4200 MUTEX_LOCK(_mutex_debug, lck_debug);
4201 if ((*it->queue)[pos]->atomic_size > 1) {
4202 C_task *kt = (*it->queue)[pos];
4203 cerr << pid << " b-c-a " << pos << " : " << kt->task_name << " : "
4204 << kt->parents_work->size() << " / ";
4205
4206 for (list<C_task *>::const_iterator mt = kt->parents_work->begin();
4207 mt != kt->parents_work->end(); ++mt) {
4208 cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
4209 }
4210 cerr << "no statically assigned task : with status check." << endl;
4211 }
4212 MUTEX_UNLOCK(_mutex_debug);
4213 }
4214 #endif
4215 for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
4216 C_task *kt = (*it->queue)[pos + i];
4217 int waiting = check_parents_done(kt, _mutex_dependency);
4218 while(waiting > 0) {
4219 { // scope of mutex
4220 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4221 MUTEX_LOCK(_mutex_root, lck_root);
4222 _waiting_root++;
4223 #ifdef DEBUG_DEADLOCK
4224 if (_waiting_root > num_threads) {
4225 fprintf(stderr, "dead lock occured : %s %d\n",
4226 __FILE__, __LINE__);
4227 exit(-1);
4228 }
4229 #endif
4230 #ifdef DEBUG_EXEC_THREAD_IDLE
4231 {
4232 cerr << pid << " " << kt->task_name << " "
4233 << "waiting = " << waiting
4234 << " : " << (int)_waiting_root << " : "
4235 << __FILE__ << " " << __LINE__ << " ";
4236 for (list<C_task *>::const_iterator jt = kt->parents_work->begin();
4237 jt != kt->parents_work->end(); ++jt) {
4238 cerr << (*jt)->task_name << " ";
4239 }
4240 cerr << " : sleeping" << endl;
4241 }
4242 #endif
4243 COND_WAIT(_mutex_root, _cond_root, lck_root); //
4244 _waiting_root--;
4245 #ifdef DEBUG_EXEC_THREAD_IDLE
4246 {
4247 cerr << endl
4248 << pid << " " << kt->task_name << " "
4249 << " waked up : _waiting_root = " << (int)_waiting_root
4250 << endl;
4251 }
4252 #endif
4253 waiting = check_parents_done(kt, _mutex_dependency);
4254 MUTEX_UNLOCK(_mutex_root);
4255 } // scope of mutex
4256 } // while (waiting > 0)
4257 if (waiting == (-1)) {
4258 #ifdef DEBUG_EXEC_THREAD
4259 {
4260 MUTEX_LOCK(_mutex_debug, lck_debug);
4261 cerr << pid << " pod = " << pos + i << " : "
4262 << (*it->queue)[pos + i]->task_name
4263 << " : " << it->task_name << " quitted..." << endl;
4264 MUTEX_UNLOCK(_mutex_debug);
4265 }
4266 #endif
4267 return;
4268 } // if (wating == (-1))
4269 execute_task(it, (pos + i), permute_block,
4270 pid,
4271 _mutex_group[pid_g]);
4272
4273 if ((*it->queue)[pos + i]->quit_queue) {
4274 #ifdef DEBUG_EXEC_THREAD
4275 {
4276 MUTEX_LOCK(_mutex_debug, lck_debug);
4277 cerr << pid << " i = " << i
4278 << " : " << it->task_name << " finished... skip "
4279 << (*it->queue)[pos + i]->to_next_task << endl;
4280 MUTEX_UNLOCK(_mutex_debug);
4281 }
4282 #endif
4283 // const int ibegin = pos + i + 1;
4284 i += (*it->queue)[pos + i]->to_next_task;
4285 return;
4286 } // if (quit_queue)
4287 #ifdef DEBUG_EXEC_THREAD
4288 {
4289 MUTEX_LOCK(_mutex_debug, lck_debug);
4290 cerr << "( "
4291 << (*it->queue)[pos + i]->task_name << " @ "
4292 << pid << " " << (pos + i) << " )";
4293 MUTEX_UNLOCK(_mutex_debug);
4294 }
4295 #endif
4296 } // loop : i
4297 } // // if (_begin_grp <_end_grp)
4298 } // while (1)
4299 #ifdef DEBUG_EXEC_THREAD
4300 {
4301 MUTEX_LOCK(_mutex_debug, lck_debug);
4302 cerr << pid << " finish " << group
4303 << " pos = " << it->pos << endl;
4304 MUTEX_UNLOCK(_mutex_debug);
4305 }
4306 #endif
4307 if (pos >= it->end) {
4308 #ifdef DEBUG_EXEC_THREAD
4309 {
4310 MUTEX_LOCK(_mutex_debug, lck_debug);
4311 cerr << pid << " pod = " << pos << "it->end = " << it->end
4312 << " : " << it->task_name << " finished..." << endl;
4313 MUTEX_UNLOCK(_mutex_debug);
4314 }
4315 #endif
4316 return;
4317 }
4318 { // scope of mutex
4319 MUTEX_LOCK(_mutex_group[pid_g], lck_root);
4320 group_first_finished = 0;
4321 if (_grp_finished[gidxn] == 0) {
4322 group_first_finished = 1;
4323 }
4324 _grp_finished[gidxn]++;
4325 if (_grp_finished[gidxn] == it->num_threads) {
4326 // clear status of cyclic buffer
4327 _grp_finished[gidxp] = 0;
4328 }
4329 MUTEX_UNLOCK(_mutex_group[pid_g]);
4330 } // scope of mutex
4331 } // while (1)
4332 }
4333
4334 void QueueRuntime::thread_queue_parallel_dynamic(const int pid,
4335 const int num_threads,
4336 C_task_seq *it,
4337 int *permute_block,
4338 const int zone_idxn)
4339 {
4340 // completely greedy
4341 int pos, end, atomic_size, atomic_id, update_flag;
4342 while(1) {
4343 { // scope of mutex
4344 MUTEX_LOCK(_mutex_root, lck_root);
4345 pos = it->pos;
4346 end = it->end;
4347 if (pos < end) {
4348 atomic_size = (*it->queue)[pos]->atomic_size;
4349 atomic_id = (*it->queue)[pos]->atomic_id;
4350 it->pos += atomic_size; // it->pos++;
4351 if (it->pos >= end) {
4352 update_flag = 1;
4353 }
4354 }
4355 MUTEX_UNLOCK(_mutex_root);
4356 } // scope of mutex
4357 if (pos >= end) {
4358 break;
4359 }
4360 C_task *kt = (*it->queue)[pos]; // [pos + atomic_size - 1];
4361 int waiting = check_parents_done(kt, _mutex_dependency);
4362 while (waiting > 0) {
4363 // looking for dynamic queue
4364 int flag = execute_task_dynamic_buffer(permute_block,
4365 pid,
4366 _mutex_dependency);
4367 if (flag != 1) {
4368 while(waiting > 0) {
4369 { // scope of mutex
4370 MUTEX_LOCK(_mutex_root, lck_root);
4371 _waiting_root++;
4372 #ifdef DEBUG_DEADLOCK
4373 if (_waiting_root > num_threads) {
4374 fprintf(stderr, "dead lock occured : %s %d\n",
4375 __FILE__, __LINE__);
4376 exit(-1);
4377 }
4378 #endif
4379 #ifdef DEBUG_EXEC_THREAD_IDLE
4380 {
4381 cerr << pid << " " << kt->task_name << " "
4382 << "waiting = "<< waiting << " : "
4383 << (int)_waiting_root << " : "
4384 << __FILE__ << " " << __LINE__ << " ";
4385 for (list<C_task *>::const_iterator jt = kt->parents_work->begin();
4386 jt != kt->parents_work->end(); ++jt) {
4387 cerr << (*jt)->task_name << " ";
4388 }
4389 cerr << " : sleeping" << endl;
4390 }
4391 #endif
4392 COND_WAIT(_mutex_root, _cond_root, lck_root); //
4393 #ifdef DEBUG_EXEC_THREAD_IDLE
4394 {
4395 cerr << endl
4396 << pid << " " << kt->task_name << " "
4397 << " waked up : _waiting_root = " << (int)_waiting_root
4398 << endl;
4399 }
4400 #endif
4401 _waiting_root--;
4402 // other thread broacast wake up and decreasing _waiting_root
4403 MUTEX_UNLOCK(_mutex_root);
4404 } // scope of mutex
4405 waiting = check_parents_done(kt, _mutex_dependency);
4406 } // while (waiting > 0)
4407 } // if (flag != 1)
4408 waiting = check_parents_done(kt, _mutex_dependency);
4409 } // while (waiting > 0)
4410 for (int m = 0; m < atomic_size; m++) {
4411 execute_task(it, (pos + m), permute_block, // loop with atomic_size
4412 pid,
4413 _mutex_dependency);
4414 }
4415 if ((*it->queue)[pos]->quit_queue) {
4416 #ifdef DEBUG_EXEC_THREAD
4417 {
4418 MUTEX_LOCK(_mutex_debug, lck_debug);
4419 cerr << pid << " pos = " << pos
4420 << " : " << it->task_name << " finished..."
4421 << "skip " << (*it->queue)[pos]->to_next_task
4422 << endl;
4423 MUTEX_UNLOCK(_mutex_debug);
4424 }
4425 #endif
4426 // const int ibegin = pos + 1;
4427 pos += (*it->queue)[pos]->to_next_task;
4428 } // if (quit_queue)
4429 #ifdef DEBUG_EXEC_THREAD
4430 {
4431 MUTEX_LOCK(_mutex_debug, lck_debug);
4432 cerr << "( " << pid << " " << pos << " ) " ;
4433 MUTEX_UNLOCK(_mutex_debug);
4434 }
4435 #endif
4436 } // while (1)
4437 #ifdef DEBUG_EXEC_THREAD
4438 {
4439 MUTEX_LOCK(_mutex_debug, lck_debug);
4440 cerr << pid << " " << it->task_name
4441 << " @ " << it->task_id << " greedy end." << endl;
4442 MUTEX_UNLOCK(_mutex_debug);
4443 }
4444 #endif
4445 }
4446
4447 void QueueRuntime::thread_queue_parallel_static(const int pid,
4448 const int num_threads,
4449 C_task_seq* it,
4450 int *permute_block,
4451 const int zone_idxp,
4452 const int zone_idxn,
4453 const int zone_first_entered,
4454 const int zone_last_entered)
4455 {
4456 // the last thread which turns into the zone assigns jobs statiscally
4457 int pos, end, atomic_size, atomic_id;
4458 int finished_status = 0;
4459 { // scope of mutex
4460 MUTEX_LOCK(_mutex_root, lck_root);
4461 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4462 pos = it->pos;
4463 MUTEX_UNLOCK(_mutex_root);
4464 } // scope of mutex
4465 // reach the end before all threads entered
4466 if (pos == it->end) {
4467 return;
4468 }
4469 if (zone_last_entered) {
4470 long nops, nops_total, nops_static, nops_per_thread;
4471 int begin, end;
4472 // this mutex is relatively larage
4473 // : lock out other threads until assingnment is finished
4474 { // scope of mutex
4475 MUTEX_LOCK(_mutex_root, lck_root);
4476 begin = it->pos;
4477 end = it->end;
4478 if ((end - begin) < num_threads) {
4479 // execute tasks by greedy way
4480 for (int q = 0; q < num_threads; q++) {
4481 _begins[q][zone_idxn] = _ends[q][zone_idxn] = pos;
4482 }
4483 _zone_static_assigned[zone_idxn] = 1;
4484 }
4485 else {
4486 // nops_total = it->ops_complexity;
4487 nops_total = 0L;
4488 for (int j = begin; j < end; j++) {
4489 nops_total += *((*it->queue)[j]->ops_complexity);
4490 // 28 May 2012 : Atsushi
4491 // cerr << (*it->queue)[j]->task_name
4492 // << *((*it->queue)[j]->ops_complexity) << " ";
4493 }
4494 //cerr << endl;
4495
4496 nops_static = (long)((double)nops_total * RATIO_QUEUE_GREEDY);
4497 nops_per_thread = nops_static / (long)num_threads;
4498 #ifdef DEBUG_EXEC_THREAD
4499 {
4500 MUTEX_LOCK(_mutex_debug, lck_debug);
4501 cerr << pid << " begin = " << begin << " end = "
4502 << end << " "
4503 << nops_total << " " << nops_static << " "
4504 << nops_per_thread << endl;
4505 MUTEX_UNLOCK(_mutex_debug);
4506 }
4507 #endif
4508 _begins[0][zone_idxn] = begin;
4509 _ends[num_threads - 1][zone_idxn] = end;
4510 nops = 0L;
4511 int p = 0;
4512 for (int j = begin; j < end; j++) {
4513 nops += *((*it->queue)[j]->ops_complexity);
4514 if (nops > nops_per_thread) {
4515 // && ((*it->queue)[j]->atomic_size == // 13 May 2014
4516 // ((*it->queue)[j]->atomic_id + 1))) {
4517 const int jj = j - (*it->queue)[j]->atomic_id;
4518 _ends[p][zone_idxn] = jj;
4519 p++;
4520 if (p == num_threads) {
4521 break;
4522 }
4523 _begins[p][zone_idxn] = jj;
4524 nops = 0L;
4525 }
4526 } // loop : j
4527 if (p < num_threads) { // equally assignment is failed
4528 // execute tasks by greedy way
4529 for (int q = 0; q < num_threads; q++) {
4530 _begins[q][zone_idxn] = _ends[q][zone_idxn] = pos;
4531 }
4532 }
4533 else {
4534 it->pos = _ends[num_threads - 1][zone_idxn];
4535 }
4536 _zone_static_assigned[zone_idxn] = 1;
4537 }
4538 MUTEX_UNLOCK(_mutex_root);
4539 } // scope of mutex
4540 #ifdef DEBUG_EXEC_THREAD
4541 {
4542 MUTEX_LOCK(_mutex_debug, lck_debug);
4543 for (int p = 0; p < num_threads; p++) {
4544 cerr << "[ " << _begins[p][zone_idxn]
4545 << " : " << _ends[p][zone_idxn] << " ] ";
4546 }
4547 cerr << it->pos << endl;
4548 MUTEX_UNLOCK(_mutex_debug);
4549 }
4550 #endif
4551 //
4552 } // if (zone_last_entered)
4553 else { // if (zone_last_entered)
4554 int zone_static_assigned = 0;
4555 while(zone_static_assigned == 0) {
4556 // similar to the routine : execute_task_dynamic_buffer()
4557 { // scope of mutex
4558 MUTEX_LOCK(_mutex_root, lck_root);
4559 zone_static_assigned = _zone_static_assigned[zone_idxn];
4560 if (zone_static_assigned == 0) {
4561 pos = it->pos;
4562 end = it->end;
4563 if (pos < end) {
4564 atomic_size = (*it->queue)[pos]->atomic_size;
4565 atomic_id = (*it->queue)[pos]->atomic_id;
4566 it->pos += atomic_size; // pos++;
4567 if (it->pos >= end) {
4568 finished_status = 1;
4569 //
4570 _phase_dynamic++;
4571 if (_phase_dynamic == _queue_dynamic->size()) {
4572 _phase_dynamic = (-1);
4573 }
4574 // queue is exhaused by this step and enforcing other tasks to quit
4575 for (int p = 0; p < num_threads; p++) {
4576 _begins[p][zone_idxn] = _ends[p][zone_idxn] = end;
4577 }
4578 } // if (it->pos == end) {
4579 }
4580 } // if (zone_static_assigned == 0)
4581 #ifdef DEBUG_EXEC_THREAD
4582 {
4583 MUTEX_LOCK(_mutex_debug, lck_debug);
4584 cerr << pid << " pos = " << pos << " zone_idxn = " << zone_idxn
4585 << " zone_static_assigned " << zone_static_assigned << " : "
4586 << _zone_static_assigned[zone_idxn]
4587 << endl;
4588 MUTEX_UNLOCK(_mutex_debug);
4589 }
4590 #endif
4591 MUTEX_UNLOCK(_mutex_root);
4592 } // scope of mutex
4593 if (zone_static_assigned == 1) {
4594 break;
4595 }
4596 if (pos >= end) {
4597 // skip my task
4598 _begins[pid][zone_idxn] = _ends[pid][zone_idxn] = end;
4599 #ifdef DEBUG_EXEC_THREAD
4600 {
4601 MUTEX_LOCK(_mutex_debug, lck_debug);
4602 cerr << pid << " queue is already exhausted "
4603 << it->pos << endl;
4604 MUTEX_UNLOCK(_mutex_debug);
4605 }
4606 #endif
4607 break;
4608 }
4609 C_task *kt = (*it->queue)[pos]; // [pos + atomic_size - 1];
4610 int waiting = check_parents_done(kt, _mutex_dependency);
4611 if (waiting > 0) {
4612 { // scope of mutex
4613 MUTEX_LOCK(_mutex_root, lck_root);
4614 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4615 while (waiting > 0) { // real sleeping
4616 _waiting_root++;
4617 #ifdef DEBUG_DEADLOCK
4618 if (_waiting_root > num_threads) {
4619 fprintf(stderr, "dead lock occured : %s %d\n",
4620 __FILE__, __LINE__);
4621 exit(-1);
4622 }
4623 #endif
4624 #ifdef DEBUG_EXEC_THREAD_IDLE
4625 {
4626 cerr << pid << " " << kt->task_name << " "
4627 << "waiting = "<< waiting << " : "
4628 << (int)_waiting_root << " : "
4629 << __FILE__ << " " << __LINE__ << " ";
4630 for (list<C_task *>::const_iterator jt = kt->parents_work->begin();
4631 jt != kt->parents_work->end(); ++jt) {
4632 cerr << (*jt)->task_name << " ";
4633 }
4634 cerr << " : sleeping" << endl;
4635 }
4636 #endif
4637 COND_WAIT(_mutex_root, _cond_root, lck_root);
4638 _waiting_root--;
4639 #ifdef DEBUG_EXEC_THREAD_IDLE
4640 {
4641 cerr << endl
4642 << pid << " " << kt->task_name << " "
4643 << " waked up : _waiting_root = " << (int)_waiting_root
4644 << endl;
4645 }
4646 #endif
4647 // other thread broacast wake up and decreasing _waiting_root
4648 waiting = check_parents_done(kt, _mutex_dependency);
4649 } // while (waiting > 0)
4650 MUTEX_UNLOCK(_mutex_root);
4651 } // scope of mutex
4652 } // if (waiting > 0)
4653 atomic_size = (*it->queue)[pos]->atomic_size;
4654 for (int m = 0; m < atomic_size; m++) {
4655 execute_task(it, (pos + m), permute_block, // loop with atomic_size
4656 pid, _mutex_dependency);
4657 }
4658 #ifdef DEBUG_EXEC_THREAD
4659 {
4660 MUTEX_LOCK(_mutex_debug, lck_debug);
4661 cerr << "{ " << pid << " " << pos << " }";
4662 MUTEX_UNLOCK(_mutex_debug);
4663 }
4664 #endif
4665 if (finished_status) { // && (zone_static_assigned == 0)) {
4666 #ifdef DEBUG_EXEC_THREAD
4667 {
4668 MUTEX_LOCK(_mutex_debug, lck_debug);
4669 cerr << pid << " queue is exhausted in the first greedy"
4670 << it->pos << endl;
4671 MUTEX_UNLOCK(_mutex_debug);
4672 }
4673 #endif
4674 break;
4675 }
4676 { // scope of mutex
4677 MUTEX_LOCK(_mutex_root, lck_root);
4678 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4679 it->ops_complexity -= *((*it->queue)[pos]->ops_complexity);
4680 zone_static_assigned = _zone_static_assigned[zone_idxn];
4681 MUTEX_UNLOCK(_mutex_root);
4682 } // scope of mutex
4683 #ifdef DEBUG_EXEC_THREAD
4684 if (zone_static_assigned == 1) {
4685 {
4686 MUTEX_LOCK(_mutex_debug, lck_debug);
4687 cerr << pid << " end the first greedy "
4688 << it->pos << endl;
4689 MUTEX_UNLOCK(_mutex_debug);
4690 }
4691 }
4692 #endif
4693 } // while (zone_static_assigned == 0)
4694 } // if (zone_last_entered)
4695 // static
4696 #ifdef DEBUG_EXEC_THREAD
4697 {
4698 MUTEX_LOCK(_mutex_debug, lck_debug);
4699 cerr << "pid = " << pid << " zone_idxn = " << zone_idxn
4700 << "< " << _begins[pid][zone_idxn]
4701 << " " << _ends[pid][zone_idxn] << " > assigned" << endl;
4702 MUTEX_UNLOCK(_mutex_debug);
4703 }
4704 #endif
4705
4706 for (int i = _begins[pid][zone_idxn]; i < _ends[pid][zone_idxn]; i++) {
4707 execute_task(it, i, permute_block,
4708 pid);
4709 }
4710 #ifdef DEBUG_EXEC_THREAD
4711 {
4712 MUTEX_LOCK(_mutex_debug, lck_debug);
4713 cerr << pid << ": " << "< " << _begins[pid][zone_idxn]
4714 << " " << _ends[pid][zone_idxn] << " > done." << endl;
4715 MUTEX_UNLOCK(_mutex_debug);
4716 }
4717 #endif
4718 // greedy
4719 #ifdef DEBUG_EXEC_THREAD
4720 {
4721 MUTEX_LOCK(_mutex_debug, lck_debug);
4722 cerr << pid << " "
4723 << it->task_name << " @ " << it->task_id
4724 << " greedy begin: " << endl;
4725 MUTEX_UNLOCK(_mutex_debug);
4726 }
4727 #endif
4728 while(1) {
4729 { // scope of mutex
4730 MUTEX_LOCK(_mutex_root, lck_root);
4731 pos = it->pos;
4732 end = it->end;
4733 if (pos < end) {
4734 atomic_size = (*it->queue)[pos]->atomic_size;
4735 atomic_id = (*it->queue)[pos]->atomic_id;
4736 it->pos += atomic_size; // pos++
4737 if (it->pos >= end) {
4738 finished_status = 1;
4739 _phase_dynamic++;
4740 if (_phase_dynamic == _queue_dynamic->size()) {
4741 _phase_dynamic = (-1);
4742 } // queue is exhausted
4743 #ifdef DEBUG_EXEC_THREAD
4744 {
4745 MUTEX_LOCK(_mutex_debug, lck_debug);
4746 cerr << pid << " _phase_dynamic = "
4747 << _phase_dynamic << " @ "
4748 << _queue_dynamic->size() << endl;
4749 if (_phase_dynamic >= 0) {
4750 cerr << pid << " next = "
4751 << (*_queue_dynamic)[_phase_dynamic]->task_name
4752 << endl;
4753 }
4754 MUTEX_UNLOCK(_mutex_debug);
4755 }
4756 #endif
4757 }
4758 } // if (pos < end)
4759 MUTEX_UNLOCK(_mutex_root);
4760 } // scope of mutex
4761 if (pos >= end) {
4762 #ifdef DEBUG_EXEC_THREAD
4763 {
4764 MUTEX_LOCK(_mutex_debug, lck_debug);
4765 cerr << pid << " queue is already exhausted " << endl;
4766 MUTEX_UNLOCK(_mutex_debug);
4767 }
4768 #endif
4769 break;
4770 }
4771 atomic_size = (*it->queue)[pos]->atomic_size;
4772 for (int m = 0; m < atomic_size; m++) {
4773 execute_task(it, (pos + m), permute_block, // loop with atomic_size
4774 pid,
4775 _mutex_dependency);
4776 }
4777 #ifdef DEBUG_EXEC_THREAD1
4778 {
4779 MUTEX_LOCK(_mutex_debug, lck_debug);
4780 cerr << "( " << pid << " " << pos << " : "
4781 << (*it->queue)[pos]->task_name << " ) ";
4782 MUTEX_UNLOCK(_mutex_debug);
4783 }
4784 #endif
4785
4786 if (finished_status) {
4787 break;
4788 }
4789 } // while(1)
4790 //
4791 #ifdef DEBUG_EXEC_THREAD
4792 {
4793 MUTEX_LOCK(_mutex_debug, lck_debug);
4794 cerr << pid << " greedy end : " << endl;
4795 MUTEX_UNLOCK(_mutex_debug);
4796 }
4797 #endif
4798 }
4799
4800 void QueueRuntime::thread_queue_single(const int pid,
4801 const int num_threads,
4802 C_task_seq *it,
4803 int *permute_block,
4804 const int zone_idxn)
4805 {
4806 // tasks are excuted by a single thread : atomic operation will not be divided.
4807 int start = it->begin;
4808 bool zone_flag;
4809 { // scope of mutex
4810 MUTEX_LOCK(_mutex_root, lck_root);
4811 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4812 zone_flag = (_zone_entered[zone_idxn] == num_threads);
4813 MUTEX_UNLOCK(_mutex_root);
4814 } // scope of mutex
4815 #ifdef DEBUG_EXEC_THREAD
4816 {
4817 MUTEX_LOCK(_mutex_debug, lck_debug);
4818 cerr << pid << " @ " << num_threads << " single "
4819 << it->task_name << " : " << it->task_id
4820 << " zone_flag = " << zone_flag << endl;
4821 MUTEX_UNLOCK(_mutex_debug);
4822 }
4823 #endif
4824
4825 while ((start < it->end) && (!zone_flag)) {
4826 C_task *kt = (*it->queue)[start];
4827 int waiting = check_parents_done(kt, _mutex_dependency);
4828 while(waiting > 0) {
4829 // looking for dynamic queue
4830 int flag = execute_task_dynamic_buffer(permute_block,
4831 pid,
4832 _mutex_dependency);
4833 if (flag != 1) {
4834 //
4835 int waiting2;
4836 waiting2 = check_parents_done(kt, _mutex_dependency);
4837 while(waiting2 > 0) {
4838 { // scope of mutex
4839 MUTEX_LOCK(_mutex_root, lck_root);
4840 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4841 _waiting_root++;
4842 #ifdef DEBUG_DEADLOCK
4843 if (_waiting_root > num_threads) {
4844 fprintf(stderr, "dead lock occured : %s %d\n",
4845 __FILE__, __LINE__);
4846 exit(-1);
4847 }
4848 #endif
4849 #ifdef DEBUG_EXEC_THREAD_IDLE
4850 {
4851 cerr << pid << " " << kt->task_name << " "
4852 << "waiting = "<< waiting << " : "
4853 << (int)_waiting_root << " : "
4854 << __FILE__ << " " << __LINE__ << " ";
4855 for (list<C_task *>::const_iterator jt = kt->parents_work->begin();
4856 jt != kt->parents_work->end(); ++jt) {
4857 cerr << (*jt)->task_name << " ";
4858 }
4859 cerr << " : sleeping" << endl;
4860 }
4861 #endif
4862 COND_WAIT(_mutex_root, _cond_root, lck_root);
4863 #ifdef DEBUG_EXEC_THREAD_IDLE
4864 {
4865 cerr << endl
4866 << pid << " " << kt->task_name << " "
4867 << " waked up : _waiting_root = " << (int)_waiting_root
4868 << endl;
4869 }
4870 #endif
4871 _waiting_root--;
4872 // other thread broacast wake up and decreasing _waiting_root
4873 waiting2 = check_parents_done(kt, _mutex_dependency);
4874 MUTEX_UNLOCK(_mutex_root);
4875 } // scope of mutex
4876 } // while (waiting2)
4877 } // if (flag != 1)
4878 waiting = check_parents_done(kt, _mutex_dependency);
4879 { // scope of mutex
4880 MUTEX_LOCK(_mutex_root, lck_root);
4881 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4882 zone_flag = (_zone_entered[zone_idxn] == num_threads);
4883 MUTEX_UNLOCK(_mutex_root);
4884 } // scope of mutex
4885 if (zone_flag) {
4886 break;
4887 }
4888 } // while (waiting > 0)
4889 execute_task(it, start, permute_block,
4890 pid,
4891 _mutex_dependency);
4892 if ((*it->queue)[start]->quit_queue) {
4893 #ifdef DEBUG_EXEC_THREAD
4894 {
4895 MUTEX_LOCK(_mutex_debug, lck_debug);
4896 cerr << pid << " start = " << start
4897 << " : " << it->task_name << " finished... skip "
4898 << (*it->queue)[start]->to_next_task << endl;
4899 MUTEX_UNLOCK(_mutex_debug);
4900 }
4901 #endif
4902 // const int ibegin = start + 1;
4903 start += (*it->queue)[start]->to_next_task;
4904 }
4905 #ifdef DEBUG_EXEC_THREAD
4906 {
4907 MUTEX_LOCK(_mutex_debug, lck_debug);
4908 cerr << "( " << pid << " : "
4909 << (*it->queue)[start]->task_name << " ) ";
4910 MUTEX_UNLOCK(_mutex_debug);
4911 }
4912 #endif
4913 start++;
4914 { // scope of mutex
4915 MUTEX_LOCK(_mutex_root, lck_root);
4916 // std::unique_lock<std::mutex>lck_root(_mutex_root);
4917 zone_flag = (_zone_entered[zone_idxn] == num_threads);
4918 MUTEX_UNLOCK(_mutex_root);
4919 } // scope of mutex
4920 } // while ((start < it->end) || (!zone_flag))
4921 for (int j = start; j < it->end; j++) {
4922 execute_task(it, j, permute_block,
4923 pid);
4924 if ((*it->queue)[j]->quit_queue) {
4925 #ifdef DEBUG_EXEC_THREAD
4926 {
4927 MUTEX_LOCK(_mutex_debug, lck_debug);
4928 cerr << pid << " j = " << j
4929 << " : " << it->task_name << " finished... skip "
4930 << (*it->queue)[j]->to_next_task << endl;
4931 MUTEX_UNLOCK(_mutex_debug);
4932 }
4933 #endif
4934 // const int ibegin = j + 1;
4935 j += (*it->queue)[j]->to_next_task;
4936 }
4937 } // loop : j
4938
4939 #ifdef DEBUG_EXEC_THREAD2
4940 {
4941 MUTEX_LOCK(_mutex_debug, lck_debug);
4942 for (int j = start; j < it->end; j++) {
4943 cerr << "( " << pid << " : "
4944 << (*it->queue)[j]->task_name << " ) ";
4945 }
4946 MUTEX_UNLOCK(_mutex_debug);
4947 }
4948 #endif
4949 //
4950 }
4951
4952 int QueueRuntime::execute_task_dynamic_buffer(int *permute_block,
4953 int pid,
4954 QueueRuntime_mutex &mutex_dependency)
4955 {
4956 int ph_dynmc, pos, end, atomic_size, atomic_id;
4957 int waiting;
4958 int update_status = 0;
4959 C_task *kt;
4960
4961 { // scope of mutex
4962 MUTEX_LOCK(_mutex_root, lck_root);
4963 ph_dynmc = _phase_dynamic;
4964 if (ph_dynmc >= 0) {
4965 pos = (*_queue_dynamic)[ph_dynmc]->pos;
4966 end = (*_queue_dynamic)[ph_dynmc]->end;
4967 if (pos < end) {
4968 atomic_size = (*(*_queue_dynamic)[ph_dynmc]->queue)[pos]->atomic_size;
4969 atomic_id = (*(*_queue_dynamic)[ph_dynmc]->queue)[pos]->atomic_id;
4970 kt = (*(*_queue_dynamic)[ph_dynmc]->queue)[pos];
4971 // to avoid other thread takes the same pos
4972 waiting = check_parents_done(kt, mutex_dependency);
4973 if (waiting <= 0) {
4974 (*_queue_dynamic)[ph_dynmc]->pos += atomic_size; // pos++
4975 if ((*_queue_dynamic)[ph_dynmc]->pos == end) {
4976 update_status = 1;
4977 _phase_dynamic++;
4978 if (_phase_dynamic == _queue_dynamic->size()) {
4979 _phase_dynamic = (-1);
4980 }
4981 } // if ((*_queue_dynamic)[ph_dynmc]->pos == end)
4982 }
4983 }
4984 else {
4985 ph_dynmc = (-1);
4986 }
4987 } // if (ph_dynmc > 0)
4988 MUTEX_UNLOCK(_mutex_root);
4989 } // scope of mutex
4990 if (ph_dynmc < 0) {
4991 return (-1); // queue exhausted
4992 }
4993 if (waiting > 0) { // waiting == (-1) <=> quit_queue == true
4994 return 0; // the first task in the queue is not ready
4995 }
4996
4997 #ifdef DEBUG_EXEC_THREAD
4998 {
4999 MUTEX_LOCK(_mutex_debug, lck_debug);
5000 cerr << pid << " from dynamic "
5001 << (*_queue_dynamic)[ph_dynmc]->task_name << " "
5002 << pos << " @ " << ph_dynmc
5003 << " " << (*_queue_dynamic)[ph_dynmc]->end
5004 << " " << kt->task_name << " : ";
5005 MUTEX_UNLOCK(_mutex_debug);
5006 }
5007 #endif
5008 for (int m = 0; m < atomic_size; m++) {
5009 execute_task((*_queue_dynamic)[ph_dynmc], (pos + m), // pos
5010 permute_block,
5011 pid, mutex_dependency);
5012 }
5013 #ifdef DEBUG_EXEC_THREAD
5014 {
5015 MUTEX_LOCK(_mutex_debug, lck_debug);
5016 cerr << kt->task_name << " : "
5017 << pos << " done" << endl;
5018 MUTEX_UNLOCK(_mutex_debug);
5019 }
5020 #endif
5021 // ops_complexity is recalculated in each routine :-
5022 { // scope of mutex
5023 // std::unique_lock<std::mutex>lck_root(_mutex_root);
5024 MUTEX_LOCK(_mutex_root, lck_root);
5025 (*_queue_dynamic)[ph_dynmc]->ops_complexity -= *(kt->ops_complexity);
5026 if (update_status) {
5027 (*_queue_dynamic)[ph_dynmc]->status = TASK_DONE;
5028 }
5029 MUTEX_UNLOCK(_mutex_root);
5030 } // scope of mutex
5031 return 1; // success
5032 }
5033
5034 int QueueRuntime::check_parents_done(C_task *it,
5035 QueueRuntime_mutex &mutex_dependency)
5036 {
5037 unsigned char status;
5038 int dependency = 0;
5039 bool quit_queue = false;
5040 // cerr << it->task_name << " size = " << it->parents_work->size() << " || ";
5041 for(list<C_task *>::iterator nt = it->parents_work->begin();
5042 nt != it->parents_work->end(); ) {
5043 // cerr << (*nt)->task_name << " ";
5044 #ifdef TASKSTATUS_MUTEX
5045 {
5046 MUTEX_LOCK(_mutex_dependency, lck_dependency);
5047 status = (*nt)->status;
5048 MUTEX_UNLOCK(_mutex_dependency);
5049 }
5050 #else
5051 status = (*nt)->status;
5052 #endif
5053 if (status == TASK_DONE) {
5054 if ((*nt)->quit_queue) {
5055 quit_queue = true;
5056 }
5057 // 5 Jul.2015 Atsushi
5058 nt = it->parents_work->erase(nt);
5059 // ++nt;
5060 }
5061 else {
5062 dependency++;
5063 ++nt;
5064 }
5065 }
5066 // cerr << " >> " << it->parents_work->size() << " . " << endl;
5067 if (quit_queue && (dependency == 0)) {
5068 dependency = (-1);
5069 }
5070 return dependency;
5071 }
5072
5073 int QueueRuntime::check_parents_done(C_task *it)
5074 {
5075 int dependency = 0;
5076 bool quit_queue = false;
5077 // cerr << it->task_name << " size = " << it->parents_work->size() << " | ";
5078 for(list<C_task *>::iterator nt = it->parents_work->begin();
5079 nt != it->parents_work->end(); ) {
5080 // cerr << (*nt)->task_name << " ";
5081 if ((*nt)->status == TASK_DONE) {
5082 if ((*nt)->quit_queue) {
5083 quit_queue = true;
5084 }
5085 // 5 Jul.2015 Atsushi
5086 nt = it->parents_work->erase(nt);
5087 // ++nt;
5088 }
5089 else {
5090 dependency++;
5091 ++nt;
5092 }
5093 }
5094 if (quit_queue && (dependency == 0)) {
5095 dependency = (-1);
5096 }
5097 return dependency;
5098 }
5099
5100 void QueueRuntime::execute_task(C_task_seq *seq, int pos,
5101 int *permute_block,
5102 int pid,
5103 QueueRuntime_mutex &mutex_depenency)
5104 {
5105 C_task *task = (*seq->queue)[pos];
5106
5107 // debugging
5108 #ifdef DEBUG_CHECKPARENTS_DONE
5109 int waiting;
5110 waiting = check_parents_done(task, mutex_dependency);
5111 if (waiting > 0) {
5112 {
5113 MUTEX_LOCK(_mutex_debug, lck_debug);
5114 cerr << pid << " parents of task " << task->task_name
5115 << " not finished : ";
5116 for(list<C_task *>::const_iterator nt = task->parents_work->begin();
5117 nt != task->parents_work->end(); ++nt) {
5118 cerr << (*nt)->task_name << " ";
5119 }
5120 cerr << endl;
5121 MUTEX_UNLOCK(_mutex_debug);
5122 }
5123 }
5124 #endif
5125 //
5126 #ifdef DEBUG_PRINT_TASK
5127 switch (task->task_id) {
5128 case C_FILLMATRIX:
5129 case C_DFULL_SYM_GAUSS:
5130 case C_DTRSMSCALE:
5131 // case C_SPARSESCHUR:
5132 case C_DGEMM_LOCAL_MULT:
5133 case C_DGEMM_LOCAL_TWO:
5134 case C_DGEMM_DIRECT_TWO:
5135 diss_printf(_verbose, _fps[pid], "%s\n", task->task_name);
5136 *(task->fp) = &_fps[pid];
5137 break;
5138 }
5139 #endif
5140
5141 #ifdef TASKSTATUS_MUTEX
5142 {
5143 MUTEX_LOCK(_mutex_dependency, lck_dependency);
5144 task->status = TASK_WORKING;
5145 MUTEX_UNLOCK(_mutex_dependency);
5146 }
5147 #else
5148 task->status = TASK_WORKING;
5149 #endif // #ifdef TASKSTATUS_MUTEX
5150 #ifdef DEBUG_THREAD_TIME
5151 get_realtime(&(task->t0));
5152 // clock_gettime(CLOCK_MONOTONIC, &(task->t0));
5153 #endif
5154 task->func(task->func_arg);
5155 #ifdef DEBUG_THREAD_DONE_PRINT
5156 {
5157 MUTEX_LOCK(_mutex_debug, lck_debug);
5158 fprintf(stderr, "pid = %d : %s\n", pid, task->task_name);
5159 MUTEX_UNLOCK(_mutex_debug);
5160 }
5161 #endif
5162 if (task->task_id == C_DFULL_SYM_GAUSS) {
5163 // task->quit_queue = ((C_dfull_gauss_arg*)task->func_arg)->quit;
5164 #ifdef TASKSTATUS_MUTEX
5165 { // scope of mutex
5166 MUTEX_LOCK(_mutex_dependency, lck_dependency);
5167 // std::unique_lock<std::mutex>lck_dependency(mutex_dependency);
5168 for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
5169 (*seq->queue)[i]->status = TASK_DONE;
5170 (*seq->queue)[i]->quit_queue = true;
5171 }
5172 MUTEX_UNLOCK(_mutex_dependency);
5173 } // scope of mutex
5174 #endif // #ifdef TASKSTATUS_MUTEX
5175 {
5176 for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
5177 (*seq->queue)[i]->status = TASK_DONE;
5178 (*seq->queue)[i]->quit_queue = true;
5179 #ifdef DEBUG_EXEC_THREAD2
5180 {
5181 MUTEX_LOCK(_mutex_debug, lck_debug);
5182 cerr << (*seq->queue)[i]->task_name << " ";
5183 MUTEX_UNLOCK(_mutex_debug);
5184 }
5185 #endif
5186 }
5187 }
5188 } // if (task->task_id == C_DFULL_SYM_GAUSS)
5189 #ifdef DEBUG_THREAD_TIME
5190 get_realtime(&(task->t1));
5191 // clock_gettime(CLOCK_MONOTONIC, &(task->t1));
5192 task->thread_id = pid;
5193 #endif
5194 #ifdef DEBUG_EXEC_THREAD_FILE
5195 {
5196 MUTEX_LOCK(_mutex_file, lck_file);
5197 const int sec_n0 = convert_sec(task->t0);
5198 const int sec_m0 = convert_microsec(task->t0);
5199 _fout << task->task_name << " / ";
5200 _fout << sec_n0 << " " << sec_m0 << "\t";
5201 for(list<C_task *>::const_iterator nt = task->parents->begin();
5202 nt != task->parents->end(); ++nt) {
5203 int sec_n1 = convert_sec((*nt)->t1);
5204 int sec_m1 = convert_microsec((*nt)->t1);
5205 if ((sec_n0 < sec_n1) || ((sec_n0 == sec_n1) && (sec_m0 < sec_m1))) {
5206 _fout << "*";
5207 }
5208 _fout << (*nt)->task_name << " / ";
5209 _fout << sec_n1 << " " << sec_m1 << "\t";
5210 }
5211 _fout << endl; // " : " << pid << endl;
5212 MUTEX_UNLOCK(_mutex_file);
5213 }
5214 #endif
5215 #ifdef TASKSTATUS_MUTEX
5216 { // scope of mutex
5217 MUTEX_LOCK(_mutex_dependency, lck_dependency);
5218 task->status = TASK_DONE;
5219 MUTEX_UNLOCK(_mutex_dependecny);
5220 } // scope of mutex
5221 #else
5222 task->status = TASK_DONE;
5223 #endif
5224 //
5225 if (_waiting_root > 0) {
5226 { // scope of mutex
5227 MUTEX_LOCK(_mutex_root, lck_root);
5228 COND_BROADCAST(_cond_root);
5229 MUTEX_UNLOCK(_mutex_root);
5230 } // scope of mutex
5231 #ifdef DEBUG_EXEC_THREAD_IDLE
5232 {
5233 cerr << pid << " " << task->task_name
5234 << "_waiting_root = " << (int)_waiting_root
5235 << " broadcast." << endl;
5236 }
5237 #endif
5238 }
5239 }
5240
5241 void QueueRuntime::execute_task(C_task_seq *seq, int pos,
5242 int *permute_block,
5243 int pid)
5244 {
5245 C_task *task = (*seq->queue)[pos];
5246 #ifdef DEBUG_CHECKPARENTS_DONE
5247 // debugging
5248 int waiting;
5249 waiting = check_parents_done(task);
5250 if (waiting > 0) {
5251 {
5252 MUTEX_LOCK(_mutex_debug, lck_debug);
5253 cerr << pid << " parents of task " << task->task_name
5254 << " not finished : " << task->parents_work->size() << " : ";
5255 // debug : 5 Jul. 2015, Atsushi
5256 for(list<C_task *>::const_iterator nt = task->parents_work->begin();
5257 nt != task->parents_work->end(); ++nt) {
5258 cerr << (*nt)->task_name << " / ";
5259 }
5260 cerr << endl;
5261 MUTEX_UNLOCK(_mutex_debug);
5262 }
5263 }
5264 //
5265 #endif
5266 #ifdef DEBUG_PRINT_TASK
5267 switch (task->task_id) {
5268 case C_FILLMATRIX:
5269 case C_DFULL_SYM_GAUSS:
5270 case C_DTRSMSCALE:
5271 // case C_SPARSESCHUR:
5272 case C_DGEMM_LOCAL_MULT:
5273 case C_DGEMM_LOCAL_TWO:
5274 case C_DGEMM_DIRECT_TWO:
5275 diss_printf(_verbose, _fps[pid], "%s\n", task->task_name);
5276 *(task->fp) = &_fps[pid];
5277 break;
5278 }
5279 #endif
5280 // accuessing to unsigned char does not need mutex
5281 task->status = TASK_WORKING;
5282 //
5283 #ifdef DEBUG_THREAD_TIME
5284 get_realtime(&(task->t0));
5285 // clock_gettime(CLOCK_MONOTONIC, &(task->t0));
5286 #endif
5287 // debugging : 13 :Apr.2012 Atsushi
5288 task->func(task->func_arg);
5289 #ifdef DEBUG_THREAD_DONE_PRINT
5290 {
5291 MUTEX_LOCK(_mutex_debug, lck_debug);
5292 fprintf(stderr, "pid = %d : %s\n", pid, task->task_name);
5293 MUTEX_UNLOCK(_mutex_debug);
5294 }
5295 #endif
5296 if (task->task_id == C_DFULL_SYM_GAUSS) {
5297 for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
5298 (*seq->queue)[i]->status = TASK_DONE;
5299 (*seq->queue)[i]->quit_queue = true;
5300 #ifdef DEBUG_EXEC_THREAD2
5301 {
5302 MUTEX_LOCK(_mutex_debug, lck_debug);
5303 cerr << (*seq->queue)[i]->task_name << " ";
5304 MUTEX_UNLOCK(_mutex_debug);
5305 }
5306 #endif
5307 }
5308 }
5309 #ifdef DEBUG_THREAD_TIME
5310 get_realtime(&(task->t1));
5311 // clock_gettime(CLOCK_MONOTONIC, &(task->t1));
5312 task->thread_id = pid;
5313 #endif
5314 // accessing to unsigned char does not neet mutex
5315 task->status = TASK_DONE;
5316 //
5317 if (_waiting_root > 0) {
5318 { // scope of mutex
5319 MUTEX_LOCK(_mutex_root, lck_root);
5320 // std::unique_lock<std::mutex>lck_root(_mutex_root);
5321 COND_BROADCAST(_cond_root);
5322 // _cond_root.notify_all();
5323 MUTEX_UNLOCK(_mutex_root);
5324 } //scope of mutex
5325 #ifdef DEBUG_EXEC_THREAD_IDLE
5326 {
5327 cerr << pid << " " << task->task_name
5328 << "_waiting_root = " << (int)_waiting_root
5329 << " broadcast." << endl;
5330 }
5331 #endif
5332 }
5333 //
5334 #ifdef DEBUG_EXEC_THREAD_FILE
5335 {
5336 MUTEX_LOCK(_mutex_file, lck_file);
5337 const int sec_n0 = convert_sec(task->t1);
5338 const int sec_m0 = convert_microsec(task->t1);
5339 _fout << task->task_name << " / ";
5340 _fout << sec_n0 << " " << sec_m0 << "\t";
5341 for(list<C_task *>::const_iterator nt = task->parents->begin();
5342 nt != task->parents->end(); ++nt) {
5343 int sec_n1 = convert_sec((*nt)->t1);
5344 int sec_m1 = convert_microsec((*nt)->t1);
5345 if ((sec_n0 < sec_n1) || ((sec_n0 == sec_n1) && (sec_m0 < sec_m1))) {
5346 _fout << "*";
5347 }
5348 _fout << (*nt)->task_name << " / ";
5349 _fout << sec_n1 << " " << sec_m1 << "\t";
5350 }
5351 _fout << endl; // " : " << pid << endl;
5352 MUTEX_UNLOCK(_mutex_file);
5353 }
5354 #endif
5355 task->status = TASK_DONE;
5356 }
5357
5358 void QueueRuntime::exec_fwbw_seq()
5359 {
5360 clock_t t0_cpu, t1_cpu;
5361 elapsed_t t0_elapsed, t1_elapsed;
5362
5363 t0_cpu = clock();
5364 get_realtime(&t0_elapsed);
5365 for (vector<C_task*>::const_iterator it = _queue_fwbw->queue->begin();
5366 it != _queue_fwbw->queue->end(); ++it) {
5367 (*it)->func((*it)->func_arg);
5368 }
5369 t1_cpu = clock();
5370 get_realtime(&t1_elapsed);
5371 diss_printf(_verbose, _fp,
5372 "execution of fw/bw : cpu time = %.4e elapsed time = %.4e\n",
5373 (double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
5374 convert_time(t1_elapsed, t0_elapsed));
5375 }
5376
5377 void QueueRuntime::exec_fwbw()
5378 {
5379 const int num_threads = _num_threads; //_num_threads_symb;
5380 #ifdef POSIX_THREADS
5381 void* results;
5382 pthread_attr_t th_attr;
5383 #endif
5384 vector<QueueRuntime_thread> threads;
5385
5386 clock_t t0_cpu, t1_cpu;
5387 elapsed_t t0_elapsed, t1_elapsed;
5388 // struct timespec ts0, ts1;
5389 int ierr;
5390 diss_printf(_verbose, _fp, "fwbw with %d threads\n", num_threads);
5391
5392 // copy dependency data : parents -> parents_work
5393 {
5394 for (vector<C_task *>::const_iterator it = _queue_fwbw->queue->begin();
5395 it != _queue_fwbw->queue->end(); ++it) {
5396 list<C_task *>& parents_work = *((*it)->parents_work);
5397 if (parents_work.size() > 0) { // to avoid double free
5398 parents_work.clear();
5399 }
5400 } // loop : it
5401 for (vector<C_task *>::const_iterator it = _queue_fwbw->queue->begin();
5402 it != _queue_fwbw->queue->end(); ++it) {
5403 list<C_task *>& parents = *((*it)->parents);
5404 list<C_task *>& parents_work = *((*it)->parents_work);
5405 (*it)->status = TASK_WAITING; // reset status
5406 (*it)->quit_queue = false;
5407 if (parents_work.size() == 0) {
5408 #ifdef SX_ACE
5409 for (list<C_task *>::const_iterator lt = parents.begin();
5410 lt != parents.end(); ++lt) {
5411 parents_work.push_back(*lt);
5412 }
5413 #else // SX-ACE C++ rev 110 with C++98/03 does not understand back_inserter
5414 std::copy(parents.begin(), parents.end(), back_inserter(parents_work));
5415 #endif
5416 }
5417 (*it)->broadcast_deadlock = 0;
5418 } // loop : it
5419 _queue_fwbw->pos = _queue_fwbw->begin;
5420 }
5421 #ifdef POSIX_THREADS
5422 // threads = new pthread_t[num_threads];
5423 threads.resize(num_threads);
5424 #ifdef DEBUG_EXEC_THREAD
5425 pthread_mutex_init(&_mutex_debug, NULL);
5426 #endif
5427 pthread_mutex_init(&_mutex_dependency, NULL);
5428 pthread_cond_init(&_cond_root, NULL);
5429 ierr = pthread_mutex_init(&_mutex_root, NULL);
5430 if (ierr != 0) {
5431 fprintf(stderr, " pthread_mutex_init(&_mutex_root, NULL) %s %d : %d\n",
5432 __FILE__, __LINE__, ierr);
5433 }
5434 #ifdef DEBUG_EXEC_THREAD
5435 ierr = pthread_mutex_init(&_mutex_debug, NULL);
5436 if (ierr != 0) {
5437 diss_printf(_verbose, _fp,
5438 "%s %d : pthread_mutex_init(&_mutex_debug, NULL) %d\n",
5439 __FILE__, __LINE__, ierr);
5440 }
5441 #endif
5442 pthread_attr_init(&th_attr);
5443 pthread_attr_setdetachstate(&th_attr, PTHREAD_CREATE_JOINABLE);
5444 #endif
5445 #ifdef DEBUG_EXEC_THREAD_FILE
5446 {
5447 int pid = get_process_id();
5448 char fname[256];
5449 sprintf(fname, "task-s.%d.data", pid);
5450 _fout.open(fname);
5451 }
5452 #endif
5453
5454 t0_cpu = clock();
5455 get_realtime(&t0_elapsed);
5456 // clock_gettime(CLOCK_REALTIME, &ts0);
5457 #ifdef POSIX_THREADS
5458 THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
5459 for (int p = 0; p < num_threads; p++) {
5460 params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
5461 int pid = pthread_create(&threads[p], &th_attr,
5462 &thread_queue_fwbw_,
5463 (void *)params[p]);
5464 if (pid != 0) {
5465 fprintf(stderr, "bad thread creation ? : %d\n", pid);
5466 exit(0);
5467 }
5468 }
5469 pthread_attr_destroy(&th_attr);
5470 for (int p = 0; p < num_threads; p++) {
5471 int pid = pthread_join(threads[p], &results);
5472 if (pid != 0) {
5473 fprintf(stderr, "bad thread creation ? : %d\n", pid);
5474 exit(0);
5475 }
5476 delete params[p];
5477 }
5478 delete [] params;
5479 #else
5480 THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
5481 for (int p = 0; p < num_threads; p++) {
5482 params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
5483 threads.push_back(std::thread(thread_queue_fwbw_,
5484 (void *)params[p]));
5485 }
5486 for (int p = 0; p < num_threads; p++) {
5487 threads[p].join();
5488 delete params[p];
5489 }
5490 delete [] params;
5491
5492 #endif
5493 t1_cpu = clock();
5494 get_realtime(&t1_elapsed);
5495 // clock_gettime(CLOCK_REALTIME, &ts1);
5496 diss_printf(_verbose, _fp,
5497 "execution of fw/bw : cpu time = %.4e elapsed time = %.4e\n",
5498 (double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
5499 convert_time(t1_elapsed, t0_elapsed));
5500
5501 #ifdef DEBUG_EXEC_THREAD_FILE
5502 _fout.close();
5503 #endif
5504
5505 #ifdef DEBUG_THREAD_TIME
5506 {
5507 int pid = get_process_id();
5508 char filename[256];
5509 FILE *fp;
5510 sprintf(filename, "threadtime-fwbw.%d.data", pid);
5511 if ((fp = fopen(filename, "w")) == NULL) {
5512 fprintf(stderr,
5513 "%s %d : fail to open %s\n",
5514 __FILE__, __LINE__, filename);
5515 exit(-1);
5516 }
5517 else {
5518 fprintf(fp, "queue_fwbw\n");
5519 for (int j = _queue_fwbw->begin; j < _queue_fwbw->end; j++) {
5520 double t0 = (convert_sec((*_queue_fwbw->queue)[j]->t0) +
5521 convert_microsec((*_queue_fwbw->queue)[j]->t0) * 1.0e-6);
5522
5523 fprintf(fp, "%2d:\t%-16s\t%2d\t%4d\t%7d\t%7d\t%7d\t%7d",
5524 (*_queue_fwbw->queue)[j]->thread_id,
5525 (*_queue_fwbw->queue)[j]->task_name,
5526 (int)(*_queue_fwbw->queue)[j]->parents_work->size(),
5527 (*_queue_fwbw->queue)[j]->broadcast_deadlock,
5528 convert_sec((*_queue_fwbw->queue)[j]->t0),
5529 convert_microsec((*_queue_fwbw->queue)[j]->t0),
5530 convert_sec((*_queue_fwbw->queue)[j]->t1),
5531 convert_microsec((*_queue_fwbw->queue)[j]->t1));
5532 for (list<C_task *>::const_iterator it = (*_queue_fwbw->queue)[j]->parents->begin();
5533 it != (*_queue_fwbw->queue)[j]->parents->end(); ++it) {
5534 double tt1 = (convert_sec((*it)->t1) +
5535 convert_microsec((*it)->t1) * 1.0e-6);
5536 if (t0 < tt1) {
5537 fprintf(fp, " [ %10s ]", (*it)->task_name);
5538 }
5539 }
5540 fprintf(fp, "\n");
5541 }
5542 fclose(fp);
5543 } // if ((fp = fopen(filename, "a")) == NULL)
5544 }
5545 #endif
5546 #ifdef POSIX_THREADS
5547 pthread_mutex_destroy(&_mutex_root);
5548 #ifdef DEBUG_EXEC_THREAD
5549 pthread_mutex_destroy(&_mutex_debug);
5550 #endif
5551 threads.clear();
5552 #endif
5553 }
5554
5555
5556 void *thread_queue_fwbw_(void *arg)
5557 {
5558 THREAD_QUEUE_EXEC *params = (THREAD_QUEUE_EXEC *)arg;
5559 params->dissectionRuntime->thread_queue_fwbw(params->id,
5560 params->num_threads);
5561 #ifdef POSIX_THREADS
5562 pthread_exit(arg);
5563 #endif
5564 return (void *)NULL;
5565 }
5566
5567 // #define DEBUG_EXEC_THREAD_IDLEa
5568
5569 void QueueRuntime::thread_queue_fwbw(const int pid, const int num_threads)
5570 {
5571 // const int pid = params->id;
5572 // const int num_threads = params->num_threads;
5573 // greedy -- better to be in seperated function
5574 int pos, end;
5575 C_task_seq* it = _queue_fwbw;
5576 // cerr << "pid = " << pid
5577 // << " _queue_symb : pos = " << it->pos << " end = " << it->end << endl;
5578 while (1) {
5579 {
5580 // std::unique_lock<std::mutex>lck_root(_mutex_root);
5581 MUTEX_LOCK(_mutex_root, lck_root);
5582 pos = it->pos;
5583 end = it->end;
5584 if (pos < end) {
5585 it->pos = it->pos + (*it->queue)[pos]->atomic_size;
5586 }
5587 MUTEX_UNLOCK(_mutex_root);
5588 } // destruction of lck_root
5589 if (pos >= end) {
5590 break;
5591 }
5592 C_task *task_p = (*it->queue)[pos];
5593 for (int i = 0; i < task_p->atomic_size; i++) {
5594 C_task *task = (*it->queue)[pos + i];
5595 int waiting = check_parents_done(task, _mutex_dependency);
5596 while (waiting > 0) {
5597 { // scope of mutex
5598 MUTEX_LOCK(_mutex_root, lck_root);
5599 _waiting_root++;
5600 if (_waiting_root == num_threads) {
5601 #ifdef DEBUG_EXEC_THREAD_IDLEa
5602 {
5603 MUTEX_LOCK(_mutex_debug, lck_debug);
5604 cerr << pid << " " << task->task_name
5605 << " _waiting_root = " << (int)_waiting_root
5606 << " dead locked! : emergency broadcast." << endl;
5607 MUTEX_UNLOCK(_mutex_debug);
5608 }
5609 #endif // DEBUG_EXEC_THREAD_IDLEa
5610 COND_BROADCAST(_cond_root);
5611 task->broadcast_deadlock++;
5612 }
5613 #ifdef DEBUG_EXEC_THREAD_IDLEa
5614 {
5615 MUTEX_LOCK(_mutex_debug, lck_debug);
5616 cerr << pid << " " << task->task_name << " "
5617 << "waiting = "<< waiting << " : "
5618 << (int)_waiting_root << " "
5619 << __FILE__ << " " << __LINE__ << " ";
5620 for (list<C_task *>::const_iterator jt = task->parents_work->begin();
5621 jt != task->parents_work->end(); ++jt) {
5622 cerr << (*jt)->task_name << " ";
5623 }
5624 cerr << " : sleeping" << endl;
5625 MUTEX_UNLOCK(_mutex_debug);
5626 }
5627 #endif // DEBUG_EXEC_THREAD_IDLEa
5628 COND_WAIT(_mutex_root, _cond_root, lck_root);
5629 _waiting_root--;
5630 #ifdef DEBUG_EXEC_THREAD_IDLEa
5631 {
5632 MUTEX_LOCK(_mutex_debug, lck_debug);
5633 cerr << pid << " " << task->task_name
5634 << " waked up : _waiting_root = " << (int)_waiting_root
5635 << endl;
5636 MUTEX_UNLOCK(_mutex_debug);
5637 }
5638 #endif // DEBUG_EXEC_THREAD_IDLEa
5639 // other thread broacast wake up and decreasing _waiting_root
5640 waiting = check_parents_done(task, _mutex_dependency);
5641 MUTEX_UNLOCK(_mutex_root);
5642 } // destruction of lck_root
5643 } // while (waiting > 0)
5644 {
5645 MUTEX_LOCK(_mutex_dependency, lck_dependency);
5646 task->status = TASK_WORKING;
5647 MUTEX_UNLOCK(_mutex_dependency);
5648 } // destruction of lck_dependency
5649 #ifdef DEBUG_THREAD_TIME
5650 get_realtime(&(task->t0));
5651 #endif
5652 task->func(task->func_arg);
5653 #ifdef DEBUG_THREAD_TIME
5654 get_realtime(&(task->t1));
5655 task->thread_id = pid;
5656 #endif
5657 {
5658 MUTEX_LOCK(_mutex_dependency, lck_depenency);
5659 task->status = TASK_DONE;
5660 MUTEX_UNLOCK(_mutex_dependency);
5661 }
5662 if (_waiting_root > 0) {
5663 { // scope of mutex
5664 MUTEX_LOCK(_mutex_root, lck_root);
5665 #ifdef DEBUG_EXEC_THREAD_IDLEa
5666 {
5667 MUTEX_LOCK(_mutex_debug, lck_debug);
5668 cerr << pid << " " << task->task_name
5669 << " _waiting_root = " << (int)_waiting_root
5670 << " broadcast." << endl;
5671 MUTEX_UNLOCK(_mutex_debug);
5672 }
5673 #endif // DEBUG_EXEC_THREAD_IDLEa
5674 COND_BROADCAST(_cond_root);
5675 MUTEX_UNLOCK(_mutex_root);
5676 } // destruction of lck_root
5677 }
5678 } // loop : i
5679 } // while (1)
5680 #ifdef DEBUG_EXEC_THREAD
5681 {
5682 MUTEX_LOCK(_mutex_debug, lck_debug);
5683 cerr << pid << " " << it->task_name
5684 << " @ " << it->task_id << " greedy end." << endl;
5685 MUTEX_UNLOCK(_mutex_debug);
5686 }
5687 #endif
5688 }