岡本 秀輔

本研究で使用している対話型アニメーションは、JavaScriptで書かれており、対話処理とアニメーションの描画処理を逐次的に処理していた。そのため、アニメーション内にあるキャラクタの数が増加すると、アニメーションの描画間隔が間延びする問題があった。そこで、本研究ではJavaScriptの機能の1つである、Web Workersを使用し、この対話型アニメーションの並列化を行う。そのとき、対話処理とアニメーションの描画処理の分割に注目した。本発表では、その並列化のアプローチと評価について報告する。

近年、多くの文書をPDF ファイルとしてインターネット上から取得することが容易となった。そこで、本研究ではその膨大な量の文書ファイルを自動的に分類する、ドキュメント分類アルゴリズムを提案する。そのアルゴリズムは各文書から複数の単語を抽出し、単語間の類似度をweb 検索エンジンによるAND 検索のヒット数を基準にして計算する。そして、求めた各単語間の類似度をクラスタ分析手法の一つであるK-平均法に適用させることで、文書ファイルの分類を行う。本発表では提案したアルゴリズムの詳細と、その精度を評価するために行った実験とその結果について報告する。

本研究では拡張現実感を利用したロボットシミュレーション環境を提案する.この環境では仮想ロボットを実空間内に擬似的に配置し動作させる.そして実空間に存在する音や光,実オブジェクトといった周辺環境と仮想ロボットのインタラクションを可能にする.これにより,ユーザは実ロボットを使うことによるリスクやコストを抑えつつ,実空間の環境をそのまま使ってロボットシミュレーションを行うことができる.また,本シミュレーション環境を利用した試作シミュレータを実装し,動作確認の実験を行った.試作シミュレータを使った実験結果から,実空間のオブジェクトと仮想ロボットのリアルタイムなインタラクションが可能であることを確認した.

近年、ソーシャルネットワーキングサービス (SNS) の中でも、Twitter は特に注目を集めている。我々は、Twitter のリアルタイム性の高さに着目し、Twitter に投稿されたメッセージの中から、文化祭を楽しむ上で有効な情報のみを抽出し、ユーザに提供するサーバを構築した。2010年度秋に行われた文化祭においてつぶやきを抽出して、出店、イベント内容で分類し、人気の単語と統計情報などを提供した。本発表ではこの結果を受けて、リアルタイム情報の収集と文化祭に有効な情報の提供において Twitter を使用することの有効性を考察する。

本発表では，ロボット制御を行うためのプログラミング環境を，小学校で使用した際の評価について述べる．本環境でのプログラミングは状態遷移図を用いたグラフィカルなプログラミングを基本とし，より直感的にロボット制御を行える環境にすることを目指している．本環境では2種類のプログラマが共同してロボット制御を行う．一方のプログラマはロボット設計を担当し，ロボットのパーツのオン・オフの組合せによって，状態遷移図の遷移条件となるイベントと各状態で行うためのアクションを定義する．他方のプログラマは定義されたイベントとアクションを用いて状態遷移図を構成することで，ロボットの動作指定を中心としたプログラミングを行う．小学校のパソコンクラブにおいて，本環境を使用して評価を行った．小学生には後者のプログラマとして，ロボット制御の課題に取り組んでもらった．本発表では，取り組んだ実験内容と結果の考察を中心に，本環境の評価について述べる．We evaluate a robot control programming environment in an elementary school. The programming in our environment is a visual programming which is written in terms of a state transition diagram. A diagram allows a user to describe a robotic behavior intuitively. Our programming environment is for two kinds of programmers. The first is a programmer who designs the robot and defines the actions and events to construct the diagram. The second kind of programmer writes a final robot control program. We tested our environment at the PC club in an elementary school. The students addressed the challenge of the robot control as a latter programmer. In this presentation, we evaluate our environment as well as the content of the challenge and its result.

本発表では,ロボット制御を行うためのプログラミング環境を,小学校で使用した際の評価について述べる.本環境でのプログラミングは状態遷移図を用いたグラフィカルなプログラミングを基本とし,より直感的にロボット制御を行える環境にすることを目指している.本環境では2種類のプログラマが共同してロボット制御を行う.一方のプログラマはロボット設計を担当し,ロボットのパーツのオン・オフの組合せによって,状態遷移図の遷移条件となるイベントと各状態で行うためのアクションを定義する.他方のプログラマは定義されたイベントとアクションを用いて状態遷移図を構成することで,ロボットの動作指定を中心としたプログラミングを行う.小学校のパソコンクラブにおいて,本環境を使用して評価を行った.小学生には後者のプログラマとして,ロボット制御の課題に取り組んでもらった.本発表では,取り組んだ実験内容と結果の考察を中心に,本環境の評価について述べる.

