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

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

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

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

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

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

一种简单的长码周期估计方法

在直接序列扩频（DS／SS）通信系统中，提出了一种简单的长码周期检测方法．将输入的DS／SS信号进行延迟相乘处理，消除信息数据对PN码周期的影响，应用自相关处理，提取长码周期．理论分析和仿真表明，在信噪比大于-10dB条件下，应用谊方法能够简单有效地估计出长码和短码周期．图4，表3，参11．     

基于非精确计算的保证计算质量的容错调度

针对单处理器系统的周期性实时任务集，基于非精确计算，提出FT／FA（Fault Tolerance／Frequency Assurance）调度方法．该方法对任务的强制部分进行容错，保证出错时仍能满足任务的时限要求；采用对可选部分的执行频率进行保证，保证任务的计算质量．此外。给出了FT／FA方法的可调度条件，并分析了该调度方法的性能．     

关于图的减控制数

图G=（V，E），一个函数f：V（G）→{-1，0，1}称为G的减控制函数当且仅当对任意v∈V有∑u∈N[V]f （u）≥1．令f（V）=∑v∈Vf（v）为f的权．图G的减控制数γ^-（G）=min{f（V）│f是一个减控制函数}．建立了几类特殊图的减控制数的值，并对一般图讨论了γ^-（G）的界．     

正性情绪状态对工作记忆刷新功能的影响

采用事件相关电位（ERP）技术,检验动态记忆任务中各认知成分在正性情绪状态下的变化,并探讨了正性情绪对工作记忆各组成系统的影响．实验结果发现,相对于中性情绪状态,与中央执行系统刷新功能密切相关的中央-顶分布的晚正成分（350—600ms）在正性情绪下波形更负;在左右额区的150-350ms及600-800ms也发现,与刷新相关差异波在正性情绪下更负;而与复述和储存子系统相关的ERP波形在正性情绪下更正,并且在350600ms的左侧脑区最明显．实验结果表明,工作记忆的各组成系统功能不同,因此正性情绪对它们的作用不同,并在中央执行系统中发现了情绪与认知的高级结合．     

多任务并行调度系统中的一种订票算法

本文提出多道相关任务系统并行调度方法,文中引入了一种描述任务资源分配的数据基ＴＣＢ（任务控制块）,并提出一个用于任务定序的“订票”算法,简称ＢＴ算法,改善了系统的处理能力。     

特殊图的条件染色

对于一个正整数r，图G的一个条件（k，r）-染色是使得图G的每个度至少为r的顶点至少与具有r种不同颜色的顶点相邻的正常的顶点染色．使图有一个条件（k，r）-染色的最小的整数k是图的第r个条件色数Z，（G），本文给出了对于不同的正整数，路、扇、轮的条件色数。     

多元自相关过程的残差T2控制图

为了满足传统的统计过程控制理论中统计量彼此独立的基本假设,研究了多元自相关过程的残差T2控制图的控制方法及其控制性能。针对一般多元自相关过程,在参数已知的条件下,讨论了多元自相关过程的残差T2控制图,给出多元自相关过程偏移量的定义。通过M on te C arlo模拟,得出该控制图在不同偏移量时的平均链长,在残差T2控制图的适用范围内给出平均链长与偏移量之间的经验公式。结果表明,残差T2控制图可以有效控制出现大偏移的多元自相关过程。     

并发程序内部表示及静态切片算法的改进

通过分析Krinke切片算法对程序循环体内嵌套一个或多个线程结构会产生切片不精确现象,得出Krinke算法所基于的程序依赖图对线程间数据的依赖关系定义得过于粗糙,且对并发程序执行行为的合法性约束不够严格的结果.据此,提出一种新的并发程序依赖图,引入跨线程边界循环-承载数据依赖关系,并在此数据结构上改进了切片算法;引入区域化执行证据概念,进一步约束程序执行行为的合法性,并给出了添加跨线程边界循环-承载数据依赖关系的算法及新的并发程序切片算法的伪代码.实例分析与算法性能测试表明,改进的切片算法克服了Krinke算法的不精确现象,降低了时间开销,改善了算法的可伸缩性.     

Task-Aware Flow Scheduling with Heterogeneous Utility Characteristics for Data Center Networks

