电路的多项式模型及其在元件匹配中的应用

摘要

超大规模集成电路的飞速发展,使人们越来越多的考虑利用已设计好的电路模块来加速系统设计,即设计重用问题.随着可重用模块数目的增长,搜索和分配可重用模块也变得越来越复杂.如何选择合适的元件来实现系统芯片设计是目前面临的重大难题之一.本文中提出的改进的符号多项式模型方法能在一定程度上解决这一难题.它能把组合电路和时序电路的位级描述的设计规范表示成字级多项式.这种方法有助于多项式模型的化简.对时序电路,通过确立其等效的组合电路,理论上也可以解决,但过程非常复杂,本文仅就此做一些简单的探讨.用本文改进的方法确立电路的多项式模型后,再利用Grobner Basis理论可以解决元件匹配问题.首先求出元件库的多项式表示生成的理想,然后求出该理想的Grobner Basis.由于已有的串行匹配算法在进行多项式的分解时,时间复杂度太高,于是本文在共享主存多指令流多数据流MIMD编程模型下,提出了一种并行算法.该并行算法从两个方面对原来的算法进行并行化.一方面是基于分组策略的粗粒度并行算法,另一方面是细粒度并行化简算法.随后对串并两种算法的复杂性进行了分析和比较.接下来还指出了算法需要进一步改进的地方.最后给出本文的结论.

目录

文摘

英文文摘

哈尔滨工程大学学位论文原创性声明

第1章绪论

1.1 EDA的发展及SOC的出现

1.2 SOC设计的特点

1.3设计模型的发展现状

1.4 SOC设计方法学的发展趋势

1.5课题的研究意义

1.6本文的主要内容及结构安排

第2章组合电路的多项式模型

2.1概述

2.2位级多项式表示

2.2.1相关的几个基本定理

2.2.2求多项式表示的算法

2.2.3多项式表示的计算

2.3多元函数的扩展

2.4误差量化

2.5实验结果

2.6本章小结

第3章时序电路的多项式模型

3.1 概述

3.2时序非循环电路

3.3时序循环电路

3.4逼近

3.4.1逼近的计算

3.4.2计算逼近误差

3.5实验结果

3.6本章小结

第4章多项式模型在元件匹配中的应用

4.1概述

4.2基本符号代数理论

4.2.1几个基本的概念

4.2.2除法运算

4.2.3 Grobner Basis理论

4.3串行分解算法

4.4串行算法分析

4.5并行分解算法

4.5.1并行算法模型

4.5.2细粒度并行化简算法

4.5.3基于分组策略的粗粒度并行算法

4.6两种算法的解析与比较

4.7算法还需要进一步改进的地方

4.8本章小结

结 论

参考文献

攻读硕士学位期间发表的论文及取得的科研成果

致 谢