基于空间管理器和适配器的可重构设备在线放置
2023,31(2):277-283
摘要：为了实现可重构设备上的模块/组件的在线放置,提出了一种基于空间管理器和适配器的在线放置策略。对于空间管理器,提出管理可重构设备上的已占用空间,而不是空闲空间,这样将更快地通过使用已占用的空间来查找到可以放置新组件的空闲位置集,具体实现是计算出相对于设备和每个已放置组件的IPR,从而得到IPR集。然后通过从总的设备区域中减去IPR集来得到可以放置新组件的空闲位置集；对于适配器,首先计算能得到最佳放置路由成本的点即放置新模块的最佳点,然后检查该点是否属于PPR集,如果是,则得到问题的解,否则,就寻找接近最佳点最近可能的位置,并选择它作为最佳放置位置；实验结果表明,提出的空间管理器和适配器相比于目前常用的几种放置方法不仅有更低的复杂度,而且有更低的装配时间。
关键词：可重构设备;在线放置;空间管理器;适配器;位置集;复杂度;路由成本;适配时间
On-line Placement of Reconfigurable Devices Based onSpace Manager and Fitter
Abstract：In order to implement the on-line placement of module/component on reconfigurable devices,an on-line placement strategy based on space manager and fitter is proposed.For the space manager,it is proposed to manage the occupied space rather than the free space on the device,so that the occupied space will be used more quickly to find the set of free places where the new component can be placed.The concrete implementation is to calculate the IPRs relative to the device and each placed components so as to get the set of IPRs,and then the set of free places where the new component can be placed is obtained by subtracting the set of IPRs from the total device area.For the fitter,the point at which the placement routing cost is optimal,namely the best point to place the new module,is first calculated,and then the point must be checked if it belongs to the PPR set,and if so,the solution to the problem is obtained,if not,the nearest possible position to the optimal point will be found and it is selected as the best placement position.Experimental results show that the proposed space manager and fitter not only have lower complexity but also lower fitting time compared with several methods commonly used at present.
Key words：reconfigurable device; on-line placement; space manager; fitter; position set; complexity; routing cost; fitting time
收稿日期：2022-10-12
基金项目：内蒙古自治区内蒙古工业大学大学生创新创业训练计划项目（2022193009）； 湖北省自然科学基金(2019CFC888) 。
