异构计算的一种可移植编程模型及实现

介绍了异构计算的一种编程模型．该模型处理的对象是任意非一致的求解任务映射到任意非一致的系统结构上．文中分别给出了任务图的分簇算法,系统图的分簇算法和映射算法及实例．利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行     

基于Anytime算法的模型预测控制器的优化反馈调度

模型预测控制器可以实现为具有Anytime算法特征的模型预测控制（MPC）任务,它允许在执行时间和控制性能之间进行折衷．文中针对一组MPC任务,提出一种优化反馈调度算法（FS-CBS）,在有限处理器时间约束范围内使全局控制性能最大化．该算法为每个MPC任务分配了一个恒定带宽服务器（CBS）,并对CBS所预定的处理器时间进行动态调节,同时通过约束条件保证整个任务集的可调度性和各组分的稳定性．仿真结果表明,该算法对MPC运行时的执行时间变化不敏感,明显优于基本的CBS算法．     

基于双优先级队列的异构分布式控制系统容错调度算法

在对分布式控制系统进行分析的基础上,给出了任务模型和处理器模型.为了调度多种实时性的任务,提出了双优先级队列调度算法,用于调度每个处理器上的任务.该算法设置2个优先级队列,其中高优先级队列用于调度实时任务,低优先级队列用于调度非实时任务,高优先级队列中的任务可抢占低优先级队列中的任务.在此基础上,采用版本复制技术使系统具有容错能力,并分析了任务的容错可调度条件.基于此,采用首次适应的启发式任务分配策略,将任务分配到各个处理器上,在确保任务容错可调度的条件下使处理器负载均衡.仿真结果表明所提出的算法是有效的.     

异构环境下基于任务交互图的调度算法

针对异构环境下任务图为TIG（task interaction graph）的问题，利用松弛标记法善于利用邻居属性处理大量约束的特点，提出一种任务调度算法．算法把任务看作目标对象，处理器单元看作待分配标记，根据对象间所有可能关系，逐渐排除不相关的处理器单元，选择计算和通信综合性能较好的处理器单元．在兼顾任务执行的计算和通信需求的情况下，能够合理分配资源、提高处理速度、缩短整个应用程序的执行时间．实验结果与用穷举法得出的最优结果比较显示，本算法能较理想地解决异构环境下基于任务交互图的调度问题．     

满足吞吐约束与资源节约的任务流调度方法

根据实时信号处理应用中嵌入式计算硬件的资源受限特点,提出一种新的适合计算任务流的实时任务调度算法,以满足吞吐率为调度约束条件、以最小化流水线时延为调度目标并兼顾资源节约原则.算法为两层结构,首先采用任务插入策略得到满足吞吐率约束的中间结果;再通过基于任务复制的优化调度,分析了影响调度长度的关键任务并按照所定义的优先级构造关键边的决策树以确定需复制的关键父任务,充分利用了处理器的空闲时间片以减少时延.另外还设计了检测任务复制后出现的冗余处理器的方法.通过随机任务图仿真分析,说明该算法能以较小的处理器使用量获得满足吞吐率约束的调度结果.     

多设计任务调度的非合作博弈研究

从客户竞争需求的角度出发，以提交的设计任务各自的设计时间最短为调度目标，采用博弈理论，提出并构建了一种面向多设计任务的非合作博弈调度模型．在该调度模型中，设计任务被映射为博弈模型的局中人，与设计子任务集对应的可选设计节点映射为各设计任务的可行方案集，各设计任务的设计完成时间的倒数映射为收益函数，将多设计任务的调度转化为多设计任务调度模型的Nash均衡点来求解问题，并采用遗传算法进行了解算．同时，以6个设计任务验证了该任务调度模型及算法的可行性，为解决多设计任务调度问题提供了一种新的思路．     

多核平台的并行实时调度与内存分配算法

