Processor Allocation Algorithms

Allocating subtori in a multi-dimensional torus is a challenging problem that has not received much research attention. Here, we present an overview of our processor allocation algorithm design, which is also the main contribution of this work. The first step is preprocessing, done only once and before any scheduling starts. Recall that the multicomputer system we assume in our problem model is a torus with all-but-one dimension sizes to be powers of two. That is, let the torus of dimension d be 2n1×2n2×· · ·×2nd−1×2nd ·p, where p ≥ 1 is odd. When p = 1, all dimension sizes are powers of two. (Note that when we describe a torus in this paper, we do not care about the orientation of dimensions, e.g., a × b is the same as b × a.) The preprocessing step partitions the original torus into a set of semitori with all dimension sizes to be powers of two, where a semitorus is similar to a torus except that some of the wrap-around edges may be missing. Note that any torus or mesh is a semitorus. For example, if the original torus is 2×2×2×6×8, then the fourth dimension of size 6 can be written as 6=2 · 3=2 ·(2 + 1), where the odd factor is expressed as a sum of powers of two based on the odd factor’s binary representation. Therefore, this torus can be partitioned into two semitori, 2 × 2 × 2 × 4 × 8 (with one wrap-around edge missing in the fourth dimension) and 2 × 2 × 2 × 2 × 8. We name the set of obtained semitori as the initial available set. When a job chosen by a job scheduling algorithm (FCFS or backfilling) is being considered, its requested number of processors will first be converted to the next nearest power of two since this condition usually makes processor allocation less tedious and users usually do not mind receiving more processors than they need. Assume the input contains (1) the number of processors m = 2k requested by the job being considered currently and (2) the set of currently available semitori, A, which is initialized by the preprocessing step and maintained dynamically throughout the schedule. Our allocation algorithms then follow the following three steps. • Semitorus identification: Identify a semitorus S ∈ A that has at least as many nodes as m and remove S from A. If no such semitorus exists, the job cannot be scheduled now. If such a semitorus S exists, let S be 2k1 ×···× 2kh . If h i=1 ki = k, assign S to R and go to the torus conversion step. If h i=1 ki > k, go to the semitorus partition step. • Semitorus partition: (1) Partition scheme: Partition S into semitori, one of which has m nodes and (2) Assign the semitorus with m nodes to R and add the remaining semitori in the partition to A. • Conversion to torus: Combine (collapse) all dimensions with missing wrap-around edges in R to get a torus T that will be allocated to the job. Two partition schemes are used in the partition step, resulting in two processor allocation algorithms: allocating with equal partition and allocating with non-equal partition. We will discuss these schemes in details in the next section. In the conversion step, a semitorus R with the desired number of nodes m is to be reconfigured into a torus with the same number of nodes by reducing the number of dimensions. One approach is to take all the dimensions in R with missing wrap-around edges and replace them with one dimension. For example, a semitorus 22 × 23 × 2 × 22 with the first two dimensions missing wrap-around edges can be converted to a torus 25 × 2 × 22, where the 22 × 23 mesh formed in the first and second dimensions in the semitorus is made to be a ring of 25 nodes. This approach has the advantage to produce a torus with more dimensions. Another approach is to pair a dimension that misses a wrap-around edge with a dimension with no edge missing and replace them with one dimension. For example, the same semitorus 22 × 23 × 2 × 22 can be converted to a torus 24 × 24, where the first and fourth dimensions are paired and the second and third dimensions are paired. This approach has the advantage to produce a more cube-like torus. See Figure 1 for an example of the torus conversion step, in which a 2-Dsemitorus with missing wrap-around edges in both dimensions is converted to a 1-D torus (ring).

[gallery ids="7705"]

Comparing to processor allocation, deallocation is relatively easier, which is done every time a job finishes execution. In the allocation algorithms, we need to keep a record of the chosen semitorus S in the identification step and its children (these children are siblings to each other) which are obtained in the partition step. When a job return its torus to the available set A, the deallocation algorithm checks to see if all its siblings are in A. If so all siblings together with the returned torus are replaced by their parent S, which is put back to A.