关键词： 嵌入式系统   可重构   多处理器片上系统   软硬件划分   节能调度   温度感知调度   启发式算法  

摘要： 由于芯片制造工艺的限制，处理器频率的继续提升遇到了物理瓶颈，多处理器技术被认为是维持片上系统性能增长的有效方法。异构多处理器片上系统(Multi-Processor System-on-Chip, MPSoC)兼顾了系统的通用性与灵活性，受到了工业界和学术界的青睐，已经被广泛应用于移动通信、嵌入式多媒体等领域。对于异构MPSoC来说，其性能的充分发挥依赖于所采用的任务调度算法。高效的调度算法可以缓解处理器数目增加所带来的高能耗、高温度、高成本等问题，能够进一步扩大MPSoC的应用范围。在满足各种约束的前提下对异构MPSoC进行优化调度已经证明是NP难问题。因而，针对异构MPSoC的各种应用需求，寻求不同优化目标下的最佳调度方案，已经成为当今多处理器技术的研究热点和重点。 随着可重构技术和MPSoC的发展，出现了包含可重构资源的异构MPSoC，它兼具可重构资源的高效性和MPSoC的灵活性，为系统设计和应用提供了更多的选择。对含有可重构资源的异构MPSoC而言，任务调度时还需要完成软硬件划分，因而进一步增加了问题的复杂度。针对具有可重构功能的异构MPSoC，以充分发挥可重构资源的性能、解决异构MPSoC所面临的能耗和温度问题为出发点，分别开展软硬件优化划分算法、节能调度算法和温度感知调度算法研究。论文的具体工作如下： (1)针对双路软硬件划分的特点，借鉴0/1背包问题的相关算法思想，基于模拟退火算法的全局寻优特性，提出了一种融合贪心算法与模拟退火算法的软硬件划分方法。该方法在研究双路软硬件划分系统结构基础上，首先将软硬件划分问题规约为0/1背包问题，采用贪心算法进行快速初始划分;然后设计一种新的接收准则，根据新解在扰动模型中的位置来计算其接收概率，基于贪心算法的预划分结果，采用改进的模拟退火算法进行全局寻优。由于该算法兼具贪心算法的高效性和模拟退火算法的全局寻优能力，从而避免了模拟退火算法初始划分难以设定的问题，在任务划分质量和算法运行时间方面均取得了较好的效果。仿真实验证明了本文所提算法的有效性。 (2)针对异构MPSoC中处理器数目增长所引起的高能耗问题，考虑遗传算法的高效搜索能力，采用动态电压缩放技术，提出了一种新的节能调度算法。该算法首先对遗传算法的选择算子和群体更新机制进行改进，增强了群体的多样性，然后基于改进的遗传算法来确定任务优先级，采用链表调度方法确定任务执行顺序;最后根据任务能量和时间关系，设计了一种新的任务缩放优先级计算方法，基于该优先级进行节能调度。该算法在具备遗传算法的高效搜索能力的同时，弥补了其容易陷入局部最优解的缺陷，并且通过对高能耗任务进行有针对性的缩放，很好地实现系统节能。 (3)针对能量密度增长给异构MPSoC所带来的温度提升，考虑漏极功率、供电电压和温度之间的关系，以系统峰值温度最小化为优化目标，提出了一种新的温度感知调度算法。温度升高将直接缩短处理器的生命周期，同时影响系统性能和使用舒适度。本文首先针对异构MPSoC应用推广所面临的温度问题，在温度与供电电压关系的基础上，考虑处理器的漏极功率，建立温度模型;然后根据任务关键路径进行初始调度，在温度模型基础上计算任务的运行温度，运用动态电压缩放技术，通过迭代操作优化系统峰值温度。该算法中所考虑的温度模型更为实际，并且直接对具有峰值温度的任务进行优化，从而能够显著降低系统峰值温度和平均温度。 (4)针对本文提出的任务调度算法，在相关嵌入式系统中进行了应用研究。针对湖南省科研条件创新专项“三维荧光光谱仪高性能数学分离关键部件研制”，进行了软硬件划分算法应用研究。该部件的核心是“数学分离”算法，涉及到大量的高维矩阵运算，在嵌入式应用中需要解决复杂计算问题。本文通过分析问题的计算特性，采用通用处理器和可重构资源相结合的方式，进行系统结构设计;然后运用本文提出的软硬件划分方法，对任务进行划分，获得了较好的系统性能。针对国家发改委项目“中国网上教育平台”子项——“移动学习平台”，进行了节能调度算法应用研究。嵌入式移动平台特别关注能耗问题，本文采用具有较好电源管理功能的PXA255芯片进行系统设计，并进行动态电压缩放技术的具体实现。在此基础上，运用本文的节能调度方法，对AVS视频解码任务进行节能调度应用研究。应用结果表明了本文算法的有效性。