多核处理器凭借着低功耗高性能的优势占据了市场.针对多核平台上并行实时任务,提出局部与全局EDF相结合的调度算法,其中任务的截止期划分、执行预算以及迁移时机由所设计的处理器带宽预留服务器决定.同时,提出了内存分配算法,该算法能够更好地为并行实时任务管理内存资源.实验结果表明新的调度算法具有更高的调度成功率.另外,在内存资源竞争的前提下,内存分配算法可以保证并行任务的实时性与系统稳定性.     

基于约简任务资源分配图的网格依赖任务静态调度

网格资源环境的动态性和异构性对依赖任务的静态调度策略产生了极大的挑战.提出了一个能够更好地适应资源异构性,并完整支持调度、重调度的统一静态调度模型,即基于约简任务资源分配图(RT-RAG)的调度模型和调度算法.基于该模型的调度问题归结为RT-RAG的优化选取问题.实验分析表明,基于该模型的调度方法更好地适应了网格环境的动态性和异构性,使得静态调度策略与动态调度策略相比依然保持着较大的性能优势,并且也优于基于DAG任务图调度模型的AHEFT静态调度算法,特别是在资源差异较大的情况下.     

基于启发式群聚算法的机器人全局任务调度策略

提出了一种基于启发式群聚算法的机器人全局任务调度策略，在任务划分阶段采用一种启发式群聚算法对随机划分的各子任务按能否使总的运行时间缩短进行各子任务间的聚合，以使各子任务粒度和相互之间的通讯量达到一种优化状态，并在此基础上对群聚之后的各子群任务采用集中式动态调度策略，在程序运行过程中实现各处理器的负载平衡，提高各处理器的利用率，缩短总的运行时间．在一个由5个DSP（digital signal processor）处理器组成的同构型松耦合MIMD（multi instruction multidata）并行处理平台上，对平面四自由度连杆机器人在关节锁定下的运动控制任务采用上述先随机划分，再聚合，最后集中式调度的方法进行了并行实时仿真实验，取得了满意的并行性能指标．     

利用投影时序逻辑的多内核进程调度建模与验证

针对软件测试无法满足多内核处理器上进程调度的验证需要这一问题,提出利用投影时序逻辑(PTL)的定理证明方法来验证进程调度.使用PTL公式建立了支持当前主流进程调度算法的多内核处理器进程调度一般模型S,并将系统期望的性质描述为PTL公式P,在PTL公理系统的基础上,通过证明S蕴含P是否为一个定理来验证系统是否具备该性质.以2内核处理器上的多级反馈队列算法的正确性为案例进行检验,结果表明所提方法可验证多内核处理器进程调度的系统性质,保证多内核进程调度的可靠性.由于多内核处理器的进程调度具备了并发系统的主要特点,因此该方法也适用于一般的并发系统验证.     

支持优先级约束任务的容错调度算法

为了解决异构分布式系统中可靠调度问题,提出一种考虑处理机链路通信竞争的,支持优先级约束任务的容错调度(FSPCT)算法。该算法使用通信竞争模型描述处理机之间通信,在备份成本最小化和备份任务最早完成之间寻求平衡点。对主副版本任务的最早开始时间进行分析,并限定了所执行的处理机,在处理机出现故障后任务可以顺利执行。实验结果表明FSPCT算法的综合性能优于现有一些算法。     

一种基于多Agent的动态负载平衡算法应用研究

在介绍动态负载平衡算法基本原理的基础上，提出了一种基于多Agent的负载平衡算法DMAL，定义了节点机可能的4种状态，并讨论了DMAL算法的实现规则；描述了基于DMAL算法的任务调度模型；讨论了DMAL算法中任务的分类问题、任务的迁移粒度问题、负载迁移的触发时机问题；为了增强在负载平衡时处理节点间的通信能力，引入了多Agent技术，并为异构分布式处理系统提出了一种基于DMAL算法的负载平衡框架结构；最后通过实验仿真，比较了DMAL算法、现有的负载平衡算法以及不作负载平衡的运行结果．实验结果表明，基于DMAL算法的分布式处理系统工作在不同负载和应用问题数据规模的情况下，在任务的处理时间、丢弃率和平均响应比方面都显示出良好的性能，从而验证了该算法方案的可行性和有效性．     

