グラフ理論と計算機科学(Lamportの前あたりまで)
- TuvianNavy
- 883
- 1
- 0
- 0
@TuvianNavy Tony Hoareのみょうじがまちがってる techblog.yahoo.co.jp/architecture/2…
2016-02-17 12:21:48よくわからんけど、プロセッサ単位の並列化とノード単位の並列化のアナロジーを明示的な断りもなく導入しちゃってるのが問題かなあ
2016-02-17 12:17:38@TuvianNavy DAG(directed acyclic graph)がバズワード化してるんだよね
2016-02-17 13:32:36@TuvianNavy UT物工には今も物理学汎論の授業があるらしいが、非専門家向けの「計算機科学汎論」を講義するとしたらいろいろなところに現れるグラフ理論の話をしたらいいと自分は思う
2016-02-18 05:43:52@TuvianNavy 手分けしてなにかやろうってときに、サブタスクに分割して、順番のあるもの(前工程の成果物に依存するもの)はその順番に並べて、依存関係のないタスクを洗い出したら手のあいてるひと(タスクによっては人を選ぶけど)にアサインして、っていう当たり前の
2016-02-17 12:58:37@TuvianNavy 話を形式的に考えると離散的な位相空間(グラフ)の話になってしまって、一見さんお断りのチョー難しげな話ということになる、 人にものを頼むときに誰でも或る程度はやっていることなんだけど
2016-02-17 13:01:15@TuvianNavy makeでやってるのも同じ話。tsortとかPascalみたいな1passの処理系の場合、要するにローダやコンパイラで関数シンボルは定義済みでないといけない(先立つ工程でコンパイルされていないといけない)という制限があってこれも同様の話
2016-02-17 13:31:52@TuvianNavy プロセッサのキャッシュの一貫性とか、SMPのメモリのatomicな操作のセマンティックスの話は、DBの読み取り一貫性の話とかと似てる、自分はSPARCのマニュアルでPSOとかTSOとかの説明よんでややこしそうだなーと思って以後勉強してない
2016-02-17 13:37:25@TuvianNavy Lamportが何をやったか、というのを自分はまだ間違えずに説明できる自信が無い、たとえばMAGIシステムを設計するには必須の知識だし、ntpdを実装するにも知ってないと危ない
2016-02-17 13:51:28@TuvianNavy たとえば地デジの受像機のデコードは機器間で秒単位の差が出るからもう放送の世界では「同時」という概念が成立していない、LamportのPaxosとかの世界
2016-02-05 11:06:34