FPGA板级路由问题的SMT方法研究

【摘要】：FPGA板级路由问题是电路设计环节中的一个重要问题,它主要解决的问题是当把一个大规模电路设计划分成多个模块,并把多个模块封装到多个FPGA芯片中之后,如何用多个多端网把每个FPGA芯片按特定要求链接起来,实现信息路由通常的问题。而面对集成电路规模的增长,使得问题规模越来越大,如何高效解决FPGA板级路由问题是该领域的一个研究热点。本文通过对该问题的研究,提出了一种基于可满足模理论(Satisfiability Modulo Theories,简称SMT)的方法来解决该问题。经过对该问题和SMT的深入研究,本文主要取得了以下成果：建立了FPGA板级路由问题的算术模型,并转化成SMT表达式,最后用SMT解决器求解；提出了一种约化该问题的方法,通过约减多端网的数量,以到达缩减问题规模的目的,并用SMT方法求解。实验表明,采用SMT方法具有更高的解决问题效率,具备处理更大规模问题的能力；此外约减方法对基于SMT方法的计算效率有一定的提高。
【关键词】：FPGA 板级路由问题 集成电路设计 可满足模理论 理论解决器
【学位级别】：硕士
【学位授予年份】：2015
【分类号】：TN791