ロボットの動作を直観的にプログラムできる環境の研究を行っている．そのプログラムは状態遷移図で書かれ，マクロ機能を使用することで複雑な状態遷移図を階層的に記述できる．マクロ機能とは，状態遷移図の一部に名前をつけて，それを 1 つの状態として扱える機能である．そのため，ユーザは複雑な状態遷移図を容易に書くことができる．試作環境はレゴ社の MindstormsNXT を対象としており，本発表の例では直線上に並んだボールを色ごとに区別して，ボールを並べ替えるロボット制御プログラミングを示す．また，そのロボットの状態遷移プログラムと，それをロボット用に変換した Java プログラムを示すことで，複雑なロボット制御をいかに系統立てて記述できるかを考察する．We have been studying a robot programming environment in which users can describe a robot control program intuitively. The program is written in terms of state transition diagram. This environment allows for definition of higher-level macro actions in terms of state diagrams. By referring to a macro action as a state in a higher-level diagram, we can express complicated control procedures by hierarchical and rather simple diagrams. The target machine is the mindstorms NXT Robot developed by the LEGO group of companies. In our example, the robot distinguishes balls by color and sorts them in line. This presentation shows the state transition diagram for the example task as well as the Java program converted from the diagram. It also describes our consideration whether it is easier for users to describe a complicated robot control program.

ロボットの動作を直観的にプログラムできる環境の研究を行っている.そのプログラムは状態遷移図で書かれ,マクロ機能を使用することで複雑な状態遷移図を階層的に記述できる.マクロ機能とは,状態遷移図の一部に名前をつけて,それを 1 つの状態として扱える機能である.そのため,ユーザは複雑な状態遷移図を容易に書くことができる.試作環境はレゴ社の MindstormsNXT を対象としており,本発表の例では直線上に並んだボールを色ごとに区別して,ボールを並べ替えるロボット制御プログラミングを示す.また,そのロボットの状態遷移プログラムと,それをロボット用に変換した Java プログラムを示すことで,複雑なロボット制御をいかに系統立てて記述できるかを考察する.

状態遷移図を階層的に指定することにより,ロボットの動作制御を可能とするプログラミング環境を提案する.この環境でのプログラミングは,ビジュアルプログラミングとなるため,テキストベースのプログラミングを知らない子供でも使用でき,ロボットを自分の思うように動かしたい人すべてが対象ユーザとなる.試作環境は,レゴ社のMindstorms NXTを対象としている.本論文では,単純な例によるロボットプログラムの記述力について示し,実際のロボットコードへの変換例を示すことで,提案環境の有用性について述べる.

Webアプリケーションとして複数プレイヤー参加型RPGを簡易に作成するためのプログラミングツールについて述べる.このツールの設計目標は単純な指定でさまざまなRPGを作成できることである.プログラミングの初心者や小学生などもこのツールの対象ユーザに含めている.ツールはGUIエディタとコードジェネレータからなる.GUIエディタはRPGのキャラクタの動作を規定する状態遷移図を作成するためのものである.コードジェネレータは,ゲームを構成するためのC,PHP,JavaScript,HTMLなどのコードを状態遷移図から生成する.生成されたRPGは,Firefox,Safari,IEといったよく使われるWebブラウザで操作できる.RPGのプレイヤーがWebブラウザ上でクリックやキー入力を行うと,その結果がWebサーバに送られデータベースに記録される.その結果,プレイヤーの入力が,他のプレイヤーのアバタやプレイヤーと関連を持たないゲームキャラクタに影響を与えることができ,さらにそれが他のプレイヤーの画面に反映される.状態遷移図は特定のプログラミング言語には依存せずに動作を規定するための道具である.そして,その構造は単純なために簡単に学習できるとともに,ゲームキャラクタの振舞指定に適している.本報告では,ツールを用いて容易にWeb用のRPGを作成できる可能性について述べる.

Webページやプレゼンテーション用の簡易なアニメーションを作成するためのツールの要求は以前から存在し、様々なツールが提案されてきたが、生成結果の予想のしやすさについては十分に議論されていなかった。我々はr-θ座標上で動的にメッシュを構築しメッシュの存在をユーザに意識させずにワーピングさせる技法を考案した。この手法はアニメーションの生成結果がユーザにとって予想しやすく、尚且つある程度複雑な変形にも対応することができる。これをSPHINXと名づけ提案する。

