著者

木村 真也 鹿股 昭雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.81, no.12, pp.1241-1248, 1998-12-20

被引用文献数

1

---

コンピュータの内部構造と実際の動作を教育するための教材を開発した.開発した教材はTTL及びPLD(programmable logic device)中心に構成したボード型コンピュータである.特徴としては次の3点がある.(1)コンピュータの内部を逐次, 詳細に観測することができる.(2)学習者が独自の命令セットを設計し, 容易に実装することができる.(3)命令の実行制御方式を3種類用意しており, 選択してコンピュータシステムを構成することができる.本システムはコンピュータ教育のみならず, 大規模なディジタルシステム設計技術の教育への導入部の教材としても利用できる.本システムを実際の教育に利用したところ, 学習者がコンピュータの内部構造の理解と興味をいっそう増加するといったアンケート結果を得た.

著者

仲野 巧 ウタマ アンディ 板橋 光義 塩見 彰睦 今井 正治

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.78, no.8, pp.679-686, 1995-08-25

被引用文献数

10

---

本論文では,VLSI化によるリアルタイムOSの高性能化の手法を提案する.本手法では,リアルタイムOSの基本機能をハードウェアで実現し,周辺チップとして汎用マイクロプロセッサに接続することによって,システムコールの処理およびスケジューリングの高速化を実現する.この手法の有効性を確認するために,制御用リアルタイムOSであるμITRONの機能の一部をVLSIとして設計した.この設計を0.8μmCMOSプロセスを用いて論理合成した結果,現在の半導体技術を用いても容易にVLSI化できることが知られた.また,シミュレーションの結果,実現されたシステムコールのハードウェア処理が200ns以内で終了し,スケジューリングも600ns以内で完了することが知られた.本手法を用いて実現されたOSチップを適用することによって,非常に高性能なリアルタイムシステムを容易に実現できる.

著者

片山 紀生 佐藤 真一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.80, no.8, pp.703-717, 1997-08-25

被引用文献数

38

---

画像データに対する内容検索の実現法として, 特徴ベクトルを類似検索する方法が広く使われており, その高速化のためのインデックス構造が求められている. これまでにR^*-treeを用いる方法や, 新たに考案されたSS-treeを用いる方法が提案されているが, 本研究では, これらのインデックスよりも更に高速なインデックスとしてSR-tree (Sphere/Rectangle-Tree)を提案する. SR-treeの特徴は, 包囲球(bounding sphere)と包囲長方形(bounding rectangle)を併用する点にある. これまでにも, 包囲球はSS-treeで, 包囲長方形はR^*-treeで使われている. しかし, 本研究が行った実験によると, 次元が高くなった場合, 包囲長方形を用いる方法では1辺の長さと対角線の長さの差が大きくなるという問題があり, 包囲球を用いる方法では包囲長方形よりも体積が大きくなるという問題があることがわかった. そこで, SR-treeではこれらを同時に使用することによって, 高次元空間をR^*-treeやSS-treeよりもより効果的に分割することを可能にする. 評価実験を行った結果, CPU時間, ディスクアクセス回数, いずれの面についても, SR-treeがR^*-treeならびにSS-treeを上回ることが確認された.

著者

北嶋 暁 森岡 澄夫 島谷 肇 東野 輝夫 谷口 健一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.79, no.12, pp.1017-1029, 1996-12-25

参考文献数

15

被引用文献数

4

---

教育用CPU KUE-CHIP2を,各命令の意味を記述した要求仕様からRTレベルまで段階的に設計し,それをSFL記述に自動変換してハードウェア合成系パルテノンを用いて回路を得た.そして,その設計が正しいことを代数的手法に基づいた証明支援系を用いて完全に自動で証明した.自動で証明できた理由は,CPUでは,要求仕様も含め,各レベルの仕様が共通の基本関数(算術・論理演算,メモリの入出力)を用いて記述できる,CPUの正しさの証明では1命令ごとに正しく動作することを調べればよく,かつ1命令の実行では繰返しループを含まない,また,我々の開発した証明支援系では,項書換え,場合分け,整数上の論理式の恒真性判定などを一定の手順で自動実行する,扱う式の大きさが増大するのに対処した工夫をしている,などである.証明作業は,記述誤りに伴う再証明も含め2週間程度で行えた.CPUの命令数が増えても証明のための計算時間はそれに比例する程度ですむので,本実験の結果より,単一制御部をもつ非パイプラインCPUについては,本論文の手法により,その正しさの証明を,現実的な時間で自動で行うことが可能であると言える.

