#ifdef MPI

#define SYNC_FIX_BY_RTJ   1

//#include <stdlib.h>
//#include <iostream.h>
#include <iostream>
#include "SA_Synchronizer.h"



//---- SA_Synchronizer ---------------------------------------------------------
//#define nSYNC_DEBUG			// define SYNC_DEBUG leads to warnings about late messages 
SA_Synchronizer::SA_Synchronizer(MPI_Comm comm):
	cluster(comm),
	MasterSlave(17),
	SlaveMaster(23),
	ClusterSync_ready(0),
	costs(NULL),
	arr_ind(NULL),
	arr_stat(NULL),
	founds(NULL),
	FoundTag(0),
	reqs(NULL)
{
	SetCluster(comm);

#ifdef SHOW_NFOUND
	NfoundSum = Nfoundi = 0;
#endif
}

SA_Synchronizer::SA_Synchronizer():
	MasterSlave(17),
	SlaveMaster(23),
	ClusterSync_ready(0),
	costs(NULL),
	arr_ind(NULL),
	arr_stat(NULL),
	founds(NULL),
	FoundTag(0),
	reqs(NULL)
{
#ifdef SHOW_NFOUND
	NfoundSum = Nfoundi = 0;
#endif
}


void SA_Synchronizer::SetCluster(MPI_Comm comm)
{
	FoundTag = 0;
	
	if (costs != NULL)
		{delete [] costs;costs = NULL;}
	if ( reqs != NULL)
		{delete [] reqs;reqs = NULL;}
	if(arr_ind != NULL)
		{delete [] arr_ind;arr_ind = NULL;}
	if ( arr_stat != NULL)
		{delete [] arr_stat;arr_stat = NULL;}
	if ( founds != NULL)
		{delete [] founds;founds = NULL;}
	
	int comp_res;
	
	MPI_Comm_compare(comm,MPI_COMM_SELF,&comp_res);
		
	if (comp_res == MPI_IDENT || comp_res == MPI_CONGRUENT)
	{
		cluster = comm;
		nproc = 1;
		me = 0;
	}
	else
	{
		MPI_Comm_dup(comm,&cluster);
		MPI_Comm_size(cluster, &nproc);
		MPI_Comm_rank(cluster,&me);
		if ( me == 0 )
		{
			costs = new float[nproc];
			founds = new int[nproc];
			reqs = new MPI_Request[nproc];
			arr_ind = new int[nproc];
			arr_stat = new MPI_Status[nproc];
			if (costs == NULL || founds == NULL || reqs == NULL || arr_ind == NULL || arr_stat == NULL)
			{
				std::cout <<"n"<<myrank<<"SA_Synchronizer cannot allocate memory!\n";
				exit(1);
			}
		InitReqsCosts();
		}
	}
}


SA_Synchronizer::~SA_Synchronizer()
{
	if (costs != NULL)
		delete [] costs;
	if ( reqs != NULL)
		delete [] reqs;
	if(arr_ind != NULL)
		delete [] arr_ind;
	if ( arr_stat != NULL)
		delete [] arr_stat;
	if ( founds != NULL)
		delete [] founds;
}

bool SA_Synchronizer::MasterSync(bool found)
{
	if ( me == 0)
	{
		if ( found )
		{
			FoundTag++;
			int i;
			for(i=1;i<nproc;i++)
			{			
//				MPI_Request_free(&reqs[i]);
				MPI_Issend(NULL,0,MPI_BYTE,i,FoundTag,cluster,&reqs[i]);
			}
		}
		return found;
	}
	else /* Slave */
	{
		int flag=0;
		MPI_Status status;
	
		MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
		
		if (flag )	// Falls der Master einen Isend abgeschickt hat, d.h. bevor mein Send ankam
		{
			FoundTag++;
			if (status.MPI_TAG != FoundTag ) // 
			{ 
#ifdef SYNC_DEBUG
std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<". Status: Error!\n";
#endif
			}
			else	// 
			{
				MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
			}
			return true;
		}
		else
			return false;
	}
}

bool SA_Synchronizer::ClusterSyncGroup(int found, float cost, EXCHANGE_MODE exch_m, int * root)
{
	struct
	{
		float	cost_value;
		int		rank;
	} my_config, best_config;

	my_config.rank = me;
	
	if ( exch_m == BEST )
		//my_config.cost_value = found ? cost : (OptType == Opt::MIN ? INFINITY : -INFINITY);
		my_config.cost_value = found ? cost : INFINITY;
	else if ( exch_m == FIRST || exch_m == RANDOM)
		my_config.cost_value = found ? me : INFINITY;
	else if (exch_m == MESSAGE)
	{
		my_config.cost_value = -1;
/**/	my_config.rank = me;			// Hier gilt, da MESSAGE : cost -1,-2,-3
	}
	else
		std::cout <<"n"<<myrank<<" unknown EXCHANGE_MODE "<<exch_m<<std::endl;
		

//	if ( OptType == Opt::MIN )
//		MPI_Allreduce(&my_config,&best_config,1,MPI_FLOAT_INT,MPI_MINLOC,cluster);
//	else
//		MPI_Allreduce(&my_config,&best_config,1,MPI_FLOAT_INT,MPI_MAXLOC,cluster);
	MPI_Allreduce(&my_config,&best_config,1,MPI_FLOAT_INT,MPI_MINLOC,cluster);

	if ( best_config.cost_value == INFINITY )	// Falls niemand etwas fand
		return false;
	else if ( best_config.cost_value < 0 )	// falls Master eine Nachricht verteilen moechte
	{
		*root = best_config.rank;
		return false;
	}
	else
	{
		*root = best_config.rank;
		return true;
	}
}



