/*! \file QueueRuntime.cpp
\brief management of threads for Dissection Matrix
\author Atsushi Suzuki, Laboratoire Jacques-Louis Lions
\date Jun. 20th 2014
\date Jul. 12th 2015
\date Nov. 30th 2016
\date Apr. 17th 2016
*/
// This file is part of Dissection
//
// Dissection is free software: you can redistribute it and/or modify
// it under the terms of the GNU General Public License as published by
// the Free Software Foundation, either version 3 of the License, or
// (at your option) any later version.
//
// Linking Dissection statically or dynamically with other modules is making
// a combined work based on Disssection. Thus, the terms and conditions of
// the GNU General Public License cover the whole combination.
//
// As a special exception, the copyright holders of Dissection give you
// permission to combine Dissection program with free software programs or
// libraries that are released under the GNU LGPL and with independent modules
// that communicate with Dissection solely through the Dissection-fortran
// interface. You may copy and distribute such a system following the terms of
// the GNU GPL for Dissection and the licenses of the other code concerned,
// provided that you include the source code of that other code when and as
// the GNU GPL requires distribution of source code and provided that you do
// not modify the Dissection-fortran interface.
//
// Note that people who make modified versions of Dissection are not obligated
// to grant this special exception for their modified versions; it is their
// choice whether to do so. The GNU General Public License gives permission to
// release a modified version without this exception; this exception also makes
// it possible to release a modified version which carries forward this
// exception. If you modify the Dissection-fortran interface, this exception
// does not apply to your modified version of Dissection, and you must remove
// this exception when you distribute your modified version.
//
// This exception is an additional permission under section 7 of the GNU
// General Public License, version 3 ("GPLv3")
//
// Dissection is distributed in the hope that it will be useful,
// but WITHOUT ANY WARRANTY; without even the implied warranty of
// MERCHANTABILITY or FITNESS FOR A PARTICULAR PURPOSE. See the
// GNU General Public License for more details.
//
// You should have received a copy of the GNU General Public License
// along with Dissection. If not, see .
//
#include
#include "Driver/QueueRuntime.hpp"
#include "Compiler/DissectionIO.hpp"
#define RATIO_STATIC 0.7 // for slow DGEMM'
#define RATIO_QUEUE_GREEDY 0.8
//#define DEBUG_THREAD_TIME
//#define DEBUG_EXEC_THREAD
#define DEBUG_DEADLOCK
// DEBUG_DEADLOCK only works without setting DEBUG_EXEC_THREAD_IDLE
#ifdef DEBUG_DEADLOCK
#ifdef DEBUG_EXEC_THREAD_IDLE
#undef DEBUG_EXEC_THREAD_IDLE
#endif // DEBUG_EXEC_THREAD_IDLE
#endif // DEBUG_DEADLOCK
// constructor
QueueRuntime::QueueRuntime(int nb_doms, int num_threads, const bool isSym,
const bool verbose, FILE *fp)
{
_nb_doms = nb_doms;
_num_threads = num_threads;
_isSym = isSym;
_verbose = verbose;
_fp = fp;
_zone_entered = new int[DIST_TASK_CRITICAL];
_zone_finished = new int[DIST_TASK_CRITICAL];
_zone_static_assigned = new int[DIST_TASK_CRITICAL];
allocate_int2d(_begins, num_threads);
allocate_int2d(_ends, num_threads);
allocate_int3d(_group_entered, num_threads);
allocate_int3d(_group_finished, num_threads);
allocate_int3d(_group_task_ends, num_threads);
allocate_int3d(_group_static_assigned, num_threads);
_group_task_id = new int[num_threads];
allocate_int3d(_begins_group, num_threads);
allocate_int3d(_ends_group, num_threads);
allocate_unsigned2d(_group_nops, num_threads);
_mutex_group = new QueueRuntime_mutex[num_threads];
}
QueueRuntime::~QueueRuntime()
{
// initialize state to controle tasks
delete [] _zone_entered;
delete [] _zone_finished;
delete [] _zone_static_assigned;
deallocate_int2d(_begins);
deallocate_int2d(_ends);
deallocate_int3d(_group_entered);
deallocate_int3d(_group_finished);
deallocate_int3d(_group_task_ends);
deallocate_int3d(_group_static_assigned);
deallocate_int3d(_begins_group);
deallocate_int3d(_ends_group);
deallocate_unsigned2d(_group_nops);
delete [] _group_task_id;
delete [] _mutex_group;
}
void allocate_int2d(int **&array, const int num_threads)
{
array = new int*[num_threads];
array[0] = new int[num_threads * DIST_TASK_CRITICAL];
int p, pp;
p = 1;
pp = DIST_TASK_CRITICAL;
for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
array[p] = &array[0][pp];
}
}
void allocate_unsigned2d(long **&array, const int num_threads)
{
array = new long*[num_threads];
array[0] = new long[num_threads * DIST_TASK_CRITICAL];
int p, pp;
p = 1;
pp = DIST_TASK_CRITICAL;
for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
array[p] = &array[0][pp];
}
}
void allocate_int3d(int ***&array, const int num_threads)
{
array = new int**[num_threads];
array[0] = new int*[num_threads * DIST_TASK_CRITICAL];
array[0][0] = new int[(num_threads *
DIST_TASK_CRITICAL * DIST_TASK_CRITICAL)];
int p, q, pp;
p = 1;
pp = DIST_TASK_CRITICAL;
for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
array[p] = &array[0][pp];
}
p = 0;
pp = 0;
for ( ; p < num_threads; p++, pp += DIST_TASK_CRITICAL) {
for (q = 0; q < DIST_TASK_CRITICAL; q++) {
if (!((p == 0) && (q == 0))) {
array[p][q] = &array[0][0][(q + pp) * DIST_TASK_CRITICAL];
}
}
}
}
void deallocate_int2d(int **&array)
{
delete [] array[0];
delete [] array;
}
void deallocate_unsigned2d(long **&array)
{
delete [] array[0];
delete [] array;
}
void deallocate_int3d(int ***&array)
{
delete [] array[0][0];
delete [] array[0];
delete [] array;
}
int IndexTask(vector &queue, int pos)
{
int j = 0;
int pos1 = pos > queue.size() ? queue.size() : pos;
for (int i = 0; i < pos1; i++) {
j += queue[j]->atomic_size;
}
return j;
}
// #define DEBUG_NULL_TASK
void copytask_list2seq(list &queue_static,
list queue_lists,
list &queue_null,
// list &queue_dummy,
string task_name,
int task_id,
int mutex_id,
int parallel_single,
int num_threads,
int level,
int phase)
{
// #define DEBUG_ASSIGN_TASK
#ifdef DEBUG_ASSIGN_TASK
cerr << endl << "** " << task_name << " ** " << queue_lists.size() << endl;
#endif
int num_tasks = 0;
for (list::const_iterator it = queue_lists.begin();
it != queue_lists.end(); ++it) {
// int itmp = 0;
for (int j = (*it)->begin; j < (*it)->end; j++) {
if (*((*(*it)->queue)[j]->ops_complexity) != 0L) {//cf. -1L : 16 Sep.2014
num_tasks++;
// itmp++;
}
else {
(*(*it)->queue)[j]->status = TASK_DONE;
#ifdef DEBUG_NULL_TASK
fprintf(stderr, "%s %d : copytask_list2seq() null task = %s\n",
__FILE__, __LINE__, (*(*it)->queue)[j]->task_name);
#endif
queue_null.push_back((*(*it)->queue)[j]);
}
}
#ifdef DEBUG_ASSIGN_TASK
cerr << (*it)->task_id
<< " [ " << (*it)->end << " " << (*it)->begin << " ] ";
#endif
}
#ifdef DEBUG_ASSIGN_TASK
cerr << endl;
#endif
vector *tasks_tmp = new vector;
long nops = 0L;
tasks_tmp->resize(num_tasks);
// tasks_tmp->reserve(num_tasks);
int k = 0;
for (list::const_iterator it = queue_lists.begin();
it != queue_lists.end(); ++it) {
for (int j = (*it)->begin; j < (*it)->end; j++) {
if (*((*(*it)->queue)[j]->ops_complexity) != 0L) { //cf. -1L : 16 Sep.2014
(*tasks_tmp)[k++] = (*(*it)->queue)[j];
if (*((*(*it)->queue)[j]->ops_complexity) > 0L) {
nops += *((*(*it)->queue)[j]->ops_complexity);
}
}
}
}
C_task_seq* seq_tmp = new C_task_seq(task_id,
task_name,
mutex_id,
parallel_single,
num_threads,
level,
phase,
tasks_tmp,
0, // begin
num_tasks, // end
nops);
queue_static.push_back(seq_tmp);
}
void task_assign_diag1(list * &queue_static,
vector* &tasks_queue,
list &queue_null,
// list &queue_dummy,
vector &nrow_DFullLDLt,
vector &isMergedDTRSM,
string queue_symbol,
int queue_id,
int level_id,
int num_threads,
int level_last,
int level,
int begdom,
int enddom,
long *nops_sum,
vector starts,
list* &queue_lists,
bool queue_lists_clear,
Dissection::Tree* btree,
vector* children)
{
int num_tmp_shared;
list tmp_dynamic;
list task_seq_tmp;
long nops_block_total;
vector *tmp_shared = new vector;
if (queue_lists_clear) {
for (int p = 0; p < num_threads; p++) {
#if 1
for (list::iterator it = queue_lists[p].begin();
it != queue_lists[p].end(); ++it) {
delete (*it);
(*it) = NULL;
}
#endif
queue_lists[p].clear();
}
}
task_seq_tmp.clear();
nops_block_total = 0L;
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
if ((queue_id == C_DTRSM) && (nrow_DFullLDLt[jc] > 2)) {
continue;
}
long nops = 0L;
const int begin = starts[jc];
int end;
if (queue_id == C_DTRSM) {
if (!isMergedDTRSM[j]) { // looking the father node
end = IndexTask(tasks_queue[jc], tasks_queue[jc][0]->parallel_max);
}
else {
end = tasks_queue[jc].size();
}
}
else {
int itmp = tasks_queue[jc][0]->parallel_max;
int jtmp = tasks_queue[jc].size();
// if (itmp < (_isSym ? 3 : 4)) {
if (!isMergedDTRSM[j]) {
end = itmp;
}
else {
if (itmp == jtmp) {
end = jtmp;
}
else {
end = itmp + tasks_queue[jc][itmp]->parallel_max;
}
}
}
if (level == 0) {
end = (int)((double)end * RATIO_STATIC);
const int ktmp = tasks_queue[jc][end]->atomic_id;
end -= ktmp;
}
for (int i = begin; i < end; i++) {
nops += *(tasks_queue[jc][i]->ops_complexity);
}
string task_name = to_string(jc);
if (nops > 0L) {
C_task_seq* tmp =
new C_task_seq(queue_id,
task_name, // for debugging
(-1), // mutex_id
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + level_id,
&tasks_queue[jc],
begin,
end,
nops);
task_seq_tmp.push_back(tmp);
nops_block_total += nops;
}
else {
for (int i = begin; i < end; i++) {
queue_null.push_back(tasks_queue[jc][i]);
}
}
} // loop : ic
} // loop : j
num_tmp_shared = 0;
tmp_dynamic.clear();
if (task_seq_tmp.size() > 0) {
task_seq_tmp.sort(C_task_seq_complexity_greater);
string queue_name;
if (level == 0) {
queue_name = queue_symbol + "% ";
}
else {
queue_name = queue_symbol + "* ";
}
assign_tasks_statically(queue_lists,
tmp_dynamic,
nops_sum,
task_seq_tmp,
queue_id,
queue_name.c_str(),
(level + 1),
(level_last - 1 - level) * 6 + level_id,
nops_block_total,
num_threads);
// task_seq_tmp.clear(); moved in assign_tasks_statically
if (tmp_dynamic.size() > 0) {
num_tmp_shared += tmp_dynamic.size();
}
}
if (level == 0) {
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
int parallel_max;
if ((queue_id == C_DTRSM) && (nrow_DFullLDLt[jc] > 2)) {
continue;
}
if (queue_id == C_DTRSM) {
if (!isMergedDTRSM[j]) { // looking father node
parallel_max = IndexTask(tasks_queue[jc],
tasks_queue[jc][0]->parallel_max);
}
else {
parallel_max = tasks_queue[jc].size();
}
}
else {
int itmp = tasks_queue[jc][0]->parallel_max;
int jtmp = tasks_queue[jc].size();
// if (itmp < _isSym ? 3 : 4) {
if (!isMergedDTRSM[j]) {
parallel_max = itmp;
}
else {
parallel_max = ((itmp == jtmp) ? jtmp :
(itmp + tasks_queue[jc][itmp]->parallel_max));
}
}
const int end = (int)((double)parallel_max * RATIO_STATIC);
const int ktmp = tasks_queue[jc][end]->atomic_id;
num_tmp_shared += parallel_max - end + ktmp;
}
}
}
tmp_shared->reserve(num_tmp_shared);
if (tmp_dynamic.size() > 0) {
long nops = 0L;
for (list::iterator mt = tmp_dynamic.begin();
mt != tmp_dynamic.end(); ++mt) {
nops += (*mt)->ops_complexity;
}
#ifdef DEBUG_PREPARE_THREAD
cout << "static -> dynamic : " << tmp_dynamic.size()
<< " nops_sum = " << nops << " " ;
#endif
for (list::iterator mt = tmp_dynamic.begin();
mt != tmp_dynamic.end(); ++mt) {
for (int i = (*mt)->begin; i < (*mt)->end; i++) {
tmp_shared->push_back((*(*mt)->queue)[i]);
}
delete (*mt);
(*mt) = NULL;
}
#ifdef DEBUG_PREPARE_THREAD
cout << endl;
#endif
} // if (tmp_dynamic.size() > 0)
if (level == 0) {
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
int parallel_max;
if ((queue_id == C_DTRSM) && (nrow_DFullLDLt[jc] > 2)) {
continue;
}
if (queue_id == C_DTRSM) {
if (!isMergedDTRSM[j]) { // looking father node
parallel_max = IndexTask(tasks_queue[jc],
tasks_queue[jc][0]->parallel_max);
}
else {
parallel_max = tasks_queue[jc].size();
}
}
else {
int itmp = tasks_queue[jc][0]->parallel_max;
int jtmp = tasks_queue[jc].size();
// if (itmp <= (_isSym ? 3 : 4)) {
if (!isMergedDTRSM[j]) {
parallel_max = itmp;
}
else {
parallel_max = ((itmp == jtmp) ? jtmp :
(itmp + tasks_queue[jc][itmp]->parallel_max));
}
}
int end = (int)((double)parallel_max * RATIO_STATIC);
const int ktmp = tasks_queue[jc][end]->atomic_id;
end -= ktmp;
for (int i = end; i < parallel_max; i++) {
// exclude null tasks
if (*(tasks_queue[jc][i]->ops_complexity) > 0L) {
tmp_shared->push_back(tasks_queue[jc][i]);
}
else {
queue_null.push_back(tasks_queue[jc][i]);
}
// cyclic by index jc is better ?
}
} // loop : ic
}
}
{
string task_name = queue_symbol + " " + to_string(level + 1);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(queue_static[p],
queue_lists[p],
queue_null,
// queue_dummy,
task_name,
queue_id,
p,
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + level_id);
for (list::iterator it = queue_lists[p].begin();
it != queue_lists[p].end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
}
#ifdef DEBUG_PREPARE_THREAD
cout << queue_symbol << num_tmp_shared << " : " << tmp_shared->size()
<< endl;
#endif
if (tmp_shared->size() > 0) {
string task_name = queue_symbol + "+ " + to_string(level + 1);
long nops = 0L;
for (vector::const_iterator it = tmp_shared->begin();
it != tmp_shared->end(); ++it) {
nops += *((*it)->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(queue_id,
task_name,
0,
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + level_id,
tmp_shared,
0,
tmp_shared->size(),
nops);
for (int p = 0; p < num_threads; p++) {
queue_static[p].push_back(tmp);
}
} // if (num_tmp_shared > 0)
else {
delete tmp_shared;
}
// delete tmp_shared;
}
void task_assign_diag2(list *&queue_static,
vector* &tasks_queue,
list &queue_null,
// list &queue_dummy,
vector &isMergedDTRSM,
string queue_symbol,
int queue_id,
int level_id,
int num_threads,
int level_last,
int level,
int begdom,
int enddom,
long *nops_sum,
vector starts,
vector starts_sub,
list* &queue_lists,
bool queue_lists_clear,
Dissection::Tree* btree,
vector* children)
{
int num_tmp_shared;
list tmp_dynamic;
listtask_seq_tmp;
long nops_block_total;
vector *tmp_shared = new vector;
task_seq_tmp.clear();
nops_block_total = 0L;
if (queue_lists_clear) {
for (int p = 0; p < num_threads; p++) {
#if 1
for (list::iterator it = queue_lists[p].begin();
it != queue_lists[p].end(); ++it) {
delete (*it);
(*it) = NULL;
}
#endif
queue_lists[p].clear();
}
}
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
long nops = 0L;
const int begin = starts_sub[j];
int end;
// if (tasks_queue0[j].size() <= 4) {
if (!isMergedDTRSM[j]) {
end = tasks_queue[j][0]->parallel_max;
}
else {
end = tasks_queue[j].size();
}
if (level == 0) {
end = (int)((double)end * RATIO_STATIC);
}
for (int i = begin; i < end; i++) {
nops += *(tasks_queue[j][i]->ops_complexity);
}
string task_name = to_string(j);
if (nops > 0L) {
C_task_seq* tmp =
new C_task_seq(queue_id,
task_name, // for debugging
(-1), // mutex_id
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + level_id,
&tasks_queue[j],
begin,
end,
nops);
task_seq_tmp.push_back(tmp);
nops_block_total += nops;
}
else {
for (int i = begin; i < end; i++) {
queue_null.push_back(tasks_queue[j][i]);
}
}
} // loop : j
tmp_dynamic.clear();
num_tmp_shared = 0;
if (task_seq_tmp.size() > 0) {
task_seq_tmp.sort(C_task_seq_complexity_greater);
string queue_name;
if (level == 0) {
queue_name = queue_symbol + "% " ;
}
else {
queue_name = queue_symbol + "* " ;
}
assign_tasks_statically(queue_lists,
tmp_dynamic,
nops_sum,
task_seq_tmp,
queue_id,
queue_name.c_str(),
(level + 1),
(level_last - 1 - level) * 6 + level_id,
nops_block_total,
num_threads);
if (tmp_dynamic.size() > 0) {
num_tmp_shared += tmp_dynamic.size();
}
}
if (level == 0) {
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
const int parallel_max = tasks_queue[j].size();
const int end = (int)((double)parallel_max * RATIO_STATIC);
num_tmp_shared += parallel_max - end;
}
}
tmp_shared->reserve(num_tmp_shared);
if (tmp_dynamic.size() > 0) {
long nops = 0L;
for (list::const_iterator mt = tmp_dynamic.begin();
mt != tmp_dynamic.end(); ++mt) {
nops += (*mt)->ops_complexity;
}
for (list::iterator mt = tmp_dynamic.begin();
mt != tmp_dynamic.end(); ++mt) {
for (int i = (*mt)->begin; i < (*mt)->end; i++) {
tmp_shared->push_back((*(*mt)->queue)[i]);
}
delete (*mt);
(*mt) = NULL;
}
}
if (level == 0) {
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
int parallel_max;
if (!isMergedDTRSM[j]) {
parallel_max = tasks_queue[j][0]->parallel_max;
}
else {
parallel_max = tasks_queue[j].size();
}
const int end = (int)((double)parallel_max * RATIO_STATIC);
for (int i = end; i < parallel_max; i++) {
if (*(tasks_queue[j][i]->ops_complexity) > 0L) { // exclude null tasks
tmp_shared->push_back(tasks_queue[j][i]);
}
else {
queue_null.push_back(tasks_queue[j][i]);
}
// cyclic by index jc is better ?
}
}
}
{
string task_name = queue_symbol + " " + to_string(level + 1);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(queue_static[p],
queue_lists[p],
queue_null,
// queue_dummy,
task_name,
queue_id,
p,
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + level_id);
// 3 Jul 2016
for (list::iterator it = queue_lists[p].begin();
it != queue_lists[p].end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
}
#ifdef DEBUG_PREPARE_THREAD
cout << queue_symbol << num_tmp_shared << " : " << tmp_shared->size()
<< endl;
#endif
if (tmp_shared->size() > 0) {
string task_name = queue_symbol + "+ " + to_string(level + 1);
long nops = 0L;
for (vector::const_iterator it = tmp_shared->begin();
it != tmp_shared->end(); ++it) {
nops += *((*it)->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(queue_id,
task_name,
0,
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + level_id,
tmp_shared,
0,
tmp_shared->size(),
nops);
for (int p = 0; p < num_threads; p++) {
queue_static[p].push_back(tmp);
}
} // if (tmp_shared->size() > 0)
else {
delete tmp_shared;
}
}
void QueueRuntime::generate_queue(C_task_seq* &queue_symb_,
list* & queue_static_,
vector* &queue_dynamic_,
list &queue_null_,
// list &queue_dummy_,
Dissection::Tree* btree,
vector* children,
vector* tasks_SparseSymb,
vector* tasks_SparseNum,
vector* tasks_SparseLocalSchur,
vector* tasks_DFillSym,
vector* tasks_DFullLDLt,
vector* tasks_DTRSMScale,
vector* tasks_DGEMM,
vector** tasks_Dsub,
vector* tasks_deallocLower,
vector* tasks_deallocLocalSchur,
long **nops_queue,
vector > all_fathersIndex,
vector nrow_DFullLDLt,
vector isMergedDTRSM,
vector isDividedDTRSM,
const int level_last)
{
// begin : task squence for symmbolic factorization
const int num_threads = _num_threads;
const int nb_doms_dense = (1U << level_last) - 1;
{ //begin scope : task_name
list queue_tmp;
string task_name = "l " + to_string(level_last);
const int begdom = 1U << level_last;
const int enddom = begdom * 2;
for (int d = begdom; d < enddom; d++) {
const int j = d - begdom;
C_task_seq* tmp =
new C_task_seq(C_SPARSESYMBFACT,
_null_name, // dummy
(-1), // mutex_id
TASK_SINGLE,
1,
level_last,
(-1), // phase
&tasks_SparseSymb[j],
0,
1,
*(tasks_SparseSymb[j][0]->ops_complexity));
queue_tmp.push_back(tmp);
}
//
queue_tmp.sort(C_task_seq_complexity_greater);
vector *task_tmp = new vector;
task_tmp->resize(begdom);
int k = 0;
for (list::iterator it = queue_tmp.begin();
it != queue_tmp.end(); ++it, k++) {
(*task_tmp)[k] = (*it)->queue[0][0];
}
queue_symb_ = new C_task_seq(C_SPARSESYMBFACT,
task_name, // dummy
(-1), // mutex_id
TASK_SINGLE,
1,
level_last,
(-1), // phase
task_tmp,
0,
begdom,
0); // dummy
_queue_symb = queue_symb_;
for (list::iterator it = queue_tmp.begin();
it != queue_tmp.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} //end scope : task_name
queue_static_ = new list[num_threads];
_queue_static = queue_static_;
queue_dynamic_ = new vector;
_queue_dynamic = queue_dynamic_;
// end : task squence for symmbolic factorization
list* queue_dynamic = new list[level_last + 1];
list* queue_dynamic0 = new list;
list* queue_dynamic1 = new list[level_last + 1];
list* queue_dynamic2 = new list[level_last + 1];
// list* queue_dynamic3 = new list[level_last + 1];
list* queue_lists = new list[num_threads];
list queue_tmp0, queue_tmp1;
// assuming that num_leaves(level_last) > num_threads
// num_leaves(level_last) = _begLevel[level_last] - _begLevel[level_last + 1]
//
// Sparse numeric factorization : tasks_SparseNum[] -> _queue_static[]
queue_tmp0.clear();
#define SPARSE_MERGED
#ifdef SPARSE_MERGED
{
// sparse subdomains : tasks_SparseNum[]
// all dense subdomains : tasks_DFillSym[]
// the begining of the dense subdomains
const int begdom = 1U << (level_last - 1);
const int enddom = begdom * 2;
for (int d = begdom; d < enddom; d++) {
int j;
vector* tasks = new vector;
j = btree->selfIndex(2 * d);
long nops = 0L;
tasks->push_back(tasks_SparseNum[j][0]);
nops += *(tasks_SparseNum[j][0]->ops_complexity);
tasks->push_back(tasks_SparseLocalSchur[j][0]);
nops += *(tasks_SparseLocalSchur[j][0]->ops_complexity);
j = btree->selfIndex(2 * d + 1);
tasks->push_back(tasks_SparseNum[j][0]);
nops += *(tasks_SparseNum[j][0]->ops_complexity);
tasks->push_back(tasks_SparseLocalSchur[j][0]);
nops += *(tasks_SparseLocalSchur[j][0]->ops_complexity);
j = btree->selfIndex(d);
for (vector::const_iterator it = tasks_DFillSym[j].begin();
it != tasks_DFillSym[j].end(); ++it) {
tasks->push_back(*it);
nops += *((*it)->ops_complexity);
}
// task complexity of DFillSym[] in higher level is very large
int dd;
if (d % 2 == 0) {
dd = (d - begdom) / 2;
}
else {
dd = begdom - (d - begdom + 1) / 2;
}
if (dd > 0) {
j = btree->selfIndex(dd);
for (vector::const_iterator it = tasks_DFillSym[j].begin();
it != tasks_DFillSym[j].end(); ++it) {
tasks->push_back(*it);
nops += *((*it)->ops_complexity);
}
}
C_task_seq* tmp =
new C_task_seq(C_SPARSESOLVER,
_null_name,
(-1), // mutex_id
(-1), //TASK_SINGLE,
(-1), // 1,
(-1), // level_last,
(-1), // phase
tasks,
0,
tasks->size(),
nops);
queue_tmp0.push_back(tmp);
} // loop : d(j)
string task_name = "z " + to_string(level_last);
copytask_list2seq(queue_dynamic[level_last],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_SPARSESOLVER, // C_FILLMATRIX1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
level_last,
2);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it)->queue; // deallocate a container : tasks in L880
delete (*it);
(*it) = NULL;
}
}
#else
{
// sparse subdomains : tasks_SparseNum[]
// all dense subdomains : tasks_DFillSym[]
// the begining of the dense subdomains
const int begdom = 1U << level_last;
const int enddom = begdom * 2;
queue_tmp0.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
C_task_seq* tmp =
new C_task_seq(C_SPARSENUMFACT,
_null_name,
(-1), // mutex_id
(-1), //TASK_SINGLE,
(-1), // 1,
(-1), // level_last,
(-1), // phase
&tasks_SparseNum[j],
0,
1,
*(tasks_SparseNum[j][0]->ops_complexity));
queue_tmp0.push_back(tmp);
} // loop : d(j)
queue_tmp0.sort(C_task_seq_complexity_greater);
{
int itmp = 0;
for (list::const_iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it, itmp++) {
queue_lists[itmp % num_threads].push_back(*it);
}
} // loop : it, itmp
{
string task_name = "u " + to_string(level_last);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(_queue_static[p],
queue_lists[p],
queue_null_,
// queue_dummy_,
task_name,
C_SPARSENUMFACT,
p,
TASK_SINGLE,
1,
level_last,
0);
}
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
// Sparse local Schur complement : tasks_SparseLocalSchur[] -> queue_dynamic[]
queue_tmp0.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
C_task_seq* tmp =
new C_task_seq(C_SPARSELOCALSCHUR,
_null_name, //(char *)NULL, // dummy
(-1), // mutex_id
(-1), //TASK_SINGLE,
(-1), // 1,
(-1), // level_last,
(-1), // phase
&tasks_SparseLocalSchur[j],
0,
1,
*(tasks_SparseLocalSchur[j][0]->ops_complexity));
queue_tmp0.push_back(tmp);
} // loop : d(j)
queue_tmp0.sort(C_task_seq_complexity_greater);
{
string task_name = "w " + to_string(level_last);
// C_SPARSELOCALSCHUR is simple greedy estimated complexity by
// assuming blocks are dense
// C_SPARSELOCALSCHUR1 uses estimated complexity by C_SPARSENUMFACT
copytask_list2seq(*queue_dynamic0,
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_SPARSELOCALSCHUR, // C_SPARSELOCALSCHUR1
0, // shared by all threads
TASK_PARALLEL,
num_threads,
level_last,
1); // SparseLDLt : 0
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic0->begin();
it != queue_dynamic0->end(); ++it) {
_queue_static[p].push_back(*it);
}
}
}
// -- C_FILLMATRIX diagonal -
// without using children
queue_tmp0.clear();
{
// sparse subdomains : tasks_SparseNum[]
// all dense subdomains : tasks_DFillSym[]
// the begining of the dense subdomains
const int begdom = 1U << (level_last - 1);
const int enddom = begdom * 2;
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
{
string task_name = "v " + to_string(level_last) + " : ";
queue_tmp0.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
const int begin = 0; // better that all (diag/offdiag) in greedy
// const int begin = tasks_DFillSym[j][0]->parallel_max;
// -- C_FILLMATRIX offdiagonal --
const int end = tasks_DFillSym[j].size();
if ((end - begin) > 0) { // always true
task_name += to_string(d) + " ";
C_task_seq* tmp =
new C_task_seq(C_FILLMATRIX,
_null_name, // task_name_cstr,
(-1), // mutex_id
(-1), // TASK_PARALLEL,
(-1), // num_threads,
(-1), // level
(-1), // phase
&tasks_DFillSym[j],
begin,
end,
0L // nops;
);
queue_tmp0.push_back(tmp);
}
} // loop : d(j)
// -- C_FILLMATRIX diag/offdiagonal for grand fathers --
for (int d = 1; d < begdom; d++) {
const int j = btree->selfIndex(d);
task_name += to_string(d) + " ";
C_task_seq* tmp =
new C_task_seq(C_FILLMATRIX,
_null_name, // task_name_cstr,
(-1), // mutex_id
(-1), // TASK_PARALLEL,
(-1), // num_threads,
(-1), // level
(-1), // phase
&tasks_DFillSym[j],
0,
tasks_DFillSym[j].size(),
0L // nops;
);
queue_tmp0.push_back(tmp);
} // loop : d(j)
if (queue_tmp0.size() > 0) { // only the last block
copytask_list2seq(queue_dynamic[level_last],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_FILLMATRIX, // C_FILLMATRIX1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
level_last,
2);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
}
}
#endif
{
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic[level_last].begin();
it != queue_dynamic[level_last].end(); ++it) {
_queue_static[p].push_back(*it);
}
}
}
// for dense subdomains
for (int level = (level_last - 1); level >=0; level--) {
const int begdom = 1U << level;
const int enddom = begdom * 2;
const int num_leaves = 1 << (level + 1); // 1 << level
if (level < (level_last - 1)) {
// better management by mixed Assignment of blocks of DTRSM/DGEMM
// -- DTRSM offdiagonal --
{
string task_name = "q offdiag " + to_string(level + 1) + " : ";
queue_tmp0.clear();
// off-diagonal parallel block between children and grandfather, ancenstors
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
const int end = tasks_DTRSMScale[jc].size();
int begin = tasks_DTRSMScale[jc].size();
if (!isDividedDTRSM[jc] && (end > 0) && !isMergedDTRSM[j]) {
begin = IndexTask(tasks_DTRSMScale[jc],
tasks_DTRSMScale[jc][0]->parallel_max);
}
if ((end - begin) > 0) {
task_name += to_string(jc) + " ";
C_task_seq* tmp =
new C_task_seq(C_DTRSM,
_null_name, // task_name_cstr,
(-1), // mutex_id
(-1), // TASK_PARALLEL,
(-1), // num_threads,
(-1), // level
(-1), // phase
&tasks_DTRSMScale[jc],
begin,
end,
0L // nops;
);
queue_tmp0.push_back(tmp);
} // if ((end - begin) > 0)
} // loop : ic
} // loop : j
if (queue_tmp0.size() > 0) { // only the last block
copytask_list2seq(queue_dynamic[level],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_DTRSM1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 1);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
}
// dependency
// -- D_GEMM offdiagonal --
{
string task_name = "r " + to_string(level + 1) + " : ";
queue_tmp0.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
const int end = tasks_DGEMM[jc].size();
if (end > 0) {
int begin;
const int itmp = tasks_DGEMM[jc][0]->parallel_max;
if (!isMergedDTRSM[j]) {
begin = itmp;
}
else {
begin = ((itmp == end) ? end :
(itmp + tasks_DGEMM[jc][itmp]->parallel_max));
}
if ((end - begin) > 0) {
task_name += to_string(jc) + " ";
C_task_seq* tmp =
new C_task_seq(C_DGEMM,
_null_name, // task_name_cstr,
(-1), // mutex_id
(-1), // TASK_PARALLEL,
(-1), // num_threads,
(-1), // (level + 1),
(-1), // (level_last - 1 - level) * 5 + 2,
&tasks_DGEMM[jc],
begin,
end,
0L// nops);
);
queue_tmp0.push_back(tmp);
}
} // if (tasks_DGEMM[jc].size() > 0)
} // loop : ic
} // loop j
if (queue_tmp0.size() > 0) { // only the last part
copytask_list2seq(queue_dynamic[level],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_DGEMM1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 2);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} // if (queue_tmp0.size() > 0)
} // scope of task_name
} // if (level < (level_last - 1))
// -- DEALLACATE
{
string task_name = "X " + to_string(level + 1) + " : ";
queue_tmp0.clear();
C_task_seq* tmp =
new C_task_seq(C_DEALLOCATE,
_null_name,
(-1), // mutex_id
(-1), //TASK_PARALLEL,
(-1),//num_threads,
(-1),//(level + 1),
(-1),//(level_last - 1 - level) * 5 + 3,
&tasks_deallocLower[level + 1],
0,
tasks_deallocLower[level + 1].size(),
0L// nops);
);
queue_tmp0.push_back(tmp);
copytask_list2seq(queue_dynamic[level],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_DEALLOCATE1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 3);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
// -- DSUB offdiagonal --
{
string task_name = "s " + to_string(level + 1) + " : ";
queue_tmp0.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
if (!isMergedDTRSM[j]) {
const int end = tasks_Dsub[level + 1][j].size();
if (end > 0) { // to skip non allocated tasks_Dsub[level + 1][j][0]
const int begin = tasks_Dsub[level + 1][j][0]->parallel_max;
if ((end - begin) > 0) {
task_name += to_string(j) + " ";
C_task_seq* tmp =
new C_task_seq(C_DSUB,
_null_name,
(-1), // mutex_id
(-1), //TASK_PARALLEL,
(-1),//num_threads,
(-1),//(level + 1),
(-1),//(level_last - 1 - level) * 5 + 3,
&tasks_Dsub[level + 1][j],
begin,
end,
0L// nops);
);
queue_tmp0.push_back(tmp);
} // if ((end - begin) > 0)
} // if (end > 0)
} // if (!isMergedDTRSM[j])
} // loop : d / j
for (vector::const_iterator it = all_fathersIndex[level].begin();
it != all_fathersIndex[level].end(); ++it) {
const int size = tasks_Dsub[level + 1][*it].size();
if (size > 0) {
task_name += to_string(*it) + " ";
C_task_seq* tmp =
new C_task_seq(C_DSUB,
_null_name,
(-1), // mutex_id
(-1), //TASK_PARALLEL,
(-1), //num_threads,
(-1), //(level + 1),
(-1), //(level_last - 1 - level) * 5 + 3,
&tasks_Dsub[level + 1][*it],
0,
size,
0L// nops);
);
queue_tmp0.push_back(tmp);
}
} // loop : it
if (queue_tmp0.size() > 0) { // only the last part
copytask_list2seq(queue_dynamic[level],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_DSUB1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 4);
// erase temporary C_task_seq whose elements are copied to
// queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
}
// -- DEALLACATE
{
string task_name = "x " + to_string(level + 1) + " : ";
queue_tmp0.clear();
const int begdom1 = 1U << (level + 1);
const int enddom1 = begdom1 * 2;
for (int d = begdom1; d < enddom1; d++) {
const int j = btree->selfIndex(d);
C_task_seq* tmp =
new C_task_seq(C_DEALLOCATE,
_null_name,
(-1), // mutex_id
(-1), //TASK_PARALLEL,
(-1),//num_threads,
(-1),//(level + 1),
(-1),//(level_last - 1 - level) * 5 + 3,
&tasks_deallocLocalSchur[j],
0,
tasks_deallocLocalSchur[j].size(),
0L// nops);
);
queue_tmp0.push_back(tmp);
}
copytask_list2seq(queue_dynamic2[level],
queue_tmp0,
queue_null_,
// queue_dummy_,
task_name,
C_DEALLOCATE1,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 5);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
// level == 0 <==> num_leaves = 2
if (num_leaves <= num_threads) {
// trick to merge DFullLDLt into previous stage of DTRSM to follow
// the critical path
long *nops_sum = new long[num_threads];
for (int i = 0; i < num_threads; i++) {
nops_sum[i] = 0L;
}
vector starts(nb_doms_dense, 0);
vector starts_dtrsm(nb_doms_dense, 0);
vector starts_sub(nb_doms_dense, 0);
long nops_block_total = 0L;
// -- STARTING BLOCK : DTSRM + DGEMM + DSUB + DFULLLDLT --
list *> diag_starting;
list task_name_strs;
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
#ifdef DEBUG_PREPARE_THREAD
cout << "+ level = " << (level + 1) << " j = " << j << " children = "
<< children[j][0] << " " << children[j][1] << " : "
<< "# DFullLDLt @ " << level << " : " << j << " / "
<< tasks_DFullLDLt[j].size() << endl;
#endif
// 3 * 4 * 5 / 6 + 1 = 11
// 3 * 4 * 5 / 6 + 2 * 3 * 4 / 6 + 3 = 17
// if (tasks_DFullLDLt[j].size() > 4) { // with parallelizing
if(nrow_DFullLDLt[j] > 2) {
vector *tmp = new vector;
tmp->reserve(4 + 2 * (_isSym ? 3 : 6)); // 3 = 2 + 1
for (int ic = 0; ic < 2; ic++) {
const int jj = children[j][ic];
if ((nrow_DFullLDLt[jj] <= 2) && !isMergedDTRSM[jj]) {
// the case DFullLDLt and DTRSMScale are concatenated can be skipped
const int itmp = tasks_DTRSMScale[jj][0]->atomic_size;
for (int k = 0; k < itmp; k++) {
tmp->push_back(tasks_DTRSMScale[jj][k]);
}
if (_isSym) {
starts_dtrsm[jj] = tasks_DTRSMScale[jj][0]->atomic_size;
}
else {
for (int k = 0; k < tasks_DTRSMScale[jj][itmp]->atomic_size;
k++) {
tmp->push_back(tasks_DTRSMScale[jj][itmp + k]);
}
starts_dtrsm[jj] = (itmp +
tasks_DTRSMScale[jj][itmp]->atomic_size);
} // if (_isSym)
} // if ((nrow_DFullLDLt[jj] <= 2) && !isMergedDTRSM[jj])
tmp->push_back(tasks_DGEMM[jj][0]);
starts[jj] = 1;
} // loop : ic
tmp->push_back(tasks_Dsub[level + 1][j][0]); // null for many cases
tmp->push_back(tasks_DFullLDLt[j][0]);
diag_starting.push_back(tmp);
string task_name = "p " + to_string(level + 1) + " " + to_string(j);
task_name_strs.push_back(task_name);
starts_sub[j] = 1;
} // if(nrow_DFullLDLt[j] > 2)
} // loop : d
list::const_iterator kt = task_name_strs.begin();
{
int itmp = 0;
for (list *>::const_iterator it = diag_starting.begin();
it != diag_starting.end(); ++it, ++kt, itmp++){
long nops = 0L;
for (vector::const_iterator jt = (*it)->begin();
jt != (*it)->end(); ++jt) {
nops += *((*jt)->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(C_DIAG_START,
(*kt),
TASK_SINGLE,
(-1), // mutex_id
1,
(level + 1),
(level_last - 1 - level) * 6 + 1,
(*it),
0,
(*it)->size(),
nops);
queue_lists[itmp % num_threads].push_back(tmp);
nops_sum[itmp % num_threads] = nops;
nops_block_total += nops;
#ifdef DEBUG_PREPARE_THREAD
cout << "ll = " << itmp % num_threads
<< " critical path " << *kt << " nops = " << nops << endl;
#endif
} // loop : it, kt, itmp
} // scope of itmp
// -- DTRSM -- diangonal
task_assign_diag1(_queue_static,
tasks_DTRSMScale,
queue_null_,
// queue_dummy_,
nrow_DFullLDLt,
isMergedDTRSM,
"q",
C_DTRSM,
1, // int level_id,
num_threads,
level_last,
level,
begdom,
enddom,
nops_sum,
starts_dtrsm,
queue_lists,
false,
btree,
children);
// erase STL container defined in line 1499
for (list *>::iterator it = diag_starting.begin();
it != diag_starting.end(); ++it) {
delete (*it);
(*it) = NULL;
}
{ // begin : scope queue_tmp2
list queue_tmp2;
queue_tmp2.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
long nops = 0L;
if (isDividedDTRSM[jc]) {
const int end = tasks_DTRSMScale[jc].size();
for (int i = 0; i < end; i++) {
nops += *(tasks_DTRSMScale[jc][i]->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(C_DTRSM,
_null_name,
(-1), // mutex_id
(-1), // TASK_SINGLE,
(-1), // 1,
(-1), // (level + 1),
(-1), // (level_last - 1 - level) * 5 + 1,
&tasks_DTRSMScale[jc],
0,
end,
nops);
queue_tmp2.push_back(tmp);
} // if (isDividedDTRSM[jc])
} // loop : ic
} // loop : d
{ // begin : scope task_name
string task_name = "q Offdiag " + to_string(level + 1);
if (queue_tmp2.size() > 0) { // only the last block
copytask_list2seq(queue_dynamic1[level],
queue_tmp2,
queue_null_,
// queue_dummy_,
task_name,
C_DTRSM,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 1);
for (list::iterator it = queue_tmp2.begin();
it != queue_tmp2.end(); ++it) {
delete (*it);
(*it) = NULL;
} // loop : it
} // if (queue_tmp2.size() > 0)
} // end : scope task_name
} // end : scope queue_tmp2
if (level >= 0) {
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic1[level].begin();
it != queue_dynamic1[level].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
// the case queue_dynamic consists of only C_task_seq == 'x', copied here
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic2[level + 1].begin();
it != queue_dynamic2[level + 1].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
}
// -- DGEMM -- diagonal
vector null_idx;
task_assign_diag1(_queue_static,
tasks_DGEMM,
queue_null_,
// queue_dummy_,
null_idx, // not used
isMergedDTRSM,
"r",
C_DGEMM,
2, // int level_id,
num_threads,
level_last,
level,
begdom,
enddom,
nops_sum,
starts,
queue_lists,
true,
btree,
children);
// -- DSUB -- diagonal
task_assign_diag2(_queue_static,
tasks_Dsub[level + 1],
queue_null_,
// queue_dummy_,
isMergedDTRSM,
//tasks_DFullLDLt,
"s",
C_DSUB,
3, // int level_id,
num_threads,
level_last,
level,
begdom,
enddom,
nops_sum,
starts,
starts_sub,
queue_lists,
true,
btree,
children);
if (level == 0) {
// the case queue_dynamic consists of only C_task_seq == 'x', copied here
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic2[level].begin();
it != queue_dynamic2[level].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
}
// -- C_DFULL -- diagonal
queue_tmp0.clear();
queue_tmp1.clear();
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
long nops = 0L;
for (int i = starts_sub[j]; i < tasks_DFullLDLt[j].size(); i++) {
nops += *(tasks_DFullLDLt[j][i]->ops_complexity);
}
string task_name = "t& " + to_string(level) + " : " + to_string(j);
C_task_seq* tmp = new C_task_seq(C_DFULL,
task_name,
0, // mutex_id
TASK_SINGLE,
1,
level,
(level_last - level) * 6,
&tasks_DFullLDLt[j],
starts_sub[j],
tasks_DFullLDLt[j].size(),
nops);
if (starts_sub[j] > 0) {
queue_tmp0.push_back(tmp);
}
else {
queue_tmp1.push_back(tmp);
}
}
const int size_task0 = queue_tmp0.size();
const int size_threads = num_threads - queue_tmp1.size();
#ifdef DEBUG_PREPARE_THREAD
cout << "*** C_DFULL : parallel = " << size_task0 << " : serial "
<< queue_tmp1.size() << " / ";
#endif
if (size_task0 > 0 && size_threads > 0) {
queue_tmp0.sort(C_task_seq_complexity_greater);
int mm0 = size_threads % size_task0;
const int mm = (size_threads / size_task0) + (mm0 != 0);
if (mm0 == 0) {
mm0 = size_task0;
}
int jj = 0;
for (list::const_iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it, jj++) {
const int multplcty = (jj < mm0) ? mm : (mm - 1);
#ifdef DEBUG_PREPARE_THREAD
cout << (*it)->task_id << " : " << (*it)->task_name
<< " : < " << multplcty << " > ";
#endif
const int parallel_single =
(multplcty == 1) ? TASK_SINGLE : TASK_PARALLEL;
// copy raw task into a task sequence whose length is one
list queue_tmp2, queue_tmp3;
queue_tmp2.push_back(*it);
copytask_list2seq(queue_tmp3,
queue_tmp2,
queue_null_,
// queue_dummy_,
(*it)->task_name,
(*it)->task_id,
jj,
parallel_single,
multplcty,
(*it)->level,
(*it)->phase);
// threads share one task (*it)
for (int m = 0; m < mm; m++) {
const int n = jj + m * size_task0;
if (n < size_threads) {
_queue_static[n % num_threads].push_back(queue_tmp3.front());
// _queue_static[n % num_threads].push_back(seq_tmp);
#ifdef DEBUG_PREPARE_THREAD
cout << "[ " << jj << " @ " << n << " : "
<< n % num_threads << " ]";
#endif
}
}
} // loop : j
#ifdef DEBUG_PREPARE_THREAD
cout << "/ ";
#endif
jj = size_threads;
for (list::const_iterator it = queue_tmp1.begin();
it != queue_tmp1.end(); ++it, jj++) {
// copy for each thread
list queue_tmp2, queue_tmp3;
queue_tmp2.push_back(*it);
copytask_list2seq(queue_tmp3,
queue_tmp2,
queue_null_,
// queue_dummy_,
(*it)->task_name,
(*it)->task_id,
0,
TASK_SINGLE,
1,
(*it)->level,
(*it)->phase);
_queue_static[jj % num_threads].push_back(queue_tmp3.front());
#ifdef DEBUG_PREPARE_THREAD
cout << jj << " ; " << jj % num_threads << " / ";
#endif
}
#ifdef DEBUG_PREPARE_THREAD
cout << endl;
#endif
// delete original C_task_seq after copying to all threads
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
for (list::iterator it = queue_tmp1.begin();
it != queue_tmp1.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} // if (size_task0 > 0)
else { // (size_task0 == 0) || (size_threads <= 0)
#ifdef DEBUG_PREPARE_THREAD
cout << endl;
#endif
{
int itmp = 0;
queue_tmp1.sort(C_task_seq_complexity_greater);
for (list::const_iterator it = queue_tmp1.begin();
it != queue_tmp1.end(); ++it, itmp++) {
(*it)->parallel_single = TASK_SINGLE;
queue_lists[itmp % num_threads].push_back(*it);
} // loop : it, itmp
}
{
string task_name = "t " + to_string(level);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(_queue_static[p],
queue_lists[p],
queue_null_,
// queue_dummy_,
task_name,
C_DFULL,
p,
TASK_SINGLE,
1,
level,
(level_last - level) * 6);
} // loop : p
// (queue_tmp0.size() == 0) ? for safty of non-memory-leak
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
for (list::iterator it = queue_tmp1.begin();
it != queue_tmp1.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
} // if (size_task > 0)
if (level > 0) {
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic[level].begin();
it != queue_dynamic[level].end(); ++it) {
_queue_static[p].push_back(*it);
}
}
}
delete [] nops_sum;
} //
else { // if (num_leaves <= num_threads)
if (level < (level_last - 1)) {
// -- DTRSM -- diagonal
queue_tmp0.clear();
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
list queue_tmp2;
queue_tmp2.clear();
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
#ifdef DEBUG_PREPARE_THREAD
cout << "* level = " << (level + 1) << " j = " << j << " children = "
<< children[j][0] << " " << children[j][1] << " " << endl;
#endif
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
if (tasks_DTRSMScale[jc].size() > 0) {
long nops = 0L;
if (isDividedDTRSM[jc]) {
const int end = tasks_DTRSMScale[jc].size();
for (int i = 0; i < end; i++) {
nops += *(tasks_DTRSMScale[jc][i]->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(C_DTRSM,
_null_name,
(-1), // mutex_id
(-1), // TASK_SINGLE,
(-1), // 1,
(-1), // (level + 1),
(-1), // (level_last - 1 - level) * 5 + 1,
&tasks_DTRSMScale[jc],
0,
end,
nops);
queue_tmp2.push_back(tmp);
} // if (isDividedDTRSM[jc])
else {
int end;
if (!isMergedDTRSM[j]) { // looking the father node
end = IndexTask(tasks_DTRSMScale[jc],
tasks_DTRSMScale[jc][0]->parallel_max);
}
else {
end = tasks_DTRSMScale[jc].size();
}
for (int i = 0; i < end; i++) {
nops += *(tasks_DTRSMScale[jc][i]->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(C_DTRSM,
_null_name,
(-1), // mutex_id
(-1), // TASK_SINGLE,
(-1), // 1,
(-1), // (level + 1),
(-1), // (level_last - 1 - level) * 5 + 1,
&tasks_DTRSMScale[jc],
0,
end,
nops);
queue_tmp0.push_back(tmp);
} // if (isDividedDTRSM[jc])
} // if (tasks_DTRSMScale[jc].size() > 0)
} // loop : ic
} // loop : d
queue_tmp0.sort(C_task_seq_complexity_smaller);
{ // begin : scope itmp
int itmp = 0;
for (list::const_iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it, itmp++) {
queue_lists[itmp % num_threads].push_back(*it);
} // loop : it
} // end : scope itmp
{ // begin : scope task_name
string task_name = "q diag " + to_string(level + 1);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(_queue_static[p],
queue_lists[p],
queue_null_,
// queue_dummy_,
task_name,
C_DTRSM,
p,
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + 1);
}
// erase temporary C_task_seq whose elements are copied to
// queue_static[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} // end : scope task_name
{ // begin : scope task_name
string task_name = "q Offdiag " + to_string(level + 1);
if (queue_tmp2.size() > 0) { // only the last block
copytask_list2seq(queue_dynamic1[level],
queue_tmp2,
queue_null_,
// queue_dummy_,
task_name,
C_DTRSM,
0, // shared by all threads
TASK_PARALLEL,
num_threads,
(level + 1),
(level_last - 1 - level) * 6 + 1);
// erase temporary C_task_seq whose elements are copied to queue_dynamic[]
for (list::iterator it = queue_tmp2.begin();
it != queue_tmp2.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} // if (queue_tmp2.size() > 0)
} // end : scope task_name
if (level >= 0) {
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic1[level].begin();
it != queue_dynamic1[level].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
// C_task_seq == 'x', copied here
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic2[level + 1].begin();
it != queue_dynamic2[level + 1].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
} // if (level >= 0)
// -- DGEMM -- diagonal
queue_tmp0.clear();
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
for (int ic = 0; ic < 2; ic++) {
const int jc = children[j][ic];
const int tasks_size = tasks_DGEMM[jc].size();
if (tasks_size > 0) {
long nops = 0L;
int end;
int itmp = tasks_DGEMM[jc][0]->parallel_max;
// if (itmp <= (_isSym ? 3 : 4)) {
#if 1
if (!isMergedDTRSM[j]) {
end = itmp;
}
else {
end = ((itmp == tasks_size) ? tasks_size :
itmp + tasks_DGEMM[jc][itmp]->parallel_max);
}
#else
end = ((itmp == tasks_size) ? tasks_size :
itmp + tasks_DGEMM[jc][itmp]->parallel_max);
#endif
for (int i = 0; i < end; i++) {
nops += *(tasks_DGEMM[jc][i]->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(C_DGEMM,
_null_name,
(-1), // mutex_id
(-1), // TASK_SINGLE,
(-1), //1,
(-1), //(level + 1),
(-1), //(level_last - 1 - level) * 5 + 2,
&tasks_DGEMM[jc],
0,
end,
nops);
queue_tmp0.push_back(tmp);
} // if (tasks_DGEMM[jc].size() > 0)
} // loop : ic
} // loop : d
queue_tmp0.sort(C_task_seq_complexity_greater);
{
int itmp = 0;
for (list::const_iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it, itmp++) {
queue_lists[itmp % num_threads].push_back(*it);
} // loop : it
}
{
string task_name = "r " + to_string(level + 1);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(_queue_static[p],
queue_lists[p],
queue_null_,
// queue_dummy_,
task_name,
C_DGEMM,
p,
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + 2);
}
// erase temporary C_task_seq whose elements are copied to
// queue_static[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
}
} // if (level == (level_last - 1))
// -- DSUB -- diagonal
queue_tmp0.clear();
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
long nops = 0L;
if (tasks_Dsub[level + 1][j].size() > 0) {
int end;
// if (tasks_DFullLDLt[j].size() <= 4) {
// if(nrow_DFullLDLt[j] <= 2) {
if (!isMergedDTRSM[j]) {
end = tasks_Dsub[level + 1][j][0]->parallel_max;
}
else {
end = tasks_Dsub[level + 1][j].size();
}
for (int i = 0; i < end; i++) {
nops += *(tasks_Dsub[level + 1][j][i]->ops_complexity);
}
C_task_seq* tmp =
new C_task_seq(C_DSUB,
_null_name,
(-1), // mutex_id
(-1), // TASK_SINGLE,
(-1), //1,
(-1), //(level + 1),
(-1), //(level_last - 1 - level) * 5 + 3,
&tasks_Dsub[level + 1][j],
0,
end,
// tasks_Dsub[level + 1][j][0]->parallel_max,
nops);
queue_tmp0.push_back(tmp);
}
} // loop : d
queue_tmp0.sort(C_task_seq_complexity_greater);
{
int itmp = 0;
for (list::const_iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it, itmp++) {
queue_lists[itmp % num_threads].push_back(*it);
} // loop : it
}
{ // begin : scope for task_name;
string task_name = "s " + to_string(level + 1);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(_queue_static[p],
queue_lists[p],
queue_null_,
// queue_dummy_,
task_name,
C_DSUB,
p,
TASK_SINGLE,
1,
(level + 1),
(level_last - 1 - level) * 6 + 3);
}
// erase temporary C_task_seq whose elements are copied to
// queue_static[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} // end : scope for task_name;
if (level == 0) {
// the case queue_dynamic consists of only C_task_seq == 'x', copied here
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic2[level].begin();
it != queue_dynamic2[level].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
}
// -- C_DFULL --
queue_tmp0.clear();
for (int p = 0; p < num_threads; p++) {
queue_lists[p].clear();
}
for (int d = begdom; d < enddom; d++) {
const int j = btree->selfIndex(d);
long nops = 0L;
for (int i = 0; i < tasks_DFullLDLt[j].size(); i++) {
nops += *(tasks_DFullLDLt[j][i]->ops_complexity);
}
string task_name = "t " + to_string(level) + " : " + to_string(j);
C_task_seq* tmp = new C_task_seq(C_DFULL,
task_name,
(-1), // mutex_id
TASK_SINGLE,
1,
level,
(level_last - level) * 6,
&tasks_DFullLDLt[j],
0,
tasks_DFullLDLt[j].size(),
nops);
queue_tmp0.push_back(tmp);
} // loop : d
queue_tmp0.sort(C_task_seq_complexity_greater);
{
int itmp = 0;
for (list::const_iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it, itmp++) {
queue_lists[itmp % num_threads].push_back(*it);
} // loop : it
}
// begin : scope for task_name;
{
string task_name = "t " + to_string(level);
for (int p = 0; p < num_threads; p++) {
copytask_list2seq(_queue_static[p],
queue_lists[p],
queue_null_,
// queue_dummy_,
task_name,
C_DFULL,
p,
TASK_SINGLE,
1,
level,
(level_last - level) * 6);
}
// erase temporary C_task_seq whose elements are copied to
// queue_static[]
for (list::iterator it = queue_tmp0.begin();
it != queue_tmp0.end(); ++it) {
delete (*it);
(*it) = NULL;
}
} // end : scope for task_name
if ((level > 0)) { // && (level < (level_last - 1))) {
for (int p = 0; p < num_threads; p++) {
for(list::const_iterator it = queue_dynamic[level].begin();
it != queue_dynamic[level].end(); ++it) {
_queue_static[p].push_back(*it);
}
} // loop : p
}
// dependency
} // if (num_leaves < num_threads)
} // loop : level
// begin : counting task size
{
for (int p = 0; p < num_threads; p++) {
#ifdef DEBUG_PREPARE_THREAD
cout << "thread = " << p << " @ " << _queue_static[p].size() << " / ";
#endif
for (list::const_iterator it = _queue_static[p].begin();
it != _queue_static[p].end(); ++it) {
if ((*it)->parallel_single == TASK_SINGLE) {
#ifdef DEBUG_PREPARE_THREAD
cout << (*it)->task_name << " [ "
<< (*it)->begin << " : " << (*it)->end << " ] ; "
<< (*it)->ops_complexity << " / ";
#endif
nops_queue[p][(*it)->level] += (*it)->ops_complexity;
}
if ((*it)->parallel_single == TASK_PARALLEL) {
#ifdef DEBUG_PREPARE_THREAD
cout << (*it)->task_name << " [[ "
<< (*it)->begin << " : " << (*it)->end << " ]] ; "
<< (*it)->ops_complexity << " / ";
#endif
if (((*it)->num_threads > 0) && ((*it)->task_id == C_DFULL)) {
// cout << "mutex_id = " << (*it)->mutex_id;
nops_queue[p][(*it)->level] +=
(*it)->ops_complexity / (long)(*it)->num_threads;
}
if ((*it)->level == 1) {
nops_queue[num_threads][(*it)->level] += (*it)->ops_complexity;
}
}
}
#ifdef DEBUG_PREPARE_THREAD
cout << endl;
#endif
}
#ifdef DEBUG_PREPARE_THREAD
cout << "shared / ";
#endif
for (int level = level_last; level >=0; level--) {
#ifdef DEBUG_PREPARE_THREAD
cout << "level = " << level << endl;
#endif
for (list::const_iterator it = queue_dynamic[level].begin();
it != queue_dynamic[level].end(); ++it) {
#ifdef DEBUG_PREPARE_THREAD
cout << (*it)->task_name << " [ "
<< (*it)->begin << " : " << (*it)->end << " ] ; "
<< (*it)->ops_complexity << " / ";
#endif
nops_queue[num_threads][(*it)->level] += (*it)->ops_complexity;
}
#ifdef DEBUG_PREPARE_THREAD
cout << endl;
#endif
}
#ifdef DEBUG_PREPARE_THREAD
for (int level = (level_last + 1); level >= 0; level--) {
cout << "level = " << level << " : ";
for (int j = 0; j <= num_threads; j++) {
cout << nops_queue[j][level] << " ";
}
cout << endl;
}
#endif
}
// end : counting task size
// copy tasks in reverse order
{
int itmp = 0;
for (int i = 0; i <= level_last; i++) {
itmp += queue_dynamic[i].size();
itmp += queue_dynamic1[i].size();
itmp += queue_dynamic2[i].size(); // C_DEALLOCATE
// itmp += queue_dynamic3[i].size(); // C_DEALLOCATE
}
_queue_dynamic->reserve(itmp);
}
for (int i = 0; i <= level_last; i++) {
const int level = level_last - i;
for (list::const_iterator it = queue_dynamic[level].begin();
it != queue_dynamic[level].end(); ++it) {
_queue_dynamic->push_back(*it);
}
for (list::const_iterator it = queue_dynamic1[level].begin();
it != queue_dynamic1[level].end(); ++it) {
_queue_dynamic->push_back(*it);
}
for (list::const_iterator it = queue_dynamic2[level].begin();
it != queue_dynamic2[level].end(); ++it) {
_queue_dynamic->push_back(*it);
}
}
// begin : scope for fout
if (false) {
char fname[256];
int pid = get_process_id();
sprintf(fname, "tasks-created.%d.data", pid);
FILE *fp;
if ((fp = fopen(fname, "a")) != NULL) {
write_dependency(fp);
}
else {
fprintf(stderr,
"%s %d : fail to open %s\n",
__FILE__, __LINE__, fname);
exit(-1);
}
}
queue_dynamic0->clear();
for (int i = 0; i < (level_last + 1); i++) {
queue_dynamic[i].clear();
queue_dynamic1[i].clear();
queue_dynamic2[i].clear();
// queue_dynamic3[i].clear();
}
delete [] queue_dynamic;
delete [] queue_dynamic1;
delete [] queue_dynamic2;
// delete [] queue_dynamic3;
delete queue_dynamic0;
for (int i = 0; i < num_threads; i++) {
queue_lists[i].clear();
}
delete [] queue_lists;
}
void QueueRuntime::write_dependency(FILE *fp)
{
for (int p = 0; p < _num_threads; p++) {
fprintf(fp, "*** thread = %d @ %d ***\n",
p, (int)_queue_static[p].size());
for (list::const_iterator it = _queue_static[p].begin();
it != _queue_static[p].end(); ++it) {
fprintf(fp, "** %d C_task_seq = %d %s %s **\n",
p, (*it)->task_id, (*it)->task_name,
(((*it)->parallel_single == TASK_SINGLE) ? " single " : " shared "));
for (int j = (*it)->begin; j < (*it)->end; j++) {
fprintf(fp, "%s : ", (*(*it)->queue)[j]->task_name);
if ((*(*it)->queue)[j]->atomic_size > 1) {
fprintf(fp, "atomic %d / %d ",
(*(*it)->queue)[j]->atomic_id,
(*(*it)->queue)[j]->atomic_size);
}
// list& parents = *(*(*it)->queue)[j]->parents_work;
list& parents = *(*(*it)->queue)[j]->parents;
fprintf(fp, "parents = %d / ", (int)parents.size());
for (list::const_iterator jt = parents.begin();
jt != parents.end(); ++jt) {
fprintf(fp, "[%p] %s / ", (*jt), (*jt)->task_name);
}
fprintf(fp, "\n");
}
} // loop : it
} // loop : p
fprintf(fp, "*** dynamic : %d ***\n", (int)_queue_dynamic->size());
for (vector::const_iterator it = _queue_dynamic->begin();
it != _queue_dynamic->end(); ++it) {
fprintf(fp, "** C_task_seq = %d : %s [ %d %d] %d **\n",
(*it)->task_id,
(*it)->task_name,
(*it)->begin, (*it)->end,
(*it)->pos);
for (int j = (*it)->begin; j < (*it)->end; j++) {
fprintf(fp, "%s : ", (*(*it)->queue)[j]->task_name);
if ((*(*it)->queue)[j]->atomic_size > 1) {
fprintf(fp, " atomic %d / %d ",
(*(*it)->queue)[j]->atomic_id,
(*(*it)->queue)[j]->atomic_size);
}
// list& parents = *(*(*it)->queue)[j]->parents_work;
list& parents = *(*(*it)->queue)[j]->parents;
fprintf(fp, "parents = %d / ", (int)parents.size());
for (list::const_iterator jt = parents.begin();
jt != parents.end(); ++jt) {
fprintf(fp, "[%p] %s / ", (*jt), (*jt)->task_name);
}
fprintf(fp, "\n");
}
} // loop : it
} // end : scope for fout
void QueueRuntime::exec_symb_fact()
{
const int num_threads = _num_threads;
#ifdef POSIX_THREADS
void* results;
pthread_attr_t th_attr;
#endif
vector threads;
//#else
// vector threads;
//#endif
clock_t t0_cpu, t1_cpu;
elapsed_t t0_elapsed, t1_elapsed;
// struct timespec ts0, ts1;
int ierr;
diss_printf(_verbose, _fp,
"symbolic factorization of sparse matrices with %d threads\n",
num_threads);
#ifdef POSIX_THREADS
// threads = new pthread_t[num_threads];
threads.resize(num_threads);
ierr = pthread_mutex_init(&_mutex_root, NULL);
if (ierr != 0) {
diss_printf(_verbose, _fp,
"%s %d : pthread_mutex_init(&_mutex_root, NULL) : %d\n",
__FILE__, __LINE__, ierr);
}
#endif
#ifdef POSIX_THREADS
#ifdef DEBUG_EXEC_THREAD
ierr = pthread_mutex_init(&_mutex_debug, NULL);
#endif
if (ierr != 0) {
diss_printf(_verbose, _fp,
"%s %d : pthread_mutex_init(&_mutex_debug, NULL) %d\n",
__FILE__, __LINE__, ierr);
}
pthread_attr_init(&th_attr);
pthread_attr_setdetachstate(&th_attr, PTHREAD_CREATE_JOINABLE);
#endif
#ifdef DEBUG_EXEC_THREAD_FILE
{
int pid = get_process_id();
char fname[256];
sprintf(fname, "task-s.%d.data", pid);
_fout.open(fname);
}
#endif
t0_cpu = clock();
get_realtime(&t0_elapsed);
#ifdef POSIX_THREADS
THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
for (int p = 0; p < num_threads; p++) {
params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
int pid = pthread_create(&threads[p], &th_attr,
&thread_queue_symb_factorize_,
(void *)params[p]);
if (pid != 0) {
fprintf(stderr, "bad thread creation ? : %d\n", pid);
exit(0);
}
}
pthread_attr_destroy(&th_attr);
for (int p = 0; p < num_threads; p++) {
int pid = pthread_join(threads[p], &results);
if (pid != 0) {
fprintf(stderr, "bad thread creation ? : %d\n", pid);
exit(0);
}
delete params[p];
}
delete [] params;
#else
THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
for (int p = 0; p < num_threads; p++) {
params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
threads.push_back(std::thread(thread_queue_symb_factorize_,
(void *)params[p]));
}
for (int p = 0; p < num_threads; p++) {
threads[p].join();
delete params[p];
}
delete [] params;
#endif
t1_cpu = clock();
get_realtime(&t1_elapsed);
diss_printf(_verbose, _fp,
"execution of symb queue : cpu time = %.4e elapsed time = %.4e\n",
(double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
convert_time(t1_elapsed, t0_elapsed));
#ifdef DEBUG_EXEC_THREAD_FILE
_fout.close();
#endif
#ifdef DEBUG_THREAD_TIME
{
int pid = get_process_id();
char filename[256];
FILE *fp;
sprintf(filename, "threadtime-symb.%d.data", pid);
if ((fp = fopen(filename, "w")) == NULL) {
fprintf(stderr, "%s %d : fail to open %s\n",
__FILE__, __LINE__, filename);
exit(-1);
}
else {
for (int j = _queue_symb->begin; j < _queue_symb->end; j++) {
fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
(*_queue_symb->queue)[j]->task_name,
(*_queue_symb->queue)[j]->thread_id,
convert_sec((*_queue_symb->queue)[j]->t0),
convert_microsec((*_queue_symb->queue)[j]->t0),
convert_sec((*_queue_symb->queue)[j]->t1),
convert_microsec((*_queue_symb->queue)[j]->t1),
*((*_queue_symb->queue)[j]->ops_complexity));
}
fclose(fp);
} // if fopen()
}
#endif
#ifdef POSIX_THEADS
pthread_mutex_destroy(&_mutex_root);
#ifdef DEBUG_EXEC_THREAD
pthread_mutex_destroy(&_mutex_debug);
#endif
#endif
threads.clear();
}
void QueueRuntime::exec_num_fact_debug()
{
diss_printf(_verbose, _fp,
"numerical factorization with single threads :: DEBUG\n");
int *permute_block = new int[SIZE_B1];
list::const_iterator *its = new list::const_iterator[_num_threads];
diss_printf(_verbose, _fp,
"*** thread = 0 @ %d ***\n", (int)_queue_static[0].size());
for (int p = 0; p < _num_threads; p++) {
its[p] = _queue_static[p].begin();
}
for (list::const_iterator it = _queue_static[0].begin();
it != _queue_static[0].end(); ++it) {
diss_printf(_verbose, _fp, "** C_task_seq = %d : %s, %s **\n",
(*it)->task_id, (*it)->task_name ,
(((*it)->parallel_single == TASK_SINGLE) ? " single " : " shared "));
for (int j = (*it)->begin; j < (*it)->end; j++) {
diss_printf(_verbose, _fp, "%s : ", (*(*it)->queue)[j]->task_name);
if ((*(*it)->queue)[j]->atomic_size > 1) {
diss_printf(_verbose, _fp, "atomic %d / %d ",
(*(*it)->queue)[j]->atomic_id,
(*(*it)->queue)[j]->atomic_size);
}
else {
diss_printf(_verbose, _fp, "\n");
}
execute_task_debug(*it, j, permute_block, 0);
if ((*(*it)->queue)[j]->quit_queue) {
return;
}
} // loop : j
for (int p = 1 ; p < _num_threads; p++) {
diss_printf(_verbose, _fp, "** C_task_seq = %d : %s %s **\n",
(*its[p])->task_id, (*its[p])->task_name,
(((*its[p])->parallel_single == TASK_SINGLE) ? " single " : " shared "));
if ((*its[p])->parallel_single == TASK_SINGLE) {
for (int j = (*its[p])->begin; j < (*its[p])->end; j++) {
diss_printf(_verbose, _fp, "%s : ",
(*(*its[p])->queue)[j]->task_name);
if ((*(*its[p])->queue)[j]->atomic_size > 1) {
diss_printf(_verbose, _fp, " atomic %d / %d\n",
(*(*its[p])->queue)[j]->atomic_id,
(*(*its[p])->queue)[j]->atomic_size);
}
else {
diss_printf(_verbose, _fp, "\n");
}
execute_task_debug(*its[p], j, permute_block, 0);
if ((*(*its[p])->queue)[j]->quit_queue) {
return;
}
} // loop : j
} // if ((*its[p])->parallel_single == TASK_SINGLE)
++its[p];
} // loop : p > 0
} // loop : it
}
void QueueRuntime::execute_task_debug(C_task_seq *seq, int pos,
int *permute_block,
int pid)
{
C_task *task = (*seq->queue)[pos];
#ifdef DEBUG_CHECKPARENTS_DONE
// debugging
int waiting;
waiting = check_parents_done(task);
if (waiting > 0) {
{
cerr << pid << " parents of task " << task->task_name
<< " not finished : ";
for(list::const_iterator nt = task->parents_work->begin();
nt != task->parents_work->end(); ++nt) {
cerr << (*nt)->task_name << " ";
}
cerr << endl;
}
}
//
#endif
// accuessing to unsigned char does not need mutex
task->status = TASK_WORKING;
//
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t0));
// clock_gettime(CLOCK_MONOTONIC, &(task->t0));
#endif
// debugging : 13 :Apr.2012 Atsushi
task->func(task->func_arg);
if (task->task_id == C_DFULL_SYM_GAUSS) {
// task->quit_queue = ((C_dfull_gauss_arg*)task->func_arg)->quit;
for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
(*seq->queue)[i]->status = TASK_DONE;
(*seq->queue)[i]->quit_queue = true;
}
}
// accuessing to unsigned char does not neet mutex
task->status = TASK_DONE;
//
}
void QueueRuntime::exec_num_fact(const int called)
{
// unsigned int ui;
const int num_threads = _num_threads;
#ifdef POSIX_THREADS
void* results;
pthread_attr_t th_attr;
vector threads;
#else
vector threads;
#endif
clock_t t0_cpu, t1_cpu;
elapsed_t t0_elapsed, t1_elapsed;
// struct timespec ts0, ts1;
#ifdef DEBUG_PRINT_TASK
_fps = new FILE*[num_threads];
char fname[256];
for (int p = 0; p < num_threads; p++) {
sprintf(fname, "log.%04d.data", p);
_fps[p] = fopen(fname, "w");
}
#endif
t0_cpu = clock();
get_realtime(&t0_elapsed);
// clock_gettime(CLOCK_REALTIME, &ts0);
diss_printf(_verbose, _fp,
"numerical factorization with %d threads\n", num_threads);
_queue_dynamic_pos_start = (int)((double)(_queue_dynamic->size())
* RATIO_QUEUE_GREEDY);
_queue_dynamic_pos = _queue_dynamic_pos_start;
_queue_dynamic_notcopied = num_threads;
// reset status for numeric queue execution
_waiting_root = 0;
_phase_dynamic = 0;
for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
_zone_entered[i] = 0;
_zone_finished[i] = 0;
}
for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
_zone_static_assigned[i] = 0;
}
for (int p = 0; p < num_threads; p++) {
for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
_begins[p][i] = 0;
_ends[p][i] = 0;
}
for (int q = 0; q < DIST_TASK_CRITICAL; q++) {
for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
_group_entered[p][q][i] = 0;
_group_finished[p][q][i] = 0;
_group_task_ends[p][q][i] = (-1);
_group_static_assigned[p][q][i] = (-1);
}
} // loop : q
} // loop : p
#ifdef POSIX_THREADS
pthread_mutex_init(&_mutex_file, NULL);
pthread_mutex_init(&_mutex_dependency, NULL);
pthread_attr_init(&th_attr);
pthread_attr_setdetachstate(&th_attr, PTHREAD_CREATE_JOINABLE);
for (int p = 0; p < num_threads; p++) {
pthread_mutex_init(&_mutex_group[p], NULL);
}
// threads = new pthread_t[num_threads];
threads.resize(num_threads);
pthread_mutex_init(&_mutex_root, NULL);
pthread_mutex_init(&_mutex_debug, NULL);
pthread_cond_init(&_cond_root, NULL);
#endif
#ifdef DEBUG_EXEC_THREAD_FILE
{
int pid = get_process_id();
char fname[256];
sprintf(fname, "task-n.%d.data", pid);
cerr << "== task log == " << fname << endl;
_fout.open(fname);
}
#endif
#if 1
{
// copy dependency data : parents -> parents_work
for (int p = 0; p < _num_threads; p++) {
for (list::const_iterator it = _queue_static[p].begin();
it != _queue_static[p].end(); ++it) {
vector &queue = *(*it)->queue;
for (int j = (*it)->begin; j < (*it)->end; j++) {
list& parents_work = *(queue[j]->parents_work);
if (parents_work.size() > 0) { // to avoid double free
parents_work.clear();
}
} // loop : j
} // loop : it
}
for (vector::const_iterator it = _queue_dynamic->begin();
it != _queue_dynamic->end(); ++it) {
vector &queue = *((*it)->queue);
for (int j = (*it)->begin; j < (*it)->end; j++) {
list& parents_work = *(queue[j]->parents_work);
if (parents_work.size() > 0) { // to avoid double free
parents_work.clear();
}
} // loop : j
} // loop : it
for (int p = 0; p < _num_threads; p++) {
for (list::const_iterator it = _queue_static[p].begin();
it != _queue_static[p].end(); ++it) {
vector &queue = *(*it)->queue;
for (int j = (*it)->begin; j < (*it)->end; j++) {
queue[j]->quit_queue = false;
list& parents = *(queue[j]->parents);
list& parents_work = *(queue[j]->parents_work);
if (parents_work.size() == 0) {
#ifdef SX_ACE
for (list::const_iterator lt = parents.begin();
lt != parents.end(); ++lt) {
parents_work.push_back(*lt);
}
#else // SX-ACE C++ rev 110 with C++98/03 does not understand back_insertera
std::copy(parents.begin(), parents.end(),
back_inserter(parents_work));
#endif
}
queue[j]->status = TASK_WAITING; // reset status
} // loop : j
(*it)->pos = (*it)->begin;
} // loop : it
}
for (vector::const_iterator it = _queue_dynamic->begin();
it != _queue_dynamic->end(); ++it) {
vector &queue = *((*it)->queue);
for (int j = (*it)->begin; j < (*it)->end; j++) {
queue[j]->quit_queue = false;
list& parents = *(queue[j]->parents);
list& parents_work = *(queue[j]->parents_work);
if (parents_work.size() == 0) {
#ifdef SX_ACE
for (list::const_iterator lt = parents.begin();
lt != parents.end(); ++lt) {
parents_work.push_back(*lt);
}
#else // SX-ACE C++ rev 110 with C++98/03 does not understand back_inserter
std::copy(parents.begin(), parents.end(), back_inserter(parents_work));
#endif
}
queue[j]->status = TASK_WAITING; // reset status
} // loop : j
(*it)->pos = (*it)->begin;
} // loop : it
}
#endif
// begin : scope for fout
if (0) {
char fname[256];
int pid = get_process_id();
sprintf(fname, "tasks-before.%d.%d.data", pid, called);
FILE *fp;
if ((fp = fopen(fname, "a")) != NULL) {
write_dependency(fp);
fclose(fp);
}
else {
fprintf(stderr,
"%s %d : fail to open %s\n",
__FILE__, __LINE__, fname);
exit(-1);
}
} // end : scope for fout
t0_cpu = clock();
get_realtime(&t0_elapsed);
#ifdef POSIX_THREADS
THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
for (int p = 0; p < num_threads; p++) {
params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
int pid = pthread_create(&threads[p], &th_attr,
&thread_queue_num_factorize_,
(void *)params[p]);
if (pid != 0) {
fprintf(_fp, "bad thread creation ? : %d\n", pid);
exit(0);
}
}
pthread_attr_destroy(&th_attr);
for (int p = 0; p < num_threads; p++) {
int pid = pthread_join(threads[p], &results);
if (pid != 0) {
fprintf(_fp, "bad thread creation ? : %d\n", pid);
exit(0);
}
delete params[p];
}
delete [] params;
#else
THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
for (int p = 0; p < num_threads; p++) {
params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
threads.push_back(std::thread(thread_queue_num_factorize_,
(void *)params[p]));
}
for (int p = 0; p < num_threads; p++) {
threads[p].join();
delete params[p];
}
delete [] params;
#endif
t1_cpu = clock();
get_realtime(&t1_elapsed);
diss_printf(_verbose, _fp,
"execution of num queue : cpu time = %.4e elapsed time = %.4e\n",
(double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
convert_time(t1_elapsed, t0_elapsed));
#ifdef DEBUG_EXEC_THREAD_FILE
_fout.close();
#endif
// begin : scope for fout
if (0) {
char fname[256];
int ppid = get_process_id();
sprintf(fname, "tasks-copied.%d.data", ppid);
FILE *fp;
if ((fp = fopen(fname, "a")) != NULL) {
write_dependency(fp);
fclose(fp);
}
else {
fprintf(stderr,
"%s %d : fail to open %s\n",
__FILE__, __LINE__, fname);
exit(-1);
}
}
#ifdef DEBUG_THREAD_TIME
{
int pid = get_process_id();
char filename[256];
FILE *fp;
for (int p = 0; p < num_threads; p++) {
for (list::const_iterator it = _queue_static[p].begin();
it != _queue_static[p].end(); ++it) {
(*it)->status = TASK_WAITING;
}
}
for (vector::const_iterator it = _queue_dynamic->begin();
it != _queue_dynamic->end(); ++it) {
(*it)->status = TASK_WAITING;
}
sprintf(filename, "threadtime-num.%d.data", pid);
if ((fp = fopen(filename, "w")) == NULL) {
fprintf(stderr, "%s %d : fail to open %s\n",
__FILE__, __LINE__, filename);
exit(-1);
}
else {
fprintf(fp, "**** numeric factorization start ****\n");
for (int p = 0; p < num_threads; p++) {
fprintf(fp, "*** thread = %d @ %d ** ", p,
(int)_queue_static[p].size());
for (list::const_iterator it = _queue_static[p].begin();
it != _queue_static[p].end(); ++it) {
fprintf(fp, "** %d C_task_seq = %d : %s %s **\n",
p, (*it)->task_id,
((*it)->parallel_single == TASK_SINGLE ? "distributed " : "shared "),
(*it)->task_name);
if ((*it)->status == TASK_DONE) {
continue;
}
for (int j = (*it)->begin; j < (*it)->end; j++) {
if ((*(*it)->queue)[j]->task_id == C_SPARSESCHUR) {
elapsed_t t0, t1;
t0 = (*(*it)->queue)[j]->t0;
t1 = ((C_SparseNumFact_arg *)(*(*it)->queue)[j]->func_arg)->tt[0];
string task_name = "o0 : ";
fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
task_name.c_str(),
// (*(*it)->queue)[j]->task_name,
(*(*it)->queue)[j]->thread_id,
convert_sec(t0),
convert_microsec(t0),
convert_sec(t1),
convert_microsec(t1), 0L);
for (int i = 0; i < 4; i++) {
string task_name = "o" + to_string(i + 1) + " : ";
t0 = ((C_SparseNumFact_arg *)(*(*it)->queue)[j]->func_arg)->tt[i];
t1 = ((C_SparseNumFact_arg *)(*(*it)->queue)[j]->func_arg)->tt[i + 1];
fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
task_name.c_str(),
// (*(*it)->queue)[j]->task_name,
(*(*it)->queue)[j]->thread_id,
convert_sec(t0),
convert_microsec(t0),
convert_sec(t1),
convert_microsec(t1), 0L);
}
}
else {
fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
(*(*it)->queue)[j]->task_name,
(*(*it)->queue)[j]->thread_id,
convert_sec((*(*it)->queue)[j]->t0),
convert_microsec((*(*it)->queue)[j]->t0),
convert_sec((*(*it)->queue)[j]->t1),
convert_microsec((*(*it)->queue)[j]->t1),
*((*(*it)->queue)[j]->ops_complexity));
}
//*((C_SparseNumFact_arg *)(*(*it)->queue)[j]->func_arg)->nops :
}
(*it)->status = TASK_DONE;
}
}
fprintf(fp, "*** dynamic : %d ***", (int)_queue_dynamic->size());
for (vector::const_iterator it = _queue_dynamic->begin();
it != _queue_dynamic->end(); ++it) {
fprintf(fp, "** C_task_seq = %s : [%d, %d] %d **\n",
(*it)->task_name,
(*it)->begin, (*it)->end,(*it)->pos);
if ((*it)->status == TASK_DONE) {
continue;
}
for (int j = (*it)->begin; j < (*it)->end; j++) {
fprintf(fp, "%s\t%d\t%d\t%d\t%d\t%d\t%ld\n",
(*(*it)->queue)[j]->task_name,
(*(*it)->queue)[j]->thread_id,
convert_sec((*(*it)->queue)[j]->t0),
convert_microsec((*(*it)->queue)[j]->t0),
convert_sec((*(*it)->queue)[j]->t1),
convert_microsec((*(*it)->queue)[j]->t1),
*((*(*it)->queue)[j]->ops_complexity));
}
(*it)->status = TASK_DONE;
}
fprintf(fp, "**** numeric factorization end ****\n");
fclose(fp);
}
} // if fopen()
#endif // DEBUG_THREAD_TIME
#ifdef DEBUG_PRINT_TASK
for (int p = 0; p < num_threads; p++) {
fclose(_fps[p]);
}
delete [] _fps;
#endif
threads.clear();
}
void *thread_queue_symb_factorize_(void *arg)
{
THREAD_QUEUE_EXEC *params = (THREAD_QUEUE_EXEC *)arg;
params->dissectionRuntime->thread_queue_symb_factorize(params->id,
params->num_threads);
#ifdef POSIX_THREADS
pthread_exit(arg);
#endif
return (void *)NULL;
}
void QueueRuntime::thread_queue_symb_factorize(const int pid,
const int num_threads)
{
// const int pid = params->id;
// const int num_threads = params->num_threads;
// greedy -- better to be in seperated function
int pos, end;
C_task_seq* it = _queue_symb;
while(1) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
pos = it->pos;
end = it->end;
if (pos < end) {
it->pos++;
}
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
if (pos >= end) {
break;
}
C_task *task = (*it->queue)[pos];
task->status = TASK_WORKING;
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t0));
// clock_gettime(CLOCK_MONOTONIC, &(task->t0));
#endif
task->func(task->func_arg);
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t1));
// clock_gettime(CLOCK_MONOTONIC, &(task->t1));
task->thread_id = pid;
#endif
// accuessing to unsigned char does not neet mutex
task->status = TASK_DONE;
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( " << pid << " " << pos << " ) " ;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // while (1)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << it->task_name
<< " @ " << it->task_id << " greedy end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
void *thread_queue_num_factorize_(void *arg)
{
THREAD_QUEUE_EXEC *params = (THREAD_QUEUE_EXEC *)arg;
params->dissectionRuntime->thread_queue_num_factorize(params->id,
params->num_threads);
#ifdef POSIX_THREADS
pthread_exit(arg);
#endif
return (void *)NULL;
}
void QueueRuntime::thread_queue_num_factorize(const int pid,
const int num_threads)
{
int *permute_block = new int[SIZE_B1];
list::const_iterator it = _queue_static[pid].begin();
int zone, zone_idxn, zone_idxp;
bool zone_flag;
int zone_first_entered = 0;
int zone_last_entered = 0;
int zone_first_finished = 0;
int zone_last_finished = 0;
int cnt_cdfull = 0;
//
zone = 0;
while(it != _queue_static[pid].end()) {
#ifdef DEBUG_THREAD_LOOP
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " : " << (*it)->task_name
<< " _phase_dynamic = " << _phase_dynamic << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
//
zone_idxp = (zone + DIST_TASK_CRITICAL - 1) % DIST_TASK_CRITICAL;
zone_idxn = zone % DIST_TASK_CRITICAL;
zone_first_entered = 0;
zone_last_entered = 0;
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
if (_zone_entered[zone_idxn] == 0) {
zone_first_entered = 1;
_zone_static_assigned[zone_idxn] = 0;
}
_zone_entered[zone_idxn]++;
zone_flag = (_zone_entered[zone_idxn] == num_threads);
if (zone_flag) {
// clear cyclic buffer
_zone_entered[zone_idxp] = 0;
_zone_static_assigned[zone_idxp] = 0; // only for safety
zone_last_entered = 1;
}
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
zone++;
//
if ((*it)->parallel_single == TASK_PARALLEL) {
switch((*it)->task_id) {
case C_DFULL :
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " C_DFULL "
<< (*it)->task_name << " : " << (*it)->task_id
<< " @ " << zone << " : " << zone_flag << " : "
<< " zone ( " << zone_first_entered << " : "
<< zone_last_entered << " )"
<< " : " << (*it)->pos << " " << (*it)->end << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
thread_queue_C_DFULL(pid, num_threads, *it,
permute_block,
cnt_cdfull,
zone_first_entered,
zone_idxn);
#ifdef DEBUG_THREAD_LOOP
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " C_DFULL "
<< (*it)->task_name << " end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
case C_SPARSELOCALSCHUR:
case C_DTRSM:
case C_DGEMM:
case C_DSUB:
case C_FILLMATRIX:
case C_DEALLOCATE:
case C_SPARSESOLVER:
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " remaining diagonal "
<< (*it)->task_name << " : " << (*it)->task_id
<< " @ " << zone << " : " << zone_flag << " : "
<< " zone ( " << zone_first_entered << " : "
<< zone_last_entered << " )"
<< " : " << (*it)->pos << " " << (*it)->end << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
thread_queue_parallel_dynamic(pid, num_threads, *it,
permute_block,
zone_idxn);
#ifdef DEBUG_THREAD_LOOP
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " remaining diagonal "
<< (*it)->task_name << " end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
case C_SPARSELOCALSCHUR1:
case C_DTRSM1:
case C_DGEMM1:
case C_DSUB1:
case C_FILLMATRIX1:
case C_DEALLOCATE1:
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " remaining off-diagonal "
<< (*it)->task_name << " : " << (*it)->task_id
<< " @ " << zone << " : " << zone_flag << " : "
<< " zone ( " << zone_first_entered << " : "
<< zone_last_entered << " )"
<< " : " << (*it)->pos << " " << (*it)->end << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
thread_queue_parallel_static(pid, num_threads, *it,
permute_block,
zone_idxp,
zone_idxn,
zone_first_entered,
zone_last_entered);
#ifdef DEBUG_THREADS_LOOP
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " remaining off-diagonal "
<< (*it)->task_name << " end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
}
}
else { // if ((*it)->parallel_single == TASK_SINGLE)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " single "
<< (*it)->task_name << " : " << (*it)->task_id
<< " @ " << zone << " : " << zone_flag << " : "
<< " zone ( " << zone_first_entered << " : "
<< zone_last_entered << " )"
<< " : " << (*it)->pos << " " << (*it)->end << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
thread_queue_single(pid, num_threads, *it,
permute_block,
zone_idxn);
#ifdef DEBUG_THREAD_LOOP
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " single "
<< (*it)->task_name << " end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // if ((*it)->parallel_single == TASK_SINGLE)
int clear_flag = 0;
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
if (_zone_finished[zone_idxn] == 0) {
zone_first_finished = 1;
}
_zone_finished[zone_idxn]++;
if (_zone_finished[zone_idxn] == num_threads) {
zone_last_finished = 1;
// clear status of cyclic buffer
_zone_finished[zone_idxp] = 0;
// the last task
(*it)->status = TASK_DONE;
if((*it)->task_id == C_DFULL) {
clear_flag = 1;
}
#ifdef DEBUG_THREAD_LOOP
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " "
<< (*it)->task_name << " end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
// without mutex
if((*it)->task_id == C_DFULL) {
cnt_cdfull = (cnt_cdfull + 1) % DIST_TASK_CRITICAL;
if (clear_flag) {
const int cnt_cdfull_p =
((cnt_cdfull + DIST_TASK_CRITICAL - 1) % DIST_TASK_CRITICAL);
for (int p = 0; p < num_threads; p++) {
for (int i = 0; i < DIST_TASK_CRITICAL; i++) {
_group_entered[p][cnt_cdfull_p][i] = 0;
_group_finished[p][cnt_cdfull_p][i] = 0;
_group_task_ends[p][cnt_cdfull_p][i] = (-1);
}
}
}
} // if((*it)->task_id == C_DFULL) {
++it;
} // while (it != _queue_static[pid].end()) {
delete [] permute_block;
}
void QueueRuntime::thread_queue_C_DFULL(const int pid,
const int num_threads,
C_task_seq *it,
int *permute_block,
const int cnt_cdfull,
const int zone_first_entered,
const int zone_idxn)
{
const int pid_g = it->mutex_id;
int group = 0;
int group_first_entered = 0, group_last_entered = 0;
int group_first_finished = 0;
int pos;
int pid0;
int *_grp_entered = _group_entered[pid_g][cnt_cdfull];
int *_grp_finished = _group_finished[pid_g][cnt_cdfull];
int *_grp_task_ends = _group_task_ends[pid_g][cnt_cdfull];
int *_grp_static_assigned = _group_static_assigned[pid_g][cnt_cdfull];
bool zone_flag;
// get status other threads entered the same zone
{
// std::unique_locklck_root(_mutex_root);
MUTEX_LOCK(_mutex_root, lck_root);
zone_flag = (_zone_entered[zone_idxn] == num_threads);
MUTEX_UNLOCK(_mutex_root);
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " cnt_cdfull = " << cnt_cdfull << " parallel : c_dfull "
<< it->task_name << " pos = " << it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
if (_grp_entered[0] == 0) {
// reset flags to keep status of entered/finshed tasks
for (int i = 1; i < DIST_TASK_CRITICAL; i++) {
_grp_entered[i] = 0;
_grp_finished[i] = 0;
}
for (int i = 0; i < it->num_threads; i++) {
_group_nops[pid_g][i] = 0L;
}
group_first_entered = 1;
_grp_static_assigned[0] = 0; // 12 Feb.2013 Atsusti : for safety?
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " : " << it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
// pid0 is decided by arrived order
pid0 = _grp_entered[0]++;
if (_grp_entered[0] == it->num_threads) {
group_last_entered = 1;
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
//
while (1) { // global loop of task queue
//
const int gidxp = (group + DIST_TASK_CRITICAL - 1) % DIST_TASK_CRITICAL;
const int gidxn = group % DIST_TASK_CRITICAL;
int finish_group = 0;
int skip_flag = 0;
if (group > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
_begins_group[pid_g][pid0][gidxn] = (-1);
_ends_group[pid_g][pid0][gidxn] = (-1);
group_first_entered = 0;
group_last_entered = 0;
if (_grp_entered[gidxn] == 0) {
group_first_entered = 1;
// assuming other jobs are assiged by static
for (int i = 0; i < it->num_threads; i++) {
_group_nops[pid_g][i] = 0L;
}
#if 1
pos = it->pos;
int jtmp = pos;
for (int i = (*it->queue)[pos]->parallel_id;
i < (*it->queue)[pos]->parallel_max; i++) {
jtmp += (*it->queue)[jtmp]->atomic_size;
}
_grp_task_ends[gidxn] = jtmp;
_grp_task_ends[gidxp] = (-1);
_grp_static_assigned[gidxn] = 0;
#else
_group_task_ends[pid_g][cnt_cdfull][gidxn] = (-1);
#endif
} // if (_grp_entered[gidxn] == 0)
_grp_entered[gidxn]++;
if (_grp_entered[gidxn] == it->num_threads) {
// clear status of cyclic buffer
_grp_entered[gidxp] = 0;
group_last_entered = 1;
}
if ((_grp_finished[gidxn] > 0) && (group_first_finished == 0)) {
_grp_finished[gidxn]++;
if (_grp_finished[gidxn] == it->num_threads) {
// clear status of cyclic buffer
_grp_finished[gidxp] = 0;
_group_task_ends[pid_g][cnt_cdfull][gidxp] = (-1);
}
skip_flag = 1;
} // if ((_grp_finished[gidxn] > 0) && (group_first_finished == 0))
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
} // if (group > 0)
else {
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
if ((_grp_finished[gidxn] > 0) &&
(group_first_finished == 0)) {
_grp_finished[gidxn]++;
if (_grp_finished[gidxn] == it->num_threads) {
// clear status of cyclic buffer
_grp_finished[gidxp] = 0;
_group_task_ends[pid_g][cnt_cdfull][gidxp] = (-1);
}
skip_flag = 1;
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope mutex
} // if (group > 0)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pid_g = " << pid_g << " pid0 " << pid0
<< " group " << group << " entered "
<< group_first_entered << " / " << group_last_entered
<< " (" << _grp_entered[gidxp] << "@" << gidxp
<< ") / (" << _grp_entered[gidxn] << "@" << gidxn
<< ") finished "
<< " (" << _grp_finished[gidxp] << "@" << gidxp
<< ") / ( " << _grp_finished[gidxn] << "@" << gidxn
<< ") " << it->pos << " : " << it->end
<< " skip_flag = " << skip_flag;
if (skip_flag) {
cerr << " task is already finished : my job is skipped";
}
cerr << " zone_flag = " << zone_flag
<< " zone_idxn = " << zone_idxn
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
group++;
//
if (skip_flag) {
continue;
}
#if 1
// wait until other threads enter the same zone
while (!zone_flag) {
// looking for dynamic queue
int flag = 1;
while ((flag == 1) && (!zone_flag)) {
flag = execute_task_dynamic_buffer(permute_block,
pid,
_mutex_dependency);
{ // scope of mutex
// std::unique_locklck_root(_mutex_root);
MUTEX_LOCK(_mutex_root, lck_root);
zone_flag = (_zone_entered[zone_idxn] == num_threads);
MUTEX_UNLOCK(_mutex_root);
}
} // while ((flag == 1) && (!zone_flag))
if (zone_flag) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pid_g = " << pid_g << " pid0 " << pid0
<< " zone_idxn = " << zone_idxn
<< " zone_flag = " << zone_flag
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
}
// get tasks with atomic_size from the queue : *it
int itmp, jtmp;
int exit_flag = 0;
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
// do not increase queue more than its size
if (pos == it->end) {
exit_flag = 1;
}
else {
// there might be segments with more than 1 automic size
// between parallel_id and parallel_max
itmp = pos + (*it->queue)[pos]->atomic_size;
jtmp = (itmp - 1 + ((*it->queue)[pos]->parallel_max -
(*it->queue)[pos]->parallel_id));
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " +atomic_size = " << itmp
<< " parallel_max " << jtmp << " : " << it->end
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (itmp <= jtmp) {
it->pos = itmp;
}
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
if (exit_flag) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos << "it->end = " << it->end
<< " : " << it->task_name << " already finished.." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
if (itmp == jtmp) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " jtmp = " << jtmp << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
finish_group = 1;
}
// reserve tasks and conunt estimated job size
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
_group_nops[pid_g][pid0] +=
*((*it->queue)[pos + i]->ops_complexity);
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope mutex
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
if ((*it->queue)[pos]->atomic_size > 1) {
C_task *kt = (*it->queue)[pos];
cerr << pid << " b-c-a " << pos << " : "
<< kt->task_name << " : "
<< kt->parents_work->size() << " / ";
for (list::const_iterator mt = kt->parents_work->begin();
mt != kt->parents_work->end(); ++mt) {
cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
}
cerr << "before statically assigned task : with status check."
<< endl;
}
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
C_task *kt = (*it->queue)[pos + i];
int waiting1 = check_parents_done(kt, _mutex_dependency);
while(waiting1 > 0) {
//
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
_waiting_root++;
#ifdef DEBUG_DEADLOCK
if (_waiting_root > num_threads) {
fprintf(stderr, "dead lock occured : %s %d\n",
__FILE__, __LINE__);
exit(-1);
}
#endif
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << kt->task_name << " "
<< "waiting = "<< waiting1 << " : "
<< (int)_waiting_root << " "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = kt->parents_work->begin();
jt != kt->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
}
#endif
COND_WAIT(_mutex_root, _cond_root, lck_root); //
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << "\t" << pid
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
}
#endif
_waiting_root--;
// other thread broacast wake up and decreasing _waiting_root
waiting1 = check_parents_done(kt, _mutex_dependency);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
//#endif
} // while (waiting > 0)
if (waiting1 == (-1)) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos << " : "
<< (*it->queue)[pos + i]->task_name
<< " : " << it->task_name << " quitted..." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
execute_task(it, (pos + i),
permute_block,
pid, _mutex_dependency);
if ((*it->queue)[pos + i]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " atomic_size= "
<< (*it->queue)[pos]->atomic_size
<< " : " << it->task_name << " finished..."
<< "skip " << (*it->queue)[pos + i]->to_next_task
<< " : " << __FILE__ << " : " << __LINE__
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
pos += (*it->queue)[pos + i]->to_next_task;
return;
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "{ "
<< (*it->queue)[pos + i]->task_name << " @ "
<< pid << " " << (pos + i) << " }";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // loop : i
// static tasks are assigned by other thread
if (finish_group) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " C_FULL : the first greedy end the queue."
<< it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
for (int p = 0; p < it->num_threads; p++) {
_begins_group[pid_g][p][gidxn] = pos;
_ends_group[pid_g][p][gidxn] = pos;
}
_grp_static_assigned[gidxn] = 1;
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
continue;
}
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
zone_flag = (_zone_entered[zone_idxn] == num_threads);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
} // while (zone_flag)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pid_g = " << pid_g << " pid0 " << pid0
<< " group " << (group - 1) // after increment of group
<< " zone_flag = " << zone_flag
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
#endif
if (group_last_entered) {
//
long nops, nops_total, nops_static, nops_per_thread;
nops = 0L;
nops_total = 0L;
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
if (pos == it->end) {
break;
}
const int queue_size = ((*it->queue)[pos]->parallel_max -
(*it->queue)[pos]->parallel_id);
if (queue_size < it->num_threads) {
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
for (int p = 0; p < it->num_threads; p++) {
_begins_group[pid_g][p][gidxn] = pos;
_ends_group[pid_g][p][gidxn] = pos;
}
_grp_static_assigned[gidxn] = 1;
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
}
else {
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
int jj = pos;
for (int i = (*it->queue)[pos]->parallel_id;
i < (*it->queue)[pos]->parallel_max; i++) {
// atomic_size
const int itmp = jj;
for (int j = 0; j < (*it->queue)[itmp]->atomic_size;
j++, jj++) {
nops_total += *((*it->queue)[jj]->ops_complexity);
}
}
nops_static = (long)((double)nops_total * RATIO_QUEUE_GREEDY);
nops_per_thread = (nops_static / (long)it->num_threads);
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pos << " " << _grp_task_ends[gidxn] << " "
<< nops_total << " " << nops_per_thread << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
long ntmp = 0L;
for (int p = 0; p < it->num_threads; p++) {
if (ntmp < _group_nops[pid_g][p]) {
ntmp = _group_nops[pid_g][p];
}
}
if (ntmp >= nops_per_thread) { // greedy
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pos << " max _group_nops[pid_g][] = " << ntmp
<< " nops_per_threads = " << nops_per_thread << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int p = 0; p < it->num_threads; p++) {
_begins_group[pid_g][p][gidxn] = pos;
_ends_group[pid_g][p][gidxn] = pos;
}
// _group_task_ends[pid_g][cnt_cdfull][gidxn] = end_queue;
}
else { // if (ntmp < nops_per_thread)
_begins_group[pid_g][0][gidxn] = pos;
// for fail-safe
//_ends_group[pid_g][it->num_threads - 1][gidxn] = end_queue;
_ends_group[pid_g][it->num_threads - 1][gidxn] =
_grp_task_ends[gidxn];
nops = 0L;
int p = 0;
for (int j = pos; j < _grp_task_ends[gidxn]; ) {
for (int k = 0; k < (*it->queue)[j]->atomic_size;
k++) {
nops += *((*it->queue)[j + k]-> ops_complexity);
}
j += (*it->queue)[j]->atomic_size;
// do not devide atomic operation
if (nops > nops_per_thread) {
_ends_group[pid_g][p][gidxn] = j;
p++;
if (p == it->num_threads) {
break;
}
_begins_group[pid_g][p][gidxn] = j;
nops = 0L;
} // if
} // loop : j
if (p < it->num_threads) {
// static assignment is failed.
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << "pid_g = " << pid_g << " gidxn = " << gidxn
<< " : pos = " << pos << " static assignment is failed"
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int j = 0; j < it->num_threads; j++) {
_begins_group[pid_g][j][gidxn] = pos;
_ends_group[pid_g][j][gidxn] = pos;
}
}
it->pos = _ends_group[pid_g][it->num_threads - 1][gidxn];
// cerr << pid << " pos = " << it->pos << endl;
// _group_task_ends[pid_g][cnt_cdfull][gidxn] = end_queue;
} // if (ntmp < nops_per_thread)
_grp_static_assigned[gidxn] = 1;
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
} // if (queue_size < it->num_threads)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " : ";
for (int p = 0; p < it->num_threads; p++) {
cerr << "[ " << _begins_group[pid_g][p][gidxn]
<< " : " << _ends_group[pid_g][p][gidxn] << " ] ";
}
cerr << _grp_task_ends[gidxn] << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // if (group_last_entered)
else {
int group_task_end, group_static_assigned;
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
group_task_end = _grp_task_ends[gidxn];
group_static_assigned = _grp_static_assigned[gidxn];
pos = it->pos;
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " gidxn = " << gidxn
<< " group_task_end " << group_task_end
<< " group_static_assigned " << group_static_assigned
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (pos == it->end && (group_static_assigned == 0)) {
// not yet static assigned but queue is exhausted
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos << "it->end = " << it->end
<< " : " << it->task_name << " finished." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
// include group_static_assigned == (-1) : 21 Jun.2012, Atsushi
while (group_static_assigned != 1) { // greedy
int exit_flag = 0;
// to skip un-necessary access to _dynamic_queue
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
if (pos == it->end) {
exit_flag = 1;
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
if (exit_flag) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos << "it->end = " << it->end
<< " : " << it->task_name << " already finished." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
// looking for dynamic queue
int flag = 1;
// include group_static_assigned == (-1) : 21 Jun.2012, Atsushi
while ((flag == 1) && (group_static_assigned != 1)) {
flag = execute_task_dynamic_buffer(permute_block,
pid,
_mutex_dependency);
{ // scope of mutex
// std::unique_locklck_root(_mutex_group[pid_g]);
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
group_static_assigned = _grp_static_assigned[gidxn];
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
} // while ((flag == 1) && (group_static_assigned != 0))
if (group_static_assigned) {
break;
}
// get tasks with atomic_size from the queue : *it
int itmp, jtmp;
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
// do not increase queue more than its size
if (pos == it->end) {
exit_flag = 1;
}
else {
// there might be segments with more than 1 automic size
// between parallel_id and parallel_max
itmp = pos + (*it->queue)[pos]->atomic_size;
jtmp = (itmp - 1 + ((*it->queue)[pos]->parallel_max -
(*it->queue)[pos]->parallel_id));
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " +atomic_size = " << itmp
<< " parallel_max " << jtmp << " : " << it->end
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (itmp <= jtmp) {
it->pos = itmp;
}
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
if (exit_flag) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos << "it->end = " << it->end
<< " : " << it->task_name << " already finished.." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
if (itmp == jtmp) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " jtmp = " << jtmp << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
finish_group = 1;
}
// reserve tasks and conunt estimated job size
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
_group_nops[pid_g][pid0] +=
*((*it->queue)[pos + i]->ops_complexity);
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
if ((*it->queue)[pos]->atomic_size > 1) {
C_task *kt = (*it->queue)[pos];
cerr << pid << " b-c-a " << pos << " : "
<< kt->task_name << " : "
<< kt->parents_work->size() << " / ";
for (list::const_iterator mt = kt->parents_work->begin();
mt != kt->parents_work->end(); ++mt) {
cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
}
cerr << "before statically assigned task : with status check."
<< endl;
}
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
C_task *kt = (*it->queue)[pos + i];
int waiting = check_parents_done(kt, _mutex_dependency);
while(waiting > 0) {
//
{ // scope of mutex
// std::unique_locklck_root(_mutex_root);
MUTEX_LOCK(_mutex_root, lck_root);
_waiting_root++;
#ifdef DEBUG_DEADLOCK
if (_waiting_root > num_threads) {
fprintf(stderr, "dead lock occured : %s %d\n",
__FILE__, __LINE__);
exit(-1);
}
#endif
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << kt->task_name << " "
<< "waiting = "<< waiting << " : "
<< (int)_waiting_root << " "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = kt->parents_work->begin();
jt != kt->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
}
#endif
COND_WAIT(_mutex_root, _cond_root, lck_root); //
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << "\t" << pid
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
}
#endif
_waiting_root--;
// other thread broacast wake up and decreasing _waiting_root
waiting = check_parents_done(kt, _mutex_dependency);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
} // while (waiting > 0)
if (waiting == (-1)) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos + i << " : "
<< (*it->queue)[pos + i]->task_name
<< " : " << it->task_name << " quitted..." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
execute_task(it, (pos + i),
permute_block,
pid, _mutex_dependency);
if ((*it->queue)[pos + i]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " atomic_size= "
<< (*it->queue)[pos]->atomic_size
<< " : " << it->task_name << " finished..."
<< "skip " << (*it->queue)[pos + i]->to_next_task
<< " : " << __FILE__ << " : " << __LINE__
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
pos += (*it->queue)[pos + i]->to_next_task;
return;
// break;
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "{ "
<< (*it->queue)[pos + i]->task_name << " @ "
<< pid << " " << (pos + i) << " }";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // loop : i
// static tasks are assigned by other thread
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
group_static_assigned = _grp_static_assigned[gidxn];
if ((finish_group == 1) && (group_static_assigned == 0)) {
// static task is not assigned but queue becomes empty
for (int p = 0; p < it->num_threads; p++) {
_begins_group[pid_g][p][gidxn] = (-1);
_ends_group[pid_g][p][gidxn] = (-1);
}
_grp_task_ends[gidxn] = jtmp;
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
if (finish_group) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " C_FULL : the first greedy end the queue."
<< it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
for (int p = 0; p < it->num_threads; p++) {
_begins_group[pid_g][p][gidxn] = pos;
_ends_group[pid_g][p][gidxn] = pos;
}
_grp_static_assigned[gidxn] = 1;
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
continue;
}
// just for debugging : group_task_end >=0 <=> braek while ( < 0 )
#ifdef DEBUG_EXEC_THREAD
if (group_static_assigned) {
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " end the first greedy "
<< it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
}
#endif
} // while (group_static_assigned != 1)
} // if (group_last_entered)
// static assignment
int _begin_grp, _end_grp;
if ( _grp_static_assigned[gidxn] == (-1)) {
// this never happen?
_begin_grp = _end_grp = (-1);
#ifdef DEBUG_EXEC_THREAD_21Jun2012
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << ": pid0 = " << pid0 << " gidxn = " << gidxn
<< " static assignment is not yet done! "
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
else {
_begin_grp = _begins_group[pid_g][pid0][gidxn];
_end_grp = _ends_group[pid_g][pid0][gidxn];
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << ": pid0 = " << pid0 << " gidxn = " << gidxn
<< " < " << _begin_grp << " " << _end_grp << " > assigned"
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int i = _begin_grp; i < _end_grp; i++) {
// no need to check dependency for static assignement
execute_task(it, i, permute_block,
pid);
if ((*it->queue)[i]->quit_queue) {
fprintf(stderr, "%d i = %d : %s finished ... skip %d\n",
pid, i, it->task_name,
(*it->queue)[i]->to_next_task);
i += (*it->queue)[i]->to_next_task;
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( "
<< (*it->queue)[i]->task_name << " @ "
<< pid << " " << i << " )";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // loop : i
// greedy
while(1) {
int group_task_end;
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
pos = it->pos;
group_task_end = _grp_task_ends[gidxn];
if (pos < group_task_end) {
const int itmp = (it->pos +
(*it->queue)[pos]->atomic_size);
if (itmp <= group_task_end) {
it->pos = itmp;
}
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
if (pos >= group_task_end) {
break;
}
if (_begin_grp < _end_grp) {
// <==> statically assigned block is computed
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
if ((*it->queue)[pos]->atomic_size > 1) {
C_task *kt = (*it->queue)[pos];
cerr << pid << " b-c-a " << pos << " : " << kt->task_name << " : "
<< kt->parents_work->size() << " / ";
for (list::const_iterator mt = kt->parents_work->begin();
mt != kt->parents_work->end(); ++mt) {
cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
}
cerr << "within statically assigned task : without status check."
<< endl;
}
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
execute_task(it, (pos + i), permute_block,
pid,
_mutex_group[pid_g]);
if ((*it->queue)[pos + i]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " atomic_size= "
<< (*it->queue)[pos]->atomic_size
<< " : " << it->task_name << " finished..."
<< "skip " << (*it->queue)[pos + i]->to_next_task
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// const int ibegin = pos + i + 1;
pos += (*it->queue)[pos + i]->to_next_task;
return;
// break;
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( "
<< (*it->queue)[pos + i]->task_name << " @ "
<< pid << " " << (pos + i) << " )";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // loop : i
} // if (_begins_grp == _ends_grp)
else {
// <==> no statically assigned block
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
if ((*it->queue)[pos]->atomic_size > 1) {
C_task *kt = (*it->queue)[pos];
cerr << pid << " b-c-a " << pos << " : " << kt->task_name << " : "
<< kt->parents_work->size() << " / ";
for (list::const_iterator mt = kt->parents_work->begin();
mt != kt->parents_work->end(); ++mt) {
cerr << (int)(*mt)->status << "@" << (*mt)->task_name << " / ";
}
cerr << "no statically assigned task : with status check." << endl;
}
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int i = 0; i < (*it->queue)[pos]->atomic_size; i++) {
C_task *kt = (*it->queue)[pos + i];
int waiting = check_parents_done(kt, _mutex_dependency);
while(waiting > 0) {
{ // scope of mutex
// std::unique_locklck_root(_mutex_root);
MUTEX_LOCK(_mutex_root, lck_root);
_waiting_root++;
#ifdef DEBUG_DEADLOCK
if (_waiting_root > num_threads) {
fprintf(stderr, "dead lock occured : %s %d\n",
__FILE__, __LINE__);
exit(-1);
}
#endif
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << kt->task_name << " "
<< "waiting = " << waiting
<< " : " << (int)_waiting_root << " : "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = kt->parents_work->begin();
jt != kt->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
}
#endif
COND_WAIT(_mutex_root, _cond_root, lck_root); //
_waiting_root--;
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << endl
<< pid << " " << kt->task_name << " "
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
}
#endif
waiting = check_parents_done(kt, _mutex_dependency);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
} // while (waiting > 0)
if (waiting == (-1)) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos + i << " : "
<< (*it->queue)[pos + i]->task_name
<< " : " << it->task_name << " quitted..." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
} // if (wating == (-1))
execute_task(it, (pos + i), permute_block,
pid,
_mutex_group[pid_g]);
if ((*it->queue)[pos + i]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " i = " << i
<< " : " << it->task_name << " finished... skip "
<< (*it->queue)[pos + i]->to_next_task << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// const int ibegin = pos + i + 1;
i += (*it->queue)[pos + i]->to_next_task;
return;
} // if (quit_queue)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( "
<< (*it->queue)[pos + i]->task_name << " @ "
<< pid << " " << (pos + i) << " )";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // loop : i
} // // if (_begin_grp <_end_grp)
} // while (1)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " finish " << group
<< " pos = " << it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (pos >= it->end) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pod = " << pos << "it->end = " << it->end
<< " : " << it->task_name << " finished..." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
return;
}
{ // scope of mutex
MUTEX_LOCK(_mutex_group[pid_g], lck_root);
group_first_finished = 0;
if (_grp_finished[gidxn] == 0) {
group_first_finished = 1;
}
_grp_finished[gidxn]++;
if (_grp_finished[gidxn] == it->num_threads) {
// clear status of cyclic buffer
_grp_finished[gidxp] = 0;
}
MUTEX_UNLOCK(_mutex_group[pid_g]);
} // scope of mutex
} // while (1)
}
void QueueRuntime::thread_queue_parallel_dynamic(const int pid,
const int num_threads,
C_task_seq *it,
int *permute_block,
const int zone_idxn)
{
// completely greedy
int pos, end, atomic_size, atomic_id, update_flag;
while(1) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
pos = it->pos;
end = it->end;
if (pos < end) {
atomic_size = (*it->queue)[pos]->atomic_size;
atomic_id = (*it->queue)[pos]->atomic_id;
it->pos += atomic_size; // it->pos++;
if (it->pos >= end) {
update_flag = 1;
}
}
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
if (pos >= end) {
break;
}
C_task *kt = (*it->queue)[pos]; // [pos + atomic_size - 1];
int waiting = check_parents_done(kt, _mutex_dependency);
while (waiting > 0) {
// looking for dynamic queue
int flag = execute_task_dynamic_buffer(permute_block,
pid,
_mutex_dependency);
if (flag != 1) {
while(waiting > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
_waiting_root++;
#ifdef DEBUG_DEADLOCK
if (_waiting_root > num_threads) {
fprintf(stderr, "dead lock occured : %s %d\n",
__FILE__, __LINE__);
exit(-1);
}
#endif
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << kt->task_name << " "
<< "waiting = "<< waiting << " : "
<< (int)_waiting_root << " : "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = kt->parents_work->begin();
jt != kt->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
}
#endif
COND_WAIT(_mutex_root, _cond_root, lck_root); //
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << endl
<< pid << " " << kt->task_name << " "
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
}
#endif
_waiting_root--;
// other thread broacast wake up and decreasing _waiting_root
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
waiting = check_parents_done(kt, _mutex_dependency);
} // while (waiting > 0)
} // if (flag != 1)
waiting = check_parents_done(kt, _mutex_dependency);
} // while (waiting > 0)
for (int m = 0; m < atomic_size; m++) {
execute_task(it, (pos + m), permute_block, // loop with atomic_size
pid,
_mutex_dependency);
}
if ((*it->queue)[pos]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos
<< " : " << it->task_name << " finished..."
<< "skip " << (*it->queue)[pos]->to_next_task
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// const int ibegin = pos + 1;
pos += (*it->queue)[pos]->to_next_task;
} // if (quit_queue)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( " << pid << " " << pos << " ) " ;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
} // while (1)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << it->task_name
<< " @ " << it->task_id << " greedy end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
void QueueRuntime::thread_queue_parallel_static(const int pid,
const int num_threads,
C_task_seq* it,
int *permute_block,
const int zone_idxp,
const int zone_idxn,
const int zone_first_entered,
const int zone_last_entered)
{
// the last thread which turns into the zone assigns jobs statiscally
int pos, end, atomic_size, atomic_id;
int finished_status = 0;
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
pos = it->pos;
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
// reach the end before all threads entered
if (pos == it->end) {
return;
}
if (zone_last_entered) {
long nops, nops_total, nops_static, nops_per_thread;
int begin, end;
// this mutex is relatively larage
// : lock out other threads until assingnment is finished
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
begin = it->pos;
end = it->end;
if ((end - begin) < num_threads) {
// execute tasks by greedy way
for (int q = 0; q < num_threads; q++) {
_begins[q][zone_idxn] = _ends[q][zone_idxn] = pos;
}
_zone_static_assigned[zone_idxn] = 1;
}
else {
// nops_total = it->ops_complexity;
nops_total = 0L;
for (int j = begin; j < end; j++) {
nops_total += *((*it->queue)[j]->ops_complexity);
// 28 May 2012 : Atsushi
// cerr << (*it->queue)[j]->task_name
// << *((*it->queue)[j]->ops_complexity) << " ";
}
//cerr << endl;
nops_static = (long)((double)nops_total * RATIO_QUEUE_GREEDY);
nops_per_thread = nops_static / (long)num_threads;
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " begin = " << begin << " end = "
<< end << " "
<< nops_total << " " << nops_static << " "
<< nops_per_thread << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
_begins[0][zone_idxn] = begin;
_ends[num_threads - 1][zone_idxn] = end;
nops = 0L;
int p = 0;
for (int j = begin; j < end; j++) {
nops += *((*it->queue)[j]->ops_complexity);
if (nops > nops_per_thread) {
// && ((*it->queue)[j]->atomic_size == // 13 May 2014
// ((*it->queue)[j]->atomic_id + 1))) {
const int jj = j - (*it->queue)[j]->atomic_id;
_ends[p][zone_idxn] = jj;
p++;
if (p == num_threads) {
break;
}
_begins[p][zone_idxn] = jj;
nops = 0L;
}
} // loop : j
if (p < num_threads) { // equally assignment is failed
// execute tasks by greedy way
for (int q = 0; q < num_threads; q++) {
_begins[q][zone_idxn] = _ends[q][zone_idxn] = pos;
}
}
else {
it->pos = _ends[num_threads - 1][zone_idxn];
}
_zone_static_assigned[zone_idxn] = 1;
}
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
for (int p = 0; p < num_threads; p++) {
cerr << "[ " << _begins[p][zone_idxn]
<< " : " << _ends[p][zone_idxn] << " ] ";
}
cerr << it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
//
} // if (zone_last_entered)
else { // if (zone_last_entered)
int zone_static_assigned = 0;
while(zone_static_assigned == 0) {
// similar to the routine : execute_task_dynamic_buffer()
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
zone_static_assigned = _zone_static_assigned[zone_idxn];
if (zone_static_assigned == 0) {
pos = it->pos;
end = it->end;
if (pos < end) {
atomic_size = (*it->queue)[pos]->atomic_size;
atomic_id = (*it->queue)[pos]->atomic_id;
it->pos += atomic_size; // pos++;
if (it->pos >= end) {
finished_status = 1;
//
_phase_dynamic++;
if (_phase_dynamic == _queue_dynamic->size()) {
_phase_dynamic = (-1);
}
// queue is exhaused by this step and enforcing other tasks to quit
for (int p = 0; p < num_threads; p++) {
_begins[p][zone_idxn] = _ends[p][zone_idxn] = end;
}
} // if (it->pos == end) {
}
} // if (zone_static_assigned == 0)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " pos = " << pos << " zone_idxn = " << zone_idxn
<< " zone_static_assigned " << zone_static_assigned << " : "
<< _zone_static_assigned[zone_idxn]
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
if (zone_static_assigned == 1) {
break;
}
if (pos >= end) {
// skip my task
_begins[pid][zone_idxn] = _ends[pid][zone_idxn] = end;
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " queue is already exhausted "
<< it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
}
C_task *kt = (*it->queue)[pos]; // [pos + atomic_size - 1];
int waiting = check_parents_done(kt, _mutex_dependency);
if (waiting > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
while (waiting > 0) { // real sleeping
_waiting_root++;
#ifdef DEBUG_DEADLOCK
if (_waiting_root > num_threads) {
fprintf(stderr, "dead lock occured : %s %d\n",
__FILE__, __LINE__);
exit(-1);
}
#endif
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << kt->task_name << " "
<< "waiting = "<< waiting << " : "
<< (int)_waiting_root << " : "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = kt->parents_work->begin();
jt != kt->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
}
#endif
COND_WAIT(_mutex_root, _cond_root, lck_root);
_waiting_root--;
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << endl
<< pid << " " << kt->task_name << " "
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
}
#endif
// other thread broacast wake up and decreasing _waiting_root
waiting = check_parents_done(kt, _mutex_dependency);
} // while (waiting > 0)
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
} // if (waiting > 0)
atomic_size = (*it->queue)[pos]->atomic_size;
for (int m = 0; m < atomic_size; m++) {
execute_task(it, (pos + m), permute_block, // loop with atomic_size
pid, _mutex_dependency);
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "{ " << pid << " " << pos << " }";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (finished_status) { // && (zone_static_assigned == 0)) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " queue is exhausted in the first greedy"
<< it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
}
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
it->ops_complexity -= *((*it->queue)[pos]->ops_complexity);
zone_static_assigned = _zone_static_assigned[zone_idxn];
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
#ifdef DEBUG_EXEC_THREAD
if (zone_static_assigned == 1) {
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " end the first greedy "
<< it->pos << endl;
MUTEX_UNLOCK(_mutex_debug);
}
}
#endif
} // while (zone_static_assigned == 0)
} // if (zone_last_entered)
// static
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "pid = " << pid << " zone_idxn = " << zone_idxn
<< "< " << _begins[pid][zone_idxn]
<< " " << _ends[pid][zone_idxn] << " > assigned" << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int i = _begins[pid][zone_idxn]; i < _ends[pid][zone_idxn]; i++) {
execute_task(it, i, permute_block,
pid);
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << ": " << "< " << _begins[pid][zone_idxn]
<< " " << _ends[pid][zone_idxn] << " > done." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// greedy
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " "
<< it->task_name << " @ " << it->task_id
<< " greedy begin: " << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
while(1) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
pos = it->pos;
end = it->end;
if (pos < end) {
atomic_size = (*it->queue)[pos]->atomic_size;
atomic_id = (*it->queue)[pos]->atomic_id;
it->pos += atomic_size; // pos++
if (it->pos >= end) {
finished_status = 1;
_phase_dynamic++;
if (_phase_dynamic == _queue_dynamic->size()) {
_phase_dynamic = (-1);
} // queue is exhausted
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " _phase_dynamic = "
<< _phase_dynamic << " @ "
<< _queue_dynamic->size() << endl;
if (_phase_dynamic >= 0) {
cerr << pid << " next = "
<< (*_queue_dynamic)[_phase_dynamic]->task_name
<< endl;
}
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
} // if (pos < end)
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
if (pos >= end) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " queue is already exhausted " << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
break;
}
atomic_size = (*it->queue)[pos]->atomic_size;
for (int m = 0; m < atomic_size; m++) {
execute_task(it, (pos + m), permute_block, // loop with atomic_size
pid,
_mutex_dependency);
}
#ifdef DEBUG_EXEC_THREAD1
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( " << pid << " " << pos << " : "
<< (*it->queue)[pos]->task_name << " ) ";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (finished_status) {
break;
}
} // while(1)
//
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " greedy end : " << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
void QueueRuntime::thread_queue_single(const int pid,
const int num_threads,
C_task_seq *it,
int *permute_block,
const int zone_idxn)
{
// tasks are excuted by a single thread : atomic operation will not be divided.
int start = it->begin;
bool zone_flag;
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
zone_flag = (_zone_entered[zone_idxn] == num_threads);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " @ " << num_threads << " single "
<< it->task_name << " : " << it->task_id
<< " zone_flag = " << zone_flag << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
while ((start < it->end) && (!zone_flag)) {
C_task *kt = (*it->queue)[start];
int waiting = check_parents_done(kt, _mutex_dependency);
while(waiting > 0) {
// looking for dynamic queue
int flag = execute_task_dynamic_buffer(permute_block,
pid,
_mutex_dependency);
if (flag != 1) {
//
int waiting2;
waiting2 = check_parents_done(kt, _mutex_dependency);
while(waiting2 > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
_waiting_root++;
#ifdef DEBUG_DEADLOCK
if (_waiting_root > num_threads) {
fprintf(stderr, "dead lock occured : %s %d\n",
__FILE__, __LINE__);
exit(-1);
}
#endif
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << kt->task_name << " "
<< "waiting = "<< waiting << " : "
<< (int)_waiting_root << " : "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = kt->parents_work->begin();
jt != kt->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
}
#endif
COND_WAIT(_mutex_root, _cond_root, lck_root);
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << endl
<< pid << " " << kt->task_name << " "
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
}
#endif
_waiting_root--;
// other thread broacast wake up and decreasing _waiting_root
waiting2 = check_parents_done(kt, _mutex_dependency);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
} // while (waiting2)
} // if (flag != 1)
waiting = check_parents_done(kt, _mutex_dependency);
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
zone_flag = (_zone_entered[zone_idxn] == num_threads);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
if (zone_flag) {
break;
}
} // while (waiting > 0)
execute_task(it, start, permute_block,
pid,
_mutex_dependency);
if ((*it->queue)[start]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " start = " << start
<< " : " << it->task_name << " finished... skip "
<< (*it->queue)[start]->to_next_task << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// const int ibegin = start + 1;
start += (*it->queue)[start]->to_next_task;
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << "( " << pid << " : "
<< (*it->queue)[start]->task_name << " ) ";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
start++;
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
zone_flag = (_zone_entered[zone_idxn] == num_threads);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
} // while ((start < it->end) || (!zone_flag))
for (int j = start; j < it->end; j++) {
execute_task(it, j, permute_block,
pid);
if ((*it->queue)[j]->quit_queue) {
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " j = " << j
<< " : " << it->task_name << " finished... skip "
<< (*it->queue)[j]->to_next_task << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// const int ibegin = j + 1;
j += (*it->queue)[j]->to_next_task;
}
} // loop : j
#ifdef DEBUG_EXEC_THREAD2
{
MUTEX_LOCK(_mutex_debug, lck_debug);
for (int j = start; j < it->end; j++) {
cerr << "( " << pid << " : "
<< (*it->queue)[j]->task_name << " ) ";
}
MUTEX_UNLOCK(_mutex_debug);
}
#endif
//
}
int QueueRuntime::execute_task_dynamic_buffer(int *permute_block,
int pid,
QueueRuntime_mutex &mutex_dependency)
{
int ph_dynmc, pos, end, atomic_size, atomic_id;
int waiting;
int update_status = 0;
C_task *kt;
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
ph_dynmc = _phase_dynamic;
if (ph_dynmc >= 0) {
pos = (*_queue_dynamic)[ph_dynmc]->pos;
end = (*_queue_dynamic)[ph_dynmc]->end;
if (pos < end) {
atomic_size = (*(*_queue_dynamic)[ph_dynmc]->queue)[pos]->atomic_size;
atomic_id = (*(*_queue_dynamic)[ph_dynmc]->queue)[pos]->atomic_id;
kt = (*(*_queue_dynamic)[ph_dynmc]->queue)[pos];
// to avoid other thread takes the same pos
waiting = check_parents_done(kt, mutex_dependency);
if (waiting <= 0) {
(*_queue_dynamic)[ph_dynmc]->pos += atomic_size; // pos++
if ((*_queue_dynamic)[ph_dynmc]->pos == end) {
update_status = 1;
_phase_dynamic++;
if (_phase_dynamic == _queue_dynamic->size()) {
_phase_dynamic = (-1);
}
} // if ((*_queue_dynamic)[ph_dynmc]->pos == end)
}
}
else {
ph_dynmc = (-1);
}
} // if (ph_dynmc > 0)
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
if (ph_dynmc < 0) {
return (-1); // queue exhausted
}
if (waiting > 0) { // waiting == (-1) <=> quit_queue == true
return 0; // the first task in the queue is not ready
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " from dynamic "
<< (*_queue_dynamic)[ph_dynmc]->task_name << " "
<< pos << " @ " << ph_dynmc
<< " " << (*_queue_dynamic)[ph_dynmc]->end
<< " " << kt->task_name << " : ";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
for (int m = 0; m < atomic_size; m++) {
execute_task((*_queue_dynamic)[ph_dynmc], (pos + m), // pos
permute_block,
pid, mutex_dependency);
}
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << kt->task_name << " : "
<< pos << " done" << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
// ops_complexity is recalculated in each routine :-
{ // scope of mutex
// std::unique_locklck_root(_mutex_root);
MUTEX_LOCK(_mutex_root, lck_root);
(*_queue_dynamic)[ph_dynmc]->ops_complexity -= *(kt->ops_complexity);
if (update_status) {
(*_queue_dynamic)[ph_dynmc]->status = TASK_DONE;
}
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
return 1; // success
}
int QueueRuntime::check_parents_done(C_task *it,
QueueRuntime_mutex &mutex_dependency)
{
unsigned char status;
int dependency = 0;
bool quit_queue = false;
// cerr << it->task_name << " size = " << it->parents_work->size() << " || ";
for(list::iterator nt = it->parents_work->begin();
nt != it->parents_work->end(); ) {
// cerr << (*nt)->task_name << " ";
#ifdef TASKSTATUS_MUTEX
{
MUTEX_LOCK(_mutex_dependency, lck_dependency);
status = (*nt)->status;
MUTEX_UNLOCK(_mutex_dependency);
}
#else
status = (*nt)->status;
#endif
if (status == TASK_DONE) {
if ((*nt)->quit_queue) {
quit_queue = true;
}
// 5 Jul.2015 Atsushi
nt = it->parents_work->erase(nt);
// ++nt;
}
else {
dependency++;
++nt;
}
}
// cerr << " >> " << it->parents_work->size() << " . " << endl;
if (quit_queue && (dependency == 0)) {
dependency = (-1);
}
return dependency;
}
int QueueRuntime::check_parents_done(C_task *it)
{
int dependency = 0;
bool quit_queue = false;
// cerr << it->task_name << " size = " << it->parents_work->size() << " | ";
for(list::iterator nt = it->parents_work->begin();
nt != it->parents_work->end(); ) {
// cerr << (*nt)->task_name << " ";
if ((*nt)->status == TASK_DONE) {
if ((*nt)->quit_queue) {
quit_queue = true;
}
// 5 Jul.2015 Atsushi
nt = it->parents_work->erase(nt);
// ++nt;
}
else {
dependency++;
++nt;
}
}
if (quit_queue && (dependency == 0)) {
dependency = (-1);
}
return dependency;
}
void QueueRuntime::execute_task(C_task_seq *seq, int pos,
int *permute_block,
int pid,
QueueRuntime_mutex &mutex_depenency)
{
C_task *task = (*seq->queue)[pos];
// debugging
#ifdef DEBUG_CHECKPARENTS_DONE
int waiting;
waiting = check_parents_done(task, mutex_dependency);
if (waiting > 0) {
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " parents of task " << task->task_name
<< " not finished : ";
for(list::const_iterator nt = task->parents_work->begin();
nt != task->parents_work->end(); ++nt) {
cerr << (*nt)->task_name << " ";
}
cerr << endl;
MUTEX_UNLOCK(_mutex_debug);
}
}
#endif
//
#ifdef DEBUG_PRINT_TASK
switch (task->task_id) {
case C_FILLMATRIX:
case C_DFULL_SYM_GAUSS:
case C_DTRSMSCALE:
// case C_SPARSESCHUR:
case C_DGEMM_LOCAL_MULT:
case C_DGEMM_LOCAL_TWO:
case C_DGEMM_DIRECT_TWO:
diss_printf(_verbose, _fps[pid], "%s\n", task->task_name);
*(task->fp) = &_fps[pid];
break;
}
#endif
#ifdef TASKSTATUS_MUTEX
{
MUTEX_LOCK(_mutex_dependency, lck_dependency);
task->status = TASK_WORKING;
MUTEX_UNLOCK(_mutex_dependency);
}
#else
task->status = TASK_WORKING;
#endif // #ifdef TASKSTATUS_MUTEX
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t0));
// clock_gettime(CLOCK_MONOTONIC, &(task->t0));
#endif
task->func(task->func_arg);
#ifdef DEBUG_THREAD_DONE_PRINT
{
MUTEX_LOCK(_mutex_debug, lck_debug);
fprintf(stderr, "pid = %d : %s\n", pid, task->task_name);
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (task->task_id == C_DFULL_SYM_GAUSS) {
// task->quit_queue = ((C_dfull_gauss_arg*)task->func_arg)->quit;
#ifdef TASKSTATUS_MUTEX
{ // scope of mutex
MUTEX_LOCK(_mutex_dependency, lck_dependency);
// std::unique_locklck_dependency(mutex_dependency);
for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
(*seq->queue)[i]->status = TASK_DONE;
(*seq->queue)[i]->quit_queue = true;
}
MUTEX_UNLOCK(_mutex_dependency);
} // scope of mutex
#endif // #ifdef TASKSTATUS_MUTEX
{
for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
(*seq->queue)[i]->status = TASK_DONE;
(*seq->queue)[i]->quit_queue = true;
#ifdef DEBUG_EXEC_THREAD2
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << (*seq->queue)[i]->task_name << " ";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
}
} // if (task->task_id == C_DFULL_SYM_GAUSS)
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t1));
// clock_gettime(CLOCK_MONOTONIC, &(task->t1));
task->thread_id = pid;
#endif
#ifdef DEBUG_EXEC_THREAD_FILE
{
MUTEX_LOCK(_mutex_file, lck_file);
const int sec_n0 = convert_sec(task->t0);
const int sec_m0 = convert_microsec(task->t0);
_fout << task->task_name << " / ";
_fout << sec_n0 << " " << sec_m0 << "\t";
for(list::const_iterator nt = task->parents->begin();
nt != task->parents->end(); ++nt) {
int sec_n1 = convert_sec((*nt)->t1);
int sec_m1 = convert_microsec((*nt)->t1);
if ((sec_n0 < sec_n1) || ((sec_n0 == sec_n1) && (sec_m0 < sec_m1))) {
_fout << "*";
}
_fout << (*nt)->task_name << " / ";
_fout << sec_n1 << " " << sec_m1 << "\t";
}
_fout << endl; // " : " << pid << endl;
MUTEX_UNLOCK(_mutex_file);
}
#endif
#ifdef TASKSTATUS_MUTEX
{ // scope of mutex
MUTEX_LOCK(_mutex_dependency, lck_dependency);
task->status = TASK_DONE;
MUTEX_UNLOCK(_mutex_dependecny);
} // scope of mutex
#else
task->status = TASK_DONE;
#endif
//
if (_waiting_root > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
COND_BROADCAST(_cond_root);
MUTEX_UNLOCK(_mutex_root);
} // scope of mutex
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << task->task_name
<< "_waiting_root = " << (int)_waiting_root
<< " broadcast." << endl;
}
#endif
}
}
void QueueRuntime::execute_task(C_task_seq *seq, int pos,
int *permute_block,
int pid)
{
C_task *task = (*seq->queue)[pos];
#ifdef DEBUG_CHECKPARENTS_DONE
// debugging
int waiting;
waiting = check_parents_done(task);
if (waiting > 0) {
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " parents of task " << task->task_name
<< " not finished : " << task->parents_work->size() << " : ";
// debug : 5 Jul. 2015, Atsushi
for(list::const_iterator nt = task->parents_work->begin();
nt != task->parents_work->end(); ++nt) {
cerr << (*nt)->task_name << " / ";
}
cerr << endl;
MUTEX_UNLOCK(_mutex_debug);
}
}
//
#endif
#ifdef DEBUG_PRINT_TASK
switch (task->task_id) {
case C_FILLMATRIX:
case C_DFULL_SYM_GAUSS:
case C_DTRSMSCALE:
// case C_SPARSESCHUR:
case C_DGEMM_LOCAL_MULT:
case C_DGEMM_LOCAL_TWO:
case C_DGEMM_DIRECT_TWO:
diss_printf(_verbose, _fps[pid], "%s\n", task->task_name);
*(task->fp) = &_fps[pid];
break;
}
#endif
// accuessing to unsigned char does not need mutex
task->status = TASK_WORKING;
//
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t0));
// clock_gettime(CLOCK_MONOTONIC, &(task->t0));
#endif
// debugging : 13 :Apr.2012 Atsushi
task->func(task->func_arg);
#ifdef DEBUG_THREAD_DONE_PRINT
{
MUTEX_LOCK(_mutex_debug, lck_debug);
fprintf(stderr, "pid = %d : %s\n", pid, task->task_name);
MUTEX_UNLOCK(_mutex_debug);
}
#endif
if (task->task_id == C_DFULL_SYM_GAUSS) {
for (int i = (pos + 1); i <= (pos + task->to_next_task); i++) {
(*seq->queue)[i]->status = TASK_DONE;
(*seq->queue)[i]->quit_queue = true;
#ifdef DEBUG_EXEC_THREAD2
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << (*seq->queue)[i]->task_name << " ";
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}
}
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t1));
// clock_gettime(CLOCK_MONOTONIC, &(task->t1));
task->thread_id = pid;
#endif
// accessing to unsigned char does not neet mutex
task->status = TASK_DONE;
//
if (_waiting_root > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
// std::unique_locklck_root(_mutex_root);
COND_BROADCAST(_cond_root);
// _cond_root.notify_all();
MUTEX_UNLOCK(_mutex_root);
} //scope of mutex
#ifdef DEBUG_EXEC_THREAD_IDLE
{
cerr << pid << " " << task->task_name
<< "_waiting_root = " << (int)_waiting_root
<< " broadcast." << endl;
}
#endif
}
//
#ifdef DEBUG_EXEC_THREAD_FILE
{
MUTEX_LOCK(_mutex_file, lck_file);
const int sec_n0 = convert_sec(task->t1);
const int sec_m0 = convert_microsec(task->t1);
_fout << task->task_name << " / ";
_fout << sec_n0 << " " << sec_m0 << "\t";
for(list::const_iterator nt = task->parents->begin();
nt != task->parents->end(); ++nt) {
int sec_n1 = convert_sec((*nt)->t1);
int sec_m1 = convert_microsec((*nt)->t1);
if ((sec_n0 < sec_n1) || ((sec_n0 == sec_n1) && (sec_m0 < sec_m1))) {
_fout << "*";
}
_fout << (*nt)->task_name << " / ";
_fout << sec_n1 << " " << sec_m1 << "\t";
}
_fout << endl; // " : " << pid << endl;
MUTEX_UNLOCK(_mutex_file);
}
#endif
task->status = TASK_DONE;
}
void QueueRuntime::exec_fwbw_seq()
{
clock_t t0_cpu, t1_cpu;
elapsed_t t0_elapsed, t1_elapsed;
t0_cpu = clock();
get_realtime(&t0_elapsed);
for (vector::const_iterator it = _queue_fwbw->queue->begin();
it != _queue_fwbw->queue->end(); ++it) {
(*it)->func((*it)->func_arg);
}
t1_cpu = clock();
get_realtime(&t1_elapsed);
diss_printf(_verbose, _fp,
"execution of fw/bw : cpu time = %.4e elapsed time = %.4e\n",
(double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
convert_time(t1_elapsed, t0_elapsed));
}
void QueueRuntime::exec_fwbw()
{
const int num_threads = _num_threads; //_num_threads_symb;
#ifdef POSIX_THREADS
void* results;
pthread_attr_t th_attr;
#endif
vector threads;
clock_t t0_cpu, t1_cpu;
elapsed_t t0_elapsed, t1_elapsed;
// struct timespec ts0, ts1;
int ierr;
diss_printf(_verbose, _fp, "fwbw with %d threads\n", num_threads);
// copy dependency data : parents -> parents_work
{
for (vector::const_iterator it = _queue_fwbw->queue->begin();
it != _queue_fwbw->queue->end(); ++it) {
list& parents_work = *((*it)->parents_work);
if (parents_work.size() > 0) { // to avoid double free
parents_work.clear();
}
} // loop : it
for (vector::const_iterator it = _queue_fwbw->queue->begin();
it != _queue_fwbw->queue->end(); ++it) {
list& parents = *((*it)->parents);
list& parents_work = *((*it)->parents_work);
(*it)->status = TASK_WAITING; // reset status
(*it)->quit_queue = false;
if (parents_work.size() == 0) {
#ifdef SX_ACE
for (list::const_iterator lt = parents.begin();
lt != parents.end(); ++lt) {
parents_work.push_back(*lt);
}
#else // SX-ACE C++ rev 110 with C++98/03 does not understand back_inserter
std::copy(parents.begin(), parents.end(), back_inserter(parents_work));
#endif
}
(*it)->broadcast_deadlock = 0;
} // loop : it
_queue_fwbw->pos = _queue_fwbw->begin;
}
#ifdef POSIX_THREADS
// threads = new pthread_t[num_threads];
threads.resize(num_threads);
#ifdef DEBUG_EXEC_THREAD
pthread_mutex_init(&_mutex_debug, NULL);
#endif
pthread_mutex_init(&_mutex_dependency, NULL);
pthread_cond_init(&_cond_root, NULL);
ierr = pthread_mutex_init(&_mutex_root, NULL);
if (ierr != 0) {
fprintf(stderr, " pthread_mutex_init(&_mutex_root, NULL) %s %d : %d\n",
__FILE__, __LINE__, ierr);
}
#ifdef DEBUG_EXEC_THREAD
ierr = pthread_mutex_init(&_mutex_debug, NULL);
if (ierr != 0) {
diss_printf(_verbose, _fp,
"%s %d : pthread_mutex_init(&_mutex_debug, NULL) %d\n",
__FILE__, __LINE__, ierr);
}
#endif
pthread_attr_init(&th_attr);
pthread_attr_setdetachstate(&th_attr, PTHREAD_CREATE_JOINABLE);
#endif
#ifdef DEBUG_EXEC_THREAD_FILE
{
int pid = get_process_id();
char fname[256];
sprintf(fname, "task-s.%d.data", pid);
_fout.open(fname);
}
#endif
t0_cpu = clock();
get_realtime(&t0_elapsed);
// clock_gettime(CLOCK_REALTIME, &ts0);
#ifdef POSIX_THREADS
THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
for (int p = 0; p < num_threads; p++) {
params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
int pid = pthread_create(&threads[p], &th_attr,
&thread_queue_fwbw_,
(void *)params[p]);
if (pid != 0) {
fprintf(stderr, "bad thread creation ? : %d\n", pid);
exit(0);
}
}
pthread_attr_destroy(&th_attr);
for (int p = 0; p < num_threads; p++) {
int pid = pthread_join(threads[p], &results);
if (pid != 0) {
fprintf(stderr, "bad thread creation ? : %d\n", pid);
exit(0);
}
delete params[p];
}
delete [] params;
#else
THREAD_QUEUE_EXEC **params = new THREAD_QUEUE_EXEC*[num_threads];
for (int p = 0; p < num_threads; p++) {
params[p] = new THREAD_QUEUE_EXEC(p, num_threads, this);
threads.push_back(std::thread(thread_queue_fwbw_,
(void *)params[p]));
}
for (int p = 0; p < num_threads; p++) {
threads[p].join();
delete params[p];
}
delete [] params;
#endif
t1_cpu = clock();
get_realtime(&t1_elapsed);
// clock_gettime(CLOCK_REALTIME, &ts1);
diss_printf(_verbose, _fp,
"execution of fw/bw : cpu time = %.4e elapsed time = %.4e\n",
(double)(t1_cpu - t0_cpu) / (double)CLOCKS_PER_SEC,
convert_time(t1_elapsed, t0_elapsed));
#ifdef DEBUG_EXEC_THREAD_FILE
_fout.close();
#endif
#ifdef DEBUG_THREAD_TIME
{
int pid = get_process_id();
char filename[256];
FILE *fp;
sprintf(filename, "threadtime-fwbw.%d.data", pid);
if ((fp = fopen(filename, "w")) == NULL) {
fprintf(stderr,
"%s %d : fail to open %s\n",
__FILE__, __LINE__, filename);
exit(-1);
}
else {
fprintf(fp, "queue_fwbw\n");
for (int j = _queue_fwbw->begin; j < _queue_fwbw->end; j++) {
double t0 = (convert_sec((*_queue_fwbw->queue)[j]->t0) +
convert_microsec((*_queue_fwbw->queue)[j]->t0) * 1.0e-6);
fprintf(fp, "%2d:\t%-16s\t%2d\t%4d\t%7d\t%7d\t%7d\t%7d",
(*_queue_fwbw->queue)[j]->thread_id,
(*_queue_fwbw->queue)[j]->task_name,
(int)(*_queue_fwbw->queue)[j]->parents_work->size(),
(*_queue_fwbw->queue)[j]->broadcast_deadlock,
convert_sec((*_queue_fwbw->queue)[j]->t0),
convert_microsec((*_queue_fwbw->queue)[j]->t0),
convert_sec((*_queue_fwbw->queue)[j]->t1),
convert_microsec((*_queue_fwbw->queue)[j]->t1));
for (list::const_iterator it = (*_queue_fwbw->queue)[j]->parents->begin();
it != (*_queue_fwbw->queue)[j]->parents->end(); ++it) {
double tt1 = (convert_sec((*it)->t1) +
convert_microsec((*it)->t1) * 1.0e-6);
if (t0 < tt1) {
fprintf(fp, " [ %10s ]", (*it)->task_name);
}
}
fprintf(fp, "\n");
}
fclose(fp);
} // if ((fp = fopen(filename, "a")) == NULL)
}
#endif
#ifdef POSIX_THREADS
pthread_mutex_destroy(&_mutex_root);
#ifdef DEBUG_EXEC_THREAD
pthread_mutex_destroy(&_mutex_debug);
#endif
threads.clear();
#endif
}
void *thread_queue_fwbw_(void *arg)
{
THREAD_QUEUE_EXEC *params = (THREAD_QUEUE_EXEC *)arg;
params->dissectionRuntime->thread_queue_fwbw(params->id,
params->num_threads);
#ifdef POSIX_THREADS
pthread_exit(arg);
#endif
return (void *)NULL;
}
// #define DEBUG_EXEC_THREAD_IDLEa
void QueueRuntime::thread_queue_fwbw(const int pid, const int num_threads)
{
// const int pid = params->id;
// const int num_threads = params->num_threads;
// greedy -- better to be in seperated function
int pos, end;
C_task_seq* it = _queue_fwbw;
// cerr << "pid = " << pid
// << " _queue_symb : pos = " << it->pos << " end = " << it->end << endl;
while (1) {
{
// std::unique_locklck_root(_mutex_root);
MUTEX_LOCK(_mutex_root, lck_root);
pos = it->pos;
end = it->end;
if (pos < end) {
it->pos = it->pos + (*it->queue)[pos]->atomic_size;
}
MUTEX_UNLOCK(_mutex_root);
} // destruction of lck_root
if (pos >= end) {
break;
}
C_task *task_p = (*it->queue)[pos];
for (int i = 0; i < task_p->atomic_size; i++) {
C_task *task = (*it->queue)[pos + i];
int waiting = check_parents_done(task, _mutex_dependency);
while (waiting > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
_waiting_root++;
if (_waiting_root == num_threads) {
#ifdef DEBUG_EXEC_THREAD_IDLEa
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << task->task_name
<< " _waiting_root = " << (int)_waiting_root
<< " dead locked! : emergency broadcast." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif // DEBUG_EXEC_THREAD_IDLEa
COND_BROADCAST(_cond_root);
task->broadcast_deadlock++;
}
#ifdef DEBUG_EXEC_THREAD_IDLEa
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << task->task_name << " "
<< "waiting = "<< waiting << " : "
<< (int)_waiting_root << " "
<< __FILE__ << " " << __LINE__ << " ";
for (list::const_iterator jt = task->parents_work->begin();
jt != task->parents_work->end(); ++jt) {
cerr << (*jt)->task_name << " ";
}
cerr << " : sleeping" << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif // DEBUG_EXEC_THREAD_IDLEa
COND_WAIT(_mutex_root, _cond_root, lck_root);
_waiting_root--;
#ifdef DEBUG_EXEC_THREAD_IDLEa
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << task->task_name
<< " waked up : _waiting_root = " << (int)_waiting_root
<< endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif // DEBUG_EXEC_THREAD_IDLEa
// other thread broacast wake up and decreasing _waiting_root
waiting = check_parents_done(task, _mutex_dependency);
MUTEX_UNLOCK(_mutex_root);
} // destruction of lck_root
} // while (waiting > 0)
{
MUTEX_LOCK(_mutex_dependency, lck_dependency);
task->status = TASK_WORKING;
MUTEX_UNLOCK(_mutex_dependency);
} // destruction of lck_dependency
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t0));
#endif
task->func(task->func_arg);
#ifdef DEBUG_THREAD_TIME
get_realtime(&(task->t1));
task->thread_id = pid;
#endif
{
MUTEX_LOCK(_mutex_dependency, lck_depenency);
task->status = TASK_DONE;
MUTEX_UNLOCK(_mutex_dependency);
}
if (_waiting_root > 0) {
{ // scope of mutex
MUTEX_LOCK(_mutex_root, lck_root);
#ifdef DEBUG_EXEC_THREAD_IDLEa
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << task->task_name
<< " _waiting_root = " << (int)_waiting_root
<< " broadcast." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif // DEBUG_EXEC_THREAD_IDLEa
COND_BROADCAST(_cond_root);
MUTEX_UNLOCK(_mutex_root);
} // destruction of lck_root
}
} // loop : i
} // while (1)
#ifdef DEBUG_EXEC_THREAD
{
MUTEX_LOCK(_mutex_debug, lck_debug);
cerr << pid << " " << it->task_name
<< " @ " << it->task_id << " greedy end." << endl;
MUTEX_UNLOCK(_mutex_debug);
}
#endif
}