基于项重写的动态可重构系统建模与仿真框架.docVIP

基于项重写的动态可重构系统建模与仿真框架 摘要:可重构系统建模与仿真是一项复杂的任务.本文从可重构计算模式的基本特征出发,建立计算与通讯并重的生产者-消费者系统架构,并提取其数据、计算、通讯基本元素,解决运行时的调度和加载问题,形成基于项重写理论的动态可重构计算系统建模框架.最后指出基于本框架进行系统规范描述、系统设计和仿真验证的方法与步骤.并以实例说明了不同的调度策略产生满足不同规范的应用系统,显示了本框架的通用性. 关键词:可重构计算;项重写系统;建模;仿真;验证 A Modeling and Simulation Framework for Dynamic Reconfigurable Computing System using Term-Rewriting Abstract: Its difficult to model and simulate reconfigurable computing system. In this paper, a producer-consumer system architecture is suggested following the fundamental character of reconfigurable system. After considering its basic elements nature such as data, computation and communication, and investigating the runtime dynamic task state and task scheduling, the authors propose a general modeling and simulation framework based on term-rewriting theory for dynamic reconfigurable system. In the end, the way to define system specification, design task module, simulate and verify the implementation is illustrated with an example. The result that different scheduling strategies generate different systems shows the versatility of this modeling framework. Key words: reconfigurable computing; term-rewriting system; modeling; simulation; verification 1 引言可重构计算(Reconfigurable Computing)是一种新兴的时空域上的计算模式[1].在此之前有两种传统的计算方法.首先是使用软件编程,在通用处理器上串行执行各条指令,速度较低.其次是将算法实现到专用ASIC芯片上.直接在硬件上并行执行,速度快但电路不可改变,灵活性差.可重构计算模式填补了二者之间的空白.可重构计算系统通常含有大量的可编程硬件资源,运行时动态定制硬件使之匹配特定算法,具有比通用处理器更高的性能.因其高速计算能力和编程灵活性,可重构计算获得了越来越广泛的研究关注. 然而,可重构计算系统及应用设计是一项复杂而繁琐的工程.首先,系统架构多种多样[2].从计算单元考虑有位级、字级和混合级等不同粒度,从网络拓扑考虑有一维线性、二维网孔或交叉开关等不同连接方式.其次,应用设计发非常复杂.同样的功能需求不同的性能侧重甚至会产生完全不同的设计方案.支持多模块动态调度的快速系统仿真始终是可重构计算研究的难点.针对上述问题,我们提出了一种主处理器与重构硬件耦合的开放性可重构系统架构[3],进而基于项重写理论提出计算与通讯及动态任务调度一体化的系统级建模与仿真框架,并分析动态可重构系统的仿真验证问题. 项重写系统(Term Rewriting System,TRS)是一种与λ演算和图灵机具有相同计算能力的形式化演算模型[4].系统由项和重写规则组成,在规则的匹配、代入和替换的基础上进行演算.其运算过程显式可见,较Petri网、CCS等模型具有更清晰简洁的语义[5].通常用于描述具备局部性和并发性的系统,广泛应用于代数规范、函数式语言、自动理论证明等研究领域. TRS在计算机体系结构方面最成功的案例是Arvind和Shen的工作.他们在[6]中利用TRS理论指导带分支预测、乱序执行和多级流水的复杂微处理器的设计,在[7]中设计并验证了一种高速缓存一致性协议.在可