Very efficient cyclic shifts on hypercubes

paper ckks math

@inproceedings{ouyang1991very,
  title={Very efficient cyclic shifts on hypercubes},
  author={Ouyang, Pei and Palem, Krishna V},
  booktitle={Proceedings of the Third IEEE Symposium on Parallel and Distributed Processing},
  pages={556--563},
  year={1991},
  organization={IEEE},
  url={https://ieeexplore.ieee.org/stamp/stamp.jsp?tp=&arnumber=218250}
}

• hypercube 上の効率的な 巡回シフト
  • 分散ネットワークでデータを運搬するときの話

Abstract

巡回シフト は多くの並列アルゴリズムに内在する演算である
したがって、それらを効率的に実行することが重要である。著者らは、n次元（分散メモリ）ハイパーキューブ上のサイクリック・シフト操作のアルゴリズムを提示し、解析している。S.L. Johnsson (1987) による最初のアルゴリズムは、常にハイパーキューブのノード間の最短経路をルーティングに用いるものである。このアルゴリズムを用いた場合、同期ハイパーキューブ上のどの通信ステップにおいても、ノードやリンクの輻輳が発生しないことを著者らは証明している。その結果、このようなマシン上では、メッセージのローカルバッファリングなしに、任意のサイクリック・シフトをnステップで実装することができる。彼らは、これまでに知られているすべてのアルゴリズムが、非同期ハイパーキューブの文脈では、ローカルバッファリングを必要とすることを示す。これを克服するために、彼らは常にリンク不連続な経路をルーティングに使用するアルゴリズムを設計する。この場合、任意の周期的シフトは、ローカルメッセージバッファを一切使用せず、最大で/sup 4///sub 3/nステップで実現できることを証明する<>。