生産スケジューラ用アクセラレータ

あると思います!(そればっか)

最近OpenCLがちょっと話題になっていて、あれもMSの次世代技術へのあてこすりなのであまり気にしなくていいとは思うんですが。

VLIWの研究論文とか読んでた頃には、パイプラインレベルの最適化とかリスケが重要なんだなという視点でした。これは生産ラインのベルトコンベア1本に相当します。CPUとGPUの連携や非対称なマルチプロセッサ環境が一般的になってくると、ふた昔くらい前の分散CPU環境の話題がぶり返してくるようです。これは複数ラインの協調に相当するでしょう。

OpenTransportやなんとかチャネルのように、プロセッサ間、プロセッサ-メモリ間通信の帯域も少し上がってきています。

多数のプロセッサ要素で多数のスレッドが並行動作するようになりますので、従来のL2キャッシュに収まるかどうかのメモリアクセスの時間的アドレス的局在性だけでは語れなくなってきます。

時代の最先端の皆様はとっくにそんな問題には取り組み済みかと思いますが、どぶ川の下流に住むごみためまんとしては、絵に描いた餅ソリューションが阿呆によって食い散らかされた結果のケツから出たカレーをメンテするような仕事をこなしていかなければなりません。つまり2歩先の1歩ななめ後ろを狙っていかないといけないのです。

従来のRTOS対策や、マルチスレッド取り扱い戦略を拡張していかなければならないのです。

現代的なプロセッサ環境、OpenCL eraと呼びましょうか。OpenCL 時代では、プロセッサの仕事の粒度が少し大きくなるということです。

VLIWの命令単位から、OpenCLのコマンドキュー単位というわけです。

すると、プロセッサのレジスタやALUというローカルなリソースだけではなく、ちょっと遠くの隣のプロセッサのメモリや、3軒向こうのGPUのテクスチャメモリなど、セミローカルなリソースの最適化についても考えなくてはならなくなります。

ファンクションブロック的あるいはストリーミング的に

入力→プロセス→出力

という単位だけを見ていては全体最適化はできないわけですね。

この問題については製造業が大昔から生産スケジューラ問題として取り組んでいます。

問題の基本は順列組み合わせであり最適化問題です。NP困難とか聞いたことある人も多いと思いますが。21世紀の生産スケジューラ界隈というのはPCの高速化の恩恵にかなりあやかったと言えます。

理論の裏づけは所詮第2次大戦のロジスティック経験しかありませんでしたので、戦後世界ではそこに宝の山が眠っているとはなかなか皆さん気づかなかったわけです。

そんな中トヨタのカンバン方式やゴールドラット博士のTOCなどで、『なんでいままで気づかなかったんだろうソリューション』が編み出され、スケジューリング界隈は二皮むけたような次第です。

IT界隈でのXPやアジャイルブームも、その余波の一部であるということにお気づきの皆様も多いかと思いますが。

さて、いよいよこの波がプロセッサ界隈に打ち寄せる時が来た気がします。

限られた計算リソース(プロセッサ、メモリ、バス帯域)から最大のアウトプットを得るためのスケジューリング技術です。

ご存じないかもしれませんが、現代の製造業では夜間バッチのみの生産計画がデフォルトではありません。特急生産や超特急生産もこなします。

工程が数千、管理するリソースもラインあたり数百は当たり前ですね。多品種小ロット時代ですから品種では数万もありえます。そこから準最適解をリアルタイムに計算しなければ、競争に勝てないのです。なんといっても競争相手は全世界ですから。計算している時間はそのまま納期に上乗せされてしまいます。

これらの製造業で培われたノウハウがOpenCLのコマンドキューのスケジューラにも適用されることは容易に想像できます。

個人的には、カンバン方式的な画像処理や、異種ラインにまたがって共有されるテクスチャメモリを管理するクリティカルチェーンの考え方などはすぐに適用できると思います。

とくにコストワールドとスループットワールドを意識的に分けて考えることはプロセッサ界隈でも必須になると思われます。コストはゲート数と発熱、スループットは時間当たり性能でしょう。コスト↓とスループット↑を両立させるソリューションは、部分最適化(コンパイラ技術)だけではだめなのでしょう。ブレークスルーの大物としてスケジューリングがあると思います。プロセッサごとのローカルメモリキャッシュは生産ラインにおける仕掛在庫に相当し、プロセッサ間バスは物流と情報インフラそのものです。OpenCL時代のスケジューラはおそろしくキャッシュのミスヒットが低減されるかもしれません。その次にくるのはキャッシュってもっと小さくていいんじゃね?という議論でしょう。しかしここでもキャッシュだけの微視的視点だけではすぐに壁にぶち当たるのです。

***

おろかなプロセッサ屋さんのことですから、スケジューリング支援シリコンを、もう作り散らかしていると思います。制約条件つき、重み付けありのソート処理の支援シリコンですね。これは生産スケジューラ用のアクセラレータとしては垂涎モノであることをここでお知らせしておきます。

ゲーム屋の物理演算コプロを、CAD屋が狙う時代です。

生産スケジューラ用アクセラレータメーカが現れないほうがおかしいのです。

りんくる

JIT (Just in Time) 生産スケジュール  リーン生産方式(トヨタ生産方式)ノウハウ lean-manufacturing

最適スケジューラ

http://programerengine.blog.so-net.ne.jp/