Xây dựng tô-pô mạng liên kết 3 chiều dựa trên kiến trúc DSN nhằm thích ứng cài đặt thực tế

  • Nguyễn Khanh Văn Viện CNTT&TT, Đại học Bách khoa Hà Nội

Abstract

The highly rising demands today in high performance computing or building big data centers make most of traditional interconnection network topologies become outdated. Currently, to develop new types of high performance network, random topologies such as using random shortcuts, small-world models, are promising research directions.

In this paper, we develop a new 3D topology named 3D-DSN based on the principles of Distributed Shortcut Network (DSN) [1] to support saving cable length. The main idea is to use a 2D-Torus as the base structure instead of a 1D-Ring as in [1]. Furthermore, the set of shortcuts are distributed in both directions of 2D-Torus and the routing logic is extended to 5 phases instead of 3 phases as in [1]. We also give the analyses of topology properties in both theoretical and experiment aspects, then conclude that 3D-DSN is more realistic than the basic DSN and provide a nice trade-off between network diameter (or average path length) and cable cost.

 

References

Van K. Nguyen, N. T. X. Le, I. Fujiwara, M. Koibuchi, “Distributed Shortcut Networks: Layout-aware Low-degree Topologies Exploiting Small-world Effect”, In Proc. of The 42nd IEEE International Conference on Parallel Processing, Oct. Lyon, France (ICPP-2013)

M. Koibuchi, H. Matsutani, H. Amano, D. Frank Hsu, H. Casanova, “A Case for Random Shortcut Topologies for HPC Interconnects”, In Proc. of the 39th International Symposium on Computer Architecture (ISCA’2012)

O. Lysne, L. Pedro, M. Koibuchi, T. Rokicki, & C. Sancho, “A Survey and Evaluation of Tô-pô Agnostic Deterministic Routing Algorithms,” IEEE Transactions on Parallel and Distributed Systems, 1-20. 2011

J. Kim, W. J. Dally, S. Scott, and D. Abts, “Technology-Driven, Highly-Scalable Dragonfly Tô-pô,” in Proc. of the International Symposium on Computer Architecture (ISCA), 2008, pp. 77–88.

P. Coteus and et. al., “Packaging the Blue Gene/L supercomputer,” IBM Journal of Research and Development, vol. 49, no. 2/3, pp. 213–248, Mar/May 2005.c

Y. Ajima, S. Sumimoto, and T. Shimizu, “Tofu: A 6D Mesh/Torus Interconnect for Exascale Computers,” IEEE Computer, vol. 42, pp. 36–40, 2009.

I. Fujiwara, M. Koibuchi, and H. Casanova, “Cabinet Layout Optimiza-tion of Supercomputer Topologies for Shor ter Cable Length,” in Proc. of International Conference on Parallel and Distributed Com puting, Applications and Technologies, Dec 2012.

Top 500 Supercomputer Sites, http://www.top500.org/.

A. Singla, C.-Y. Hong, L. Popa, and P. B. Godfrey, “Jellyfish: Net-working Data Centers Randomly,” in Proc. of USENIX Symposium on Network Design and Implementation (NSDI), 2012.

J. Y. Shin, B. Wong, and E. G. Sirer, “Small-World Data Centers,” in Proc. of the Symposium on Cloud Computing, Oct. 2011.

M. Koibuchi, I. Fujiwara, H. Matsutani, and H. Casanova, “Layout-conscious random topologies for hpc off-chip interconnects,” in 19th International Conference on High-Performance Computer Architecture (HPCA), Feb. 2013, p. XX.

Jouraku, M. Koibuchi & H. Amano, “An effective design of deadlock-free routing algorithms based on 2d turn model for irregular networks,” Parallel and Distributed Systems, IEEE Transactions on, 18(3), 320–333. IEEE. 2007

J. Kim, W. J. Dally and D. Abts, "Flattened Butterfly: A Cost-Efficient Topology for High-Radix Networks," Proceedings of the International Symposium on Computer Architecture (ISCA), pp. 126-137, 2 May 2007.

D. Watts and S. Strogatz, “Collective dynamics of small-world net-works,” Nature, vol. 393, pp. 440–32, 1998.

J. Kleinberg, “The small-world phenomenon: An algorithmic perspective,” in STOC, 2000.

C. Martel and V. Nguyen, “Analyzing Kleinberg’s (and other) smallworld models,” in PODC, 2004.

M. R. Samatham and D. K. Pradhan, “The De Bruijn Multiprocessor Network: A Versatile Parallel Processing and Sorting Network for VLSI,” IEEE Trans. on Computers, vol. 38, no. 4, pp. 567–581, 1989.

S. B. Akers, B. Krishnamurthy, and D. Harel, “The Star Graph: An Attractive Alternative to the n-Cube,” in Proc. of the International Conference on Parallel Processing (ICPP), 1987, pp. 393–400.

K. Hwang and J. Ghosh, “Hypernet: A communication-efficient archi-tecture for constructing massively parallel computers,” IEEE Trans. On Computers, vol. 36, no. 12, pp. 1450–1466, 1987.

D. J. Watts and S. H. Strogatz, “Collective dynamics of ‘small-world’networks,” Nature, vol. 393, no. 6684, pp. 440–442, 1998.

HP, "Optimizing facility operation in high density data center environments, technoloogy brief," [Online]. Available: http://h10032.www1.hp.com/ctg/Manual/c00064724.pdf

Chuyên san số 13 (33)
Published
2015-06-30
Section
Bài báo