Decentralized scheduling algorithms of geographically-distributedcomputer systems

Locally optimal algorithm and algorithms based on job migration, job replication and bothmigration and replication of decentralized scheduling of parallel programs in geographicallydistributedcomputer systems are proposed in this paper. Software of parallel jobs decentralizedscheduling is considered. Job migration and job replication are indented to help to consider dynamicallychanged structure and resource workload. Computational complexity of proposed algorithmsdoesnt depend on number of subsystems, because the search implements within theschedulers local neighborhood. This provides algorithms applicability in large-scale geographically-distributed CS.Algorithms have been realized and included into GBroker software suite of parallel programsdecentralized scheduling in geographically-distributed multicluster and GRID-systems. Modelingof developed algorithms and software tools on the active multicluster system has shown high effectivenessof job migration. Investigation of local neighborhood structures has shown that theusing of non-fully connected structures of small (mean) diameter doesnt result in significant decreaseof the system performance. An experimental comparison of developed packet GBrokerwith centralized scheduler GridWay has shown that mean service time of job flows with centralizedand decentralized scheduling is comparable. Using of the algorithm with migration has allowedto exceed the bandwidth of this centralized scheduling system.

Keywords

Authors

References