Mercurial > hg > Papers > 2009 > tkaito-sigos

diff presen/pre1.html @ 22:363d231726bc
Proto
author: admin@mb22-no-macbook-2.local
date: Wed, 22 Apr 2009 10:52:50 +0900
children: cbfd29809746
--- /dev/null	Thu Jan 01 00:00:00 1970 +0000
+++ b/presen/pre1.html	Wed Apr 22 10:52:50 2009 +0900
@@ -0,0 +1,720 @@
+<!DOCTYPE html PUBLIC "-//W3C//DTD XHTML 1.0 Strict//EN" 
+	  "http://www.w3.org/TR/xhtml1/DTD/xhtml1-strict.dtd">
+
+<html xmlns="http://www.w3.org/1999/xhtml">
+
+<head>
+<meta http-equiv="Content-Type" content="text/html; charset=UTF-8">
+<title>第175回ARC・第111回OS合同研究会</title>
+<!-- metadata -->
+<meta name="generator" content="S5" />
+<meta name="version" content="S5 1.1" />
+<meta name="presdate" content="20050728" />
+<meta name="author" content="Tagano Kaito" />
+<meta name="company" content="ie-ryukyu" />
+<!-- configuration parameters -->
+<meta name="defaultView" content="slideshow" />
+<meta name="controlVis" content="hidden" />
+<!-- style sheet links -->
+<link rel="stylesheet" href="ui/default/slides.css" type="text/css" media="projection" id="slideProj" />
+<link rel="stylesheet" href="ui/default/outline.css" type="text/css" media="screen" id="outlineStyle" />
+<link rel="stylesheet" href="ui/default/print.css" type="text/css" media="print" id="slidePrint" />
+<link rel="stylesheet" href="ui/default/opera.css" type="text/css" media="projection" id="operaFix" />
+<!-- S5 JS -->
+<script src="ui/default/slides.js" type="text/javascript"></script>
+<style type="text/css">
+body {
+font-size: 100%;
+}
+p.ex8 { font-size: 2.0em; }
+p.ex7 { font-size: 1.9em; }
+p.ex6 { font-size: 1.8em; }
+p.ex5 { font-size: 1.7em; }
+p.ex4 { font-size: 1.6em; }
+p.ex3 { font-size: 1.5em; }
+p.ex2 { font-size: 1.4em; }
+p.ex1 { font-size: 1.3em; }
+p.ex0 { font-size: 1.0em; }
+p.ep0 { font-size: 0.5em; }
+p.ep1 { font-size: 1.1em; }
+span.classifier {
+  font-family: sans-serif ;
+  font-style: oblique }
+
+span.classifier-delimiter {
+  font-family: sans-serif ;
+  font-weight: bold }
+
+span.interpreted {
+  font-family: sans-serif }
+
+span.option {
+  white-space: nowrap }
+
+span.pre {
+  white-space: pre }
+
+span.problematic {
+  color: red }
+
+span.section-subtitle {
+  /* font-size relative to parent (h1..h6 element) */
+  font-size: 80% }
+
+</style>
+</head>
+<body>
+
+<div class="layout">
+<div id="controls"><!-- DO NOT EDIT --></div>
+<div id="currentSlide"><!-- DO NOT EDIT --></div>
+<div id="header"></div>
+<div id="footer">
+<h1>沖縄県青年会館 / 20090424</h1>
+<h2>第175回ARC・第111回OS合同研究会</h2>
+</div>
+</div>
+
+<div class="presentation">
+<div class="slide">
+<center>
+<br><br>
+<p class="ex8">Cell Task Manager Cerium の <br> SPU内データ管理</p>
+<p><font size="5" color="#000000">多賀野海人、小林佑亮、宮國渡、河野真治</font</p>
+<p><font size="5" color="#000000">琉球大学</font></p>
+<p><font size="5" color="#000000">Apr, 24, 2009</font></p>
+</center>
+</div>
+
+<div class="slide">
+<h1>研究の背景と目的</h1>
+<font size="6">研究背景</font>
+<ul>
+  <li><p class="ep1">Cell に搭載されている SPE は Local Store (256KB) にしかアクセスできない。</li>
+  <li><p class="ep1">メインメモリにアクセスするには MFC を用いて Direct Memory Access 命令を
+    送らなければならない。</li>
+  <li><p class="ep1">また、この DMA には待ち時間が存在する。待ち時間の間 SPE が動作しなければマルチコアプロセッサのパフォーマンス
+    が極端に下がる。</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>研究の背景と目的(Con't)</h1>
+<font size="6">研究目的</font>
+<ul>
+<!--<font size="5"> -->
+  <li><p class="ep1">SPE 内のデータ管理を行い Cell プログラミングの並列度を確保する手法を提案する。</li>
+  <li><p class="ep1">本研究室で開発した Cerium というの Rendering Engine を
+    用いたゲームプログラミングを例題とする。</li>
+  <li><p class="ep1">描画に必要な Texture データは、SPE の LS に収まりきらない場合があるので、
+    データを分割して転送、処理する必要がある。</li>
+  <li><p class="ep1">既に SPE 内にデータが転送されている場合、そのデータの管理を SPE 内で行うことによって、
+    DMA 転送待ち時間の間も SPE 内での処理を継続させる。</li>
+<!--</font>-->
+</ul>
+</div>
+
+<div class="slide">
+<h1>発表の流れ</h1>
+<ul>
+<font size="6" color="#000000">
+<li>Cell アーキテクチャの概要</li>
+<li>Cerium</li>
+<li>Rendering 部分の高速化</li>
+<li>比較</li>
+<li>まとめと今後の課題</li>
+</font>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Cell アーキテクチャの概要</h1>
+<ul>
+<font size="6" color="#000000">
+<li>Cell アーキテクチャの概要</li>
+<li><font color="silver">Cerium</font></li>
+<li><font color="silver">Rendering 部分の高速化</font></li>
+<li><font color="silver">比較</font></li>
+<li><font color="silver">まとめと今後の課題</font></li>
+</font>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Cell Broadband Engine</h1>
+<center>
+<img src="photo/Cell-main2.png" alt="pipeline" width="350" height="180">
+</center>
+<ul>
+<li>1 個の PPE と 8 個の SPE がリングバスで構成されている</li>
+<ul>
+<li>Linux 側から使える SPE は 6 個</li>
+</ul>
+<li>SPE は 256KB の Local Store (LS) を持つ</li>
+<li>SPE からメインメモリへ直接アクセスできない</li>
+<ul>
+<li>SPE が持つ MFC (Memory Flow Controller) へ DMA 命令を送ることで行う</li>
+</ul>
+<li>SPE は 128 ビットレジスタを 128 個持っている</li>
+</ul>
+</div>
+
+
+<div class="slide">
+<h1>Cell の基本機能</h1>
+<ul>
+<li><p class="ex4">DMA (Direct Memory Access)</p></li>
+DMA とは CPU を介さずにデータ転送を行う機能。
+<ul>
+<font size="5">
+<br>
+<li>SPE は LS(256KB) にしかアクセスできない。</li>
+<br>
+<li>メインメモリにアクセスするには、<br>MFC を通して DMA 転送命令を送る</li>
+<br>
+<li>LS にデータが転送されているあいだ、<br>SPE のプログラムは停止させたくない</li>
+<br>
+<li>SPE で処理したデータは MFC を介してメインメモリへ転送される</li>
+</ul>
+</font>
+</ul>
+
+
+<div class="slide">
+<h1>Cell の基本機能 (Con't)</h1>
+<ul>
+<li>DMA 転送には待ち時間が存在する。</li>
+<li>待ち時間の間 SPE 有効に使わなければ、マルチコアプロセッサのパフォーマンスが極端に下がる。</li>
+<ol>
+<font size="4">
+<li>Task のデータを読み込む (1)</li>
+<li>読み込んだデータの処理 (2) を行っている間に次の Task のデータを読み込む</li>
+<li>処理したデータの転送 (3) の間に、2 で読み込んだデータの処理、次の Task のデータの読み込みを行う</li>
+</font>
+</ol>
+<center>
+<img src="photo/pipeline.jpg" alt="pipeline" width="400" height="180">
+</center>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Cerium</h1>
+<ul>
+<font size="6" color="#000000">
+<li><font color="silver">Cell アーキテクチャの概要</font></li>
+<li>Cerium</li>
+<li><font color="silver">Rendering 部分の高速化</font></li>
+<li><font color="silver">比較</font></li>
+<li><font color="silver">まとめと今後の課題</font></li>
+</font>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Cerium</h1>
+PS3 ゲーム開発用フレームワーク
+<center>
+<img src="photo/Cerium.png" alt="Cerium" width="450" height="175">
+</center>
+<ul>
+<li>Scene Graph</li>
+<ul><li>ゲームに登場するオブジェクトやルールなど、ゲームを構成する要素をもつ木構造</li></ul>
+<li>Rendering Engine</li>
+<ul><li>Cerium 独自</li></ul>
+<li>Task Manager</li>
+<ul><li>Task と呼ばれる分割された各プログラムを管理するライブラリ</li></ul>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Scene Graph</h1>
+<center>
+<img src="photo/cerium_sg_tree.jpg" alt="sg" width="650" height="180">
+</center>
+<ul>
+<li>Blender <a class="footnote-reference" href="#id16" id="id15" name="id15">[1]</a>
+で生成したオブジェクトを独自の XML 形式で出力</li>
+<li>XML が持つ情報 (頂点座標、テクスチャ座標、イメージ) などから SceneGraphNode を生成</li>
+<li>ポリゴン情報の他に、オブジェクトの操作 (move、<br>collision) を持つ</li>
+</ul>
+<br>
+<font size="4">
+　　　　<a class="fn-backref" href="#id15" name="id16">[1]</a>オープンソースの3Dモデリングツール
+</font>
+</div>
+
+<div class="slide">
+<h1>Rendering Engine</h1>
+<br>
+<table>
+<tr>
+<td><img src="photo/rendering.png" alt="rendering" width="300" height="350"></td>
+<td>
+<ul>
+<li>SG2PP</li>
+SceneGraph を操作後、ポリゴンに変換し PolygonPack (ポリゴンの集合)を生成する
+<li>PP2SP</li>
+ポリゴンの中から、Span (ポリゴン内にあるx軸に水平な線分) を抽出し、
+SpanPack (Span の集合)を生成する
+<li>DrawSpan</li>
+Span を使って 1 ラインずつ FrameBuffer に描画していく
+</ul>
+</td>
+</tr>
+</table>
+</div>
+
+<div class="slide">
+<h1>Rendering Engine (Con't)</h1>
+<br>
+<center>
+<img src="photo/byouga.jpg" alt="byouga" width="600" height="400">
+</center>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Task Manager</h1>
+<center>
+<p class="ep1">Task と呼ばれる、分割された各プログラムを管理する</p>
+</center>
+<ul>
+<li>Task の単位はサブルーチンまたは関数</li>
+<li>Task 同士の依存関係を考慮する</li>
+<ul>
+<li>
+<pre>
+/* task2 は task1、task3 の終了を待つ */
+task2->wait_for(task1);
+task2->wait_for(task3);
+</pre>
+</li>
+</ul>
+<li>実行可能になった Task を各 SPE に割り振る</li>
+<ul>
+<li>
+<pre>
+/* SPE1で実行する */
+task1->set_cpu(SPE_1);
+/* SPEのどれかで実行する */
+task2->set_cpu(SPE_ANY);
+/* PPEで実行する  */
+task3->set_cpu(PPE);
+</pre>
+</li>
+</ul>
+<li>C++ で実装</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Rendering 部分の高速化</h1>
+<ul>
+<font size="6" color="#000000">
+<li><font color="silver">Cell アーキテクチャの概要</font></li>
+<li><font color="silver">Cerium</font></li>
+<li>Rendering 部分の高速化</li>
+<li><font color="silver">比較</font></li>
+<li><font color="silver">まとめと今後の課題</font></li>
+</font>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Rendering 部分の高速化</h1>
+<ul>
+<li>SPE の LS は256KB しかないので、Texture 情報を一度に転送すると容量を超えてしまう可能性がある。</li>
+<li>そこで、描画に必要な Texture データを分割、転送するという手法を用いる。</li>
+<br>
+<center>
+<img src="photo/cerium_rendering_tile.jpg" alt="pipeline" width="382" height="288">
+</center>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Rendering 部分の高速化 (Con't)</h1>
+<ul>
+<li>Tile Array を用いた Rendering</li>
+<ul>
+<li>Polygon の Span から、描画に必要な Texture A を含む Tile を計算する</li>
+<br>
+<li>Tile を SPE に転送し、Tile の中の pixel 情報 (RGBα値) を取得して描画を行う</li>
+</ul>
+<center>
+<img src="photo/Span-tile.jpg" alt="pipeline" width="500" height="265">
+</center>
+</ul>
+</div>
+
+<div class="slide">
+<h1>Scale</h1>
+<ul>
+<li><p class="ex1">Texture の縮小画像の作成</p></li>
+<ul>
+<li><p class="ex0">描画されるオブジェクトが小さい場合、そのままの大きさの Texture は必要ない</p></li>
+<li><p class="ex0">Span の長さと、縮小 Texture の大きさが一致するような Scale の縮小 Texture を選択する</p></li>
+<li><p class="ex0">Texture は縦横ともに 1/2、1/4、1/8 と、2分の1ずつ縮小させる (最小 8x8 pixel)</p></li>
+</ul>
+</ul>
+<center>
+<img src="photo/Scale.jpg" alt="pipeline" width="352" height="176">
+</center>
+</div>
+
+<div class="slide">
+<h1>Scale の効果検証</h1>
+<ul>
+<li>１０個のオブジェクトを用いたサンプル</li>
+<ul>
+<li>Polygon 総数 は 19860 </li>
+<li>Texture は合計 10 枚 <br>
+( 8x8(3)、512x384(2)、616x123(4)、1024x768(1) )</li>
+</ul>
+<center>
+<img src="photo/wakusei.jpg" alt="pipeline" width="428" height="321">
+</center>
+</ul>
+</div>
+
+<div class="slide">
+<h1>実行結果（速度検証）</h1>
+<br>
+<ul>
+<center>
+<table border="4">
+<tr>
+<th>Architecture</th>
+<th>Scale なし (FPS)</th>
+<th>Scale あり (FPS)</th>
+<th>速度の向上(%)</th>
+</tr>
+<tr>
+<th>Mac OSX</th>
+<td align="center">7.0</td>
+<td align="center">8.5</td>
+<td align="center">21</td>
+</tr>
+<tr>
+<th>PS3Linux (SPE 1)</th>
+<td align="center">4.3</td>
+<td align="center">5.6</td>
+<td align="center">30</td>
+</tr>
+<tr>
+<th>PS3Linux (SPE 6)</th>
+<td align="center">10.8</td>
+<td align="center">13.5</td>
+<td align="center">25</td>
+</tr>
+<caption>Scale を用いることによる実行速度の比較</caption>
+</table>
+</center>
+<li><p class="ex0">実行速度の比較を行った結果、<font color="#DD0000">20 ~ 30%</font> の速度向上が見られる。</li>
+<li>Mac OSX は SDL 経由で出力、PlayStation 3 は Frame Buffer へ直接出力している。</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>実行結果 (考察)</h1>
+<ul>
+<li><p class="ex1">SPE 1 個のときの速度と SPE 6 個のとき<br><br>の速度で<u>台数効果</u>が出ていない<p></li>
+<li><p class="ex1">考えられる原因</p></li>
+<ul>
+<li><p class="ex1">DMA 転送待ち時間が隠されていないため遅くなっている (Amdahl則)</p></li>
+</ul>
+<br>
+<li>Amdahl則：例えば SPE を 6 個使えたとしても、すべ<br>
+ての SPE に常に処理を行わせている状態を保たなけれ<br>
+ば、実行速度は著しく低下する。
+</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>キャッシュ</h1>
+<ul>
+<li>SPE 上の Texture データのキャッシュの有効性を検証する</li>
+<li>キャッシュを用いた場合と用いてない場合を SPE の数を変更して比較する
+(1920x1080の画像の表示をサンプルとして使用)
+</li>
+</ul>
+<br>
+<center>
+<table border="4">
+<tr>
+<th></th>
+<th>キャッシュ なし</th>
+<th>キャッシュ あり</th>
+</tr>
+<tr>
+<th>SPE 1 個</th>
+<td align="center">0.08 FPS</td>
+<td align="center">0.42 FPS</td>
+</tr>
+<tr>
+<th>SPE 6 個</th>
+<td align="center">0.59 FPS</td>
+<td align="center">2.54 FPS</td>
+</tr>
+<caption>キャッシュの有無による処理速度の比較</caption>
+</table>
+</center>
+
+<ul>
+<li>キャッシュ有りと無しとで処理速度の向上が見られる</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>他システムとの比較</h1>
+<ul>
+<font size="6" color="#000000">
+<li><font color="silver">Cell アーキテクチャの概要</font></li>
+<li><font color="silver">Cerium</font></li>
+<li><font color="silver">Rendering 部分の高速化</font></li>
+<li>比較</li>
+<li><font color="silver">まとめの今後の課題</font></li>
+</font>
+</ul>
+</div>
+
+<div class="slide" id="osmesa-gallium">
+<h1>比較 - OSMesa (Gallium)</h1>
+<ul class="simple">
+<li>先行研究 (神里)<ul>
+<li>現在 PS3Linux からは <font color="maroon">GPU にアクセスできない</font></li>
+<li><font color="maroon">frame buffer は使用できる</font> ため、OSMesa を使用</li>
+<li>OSMesa の機能の一部を SPE に乗せ、高速化に成功</li>
+<li>ソースコードの複雑化を招いた</li>
+<li>以降のメンテナンスや機能の追加、改良が困難と判断し、独自に Rendering Engine を持つことに</li>
+</ul>
+</li>
+<li>Gallium<ul>
+<li>OSMesa の Cell Driver</li>
+<li>OpenGL で動作</li>
+<li>PS3 上のゲーム開発において、レンダリングのみを SPE に実装するのでは足りない<ul>
+<li>ゲームに登場するオブジェクトの計算 (衝突判定等)</li>
+<li>Amdahl 則の問題</li>
+</ul>
+</li>
+<li>レンダリングだけでなく、ゲームオブジェクトも SPE で処理できるように
+しなければならない</li>
+</ul>
+</li>
+</div>
+<div class="slide" id="gallium-con-t">
+<h1>比較 - Gallium (Con't)</h1>
+<ul>
+<li>実行速度比較<ul>
+<li>出力解像度は 1920x1080</li>
+<li>地球のテクスチャを貼った球体のオブジェクトを表示</li>
+</ul>
+</li>
+</ul>
+<table width="90%">
+ <tr>
+   <td><div align="center" class="align-center"><img alt="com_gallium" class="align-center" src="photo/com_gallium.jpg" style="width: 340px;" /></div>
+</td>
+<td align="center"><font size="4">ポリゴン数 : 1984</font>
+<table border="1" class="small docutils">
+<colgroup>
+<col width="55%" />
+<col width="45%" />
+</colgroup>
+<tbody valign="top">
+<tr><td><font size="4">Gallium (SPE 6 個)</font></td>
+<td><font size="4">5.4 FPS</font></td>
+</tr>
+<tr><td><font size="4">Cerium (SPE 1 個)</font></td>
+<td><font size="4">2.5 FPS</font></td>
+</tr>
+<tr><td><font size="4">Cerium (SPE 6 個)</font></td>
+<td><font color="maroon" size="4">9.5 FPS</font></td>
+</tr>
+</font>
+</tbody>
+</table>
+    </td>
+  </tr>
+</table><ul class="simple">
+<li>Gallium には OpenGL API の機能が全て乗っているわけではない</li>
+<li>Cerium とのレンダリングの機能の違い<ul>
+<li>光源、アルファブレンディング、etc..</li>
+</ul>
+</li>
+</ul>
+</div>
+<div class="slide" id="opengl">
+<h1>比較 - OpenGL</h1>
+<dl class="docutils">
+<dt>OpenGL</dt>
+<dd>オープンソースの3Dグラフィックスプログラムインターフェース</dd>
+</dl>
+<ul class="simple">
+<li>変換行列、光源、カメラなどの API を実装</li>
+<li>親子関係の表現も可能</li>
+</ul>
+<p>Cerium での OpenGL の使用の問題</p>
+<ul class="simple">
+<li>SceneGraph の OpenGL の API にあわせるオーバーヘッド</li>
+<li>SceneGraph は自身の変換行列を持っている<ul>
+<li>SceneGraph 単体でオブジェクトの操作は可能</li>
+</ul>
+</li>
+<li>SceneGraph だけで問題ない</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>まとめと今後の課題</h1>
+<ul>
+<font size="6" color="#000000">
+<li><font color="silver">Cell アーキテクチャの概要</font></li>
+<li><font color="silver">Cerium</font></li>
+<li><font color="silver">Rendering 部分の高速化</font></li>
+<li><font color="silver">比較</font></li>
+<li>まとめと今後の課題</li>
+</font>
+</ul>
+</div>
+
+<div class="slide">
+<h1>まとめ</h1>
+<ul>
+<li><p class="ep1">Scale による DMA 待ち時間の有効活用と、SPE 上の Texture データのキャッシュの有 
+効性を証明できた</li>
+<li><p class="ep1">DMA 転送の待ち時間の無駄を十分に利用できていない可能性が出たので、さらに SPE 
+上で行う処理を増やし待ち時間の有効活用を目指す。</li>
+</ul>
+</div>
+
+<div class="slide">
+<h1>今後の課題</h1>
+<ul>
+<li><p class="ex1">SceneGraph の SPE 上での実行</li>
+<li><p class="ex1">プログラムコードの SPE 上での <br>On demand load</li>
+<ul>
+<li><p class="ep1">現在は予め全てのコードを SPE 上に置いておく必要がある</li>
+<li><p class="ep1">SPE のメモリ領域 (256B) を考えると好ましくない</li>
+</ul>
+</ul>
+</div>
+
+
+<!--
+<div class="slide">
+<h1>Textureの分割、Scale</h1>
+<ul>
+<li><font size="5" color="#000000">Textureの分割、Scale処理に用いるデータ構造</font></li>
+<font size="4">
+<pre>
+
+uint32 *tex_dest = (uint32*)manager->malloc(tile_size);
+
+// 1 / 2                                                                                                                                          
+for (int y = 0; y < tex_height; y += TEXTURE_SPLIT_PIXEL*2) {
+    for (int x = 0; x < tex_width; x += TEXTURE_SPLIT_PIXEL*2) {
+        for (int j = 0; j < TEXTURE_SPLIT_PIXEL*2; j+=2) {
+            for (int i = 0; i < TEXTURE_SPLIT_PIXEL*2; i+=2) {
+                tex_dest[t++] = tex_src[(x+i) + tex_width*(y+j)];
+            }
+        }
+    }
+}
+
+</pre>
+</font>
+</ul>
+<div class="handout">
+[any material that should appear in print but not on the slide]
+</div>
+</div>
+-->
+<!--
+<div class="slide">
+<h1>ハッシュテーブル</h1>
+<ul>
+<pre><font size="4" color="#000000">
+// ハッシュテーブル
+struct
+hashtable{
+  int tx_id; // Texture id                                                              
+  char* key; // キー
+};
+</font></pre>
+<pre><font size="4" color="#000000">
+// ハッシュ関数
+for(int i = 0; key[i]; i++){
+    //value += key[i] + 1;
+    value += key[i]*(i+1)*17 + 1;
+  }
+  return fmod(value, N);
+}
+</font></pre>
+</ul>
+<div class="handout">
+[any material that should appear in print but not on the slide]
+</div>
+</div>
+
+<div class="slide">
+<h1>ハッシュテーブル</h1>
+<pre><font size="3" color="#000000">
+// 登録、検索
+int
+hash::hash_regist(const char* key){
+  int hash = hash_function(key);
+  for(int i = 0; ; i++){
+    // 値が空のとき
+    if(table[hash].tx_id == -1){
+      table[hash].key   = (char*)key;
+      table[hash].tx_id = id_count;
+      id_count++;
+      printf("x : hash = %d, id = %d : %s\n"
+             , hash, table[hash].tx_id, table[hash].key);
+      return table[hash].tx_id;
+</font></pre>
+<div class="handout">
+[any material that should appear in print but not on the slide]
+</div>
+</div>
+
+
+<div class="slide">
+<h1>ハッシュテーブル</h1>
+<pre><font size="3" color="#000000">
+    // 検索keyが一致したとき
+    }else if(strcmp(key, table[hash].key) == 0 && table[hash].tx_id != -1){
+      printf("o : hash = %d, id = %d : %s\n"
+             , hash, table[hash].tx_id, table[hash].key);
+      return table[hash].tx_id;
+    }
+    printf("hash = %d  =>  ", hash);
+    hash = ((37*hash)^(11*i)) % N;
+    printf("%d\n", hash);
+  }
+}
+</font></pre>
+<div class="handout">
+[any material that should appear in print but not on the slide]
+</div>
+</div>
+-->
+<!--
+<div class="slide">
+<h1></h1>
+<ul>
+<li></li>
+</ul>
+<div class="handout">
+[any material that should appear in print but not on the slide]
+</div>
+</div>
+-->
+
+</div>
+
+</body>
+</html>
author	admin@mb22-no-macbook-2.local
date	Wed, 22 Apr 2009 10:52:50 +0900
parents
children	cbfd29809746