Browse Prior Art Database

Processor Allocation for the Hyperplane Multiprocessor Topology

IP.com Disclosure Number: IPCOM000126512D
Original Publication Date: 2005-Jul-22
Included in the Prior Art Database: 2005-Jul-22
Document File: 9 page(s) / 65K

Publishing Venue

IBM

Abstract

Processor allocation is a system function in multiprocessors used to manage processor assignment when multiple tasks are running in the system. Processor allocation is sometimes referred to as multiprocessor partitioning or space sharing, depending of the context on which the term is used, but it always has the goal of realizing high processor utilization and low latency of execution. A multiprocessor topology that has received a lot of attention is the hypercube, and that topology is used as the benchmark from which to assess the performance results from processor allocation.

This text was extracted from a PDF file.
At least one non-text object (such as an image or picture) has been suppressed.
This is the abbreviated version, containing approximately 48% of the total text.

Page 1 of 9

Processor Allocation for the Hyperplane Multiprocessor Topology

     Processor allocation for hypercube multiprocessor topologies have the inherent problem that allocation algorithms have difficulty recognizing subcubes and once the resource is freed, it is difficult to recombine the subcube into the original structure. The problem is the many combinations of subcubes, a recognition algorithm for a large-scale multiprocessor can become very complex. Incomplete recognition results in subcubes going unallocated, with internal fragmentation and low utilization of the processors. One well known algorithm is the buddy system. That algorithm, for example, can achieve complete recognition but will experience high complexity. There is a clear need to have a processor scheduling method that has good recognition capability and low implementation complexity.

     Rather than put a lot of effort into the development of new and better algorithms, it is possible to approach the problem in two fronts. First, the hypercube topology is transformed into a topology that is more flexible to work with, and second, an algorithm is developed that blends well with that topology. Two views of the hyperplane topology are illustrated in Figure 1 below. An example of a 4-dimensional hypercube with 16 nodes is used (see Figure 3). It is possible to do a transformation from the hypercube topology to a tree topology, then do another transformation from the tree topology to the hyperplane topology. The 16 node hypercube has 8 possible 3-dimensional subcubes that can be allocated in pairs:
a) pair 1: {0, 1, 2, 3, 4, 5, 6, 7} and {8, 9, 10, 11, 12, 13, 14, 15},
b) pair 2: {0, 1, 2, 3, 8, 9, 10, 11} and {4, 5, 6, 7, 12, 13, 14, 15},
c) pair 3: {0, 1, 4, 5, 8, 9, 12, 13} and {2, 3, 6, 7, 10, 11, 14, 15},
d) pair 4: {0, 2, 4, 6, 8, 10, 12, 14} and {1, 3, 5, 7, 9, 11, 13, 15}.

     It difficult to recognize the desired subcubes in a mechanical way (or by simple inspection for that matter). We decided to do the transformation for a single pair of subcubes of the hypercube, then to demonstrate that in terms of the cost of traversing the diameter of both graphs is the same. For example, in Figure 3, there are 4 hops to traverse the diameter of that graph in both cases. The scheduling algorithm for the hyperplane only needs to recognize the fact that there are 4 processors per 1st-level router, and 16 processors per 2nd-level router.

1

Page 2 of 9

P

   P P

   P P

P P

P

P P

P

P

P

P

P

P

(a) 3D View of Nodes, Links (b ) 3D V iew o f P la n e s

Figure 1

Figure 2 shows the ID numbers used to represent the various levels of the hyperplanes. The 2-bit numbers "zz" represent the lowest level links where one router (the ROOT) connects four links. The 4-bit binary numbers "zz.xx" are representative of the second level links and the 6-bit binary numbers "zz.xx.yy" are representative of the processor nodes (the leaves of the graph).

2

[This page contains 2 pictures or other non-text objects]

Page 3 of 9

101...