用于集成电路设计的多核并行最小代价流方法及装置

摘要

本发明属集成电路技术领域，涉及一种应用于集成电路设计自动化中的多核并行最小代价流求解方法及装置。该方法及装置基于非确定性事务模型来实现最小代价流的求解，易于算法设计和并行实现，并从理论上保证算法的正确性。该方法利用线程池及线程绑定技术降低线程创建释放以及线程调度的开销，提高并行的效率。本发明利用多核处理器技术来提升最小代价流求解的速度，用于包含任何数目处理器核的装置，具有很好的伸缩性。本发明可用于求解一大类集成电路设计自动化问题的多核并行实现。

主权项

一种用于集成电路设计的多核并行最小代价流方法，基于非确定性事务模型，其特征在于，其包括如下步骤：步骤1：将集成电路设计自动化问题转化为最小代价流问题；步骤2：修改最小代价流问题对应的网络图，增加地节点网络：在地节点网络中，首先生成多个地节点，使电路主输入节点和主输出节点均匀地与这些地节点相连，且每一个地节点所连接的主输入或主输出节点的数目小于某一个指定的阈值ntol，然后再增加一个地节点来连接已生成的多个地节点形成地节点网络；步骤3：为每个处理器核创建一个线程，并对最小代价流问题进行初始化；步骤4：对节点进行预处理，并将过剩流节点存储在全局队列中；步骤5：对于每个处理器核利用并行最小代价流处理网络图；其中，分步骤5.1：从任务队列中抓取一定的数量的过剩流节点；分步骤5.2：对于每一个过剩流节点进行二次检测确定其是否需要处理；分步骤5.3：对需要处理的过剩流节点进行推流或重标记操作；分步骤5.4：与其他处理器核进行同步；分步骤5.5：同步成功时，减小收缩因子，返回步骤4，进行下一轮的分配操作；否则返回分步骤5.1，开始检测全局队列并获取潜在的新的过剩流节点；步骤6：后处理最小代价流的结果得到集成电路设计自动化问题的解。