void SA_Synchronizer::InitReqsCosts(void)
{
	if ( me == 0 )
	{
		if ( costs == NULL )
		{
			std::cout <<"n"<<myrank<<" in SA_Synchronizer: costs not set up!\n";
			return;
		}
		int i;
		for(i = 0; i<nproc; i++)
		{
			costs[i] = -3;
			reqs[i] = MPI_REQUEST_NULL;
		}
	}
}

// anhand der costs und founds den gewaehlten Uebergang bestimmen
// nfound ist dabei die Laenge der Liste founds
int	SA_Synchronizer::GetWinner(EXCHANGE_MODE exch_m, int nfound)
{
	if ( exch_m == FIRST )
	{
		return founds[0];
	}
	else if (exch_m == RANDOM)
	{
		return founds[nfound-1];
	}
	else
	{
		int i,best_i; 
		if ( OptType == Opt::MIN) 
		{
			for(best_i=0,i=1; i<nfound;i++)
				if ( costs[founds[i]] < costs[founds[best_i]])
					best_i = i;
		}
		else
		{
			for(best_i=0,i=1; i<nfound;i++)
				if ( costs[founds[i]] > costs[founds[best_i]])
					best_i = i;
		}
		return founds[best_i];
	}
}

// nur anhand der costs den gewaehlten Uebergang bestimmen	
int	SA_Synchronizer::GetWinner(EXCHANGE_MODE exch_m)
{
	int i=0,best_i=0;
int nfound=0;
//std::cout <<"n"<<myrank;for(i=0;i<nproc;i++) std::cout<<" "<<costs[i]; std::cout<<std::endl;	 
	if ( OptType == Opt::MIN) 
	{
		if ( exch_m == FIRST || exch_m == RANDOM)
		{
			while( costs[best_i] >= INFINITY/2)
				best_i++; 
		}
		else
		{
			for(best_i=nproc-1,i=nproc-2; i>=0;i--)
				if ( costs[i] < costs[best_i])
					best_i = i;
		}	
#ifdef SHOW_NFOUND
		for(i=0;i<nproc;i++)
		{	if ( costs[i] < INFINITY/2 )
				nfound++;
		}
		NfoundSum +=nfound;
		Nfoundi++;
#endif
	}
	else
	{
		if ( exch_m == FIRST || exch_m == RANDOM)
		{
			while( costs[best_i] <= -INFINITY/2)
				best_i++; 
		}
		else
		{
			for(best_i=nproc-1,i=nproc-2; i>=0;i--)
			{
				if ( costs[i] > costs[best_i])
					best_i = i;
			}
		}
#ifdef SHOW_NFOUND
		for(i=0;i<nproc;i++)
		{	if ( costs[i] > -INFINITY/2 )
				nfound++;
		}
		NfoundSum +=nfound;
		Nfoundi++;
#endif
	}
	return best_i;
}


