algorithms/SMesh2BalancedParallel.h Source File

00001 /* #start# ***********************************************************
00002 
00003            Scheduling Simulator
00004         Lehrstuhl f"ur Effiziente Algorithmen
00005            Technische Universit"at M"unchen
00006 
00007  File    : $Id: SMesh2BalancedParallel.h,v 1.3 2003/01/08 18:57:11 meierb Exp $
00008 
00009  Purpose : Dynamic scheduling on a two-dimensional mesh topology
00010            without dependencies. All release times are zero.
00011            All resource requirements of the jobs are known
00012      (but processing times are not known in advance).
00013      Competitive ratio: O(sqrt(log(log N)))
00014      [A.Feldmann / J.Sgall / S.-H.Teng:
00015       "Dynamic scheduling on parallel machines", p.16-28]
00016 
00017  RCS-Log:
00018  $Log: SMesh2BalancedParallel.h,v $
00019  Revision 1.3  2003/01/08 18:57:11  meierb
00020  added randomized release times
00021 
00022  Revision 1.1.1.1  2002/12/02 22:26:19  meierb
00023  my_schedule
00024 
00025  Revision 1.1  2002/08/29 12:59:58  taeubig
00026  Added the sources
00027 
00028  Revision 1.3  2000/07/05 21:51:38  mayerh
00029  added method getLeaBibEntry and made some changes
00030 
00031  Revision 1.2  2000/07/02 23:23:20  taeubig
00032  Completely revised version of BALANCED PARALLEL algorithm
00033 
00034  Revision 1.1  2000/06/26 11:06:12  taeubig
00035  Added BALANCED PARALLEL algorithm for two-dimensional meshes
00036  (without dependencies)
00037 
00038 
00039  * #end# ************************************************************* */
00040 
00041 #ifndef SMESH2BALANCEDPARALLEL_H
00042 #define SMESH2BALANCEDPARALLEL_H
00043 
00044 // system header files
00045 
00046 // project header files
00047 #include "SSchedAlgorithm.h"
00048 
00049 class SMesh2BalancedParallel : public SSchedAlgorithm {
00050  public:
00051   SMesh2BalancedParallel():
00052     _smallJobs(NULL), 
00053     _middleJobs(NULL), 
00054     _largeJobs(NULL),
00055     _classToSubmesh(-1)
00056     {};
00057   virtual ~SMesh2BalancedParallel() {};
00058   virtual void startup();
00059   virtual double innerLoop(const leda_list<STSysSchedEvent>& rEvents);
00060   virtual const leda_string getDescription() const;
00061   virtual const leda_string &getName() const;
00062   virtual const SClassification &getClassification() const;
00063   virtual SLeaBibEntry &getLeaBibEntry() const;
00064 
00065  private:
00066   leda_d_array<int, leda_set<SJob*>* >
00067     _smallJobs, _middleJobs, _largeJobs;
00068   int _phase, _i;
00069   int _runningClass;
00070   bool _wait;
00071   bool _classesAssigned;
00072   leda_d_array<int, int> _classToSubmesh;
00073   int _parts;
00074 
00075   leda_array<bool> _subWait;
00076   leda_array<bool> _subClassesAssigned;
00077   leda_array<leda_d_array<int, int> > _classToSubsubmesh;
00078   leda_array<int> _subParts;
00079   int _k;
00080   
00081 };
00082 
00083 #endif //SMESH2BALANCEDPARALLEL_H