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

作     者：吴昊 

作者单位：广西民族大学 

学位级别：硕士

导师姓名：宋晓宇

授予年度：2015年

学科分类：080902[工学-电路与系统] 0809[工学-电子科学与技术（可授工学、理学学位）] 08[工学] 

主      题：FPGA 板级路由问题 集成电路设计 可满足模理论 理论解决器 

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