现场可编程门阵列(Field-Programmable Gate Array,FPGA)是一类可编程集成电路,既能高效地实现电路设计又能灵活地改变电路架构,具有可重构的功能。动态可重构系统基于FPGA的动态重构特性,能够以有限的资源适应不同的计算需求,是硬件加速技术的有效解决方案。通过动态重构设计,大规模计算应用中的任务可以动态地分时复用硬件资源。任务的重构次序和重构位置会影响系统运行的性能、重构资源的利用效率和任务之间的通信代价,需要对任务进行有效的调度和布局。针对现有的FPGA架构,本文对动态可重构系统中相互耦合的划分、调度和布局问题进行了研究,建立了调度和布局的问题模型,提出了相应的优化算法。为了表示动态可重构系统中的任务调度和布局,本文提出三元序列组(Se-quence Triple)的表示方法。三元序列组由三个同时集成时域和空域划分的任务嵌套序列PS、MS、RS构成。(PS,MS)为混合嵌套序列对(Hybrid Nested Sequence Pair),表示所有重构区域在各个调度时刻的任务布局。通过求解混合嵌套序列对的最长公共子序列,能够计算出任务位置坐标。RS为重构序列,表示所有重构区域中任务的配置先后顺序。将重构序列和任务数据依赖关系相结合,可以构建重构约束图(Reconfigurable Constraints Graph),表示动态重构过程中任务的优先约束关系。通过求解重构约束图中到顶点的最长路径,能够计算出任务配置时刻和执行时刻。在动态可重构过程中,任务调度和布局必须满足硬件资源约束和任务数据依赖关系。本文给出了可行任务调度和布局的充要条件,可以确立三元序列组完整的可行解空间。本文设计的优化算法基于模拟退火算法(Simulated Annealing),能够同时优化调度和布局。根据三元序列组的表示特征,本文采用删除插入的扰动方法:从三元序列组中随机删除一个任务,将所删除的任务插入三个删除后的任务序列中新的合适的位置。不同的插入位置对应不同的调度和布局解。通过枚举和评估可行插入位置,能够跳过很多调度和布局结果较差的解。在扰动过程中,本文采用增量式评估方法,能够在线性时间复杂度内评估所有可行插入位置所对应的调度和布局解。本文实验验证了调度和布局算法的有效性和高效性。实验结果表明,本文所提出的算法能够对调度和布局的进行集成优化,可以在保证较好调度效果的同时,提高布局成功率。并且对于实验测试用例中任务并行度较低的计算应用,能够明显降低动态重构过程中的重构时延。相比于未优化通信代价的情况,本文所提出的算法实现了对通信代价的优化,但求解时间会相应增加。并且对于任务数据依赖关系越多的实验测试用例,通信代价的优化效果越好。