境界配置条件を課したVLSIモデルにおける面積時間複雑度

概要

論文の詳細を見る
VLSI回路においては，回路の占める面積と計算時間が重要な評価尺度である．Thompsonや Brent，KungらはVLSI回路を面積Aと計算時間Tで評価するVLSIモデルを提案した．このVLSIモデルにいくつかの現実的な仮定を付加したとき，面積や計算時間がどのように変化するかを考察することは重要な問題である．本論文では，入出力は回路の周辺で行うという仮定（以下，境界配置の仮定と呼ぶ）をVLSIモデルに付け加えたとき，自明でないn入力m出力論理関数のクラスに対して，AT＝Ω（max（n，m）），ATα＝Ω（max（n，m） [max（logN，logM）]α）（α＞1）となることを示す．ここでNはNiをi番目の出力が依存する入力数としたときのN1，…，Nmの最大値であり，MはMjをj番目の入力変数に依存する出力数としたときのM1，…，Mnの最大値である．境界配置の仮定を課さないときには，同じ関数のクラスに対して，ATα＝Ω（max（n，m） [max（logN，logM）]α－1）（α1）となるので，この関数クラスに対しては，境界配置の仮定がATα（α＞1）に真に影響を与える．また，この下界を達成する関数が存在することを実例をあげて示す．
Institute of Electronics, Information and Communication Engineersの論文
1985-08-00