Islay（アイラ） は，対話型アニメと我々が呼ぶ，コンピュータアニメを作成するツールである．対話型アニメとは，視聴者のキー入力やマウス入力によって登場するキャラクタに影響を与えることのできるアニメである．Islay のGUI エディタで状態遷移図と表示画像を指定することにより，アニメに登場するキャラクタの動きを指定する．状態遷移図をキャラクタの動作クラスと見なし，オブジェクト指向モデルに沿った形で対話型アニメを作成する．このツールはアニメ作成というその主たる使用目的のほかに，情報処理教育の教材としての一面も持つ．状態遷移図によるアニメ作成を通して，ものが動くロジックを学ぶことができ，遷移先の状態の選択や同一状態の繰返しなどの指定により，プログラミングの基本を学ぶことができるからである．本発表では，Islay を使って学ぶことのできるプログラミングの基本事項について明らかにする．Islay is a tool for authoring interactive animations. An interactive animation is one of computer animations, in which viewer's key input and mouse clicking could influence characters. An animation author specifies the behavior of characters with both state-transition diagrams and pictures using Islay GUI editor. The classical state-transition diagrams are treated as classes in object-oriented programming. And the author can create animations in the way of the modern paradigm of the object-oriented modeling. The tool works also as an educational material on computer science as well as a software which creates animations. Students can learn how things work, through the creation of animations by state-transition diagrams. And they can also learn the basic of programming by specifying selections and repetitions for state of things. This presentation shows the basic ability of programming, which students can obtain with using Islay.

アニメーションは，Web ページの例で代表されるように，情報伝達手段の重要な選択肢の1 つである．特に，キーやマウスなどのユーザ入力によって，表示内容が変化するような対話型のアニメーションは，ユーザの興味を引きつける．しかし，ひとたびこのような対話型アニメーションを作ろうとすると，芸術的な素養のほかに，プログラミング技術やグラフィックスの知識が必要となり，素人には敷居が高すぎる．そこで，我々は小学生の利用も視野にいれた，対話型アニメーション作成ツールの設計と実装を行っている．ユーザは，GUI エディタで状態遷移図と表示画像を指定することにより，オブジェクト指向モデルに沿った形で，アニメーションに登場するキャラクタの動きを決めていく．そして，インタプリタにより動作を確認し，トランスレータによりJava やJavaScript といった対象コードへの変換を行う．変換の際には，Java の内部クラスやJavaScript の関数ポインタを用いることで，状態遷移図と対象コードの対応関係を保たせている．副産物として，このツールは楽しみながら情報処理を学ぶための教材となる可能性がある．状態遷移図を作成して，その動きをイメージすることは，情報処理教育の導入に適している．また，アニメーションに対応する中間言語表現や，対象形式への変換例を見ることは，プログラミングを含めた次のステップの教育に役立つ．Animations provide an efficient means for presenting information as practiced on modern Web pages. Interactive animations are especially attractive, because these can show variable scenarios according to key and mouse inputs by viewers. Author of an interactive animation is required of two different abilities. One is the artistic imagination as any artistic work requires. The other is highly advanced knowledge and skill in programming and graphics. The latter requirement is a strong barrier for potential authors who have good imagination and no programming skills. In this paper, design and implementation of a tool for authoring interactive animations are reported. To make it intuitively comprehensible for non-programmers, the modern paradigm of object-oriented modeling and the classical state-transition diagram are employed. An animation is constructed as a collection of characters. Behavior of each character is specified by a state-transition diagram and pictures to express its appearance. The tool consists of GUI editors for diagrams and pictures, a built-in interpreter to test the animation, and a translator into target codes including Java and JavaScript. The translation mechanism keeps the coherency between diagrams and target codes, by utilizing inner classes in Java and function pointers in JavaScript. As a side effect, the present tool works also as an educational material for enlightening children on computer science. They may learn how to define dynamical objects while having fun with animations.

