关键词： 多处理器   容错调度   全局调度   硬实时系统   优先级提升  

摘要： 在主副版本机制的全局容错调度中,副版本运行窗口短,采用优先级继承策略的副版本响应时间长,容易错失截止期.针对副版本实时性差的问题,提出基于优先级提升策略的全局容错调度算法(fault tolerant global scheduling with backup priority promotion,FTGS-BPP),通过赋予副版本比主版本高的优先级,减少副版本在运行过程中受到的干扰,缩短了副版本的响应时间,改善了副版本的实时性,从而减少了实现容错所需的额外处理器资源.仿真结果表明,和采用优先级继承策略的全局容错调度算法相比,FTGS-BPP在调度相同的任务集时明显降低了处理器资源需求.

关键词： 多处理器   任务调度   差分进化   算法   惯性  

摘要： 针对多处理器系统任务调度复杂问题,在自适应差分进化算法基础上增加惯性速度分项,提出一种称为惯性速度差分进化(IVDE)的改进算法,以避免陷入局部最优解.结合启发式任务列表,对算法的状态编码提出了处理器列表(PL)、部分偏序任务列表(PTL)和全部任务列表(CTL)等3种形式.通过求解随机生成的任务调度标准图和真实求解任务问题,进行了数值仿真验证,其中PTL-IVDE算法相比蚁群优化(ACO)算法、混合遗传算法(TLPLC-GA),能快速求得更好的任务调度方案.

关键词： 互聯網路   容錯   系統可靠度   邊連結度   超邊連結度   比較式偵錯模型   強偵錯能力   條件式偵錯度   類超立方體   增廣立方體  

摘要： 近年来，由於计算机VLSI技术的快速发展，一个多处理器系统可能包含成千上百个处理器。研究一个互联网路的错误容忍度是确保系统安全性的重要步骤。更进一步的，一个系统如有能力自动对处理器侦错，才能将坏的处理器进行替换。 超边连通度是评估一个大型互联网路安全性及错误容忍度的重要参数。给一个非负整数g，一个图G的g-超边连通度代表的意义是拿掉最少的边数，使得图G不连通，但是剩下的图，每个部分都至少有g个点。本篇论文证明了n维超立方体的g-超边连通度是4n－8。 目前侦错问题一经广泛的被讨论，很多有名的互联网路系统之侦错度也已经被计算出来。本篇论文提供了决定系统强侦错度及条件侦错度的充分条件。我们运用它证明了增广立方体的强侦错度是2n－1，条件式侦错度是6n－17。

关键词： 嵌入式系统   多处理器   任务调度   并行处理   容错技术  

摘要： 随着航天遥感技术的发展，星上采集的数据量增大，星载嵌入式系统的处理能力和存储能力必须得到提升。在存储方面，必须采用大容量存储器将采集到的数据可靠存储下来。在处理方面，必须采用多处理器并行处理架构保证处理能力。本文主要从大容量存储器的容错技术和多处理器的并行处理技术两个方面研究嵌入式系统的关键技术。\n 大容量存储器是星载嵌入式系统的重要器件，只有保证采集到的数据可靠存储，才能进行后续的处理工作。NAND Flash是最常用的大容量存储设备之一。由于位翻转效应的存在，NAND Flash必须添加高效的、可移植性高的容错措施才能保证可靠存储。本文的主要研究工作有:\n 1)本文首先对比分析现有的容错方法，提出了一种能够通过软件快速实现的BCH码译码方法。利用余式比较法求校正子、简化的PGZ方法求错误位置多项式，Zinoviev法求错误位置多项式的根。与现有方法相比能降低复杂度，使软件实现与硬件实现具有相比拟的编译码性能，获得更高的灵活性。\n 2)提出一种基于“Error locality”特性的读错误修正方法。Error locality特性告诉我们两次写数据中间有近60％到90％读错误的位置保持不变。本方法在读数据时预先比较修正Error Map中记录的具有Error locality特性的错误位置信息，使得需要纠错码纠正的错误位数大大降低。\n 3)本文还提出一种用于MLC型NAND Flash的动态ECC纠错方法。包括三个模块:ECC选择模块通过可靠性查找表预估BER，选择合适的ECC;错误修正模块借助2）中提出的读错误修正方法预先修正具有Error locality特性的错误;动态ECC纠错模块提供不同能力的ECC。本方法具有更低的存储冗余和时间开销，基于ADSP-TS201（主频600MHz）的平均读数据吞吐率达到485.4Mbps，满足大部分的实时数据处理需求。且应用灵活，可移植性高，使得纠错控制编码的使用对NAND Flash读写效率的影响大大降低。\n 大容量存储器中存储的数据，需要在星上进行实时快速处理。为了达到这一目的，目前星上嵌入式系统均采用多处理器并行处理架构。因此并行能力的发挥对嵌入式系统的处理能力具有至关重要的作用。这就需要高效的并行任务调度算法提升处理器利用率。本文的主要研究工作有:\n 1)本文给出一种通用的并行任务调度问题的系统架构，分为处理器模型、任务模型、任务调度策略和评价指标四部分。在分析本课题组嵌入式系统应用环境的特点之后，建立最为常用的并行任务模型:DAG任务模型和Fork-Join任务模型，分别进行任务调度算法研究。\n 2)针对任务之间依赖性较强的DAG任务模型，本文提出一种新的任务调度算法。将前驱任务节点分为三类，在保证最早开始时间的前提下，优先考虑关键前驱节点所在处理器是否满足直接插入、通信间隙插入及关键前驱复制条件。然后对自由非关键前驱进行分配，依次考虑能否跳过非关键前驱、直接插入现有处理器或增加新处理器。本方法非关键前驱任务也能得到合并，可以降低处理器消耗，减少调度时长，提高处理器利用率。\n 3)针对规则性较强的Fork-Join任务模型，本文提出一种通信受限条件下的TSFJ_SC调度算法。针对串行通信场合，可以严格限制处理器的数目，以规定的最少处理器完成任务调度。引入busy-window的概念模拟信道占用情况，在不推迟最早开始时间的前提下优先考虑插入主处理器、通信间隙占用、插入从处理器、插入空白新处理器等分配规则。本方法可以避免通信冲突，在处理器数目、调度长度、处理器利用率等方面均具有十分优越的效果。\n 通过以上研究，大容量存储器的容错技术能够保证星载嵌入式系统可靠高效的存储采集到的遥感数据。多处理器并行任务调度算法的研究保证嵌入式系统具有良好的并行性能，采集的数据能够快速实时处理。以上两项关键技术的突破对星载嵌入式系统的推广实现具有重要的研究意义。

关键词： 超大规模集成电路   容错技术   多处理器   子阵列重构算法   可满足性  

摘要： 二维网状连接（mesh）的超大规模集成电路（VLSI）阵列是一种应用广泛的高性能体系结构，但随着VLSI的集成密度的不断提高，被集成在单一硅晶片上的处理单元的数量呈指数级别增加，硅晶片内部的处理单元在制造和使用过程中也不可避免的会发生故障。并且目前的制作工艺也无法保证芯片在整个工作寿命中，其内部的所有处理器单元都不会发生故障，所以容错多处理器阵列的重构技术也逐渐成为研究的热点问题之一。\n 关于多处理器阵列重构的容错技术主要是用来重构含有故障的处理单元的处理器阵列，以便可以得到一个不包含故障单元的目标阵列。到目前为止，现有的研究成果主要关注于最大的目标阵列的重构算法，且对于高性能目标阵列的重构算法又普遍是基于启发式算法，但是通过启发式算法重构的目标阵列无法保证该目标阵列一定是高性能目标阵列，即目标阵列中长链接的数量是最小的。而对于超大规模集成电路来说，如果可以利用最低的能耗开销和最少的通信花费和时延等来完成相同任务量的工作时，则可认为其处于最佳的工作状态，而高性能目标阵列就是处于这种工作状态的处理器阵列。\n 针对高性能目标阵列的重构问题，首先，本文提出了二维网状链接的大规模集成电路处理器阵列的可满足性（SAT）降阶重构模型，其使得高性能目标阵列可以通过使用高效的可满足性求解器来构造。实验结果也表明目标阵列是可以被可满足性求解器从该可满足性模型中找到，即使是被一万多个变量和百万级别的析取子句所表示128?128的物理阵列的可满足性模型，都是可以通过可满足性求解器求出目标阵列。\n 其次，为了最大限度地减少目标阵列中的长链接数量，实现重构高性能目标阵列的目的。本文结合目标阵列的可满足性模型，分别提出了构造高性能目标阵列的完备算法和不完备的算法。其中完备算法是从可满足性模型的解空间中寻找一个长链接数量最少的目标阵列。虽然完备算法能够在小规模和低错误率的物理阵列中有较好的表现，即能够快速重构出高性能目标阵列。但对于大规模的物理阵列而言，由于其可满足性模型的解空间过于巨大，导致不能在有效时间内重构出高性能目标阵列。所以基于这一缺点，本文对该完备算法做了一定优化，提出了一个不完备的算法以搜寻满足系统要求的长链接数的目标阵列，相对于完备算法来说，由于其不需要从整个解空间中寻找最小长链接数量的目标阵列，使得不完备算法的适用范围得到了明显的增加，并且本文也通过与该问题的最新的发展状况的相比较，证明该不完备的算法是有效的。

关键词： 重新映射   单晶片网路   容错  

