#ifndef _SA_ClusteringSolver_h_ #define _SA_ClusteringSolver_h_ //#include //#include #include #include //#include //#include #include "SA_ParSolver.h" #include "util_salib.h" #include "SA_Synchronizer.h" #include "SA_ParScheduler.h" enum SYNC_MODE {NOSYNC=0, SYNC, GROUP = SYNC, ASYNC}; class SA_ClusteringSolver : public SA_ParSolver { private: SA_Output saclustsolvoutput; // always change, when corresponding variables are changed char choosemovestr[9]; char commincluststr[6]; char commmodestr[9]; char globalequistr[7]; char clusteringstr[30]; char distribstr[8]; char constmovesizestr[4]; protected: char processor_name[MPI_MAX_PROCESSOR_NAME]; int ncluster, // Anzahl der Clusterebenen maxcluster, // maximale Clusterebene, die benutzt werden darf; darf nur per SetMaxCluster gesetzt werden ! nproc[MAXGROUPS], // Anzahl der Prozessoren im jew. Cluster me[MAXGROUPS], // meine Nummer im jew. Cluster actual_cluster; // Der Solver befindet sich im Moment in diesem Cluster MPI_Comm cluster[MAXGROUPS], // masters[MAXGROUPS], // in masters[i] steht genau bei allen Prozessoren, die in i-tem // Cluster MASTER oder CHIEF sind, der communicator, der // alle MASTER und den CHIEF enthaelt; // auf SLAVE-Prozessoren steht dort communicator mit allen SLAVES, // aber dies wird z.Z. nicht gebraucht :) // Oben gesagte bezieht sich auf den Fall maxcluster == ncluster; // bei kleineren maxcluster gilt : masters vereinigen nur Prozessoren // innerhalb des gr"ossten cluster cluster[maxcluster]. chiefs; // Hier sind alle CHIEFS vereinigt ( bei maxcluster == ncluster ex. genau einer mit myrank ==0). MPI_Group // f"ur DistributeSolutionAfterSubchain * masters_group, // auf einem CHIEF-Prozessor steht hier ein Array der den masters-Communikatoren entspr. Groups cluster_group; // auf einem CHIEF-Prozessor steht hier Gruppe, die dem cluster[maxcluster]-Communikator entspricht. SA_Synchronizer sync[MAXGROUPS], end_chain[MAXGROUPS]; // nur auf MASTER und CHIEF-Prozessoren zur Equilibrium-Bestimmung SYNC_MODE GlobalEquilibrium; // wird das equilibrium in jedem Cluster einzeln entschieden (NOSYNC) oder // asynchron vom CHIEF mitgeteilt (ASYNC) double MinEff, // legt fest, wann geclustert wird time_trans, // mean time for (GetNeighbor,GetCost) time_reset, // mean time for (ResetSolution) time_update, // mean time for (UpdateSolution) mes_comm_time[2], // actual measured times for the communication comm_times[2][MAXGROUPS]; // [0][0..ncluster] stehen die mittleren Zeiten fuer Ueberpruefung der globalen Akzeptanz falls nicht gefunden // [1][0..ncluster] stehen die mittleren Zeiten fuer Austauschen der Loesungen(oder Moves) falls gefunden SA_Move * move; // Der gefundene Uebergang SA_Solution * StateBuffer; // Buffer, um eine L"osung zwischenzuspeichern ( bei MeasureCommTimes) int ConstantSizeMove; // Falls Benutzer garantiert, dass das OutputMove stets // gleiche Anzahl der Zeichen benutzt, // wird diese Anzahl hier gespeichert; andernfalls 0. void SetMoveSize(void); // hier ggf. ConstantSizeMove setzen COMM_MODE CommunicationMode; // Wie "Ubermittlung der L"osungen waehrend der Kettenberechnung erfolgen soll EXCHANGE_MODE ChooseMove; // how to choose ONE move from several found in cluster int (SA_ClusteringSolver::*CommunicateInCluster_fp) (int , EXCHANGE_MODE, COMM_MODE , int &); // Prueft, ob im Cluster ein Uebergang gefunden wurde; ggf diesen austauschen // gleichzeitig kann in MESSAGE-mode equilibrium von MASTER allen Slaves mitgeteilt werden int CommunicateInCluster(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE c_m, int & equilibrium); int CommunicateInClusterOld(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE c_m, int & equilibrium); int CommunicateInClusterAsync(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE c_m, int & equilibrium); int CommunicateInClusterAsyncFirst(int move_accepted, EXCHANGE_MODE exch_m, COMM_MODE comm_m, int & equilibrium); // Austauschfunktion fuer alle CommunicateInCluster // liefert 0 falls Fehler waehrend des Austauschs int ExchangeState(int moved, int root,COMM_MODE comm_m); // Flag und Funktionen fuer Bestimmung der ersten Loesung in Subchain EXCHANGE_MODE DoDistrSolAfterSubchain; // ob alle Teilketten mit gleicher Loesung anfangen sollen und wie diese zu bestimmen ist void DistributeSolutionAfterSubchain(void); void DistributeSolutionAfterClustering(void); // Lohnt es sich, Clustergroesse zu verdoppeln int DoClustering(); // Zeit bis zu einem erfolgten Uebergang im Cluster des Levels clst bei geg. Erwartungswert in diesem Cluster absch"atzen double EstimateT(int clstr,double e_clstr); double EstimateDilation(int clstr,double e_one,double e_clstr); bool BetterEffSp(int clstr,double e_single,double e_first, double e_second); void DefineCluster(void); // Unterteilung der Prozessoren in Cluster bestimmen void DefineMasters(void); // Masters-Unterteilung in Anh"angigkeit von maxcluster bestimmen void SetMaxCluster(int mc); // maximal zu benutzende Clusterebene setzen; WICHTIG : dabei wird Masters-Unterteilung neu bestimmt ! void MeasureCommTimes(int start_cluster,int end_cluster); // Zeiten fuer Austausch der Loesungen messen // gibt das Verhaeltnis BroadcastState/ComputePerturbation fuer alle Clustergroessen aus void OutputLambdas(int procnr=0); public: SA_ClusteringSolver(int *argc, char ***argv, SA_Problem&); ~SA_ClusteringSolver(); SA_Output *GetSolverOutput(); int ReadConfig(std::istream &); void ShowConfig(void); virtual float RunAnnealing(void); // Den gewaehlten SA-Algo ausfuehren float ClusteredAnn(); // Der Clustered-Annealing Algorithmus float ComputeLoopFactor(); // Fuer geg. Problem den benoetigten subchainfactor bestimmen int TestProblemImplementation(); // virtual void CreateLog(std::ostream & output, MPI_Comm comm = MPI_COMM_SELF); //Ausgabe der Durchlaufdaten in die Log-Datei // Funktionen fuer den Austausch von Loesungen und Schritten; rufen eigen oder probleminterne Bcast-Fkt. auf enum IMPL {I,PROBLEM}; IMPL BcastFkt; // Wer implementiert die Bcast-Funktionen int BcastSolution(SA_Solution &sol, int root, MPI_Comm comm, int me_comm); int BcastApplyMove(SA_Solution &sol, int root, MPI_Comm comm, int me_comm); // Standardfunktionen fuer Austausch von Loesungen und Schritten // Die Loesung vom Prozessor root in der Gruppe comm verteilen int BcastSolution_my(SA_Solution &sol, int root, MPI_Comm comm, int me_comm); // Unter Voraussetzung, dass alle Loesungen im comm aus einer Loesung // mittels hoechstens eines Schrittes entstanden sind, // und zwar ist Anzahl der Schritte in moved angegeben, // bringe alle Loesungen auf den gleichen Stand: int BcastApplyMove_my(SA_Solution &sol, int root, MPI_Comm comm, int me_comm); // Gibt ein Abschaetzung aus, bei welcher Akzeptanzrate jeweils Clustering erfolgt, // in Abhaengigkeit von time_accept, time_reset und comm_times // Nur auf Proc0 sinnvoll ! // nicht mehr sinnvoll void EstimateClusteringPoints(); private: // Testausgabe der Cluster-Zusammensetzung void ShowClusters(void); void ShowCluster(int act_cl, bool all=false); //Testen float Test(); }; #endif