プログラミング環境研究チームの中尾昌広 研究員が Graph Golf 2018 において「Widest Improvement Award」・「Deepest Improvement Award」の2つの賞を受賞し、11月27日、岐⾩県⾼⼭市で開催された国際シンポジウム 「CANDAR '18」で表彰されました。
Graph Golf では、ある「頂点数」と「次数(1つの頂点から出る辺の数 )」を持つグラフがいくつか出題され、「1つの頂点から最も離れた頂点までのホップ数」と「全頂点間のホップ数の平均値」が最も小さいグラフの設計を競います。
中尾研究員は、Simulated Annealing(SA)と呼ばれる汎用的な最適化アルゴリズムと、出題されているグラフに対称性を持たせることで、SAの解探索性能と高速化の両方を達成できるアルゴリズムの開発を行いました。特に高速化については、MPIとOpenMPを用いたハイブリッド並列を行うことにより、アルゴリズムの工夫とを組合せて最大2,000,000倍の高速化を達成しました。