集成电路逻辑优化并行处理方法转让专利
申请号 : CN201210525602.X
文献号 : CN103034758B
文献日 : 2015-03-11
发明人 : 邱建林 , 陈建平 , 顾翔 , 陈莉 , 潘阳 , 杨娜
申请人 : 南通大学
摘要 :
本发明公开了一种集成电路逻辑优化并行处理方法，并行处理在逻辑优化中所处的位置：将多输入输出逻辑矩阵划分成多个多输入单输出逻辑矩阵，然后将这些多输入单输出逻辑调度到处理结点上进行优化处理；所述优化处理是结合了逻辑优化过程中逻辑的规模和逻辑中各蕴涵项之间可以合并的几率，从而形成的并行处理调度算法；在逻辑优化并行处理的调度过程中进行分段，并在每个段内遵循优先调度处理时间较长的逻辑；集成电路逻辑优化并行处理中采用分配策略。本发明可根据集成电路逻辑函数的蕴涵项的项数和蕴涵项之间的关联度而设计的可提高集成电路逻辑优化的处理效率。
权利要求 :
1.一种集成电路逻辑优化的并行处理方法，其特征是：包括：
(1)将多输入多输出逻辑矩阵划分成多个多输入单输出逻辑矩阵，然后将这些多输入单输出逻辑调度到处理结点上进行优化处理；
(2)所述优化处理是结合了逻辑优化过程中多输入单输出逻辑的规模、以及多输入单输出逻辑中各蕴涵项之间可以合并的几率，从而形成的并行处理调度算法；在优化处理的过程中进行分段，并对每个段遵循优先调度处理时间较长的多输入单输出逻辑；逻辑优化处理过程的具体步骤如下：(a)对于划分过的多输入多输出逻辑，先考虑多输入单输出逻辑矩阵规模的影响对多个多输入单输出逻辑矩阵进行处理，也就是根据各个多输入单输出逻辑的规模，即多输入单输出逻辑中蕴涵项的数量numi，对这些多输入单输出逻辑进行分组；
(b)然后从规模较大的逻辑组到规模小的逻辑组分别进行处理；在各个逻辑组中，都是按照每个逻辑的各蕴涵项之间的关联度从大到小进行调度，关联度利用如下公式计算：其中cij表示每个逻辑中每个蕴涵项与其他蕴涵项可以合并的数量，ki是每个逻辑中cij的统计之和；
(c)对于judgei相同的逻辑来说，进一步利用每个逻辑中cij的统计之和值ki与多输入单输出逻辑中蕴涵项的数量值numi之比，对比值大的先进行调度，即公式：judge2i＝ki/numi；
(3)集成电路逻辑优化的并行处理过程中，对多输入单输出逻辑矩阵的分配策略为：根据处理结点资源的预期等待时间的长短，将多输入单输出逻辑优先调度分配到预期最先处于等待状态的处理结点资源上，也可以说是在负载均衡的基础上分配到完成代价最优的处理结点资源上，有表达式：其中Cp为该多输入单输出逻辑矩阵在处理结点p上的预期处理代价，α、β、γ分别为该多输入单输出逻辑矩阵在处理结点p上的资源代价Rcp、数据迁移代价DTcp和服务质量代价QoScp的权值，Extp为处理结点的预期完成时间，也就是处理结点预期处于等待状态的时间。
说明书 :
集成电路逻辑优化并行处理方法
技术领域
[0001] 本发明涉及一种集成电路逻辑优化并行处理方法。
背景技术
[0002] 由于在国内外期刊、会议论文、著作等中对集成电路逻辑优化并行处理中的任务调度的研究几乎是没有出现过的，因此就需要在研究并行处理调度算法和逻辑优化两个领域的基础上，结合逻辑优化中的特点，形成适用于逻辑优化的并行处理调度算法。
[0003] 随着EDA的发展，集成电路的逻辑函数变量数及状态数越来越多，而传统的逻辑函数化简方法，比如公式法、卡诺图法，已不再能满足优化集成电路的工作。公式法的不直观，导致难以确定化简思路和判定函数是否最简；而卡诺图法虽较比较直观，但它只是比较适合五个以下变量的函数，是以画图为基础的，因此不便于计算机的实现。近几年，随着VLSI芯片集成度的大大提高，一些优化方法被相继提出，其中具有代表性的算法大致可以分为两类：一类是先对最小项集合进行化简，从而获得本源蕴涵项(prime implicant)集合，然后再进行求解最小覆盖。另一类则不必求出全部实质蕴涵项，而是直接构建函数的最小覆盖。
[0004] 在逻辑问题研究领域中，美国加里福尼亚大学伯克利分校的Brayton与日本九州（Kyushu）大学的Sasao的研究是极具代表性的，而在逻辑优化领域中，日本的J.Butler和Shinobu Nagayama、台湾师大资讯工程研究所S.-S.Lin以及捷克斯洛伐克捷克科技大学的Petr Fiser的研究颇多。而在国内，中科院、清华大学、北京大学、浙江大学、上海交通大学、复旦大学、北京理工大学等著名高校的专家、学者也在逻辑设计自动化方面进行了大量的应用与研究，并且取得了引人注目的成果，从而在理论和应用方面推动了我国集成电路设计、加工和制造事业的发展。
[0005] 1952年Quine-McCluskey首次提出了最小化布尔函数的方法—Q-M法，其在功能上等同卡诺图法，但是该方法是根据真值表逐层逐项地比较并合并的表格法化简，这样可以有效地利用计算机处理问题。当逻辑变量变多时，最小项的数目也急剧增加，则需占用的内存就变多，朱幼莲提出用星积运算求质蕴涵素项，而用选择极值法求最小覆盖的方法，通过采用灵活的数据结构来重新组合化简步骤，进而大大节省存储空间，加快逻辑化简的速度。王忠林则介绍了一种可以化简复杂逻辑函数的方法——列表法，该方法是利用逻辑函数的最小项对相邻最小项进行合并，消去多余的变量因子，从而得到逻辑函数的最简式。管致锦提出的适合大变量逻辑函数最佳覆盖的改进Beister算法，是针对对最小列覆盖算法的相关规则，优先考虑含有效1多的列和含1较少的行。基于变换化简法，吕宗伟给出了一种改进的适用于局部逻辑网络优化的多级逻辑优化算法，该算法通过计算逻辑网络中门或连线处的无关项，迅速地获得最大允许函数集合，从而降低计算时间，并提高原算法的适用性。管致锦等人提出一种新的本源蕴涵项的生成算法，生成过程中遵循“最小孤立点优先”的原则，仅产生本源项子集来形成覆盖，使冗余项减少，从而有效地提高运算速度。在分析多输出逻辑函数最小化覆盖选拔算法的基础上，叶静提出了针对大规模逻辑函数优化的改进选拔算法，此算法利用相交迭代的思想，而大大提高处理速度，同时利用局部搜索的思想解决分支处理时内存占用率高、处理时间长等问题。
[0006] 而并行处理算法经过这么多年的发展，虽然各式各样、各有侧重的研究，大致可以分为数值计算和非数值计算两个方面。数值计算主要研究的是矩阵与多项式运算、矩阵特征值问题计算、线性与非线性方程组求解、微分方程数值解、最优化问题等基本数学问题。而非数值计算主要研究排序、选择、优化判定、电路设计、计算机辅助设计、神经计算、智能[5]
计算等，以及他们的实际应用 。而近些年来，并行处理的研究更强调在应用领域上的并行[3]
算法的研究 。在并行算法中，由于任务间的划分、分配与求解问题的规模和处理机的结构密切相关，因此在并行处理中能寻求到一个合理任务的分配方法将会使并行计算更有效地发挥，提高处理速度。而在国内外对于任务的调度分配算法的研究有很多。Min-min和Max-min算法是最为经典的任务调度算法，另外基于网格的任务调度算法还包括先出调度算法、遗传算法、神经网络算法等。S.Dutta提出了一种来计算一个存储单元的最佳存储调度方法，该算法最大限度地减少总的预期偏差。Wushou Sliamu提出了循环选择执行A-MM策略，即网格任务自适应调度策略(Adaptive Min-Min and Max-Min)。当调度的任务大小差不多时，调度系统选择Min-Min算法处理，反之则用Max-Min算法处理，该算法可提高在时间跨度等方面的性能。Etminani.K.和Naghibzadeh.M.综合了Min-Min算法和Max-Min算法的优点，形成了一种选择算法，当剩余任务中长任务多于短任务时，选择Min-Min算法，反之选择Max-Min算法调度，循环执行。郭创提出了基于“排序”的S-M-M算法按照每个独立任务在网格系统中的计算机上的平均执行时间，对任务进行降序排序，分成相等的几段，在段内采用Min-Min进行调度，从而避免过多的小任务先被集中调度到性能较好的计算机造成的性能较差的计算资源闲置的情况。蒋瀚洋等人提出了基于任务优先级的QoS guided Min-min算法，并通过仿真实验与Min-min算法、QoS guided Min-min算法进行分析比较，得到该算法更优，但是保留了对负载均衡问题的进一步提高。陈丽军提出的MMPRI算法，其考虑了异构环境执行时间的差异、任务所属用户的优先级、任务执行时间，而此算法有利于得到全部任务的最早完成时间的最小值。曾艳提出的主从式任务调度算法是利用求连通分量的方法把所有的任务划分成若干个组，再利用队列按组的形式将任务动态地分配给空闲从进程，这样在一定程度上能达到负载均衡、优化问题求解时间的目的。
计算等，以及他们的实际应用 。而近些年来，并行处理的研究更强调在应用领域上的并行[3]
算法的研究 。在并行算法中，由于任务间的划分、分配与求解问题的规模和处理机的结构密切相关，因此在并行处理中能寻求到一个合理任务的分配方法将会使并行计算更有效地发挥，提高处理速度。而在国内外对于任务的调度分配算法的研究有很多。Min-min和Max-min算法是最为经典的任务调度算法，另外基于网格的任务调度算法还包括先出调度算法、遗传算法、神经网络算法等。S.Dutta提出了一种来计算一个存储单元的最佳存储调度方法，该算法最大限度地减少总的预期偏差。Wushou Sliamu提出了循环选择执行A-MM策略，即网格任务自适应调度策略(Adaptive Min-Min and Max-Min)。当调度的任务大小差不多时，调度系统选择Min-Min算法处理，反之则用Max-Min算法处理，该算法可提高在时间跨度等方面的性能。Etminani.K.和Naghibzadeh.M.综合了Min-Min算法和Max-Min算法的优点，形成了一种选择算法，当剩余任务中长任务多于短任务时，选择Min-Min算法，反之选择Max-Min算法调度，循环执行。郭创提出了基于“排序”的S-M-M算法按照每个独立任务在网格系统中的计算机上的平均执行时间，对任务进行降序排序，分成相等的几段，在段内采用Min-Min进行调度，从而避免过多的小任务先被集中调度到性能较好的计算机造成的性能较差的计算资源闲置的情况。蒋瀚洋等人提出了基于任务优先级的QoS guided Min-min算法，并通过仿真实验与Min-min算法、QoS guided Min-min算法进行分析比较，得到该算法更优，但是保留了对负载均衡问题的进一步提高。陈丽军提出的MMPRI算法，其考虑了异构环境执行时间的差异、任务所属用户的优先级、任务执行时间，而此算法有利于得到全部任务的最早完成时间的最小值。曾艳提出的主从式任务调度算法是利用求连通分量的方法把所有的任务划分成若干个组，再利用队列按组的形式将任务动态地分配给空闲从进程，这样在一定程度上能达到负载均衡、优化问题求解时间的目的。
发明内容
[0007] 本发明的目的在于提供一种可根据集成电路逻辑函数的蕴涵项的项数和蕴涵项之间的关联度而设计的可提高集成电路逻辑优化的处理效率的集成电路逻辑优化并行处理方法。
[0008] 本发明的技术解决方案是：
[0009] 一种集成电路逻辑优化并行处理方法，其特征是：包括：
[0010] （1）并行处理在逻辑优化中所处的位置：将多输入输出逻辑矩阵划分成多个多输入单输出逻辑矩阵，然后将这些多输入单输出逻辑调度到处理结点上进行优化处理；
[0011] （2）所述优化处理是结合了逻辑优化过程中逻辑的规模和逻辑中各蕴涵项之间可以合并的几率，从而形成的并行处理调度算法；在逻辑优化并行处理的调度过程中进行分段，并在每个段内遵循优先调度处理时间较长的逻辑；具体的步骤如下：
[0012] (a)对于划分过的多输入多输出逻辑，先考虑逻辑规模的影响对多个逻辑进行处理，也就是根据各个多输入单输出逻辑的规模，即多输入单输出逻辑中蕴涵项的数量numi，对这些多输入单输出逻辑进行分组；
[0013] (b)然后从规模较大的逻辑组到规模小的逻辑组分别进行处理；在各个逻辑组中，都是按照每个逻辑的各蕴涵项之间的关联度从大到小进行调度，关联度利用公式：
[0014]
[0015] 其中cij表示每个逻辑中每个蕴涵项与其他蕴涵项可以并的数量，ki是每个逻辑中cij的统计之和；
[0016] (c)对于judgei相同的逻辑来说，进一步利用每个逻辑的可并规模和逻辑的规模之比，对比值大的先进行调度，即公式：
[0017] judge2i=ki/numi；
[0018] （3）集成电路逻辑优化并行处理中的分配策略：根据处理结点资源的预期等待时间的长短，将逻辑优先调度分配到预期最先处于等待状态的处理结点资源上，也可以说是在负载均衡的基础上分配到完成代价最优的处理结点资源上，有表达式：
[0019]
[0020] 其中Cp为该逻辑在处理结点p上的预期处理代价，α、β、γ分别为该逻辑在处理结点p上的资源代价Rcp、数据迁移代价DTcp和服务质量代价QoScp的权值，Extp为处理结点的预期完成时间，也就是处理结点预期处于等待状态的时间。
[0021] 本发明实现对集成电路多输入输出逻辑优化的并行处理的调度分配，调度分配多个多输入单输出逻辑，使逻辑有序地调度到资源空闲的结点上，最终达到资源的负载均衡，降低逻辑优化的并行处理时间。可根据集成电路逻辑函数的蕴涵项的项数和蕴涵项之间的关联度而设计的可提高集成电路逻辑优化的处理效率。
附图说明
[0022] 下面结合附图和实施例对本发明作进一步说明。
[0023] 图1是逻辑优化并行处理框架模型图。
[0024] 图2是集成电路逻辑优化并行处理任务调度算法流程图。
[0025] 图3是调度判定的处理框架图。
[0026] 图4-图11分别是对逻辑L1~逻辑L8处理示意图。
具体实施方式
[0027] 一种集成电路逻辑优化并行处理方法，包括：
[0028] （1）并行处理在逻辑优化中所处的位置：将多输入输出逻辑矩阵划分成多个多输入单输出逻辑矩阵，然后将这些多输入单输出逻辑调度到处理结点上进行优化处理；
[0029] （2）所述优化处理是结合了逻辑优化过程中逻辑的规模和逻辑中各蕴涵项之间可以合并的几率，从而形成的并行处理调度算法；在逻辑优化并行处理的调度过程中进行分段，并在每个段内遵循优先调度处理时间较长的逻辑；具体的步骤如下：
[0030] (a)对于划分过的多输入多输出逻辑，先考虑逻辑规模的影响对多个逻辑进行处理，也就是根据各个多输入单输出逻辑的规模，即多输入单输出逻辑中蕴涵项的数量numi，对这些多输入单输出逻辑进行分组；
[0031] (b)然后从规模较大的逻辑组到规模小的逻辑组分别进行处理；在各个逻辑组中，都是按照每个逻辑的各蕴涵项之间的关联度从大到小进行调度，关联度利用公式：
[0032]
[0033] 其中cij表示每个逻辑中每个蕴涵项与其他蕴涵项可以并的数量，ki是每个逻辑中cij的统计之和；
[0034] (c)对于judgei相同的逻辑来说，进一步利用每个逻辑的可并规模和逻辑的规模之比，对比值大的先进行调度，即公式：
[0035] judge2i=ki/numi；
[0036] （3）集成电路逻辑优化并行处理中的分配策略：根据处理结点资源的预期等待时间的长短，将逻辑优先调度分配到预期最先处于等待状态的处理结点资源上，也可以说是在负载均衡的基础上分配到完成代价最优的处理结点资源上，有表达式：
[0037]
[0038] 其中Cp为该逻辑在处理结点p上的预期处理代价，α、β、γ分别为该逻辑在处理结点p上的资源代价Rcp、数据迁移代价DTcp和服务质量代价QoScp的权值，Extp为处理结点的预期完成时间，也就是处理结点预期处于等待状态的时间。
[0039] 实例分析应用：
[0040] 有一个四输入八输出的逻辑函数F(x)，
[0041]
[0042] 转化为基于真值表的矩阵形式为
[0043]
[0044] 经过逻辑函数的划分处理后可得到8个4输入单输出矩阵Li(i=1,2....,8),[0045]
[0046]
[0047]
[0048] 根据逻辑优化并行处理调度算法的原理，可以得到以下的处理过程：
[0049] 对于8个四输入单输出逻辑，统计可以得到各逻辑的规模和各逻辑的k值。
[0050] 对 于 逻 辑 L1， 经 过 如 下 所 示 的 处 理， 可 得 num1=6，k1=4,
[0051] 对于逻辑L2，经过如下所示的处理，可得num2＝7，k2=5,
[0052] 逻辑L3，经过如下所示的处理，可得num3=6，k3=3,
[0053] 逻辑L4，经过如下所示的处理，可得num4=8，k4=6,
[0054] 逻辑L5，经过如下所示的处理，可得num5＝7，k5＝2,
[0055] 逻辑L6，经过如下所示的处理，可得num6=3，k6=2,
[0056] 逻辑L7，经过如下所示的处理，可得num7=5，k7=0，其中因为k7为0，说明此逻辑已经是最简形式的，所以逻辑不需要再分配到结点上处理，而直接留给主结点。
[0057] 逻辑L8，经过如下所示的处理，可得num8=4，k8=3,
[0058] 首先，根据num值对这8个逻辑排序分组，即得L4、L2、L5、L1一组，L3、L7、L8、L6第二组。然后对两个组分别处理。对于第一组中的四个逻辑，它们的judge值分别为先判断其中judge值为不为0，若为零则不参加处理，对于第一组中的四个逻辑，按照judge值由大到小将逻辑存放在调度队列中，但是L2和L5的judge值相同，那么比较它们的judge2的值，计算得到分别为 因此先调度L2，再调度L5、L1。
[0059] 同理处理第二组，但是L7的judge值为0，所以不需要处理，而第二组中实际只要处理三个逻辑，根据judge值由大到小调度，调度顺序为L8、L3、L6。