ソフトウェア分散共有メモリシステム構築のための，ホーム移動の一手法の提案と，その基本性能評価について述べる．提案手法は，ホームノードにおいて収集した，ページに対するread/writeのアクセス履歴を，ホーム移動の判定に用いる．ホームノードは，他の計算ノードからのページ要求や，ページへの変更データを受け取るたびに履歴を更新し，そのエントリ数が閾値を超えたところで，履歴を用いたホーム移動の判定を行う．本論では，提案手法の特徴，および既存の手法との違いを明らかにし，既存の手法を含めた基本的な性能評価について述べる．性能評価には，8台構成のPCクラスタと，SPLASH-2ベンチマークのいくつかを用いた．その結果，提案手法は，他の手法と同等以上の効果があり，ホームを固定した場合と比べて，最大で2.25倍の高速化を確認した．This paper describes a new moving home method for home-based software Distributed Shared Memory systems and its evaluations. In our system, a home node uses records for access to the shared page to determine the moving its role of home. Each time a home node receives a service request for the shared page from a non-home node, it records the node ID and the type of access. If the number of the access records exceeds the threshold of request counts, the home node decides whether the non-home node which sends the request is suitable for a new home node of the page. To evaluate our moving method, we have implemented a prototype of DSM system from scratch. The result of our performance evaluation using SPLASH2 benchmark programs shows that our method improved the performance of the system by 2.25 times over the fixed home node method.

命令フェッチ制御命令は従来から使われてきた分岐命令の置き換えとなるべく導入された命令である.分岐命令が次に実行すべき命令を指定するのに対して, 命令フェッチ制御命令は次にフェッチすべき命令群を指定する.さらに, この命令がメモリからフェッチされる際には, デコードすることなく, 他の通常の命令と区別されて, 命令群のプリフェッチに利用される.本報告では, この命令を用いた命令プリフェッチにより, いかに命令キャッシュのミスペナルティが削減されるかについて述べる.

キューマシン計算モデルは、式の木構造を幅優先に探索することで命令列を作り、式の中間結果をFIFOのキューに格納する計算モデルである。これまでにこの計算モデルの特徴を利用したスーパスカラプロセッサのモデル設計がなされてきた。本報告ではプログラム中の繰り返し操作・手続き呼び出しなどにおいて、データ順序の入れ替えやインデックス計算などを行う際に有用なデータ退避用のキューを導入した。まずキューマシン計算モデルに基づいたスーパスカラプロセッサの動作原理について説明し、続いてデータ退避用のキューについて言及し、PLD化を目指した設計・シミュレーションの結果について述べる。

命令フェッチをプログラム制御するための機構であるフェッチ分岐方式について述べる．この方式は，命令フェッチの動作を指定する命令の列をプログラム中に作り，実行時に演算命令などの命令と並列に処理を進めていく．基本的な性能評価の結果では，多くの分岐処理を他の命令実行とは並列に行えることが示され，1サイクルにフェッチする命令数を増やすことで，その性能を直接的に高められることが分かった．This paper describes a program controlled instruction fetching mechanism,which is called the Fetch Instruction Method.In this mechanism,the special instructions to control instruction fetching are inserted into programs.They are processed in parallel with the other types of instructions.The results of performance evaluations show that many of branches are processed in parallel,and the performance is moreimproved by only increasing the number of fetched instructions per clock cycle.

64ビットアーキテクチャの登場によって広大なアドレス空間が使用できるようになり、単一アドレス空間方式のオペレーティングシステムが研究されている。全てのプロセスが単一の仮想アドレス空間を共有するこの方式には、プロセス間でのデータ共有が効率良く実現できるという大きな利点がある。しかし、逆に、プロセス固有のデータを不正な参照から互いに保護するためには、単一の仮想アドレス空間上で保護領域の設定とアクセス制御を実現する必要がある。本稿では、キー/ロック方式を拡張した方式を、単一仮想アドレス空間上でのアクセス制御機構に適用する。

キューマシン計算モデルは、キューの先頭にあるオペランドを取り出して、演算を行い、結果をキューの末尾に挿入する形で計算を進めるモデルである。これまでにこの計算モデルの特徴を利用して、関数型言語における並列関数呼び出しを高速化する研究がなされて来た。本報告ではこれに対して、手続き型の高級言語を対象として、モデルを式の評価に適用し、手続き呼び出しによって作られる木をソフトウエア・スタックで管理するスーパスカラ・プロセッサの設計について述べる。まず、キューマシン計算モデルの概要と特徴についてまとめた後に、このモデルを指向する命令セットアーキテクチャ、デコードと命令発行の天理を説明する。ついで高速な切り替えを可能とするマルチスレッド実行および割り込み処理の可能性についてまとめる。

