Mercurial > hg > Papers > 2014 > toma-master
changeset 70:0b1a059c49fa
fix
| author | kono |
|---|---|
| date | Thu, 13 Feb 2014 12:08:24 +0900 |
| parents | 5e39ab004ae0 |
| children | 98a55a935619 |
| files | slides/master.html |
| diffstat | 1 files changed, 65 insertions(+), 209 deletions(-) [+] |
line wrap: on
line diff
--- a/slides/master.html Thu Feb 13 11:17:15 2014 +0900 +++ b/slides/master.html Thu Feb 13 12:08:24 2014 +0900 @@ -38,9 +38,7 @@ slides below. --> <article> - <h1> - 関数型言語 Haskell による並列データベースの実装 - </h1> + <h1> 関数型言語 Haskell による並列データベースの実装 </h1> <p> Daichi TOMA <br> @@ -48,141 +46,69 @@ </p> </article> - <article> - <h3> - 研究概要 - </h3> - <p> - Haskell を用いて並列データベースを実装した - </p> - <p> - 読み込みに関して 12 コアで実行した場合、10.37 倍 という性能向上率が確認できた - </p> - <p> - また、Web 掲示板サービスを開発し、Java と比較して読み込みで 3.25 倍、書き込みで 3.78 倍の性能差が確認できた - </p> - </article> - - <article> - <h3> - 研究背景 - </h3> - <p> - Web サービスの脆弱性を悪用されると多大な被害がでる - </p> - <p> - Haskell は型検査でバッファオーバーフローや、クロスサイトスクリプティング、SQL インジェクションを防げる - </p> - <p> - Haskell を用いることで信頼性の高いデータベースとWebサービスを開発できる - </p> - </article> +<article> + <h3> 研究概要 </h3> + <p> Haskell を用いて信頼性の高い並列データベースを実装した </p> + <p> Haskell は rseq により並列実行を指示し、STMにより共有データを実現する</p> + <p> Haskellの並列処理は、最新のコンパイラで性能がでることがわかった</p> + <p> 読み込みに関して 12 コアで実行した場合、10.37 倍 という性能向上率が確認できた </p> + <p> Web 掲示板サービスを開発し、Java と比較して読み込みで 3.25 倍、書き込みで 3.78 倍の性能差が確認できた </p> + <p> Network および IO の並列性能はあまり出てないことがわかった</p> +</article> - <article> - <h3> - 型による区別 - </h3> - <p> - Haskellは、全てに型がある - </p> - <p> - 文字列やHTMLを型として定義し、別の型として扱うことができる - </p> - <p> - 入力として受け取った文字列が、HTML型に自動変換されたりしない<br> - - > クロスサイトスクリプティングが防げる - </p> - </article> +<article> + <h3> Haskellによる信頼性の高いサービスの構築</h3> + <p> Web サービスの脆弱性を悪用されると多大な被害がでる </p> + <p> 脆弱性の大半はBuffer Overflowや、Cross site scripting、SQL injection </p> + <p> これらは型エラー。Haskell は、これらをコンパイル時にチェック</p> + <p> 入力として受け取った文字列が、HTML型に実行時に自動変換されたりしない<br> + ⇒ クロスサイトスクリプティングが防げる </p> +</article> - <article> - <h3> - 実行時型エラーがない - </h3> - <p> - Haskellは、実行時に型に起因するエラーが起きない - </p> - <p> - [1,2,3]のリストに文字'a'を追加することや、['a','b','c']のリストに 1 を追加することはできない - </p> - <p> - コンパイル時にエラーになる - </p> +<article> + <h3> Haskellの型検査の例(list) </h3> + : + / \ + 1 [] <pre> -abc = 'a' : [1,2,3] -- error -cde = 1 : ['a','b','c'] -- error +let a = 0 : [1,2,3] -- [0,1,2,3] +let b = 'a' : [1,2,3] -- error +let c = 1 : ['a','b','c'] -- error </pre> - <p> - Haskell 自体が型の不整合を防ぐ - </p> - </article> +</article> - <article> - <h3> - 型推論 - </h3> - <p> - 型エラーを検出するために全ての式や関数に型を書いていくのは大変 - </p> - <p> - Haskell は 型を推論してくれる - </p> - </article> - - <article> - <h3> - 型推論 - </h3> - <p> - 前提として関数に以下のような型が定義されている - </p> +<article> + <h3> 型推論 </h3> + <p> 前提として関数に以下のような型が定義されているとする </p> <pre> getNode :: Node -> Path -> Node elems :: Map k a -> [a] children :: Node -> Map Int Node </pre> - <p> - 新しくgetChildrenという関数を定義するとき型を自動で導出できる - </p> + <p> 新しくgetChildrenという関数を定義する</p> <pre> getChildren node path = elems (children (getNode node path)) </pre> - <p> - Haskell が推論した型を確認する - </p> + <p> 型をHaskellが自動で導出する </p> <pre> *Jungle> :type getChildren getChildren :: Node -> Path -> [Node] </pre> </article> - <article> - <h3> - 実用的なデータベースの開発 - </h3> - <p> - 現在、CPU はマルチコア化がすすんでいる - </p> - <p> - 実用的なデータベースとするためにはマルチコアに対応させる必要性がある - </p> - <p> - 並列に処理できればマルチコアで性能が出る - </p> - </article> +<article> + <h3> 実用的なデータベースには並列実行が必須 </h3> + <p> 現在、CPU はマルチコア化がすすんでいる </p> + <p> 実用的なデータベースとするためにはマルチコアに対応させる必要性がある </p> + <p> 並列に処理できればマルチコアで性能が出る </p> + <p> Haskell は Eval モナド(rpar)といったモナドで並列実行の機能を提供</p> + <p> モナドは、Haskellでメタ計算を提供する構文あるいはAPI</p> + <p> システムコールのようなものと考えてよい</p> + <p> モナドの例:IOモナド、エラーモナド、STMモナド </p> +</article> - <article> - <h3> - Haskell での並列実行 - </h3> - <p> - Eval モナドといったモナドで並列実行の機能を提供 - </p> - <p> - Haskell では様々な目的にモナドを使う<br> - I/O 処理を行うための IO モナドはよく使われる - </p> - </article> - + Haskell の並列処理 +rparの例 <article> <h3> Haskell の遅延評価 @@ -248,57 +174,19 @@ </div> </article> - <article> - <h3> - 非破壊的木構造 - ルートノード - </h3> - <p> - 非破壊的木構造の並列実行のネックとなるものがルートノード - </p> - <p> - ルートノードは、どの木構造が最新なのかを表す情報 - </p> - <p> - スレッド間で共有する状態を持つため、並列度を高めるにはルートノードの設計が重要 - </p> - <div align="center"> - <img src="images/rootnode.png" width="350px"> - </div> - </article> +<article> + <h3> Haskell でのRoot Node の管理 </h3> - <article> - <h3> - Haskell でのルートノードの管理 - </h3> - <p> - ソフトウェア・トランザクショナル・メモリ (STM) を使う - </p> - <p> - STM は、ノンブロッキングで共有データを扱える - </p> - <p> - 共有データの変更は以下の様に行われる - </p> + <p> Root Node は最新のNode → 状態を持つ</p> + <p> 共有された状態を作るには Software Transactional Memory (STM) を使う </p> + <p> STM は、ノンブロッキングで共有データを扱える </p> + <p> 共有データの変更は以下の様に行われる </p> <ul> <li>他から変更がなければそのまま適用 <li>変更している間に、他から変更されれば変更処理をやり直し </ul> - </article> +</article> - <article> - <h3> - STM のメリット - </h3> - <p> - 共有データにアクセスする時に待ちがない - </p> - <p> - 読み込みは他の変更を気にせず並列に行える - </p> - <p> - 高速に読み込める - </p> - </article> <article> <h3> @@ -339,22 +227,6 @@ </div> </article> - <article> - <h3> - Jungle に新しい木を作成 - </h3> -<pre> -data Tree = Tree (TVar Node) String -</pre> - <p> - Tree は最新のルートノードの情報と木の名前を持っている - </p> - <br> - <br> - <div align="center"> - <img src="images/get_root_node.png" width="500px"> - </div> - </article> <article> <h3> @@ -371,42 +243,26 @@ </p> </article> - <article> - <h3> - ノード - </h3> - <p> - Jungle で最も基本的な構成要素 - </p> - <p> - Jungle の参照や変更の関数は全てノードに対して行う - </p> -<pre> -data Node = Node (Map Int Node) (Map String ByteString) -</pre> +<article> + <h3> ノード </h3> + <p> Node はChildren(Node)とattributesを持つ </p> + <p> Jungle の参照や変更の関数は全てノードに対して行う </p> <div align="center"> <img src="images/node_component.png" width="500px"> </div> - </article> +</article> - <article> - <h3> - ノードを編集し、木の最新のルートノードを更新する - </h3> - <p> - updateRootNodeやupdateRootNodeWithで更新できる - </p> +<article> + <h3> ノードを編集し、木の最新のルートノードを更新する </h3> + <p> updateRootNodeやupdateRootNodeWithで更新できる </p> + <p> 内部でSTMを使っているのでIOモナドを返す</p> <pre> updateRootNode :: Jungle -> String -> Node -> IO () updateRootNodeWith :: (Node -> Node) -> Jungle -> String -> IO () </pre> - <p> - updateRootNodeには編集したNodeを渡すことで木の最新のルートノードを更新できる - </p> - <p> - updateRootNodeWithにはNodeを編集する関数を渡すことで木の最新のルートノードを更新できる - </p> - </article> + <p> updateRootNodeには編集したNodeを渡すことで木の最新のルートノードを更新できる </p> + <p> updateRootNodeWithにはNodeを編集する関数を渡すことで木の最新のルートノードを更新できる </p> +</article> <article> <h3> @@ -456,13 +312,13 @@ 現在の GHC の安定版 7.6.3 は並列時にIOマネージャーがスケールしないという問題がある </p> <p> - リリース候補版である 7.8 を用いる + リリース候補版である 7.8 を用いることにより、よりよい性能を得ることができた </p> </article> <article> <h3> - 親和性機能を利用する + 親和性機能(affinity)を利用する </h3> <p> 親和性機能とは OS スレッドをCPUコアに固定する機能