Job preemption, fast subcube compaction, or waiting in hypercube systems? A selection methodology

摘要

For a hypercube environment, this paper proposes a decision making method that tries to answer the following question: when a fully specified job arrives into a hypercube system and does not find an available free subcube that fulfills its execution requirements, what action to take: (1) Preempt one of the running jobs, use its allocated subcube and resume it later. (2) Do fast compaction for one of the allocated subcubes (using all disjoint paths method [IEEE Trans. Parallel Dist. Syst. 9 (1) (1998) 50]) to utilize a coalesced subcube area and run in it. (3) Wait till one of the running jobs terminates and leaves the system. An algorithm of complexity O(N~2m log(N)) is given to illustrate the selection methodology of a candidate job and the corresponding action, where N is the maximum number of jobs running in the hypercube system, and m is the maximum number of processing segments defined along one execution window. The action that causes a maximum time gain (maximum remaining laxities) is chosen. The selection approach enhances the preemption concept and can be incorporated into a job allocator for a hypercube system. Illustrative case studies are given to illustrate its applicability.