Benders Decomposition(ベンダー分解)は問題を二つのmain, sub問題に分割することで問題を解きやすくするテクニックです。次のような性質がある問題に有効です。Kohji Nishimuraさんの「双対変数を直感的に理解したい」から引用しています。 決定変数にyが一…

本記事は数理最適化 Advent Calendar 2023の18日目の記事です。分散深層学習に使われる最適化について紹介します。 分散深層学習は、複数の計算ユニット（GPU、CPUなど）を活用して深層学習モデルを訓練する手法のことで、特にLLMのような巨大モデルの訓練に…

Networking, Cisco Visual."Forecast and methodology, 2010-2015." White paper. (2011). Networking, Cisco Visual. "Cisco global cloud index: Forecast and methodology, 2016–2021." White paper. Cisco Public, San Jose 1 (2016). を元に可視化。 ta…

Gurobiのログに出てくる項目について。 Nodes | Current Node | Objective Bounds | Work Expl Unexpl | Obj Depth IntInf | Incumbent BestBd Gap | It/Node Time Nodes: 解探索の過程で考慮されたノード数。これは分枝限定法で生成される。 Expl: 既に探索…

igraph経由で行うと楽です。 pythonパッケージ↓ import igraph as ig # m = the size of the alphabet minus one # n = the length of the strings minus one # total nodes = (m+1)m^n # degree = m G = ig.Graph.Kautz(3, 1) nx_G = G.to_networkx() # con…

