配線遅延を考慮した回路モデル上での加算及び乗算の計算複雑さ
スポンサーリンク
概要
- 論文の詳細を見る
ある問題を解くアルゴリズムの性能を評価するためには,その問題を解くために本質的に必要となる計算資源の量,すなわち問題の計算複雑さを知ることが重要となる.集積回路上での問題の計算複雑さを議論する殆どの研究においては,計算時間の評価において配線遅延を考慮していない.しかし,集積回路の微細化の進展に伴い,論理素子の遅延に対して配線遅延が相対的に増大している.従って,配線遅延を考慮した回路モデル上での計算複雑さを議論することが重要であると考えられる.本稿では,加算及び乗算について,配線遅延を考慮した回路モデル上での計算複雑さを示す.計算量の下界の評価の結果,配線遅延の影響が大きなモデルほど加算の計算量は大きくなったが,乗算の計算量には変化がなかった.計算量の上界の評価の結果,下界に近い計算量を実現する回路を示すことができた.
- 2009-02-26
著者
関連論文
- 超伝導単一磁束量子集積回路の技術動向と超伝導コンピュータの展望
- 複合算術演算の減算シフト型ハードウェアアルゴリズムの設計支援(VLSI設計技術とCAD)
- Nbアドバンストプロセスを用いた単一磁束量子浮動小数点演算器の設計(ディジタル,一般)
- テスト容易な並列プレフィックス加算器の設計手法(設計/テスト/検証,設計/テスト/検証)
- 投票無衝突化手法を用いた小面積画素並列ハフ変換回路(応用,組込技術とネットワークに関するワークショップETNET2009)
- C-8-10 SFQ浮動小数点乗算器の同期化および動作実証(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-9 アドバンスドプロセスを用いたSFQ半精度浮動小数点加算器の高速化に関する検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-13 Nb多層プロセスを用いて試作したシフトレジスタの測定評価(C-8.超伝導エレクトロニクス,一般セッション)
- オペランドの和を利用した小面積乗算器(演算器最適化,デザインガイア2008-VLSI設計の新しい大地)
- オペランドの和を利用した小面積乗算器(演算器最適化,デザインガイア2008-VLSI設計の新しい大地-)
- 全加算器で構成したマルチオペランド加算器のテスト生成(設計/テスト/検証)
- Nb多層デバイス構造用セルライブラリに向けた最適なモート構造の検討(単一磁束量子大規模集積回路技術の現状と将来展望、デジタル応用及び一般)
- パイプライン動作を考慮した単一磁束量子回路のための論理設計検証手法(ディジタル,一般)
- テスト容易な並列プレフィックス加算器の自動合成手法の検討(ディペンダブルシステム,組込み技術とネットワークに関するワークショップ ETNET2010)
- 投票高々1衝突化手法を用いた小面積画素並列ハフ変換回路の設計 (ディペンダブルコンピューティング)
- 投票高々1衝突化手法を用いた小面積画素並列ハフ変換回路の設計 (VLSI設計技術)
- オペランドの和を用いた並列乗算器の消費エネルギー評価(論理設計,デザインガイア2009-VLSI設計の新しい大地-)
- A-3-1 Sequential SATの高速化のためのm-Trieを用いた時間フレームを跨いだ状態併合(A-3.VLSI設計技術,一般セッション)
- C-8-14 可変遅延素子を用いた単一磁束量子可変長シフトレジスタ(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-6 10kA/cm^2Nbプロセス用単一磁束量子セルライブラリの構築(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-9 A^*アルゴリズムに基づく単一磁束量子回路受動線路配線ツールの実装と評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-10 2並列4段の再構成可能なデータパスを有する単一磁束量子回路の検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-11 SFQ半精度浮動小数点演算器の回路面積の削減に関する検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-12 SFQ半精度浮動小数点乗算器の試作と動作実証(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-21 単一磁束量子回路における2並列2段の再構成可能なデータパスの動作実証(C-8. 超伝導エレクトロニクス,一般セッション)
- C-8-18 SFQ半精度浮動小数点乗算器の設計と試作(C-8. 超伝導エレクトロニクス,一般セッション)
- C-8-16 アドバンストプロセス2.1を用いた2並列2段のSFQ-RDPの検討(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-15 10kA/cm^2Nbアドバンスドプロセスを用いたSFQ半精度浮動小数点乗算器の設計(C-8.超伝導エレクトロニクス,一般セッション)
- A-20-20 TLDP法の並列化による省メモリな連続単語音声認識回路(A-20. スマートインフォメディアシステム,一般セッション)
- A-3-11 テスト容易な並列プレフィックス加算器の設計(A-3. VLSI設計技術,一般セッション)
- C-8-5 10kA/cm^2Nbプロセスを用いたSFQ半精度浮動小数点加算器のコンポーネント回路の設計(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-2 単一磁束量子回路による冗長2進表現を用いたシストリックシリアル指数計算回路(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-1 単一磁束量子回路のためのパイプライン検証手法(C-8.超伝導エレクトロニクス,一般セッション)
- けた上げ保存加算器で構成された部分積加算部をもつ乗算器のテスト(ディペンダブルコンピューティング)
- C-8-17 SFQ半精度浮動小数点加算器の設計と試作(C-8. 超伝導エレクトロニクス,一般セッション)
- 投票高々1衝突化手法を用いた小面積画素並列ハフ変換回路の設計
- 再構成可能なデータパスに向けた単一磁束量浮動小数点除算器の実証(単一磁束量子大規模集積回路技術の現状と将来展望、デジタル応用及び一般)
- C-8-22 単一磁束量子回路のフロアプラン設計支援に向けた配線遅延時間の推定(C-8. 超伝導エレクトロニクス,一般セッション)
- SC-8-11 単一磁束量子マイクロプロセッサの開発(SC-8.超伝導SFQ回路技術の最近の進展)
- 順序回路の形式的検証におけるフォールスネガティブ削減のための回路変換(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- 多層配線単一磁束量子回路のための自動配線手法(単一磁束量子大規模集積回路技術の現状と将来展望、デジタル応用及び一般)
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 保存型一括並列処理による高速なHMM出力確率計算・最尤推定回路の構成法
- 単一磁束量子論理回路のための故障モデルとテストパターン生成手法の検討(信号処理基盤技術及びその応用,一般)
- バイアス電源の高電圧化による単一磁束量子回路の高速化の検討(信号処理基盤技術及びその応用,一般)
- 10kA/cm^2プロセスを用いた2並列2段単一磁束量子再構成可能なデータパスの動作実証(超伝導エレクトロニクス基盤技術及び一般)
- 10kA/cm^2Nb Processを用いたSFQ浮動小数点乗算器の50GHzでの動作評価(信号処理基盤技術及びその応用,一般)
- C-8-15 10kA/cm^2Nb Processを用いたSFQ浮動小数点乗算器コンポーネント回路の動作評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-14 10kA/cm^2Nbプロセスを用いたSFQ半精度浮動小数点加算器のコンポーネント回路の動作実証(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-12 アドバンストプロセスを用いたSFQ-RDP用コンポーネント回路の動作評価(C-8.超伝導エレクトロニクス,一般セッション)
- D-10-10 乗算器の種々の部分積加算部の順序故障テスト(D-10. ディペンダブルコンピューティング,一般セッション)
- 加算器の平均スイッチングエネルギーの解析的評価(低電力設計と回路設計技術,システムオンシリコンを支える設計技術)
- セル遅延モデルを用いた算術演算回路の信号遷移回数見積もり手法(システム設計・高位論理設計,システムオンシリコンを支える設計技術)
- TLDP法のパイプライン化による省メモリな連続単語音声認識回路
- TLDP法のパイプライン化による省メモリな連続単語音声認識回路
- A-3-6 Sequential SATにおける時間フレームを跨いだ状態併合(A-3.VLSI設計技術,一般セッション)
- オペランドの和を用いた並列乗算器の消費エネルギー評価(論理設計,デザインガイア2009-VLSI設計の新しい大地)
- A-3-5 拡張ユークリッド法に基づくGF(2^m)上の除算回路の剰余計算並列化による高速化(A-3.VLSI設計技術,一般セッション)
- 配線遅延を考慮した回路モデル上での加算及び乗算の計算複雑さ
- オペランドの和を利用した小面積乗算器(演算器最適化,デザインガイア2008-VLSI設計の新しい大地)
- A-3-6 Chen-Willonerアルゴリズムに基づく小面積並列乗算器について(A-3.VLSI設計技術,一般セッション)
- Karatsubaアルゴリズムに基づく小面積乗算器(VLSI設計技術とCAD)
- A-3-7 剰余計算並列化によるGF(2^m)上の高速拡張モンゴメリ乗算器(A-3.VLSI設計技術,一般セッション)
- C-8-13 10 kA/cm^2 Nbプロセスを用いたSFQ-RDPの45GHz動作(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-12 ISTEC 10 kA/cm^2 Nbプロセスを用いた単一磁束量子浮動小数点乗算器の改良と動作評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-17 単一磁束量子回路のためのマルチサイクルパスを考慮した遅延素子削減手法(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-16 SFQ論理回路のタイミング明示化表現法と論理シミュレーション(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-15 クロック入力が不要な論理ゲートを用いたSFQ論理回路の構成法(C-8.超伝導エレクトロニクス,一般セッション)
- A-20-1 投票無衝突化と投票空間アクセス局所化による小面積画素並列ハフ変換回路(A-20.スマートインフォメディアシステム,一般セッション)
- 多重高速保存型一括並列処理による省メモリな音声認識用HMM計算回路
- 多重高速保存型一括並列処理による省メモリな音声認識用HMM計算回路
- 投票無衝突化手法を用いた小面積画素並列ハフ変換回路(応用,組込技術とネットワークに関するワークショップETNET2009)
- 投票無衝突化手法を用いた小面積画素並列ハフ変換回路(応用,組込技術とネットワークに関するワークショップETNET2009)
- 投票無衝突化手法を用いた小面積画素並列ハフ変換回路(応用,組込技術とネットワークに関するワークショップETNET2009)
- 投票メモリへのアクセスを局所化した並列ハフ変換回路の構成法(応用,組込技術とネットワークに関するワークショップETNET2008)
- 投票メモリへのアクセスを局所化した並列ハフ変換回路の構成法(応用,組込技術とネットワークに関するワークショップETNET2008)
- 投票メモリへのアクセスを局所化した並列ハフ変換回路の構成法(応用,組込技術とネットワークに関するワークショップETNET2008)
- 投票メモリへのアクセスを局所化した並列ハフ変換回路の構成法(応用,組込技術とネットワークに関するワークショップETNET2008)
- 種々の部分積加算構造をもつテスト容易な乗算器の設計手法(ディペンダブルコンピューティング)
- SFQ回路を用いた高スループットなビットスライス乗算器 (超伝導エレクトロニクス)
- 二段階検証による順序回路の限定モデル検査の高速化手法(論理設計2,システムオンシリコンを支える設計技術)
- 単一磁束量子論理回路のためのタイミング故障のモデル化とテスト手法の検討(ディペンダブルシステム,組込み技術とネットワークに関するワークショップETNET2011)
- 単一磁束量子論理回路のためのタイミング故障のモデル化とテスト手法の検討(ディペンダブルシステム,組込み技術とネットワークに関するワークショップETNET2011)
- 多層配線単一磁束量子回路のための遅延余裕割り当てに基づく配線順序を考慮した配線手法(物理設計,システムオンシリコンを支える設計技術)
- DS-1-7 配線遅延を考慮した回路モデル上での算術演算の計算複雑さ(DS-1. COMP学生シンポジウム,シンポジウムセッション)
- 配線遅延を考慮した回路モデル上でのハードウェアアルゴリズムの評価(システムレベル設計,デザインガイア2008-VLSI設計の新しい大地)
- 配線遅延を考慮した回路モデル上でのハードウェアアルゴリズムの評価(システムレベル設計,デザインガイア2008-VLSI設計の新しい大地)
- 配線遅延を考慮した回路モデル上でのハードウェアアルゴリズムの評価(システムレベル設計,デザインガイア2008-VLSI設計の新しい大地-)
- C-8-4 SFQ論理回路からの時刻付き論理式の抽出手法(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-3 ISTEC 10kA/cm^2 Nbプロセスを用いた単一磁束量浮動小数点乗算器内のクロック供給法の改善と評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-1 Nb-9層アドバンストプロセスを用いて試作したシフトレジスタの測定評価(C-8.超伝導エレクトロニクス,一般セッション)
- SFQ回路を用いた高スループットなビットスライス乗算器(超伝導マイクロ波応用,信号処理基盤技術及びその応用,一般)
- 大規模SFQ回路のためのNb多層アドパンストプロセスの開発(超伝導エレクトロニクス基盤技術及び一般)
- 単一磁束量子回路の設計検証のための時刻付き論理式の等価性判定手法 (VLSI設計技術)
- 高位合成における潜在的並列性を利用した投機実行に基づくCDFG変換 (VLSI設計技術)
- SFQ回路を用いた2ビット・ビットスライス半精度浮動小数点乗算器の設計 (超伝導エレクトロニクス)
- C-8-10 10kA/cm^2Nbプロセスを用いたSFQ半精度浮動小数点加算器の設計と測定評価(C-8.超伝導エレクトロニクス,一般セッション)
- C-8-14 SFQ回路におけるJTLとPTL混合配線のための回路分割手法(C-8.超伝導エレクトロニクス,一般セッション)