【作者】 李春生；

【导师】 周学海；

【作者基本信息】 中国科学技术大学 ， 计算机系统结构， 2014， 博士

【摘要】 可重构技术综合通用和定制两类计算的优势,提供灵活高效的运算性能。多核片上系统在单芯片中集成多种功能单元,满足多样化应用需求。两者相结合的可重构多核片上系统兼顾计算灵活性与运行效率,发挥多核计算的资源优势,利用硬件可编程性,有效满足嵌入式领域不同的应用需求。上述系统在设计和应用中亦存在不少挑战。应用的灵活性和内核的多态性很难构建归一化的抽象模型；硬件加速的高效性会带来划分、调度及分配等一系列普遍认为或已被证明是NP完全或NP难的问题；资源的分时复用特性增加了管理、布局、碎片等多约束条件。因此,可重构及多核片上系统协同优化算法的研究在提升系统运算性能、增强应用可靠性等方面具有必要的现实意义。本文针对可重构及多核片上系统软硬件协同应用,以优化计算性能为主要目标开展研究。首先抽象多核片上系统和可重构多核片上系统的基础框架,归纳影响系统性能提升的主要约束因素。其次结合国内外研究现状,给出相应的软硬件协同算法。最后分析算法的时空复杂度及性能优化效果。本文主要工作和特色如下：(1)在分析国内外典型多核片上系统和可重构多核片上系统的基础上,结合多态计算及下一代通用处理器特征,构建出一体的系统框架结构。同时结合输入任务类型、主要制约因素及性能提升目标,抽象一致的约束条件和优化模型。(2)针对多核片上系统软硬件协同优化,在分析影响其运算性能的任务间依赖关系、通信代价及处理器分配等约束的基础上,提出贪心划分插入调度的GPISM算法。该算法借助于贪心划分策略,选取关键硬件路径和最长软件通路；依据系统的约束条件和优化目标,将余下零散任务插入到对应的处理器核中调度执行。GPISM算法具有多项式时间的复杂度和较小的空间开销。(3)针对可重构技术硬件分时复用的特点,在分析影响系统性能和资源利用率的布局管理、放置方式及碎片度量等约束的基础上,提出VHF硬件布局管理策略。该策略包括：节省存储开销的顶点位置树VPT数据结构；减少时间开销的高权重占角优先HWC布局方式及灵巧的跳步搜索方法；降低计算成本的碎片外形边FSE度量函数。在此基础上衍生出针对永久故障的FT-VHF容错管理策略。本文所提出的硬件布局管理及容错策略以较低的时空复杂度达到高效的资源利用率和低成本的系统可靠性。(4)针对在线型和离线型任务特征,在分析可重构多核片上系统协同优化中受截止期限、任务依赖性等约束的基础上,提出VHF-Online和VHF-Offline两类任务调度算法,结合VHF硬件资源管理策略,实现软硬件的协同优化。其中,VHF-Online算法以贪心的队列调度和动态的时间管理,获得较高的任务接受率；VHF-Offline算法借助循环迭代消除任务间相关性,赋予任务不同的软硬件执行优先级,综合动态划分、布局判定、优先调度等协同策略实现较短的调度总长度。更多还原

【Abstract】 Reconfigurable Computing (RC) technology, integrates the advantages of both general and custom computing, providing flexible and efficient computing ability. Multi Processor System on Chip (MPSoC), which integrates many function units on the single chip, meets diverse application requirements. RC-MPSoC, a combination of above has computing flexibility and operation efficiency, which makes full use of multi-core computing resources advantages; using hardware programmability, more effectively meets the demand of different embedded applications.The above systems also face many challenges in the design and application field. The flexibility of application and the kernel polymorphism are very difficult to construct the normalized abstraction model; the partitioning, scheduling, and assignment, which brought by the efficiency of hardware acceleration, have been generally considered or proved as a NP-Complete or NP-Hard problem; the feature of reconfigurable resources time-sharing multiplexing add many constraint conditions of management, placement and fragment. So, the research on the codesign optimization algorithm of RC with MPSoC is very significant in the fields of improving system operation performance, enhancing application reliability, and so on.This dissertation mainly focuses on the RC with MPSoC software/hardware codesign application. The object is to optimize computing performance. First, abstract the basic frame structure of MPSoC and RC-MPSoC, and conclude the critical factors which affected the improvement of system performance. Second, with the research status both home and abroad, the corresponding optimization algorithms were given progressively. Last, the space/time complexity of algorithms and the effect on the system performance improvement were analyzed.The main work and features embodied in the following aspects:1. On the foundation of analyzing two state-of-the-art systems platforms of MPSoC and RC-MPSoC both home and abroad, the basic unify frame structure was built, combing with polymorphism calculation and the characters of next generation general processor platform. At the same time, considering the input task type on the platform, major limitation factors and performance improvement objectives, consistent constraint conditions and optimization model was abstracted.2. For software/hardware codesign optimization of MPSoC, based on the analyzing of tasks dependencies, communication cost, processor allocation and other restrictions, we put forward greedy partitioning and insert scheduling (GPISM) codesign optimization algorithm. By using greedy partitioning, the critical hardware path and longest software path were selected; On the basis of system constraints and optimization objects, the rest scattered tasks were inserted into the corresponding processor cores. The time complexity of algorithm is polynomial level, with smaller space overhead.3. For time-sharing multiplexing character of Reconfigurable Computing, based on the analyzing of the restrictions of resource management, placement manner and the fragments measuring, which effected system performance and resource utilization and so on, The VHF hardware placement and management strategy was put forward. The strategy included:the VPT (Vertex Positions Tree) data structure, which reduced storage costs; the HWC (High Weight Corner occupied first) placement manner and clever jump search methods, which reduced the computing time overhead; the FSE (Fragment Shape Edge) measure function, which reduced the computation cost. To solve the effection of permanent fault, the FT-VHF fault tolerant strategy had also been put forward based on the above. Both the VHF and FT-VHF strategies achieved effective resource utilization and low-cost system reliability with lower complexity of time and space.4. For the online and offline task characteristics, the two task scheduling algorithms VHF-Online and VHF-Offline had been put forward, on the basis of analyzing the restrictions of deadline, task dependencies etc. in RC-MPSoC codesign optimization. Combined with the VHF hardware resource management and placement strategy, the above two scheduling algorithms achieved the software/hardware codesign optimization. Using greedy queue scheduling and dynamic priority updating, the VHF-Online algorithm achieved higher rate of tasks acceptance; Eliminating task dependencies with loop iteration, giving the different task hardware/software execution priorities, integrating dynamic partitioning, placement judgment and priority scheduling etc. policies, the VHF-Offline algorithm achieved shorter total scheduling length.更多还原