並列計算環境上の超大規模組合せ最適化基本技術の研究
并行计算环境下超大规模组合优化基础技术研究
基本信息
- 批准号:08458074
- 负责人:
- 金额:$ 2.43万
- 依托单位:
- 依托单位国家:日本
- 项目类别:Grant-in-Aid for Scientific Research (B)
- 财政年份:1996
- 资助国家:日本
- 起止时间:1996 至 1998
- 项目状态:已结题
- 来源:
- 关键词:
项目摘要
Efficient Algorithms are discussed for the very large combinatorial optimization problems emerging in the layout design for VLSI.The objectives of this project are as follows.(1) Formulate problems so as to make it possible to apply not heuristic algorithms but the optimum ones whose optimality are theoretically proven to then,(2) Formulate problems as goal programming problems to solve complicated combinatorial optimization problems,(3) Apply parallel processing techniques to reduce processing time.For attaining (1) and (2), in the research and development of algorithms for initial placement, placement improvement, global routing and detailed routing, the problems are formulated as linear or non-linear programming problems. This is because those problems are formulated as goal programming problems in order to optimize the conflicting objective functions such as electrical performances and layout size at the same time. To solve these problems the randomized algorithm is used and its performance is experimentally evaluated, The results show that it is likely that this technique generates better solution though the processing time is longer than before.To reduce the processing time, the area-division parallel processing is devised. This parallel processing consists of the division of the layout area and the net list, the layout process of the much smaller scale problems and the merge of the generated solutions. For attaining (3), a parallel processing platform is experimentally developed by using the Voyager and then it is evaluated. As a result, it is concluded that this platform is useful for our system.The layout system consisting of the placement and routing processes has not yet been developed. However, the performance of each process is independently evaluated by developing its own data input and output programs. In the near future, efforts must be concentrated to the development of the layout system so as to evaluate this system against actual benchmark data.
本文讨论了超大规模集成电路布图设计中出现的超大型组合优化问题的有效算法。(1)将问题公式化,以便能够不应用启发式算法,而是应用最优算法,其最优性在理论上已被证明,然后,(2)将问题公式化为目标规划问题,以解决复杂的组合优化问题,(3)应用并行处理技术,以减少处理时间。为了实现(1)和(2),在研究和开发初始布局算法时,布局改进、全局布线和详细布线,这些问题被公式化为线性或非线性规划问题。这是因为这些问题被公式化为目标规划问题,以便同时优化相互冲突的目标函数,例如电性能和布局尺寸。为了解决这些问题,采用了随机化算法,并对其性能进行了实验评价,结果表明,该方法虽然处理时间较长,但仍能得到较好的解。这种并行处理包括布局区域和网表的划分、小规模问题的布局过程和生成解的合并。为了实现(3),通过使用Voyager实验性地开发了并行处理平台,然后对其进行评估。因此,该平台对我们的系统是有用的。由布局和布线过程组成的布局系统尚未开发。然而,每个过程的性能是通过开发自己的数据输入和输出程序来独立评估的。在不久的将来,必须集中精力开发布局系统,以便根据实际基准数据对该系统进行评估。
项目成果
期刊论文数量(12)
专著数量(0)
科研奖励数量(0)
会议论文数量(0)
专利数量(0)
H.Oka and Y.Shiraishi: "A Look-Ahead Line-Search Router utilizing the Global Routes as Line-Search Directions" The Institute of Electronics, Information and Communication Engineers, Research Notes of VLD. 96-556. 71-78 (1997)
H.Oka 和 Y.Shiraishi:“利用全局路由作为线路搜索方向的前瞻线路搜索路由器”电子、信息和通信工程师协会,VLD 的研究笔记。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
島津一寿、白石洋一: "VLSI自動設計システムに於けるランダマイズドクラスタリングアルゴリズム" 情報処理学会、数理モデル化と問題解決研究会研究報告. 96-MPS-8. 25-30 (1996)
Kazutoshi Shimazu,Yoichi Shiraishi:“VLSI自动设计系统中的随机聚类算法”日本信息处理学会,数学建模和问题解决研究小组的研究报告96-MPS-8(1996)。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
K.Shimazu and Y.Shiraishi: "A Randomized Clustering Algorithm for VLSI Design Automation System" Information Processing of Japan, Research Notes of SIGMPS. 96-MPS9. 25-30 (1996)
K.Shimazu和Y.Shiraishi:《VLSI设计自动化系统的随机聚类算法》日本信息处理,SIGMPS研究笔记。
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
T.Nakamura and Y.Shiraishi: "A Model of the Placement and Routing Problem for Electronic Disign Automation and a Global Routing Algorithm Simultaneously Determining the Component Placement based on the Network Flow Method" Information Processing of Japan,
T.Nakamura 和 Y.Shiraishi:《电子设计自动化的布局和布线问题模型以及基于网络流方法同时确定元件布局的全局布线算法》日本信息处理,
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
中村琢八、白石洋一: "電子系の自動設計に於ける配置配線問題のモデル化と、ネットワークフローの手法に基づいて部品配置を同時に決定する概略配線手法" 情報処理学会、数理モデル化と問題解決研究会シンポジュウム. 96-MPS-12. 79-86 (1996)
Takuya Nakamura、Yoichi Shiraishi:“自动电子设计中布局和布线问题的建模以及基于网络流方法同时确定元件布局的原理图布线方法”日本信息处理学会,数学建模和问题解决研究小组研讨会96-。 MPS-12。79-86(1996)
- DOI:
- 发表时间:
- 期刊:
- 影响因子:0
- 作者:
- 通讯作者:
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
数据更新时间:{{ journalArticles.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ monograph.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ sciAawards.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ conferencePapers.updateTime }}
{{ item.title }}
- 作者:
{{ item.author }}
数据更新时间:{{ patent.updateTime }}
SHIRAISHI Yoichi其他文献
SHIRAISHI Yoichi的其他文献
{{
item.title }}
{{ item.translation_title }}
- DOI:
{{ item.doi }} - 发表时间:
{{ item.publish_year }} - 期刊:
- 影响因子:{{ item.factor }}
- 作者:
{{ item.authors }} - 通讯作者:
{{ item.author }}
{{ truncateString('SHIRAISHI Yoichi', 18)}}的其他基金
A Research on Computer Aided Design System for Embedded Software
嵌入式软件计算机辅助设计系统的研究
- 批准号:
23500033 - 财政年份:2011
- 资助金额:
$ 2.43万 - 项目类别:
Grant-in-Aid for Scientific Research (C)
相似海外基金
Hierarchical Geometric Accelerated Optimization, Collision-based Constraint Satisfaction, and Sensitivity Analysis for VLSI Chip Design
VLSI 芯片设计的分层几何加速优化、基于碰撞的约束满足和灵敏度分析
- 批准号:
2307801 - 财政年份:2023
- 资助金额:
$ 2.43万 - 项目类别:
Standard Grant
Feasibility Study of Biological Neural Networks Formations on a VLSI Chip
VLSI 芯片上生物神经网络形成的可行性研究
- 批准号:
9318328 - 财政年份:1993
- 资助金额:
$ 2.43万 - 项目类别:
Standard Grant
REAL-TIME VLSI CHIP FOR 3-D SURFACE RENDERING FOR CT & M
用于 CT 3D 表面渲染的实时 VLSI 芯片
- 批准号:
3498489 - 财政年份:1991
- 资助金额:
$ 2.43万 - 项目类别: