嵌入式系统的细粒度多处理器实时抢占式调度算法

现有的嵌入式实时系统调度算法一般以任务级为调度单位,对此提出一种细粒度的线程级多处理器实时调度算法。采用DAG图描述实时系统的任务,并采用任务分解法将其分解为线程形式;为任务级调度采用基于干扰的可调度性分析,为线程级调度采用基于工作负载的可调度性分析;将线程的偏移、截止期与优先级作为三个调度目标,设计混合线程级调度算法。仿真实验结果表明,算法对于多线程任务的实时系统具有较好的性能。     

基于CORBA的海量数据加载并行任务调度技术研究与实现

基于多集群的并行任务调度技术,简要描述在使用Oracle 10g进行海量数据加载中的并行任务调度问题,设计实现了一个基于CORBA的海量信息加载服务中的并行任务调度算法。通过测试结果表明,在适当的任务并行度的前提下,采取并行任务调度算法的加载服务的数据加载能力要优于传统的加载服务。     

基于MPI的集群监控系统

为了有效地监控集群系统,基于消息传递接口（Message Passing Interface,MPI）并行库构建一个简单易行的并行任务模型．详细介绍该任务模型中的集群监控、节点负载均衡评估模型结构以及Linux集群数据采集．实验表明该模型配置简单、资源开销低,且对集群系统的干扰小．     

异构多核全局限制性可抢占并行任务可调度分析

异构多核平台可以利用不同类别体系结构的处理器来执行特定任务,从而达到提高性能和降低功耗的目的. 然而,向大规模异构平台迁移极其困难,且大规模的、必要的程序并行会导致软件调度的复杂度. 虽然,基于有向无环图（directed acyclic graph, DAG）并行任务模型已有相关的研究工作,但是基于DAG任务模型的限制性可抢占的调度策略研究仍存在不足. 鉴于此,主要讨论了DAG任务在异构平台上进行全局固定优先级限制性可抢占调度时的最差响应时间(worst case response time,WCRT)分析,对并行任务的每个结点可用的处理器资源进行了一定的限制,即只能执行在规定类型处理器上的任务. 基于最新的单分类并行任务的可调度性分析,提出了多个并行任务的可调度性分析. 进一步,提出了高优先级任务的干涉量与低优先级任务的阻塞量的计算方法;结合最新的分类并行任务的任务内干涉计算方法,最终提出了一种伪多项式的分析方法. 实验结果表明,提出的算法能够在合理的时间范围内得到任务集可调度性的分析结果,且任务集的接受率随各个参数的变化符合预期.

     

基于有限状态机的联锁平台任务同步模型研究

二乘二取二铁路计算机联锁系统中,两套4个CPU组成了容错计算结构,实现CPU之间的同步是基于表决的容错计算机系统的关键过程。因此,本文提出了一种基于有限状态机的主/备/从并行任务同步模型,用于准确描述系统中不同CPU对象的任务同步状态,为二乘二取二同步通信表决过程大规模复杂的逻辑和时序设计提供了方法学上的参考和简化。     

求解云计算压力测试中并行任务密度的高速算法

针对当前云计算负载压力测试过程中,对所采集数据计算并行任务密度的算法效率较低的问题,基于空间换时间的思路,使用数学分析的方法,提出了一种时间复杂度为O(n lb n),空间复杂度为O(n)的求解并行任务密度的高速算法。实验结果表明,该算法与时间复杂度同为O(n lb n)的OpenSTA算法相比,效率约有6~8倍的提升。该算法对多个相同的并行任务密度能够解得并行时长最长者,可以准确反映负载最重的情况。该算法适合云计算进行负载均衡算法设计时,获取真实参照数据使用。     

线性加速比并行实时任务的节能研究

节能设计是嵌入式实时系统中一个重要的研究方向.目前的研究大多采用串行任务模型,很少关注并行任务.文中研究了在离散工作模式与实时约束下,多核平台下的线性加速比并行实时任务的能耗最小化问题.文中假设所有处理器核都支持DVS技术且加速比是线性的,在此条件下,文中首先给出一个定理证明了当各任务执行在系统全部核上时系统能耗最小.然后,将问题建模为一个0-1整数线性规划,利用最早截止期优先算法确定任务调度,并给出了两个高效的节能算法确定各任务的工作频率.文中最后通过大量的模拟实验,证明提出的算法的效果显著,可以达到几乎与最优解相同的节能效果.     

云计算中相似驱动的并行任务划分方法

云计算是并行计算、分布式计算和网格计算等高性能计算的进一步发展,它的异构性、按需等特征对高性能计算提出了新的挑战。针对云计算的典型特征,提出了基于并行任务和云环境相似驱动的任务划分方法。首先用图刻画了并行任务和云环境,建立了图的相似关系及其相似度计算方法;其次给出云计算中拟解决的问题,通过图局部相似和全局相似度偏差最小来实现并行任务和体系结构的异构匹配及按需要求;接着利用F度标号方法给出相似驱动的任务划分算法;最后通过实验和其他划分方法进行比较,阐明了该方法的优点。     

基于进程投机并行的运行时系统设计与优化

投机并行化是解决遗留串行代码并行化的重要技术,但以往投机并行化运行时系统面临着诸多的性能问题,如任务分配不均衡、通信频繁、冲突代价高,以及进程启动,结柬频繁而导致开销过高等。为此,提出一种基于进程实现的投机并行化运行时系统。采用隐式单程序多数据的并行任务划分和执行模式。通过实现重甩进程的投机任务调度策略和委托正确性检查技术,降低投机进程启动/结束和通信的开销,提高投机进程的利用率,同时利用守护进程与投机进程协同执行的方式,确保在投机进程出现异常情况时程序也能正确执行。实验结果表明,该基于进程实现的投机运行时系统比同类型系统的性能提高231%。     

MR-DBSCAN： a scalable MapReduce-based DBSCAN algorithm for heavily skewed data

DBSCAN （density-based spatial clustering of ap- plications with noise） is an important spatial clustering tech- nique that is widely adopted in numerous applications. As the size of datasets is extremely large nowadays, parallel process- ing of complex data analysis such as DBSCAN becomes in- dispensable. However, there are three major drawbacks in the existing parallel DBSCAN algorithms. First, they fail to prop- erly balance the load among parallel tasks, especially when data are heavily skewed. Second, the scalability of these al- gorithms is limited because not all the critical sub-procedures are parallelized. Third, most of them are not primarily de- signed for shared-nothing environments, which makes them less portable to emerging parallel processing paradigms. In this paper, we present MR-DBSCAN, a scalable DBSCAN algorithm using MapReduce. In our algorithm, all the crit- ical sub-procedures are fully parallelized. As such, there is no performance bottleneck caused by sequential process- ing. Most importantly, we propose a novel data partitioning method based on computation cost estimation. The objective is to achieve desirable load balancing even in the context of heavily skewed data. Besides, We conduct our evaluation us- ing real large datasets with up to 1.2 billion points. The ex- periment results well confirm the efficiency and scalability of MR-DBSCAN.