著者

小林 真也

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.79, no.2, pp.69-78, 1996-02-25

参考文献数

12

被引用文献数

9

---

マルチプロセッサシステムでは, 処理速度を最も速くするためにどのように各プロセッサにタスクを割り当てていくか, つまりタスクスケジューリングが重要な問題である. 実際のマルチプロセッサシステムのタスクスケジューリングではプロセッサ間の通信にも時間がかかり, 個々のタスクの処理時間のみならず, 通信時間も考慮しなければならない. 本論文ではこの問題に対する最適解への近似精度の高い一方法を提案する. 提案方式は, リストスケジューリングの一種であり, 各タスクの処理時間のみによって決定されるプレプライオリティと, タスクとプロセッサごとに求められる通信削減時間によりタスクプライオリティリストを決定する. 各タスクのプレプライオリティの値はそのタスクに依存する複数のタスク依存系列のうちの最長パスの長さである. また, 通信削減時間とは, 他のプロセッサで実行した場合に必要であるがプライオリティを求めようとするプロセッサで実行する場合には必要のない通信の時間である. 常微分方程式の数値解法の一つであるRunge-Kutta 法と, FFTの二つのプログラムを対象に, 完全網システムにおいて従来方式との比較を行い提案方式の優位性を示す. また, 不完全網システムに対しても提案方式が良好な割当てを行えることを示す. 更に, 乱数を用いて生成したタスク集合に対しても, 提案方式が優れていることを示す. また, 割当てに要する時間を実測し, 提案方式が問題の規模に対して多項式時間で解けることを示す.

著者

吉田 明正 前田 誠司 尾形 航 笠原 博徳

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.78, no.2, pp.162-169, 1995-02-25

被引用文献数

3

---

マルチプロセッサシステム上での粗粒度並列処理手法としてマクロデータフロー処理が提案されている.従来のマクロデータフロー処理では,粗粒度タスクが実行時にプロセッサにスケジューリングされるため,粗粒度タスク間で共有されるデータを集中型共有メモリに配置し,粗粒度タスク間のデータ授受は集中型共有メモリを介して行われていた.本論文では,共有メモリを介したデータ転送オーバヘッドを軽減するため,Doallループとシーケンシャルループの間で,ローカルメモリを介したデータ授受を行うデータローカライゼーション手法を提案する.本手法では,コンパイラが,Doallループとシーケンシャルループを配列データの使用範囲が等しくなるように整合して部分ループに分割し,データ転送量の多い(データの結び付きの強い)部分ループ集合を実行時に同一プロセッサにスケジューリングしてローカルメモリを介したデータ授受を行えるような並列マシンコードを生成する.提案手法を用いたコンパイラは,マルチプロセッサシステムOSCAR上でインプリメントされており,OSCARシミュレータ上での性能評価から処理時間が20%程度短縮されることが確認された.

著者

渡辺 貴史 村島 定行

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.79, no.3, pp.114-122, 1996-03-25

被引用文献数

19

---

ボロノイ図は勢力範囲図とも言うべきもので情報処理のさまざまの分野で重要な役割を果たしている. ボロノイ図を描く方法は母点間の垂直二等分線を描くのが一般的である. この方法では母点数をNとしてO(N)の計算時間がかかる. ここでは計算機画面上で多数の点を配置し, それぞれの点のボロノイ領域を色分けするアルゴリズムを提案する. この方法は与えられた母点に互いに異なる色を割り当てた後, その母点から近い画素順にどの母点の勢力範囲であるかを示す色を置いていくことで実現する. 既に色が置いてある場合はパスする. すべての画素にどの母点の勢力範囲であるかを示す色を置き終わるとボロノイ図が出来上がる. このアルゴリズムは整数演算に基づいているので丸め誤差などは影響しない. またボロノイ図の作成時間は母点の数に依存しない. 母点数2から4000の範囲で調べた結果, ほぼ一定の30秒であった. 距離を計算して, 最近接の母点を決定するS.K.Parui等の方法と比較すると, 母点数が10を超えると, ここで提案の方法が速くなることがわかった.

著者

石丸 知之 植村 俊亮

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.78, no.3, pp.349-357, 1995-03-25

被引用文献数

9

---

