A comparative study of job allocation and migration in the pancake network. (English) Zbl 1116.68019
Summary: Pancake networks are an attractive class of Cayley graphs functioning as a viable interconnection scheme for large multi-processor systems. The hierarchy of the pancake graph allows the assignment of its special subgraphs, which have the same topological features as the original graph, to a sequence of incoming jobs. We investigate the hierarchical structure of the pancake network and derive a job allocation scheme for assigning processors to incoming jobs. An algorithm is presented for job migration. Finally, we compare the assignment scheme to those derived previously for the star network and address the shortcomings of the pancake network.
MSC:
| 68M20 | Performance evaluation, queueing, and scheduling in the context of computer systems |
| 68M10 | Network design and communication in computer systems |
| 68R10 | Graph theory (including graph drawing) in computer science |
| 68W10 | Parallel algorithms in computer science |
References:
| [1] | S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, in: Proc. Int. Conf. Parallel Processing, 1986, pp. 216-223.; S.B. Akers, B. Krishnamurthy, A group-theoretic model for symmetric interconnection networks, in: Proc. Int. Conf. Parallel Processing, 1986, pp. 216-223. |
| [2] | S.G. Akl, K. Qiu, Data communication and computational geometry on the star and pancake interconnection networks, in: Proc. Third IEEE Sym. on Parallel and Distributed Processing, 1991, pp. 415-422.; S.G. Akl, K. Qiu, Data communication and computational geometry on the star and pancake interconnection networks, in: Proc. Third IEEE Sym. on Parallel and Distributed Processing, 1991, pp. 415-422. |
| [3] | P. Berthome, A. Ferreira, S. Perennes, Optimal information dissemination in star and pancake networks, in: Proc. Fifth IEEE Sym. on Parallel and Distributed Processing, 1993, pp. 720-723.; P. Berthome, A. Ferreira, S. Perennes, Optimal information dissemination in star and pancake networks, in: Proc. Fifth IEEE Sym. on Parallel and Distributed Processing, 1993, pp. 720-723. |
| [4] | Chen, M. S.; Shin, K. G., Processor allocation in an \(n\)-cube multiprocessor using Gray codes, IEEE Transaction on Computers, C-36, 12, 1396-1407 (1987) |
| [5] | L. Gardner, Z. Miller, D. Pritikin, I.H. Sudborough, Embedding hypercubes into pancake, cycle prefix, and substring reversal networks, in: Proc. of Hawaii Int. Conf. on System Sciences, 1995, pp. 537-545.; L. Gardner, Z. Miller, D. Pritikin, I.H. Sudborough, Embedding hypercubes into pancake, cycle prefix, and substring reversal networks, in: Proc. of Hawaii Int. Conf. on System Sciences, 1995, pp. 537-545. |
| [6] | Chun-Nan Hung, Kao-Yung Liang, Lih-Hsing Hsu, Embedding Hamiltonian paths and Hamiltonian cycles in faulty pancake graphs, in: Proc. ISPAN, 2002, pp. 157-162.; Chun-Nan Hung, Kao-Yung Liang, Lih-Hsing Hsu, Embedding Hamiltonian paths and Hamiltonian cycles in faulty pancake graphs, in: Proc. ISPAN, 2002, pp. 157-162. |
| [7] | Navid Imani, Hamid Sarbazi-Azad, S.G. Akl, On some combinatorial properties of star graph ISPAN 2005, in: Proc. 8th Int. Symposium on Parallel Architectures, Algorithms and Networks, 2005, pp. 58-65.; Navid Imani, Hamid Sarbazi-Azad, S.G. Akl, On some combinatorial properties of star graph ISPAN 2005, in: Proc. 8th Int. Symposium on Parallel Architectures, Algorithms and Networks, 2005, pp. 58-65. · Zbl 1205.68038 |
| [8] | Latifi, S., Task allocation in the star graph, IEEE Transactions on Parallel and Distributed Systems, 5, 1220-1224 (1994) |
| [9] | Li, T. K.; Tan, J. M.; Hsu, L., Hyper Hamiltonian laceablility on edge fault star graph, Information Sciences, 165, 1-2, 59-71 (2004) · Zbl 1057.05054 |
| [10] | Qiu, K., Broadcasting on the star and pancake interconnection networks, Parallel Processing Symposium, 660-665 (1995) |
| [11] | Senoussi, H.; Lavault, C., Embeddings into the pancake interconnection network, Proceeding of the High Performance Computing on the Information Superhighway, 73-78 (1997) |
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.
