文献

J-GLOBAL ID：201902268680815633   整理番号：19A0106281

order/disorder問題に対してCayleyグラフを用いたorder調整アプローチ

Order Adjustment Approach Using Cayley Graphs for the Order/Degree Problem

著者 (3件)： KITASUKA Teruaki (Graduate School of Engineering, Hiroshima University) ,  MATSUZAKI Takayuki (Graduate School of Science and Technology, Kumamoto University) ,  IIDA Masahiro (Division of Computer Engineering, Faculty of Advanced Science and Technology, Kumamoto University)
資料名： IEICE Transactions on Information and Systems (Web)  (IEICE Transactions on Information and Systems (Web))
巻： E101.D  号： 12  ページ： 2908-2915(J-STAGE)  発行年： 2018年 
JST資料番号： U0469A  ISSN： 1745-1361  資料種別： 逐次刊行物 (A)
記事区分： 原著論文  発行国： 日本 (JPN)  言語： 英語 (EN)

抄録/ポイント： order/disorder問題は与えられたorderとdisorderに対して最小直径グラフを見出すことから構成する。このようなグラフは,超並列計算機に対して高性能をもつ低遅延ネットワークの設計に対して有用である。グラフの平均最短経路長(ASPL)は遅延に影響を及ぼす。本論文では,新しいorder調整アプローチを提案した。提案したアプローチでは,与えられたorderに近い与えられたdisorderのCayleyグラフを探索した。次に,与えられた順序を満たす最良のCayleyグラフのorderを調整した。いくつかのorderとdisorderの対に対して,Graph Golf2016と2017の競合から,最小の既知のグラフをいかに導くかを説明した。(翻訳著者抄録)

シソーラス用語： *グラフ理論 ,  Cayley樹 ,  *並列演算 ,  遅れ ,  ネットワーク ,  *問題 ,  長さ ,  頂点
準シソーラス用語： *Cayleyグラフ ,  *order/disorder問題 ,  経路長 ,  *超並列計算 ,  低遅延

著者キーワード (7件)： 次数/次数問題 ,  Cayleyグラフ ,  直径 ,  平均最短経路長(ASPL) ,  頂点二分 ,  頂点注入 ,  頂点除去

分類 (1件)： グラフ理論基礎  (IA02020S)

引用文献 (15件)：

• [1] M. Koibuchi, I. Fujiwara, F. Chaix, and H. Casanova, “Towards ideal hop counts in interconnection networks with arbitrary size,” Proc. 2016 Fourth International Symposium on Computing and Networking (CANDAR), pp.188-194, Nov. 2016. 10.1109/candar.2016.0042
• [2] R. Yasudo, M. Koibuchi, K. Nakano, H. Matsutani, and H. Amano, “Order/radix problem: Towards low end-to-end latency interconnection networks,” Proc. 46th International Conference on Parallel Processing (ICPP), pp.322-331, Aug. 2017. 10.1109/icpp.2017.41
• [3] N.T. Truong, I. Fujiwara, M. Koibuchi, and K.-V. Nguyen, “Distributed shortcut networks: Low-latency low-degree non-random topologies targeting the diameter and cable length trade-off,” IEEE Trans. Parallel Distrib. Syst., vol.28, no.4, pp.989-1001, April 2017. 10.1109/tpds.2016.2613043
• [4] J. Kim, W.J. Dally, S. Scott, and D. Abts, “Technology-driven, highly-scalable dragonfly topology,” Proc. 35th International Symposium on Computer Architecture (ISCA), pp.77-88, June 2008. 10.1109/isca.2008.19
• [5] J.-Y. Shin, B. Wong, and E.G. Sirer, “Small-world datacenters,” Proc. 2nd ACM Symposium on Cloud Computing (SOCC'11), Article 2, 13 pages, Oct. 2011. 10.1145/2038916.2038918

タイトルに関連する用語 (2件)： 問題 ,  グラフ