XQuery并行实现中的任务调度算法

为提高XQuery语言的处理性能,针对XQuery并行实现中的任务调度问题,提出一种适用于共享内存多线程环境的调度算法。在一种新型调度策略的指导下,能够利用XQuery语言中存在任务并行性、数据并行性和流水线并行性的特点,提高程序并行执行效率;针对流水线并行执行方式,建立一种流水线局部并行自动机模型,通过利用流水线中各节拍之间的空闲等待时间,提高系统资源的利用率。通过实验验证了该算法的可行性和有效性。     

一种高准确度多分类结构选择方法

支持向量机SVM是目前最流行的二分类算法之一。现实生活中数据集大多要求能够进行多分类,而有向无环图DAG方法是将SVM应用扩展到多分类的用得最多的方式之一,它调用分类器次数较少,执行速度快,但是由于有错误向下累积和分类偏向性等情况存在,会影响DAG分类结果的准确度。在使用DAG-SVM的时候,对于k种类别有k!种不同的备选结构,根据数据集特性选择合适的DAG结构能够有效提高结果的准确度。提出使用估计准确度的方法,从备选结构中用穷举法选择出最高准确度估计值的DAG结构,以此作为测试集的结构进行分类。实验结果表明,相较其它方法,测试数据集采用该方法选择的DAG结构后的分类准确性得到显著提高,在对类别数量不太多的数据集进行多类分类时有较好的效果。     

网格环境下的静态启发式任务调度算法

针对网格环境中应用程序常为复杂的计算密集型的并行分布式应用程序,提出了一个新的基于复制和插入的启发式任务调度算法(duplication-and-insertion-based scheduling,DIBS),可以同时执行多个应用程序,利用决定路径对任务进行排序,缩短了应用程序总的执行时间,该算法还平衡了处理器间的负载.实验结果表明,该算法更加符合网格的复杂环境,能够更好地满足不同用户的实际需要.     

基于扩展的随机DAG的EST估算与任务调度

针对DAG调度算法中采取多次执行后的平均值估算任务的EST值问题,通过对DAG调度中常用的调度算法ETF算法进行分析提出基于扩展的随机DAG的调度方法SETF,给出扩展的随机DAG中节点的EST计算方法,以标准方差和平均值之和的数学期望表示,并以ETF算法为例进行实验模拟。实验结果表明,SETF算法相对于ETF算法,减少并行任务执行时间,并能更精确地预测任务调度的平均执行时间。     

Communication contention in APN list scheduling algorithm

Task scheduling is an essential aspect of parallel process system. This NP-hard problem assumes fully connected homogeneous processors and ignores contention on the communication links. However, as arbitrary processor network (APN), communication contention has a strong influence on the execution time of a parallel application. This paper investigates the incorporation of contention awareness into task scheduling. The innovation is the idea of dynamically scheduling edges to links, for which we use the earliest finish communication time search algorithm based on shortest-path search method. The other novel idea proposed in this paper is scheduling priority based on recursive rank computation on heterogeneous arbitrary processor network. In the end, to reduce time complexity of algorithm, a parallel algorithm is proposed and speedup O(PPE) is achieved. The comparison study, based on both randomly generated graphs and the graphs of some real applications, shows that our scheduling algorithm significantly surpasses classic and static communication contention awareness algorithm, especially for high data transmission rate parallel application. Supported by the National Natural Science Foundation of China (Grant Nos. 90715029 and 60603053), the Cultivation Fund of the Key Scientific and Technical Innovation Project, Ministry of Edacation of China, and the Key Project of Science & Technology of Hunan Province (Grant No. 2006GK2006)     

基于组件的密码学虚拟实验室的设计与实现

基于组件技术的密码学虚拟实验室(CVL)以Java Applet实现客户端,以JavaBean的形式开发密码算法组件,利用Java反射技术实现了系统组件的动态分析,采用XML技术实现了实验组件信息的保存,结合计算机图论中的有向无环图的概念和Java线程机制,提出了一种基于有向无环图的管理线程控制机制,较好地反映了组件之间的数据依赖关系和运行管理过程.CVL实现了可视化实验流程的定制,实验流程的保存与读取以及密码算法的验证和性能分析性等功能.为科研、教学提供了一个很好的密码学实验平台,并给从事仿真系统开发的研究者提供了有力的参考模型.     

面向对象的流程工业系统有向无环图建模

提出流程工业系统中有向无环图的面向对象的建模方法。介绍使用面向对象的技术对流程工业系统模进行建模的关键要素的技巧,定义描述流程工业系统中有向无环图模型的建模机制,扩展流程工业系统模型所具有的特性。以流程工业系统出现异常时的诊断实例说明系统模型解决问题的有效性。     

VLCC中的DAG并行算法

基于组件的密码学虚拟实验室（VLCC）采用有向无环图（DAG）的拓扑排序机制管理组件。在分析VLCC各组件之间的数据依赖和运行次序关系的基础上,提出一种新的基于Java多线程机制和“唤醒”机制的DAG并行算法。与拓扑排序算法相比,具有低算法时间复杂度的特点。实验结果表明,系统在新算法下较大地缩短了系统运行时间,提高资源使用效率和用户满意度,能更好地完善VLCC。     

费用限制下的工程进度计划

本文用带权的有向无环图 (DAG)表示工程设计进度 ,并通过求解 DAG条件限制下的最短路径 ,给出费用限制下的最短工程进度。     

Water-retaining ability of diacylglycerol

The water-in-oil emulsification characteristics and the adsorption properties of DAG at the oil/water interface were investigated for DAG having different FA compositions. The water-retaining ability of DAG is dependent on the FA composition but is not dependent on the interfacial tension at the oil/water interface in a simple way. The water-retaining ability is very different between uni-chain DAG (two FA have the same chain length) and complex-chain DAG (one FA is oleic acid and the other has a shorter alkyl chain). Uni-chain DAG, having long FA chains (R=C₁₂ or C_18∶1) have the ability to emulsify water at the volume fraction of 80% (ϕ80%), but uni-chain DAG with short or medium chain-length FA (R=C₃, C₄, C₆, C₈) show little ability to retain water. For complex-chain DAG, all the DAG studied here (R₁=C_18∶1, R₂=C₂−C₁₂) have the ability to emulsify water at ϕ80%. The stability of the emulsions, however, varies with the chain length of the R₂ FA (R₂ stability order: C₂, C₃>C_18∶1, C₁₀>C₈>C₄, C₆). The relationship between the water-retaining ability and the molecular structure of DAG is discussed from the viewpoint of intra- and intermolecular interactions between the FA chains.