PN(Parallel Neuman)プロセッサは, 静的に機能別の機械命令レベルの並列性を抽出し, それを並列実効する小並列プロセッサである.本論文では, PNにおけるデータキャッシュミスの性能に与える影響について述べる.評価のため, データキャッシュのついたPNプロセッサをハードウェア自動合成システムにより回路合成しシミュレーションした.その結果PNのデータ転送と計算の並列実効によりキャッシュミスの影響が隠ぺいされ性能が向上することがわかった.

著者らは処理能力が大幅に低減するキャッシュミスを避けるため, プログラムにより1ワード単位で階層メモリ間を配置および転送制御するキャッシュメモリを持たない階層メモリシステムを提案している. このメモリシステムではタグメモリをもたないキャッシュメモリ相当のメモリ(すなわちメインメモリ同様に線形的なアドレスを持つ高速なメモリ)HMに, プログラムにより1ワード単位でデータ転送を行う. この操作によりHMをキャッシュメモリよりも更に効率的に利用することが可能になる. これによりキャッシュメモリよりも高速にデータをプロセッサに供給することが可能になることが期待される. 本稿では, 命令をパイプライン実行する本提案システムの評価を示す.

近年, プロセッサの性能は, クロック周波数の上昇, スーパースカラそしてスーパーパイプライン方式などの技術により大きく向上した。しかし, プロセッサのみが高速な処理能力を持っていても, メモリアクセスに時間がかかると, プロセッサではメモリの処理を待つという状態になる。つまり, プロセッサの性能向上だけでなく, 命令やデータをプロセッサへ供給するためのメモリアクセス処理時間の短縮も重要である。現在, メモリアクセス処理時間の短縮の方法として, キャッシュメモリシステムを利用したメモリの階層化が多く用いられている。しかし, キャッシュメモリシステム方式では, 各アプリケーションプログラムの性質を考慮せず, キャッシュメモリとメインメモリ間の内容を, 一定のアルゴリズムで行う。その結果, キャッシュミスが生じ, 必要な命令やデータをメインメモリからキャッシュメモリに転送するまでの間, プロセッサはストールしてしまう。そこでキャッシュメモリの代わりに, アプリケーションプログラムの性質を解析して, 階層メモリ間の命令及びデータの転送をプログラム制御することにより, メモリアクセスをより効率的かつ高速に行う。この方式を, ブログラム制御階層メモリシステムと呼ぶ。本稿では, メモリアクセスを効率的かつ高速に行うことができる, 命令とデータに関するプログラム制御階層メモリシステムを持つコンピュータを提案する。

互いに協調する細粒度オブジェクトによって構成されるオブジェクト/スレッドモデルのオペレーティングシステムにおいて, オブジェクトの柔軟な保護を実現する機構を提案する。オブジェクトとはデータとメソッドをカプセル化したものであり, スレッドとはプログラムコードの実行主体である。複数のオブジェクトが同一のアドレス空間上にマッピシグされ, それらのオブジェクトが提供するメソッドを複数のスレッドが利用する。そのため, 一様な手続き呼び出しの手順でオブジェクトを呼び出すことができるが, オブジェクトは同一のアドレス空間上で不当なアクセスから互いに保護されなければならない。したがって, アクセス権を規定しオブジェクト呼び出しを制御する機構と, 実行時の不正なメモリ参照を防止する機構とが必要である。本稿では, 前者について, キー/ロック方式に基づいた方式を提案する。

従来のタスクスケジューリングは、プロセッサ数を指定して行うため、そのプロセッサ数では効率よく実行できるが、他のプロセッサ数のコンピュータでは、実行できない場合がある。また、並列計算機が一般的になったときに、プロセッサ数に依存しないプログラムを配布する方法が確立されていない。これを解決するため本研究では、プロセッサ数に依存しないタスクスケジューリング技法を提案する。

並列度優先スケジューリングとは、並列度に依存しないタスクスケジューリング技法である。この技法は並列度に依存しないことにより、従来の並列度を指定するスケジューリングにあった 一度スケジューリングしてできた定並列プログラムは、他のプロセッサ数のコンピュータ上では実行できない場合が多い、将来的に並列コンピュータが一般的になったときの機械語プログラムとしての配布方法がない、という二つの問題点を解決している。しかし、この並列度優先スケジューリング技法は、ヒューリステイックであり、基準として用いている CP/MISF 法によるスケジューリングの実行結果を比較すると実行時間が悪い。そこで、並列度優先スケジューリングを改良する方法を論ずる。