摘要： 我们提出了一个重新映射演算法能容忍单晶片网路之多处理器系统的处理元件(PE）的错误。一个新的图型建模被提出来以精确定义重新映射后的PE之间的沟通成本的变化量。我们的方法不仅可以用于修复PE故障，而且能改善给定的初始映射的沟通成本。实验结果显示，在多个PE错误下使用相同数量的备用PE，我们的方法比以前的方法[1]的沟通成本平均下降了43.59％。此外，我们的方法应用在由NMAP[2]产生初始映射后更进一步地减少了4.16％。

关键词： Ada programming language   Concurrent and multicore programming   Multicore and multiprocessor systems   Parallel  

摘要： Background/Objectives: Choosing a proper programming language for optimizing performance of multiprocessor systems is a trite object in the recent data processing era. Methods/Statistical Analysis: This research investigates Ada concomitant features for multicore programming. We have done several experiments to back the step that Ada is one of the best candidates for multiprocessor systems and this language is childbearing to be improved for multicore prospectus. Finding: By analyzing the simulation result we can say that Ada new features for supporting multicore programming are useful and they have improved the simulation speed. Thus it's better to schedule our tasks and set task affinity by a determined scenario using Ada new libraries rather than giving it simply to the underlying operation system. Conclusion/Application: We have done some simulation on different platforms with different models to evaluate the speed up gained using new library packages useful for multicore programming in Ada language.

关键词： Chip multiprocessors   Non uniform cache access   Uniform access  

摘要： Objective: Technology trend are one of the most important to use the bulky on-chip memories such as level-2 (L2) and level-3 (L3) cache. In this paper, Non-Uniform Cache access Architectures (NUCA) has been used in order to decrease the effects of the high access latencies. For the systems which operate at high frequency, the latencies of such caches are conquered by wire delays. Methods: In this architecture, several banks are partitioned and which is connected to the controller through switches and links. This larger cache memory increases overall wire delays across the chip due to very bulky latencies. The majority of the access time will not absorb them self and that occupy in the routing to and from the several banks. The predictable lower-level caches have the best ever access time among the entire the sub arrays, although such uniform cache access don't make the use of differences in latencies of the entire sub arrays. Findings: Hence there is a necessitate for non-uniform cache architectures where the cache memories is broken down into several banks that can be analyzed at dissimilar latencies and resulting in diminish of energy and power consumption. Applications/ Improvements: An experimental result shows the comparison of NUCA and UCA using SRAM/MRAM in terms of power and energy.

关键词： 任务管理计算机   多处理器   串行通信  

摘要： 针对航电系统任务管理计算机与外围多个设备进行高速通信的需求,本文介绍了一种基于多处理器的串行通信系统的设计思想,并详细阐述了此系统的功能、结构及具体的硬件和软件设计方法.经实际应用表明,该系统实时性好、可靠性高,满足工程要求.

关键词： 混合流水车间   多处理器   调度优化   拉格朗日算法  

摘要： 混合流水车间（Hybrid flow shop,HFS）问题最早是在石化工业背景下提出的，在传统的流水车间问题的基础上加上了并行机处理，所以该问题同时包含了流水作业和并行机的双重特征。HFS调度问题需要解决满足一定的约束条件下，比如技术资源约束，对多阶段的并行机进行合理的分配，最优化调度指标。在实际生产中存在广泛的应用，比如钢铁、电子制造、港口调度和纺织等。　　常见的混合流水车间调度问题允许同一时间同一个工件只能在一台加工机器上进行加工，而在实际生产中，比如半导体制造行业、泊位分配、实时机器视觉系统等中，工件在每个生产阶段加工时需要同时在多台处理器上加工，即存在多处理器任务的调度。带多处理器任务的HFS调度问题是传统的HFS问题的延伸。在多处理器任务调度中，每个工件可以同时在多台机器上进行加工。带多处理器任务的HFS调度问题不管是在理论还是实践中，都有很大的研究意义。　　针对带多处理器任务的HFS调度问题，考虑到并行机的存在、机器故障、运输时间、工件动态到达和在JIT模式下提前、拖期惩罚等条件，分别以总加权完成时间和总加权提前/拖期惩罚为目标函数，对车间进行调度优化。本文提出了一种基于传统的拉格朗日松弛算法上的改进算法，运用代理次梯度算法获得比较合适的更新方向，每次迭代仅最优化一个或者几个拉格朗日子问题，进而进行迭代更新。　　针对不同的目标函数，本文分别对多达150个工件和120个工件的不同问题的大量随机数据进行仿真测试，并将传统的拉格朗日算法下的结果与改进后基于代理次梯度算法的拉格朗日松弛算法得到的结果进行比较。结果表明，所提出的改进算法与传统的拉格朗日算法相比，有较好的求解能力，尤其是在解决大规模问题时，优势比较明显。