关键词： 嵌入式多处理器   PCI总线   端到端通信   DMA传输  

摘要： 在安防、图像处理、语音识别、网络通信等计算密集型应用领域，市面单颗嵌入式处理器的性能提升速度常常满足不了人们的需求。应用开发商往往会选择一种称为嵌入式多处理器方案。该方案以一定方式互连多颗嵌入式多处理器，借助芯片并行设计和软件协同处理来达到性能倍增的效果。在所有的嵌入式处理器互连方式中，PCI总线以其高带宽、通用性、成熟性以及低成本尤为引人瞩目。本文主要研究对象为基于PCI互连的嵌入式多处理器系统，重点研究其中较为核心的片间通信机制。 本文首先介绍了嵌入式多处理器通信原理，通过对比双口RAM、以太网总线、PCI总线以及Mesh架构等互连方式的特点以及适用范围，总结了PCI互连的优势，在此基础上归纳了PCI互连所要解决的主要问题。接着本文通过分析现有TCP/IPOver PCI方案的不足，设计了一种通用的面向嵌入式多处理器的并发通信模型。该模型以PCI内存映射为基础，通过对通道划分、报文格式、数据传输机制、管理机制等一系列核心问题讨论，提出了一套完整的基于PCI的端到端通信方案。该方案可满足跨越CPU节点的进程间的高效、并发、对等通信需求。本文接下来基于Linux2.6.14内核以及Hi3511双处理器系统，对模型进行了详细实现和完整测试。最后对整个测试结果进行了具体分析，并对下一阶段的研究工作进行了展望。

关键词： 超精密   运动控制   VME总线   DSP   FPGA  

摘要： 超精密运动控制是光刻机的核心技术之一，本文结合国家重大科技专项课题《双工件台运动控制系统硬件研发》的研究工作，对基于VME总线的多处理器运动控制卡进行了研制与实践。 分析了双工件台超精密同步运动控制需求，研究了光刻运动过程中各子系统间的相互关系；对常用的计算机总线：ISA总线、PCI总线、VME总线等进行了比较分析，对适用于工业控制的微处理器：单片机、ARM、DSP、FPGA等进行了优缺点对比，确立了以标准VME总线为基础、以DSP+FPGA为控制核心的运动控制卡总体结构；针对运动控制卡具体功能需求对各个功能模块进行了简要的分析。 根据运动控制卡总体结构进行详细的硬件设计，包括：DSP外围电路、FPGA外围电路、VME总线接口电路、高速光纤电路、数字和模拟IO电路、运动控制卡供电系统等。在硬件电路的基础上设计了三层软件结构，利用FPGA灵活可重新配置、集成度高等优点实现硬件接口层软件：VME从接口逻辑、自定义总线接口逻辑、高速光纤控制器和模拟IO控制器等。DSP通过外部存储器接口EMIF统一管理FPGA控制器，实现了DSP+FPGA核心处理器架构。同时，在DSP中实现FLASH启动、应用层代码从上位机下载、DSP底层程序等底层软件；最后通过搭建系统调试平台，对运动控制卡功能设计的完整性和稳定性进行了验证。 本文针对超精密双工件运动平台，设计了基于多总线数据传输的多处理器并行处理运动控制卡，实现多轴纳米级同步运动控制；根据运动控制系统总体架构进行了详细的运动控制软硬件设计和验证；运动控制卡经过长时间测试，已交付使用。

关键词： 实时数据库系统   节能调度   更新事务   时序一致性   负载最小化   多处理器  

