上海科技大学知识管理系统

一种基于图形处理单元(GPU)的逻辑重写加速方法，包括并行化基于AND-ANVERTER图形(AIG)的逻辑重写的子过程。基于AIG的逻辑重写的递归子过程被重新设计为非递归的，以为GPU提供足够的并行性。为了在GPU上并行替换步骤，本公开使用锁来保证互斥访问，这不可避免地损害了节点间并行的可扩展性。为了在大规模上充分利用节点间并行性，本公开提出了一种工作调度器，该工作调度器将具有不重叠的最大无扇出锥(MFFC)的节点添加到组，使得MFFC中的节点可以同时删除而没有冲突。为了同时创建和删除同一节点，本公开还提出了GPU友好的图形数据结构来支持这些并发操作。

A graphics processing unit (GPU)-based logic rewriting acceleration method comprising parallelizing sub-procedures of And-Inverter Graph (AIG)-based logic rewriting. A recursive sub-procedure of the AIG-based logic rewriting is redesigned to be non-recursive, to provide sufficient parallelism for a GPU. In order to parallelize a replacement step on the GPU, the present disclosure uses a lock to ensure mutually exclusive access, which inevitably damages scalability of inter-node parallelism. In order to fully utilize the inter-node parallelism on a large scale, the present disclosure proposes a work scheduler that adds nodes with non-overlapping maximum fan-out-free cones (MFFCs) to a group, such that nodes in an MFFC can be deleted simultaneously without a conflict. In order to simultaneously create and delete a same node, the present disclosure also proposes a GPU-friendly graphical data structure to support these concurrent operations.