With the continuous enrichment of cloud services, an increasing number of applications are being deployed in data centers. These emerging applications are often communication-intensive and data-parallel, and their performance is closely related to the underlying network. With their distributed nature, the applications consist of tasks that involve a collection of parallel flows. Traditional techniques to optimize flow-level metrics are agnostic to task-level requirements, leading to poor application-level performance. In this paper, we address the heterogeneous task-level requirements of applications and propose task-aware flow scheduling. First, we model tasks' sensitivity to their completion time by utilities. Second, on the basis of Nash bargaining theory, we establish a flow scheduling model with heterogeneous utility characteristics, and analyze it using Lagrange multiplier method and KKT condition. Third, we propose two utility-aware bandwidth allocation algorithms with different practical constraints. Finally, we present Tasch, a system that enables tasks to maintain high utilities and guarantees the fairness of utilities. To demonstrate the feasibility of our system, we conduct comprehensive evaluations with realworld traffic trace. Communication stages complete up to 1.4 faster on average, task utilities increase up to 2.26,and the fairness of tasks improves up to 8.66 using Tasch in comparison to per-flow mechanisms.     

可分任务的完工时间

若干台处理机完成一批任务所需要的最少时间称为完工时间.一般地,当任务数目小于处理机数目时,为了提高处理机的利用率,缩短处理机完成所有任务的完工时间,可以把每项任务预先平均分成几个部分,再放到处理机上使用并行算法进行加工,这样使完工时间尽可能小.文中具体给出了在此情况下的完工时间.       

基于多线程归并排序算法设计

为解决传统递归方式的归并排序算法串行执行效率低的问题, 使用数据依赖关系分析方法对归并排序算法进行并行性分析。通过分析发现算法本身具有并行的特征, 在多核处理器下使用OpenMp编译制导语句对算法进行直接并行化处理。在数据量较大的情况下, 为了使算法执行的速度更快, 在多核处理器系统中设置多个线程, 并将序列分成多个组, 每个线程操作一组数据, 最后对多个局部有序的结果进行逐一合并。实验验证结果表明, 该并行化算法可使执行速度提高50%以上。     

支持资源协同分配的网格任务调度研究

提出通用的网格和任务执行模型,并以此为基础,给出一种支持资源协同分配的任务调度算法。算法通过定义临界资源的概念,改进了传统的列表调度算法。模拟实验结果表明该调度策略更符合网格计算的复杂环境,能得到较短的任务执行时间,并更好的支持不同类型资源的协同分配。     

基于数据拓扑图的变量影响分析方法

为了解决软件中数据变量发生异常的问题，以及找到该异常变量在整个程序中与其余变量之间的关系和该变量的影响范围，提出了一种基于数据拓扑图的数据影响分析方法。研究了静态分析提取变量的依赖关系包括顺序依赖、自身依赖、节点依赖和函数依赖，得到变量的依赖影响集合，生成变量的数据拓扑图。实验结果表明，该方法能全面覆盖程序中的变量并准确地生成指定变量的数据拓扑图，且数据拓扑图能够发现异常变量在程序中影响了哪些变量，哪些变量被异常变量影响。     

异构任务图的实现模型

任意异构程序映射到任意异松系统上执行,是并行程序计算最复杂的情况,为此提出了异构任务图的定义,它是异构程度直观和有效描述方法,还研究了异构任务图的实现模型,它是异构计算环境中软件和硬件的桥梁,分别给出了任务图的分簇算法、系统图的分簇算法和映射算法及应用实例,利用该模型可设计出可移植的并行程序,然后调度到可动态配置的异构计算机组织上运行。     

异构型无人机群体并行任务分配算法

异构型无人机(UAV)群体任务分配机制起着至关重要的作用,分析了并行任务分配的特点,以时间消耗最短为优化目标,建立了整数线性规划的任务优化分配模型。对基本遗传算法进行了改进,提出了有效降低算法复杂度的编码方案,建立了相应的适应度函数,改进了现有遗传算法的变异策略。仿真案例表明该算法具有较强的寻优能力,能够有效地完成异构型群体UAV的并行任务分配。     

历史关系模式的最大完全时间依赖集求法

对基于TNF的历史关系模式TUg,提出了时间依赖、最大完全时间依赖集等重要概念,并给出了最大完全时间依赖集的求解算法及证明。为解决历史关系模式中存在的数据冗余、TNF异常等问题奠定了基础。     

基于P2P技术的高性能计算平台

给出了一个基于对等网络的高性能计算平台———P2HP的设计与实现技术.构建了该平台的总体结构,它由Portal,Datapool,工作台和工作组组成,给出了这些组成单元的设计方法和实现技术,并在此基础上分析了平台的性能.由于具有全新的通信方式,平台扩展了程序级并行应用的范围.通过对该平台的设计分析,提出了一种利用Internet中的计算资源进行高性能计算的新方法.实验证明该平台具有良好的扩展性和容错性.