摘要： 实时数据库系统(Real-Time DataBase System,简称RTDBS)是数据库技术和实时系统相结合的产物,它集成了实时系统和数据库系统的相关理论和技术。近年来,RTDBS在电力和数据网络管理、雷达跟踪、工业生产过程控制和证券交易等需要定时存取数据或对“暂时有效”数据进行存取的这样一类国防军事及民用实时信息服务领域得到了广泛应用。尽管应用取得了极大的成功,但是与许多其他的计算系统一样,RTDBS也受到了过量能耗的困扰。过多的能量消耗对系统的服务质量(包括服务时间,稳定性和可靠性等)产生了巨大的影响。在某些特定的运用环境中(典型如嵌入式环境),RTDBS通常是靠电池驱动的,系统补充能量的代价太高,甚至由于环境的限制而在相当长一段时间内无法补充能量,而在可见的将来电池的寿命限制问题都难以得到彻底解决,此时节省能耗从而延长系统的服务时间变得尤为重要。 与传统数据库中的数据对象不同,在实时数据库中,数据对象只在一段时间内是流行的(有效的),也即每一个数据对象都有一个有效期作为该数据当前值的生命周期,一旦超过了生命周期,该数据就是非时序一致性的(也即无效)。因此,必须在数据对象的旧版本(值)变成无效之前用新值更新该数据对象,以使其总是能够反映外部实体的当前状态。由于RTDBS的计算资源通常是有限的(尤其在嵌入式环境下),此时如何合理设置更新事务的截止期和周期并对更新事务集进行调度,以在保证数据对象时序一致性的前提下尽量减少用于更新事务的处理器负载变得非常重要。 在RTDBS中,因为用于锁表及检测数据库一致性的时间开销比执行事务本身的时间开销要大得多,事务通常以非抢占的方式执行,而已有的实时节能调度算法大都是基于可抢占任务集的。尽管也存在针对部分非抢占段任务集的节能调度策略,但是直接将它们应用于完全非抢占任务集时往往会计算出过高的减速因子(标准化的任务执行速度),因而并不能获得最佳的节能效果。为此,针对完全非抢占实时任务集提出了一个新的减速因子计算方法ISA,通过精确分析来自高优先级任务的执行次数,求得了更低的减速因子,使得任务集在频率继承策略下通过使用新的减速因子能够显著降低系统能耗。同时注意到在发生任务阻塞时,不必要总是采用频率继承策略来保证任务的截止期,提出了选择性频率继承策略SFI以进一步降低系统能耗。此外,考虑到任务的实际执行时间通常要小于其最坏情况执行时间,提出了动态空闲时间固收算法ISA-DR以获得额外的能耗节省。性能评估结果表明,提出的节能调度算法和相关策略相比于已有算法可以获得可观(平均为20%-30%)的能耗节省。 目前针对单处理器系统静态优先级调度下更新事务截止期与周期计算问题的研究已经非常成熟,但是针对该问题在动态优先级调度下的研究还比较少见。已有算法要么求得的处理器负载过高,要么运行效率过于低下。基于此,提出了一个新的两阶段算法gεEDF。gεED算法的第一阶段具有线性执行时间,因而能被用来快速求得一个解。且证明了当分派顺序固定为最短时序优先时,由第一阶段求得的解具有最优(最小)负载。当第一阶段失败时,基于确切性可调度判定条件提出了gεED算法的第二阶段。由于该阶段具有伪多项式执行时间,介绍了若干技术,通过减少需要检测的调度点数目和迭代步骤来降低进行可调度性测试时的计算代价,从而提高算法的执行效率。实验结果表明,相较于现有算法,gεED算法能够快速得到处理器负载更低的可行解。 以往针对RTDBS中数据对象时序一致性的研究都是基于单处理器系统来进行的,目前国际国内还未见针对该问题在多处理器环境下的相关研究。首次研究了多处理器环境下保证实时数据对象时序一致性的更新事务分派问题,证明了多处理环境下最小化处理器负载的更新事务分派问题是NP难的。鉴于问题的复杂性,首先只考虑问题的可调度性方面,提出了一个多项式时间分派算法TCP,并从理论上证明了TCP算法具有3—1/m的资源放大界值。随后统筹考虑事务分派问题的可调度性与最小化处理器负载两个方面,基于“一个在各个处理器之间平衡密度因子的事务分派方案趋向于得到更低的处理器负载”这一观察,提出了具有多项式时间复杂度的启发式分派算法DBF,并证明了DBF算法也具有3—1/m的资源放大界值。性能评估结果表明,DBF算法在可调度性／处理器负载性能上要优于相关算法。

关键词： 片上可编程多处理器系统   现场可编程门阵列   片上网络   空分复用   性能评估  

