二分決定グラフを用いた演繹データベースの結合処理
スポンサーリンク
概要
- 論文の詳細を見る
演繹データベースのボトムアップ質問評価においては, コストの大きな結合処理が多用されており, その結合処理の高速化のために, ハシシュ結合や並列化など様々な改良が試みられている. またボトムアップ評価時に現われる中間ファクトの記憶コストも無視できない問題である. 一方, 論理回路設計および設計検証の分野では, Akersが考案し, Bryantが効率的な演算法を示した, 二分決定グラフ(Binary Decision Diagram; BDD)と呼ばれる論理関数の記憶効率の良い表現が注目されている. これにより従来扱うことのできなかったサイズの論理関数の処理が可能になっている. 本稿では, 関係を論理関数に変換し, さらにBDDとして表現することにより, 演繹データベース質問処理中の中間ファクトを記憶効率良く表現し, BDD上の演算によりボトムアッブ質問評価する方法を示す. 推移的閉包の実験結果では, 従来のビットベクトルを用いたハッシュ結合による方法と比べ, BDDによる方法は記憶効率が良く, 多くの場合高速であるとの結果を得た.
- 一般社団法人情報処理学会の論文
- 1994-03-07
著者
-
安浦 寛人
九州大学大学院システム情報科学研究院
-
安浦 寛人
九州大学大学院システム情報科学研究科情報工学専攻
-
岩井原 瑞穂
京都大学大学院情報学研究科社会情報学専攻
-
岩井原 瑞穂
九州大学大学院システム情報科学研究院
-
安浦 寛人
九州大学 大学院 システム情報科学研究科
-
井上 裕策
九州大学工学部情報工学科
-
井上 裕策
九州大学 大学院 総合理工学研究科 情報システム学専攻
-
安浦 寛人
九州大学大学院 システム情報科学研究院
関連論文
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- 12.社会システムを支えるディペンダブルコンピューティング(時代をひらく電子情報通信技術-技術がもたらした変革,そして更なる飛躍-)
- 入力依存の遅延ばらつきを利用するDVSシステムにおける性能およびエリアオーバーヘッドの改善検討(低消費電力,集積回路とアーキテクチャの協創〜どう繋ぐ?どう使う?マルチコア〜)
- 緊密な産学連携に基づく自律的なICT人材育成の実践(情報システム教育コンテスト(3))
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- 6U-6 ウェーブレットに基づく音声認証システムの精度向上にむけて(ネットワーク応用,学生セッション,ネットワーク)
- C-12-9 ゲーテッドフリップフロップの多ビット結合によるレジスタの低電力化(C-12.集積回路,一般セッション)
- 大規模な産学連携による高度ICT人材育成に向けての取り組み
- RFIDタグを用いた安全で効率の良いデジタルネーミング社会について
- 1A1-K06 ラジコンカーを用いた計算機の動作原理教育
- 製造後にタイミング補正可能なオンチップバスアーキテクチャ(回路方式,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 90nm CMOS回路における遅延・電力ばらつきのゲート段数およびゲート幅依存性に関する考察(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 90nmCMOS回路における遅延および電力ばらつきの実測と解析(演算回路・ばらつきの測定,システム設計及び一般)
- AS-2-5 90nm CMOS回路における遅延及び電力ばらつきの実測(AS-2. ASPLA 90nmを用いたVLSIの研究開発,シンポジウム)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- Analysis of effects of input arrival time variations on on-chip bus power consumption (VLSI設計技術)
- Analysis of effects of input arrival time variations on on-chip bus power consumption (システムLSI設計技術)
- BOPに向けたビジネス戦略(2025年半導体デバイスの進化予測,デザインガイア2008-VLSI設計の新しい大地)
- 情報技術と社会の関係の再構築 (情報技術の新時代に向けて)
- ハードウェア/ソフトウェア・コデザイン : ソフトコアプロセッサによるシステム設計
- AI-1-6 ディペンダブルVLSI設計技術への挑戦(AI-1.デイベンダブルVLSIに向けて,依頼シンポジウム,ソサイエティ企画)
- ハッシュを用いたID照合における計算時間についての考察(セッション2)
- パネル討論 : システムオンシリコン時代に向けてどんなCADを作るべきか?
- パネル討論 : システムオンシリコン時代に向けてどんなCADを作るべきか?
- VLSI 設計教育の現状と将来
- タイミングエラーの予報を目的とするカナリアFFの挿入位置限定(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地)
- タイミングエラーの予報を目的とするカナリアFFの挿入位置限定(ディペンダブル設計,デザインガイア2008-VLSI設計の新しい大地)
- コデザイン環境におけるメタ記述からハードウェア/ソフトウェアコジェネレーション
- パフォーマンスを考慮したデータパス幅の最適化手法
- コデザイン環境におけるメタ記述からハードウェア/ソフトウェアコジェネレーション
- パフォーマンスを考慮したデータパス幅の最適化手法
- コデザイン環境におけるメタ記述からハードウェア/ソフトウェアコジェネレーション
- パフォーマンスを考慮したデータパス幅の最適化手法
- 出力品質を考慮した変数ビット幅最適化手法
- MPEG-2 AACデコーダ専用の組み込みシステムLSIの開発
- MPEG-2 AACデコーダ専用の組み込みシステムLSIの開発
- VDEC向けスタンダードセルライブラリの評価
- VDEC向けスタンダードセルライブラリの評価
- VDEC向けスタンダードセルライブラリの評価
- A-7-20 パストランジスタを用いたDES S-boxの実装評価
- 実行不能パスを考慮したHDL記述のプログラムスライシング・アルゴリズム
- 低消費電力化を目的とした Gated-Clock によるビット幅可変方式
- 識別可能な多値レベルを考慮したニューロンMOS論理素子設計手法
- 識別可能な多値レベルを考慮したニューロンM0S論理素子設計手法
- 新機能デバイスを利用した高集積システム設計技術
- デルタ遅延に基づくVHDL記述のスライシングアルゴリズム
- デルタ遅延に基づくVHDL記述のスライシングアルゴリズム
- UDL/IによるVLSI設計
- グループ化された仕様記述に基づくパイプライン・プロセッサの設計検証
- NeuMOSを用いたパラレルカウンタ型乗算器
- 2025年半導体デバイスの進化予測 : 集積回路研究会主催「LSIの未来を考える石垣ワークショップ」からの提言(2025年半導体デバイスの進化予測,デザインガイア2008-VLSI設計の新しい大地)
- 教育用32ビットマイクロプロセッサQP-DLXの設計における設計検証
- 2025年半導体デバイスの進化予測 : 集積回路研究会主催「LSIの未来を考える石垣ワークショップ」からの提言(2025年半導体デバイスの進化予測,デザインガイア2008-VLSI設計の新しい大地)
- 情報社会に生きる小中学生のための計算機の動作原理の教育
- フラッシュ・メモリを主記憶とするシステムのためのメモリ・アーキテクチャの検討
- フラッシュ・メモリを主記憶とするシステムのためのメモリ・アーキテクチャの検討
- フラッシュ・メモリを主記憶とするシステムのためのメモリ・アーキテクチャの検討
- マイクロプロセッサにおけるアーキテクチャレベルの低消費電力化手法
- ハードウェア/ソフトウェア・コデザインのためのソフトコア・プロセッサの検討
- VHDLによるソフトコア・プロセッサの設計
- 特定用途向け集積システム最適化手法
- システム・オン・シリコン時代の特定用途向けシステム設計手法
- 出力VHDLコードに透かしを埋め込むCADツールの不正コピー検知方式
- 90nm CMOS回路における遅延・電力ばらつきのゲート段数およびゲート幅依存性に関する考察(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- 90nmCMOS回路における遅延および電力ばらつきの実測と解析(演算回路・ばらつきの測定,システム設計及び一般)
- BOPに向けたビジネス戦略(2025年半導体デバイスの進化予測,デザインガイア2008-VLSI設計の新しい大地)
- システムLSI設計人材養成実践プログラムQUBEにおけるETSSの活用
- 通信品質を考慮したディジタル無線通信システムの低消費エネルギー化の検討(デザインガイア2006-VLSI設計の新しい大地を考える研究会)
- 通信品質を考慮したディジタル無線通信システムの低消費エネルギー化の検討
- CMOSプロセスにおけるゲート遅延ばらつき測定回路の提案(VLSI回路, デバイス技術(高速・低電圧・低消費電力))
- CMOSプロセスにおけるゲート遅延ばらつき測定回路の提案(VLSI回路, デバイス技術(高速・低電圧・低消費電力))
- アクティブビットを考慮した低電力データパス設計手法
- アクティブビットを考慮したバスの低電力化手法
- アクティブビットを考慮したバスの低電力化手法
- マルチタスク組込みアプリケーションの低消費エネルギー化のためのメモリ管理技術(消費電力1,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 製造後にタイミング補正可能なオンチップバスアーキテクチャ(回路方式,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- マルチタスク組込みアプリケーションの低消費エネルギー化のためのメモリ管理技術(消費電力1,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- 製造後にタイミング補正可能なオンチップバスアーキテクチャ(回路方式,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- マルチタスク組込みアプリケーションの低消費エネルギー化のためのメモリ管理技術(消費電力1,デザインガイア2007-VLSI設計の新しい大地を考える研究会-)
- AS-3-2 プロセッサベース組込みシステムの省エネルギー化を目的としたコード配置手法(AS-3.低消費電力設計技術とその応用,シンポジウム)
- AS-3-1 プロセスばらつきを考慮したSRAMセルの低消費電力設計手法(AS-3.低消費電力設計技術とその応用,シンポジウム)
- A-3-18 プロセッサベース組込みシステムの低消費電力化を目的としたクロックゲーティング命令に関する検討(A-3.VLSI設計技術,一般講演)
- CMOS回路におけるタイミング歩留り最大化のためのゲートサイジング手法の提案(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- CMOS回路におけるタイミング歩留り最大化のためのゲートサイジング手法の提案(耐ノイズ・ばらつき設計(1),システムオンシリコン設計技術並びにこれを活用したVLSI)
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- Non-uniform Selective Way Cacheの動的制御による組込みプロセッサの省エネルギー化(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- スキャンべース攻撃とその防御法に対する定量的なセキュリティ評価(ディペンダブル設計,デザインガイア2009-VLSI設計の新しい大地)
- スキャンベース攻撃とその防御法に対する定量的なセキュリティ評価(ディペンダブル設計,デザインガイア2009-VLSI設計の新しい大地-)
- 算術演算器を含む回路に対する高速なソフトエラー率評価手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- 算術演算器を含む回路に対する高速なソフトエラー率評価手法(ディペンダブルコンピュータシステムとセキュリティ技術及び一般)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(消費電力,組込技術とネットワークに関するワークショップETNET2009)
- シングルサイクルアクセス可能な二階層キャッシュアーキテクチャ(省エネ,組込技術とネットワークに関するワークショップETNET2009)
- スキャンパス攻撃を考慮した暗号LSIのテスタビリティ評価(フォールトセキュア・セキュリティ・2線2相回路のテスト,VLSI設計とテスト及び一般)
- 2.応用プログラム (重点領域研究 : 超並列原理に基づく情報処理基本体系)
- 大規模な産学連携による高度ICT人材育成に向けての取り組み
- RC-011 仮想キューによる高性能ハードウエアRTOSの実現(C分野:ハードウェア・アーキテクチャ,査読付き論文)
- メディア処理向けカスタムプロセッサにおける復号処理命令拡張の検討
- LSIテスタを用いたLSIの信号遅延の測定