8 0 0 0 複合長方形領域の最小分割
- 著者
- 大附 辰夫 佐藤政生 橘 昌良 鳥居 司郎
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.24, no.5, pp.647-653, 1983-09-15
- 被引用文献数
- 1
複合長方形領域を重複なく最小個の長方形に分割する問題を扱う.ここでは 複合長方形領域が中空部分(窓)を含んだり 複数個の連結成分から成っているような一般的な場合を考察する.分割手順は二つのアルゴリズムから成っている.1番目のアルゴリズムは 縮退していない複合長方形領域を最小個の長方形に分割するものである.同じXまたはY座標上の二つの凹点間が領域内であるとき 複合長方形領域は縮退しているといい そうでない場合には縮退していないという.2番目のアルゴリズムは 与えられた(縮退している)複合長方形領域を最適にいくつかの縮退していない複合長方形領域に分解するものである.複合長方形領域の頂点の数をnとすると 1番目のアルゴリズムの計算複雑度はO(n log n)となり 2番目のアルゴリズムはO(n^5/2)となることを報告する.ここで扱う問題は LSI のアートワーク処理 画像処理 図形データベースなどにおける基本的問題の一つである.
1 0 0 0 OA ラバーバンドモデルに基づいた逐次配線手法の実装
- 著者
- 粟島 亨 田中 博 福井 省三 佐藤政生 大附 辰夫
- 雑誌
- 情報処理学会研究報告システムLSI設計技術(SLDM)
- 巻号頁・発行日
- vol.1992, no.43(1992-SLDM-062), pp.229-243, 1992-05-27
径路トポロジーの標準形であるラバーバンド表現に基づいた単層2点間ネットに対する逐次配線手法を提案する.本手法はトポロジー的に存在する径路は必ず発見することができる.また,最終段階に行われる幾何学的変換処理によって,径路の押し退け,すなわち,shove asidingが自然に実現できる.本手法を可視グラフを基本探索構造として計算機上に実装し,いくつかの例題に適用することにより,その有効性を実証した.
1 0 0 0 スケッチレイアウトシステムにおけるBGAパッケージ配線手法
- 著者
- 柴田 修一 鵜飼 薫 戸川 望 佐藤 政生 大附 辰夫
- 出版者
- 一般社団法人 エレクトロニクス実装学会
- 雑誌
- 回路実装学会誌 (ISSN:13410571)
- 巻号頁・発行日
- vol.12, no.4, pp.241-246, 1997
- 被引用文献数
- 7
BGA (Ball Grid Array) パッケージの平面配線問題は, ピンーパッドのマッピング問題として定式化される。本論文では, 位相レイアウトモデルに基づいたスケッチレイアウトシステムにおけるBGA配線手法を提案する。提案手法は, 各配線を対角線上に存在するピンから離れたピン間を通過させることにより, 最大混雑度および最大配線長の減少を可能とし, 同一周上のピン列におけるピッチを通過する配線本数の差を1に抑えることができる。提案手法を計算機上に実装し, 評価した結果を報告する。
1 0 0 0 OA 複合長方形領域の最小分割
複合長方形領域を重複なく最小個の長方形に分割する問題を扱う.ここでは 複合長方形領域が中空部分(窓)を含んだり 複数個の連結成分から成っているような一般的な場合を考察する.分割手順は二つのアルゴリズムから成っている.1番目のアルゴリズムは 縮退していない複合長方形領域を最小個の長方形に分割するものである.同じXまたはY座標上の二つの凹点間が領域内であるとき 複合長方形領域は縮退しているといい そうでない場合には縮退していないという.2番目のアルゴリズムは 与えられた(縮退している)複合長方形領域を最適にいくつかの縮退していない複合長方形領域に分解するものである.複合長方形領域の頂点の数をnとすると 1番目のアルゴリズムの計算複雑度はO(n log n)となり 2番目のアルゴリズムはO(n^5/2)となることを報告する.ここで扱う問題は LSI のアートワーク処理 画像処理 図形データベースなどにおける基本的問題の一つである.
- 著者
- 田中 真 内田 純平 宮岡 祐一郎 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.46, no.6, pp.1383-1394, 2005-06-15
- 被引用文献数
- 11
演算器ごとに専用のローカルレジスタを持たせるレジスタ分散型アーキテクチャを用いると,レジスタ間データ転送を利用することによって配線遅延が回路の性能に与える影響を削減することが可能である.しかし,高位合成のスケジューリングの段階からフロアプラン情報を考慮する必要がある.本論文では,レジスタ分散型をターゲットアーキテクチャとし,(1) スケジューリング,(2) レジスタバインディング,(3) モジュール配置,の工程を繰り返し,(3) から得られたフロアプラン情報を(1),(3) の工程にフィードバックすることによって,解(合成結果)を収束させる高位合成手法を提案する.フロアプラン情報をスケジューリングに反映させるために,フィードバックされた配置情報とタイミング制約に基づいて,レジスタ間データ転送を利用することができるスケジューリング手法を提案する.また,レジスタ分散型に対応したレジスタバインディング手法を提案する.提案バインディング手法では,ローカルレジスタを入力側と出力側で区別し,出力側レジスタで可能な限りデータを保持することにより,総レジスタ数を削減する.提案手法により,フロアプランを考慮したレジスタ間データ転送を用いた回路を解として得ることが可能となる.計算機実験によって,提案手法の有効性を示す.By using a distributed-register architecture, we can synthesize the circuits with register-toregister data transfer, and can reduce influence of interconnect delay. In this paper, we propose a high-level synthesis method targeting a distributed-register architecture. Our method repeats (1) scheduling, (2) register binding, (3) module placement processes, and feeds back floorplan information from (3) to (1) in order to decide which functional units use registertoregister data transfers. Our scheduling algorithm can use register-to-register data transfer based on floorplan and timing constraint. We also propose a register binding algorithm on a distributed-register architecture. We show effectiveness of the proposed methods through experimental results.
- 著者
- 田中 真 内田 純平 宮岡 祐一郎 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人情報処理学会
- 雑誌
- 情報処理学会論文誌 (ISSN:18827764)
- 巻号頁・発行日
- vol.46, no.6, pp.1383-1394, 2005-06-15
- 参考文献数
- 13
- 被引用文献数
- 11
演算器ごとに専用のローカルレジスタを持たせるレジスタ分散型アーキテクチャを用いると,レジスタ間データ転送を利用することによって配線遅延が回路の性能に与える影響を削減することが可能である.しかし,高位合成のスケジューリングの段階からフロアプラン情報を考慮する必要がある.本論文では,レジスタ分散型をターゲットアーキテクチャとし,(1) スケジューリング,(2) レジスタバインディング,(3) モジュール配置,の工程を繰り返し,(3) から得られたフロアプラン情報を(1),(3) の工程にフィードバックすることによって,解(合成結果)を収束させる高位合成手法を提案する.フロアプラン情報をスケジューリングに反映させるために,フィードバックされた配置情報とタイミング制約に基づいて,レジスタ間データ転送を利用することができるスケジューリング手法を提案する.また,レジスタ分散型に対応したレジスタバインディング手法を提案する.提案バインディング手法では,ローカルレジスタを入力側と出力側で区別し,出力側レジスタで可能な限りデータを保持することにより,総レジスタ数を削減する.提案手法により,フロアプランを考慮したレジスタ間データ転送を用いた回路を解として得ることが可能となる.計算機実験によって,提案手法の有効性を示す.By using a distributed-register architecture, we can synthesize the circuits with register-toregister data transfer, and can reduce influence of interconnect delay. In this paper, we propose a high-level synthesis method targeting a distributed-register architecture. Our method repeats (1) scheduling, (2) register binding, (3) module placement processes, and feeds back floorplan information from (3) to (1) in order to decide which functional units use registertoregister data transfers. Our scheduling algorithm can use register-to-register data transfer based on floorplan and timing constraint. We also propose a register binding algorithm on a distributed-register architecture. We show effectiveness of the proposed methods through experimental results.
- 著者
- 小原 俊逸 史 又華 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)
- 巻号頁・発行日
- vol.107, no.506, pp.25-30, 2008-02-27
- 被引用文献数
- 5
本稿ではASIPを対象としたハードウェア/ソフトウェア協調合成システムにおける命令メモリビット幅削減に基づく低エネルギー化手法を提案する。VLIW型プロセッサは並列に命令を発行可能だが,命令メモリのビット幅が長くなり,消費電力・消費エネルギーを無駄に増加させてしまう.したがって,VLIW型プロセッサの命令メモリのビット幅の削減は,高性能でエネルギー効率の高いプロセッサを実現可能にすると考えられる.命令メモリのビット幅は命令エンコーディング形式に依存し,それはオペコードとオペランド群で構成される.オペコードのビット幅は命令セットにおける命令数に,オペランドのビット幅は汎用レジスタ数に依存する.また,我々はオペコードのビット幅を削減するために,結合命令の概念を導入した.結合命令は各VLIWスロットで同時に発行される複数の命令を1つの命令として取り扱った命令である.我々は,オペコードビット幅削減アルゴリズム,オペランドビット幅削減アルゴリズム,エネルギー最小化アルゴリズムの3つのアルゴリズムで構成されるASIP合成システムを構築した.実験結果では,メモリを含むプロセッサ全体で,9%〜12%の消費エネルギーを削減することを確認した.
- 著者
- 涌井 達彦 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)
- 巻号頁・発行日
- vol.100, no.473, pp.89-94, 2000-11-23
- 被引用文献数
- 13
本稿では, CAM(一致検索機能を有する機能メモリ)を使用したプロセッサを対象とするハードウェア/ソフトウェア協調合成システムを提案する.本システムではC言語で記述されたCAM機能を使用したアプリケーションプログラムおよび面積/時間制約を入力とし, 制約を満足するCAMとマイクロプロセッサユニットで構成されるCAMプロセッサの論理合成可能なハードウェア記述およびCAMプロセッサ上で動作するバイナリコードを出力する.本システムCAMの並列処理を担う各機能モジュールをハードウェアで実現するか, ソフトウェアで代替するかを分枝限定法により決定する.計算機上に実装した本システムにアプリケーションプログラムおよび時間制約を入力した結果, 制約を満足するCAMプロセッサのハードウェア記述およびバイナリコードが得られた.
- 著者
- 後藤 敏 大附 辰夫
- 出版者
- The Institute of Electronics, Information and Communication Engineers
- 雑誌
- 電子情報通信学会論文誌 A (ISSN:03736091)
- 巻号頁・発行日
- vol.J57-A, no.11, pp.810-817, 1974-11-25
グラフの特定の2節点間のパスの長さ,あるいはカットセットの値の最大・最小を求めることは,それ自体でも意味ある問題であるが,各種の問題の部分問題として現れるので極めて重要である.従来,解法としてラベリング法に基づくグラフ的手法と線形計画法で代表される代数的手法がよく用いられているが,二つの手法が全く独立な立場から論ぜられており,両者のギャップを縮めるための研究はあまりなされていない.本文ではこれらの問題をグラフの基本カットセット行列あるいは基本閉路行列によって表されるキルヒホッフの法則を用いて線形計画法で定式化し,シンプレックス法による解法と1対1に対応した新しいグラフ的手法を導き,これらの問題が統一的に扱えることを示した.更に,シンプレックス法における基底・枢軸変換・双対性・退化などの概念がすべてグラフ理論と対応づけられることが明らかになった.又,本文で提案した方法はパス,カットセットの最大・最小問題の一般解を求めることができるため,実用的価値が高いと思われる.
- 著者
- 本間 雅行 田村 亮 戸川 望 柳澤 政生 大附 辰夫 佐藤 真琴
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)
- 巻号頁・発行日
- vol.108, no.224, pp.7-12, 2008-09-22
近年のディジタル機器においては,多種多様で,膨大なデータを短時間で処理することが要求されている.このような要求に応える新たなアーキテクチャとして,多数の演算器を並列に動作させることができる再構成型プロセッサがある.ここでは,ディジタルメディア処理向け動的再構成プロセッサFE-GA(Flexible Engine/Generic ALU array)に注目する.現在,FE-GAの開発ツールに関してはまだ確立されていない.そこで本稿では,FE-GAへの設計を容易にし,開発コストを軽減するFE-GAマッピングアルゴリズムを提案する.このアルゴリズムは特定のデータフローグラフ(DFG)を入力とすることで,FE-GAへのマッピング結果を生成,変換し,FE-GA専用のアセンブリ言語を自動生成するものである.この自動生成したアセンブリ言語をFEEditorと呼ばれる専用ツールに読み込ませることでマッピング自動化を実現する.提案手法では,DFGの入力側から出力側に向かってレベル順にノードを一つ一つFE-GAの演算セルアレイに配置配線していく.最初にマッピングするノードを優先的に左上にマッピングすることとし,それ以降のノードは,マッピングしたいノードの入力データを出力するノードの位置により,その位置を決定する.この過程を繰り返すことでマッピングを実現する.8つのDFGに対し提案手法を適用しサイクル数および実行時間を算出した.すべてのDFGでマッピングを実現することができた.
- 著者
- 田中 真 内田 純平 宮岡 祐一郎 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. VLD, VLSI設計技術 (ISSN:09135685)
- 巻号頁・発行日
- vol.104, no.478, pp.127-132, 2004-11-25
- 被引用文献数
- 4
レジスタ分散型アーキテクチャを用いると,レジスタ間データ転送を利用することによって配線遅延が回路の性能に与える影響を削減することが可能であるが,高位合成のスケジューリングの段階からフロアプラン情報を考慮する必要がある.本稿では,レジスタ分散型をターゲットアーキテクチャとし,(1)スケジューリング,(2)レジスタバインディング,(3)モジュール配置,の工程を繰り返し,(3)から得られたフロアプラン情報を(1),(3)の工程にフィードバックすることによって,解(合成結果)を収束させる高位合成手法を提案する.提案手法により,フロアプランを考慮したレジスタ間データ転送を用いた回路を解として得ることが可能となる.また,計算機実験によって,提案手法の有効性を示す.
- 著者
- 松本 和也 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. ITS (ISSN:09135685)
- 巻号頁・発行日
- vol.108, no.171, pp.25-30, 2008-07-21
- 被引用文献数
- 5
携帯電話の高性能化・小型化により,GPSやナビゲーションシステムを用いた地図サービスの利用が拡大し,都市部から郊外部にわたって需要が増加すると考えられる.しかし表示画面が狭く処理能力の低い携帯端末で地図を表示させるには,携帯端末画面に適した略地図を生成する必要がある.本稿では,主に直線から構成される都市部だけでなく,直線・曲線を含む郊外部にも適用可能な略地図生成手法を提案する.提案手法は,エリア全体の道路ネットワークをいくつかのグループに分割し,各グループごとに間引き処理すると同時に直線化曲線化することで,都市部や郊外部に適応した略地図生成を図る.都市部と郊外部各10箇所の入力データを用いて提案手法を適用した結果,都市部ならびに曲線の多い郊外部でもデータ量削減と見やすい略地図が生成されることを確認した.
- 著者
- 山岸 敬弘 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. ITS (ISSN:09135685)
- 巻号頁・発行日
- vol.108, no.171, pp.31-36, 2008-07-21
- 被引用文献数
- 5
近年,携帯電話の普及に伴って移動通信サービスが大きく展開され,実用化が進んでいる.しかしながら実用段階まで進んでいる歩行者ナビゲーションサービスの研究は屋外環境に限ったものである.本稿では,屋外と比較して複雑な構造を持つ屋内環境におけるナビゲーションサービスに着目し,各ユーザに特化した最適な経路を提供することを目的として,ユーザの嗜好を反映させた経路探索手法を提案する.まず可視グラフを利用して対象とする屋内環境に特化したネットワークデータを提案する.次に,取り入れるべき嗜好項目を調査し,「最短経路」への要求は70%強,階段やエレベータ,エスカレータ等の「階層移動手段」に対し,特に高齢者から80%以上の要求があることを示す.これに加えて人混みを避けた経路に対し60%強の要求があった.そこで「最短経路」,「階層移動手段」さらに「混雑状況」という時間的因子を考慮した経路探索手法を提案する.提案手法の有効性を示すために実地調査を実施し,数種類に及ぶシミュレーション実験の結果から各ユーザにとって最適な経路が出力されることを示す.
- 著者
- 児島 伴幸 戸川 望 柳澤 政生 大附 辰夫
- 出版者
- 一般社団法人電子情報通信学会
- 雑誌
- 電子情報通信学会技術研究報告. ITS (ISSN:09135685)
- 巻号頁・発行日
- vol.108, no.171, pp.37-42, 2008-07-21
- 被引用文献数
- 5
GPSの普及により歩行者ナビゲーションシステムが可能になったが,都市部においてGPSは電離層やマルチパスなどの影響により数100m程度の測位誤差が生じる可能性がある.都市部において数100mの測位誤差は道路数本分の誤差に対応するため,歩行者に混乱を与えかねない.数m以下の測位誤差にするために,我々は既存インフラである道路標識と携帯カメラを用いたGPS位置補正システムを提案している.我々の提案では,携帯電話で受信したGPS座標からユーザの大まかな位置を把握し,携帯カメラで撮影した標識と地図データベースを照らし合わせ,詳細な位置を求める.GPS位置補正システムの中で重要なサブシステムの一つに道路標識認識システムがある.道路標識認識システムは,自動車向けのシステム開発が進行しているが,携帯電話向けのシステム開発はほとんど始まっていない.本稿では,我々のグループで開発を進めている2種類の道路標識認識システムを用い,実際に携帯カメラで撮影した画像を元に道路標識を解析し,撮影状況に依存した道路標識の認識度を調査する.とくに,夜間における携帯ライト・天候による逆光の影響が道路標識認識システムの認識度に変化を与えることを示した.