摘要： 单处理器的嵌入式系统已经不能满足用户的需求，多处理器系统已经成为未来嵌入式系统的主要发展趋势。现场可编程门阵列（FPGA）的出现给多处理器系统的设计带来了很多方便。相对于传统的片上系统（SoC）技术，基于FPGA的片上可编程系统（SoPC）设计技术具有很多优点，使得在FPGA上搭建多处理器系统更有优势。这种多处理器系统称之为片上可编程多处理器系统（MPSoPC）。但是传统的基于总线结构的MPSoPC系统具有很多缺点，制约了多处理器系统的性能。2001年***等研究人员将计算机网络的思想应用到芯片上，提出了片上网络（NoC）这种全新的片上互联架构，通过片上网络中的路由器来连接芯片上的各个模块。片上网络思想的提出弥补了传统总线通信结构的缺点，满足了片上多处理器中各处理模块间的高带宽以及低延时的通信需求。 本文针对片上网络以及MPSoPC进行了研究和设计，做了以下四方面的工作：（1）MPSoPC中片上网络的设计：本文提出了一种基于空分复用（SDM）的片上网络设计方法，主要包括路由器、网络接口、控制单元以及片上网络IP核设计。（2）片上网络的仿真测试：本文对片上网络的各个模块进行仿真与综合，测试片上网络的各个模块，给出了各模块的仿真波形与综合后的RTL级电路图。（3）基于片上网络IP核的MPSoPC系统设计：本文设计了一款基于片上网络通信架构的多处理器系统，该系统包括了四个MicroBlaze处理器软核。通过对处理器以及片上网络IP核进行连接、配置、编程，最终形成了一个可测试的MPSoPC系统，并且在Xilinx的Virtex-5XC5VLX110T FPGA开发板上得到了验证。（4）片上网络的性能评估：本文从面积、功耗、资源利用情况、吞吐量以及系统延时等方面对设计的片上网络的性能进行了评估,性能评估是在基于FPGA的多处理器系统中而不是在仿真软件中进行的，结果更加准确。 在对片上网络以及MPSoPC进行测试之后，测试结果证明本文设计的片上网络的功能正确，而且MPSoPC在片上网络的架构下也能够有效地工作。性能评估结果显示本文设计的网络接口灵活性强，路由器设计复杂度低。相对于时分复用（TDM）片上网络以及同类空分复用片上网络，本文的片上网络的面积、功耗以及资源利用率都比较小，而且还能够提供有保障的吞吐量。

关键词： 虚拟化   XEN   多处理器   CPU调度   负载均衡  

摘要： 虚拟化技术是创建灵活动态的企业级设施架构的关键机制。随着多处理器技术的发展,计算能力有了很大提高,也加速了虚拟化技术这一关键机制的发展。虚拟化技术可以屏蔽底层复杂的物理环境,允许多个虚拟机之间共享物理机资源,另外,正在运行的虚拟机可以无间断地在两台物理机之间进行迁移。所以对于大多数企业来说,基于虚拟化技术的企业架构能够提供更多的安全稳定性能,并且也是合并服务器资源和应用的理想解决方案之一。 Xen是目前应用比较广泛的开源虚拟化软件之一,它能够使多个客户操作系统以接近物理系统的性能同时运行在相互隔离的环境中,并对底层物理硬件实现共享访问,包括处理器资源。在虚拟化环境中,虚拟机上的CPU调度是以虚拟CPU作为调度单位进行分时调度。SEDF是Xen中缺省的CPU调度算法之一,该算法支持实时性较强的应用,但是缺少SMP架构中多处理器之间负载均衡的控制。 本文考虑到SMP架构中处理器和cache的关系,提出一种虚拟机环境中的CPU调度算法,该算法设计了一个共享等待队列,各个处理器根据自身负载情况,共享等待队列动态调整VCPU的调度顺序,不仅能够选择最优处理器来执行,并且可以避免处理器空闲。仿真测试结果表明,本文提出的调度算法具有较高的系统吞吐量和任务完成率,也能够降低任务执行的平均周转时间和平均响应时间。本文提出的算法不仅减少了cache和内存数据同步带来的性能损耗,而且支持较好的全局负载均衡,能够充分合理利用处理器资源。

关键词： 红外光电仿真系统   边缘检测   粒子滤波   三维匹配滤波   多处理器   弱小目标检测   跟踪算法  