bool SA_Synchronizer::ClusterSyncNext(int found, float cost, EXCHANGE_MODE exch_m, int * root)
/* Vorgehensweise beim nichttrivialem Cluster:
MASTER:	Benutzt IProbe, um found bei Slaves festzustellen und ISend, um allen anderen Slaves found mitzuteilen
SLAVE: benutzt Send um found zu melden und cost mitzuteilen, und Iprobe, um found im Cluster zu erfahren

Bei jedem Aufruf der Funktion:
SLAVE: 
	1. Falls move_accepted:
		1.1		Sende Message an Master: MPI_Send(cost)
		1.2		MPI_Bcast(root,0) liefert Nummer des "Gluecklichen"
		1.3		Pruefe mit MPI_Iprobe, ob kein Message vom Master vorliegt (moeglich!)
				1.3.1 ggf. empfangen 
		1.4		return true;
	2. sonst : MPI_Iprobe, ob ein Message vom Master ankommt:
		2.1 ja =>	
					Empfange das Message vom Master
					MPI_Bcast(root,0) liefert Nummer des "Gluecklichen"
					return true;
	3. return false;		
MASTER:
	1. Falls move_accepted ODER ein MPI_IProbe ein Message vom SLAVE meldet:
	  1.1	Erzeuge eine Tabelle, wo fuer jeden SLAVE vermerkt wird, ob der bereits zum Bcast ging:
		  1.1.1 wiederhole fuer i von 1 bis nproc:
			1.1.2 empfange alle vorliegende Nachrichten mit MPI_Recv, setze Eintraege in der Tabelle;
			1.1.3 ist i gesetzt ?
				nein => sende Nachricht zu i (non-block: Issend); (*)
		  [am Ende muss fuer jedes i gelten :  entweder i found UND i.cost in der Tabelle
											   oder i hat Isend empfangen, d.h. not found ]
	  1.2 Nummer des Gewinners bestimmen (exch_m und die Tabelle)
	  1.3 MPI_Bcast(root,0) verteilt Nummer des "Gluecklichen" 
	  1.4 return true;
	2. return false;	
*/
{
	
	int flag=0;
	MPI_Status status;
	
	if ( me != 0) 
	/*SLAVE*/
	{	
		if ( found)
		{
			FoundTag++;
	//MPE_Log_event(1,0,"");
			MPI_Ssend(&cost,1,MPI_FLOAT,0,FoundTag,cluster);
	//MPE_Log_event(2,0,"");
	//MPE_Log_event(9,0,"");
			MPI_Bcast(root,1,MPI_INT,0,cluster);
	//MPE_Log_event(10,0,"");
	//MPE_Log_event(3,0,"");
			MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
			if (flag )	// Falls der Master einen Isend abgeschickt hat, d.h. bevor mein Send ankam
			{
				if (status.MPI_TAG != FoundTag ) // es ist aber ein Signal von dem NAECHSTEN Found !!
				{ 
#ifdef SYNC_DEBUG
std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<". Status: no error!\n";
#endif
				}
				else	// ist doch mein Signal
				{
	//MPE_Log_event(11,0,"");
					MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
	//MPE_Log_event(12,0,"");
				}
			}
			return ( 0 <= (*root));
		}
		else
		{
	//MPE_Log_event(3,0,"");
			MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
			if (flag )	// Falls der Master einen Isend abgeschickt hat
			{
				FoundTag++;
				if (status.MPI_TAG != FoundTag )
				{ 
					std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<std::flush;
					exit(1);
				}
	//MPE_Log_event(11,0,"");
				MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
	//MPE_Log_event(12,0,"");
	//MPE_Log_event(9,0,"");
				MPI_Bcast(root,1,MPI_INT,0,cluster);
	//MPE_Log_event(10,0,"");
				return ( 0 <= (*root));
			}
		}
		return false;		
	}	
	else
	/*MASTER*/
	{
	//MPE_Log_event(3,0,"");
		MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if ( flag || found )	// falls im Cluster gefunden wurde
		{
			FoundTag++;
			int	nfound = 0,		// Anzahl der Prozessoren, die einen Uebergang gefunden haben
				nnotfound = 0;	//       -//-                 keinen        -//-
			if( found)
			{
				costs[0] = cost;
				founds[nfound] = 0;
				nfound++;
			}
			else
				nnotfound++;
			if(flag)
			{
				if (status.MPI_TAG != FoundTag )
				{ 
					std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<std::flush;
					exit(1);
				}	
	//MPE_Log_event(11,0,"");
				MPI_Recv(&costs[status.MPI_SOURCE],1,MPI_FLOAT, status.MPI_SOURCE, FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
				founds[nfound] = status.MPI_SOURCE;
				nfound++;
			}
			int i = 1;
			while ( i < nproc)
			{
				do{
	//MPE_Log_event(3,0,"");
					MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
					if(flag)
					{
						if ( costs[status.MPI_SOURCE] == -2 )	// falls zu diesem Slave bereits ein Isend geschickt wurde
						{
	//MPE_Log_event(5,0,"");
	//??	MPI_Request_free(&reqs[status.MPI_SOURCE]);
	//MPE_Log_event(6,0,"");
						}
						if (status.MPI_TAG != FoundTag )
						{ 
							std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<std::flush;
							exit(1);
						}	
	//MPE_Log_event(11,0,"");
						MPI_Recv(&costs[status.MPI_SOURCE],1,MPI_FLOAT, status.MPI_SOURCE, FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
						founds[nfound] = status.MPI_SOURCE;
						nfound++;
					}
				} while (flag);
				if ( costs[i] < 0 )	// kein cost vom i empfangen
				{
	//MPE_Log_event(101,0,"");
					MPI_Issend(NULL,0,MPI_BYTE,i,FoundTag,cluster,&reqs[i]);
	//MPE_Log_event(102,0,"");
					costs[i] = -2;
				}
				i++;
			}
			/* jetzt muss garantiert werden, dass kein blocking-Send von einem Slave gestartet wurde,
				d.i. alle Slaves bis zum Bcast durchgekommen sind*/
			int outcount=0;
			while( nfound+nnotfound < nproc )
			{	// Issend auf complete testen, d.h. ob Recv vom Slave aufgerufen wurde
	//MPE_Log_event(7,0,"");
				MPI_Testsome(nproc,reqs,&outcount,arr_ind,arr_stat);
	//MPE_Log_event(8,0,"");
				for(i=0 ; i<outcount; i++)
				{
	//MPE_Log_event(103,0,"");
					costs[arr_ind[i]] = -1;
					nnotfound++;
	//MPE_Log_event(104,0,"");
				}
				// Weitere found-Meldungen abwarten
				do{
	//MPE_Log_event(3,0,"");
					MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
					if(flag)
					{
						if ( costs[status.MPI_SOURCE] == -2 )	// falls zu diesem Slave bereits ein Isend geschickt wurde
						{
	//MPE_Log_event(5,0,"");
	//							MPI_Request_free(&reqs[status.MPI_SOURCE]);
	//MPE_Log_event(6,0,"");
						}
						if (status.MPI_TAG != FoundTag )
						{ 
							std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<std::flush;
							exit(1);
						}	
	//MPE_Log_event(11,0,"");
						MPI_Recv(&costs[status.MPI_SOURCE],1,MPI_FLOAT, status.MPI_SOURCE, FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
						founds[nfound] = status.MPI_SOURCE;
						nfound++;
					}
				} while (flag);
			}
			// Nach dem Verlassen dieser Schleife gilt : Anzahl der found-Meldungen + Anzahl der Prozessoren, die Recv aufgerufen haben, 
			// ist >= nproc, also = nproc, folglich sind alle Prozessoren bis zum Bcast durchgekommen. 
			if (exch_m == MESSAGE)
			{
				*root = -1;
			}
			else
			{
				*root = GetWinner(exch_m,nfound);
			}
	//MPE_Log_event(9,0,"");
			MPI_Bcast(root,1,MPI_INT,0,cluster);
	//MPE_Log_event(10,0,"");
			InitReqsCosts();	// Arrays fuer das naechste Mal vorbereiten
			return ( 0 <= (*root));
		}
		else
			return false;
	}
}

bool SA_Synchronizer::ClusterSyncOld(int found, float cost, EXCHANGE_MODE exch_m, int * root)
/* Vorgehensweise beim nichttrivialem Cluster:
MASTER:	Benutzt IProbe, um found bei Slaves festzustellen und ISend, um allen anderen Slaves found mitzuteilen
SLAVE: benutzt Send um found zu melden, und Iprobe, um found im Cluster zu erfahren

Bei jedem Aufruf der Funktion:
SLAVE: 
	1. Iprobe, ob Master einen Found meldet
		1.1	ja => Recv,
		1.2 Allreduce
		1.3 return true;
	2. Falls lokal found -
		2.1 Send Found zum Master
		2.2 Allreduce
		2.3 Iprobe, ob Master Found meldet (moeglich)
			2.3.1 ggf. Recv
		2.4 return true;
	3. return false;		
MASTER:
	1. Falls move_accepted ODER ein MPI_IProbe ein Message vom SLAVE meldet:
	  1.1 fuer alle i von 1 bis nproc:
			sende Nachricht zu i (non-block: Issend);		
	  1.2 Allreduce
	  1.3 Alle Founds mit gleichem FoundTag empfangen
	  1.4 return true;
	2. return false;	
*/
{
	int flag=0;
	MPI_Status status;
	
	if ( me != 0) 
	/*SLAVE*/
	{	
//MPE_Log_event(3,0,"");
		MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
//MPE_Log_event(4,0,"");
		if (flag )	// Falls der Master einen Isend abgeschickt hat
		{
			FoundTag++;
			if (status.MPI_TAG != FoundTag )
			{ 
				std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG
					<<" expected FoundTag="<<FoundTag<<". Status: bad error, exiting!\n"<<std::flush;
				exit(1);
			}
//MPE_Log_event(11,0,"");
			MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
//MPE_Log_event(12,0,"");
//MPE_Log_event(9,0,"");
			struct
			{
				float	cost_value;
				int		rank;
			} my_config, best_config;

			my_config.rank = me;

			if ( exch_m == BEST )
				my_config.cost_value = found ? cost : INFINITY;
			else if ( exch_m == FIRST || exch_m == RANDOM)
				my_config.cost_value = found ? me : INFINITY;
			else if (exch_m == MESSAGE)
			{
				my_config.cost_value = -1;
				my_config.rank = me;
			}
			else
				std::cout <<"n"<<myrank<<" unknown EXCHANGE_MODE "<<exch_m<<std::endl;


			MPI_Allreduce(&my_config,&best_config,1,MPI_FLOAT_INT,MPI_MINLOC,cluster);

			*root = best_config.rank;

//MPE_Log_event(10,0,"");
			return ( 0 <= best_config.cost_value);
		}
		if ( found)
		{
	FoundTag++;
	//MPE_Log_event(1,0,"");
			MPI_Send(NULL,0,MPI_BYTE,0,FoundTag,cluster);
	//MPE_Log_event(2,0,"");
	//MPE_Log_event(9,0,"");
//MPE_Log_event(9,0,"");
			struct
			{
				float	cost_value;
				int		rank;
			} my_config, best_config;

			my_config.rank = me;

			if ( exch_m == BEST )
				my_config.cost_value = found ? cost : INFINITY;
			else if ( exch_m == FIRST || exch_m == RANDOM)
				my_config.cost_value = found ? me : INFINITY;
			else if (exch_m == MESSAGE)
			{
				my_config.cost_value = -1;
				my_config.rank = me;
			}
			else
				std::cout <<"n"<<myrank<<" unknown EXCHANGE_MODE "<<exch_m<<std::endl;


			MPI_Allreduce(&my_config,&best_config,1,MPI_FLOAT_INT,MPI_MINLOC,cluster);

			*root = best_config.rank;

//MPE_Log_event(10,0,"");


	//MPE_Log_event(3,0,"");
			MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if (flag )	// Falls der Master einen Isend abgeschickt hat, d.h. bevor mein Send ankam
			{
				if (status.MPI_TAG != FoundTag ) // es ist aber ein Signal von dem NAECHSTEN Found !!
				{ 
					std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG
						<<" expected FoundTag="<<FoundTag<<". Status : no error!\n";
				}
				else	// ist doch mein Signal
				{
	//MPE_Log_event(11,0,"");
					MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
	//MPE_Log_event(12,0,"");
				}
			}
			return ( 0 <= best_config.cost_value);
		}
		return false;		
	}	
	else
	/*MASTER*/
	{
	//MPE_Log_event(3,0,"");
		MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if ( flag || found )	// falls im Cluster gefunden wurde
		{
	FoundTag++;
			if(flag)
			{
	if (status.MPI_TAG != FoundTag )
	{ 
		std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG
			<<" expected FoundTag="<<FoundTag<<". Status: bad error, exiting!\n"<<std::flush;
			exit(1);
	}	
	//MPE_Log_event(11,0,"");
				MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
			}
			int i = 1;
			while ( i < nproc)
			{
	//MPE_Log_event(101,0,"");
					MPI_Isend(NULL,0,MPI_BYTE,i,FoundTag,cluster,&req);
	//MPE_Log_event(102,0,"");
	//MPE_Log_event(5,0,"");
					MPI_Request_free(&req);
	//MPE_Log_event(6,0,"");
		
				i++;
			}

//MPE_Log_event(9,0,"");
			struct
			{
				float	cost_value;
				int		rank;
			} my_config, best_config;

			my_config.rank = me;

			if ( exch_m == BEST )
				my_config.cost_value = found ? cost : INFINITY;
			else if ( exch_m == FIRST || exch_m == RANDOM)
				my_config.cost_value = found ? me : INFINITY;
			else if (exch_m == MESSAGE)
			{
				my_config.cost_value = -1;
				my_config.rank = me;
			}
			else
				std::cout <<"n"<<myrank<<" unknown EXCHANGE_MODE "<<exch_m<<std::endl;


			MPI_Allreduce(&my_config,&best_config,1,MPI_FLOAT_INT,MPI_MINLOC,cluster);

			*root = best_config.rank;

//MPE_Log_event(10,0,"");

// alle sonstigen Found-Meldungen  mit GLEICHEM FoundTag empfangen
			do{
	//MPE_Log_event(3,0,"");
					MPI_Iprobe(MPI_ANY_SOURCE,FoundTag,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
					if(flag)
					{
	//MPE_Log_event(11,0,"");
						MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
					}
			} while (flag);

			return ( 0 <= best_config.cost_value);
		}
		return false;
	}
}

bool SA_Synchronizer::ClusterSync(int found, float cost, EXCHANGE_MODE exch_m, int * root)
/* Vorgehensweise beim nichttrivialem Cluster:
MASTER:	Benutzt IProbe, um found bei Slaves festzustellen und ISend, um allen anderen Slaves found mitzuteilen
SLAVE: benutzt Send um found zu melden, und Iprobe, um found im Cluster zu erfahren

Im Unterschied zu ClusterSyncOld wird statt Allreduce Gather und Bcast benutzt

Bei jedem Aufruf der Funktion:
SLAVE: 
	1. Iprobe, ob Master einen Found meldet
		1.1	ja => Recv,
		1.2 Gather,Bcast
		1.3 return true;
	2. Falls lokal found -
		2.1 Send Found zum Master
		2.2 Gather,Bcast
		2.3 Iprobe, ob Master Found meldet (moeglich)
			2.3.1 ggf. Recv
		2.4 return true;
	3. return false;		
MASTER:
	1. Falls move_accepted ODER ein MPI_IProbe ein Message vom SLAVE meldet:
	  1.1 fuer alle i von 1 bis nproc:
			sende Nachricht zu i (non-block: Issend);		
	  1.2 Gather,Bcast
	  1.3 Alle Founds mit gleichem FoundTag empfangen
	  1.4 return true;
	2. return false;	
*/
{
	int flag=0;
	MPI_Status status;
	
	cost = found ? cost : (OptType == Opt::MIN ? INFINITY : -INFINITY);
	
	if ( me != 0) 
	/*SLAVE*/
	{	
//MPE_Log_event(3,0,"");
		MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
//MPE_Log_event(4,0,"");
		if (flag )	// Falls der Master einen Isend abgeschickt hat
		{
			FoundTag++;
			if (status.MPI_TAG < FoundTag )
			{ 
#ifdef SYNC_DEBUG
std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<". Status: late message, is not really possible !\n"<<std::flush;
//				exit(1);
#endif
				MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);	// late message empfangen
				FoundTag--;
				if ( !found )
					return 0;
				else
					goto found_late_1;	// please excuse me for using GOTO ... I am quite sure in a right
										// MPI-Implementation this case cannot be reached !
			}
			else
			{
//MPE_Log_event(11,0,"");
				MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
//MPE_Log_event(12,0,"");
//MPE_Log_event(9,0,"");
				MPI_Gather(&cost,1,MPI_FLOAT,NULL,1,MPI_FLOAT,0,cluster);
				MPI_Bcast(root,1,MPI_INT,0,cluster);
//MPE_Log_event(10,0,"");
//std::cout <<"n"<<myrank<<": Solution von "<<*root<<" choosen"<<std::endl;
			return ( 0 <= (*root));
			}
		}

found_late_1:

		if ( found)
		{
			FoundTag++;
	//MPE_Log_event(1,0,"");
			MPI_Send(NULL,0,MPI_BYTE,0,FoundTag,cluster);
	//MPE_Log_event(2,0,"");
	//MPE_Log_event(9,0,"");
//MPE_Log_event(9,0,"");
			MPI_Gather(&cost,1,MPI_FLOAT,NULL,1,MPI_FLOAT,0,cluster);
			MPI_Bcast(root,1,MPI_INT,0,cluster);

//MPE_Log_event(10,0,"");


	//MPE_Log_event(3,0,"");
			MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if (flag )	// Falls der Master einen Isend abgeschickt hat, d.h. bevor mein Send ankam
			{
				if (status.MPI_TAG != FoundTag ) // es ist aber ein Signal von dem NAECHSTEN Found !!
				{ 
#ifdef SYNC_DEBUG
					std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<". Status : no error!\n";
#endif
				}
				else	// ist doch mein Signal
				{
	//MPE_Log_event(11,0,"");
					MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
	//MPE_Log_event(12,0,"");
				}
			}

//std::cout <<"n"<<myrank<<": Solution von "<<*root<<" choosen"<<std::endl;
			return ( 0 <= (*root));
		}
		return false;		
	}	
	else
	/*MASTER*/
	{
#ifdef SYNC_FIX_BY_RTJ
//--------------------------------------------------RTJ, August 6, 2007
// The following section was copied from the end of this block.  Its
// purpose seems to be harvest any "found" claim messages left over
// from the last round of the competition.  Most of the time they are
// cleaned up at exit, but once in a while there is a delayed delivery.
// That used to cause an error exit, but there is no need for that.
// Here I just repeat the request for any left-over claims from the
// previous competition and discard them before starting another round.

// alle sonstigen Found-Meldungen  mit GLEICHEM FoundTag empfangen
	int recovered=0;
	do {
	//MPE_Log_event(3,0,"");
		MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if (flag && status.MPI_TAG <= FoundTag)
		{
	//MPE_Log_event(11,0,"");
			MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,
                                 status.MPI_TAG,cluster,&status);
	//MPE_Log_event(12,0,"");
			recovered++;
		}
	} while (flag && status.MPI_TAG <= FoundTag);
	if (recovered) std::cout << "recovered: " << recovered << std::endl;
#else
	//MPE_Log_event(3,0,"");
		MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
#endif
		if ( flag || found )	// falls im Cluster gefunden wurde
		{
			FoundTag++;
			if(flag)
			{
	if (status.MPI_TAG != FoundTag )
	{ 
		std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG
			<<" expected FoundTag="<<FoundTag<<". Status: bad error, exiting!\n"<<std::flush;
		std::cout << "Iprobe returned flag " << flag
          		  << ", status.MPI_SOURCE,MPI_TAG,MPI_ERROR "
          		  << status.MPI_SOURCE << ","
          		  << status.MPI_TAG << ","
          		  << status.MPI_ERROR
          		  << std::endl;
		exit(1);
	}	
	//MPE_Log_event(11,0,"");
				MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
			}
			int i = 1;
			while ( i < nproc)
			{
	//MPE_Log_event(101,0,"");
					MPI_Isend(NULL,0,MPI_BYTE,i,FoundTag,cluster,&req);
	//MPE_Log_event(102,0,"");
	//MPE_Log_event(5,0,"");
					MPI_Request_free(&req);
	//MPE_Log_event(6,0,"");
		
				i++;
			}

//MPE_Log_event(9,0,"");
			MPI_Gather(&cost,1,MPI_FLOAT,costs,1,MPI_FLOAT,0,cluster);

			if (exch_m == MESSAGE)
			{
				*root = -1;
			}
			else
			{
				*root = GetWinner(exch_m);
			}

			MPI_Bcast(root,1,MPI_INT,0,cluster);
//MPE_Log_event(10,0,"");

// alle sonstigen Found-Meldungen  mit GLEICHEM FoundTag empfangen
			do{
	//MPE_Log_event(3,0,"");
					MPI_Iprobe(MPI_ANY_SOURCE,FoundTag,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
					if(flag)
					{
	//MPE_Log_event(11,0,"");
						MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
					}
			} while (flag);

//std::cout <<"n"<<myrank<<": Solution von "<<*root<<" choosen"<<std::endl;
			return ( 0 <= (*root));
		}
		return false;
	}
}

/* Entspricht genau dem EXCHANGE_MODE FIRST*/
bool SA_Synchronizer::ClusterSyncFirst(int found, float cost, EXCHANGE_MODE exch_m, int * root)
/* Vorgehensweise beim nichttrivialem Cluster:
MASTER:	Benutzt IProbe, um found bei Slaves festzustellen und ISend, um allen anderen Slaves found mitzuteilen
SLAVE: benutzt Send um found zu melden, und Iprobe, um found im Cluster zu erfahren

Im Unterschied zu ClusterSync wird kein Gather verwendet 

Bei jedem Aufruf der Funktion:
SLAVE: 
	1. Iprobe, ob Master einen Found meldet
		1.1	ja => Recv,
		1.2 Bcast
		1.3 return true;
	2. Falls lokal found -
		2.1 Isend Found zum Master
		2.2 Bcast
		2.3 Iprobe, ob Master Found meldet (moeglich)
			2.3.1 ggf. Recv
		2.4 return true;
	3. return false;		
MASTER:
	1. Falls move_accepted ODER ein MPI_IProbe ein Message vom SLAVE meldet:
	  1.1 fuer alle i von 1 bis nproc:
			sende Nachricht zu i (non-block: Issend);		
	  1.2 Bcast
	  1.3 Alle Founds mit gleichem FoundTag empfangen
	  1.4 return true;
	2. return false;	
*/
{
	int flag=0;
	MPI_Status status;
	
	cost = found ? cost : (OptType == Opt::MIN ? INFINITY : -INFINITY);
	
	if ( me != 0) 
	/*SLAVE*/
	{	
//MPE_Log_event(3,0,"");
		MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
//MPE_Log_event(4,0,"");
		if (flag )	// Falls der Master einen Isend abgeschickt hat
		{
			FoundTag++;
			if (status.MPI_TAG < FoundTag )
			{ 
#ifdef SYNC_DEBUG
std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<". Status: late message, is not really possible !\n"<<std::flush;
//				exit(1);
#endif
				MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);	// late message empfangen
				FoundTag--;
				if ( !found )
					return 0;
				else
					goto found_late;	// please excuse me for using GOTO ... I am quite sure in a right
										// MPI-Implementation this case cannot be reached !
			}
			else
			{
//MPE_Log_event(11,0,"");
				MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
//MPE_Log_event(12,0,"");
//MPE_Log_event(9,0,"");
			//	MPI_Gather(&cost,1,MPI_FLOAT,NULL,1,MPI_FLOAT,0,cluster);
				MPI_Bcast(root,1,MPI_INT,0,cluster);
//MPE_Log_event(10,0,"");
//std::cout <<"n"<<myrank<<": Solution von "<<*root<<" choosen"<<std::endl;
			return ( 0 <= (*root));
			}
		}
		
found_late:

		if ( found)
		{
			FoundTag++;
	//MPE_Log_event(1,0,"");
			MPI_Isend(NULL,0,MPI_BYTE,0,FoundTag,cluster,&req);
			MPI_Request_free(&req);
	//MPE_Log_event(2,0,"");
	//MPE_Log_event(9,0,"");
//MPE_Log_event(9,0,"");
//			MPI_Gather(&cost,1,MPI_FLOAT,NULL,1,MPI_FLOAT,0,cluster);
			MPI_Bcast(root,1,MPI_INT,0,cluster);

//MPE_Log_event(10,0,"");


	//MPE_Log_event(3,0,"");
			MPI_Iprobe(0,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if (flag )	// Falls der Master einen Isend abgeschickt hat, d.h. bevor mein Send ankam
			{
				if (status.MPI_TAG != FoundTag ) // es ist aber ein Signal von dem NAECHSTEN Found !!
				{ 
#ifdef SYNC_DEBUG
std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG<<" expected FoundTag="<<FoundTag<<". Status : no error!\n";
#endif
				}
				else	// ist doch mein Signal
				{
	//MPE_Log_event(11,0,"");
					MPI_Recv(NULL,0,MPI_BYTE,0,status.MPI_TAG,cluster,&status);
	//MPE_Log_event(12,0,"");
				}
			}

//std::cout <<"n"<<myrank<<": Solution von "<<*root<<" choosen"<<std::endl;
			return ( 0 <= (*root));
		}
		return false;		
	}	
	else
	/*MASTER*/
	{		
	//MPE_Log_event(3,0,"");
		MPI_Iprobe(MPI_ANY_SOURCE,MPI_ANY_TAG,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
		if ( flag || found )	// falls im Cluster gefunden wurde
		{
			FoundTag++;
			if(flag)
			{
				if (status.MPI_TAG == FoundTag )
				{ 
					*root = status.MPI_SOURCE;	// FIRST-Mode !	
				
					//MPE_Log_event(11,0,"");
					MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,FoundTag,cluster,&status);
					//MPE_Log_event(12,0,"");
				}
				else
				{
#ifdef SYNC_DEBUG
std::cout<<"n"<<myrank<<" message received with tag="<<status.MPI_TAG <<" expected FoundTag="<<FoundTag<<". Status: no error.\n"<<std::flush;
#endif
					MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,status.MPI_TAG,cluster,&status);
					if(found)
						*root=0;
					else
					{
						FoundTag--;
						return false;
					}
				}
			}
			else
			{
				*root = 0;	// local Found
			}
			int i = 1;
			while ( i < nproc)
			{
	//MPE_Log_event(101,0,"");
					MPI_Isend(NULL,0,MPI_BYTE,i,FoundTag,cluster,&req);
	//MPE_Log_event(102,0,"");
	//MPE_Log_event(5,0,"");
					MPI_Request_free(&req);
	//MPE_Log_event(6,0,"");
		
				i++;
			}

//MPE_Log_event(9,0,"");
	//		MPI_Gather(&cost,1,MPI_FLOAT,costs,1,MPI_FLOAT,0,cluster);

			if (exch_m == MESSAGE)
			{
				*root = -1;
			}

			MPI_Bcast(root,1,MPI_INT,0,cluster);
//MPE_Log_event(10,0,"");

// alle sonstigen Found-Meldungen  mit GLEICHEM FoundTag empfangen
			do{
	//MPE_Log_event(3,0,"");
					MPI_Iprobe(MPI_ANY_SOURCE,FoundTag,cluster,&flag,&status);
	//MPE_Log_event(4,0,"");
					if(flag)
					{
	//MPE_Log_event(11,0,"");
						MPI_Recv(NULL,0,MPI_BYTE,status.MPI_SOURCE,FoundTag,cluster,&status);
	//MPE_Log_event(12,0,"");
					}
			} while (flag);

//std::cout <<"n"<<myrank<<": Solution von "<<*root<<" choosen"<<std::endl;
			return ( 0 <= (*root));
		}
		else
			return false;
	}
}


void TestIprobe(void)
{
	MPI_Request req;
	MPI_Status stat;
	int flag = 0,i=0;
	float cost = 2.0;
//	MPI_Barrier(MPI_COMM_WORLD);
	if (myrank == 0)
	{
//		MPI_Issend(NULL,0,MPI_BYTE,1,17,MPI_COMM_WORLD,&req);
//		do {
//			MPI_Test(&req,&flag,&stat); 
//			i++;
//		} while ( !flag);
//		std::cout <<"At Master: after "<<i<<" tests completed!\n";
		if( MPI_Ssend(&cost,1,MPI_FLOAT,1,17,MPI_COMM_WORLD) == MPI_SUCCESS)
			std::cout <<"At Master: completed!\n";
	}
	else if (myrank == 1)
	{
		do{
			MPI_Iprobe(MPI_ANY_SOURCE,17,MPI_COMM_WORLD,&flag,&stat);
			i++;
		} while ( !flag);
		std::cout <<"At Slave : after "<<i<<" Iprobs Recv gets "<<MPI_Recv(&cost,1,MPI_FLOAT,0,17,MPI_COMM_WORLD,&stat)<<std::endl;
//		std::cout <<"At Slave : after "<<i<<" Iprobs gets TRUE\n"; 

	}
}

#ifdef SHOW_NFOUND
void SA_Synchronizer::ShowNfoundRatio(void)
{
	if ( me != 0)
		return;
	if(nproc ==1 )
	{
		NfoundSum = Nfoundi = 1;
	}		
	std::cout <<"n"<<myrank<<" nproc "<<nproc<<" average nfound/nproc "<<NfoundSum*1.0/(1.0*Nfoundi*nproc)<<std::endl;
	NfoundSum = Nfoundi = 0;
}
#endif
#endif