并行空间连接查询处理

基于顺序空间连接查询的效率不能令人满意，利用并行控制提高空间连接查询效率。空间连接查询的并行处理方法最重要的特征是任务分配根据多路平面扫描顺序，避免了连接处理过程中处理器之间的通信花费，提出基于空间连接花费模型的任务分配方法和基于花费估计的动态任务分配策略，并给出了花费模型。该模型经实际应用效果明显。     

顺序程序任务并行性的识别

探讨了任务并行性识别中任务执行条件的导出，利用任务给点间的相关性（包括数据相关和控制相关）就可求出并行执行条件．提出了层次任务图模型下直接生成优化任务执行条件的算法，省去了后控树及控制相关图（ＣＤＧ）的产生，其过程简单且比较高效．     

A communication-aware scheduling algorithm for heterogeneous systems

Previous work mostly employs an ideal system model that assumes fully connected processors and concurrent communication, which leads to inaccurate and inefficient schedule results. In this paper, a new scheduling model which integrates the communication awareness was proposed. Then, a novel scheduling algorithm based on list heuristic was put forward for the new model, which can produce optimal schedule by serializing the communications edges. Experimental results show that the accuracy and efficiency of the new model and algorithm are significantly improved.     

一种改善激励源的1.2kb/s语音编码算法及其实时实现

为了适应无线通信等低速语音编码场合，吸收2.4kb/sMELP算法优点，提出了一种改善激励源的1.2kb/s混合激励线性预测算法，该算法在模型结构、LSP量化及解码等方面较传统的2.4kb/sLPC算法有了较大改进。同时，选用TMS320VC5416DSP芯片实时实现了以该算法为核心的声码器。客观音质测试和非正式主观测试结果表明，该算法在自然度、清晰度和抗噪声等方面明显优于2.4kb/sLPC算法，是低速率下一种良好的编码方案。     

一种新的多处理器系统实时容错算法

实时多处理器容错算法是实时系统研究领域的一个重要课题.提出了一个动态处理非周期实时任务的容错算法.提出了对待实时任务的基、副版本采用不同的处理器分配策略.对于基版本,尽量提前任务的开始时间;对于副版本,尽量延迟任务的开始时间.通过实验模拟研究了算法的性能.实验表明,算法调度的成功率跟处理器个数、任务数以及任务计算时间有关.与采用单一处理器分配策略相比,具有较高的调度成功率.     

嵌入式设备中差异化多任务节能优化调度方法研究

当前任务节能调度方法通常需预先掌握嵌入式设备中差异化多任务的属性,但在实际应用中任务抵达处理器后才可获取任务属性,导致当前方法应用性较低。为此,提出一种新的嵌入式设备中差异化多任务节能优化调度方法,对嵌入式设备中处理器模型、任务模型和功耗模型进行描述。通过引入速度调节因子,依据松弛时间,结合功耗管理技术,降低嵌入式设备中差异化任务执行速度,达到合理调度与节省能耗之间的合理折中,给出嵌入式设备中差异化多任务节能优化调度的实现过程。实验结果表明,所提方法节能效果好,调度性能优。     

多状态图神经网络文本分类算法

为了提高模型在文本分类任务中的分类性能,针对图神经网络中存在的过度平滑问题,同时增强模型在处理文本特征与文本表示方面的能力,提出了一种基于多状态图神经网络的文本分类算法(multi-state graph neural network, MSGNN)。多状态图神经网络是利用网络层的多个历史状态信息对图神经网络进行强化,构建合理的文本图结构数据作为模型输入。在缓解网络层过度平滑问题的同时,结合2种改进后的不同类型的图神经网络来增强模型的特征提取与特征聚合能力。利用多头自注意力机制对文本关键词的挖掘与利用能力,从多个文本子空间来生成高质量的文本表示,进而完成文本分类。通过在几个公开的文本分类数据集上进行实验分析,相较于其他神经网络的文本分类算法,该方法取得了较好的分类准确率。