摘要： 红外成像系统和相关的图像处理技术是红外预警，目标自动搜索与跟踪等领域的关键技术。本文以红外光电仿真系统为项目背景，对红外弱小目标检测问题进行了深入的研究和讨论，并对其进行了新算法的研究和改进。　　文中根据红外光电仿真系统的设计要求，具体分析了系统的各项功能，将系统分解成几个子系统，并分别对其功能进行了实现。针对红外信号处理平台和系统功能的特点，选择了以VME总线为底板总线的G4DSP信号处理平台。文中对G4DSP的信号处理平台进行了深入的研究，包括多处理器系统的CPU间通信，CPU间同步，外设的连接等。本文还介绍了PMC数据采集卡的设计与实现，并对其中的PCI总线的逻辑进行了详细的介绍。G4DSP中采用VxWorks作为操作系统。文中介绍了VxWorks操作系统的PCI设备的驱动开发，以及VxWorks的多任务编程。本文最后介绍了算法的多处理器实现，将红外图像的检测与跟踪算法分配到多个处理器中协同处理，提高了算法效率。　　本文介绍了红外图像的一般模型，然后介绍了一些常用的红外图像背景抑制算法，如中值滤波，形态学滤波，二维最小均方差滤波和高通滤波。并对这几种算法进行了仿真，比较了算法结果。文中针对在背景预测中对图像中的边缘部分的预测不准确的现象，提出了一种基于边缘信息的红外图像背景预测算法。该算法利用改进的Sobel算子，先对图像进行边缘提取，将图像的边缘与非边缘分开。然后对图像的边缘部分和非边缘部分进行不同策略的预测，从而使预测的结果更加准确。文中然后分析了TBD的算法，重点研究了粒子滤波算法和三维匹配滤波，并对粒子滤波算法和三维匹配滤波算法进行了改进。文中提出了一种基于频域特征提取的粒子滤波算法，将红外弱小目标的模板变换到频域，在频域进行模板的比较，通过仿真，该算法能够实现较好的跟踪效果。文中还提出了一种融合粒子滤波的匹配滤波算法，将非匀速直线运动的目标通过粒子滤波算法的预测，通过直线拟合，将其近似为匀速直线运动，并通过三维匹配滤波算法进行运算，得到信噪比增强后的目标，经过算法仿真，该算法能够较好的实现对弱小目标信噪比增强的效果。

关键词： 多处理器系统   任务调度   异构系统   混合实时任务  

摘要： 针对实时异构系统的任务调度问题,提出了一种异构多处理器系统的混合实时任务调度算法。该算法采用带有非周期服务器的EDF(Earliest Deadline First)算法来调度单处理器上的任务集,可充分利用处理器的计算带宽。采用启发式搜索算法来进行任务的分配,以最大剩余计算带宽为搜索指标,可确保各处理器的负载尽量平衡。同时,对软实时任务引入QoS(Quality of Service)降级机制,可提高任务集的整体调度成功率。最后,对算法进行了仿真实验,仿真结果证明了算法的有效性。

关键词： 多处理器   软件性能   并行  

摘要： 随着单处理器架构遇到了硬件发展的瓶颈,各大处理器厂商自2004年以来,已经逐步向多线程及多核架构发展,到了现在基本已是多核处理器的天下,而多核架构的实施对软件的开发必将带来巨大的变革,要改变传统的编程思想及方式,要积极尝试采用并行软件设计方法开发应用程序,这样才能在硬件多核架构下实现软件发展提升性能。

关键词： Computer science   Hardware design   Proximity Coherence   CMP   Cache design   Network-on-chip   Physical locality  

摘要： Many-core architectures provide an efficient way of harnessing the growing numbers of transistors available in modern fabrication processes; however, the parallel programs run on these platforms are increasingly limited by the energy and latency costs of communication. Existing designs provide a functional communication layer but do not necessarily implement the most efficient solution for chip-multiprocessors, placing limits on the performance of these complex systems. In an era of increasingly power limited silicon design, efficiency is now a primary concern that motivates designers to look again at the challenge of cache *** first step in the design process is to analyse the communication behaviour of parallel benchmark suites such as Parsec and SPLASH-2. This thesis presents work detailing the sharing patterns observed when running the full benchmarks on a simulated 32-core x86 machine. The results reveal considerable locality of shared data accesses between threads with consecutive operating system assigned thread IDs. This pattern, although of little consequence in a multi-node system, corresponds to strong physical locality of shared data between adjacent cores on a chip-multiprocessor *** cache coherence protocols, although often used in chip-multiprocessor designs, have been developed in the context of older multi-node systems. By redesign- ing coherence protocols to exploit new patterns such as the physical locality of shared data, improving the efficiency of communication, specifically in chip-multiprocessors, is possible. This thesis explores such a design – Proximity Coherence – a novel scheme in which L1 load misses are optimistically forwarded to nearby caches via new dedicated links rather than always being indirected via a directory structure