本論文では,オブジェクト指向データモデルを拡張した「多態オブジェクト」データモデルを提案する.多態オブジェクトモデルの目的は,マルチメディアデータを自然にデータベース内に表現することである.マルチメディアデータの一つの特徴は,実世界の実体の多用な表現である.多態オブジェクトモデルでは,実体をオブジェクトとして理解し,そのオブジェクトに複数の完結した表現を与えることのできるモデルを提案する.このようなオブジェクトを多態オブジェクトと呼ぶ.多態オブジェクトモデルでは,一つのオブジェクトが複数のインスタンスを表現としてもち得る.クラスはインスタンスの形式を定義する.同じオブジェクトの複数のインスタンスはクラス名で識別する.複数のインスタンスの属性が同一のスーパクラスで定義されているときには,その属性は同一の意味をもつとみなし,インスタンスの間で値を共有し一貫性を達成する.多態オブジェクトの実現例として,現在試作中のデータベース管理システム「沙羅」のアーキテクチャについて述べる.

著者

山名 早人 安江 俊明 石井 吉彦 村岡 洋一

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.77, no.5, pp.343-353, 1994-05-25

被引用文献数

4

---

本論文では,並列処理システム上ではFORTRANプログラムを高速に実行する方式として,多段の条件分岐に渡る先行評価を用いたプログラムの並列化と実行方式を提案する.従来,条件分岐を含むプログラムを並列化する手法がいくつか提案されている.先行評価を用いない手法としては,(1)タスクの最早実行条件求出法があり,先行評価を用いる手法としては,(2)スーパスカラプロセッサやVLIW計算機を対象とした条件分岐1段に限った先行評価方式,および,(3)特定のループを対象とした多段の先行評価方式,が提案されている.しかし,(1)最早実行条件を求めるのみでは十分な並列性が得られない.(2)1段の条件分岐の先行評価で得られる速度向上はたかだか2倍である,(3)適用対象が特定ループに限られる,という問題をもつ.これらの問題に対して,本論文では,プログラムをマクロタスクに分割し,マクロタスク間の多段の先行評価方式を一般的な並列処理システム上で定義する.そして,各々のマクロタスクについと,実行開始条件・制御確定条件・実行停止条件を用いたマクロタスクの実行制御手法を提案する.

著者

當山 孝義 堀口 進

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.77, no.11, pp.770-773, 1994-11-25

---

最大公約数(GCD)算出は数値計算,暗号や符号計算などの分野で用いられている基本的計算の一つであり,高速解法について盛んに研究されている.Chor-Goldreichアルゴリズムは最も速い並列アルゴリズムの一つであると考えられいるが,その動作は詳細に検討されていない.本論文では,LPRAMモデルの並列マシン上での並列GCDアルゴリズムの詳細な動作をエミュレータを用いて解析し,メモリアクセス遅延が大きな影響を与えることを確認した.

著者

八槙 博史 マイケル P. ウェルマン 石田 亨

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.81, no.5, pp.540-547, 1998-05-25

被引用文献数

17

---

近年の分散マルチメディアシステムならびにネットワークに関する研究において, QoS(Quality of Service : サービス品質)の割当ては主要な課題の一つとなっている.本論文では, QoSの割当てを動的な市場機構によって行う分散化アプローチについて論ずる.このアプローチでは, 各エージェントは自己のもつ居所知識および利益に基づいて行動を決定し, 各資源の価格は各々の市場における需給が均衡する点として決定される.エージェントによる需要とネットワーク状況は動的に変化するため, 各エージェントの決定は断続的に繰り返し変更される.市場価格は系全体での価値を反映しており, これに従うことで, 各エージェントが生産あるいは消費する資源の量は適切に割り当てられる.本論文では, 実際のネットワーク会合システムFreeWalkにおける帯域割当てのための市場モデルについて述べる.実験の結果, マルチメディアネットワークアプリケーションに対するQoSの割当てにおける動的な状況変化に対して, 市場に基づくアプローチが適切に動作することを示した.

著者

中津 楢男

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.76, no.6, pp.279-287, 1993-06-25

被引用文献数

3

---

