Ein deterministisches Job-Scheduling-Verfahren fuer massiv-parallele Systeme am Beispiel Cray T3E

This thesis presents a deterministic job-scheduling procedure, which optimizes job-execution sequences on massively parallel computing systems and describes the development of a job scheduler based on this procedure for a CRAY T3E running under UNICOS/mk and NQS. Known scheduling strategies usually determine exactly one job to be executed next according to criteria like job size or estimated job runtime and, if occasion arises, using the current system allocation. The procedure proposed here chooses a complete scheduling sequence out of all possible sequences of the waiting jobs. Scheduling sequences are calculated based on user-estimated job runtimes and compared by applying a rating function. This rating function allows the simultaneous integration of more than one optimization criterion like system utilization, job-waiting periods and adherence to additional usage conditions, like job priorities or contingent limitations. A weighted sum of the single criteria also enables a flexible control over the compromise at runtime. The questions arising with this approach are discussed in detail in this thesis. This is especially the introduction of a combinatorial optimization of the search process for the best scheduling sequence, since the number of possible sequences grows with the factorial of the number of waiting jobs. Genetic algorithms and mutation-selection procedures are discussed and evaluated. Besides the estimation of job runtimes, which can only be mentioned in brevity, the selection of an appropriate rating function and the problem of job defragmentation on the CRAY T3E target system are dealt with. The final implementation of a job scheduler for a CRAY T3E system shows the practicability of the discussed approach, validated by exemplary scheduling situations. The main advantage can be seen in the possibility for a flexible conjunction of several optimization targets while using a real optimum search. (orig.)Available from TIB Hannover: RA 831(3604) / FIZ - Fachinformationszzentrum Karlsruhe / TIB - Technische InformationsbibliothekSIGLEDEGerman