Comments
Description
Transcript
計算モデル特論
自己紹介：佐藤一郎 計算モデル特論 n 国立情報学研究所・ アーキテクチャ科学研究系・教授 n 国立大学法人総合研究大学院大学・ 複合科学研究科・情報学専攻・教授 国立情報学研究所 n 専門：分散システム 佐藤一郎 E-mail: [email protected] Ichiro Satoh Ichiro Satoh 国立情報学研究所 宣伝 講義の目標 国立情報学研究所／国立大学法人 総合研究大学院大学 複合科学研究科 情報学専攻 学生募集 n ５年一貫制博士課程 大学の学部卒業と同等以上の学力を有する者を対象 とし、標準5年間で博士の学位を取得 博士後期課程 大学院修士課程修了と同等以上の学力のある者を対 象とし、標準3年間で博士の学位を取得 国立情報学研究所（NII） n n n Ichiro Satoh 計算モデルを通じて計算について理解すること 計算に関する数学的な取り扱いに慣れること 計算モデルを通じて(計算）システムを捉えること n 複雑システム(並列・分散システム、相互作用)をモデル化 n 例：クラウドコンピューティングは非同期計算モデルがベース n 例：Google MapReduceは関数型計算モデルがベース 評価： レポート（数回） （たぶん一回） Ichiro Satoh 計算モデル n 講義内容（今年） 計算モデルの必要性 n 世の中の情報システム(コンピュータや生物)は非常に複雑 n 例：PCの構成・仕組みは複雑 n n 計算モデルとは n 並列分散計算のモデル n CCS (Calculus for Communicating Systems) n 操作意味論 n プロセス等価性 n 時相論理 n Petri-net n 非計算システムの計算モデル この情報システムがどのような原理に基づくかを知るには 数学的基盤を持つ抽象的な枠組みを導入する必要がある 情報システムの抽象的な枠組み＝計算モデル n 計算モデルを通じて「計算」及び「情報システム」という概念を明確化 Ichiro Satoh 講義内容（昔） n n Ichiro Satoh 代表的な計算モデル 講義内容（予定） 計算モデル （逐次）計算モデル： n 抽象機械計算モデル n 関数型計算モデル n 論理型計算モデル n 項書き換え型計算モデル n 抽象機械モデル、関数型モデル、プロセス代数（プロ セスカルキュラス） n プログラミング言語意味論 n 操作意味論、表示意味論、公理意味論 n 型理論 n 型付きラムダ計算、多相型、オブジェクト指向型 n Ichiro Satoh （並列分散）計算モデル n 抽象機械計算モデル n プロセス代数（プロセスカルキュラス） n イベント機械モデル（ペトリネット） n Ichiro Satoh なぜ、並列分散計算モデルなのか スケールアップよりスケールアウト n ここ数年は並列分散計算モデルに特化しています。 n 並列分散計算モデルとは n 複数同時に実行されるシステム n システム間通信 n スケールアップ n 少数の高性能コンピュータ n 理由： n Webをはじめ通信する計算システムばかり n クラウドコンピューティングなど複数サーバによるシステム構成 n PCやスマートフォンではマルチコアがあたりまえ n 実世界は複数の実体が同時並列に動いている n スケールアウト n 多数の低性能コンピュータ n 経験則： n 1万台サーバのデータセンタは、1千台のデータセンタより、 規模当たりのコストは5 7倍安い Ichiro Satoh Ichiro Satoh Ichiro Satoh Ichiro Satoh 計算システムの変遷 n n n n n 逐次型計算システム（1950年） マルチタスク計算システム（1970年） クライアントサーバ計算システム（1990年） Webベース計算システム（2000年） クラウドコンピューティング（2008年） クラウドコンピューティング インターネット 膨大なサーバ群 ここ数年で計算システムは大きく変わっている パブリッククラウド n n n n n パブリッククラウドの構成 所有から利用へ n クラウドインフラ上の仮想環境、プログラム実行環境、サービスを利用 低コスト n クラウドインフラは多数サーバを少人数・一括管理（1万５千台に管理者 １人） 従量課金制 n 使った分を使っただけ利用料を支払う（固定費から変動費に） スケールアウト性 n 必要なときに必要な計算リソースを利用可能 世界規模のコンピュータ n 世界各所の巨大データセンターでアプリ・データを多重化 n 自然災害や大規模停電に対応 n n 数十万台のサーバから構成 n 計算リソースは事実上無限大 サーバ故障を前提にした運用 n データ・アプリケーションの多重化 分散ストレージ アプリケーション アプリケーション ライブラリ クライアント ライブラリ データの複製の複数サーバで保持 仮想マシン アプリケーション アプリケーション ストレージ ストレージ ストレージ サーバ サーバ サーバ インターネット ライブラリ ライブラリ 非同期データ複製・更新 仮想マシン Ichiro Satoh 高信頼性よりも多重化 n ストレージ サーバ Ichiro Satoh 大規模計算センター クラウドコンピューティングのシステム構成・運用 n サーバ台数が増えると、故障も増える n 一日辺りの故障率（Googleのデータセンター）：0.55% n サーバ数が多いので、一日に数千台が壊れている n 高信頼性ハードウェアは高価 n （低信頼な）コモディティハードウェアを数でカバー n 故障を前提にしたシステム構成 n データや処理を多重化して、部分的故障を隠蔽 n サーバ管理の集約化・自動化、故障対応コスト削減 n データセンターは「規模の経済」 中規模(1000台クラス) 大規模(5万台クラス) 倍率 通信コスト（1Mbpsの 通信回線あたり） 月額95ドル 月額１３ドル 7.1倍 ストレージコスト（1GB の容量あたり） 月額2.2ドル 月額0.40ドル 5.7倍 管理コスト（一管理者 による管理台数） 140台 1000台以上 7.1倍 n 多数のサーバ n 従量制(Pay-per-use) n 事実上、無限大の計算リソース n バックアップや運用はインフラ任せ Ichiro Satoh 10万台から100万台のサーバ Ichiro Satoh Intelのメニーコア化 メニーコアプロセッサ n n n n n Intel Xeon Phiはx86コアを60個搭載 マルチコアプロセッサはあたりまえ n Intel Xeon Phiはx86コアを60個搭載 CPU+GPUアーキテクチャ n 汎用コアとGPUをリングバス結合 CPU+FPGA n 汎用コアと再構成論理回路 ヘテロコア Ichiro Satoh いまどきの計算 n n n n n Ichiro Satoh 計算モデルの必要性 超大規模な分散コンピューティングシステムがあたりまえ n 多数のコンピュータで分散処理 n 計算よりも問題分割が重要 プロセッサはマルチコア以上があたりまえ n 並列計算機の方が普通 n 力業的な計算でもなんとかなる ネットワーク接続はあたりまえ n 計算よりも通信 低消費電力 n 消費電力当たりの性能 n 計算機のハードウェア n 複雑すぎて扱えない n CやPascalなどで書かれたプログラム n 数学的な厳密さを持つとは限らない n プログラムを入力から出力を得るものとする n 例：数学的な関数 n ただし、実際に入力を与えても、その答え（出力）が導けるとは限 らない 授業では分散システムのための計算モデルを中心にして扱う Ichiro Satoh Ichiro Satoh 講義の目標 授業資料のダウンロード 各種の計算モデルについて学ぶこと n 計算の数学的な取り扱いに慣れること n 計算モデルを通じて計算という概念を理解すること n ものの原理を見抜くセンスを養うこと n http://ichiro-satoh.jp/lectures/model/2013/! Ichiro Satoh Ichiro Satoh 履修者への質問 n 講義内容とレベルは履修者の背景知識と関心により決める n 履修者の背景知識に関する質問 集合または代数論の講義の履修（有／無） オートマトンの講義の履修（有／無） 一階述語論理の講義の履修（有／無） 計算モデルに関する講義の履修（有／無） n n n n 計算モデルとは n 国立情報学研究所 n 佐藤一郎 [email protected] n E-mail: Ichiro Satoh Ichiro Satoh 計算モデル n n n 「計算」とは 計算モデルの必要性 世の中の情報処理システムは非常に複雑 この情報処理システムがどのような原理に基づくかを知るには数学 的基盤を持つ抽象的な枠組みを導入する必要がある。 n n 「計算」とは、 n ある「アルゴリズム」に基づいて、ある基本的な手順を実行し目的 とする結果を得る作業 n しかし、実際の情報処理システムは複雑であり、本来の基本原理で ある「計算」が不明確 数学的な裏付けをもつ抽象的な枠組み（＝計算モデル）を導入し、 記号の書き換えとして計算を再現する 情報処理システムの抽象的な枠組み＝計算モデル n n n 計算モデルを通じて「計算」という概念を明確化する Ichiro Satoh アルゴリズムとは n Ichiro Satoh 計算の量 「アルゴリズム」とは n 計算手順のこと。基本的な実行単位をどのような順序で実行す るかを示したもの。 n 客観的で、実行可能な方法。 n アルゴリズムを特定の計算機で実行できるように表現したもの＝ 「プログラム」 n どうやって計算の量を測るのか？ n ある人に計算させてその時間を測る（方法１） n 特定の作業、手順に着目してその実行回数を数える（方法２） n 計算量 n 時間計算量(time complexity) n 特定の作業の実行回数を数えたもの。 n Ichiro Satoh 領域計算量(space complexity) n 記憶領域の消費量の目安。単位としてビット、ワード、バイト、 レジスタなどをきめて、その消費量を示す。 n 先の例では、変数の数など。 Ichiro Satoh 計算モデルの必要性 n 計算機のハードウェア n n （逐次）計算モデル： n 抽象機械計算モデル n 関数型計算モデル n 論理型計算モデル n 項書き換え型計算モデル n 複雑すぎて扱えない CやPascalなどで書かれたプログラム n n 代表的な計算モデル 数学的な厳密さを持つとは限らない プログラムを入力から出力を得るものとする n n 例：数学的な関数 ただし、実際に入力を与えても、その答え（出力）が導けるとは限らない （並列分散）計算モデル n 抽象機械計算モデル n プロセス代数（プロセスカルキュラス） n イベント機械モデル（ペトリネット） n Ichiro Satoh 例：DNA計算(DNA computing) 自然現象と計算 n n n n n Ichiro Satoh 自然現象を計算として捉える 既存手法ではえられない知見をえることがある n 自然現象を計算機として捉える 一般のコンピュータよりも高性能なこともある。 n 例：DNAコンピューティング n 自然現象が計算システムのヒントになることがある n n n Leonard Adleman (1994) 分子生物学的な実験手法による有向ハミルトン経路問題の解法を発 表 経路問題をDNAの塩基配列として表現 分子化学的操作のみによって変化(計算)， 大量の分子が並列的に化学反応をおきる →超並列性 宇宙はコンピューターだ ──と言われてもピンとこ ないかもしれません。でも 本当なんですよ。プログラ ムは「物理法則」。計算して いるのは「自らの構造」。か の天才・ホーキングが自説 を修正したように，何でも吸 い込むブラックホールでさ え，ちゃんと計算結果を出 力しているのです Ichiro Satoh Ichiro Satoh チューリングマシン 例:Ambient Calculus n n 細胞(膜)の変異を表す計算モデル n 構文 n n Ａ．Ｍ．チューリングが提案した仮想機械 すべてのプログラム内蔵計算機をシミュレーションできる機械 基本的な動作（特定の作業） n n n n 公理 n n n 推論 テープの読み込み テープの書き込み テープの送り、戻し 内部状態の変更 記憶領域 n n 内部記憶 テープ（外部記憶） Ichiro Satoh Ichiro Satoh チューリング機械の例 チューリング機械モデル n n 計算する機械の本質を定義した n （１）はじめに計算の手順を一種の規則として記憶する n （２）与えられたデータに上の規則を適用し、１ステップづつ計算を行 う n １ステップの動作は、データを読み込んで簡単な計算を行い、必 要に応じて結果を計算用紙に書きとめたあと、いくらかの必要な 情報を記憶して次のステップへ進む。 n ここで記憶する情報は、前のステップで得られた結果のほか、今 どの段階の計算をしているかの情報なども含む。 具体的な機械のイメージで実現 両方向に無限に長い１本のテープ １マスに１つの記号が書かれる テープを操作しながら規則に従って計算を行う本体 内部状態（（１）の規則と（２）の情報）が記憶される Ichiro Satoh n 具体的なチューリング機械 n 例：自然数ｋの１０進表現を与えられたとき、ｋ＋１の１０進表現を得る機 械Ｍ n Ｍのテープ記号の集合Ａ＝｛□、０、１、．．９｝ n Ｍの内部状態の集合Ｑ＝｛ｑ０、ｑ１、ｑ２、ｑ３｝ n Ｍの規則を表す関数Ｔ（以下の遷移図） 読み取った記号 ａ／ａ＋１、‐１ ９／０、‐１ （ａ：□、９ 以外の記号 ｑ３ ａ／ａ、＋１ （ａ：□以外 の記号） ｑ１ ｑ２ □／□、‐１ □／１、０ 書き込む記号 ａ／ａ、‐１ （ａ：□以外 の記号） ヘッドの移動方向 □／□、＋１ ‐１：左 ＋１：右 ｑ０ ０： 移動せず Ichiro Satoh チューリング機械モデルの計算 n 練習 具体的なチューリング機械での計算ステップ （１） ２５９ （６） ２５０ ｑ１ （２） ２５９ （７） ２５９ ２５９ ｑ１ （５） ２６０ （１） ｑ３ （８） ｑ１ （４） 次の入力をチューリング機械で実行せよ ｑ２ ｑ１ （３） n ｑ１ ２６０ ｑ３ （９） １２３ （２） ２５９ ２９９ ｑ１ ｑ０ （３） ２５９ ９０９ ｑ１ ｑ２ Ichiro Satoh Ichiro Satoh