@article{thao2021efficient, title={Efficient MPI-AllReduce for large-scale deep learning on GPU-clusters}, author={Thao Nguyen, Truong and Wahib, Mohamed and Takano, Ryousei}, journal={Concurrency and Computation: Practice and Experience},…

本稿ではfloptを用いて双対問題の作成のその求解を行います。 双対問題 実装 制約を不等式に変換 ラグランジュ関数の生成 双対問題の作成 線形計画法の双対問題 双対問題 min f(x) s.t. g_i(x) <= 0 (for all i) x is continuous vector このような問題の場…

本稿では、floptモデリングツールで定義した線形計画問題に対し単体法を実行して解の取得を行います。Wikipediaにある問題を例に実装してみましょう。 主問題の定義 単体法(Simplex) 等式制約に変換 線形計画の形式に変換 基底変数と非基底変数の設定 Step1:…

@article{zhuang2023optimizing, title={On optimizing the communication of model parallelism}, author={Zhuang, Yonghao and Zheng, Lianmin and Li, Zhuohan and Xing, Eric and Ho, Qirong and Gonzalez, Joseph and Stoica, Ion and Zhang, Hao and Z…

便利かもしれない（？）、フィルタコマンドのfzfの軽い紹介 install mac brew install fzf ubuntu apt-get install fzf 実行方法 標準出力をパイプさせる。 例えば下記の通り。あとは検索ワードを打ち込むと画面上で絞り込まれる。 ls | fzf 他には様々なレ…

flopt v0.5.6で座標降下法(Coordinate Descent)の実行方法を示します。 2 x2 + y2 + xy の関数について、xとyの変数の片方のみを交互に移動させて局所最適解を目指します。 prob.solve(optimized_variables=[x[0]]) のようにoptimized_variablesに最適化対象…

故きを温ねて新しきを知る Fast Multi-GPU collectives with NCCL NCCL: Collective Operations Collective communication: theory, practice, and experience A Generalization of the Allreduce Operation TACCL: Guiding Collective Algorithm Synthesis …

Cai, Zixian, et al. "Synthesizing optimal collective algorithms." Proceedings of the 26th ACM SIGPLAN Symposium on Principles and Practice of Parallel Programming. 2021. どんなもの？ 詳細 論文メタ情報 AI向けハードウェア DGX-1 Gigabyte Z52 …

26 (Online): Deep or Statistical: An Empirical Study of Traffic Predictions on Multiple Time Scales 49 (On-site): Network-Accelerated Cluster Scheduler 63 (On-site): Mind the Cost of Telemetry Data Analysis 65 (Online): PipeDevice: A Hardw…

滝澤真一朗, 遠藤敏夫, and 松岡聡. "次世代光インターコネクトでの MPI 通信に関する研究." コンピュータ ソフトウェア 26.3 (2009): 3_5-3_19. 概要 背景 どんなもの? 技術や手法のキモはどこ? どうやって有効だと検証した? OCS経路選択アルゴリズム Switc…

Sato, Ken-ichi. "How optical technologies can innovate intra data center networks." 2021 International Conference on Computer Communications and Networks (ICCCN). IEEE, 2021. paper: https://ieeexplore.ieee.org/document/9522206 光スイッチを…

Wang, Guanhua, et al. "Blink: Fast and generic collectives for distributed ml." Proceedings of Machine Learning and Systems 2 (2020): 172-186. Microsoft + インターン？ [paper] 概要 どんなもの？ 与えられたトポロジに適した集団通信アルゴリズ…

flopt v.0.5.6を公開しました。 ソルバ開発の目線だとJacobian, Hessian用のAPIが一番使う機会が多いですかね？ ユーザー目線だとprob.solve(optimized_variables=variable_list)が最も使えそうな気がします。 Update 1. problem type estimator API 問題の…

SCIP: https://www.scipopt.org/は言わずと知れたLP、MIPソルバ。 このプロジェクトにはfscip: https://ug.zib.de/も同封されています。これはSCIPのスレッド並列版ソルバです。 Environment Ubuntu 18.04.2 LTS Build unzip scipoptsuite-8.0.3.zip cd scip…

NVIDIA （Mellanox）のスイッチ、例えばQM8700, SB7700, SB7800のMLNX-OSをアップデートする手順を示します。 以下これらはIBスイッチと呼称します。古いMLNX-OSだと比較的新しいトランシーバが認識（LinkDown）しなかったり、という問題が発生することがあ…

Wang, Weiyang, et al. "Topoopt: Co-optimizing network topology and parallelization strategy for distributed training jobs." arXiv preprint arXiv:2202.00433 (2022). [paper] 概要 どんなもの? Metaにおける分散DNNトレーニングジョブの解析 それを…

本稿では、ファジィの考え方に基づいた曖昧性を線形計画法（LP）に組み込む方法について紹介します。 線形計画法は次のような問題。 この線形計画法では、少なくとも単点に最適解がある（もし最適解があるならば）という性質があります。 すなわち、得られた…

本稿は [1] の p115 手続き 4.1 として紹介されている歪対称行列を用いた線形計画問題が内点 を含むようにする手順について考察を行うものです。 [1] 並木誠 線形計画法(朝倉書店, 2008) drive.google.com

スタックトレースとは、実行していた関数やメソッドなどの履歴のことです。バグやエラーが発生した際にスタックトレースを表示させることでデバッグを行いやすくします。 Python tmp.py f = lambda: g() g = lambda: h() h = lambda: i() def i(): return 2/…

デバッグモードでコンパイルする pytorch/tools/setup_helpers/cmake.py に下記を追加。（ついでにCMAKE_VERBOSE_MAKEFILEも追加しています） --- a/pytorch/tools/setup_helpers/cmake.py +++ b/pytorch/tools/setup_helpers/cmake.py @@ -305,6 +305,9 @@ …

その問題、数理モデルが解決します 社会を解き明かす数理モデル入門 [ 浜田 宏 ]価格：2090円（税込、送料無料) (2022/11/8時点)楽天で購入 著者名 浜田宏 ISBN 978-4-86064-568-7 ページ数 308ページ サイズ A5判 並製 価格 定価2,090円 (本体1,900円＋税10…

最終的に描写するもの 暫定解値と, 下限値の時間推移 最適値 下記記事のGUROBI版です。正規表現などの解説は、次の記事にあります。 描写コード gist.github.com

本稿ではword embeddingとしてFastTextを導入してみます。 Pretrained Word Embeddings コード まとめ 他の記事 Pretrained Word Embeddings 学習済のword embeddingによる変換を試してみましょう。 pytorchで公開されているfastTextを使ってみます。 これは…

Liu, Gengchen, et al. "Architecture and performance studies of 3D-Hyper-FleX-LION for reconfigurable all-to-all HPC networks." SC20: International Conference for High Performance Computing, Networking, Storage and Analysis. IEEE, 2020. bib…

Yang, Hao, et al. "Which can Accelerate Distributed Machine Learning Faster: Hybrid Optical/Electrical or Optical Reconfigurable DCN?." 2022 Optical Fiber Communications Conference and Exhibition (OFC). IEEE, 2022. @inproceedings{yang2022c…