本論文ではデータベースの並行制御に関する直列化可能性理論を扱っている.一般に与えられた実行履歴が直列化可能かどうかの判定はNP完全であることが知られており,直列化可能な実行履歴の部分集合で多項式時間で判定できるクラスがいくつか知られている.こうしたクラスは実際のスケージューラの構成に利用できるほか,任意のスケジューラの能力の上界を与える点から注目されている.本論文では直列化可能性判定のための新しい概念を与える.この概念によれば,直列化可能性判定が明解になるばかりでなく,これまで知られている主な結果を含んだより一般的な定理を証明できる.次にこの定理に基づいて,多項式時間で認識できる,従来知られているより広いクラスをいくつか提案する.最後に多項式時間で動作する先読みスケジューラが存在するかどうかの判定にもこの概念が適用できることを示し,そのような先読みスケジューラが存在するより広いクラスを与える.

著者

鈴木 偉元 西村 一敏 阪本 秀樹

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.80, no.3, pp.300-308, 1997-03-25

被引用文献数

13

---

本論文では, 高速応答性, 大容量性および経済性に優れたビデオサーバの構築をねらいとして, 磁気ディスク装置とMSS(Mass Storage System)を用いた階層化蓄積ビデオサーバの性能解析を行う. 本解析は, ビデオファイルをアクセス頻度の高いものから順に磁気ディスク装置へ配置する場合に, ビデオストリームの平均頭出し遅延に関するシミュレーション評価結果が目標値以下となるようにハードウェア構成とビデオファイル配置の最適値を明らかにする. 数値例を用いた解析では, ビデオファイルの先頭部を磁気ディスク装置, その後続部をMSSへ分割して蓄積するファイルを設けた場合, ビデオファイル配置にはビデオストリームの平均頭出し遅延を最小にする最適値が存在することが明らかにされた. また, 磁気ディスク装置のみで構成された蓄積装置と比較して, 階層化蓄積が経済性に優れるための磁気ディスク装置とMSSの蓄積単価比が定量的に示された.

著者

高玉 圭樹 中須賀 真一 寺野 隆雄

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.81, no.5, pp.514-522, 1998-05-25

被引用文献数

13

---

本論文では, 個々のエージェントが各々の判断基準(局所評価関数)を変更しながら行動する組織学習指向型分類子システム, および, そのシステムのための新たなマルチエージェント強化学習法を提案し, これらをCADの分野におけるプリント基板配置問題に適用した結果を報告する.以前からプリント基板配置問題では, 設計期間や生産コストを下げるために大域的に最適化を行う方法が数多く提案されているが, これらの方法は与えられた部品を専門家よりも効果的に配置できず, 最終的に残った本質的な部分を専門家にゆだねなければならない場合が多い.そこで, 本システムは大域的な視点で部品配置を決定する方法ではなく, エージェント(部品)間の局所的なインタラクションにより, エージェント自らが自分の部品位置を決定する方法を取り入れる.本システムを実規模のプリント基板に応用した結果, 次の知見が得られた.1)我々のシステムは専門家と同等の実行可能解を見出した.2)従来の強化学習よりも我々のシステムの方が, 試行回数と総配線長の観点において, ともに優れている.

著者

蜷川 繁 広瀬 貞樹 長谷 博行 米田 政明

出版者

一般社団法人電子情報通信学会

雑誌

電子情報通信学会論文誌. D-I, 情報・システム, I-コンピュータ (ISSN:09151915)

巻号頁・発行日

vol.80, no.11, pp.856-865, 1997-11-25

被引用文献数

3

---

Wolframはセルオートマトンを四つのクラスに分類することを提案したが, 特にクラス3とクラス4の分類が困難な問題となっている. 本論文ではパワースペクトルを用いたスペクトル解析による1次元セルオートマトンのクラス3とクラス4の分類方法を提案する. クラス3およびクラス4に分類されるすべての1次元2状態3近傍セルオートマトン(単純セルオートマトン)についてスペクトル解析を行ったところ, クラス3のセルオートマトンは白色雑音型の不規則な変化をするかあるいは不規則な変化をしている中で周期2の周期的な変化をする確率が高いのに対して, クラス4のセルオートマトンはセルオートマトン固有の周期で周期的な変化をする確率が高いことがわかった. 更に, より複雑な1次元3状態3近傍セルオートマトンおよび1次元2状態5近傍セルオートマトンから無作為に選んだセルオートマトンのうちクラス3またはクラス4と推測されるセルオートマトンについてスペクトル解析を行ったところ, 単純セルオートマトンの場合と同様の特徴をもったパワースペクトルが得られた. これらのことから, スペクトル解析は1次元セルオートマトンのクラス3とクラス4の分類に有効であると考えられる.