Minimizing total completion time in two-processor task systems with prespecified processor allocations

We consider the problem of scheduling multiprocessor tasks with prespecified processor allocations to minimize the total completion time. The complexity of both preemptive and nonpreemptive cases of the two-processor problem are studied. We show that the preemptive case is solvable in O(n log n) time. In the nonpreemptive case, we prove that the problem is NP-hard in the strong sense, which answers an open question mentioned in Hoogeveen, van de Velde, and Veltman (1994). An efficient heuristic is also developed for this case. The relative error of this heuristic is at most 100%. © 1998 John Wiley & Sons, Inc. Naval Research Logistics 45: 231–242, 1998     

多向嵌套循环的 FMS并行执行模式

基于小粒度并行结构的分类,提出了结构范式的概念。在此基础上,探讨了多向嵌套循环的并行执行问题,提出了父、母、子进程的概念以及面向多向嵌套循环的FMS 处理机调度策略     

基于 SBM的操作级并行处理算法研究

SBM是支持操作级并行的一种有效的同步机制。文中基于SBM对结点调度和barrier插入算法进行了深入的研究,提出了一套有效的开发操作级并行的方案。用一有向图G(N,A)表示指令之间的相关关系,并以结点的临界路径为关键字将结点从小到大进行排序。按照排序后的结点顺序,描述了一种分配算法,将结点分配给各处理机。同时,描述了相关结点之间的barrier插入算法。     

多处理器实时操作系统预计与评估算法研究

预计与评估算法为反导指控系统任务调度提供基础参考信息,是执行调度策略的先决条件。对基于多处理器的反导指控实时操作系统预计与评估算法进行了研究。首先介绍了这2个算法的典型应用环境;然后具体介绍了2个算法的实现;最后通过示例对算法的使用进行了进一步的说明。     

多处理机系统中的宏任务并行

多处理机系统是巨型机的发展方向。宏任务是在多处理机系统上用来加快程序执行的一条主要途径。文中介绍了宏任务并行,描述了宏任务的实现,讨论了编译器和操作系统的支持。最后解释了宏任务的一个程序。     

关于机器人力控制器计算机系统的设计方案探讨

本文从机器人力反馈依从控制的任务和要求出发,对机器人控制多处理机系统设计中的几个主要问题,包括总的系统结构、存储器结构、机间互连结构、中断系统结构、并发实时操作系统、处理机选型和多处理机系统的调试等,进行了探讨。     

多处理机系统的微任务并行

本文讨论微任务技术及其在多机系统上的实现。微任务技术使得一个程序能在循环和语句块一级并行执行,它的显著特点是系统开销较小、效率较高,适应于小粒度并行。     

Linear compound algorithms for the partitioning problem

For a given set S of nonnegative integers the partitioning problem asks for a partition of S into two disjoint subsets S₁ and S₂ such that the sum of elements in S₁ is equal to the sum of elements in S₂. If additionally two elements (the kernels) r₁, r₂ ∈ S are given which must not be assigned to the same set S_i, we get the partitioning problem with kernels. For these NP‐complete problems the authors present two compound algorithms which consist both of three linear greedylike algorithms running independently. It is shown that the worst‐case performance of the heuristic for the ordinary partitioning problem is 12/11, while the second procedure for partitioning with kernels has a bound of 8/7. © 2000 John Wiley & Sons, Inc. Naval Research Logistics 47: 593–601, 2000     

对舰用监控系统中复杂多机通讯模式实现方法的研究

结合舰船电力网络绝缘监测装置 ,提出了一种解决舰船监控系统中复杂多机通讯问题的方法 ,对其实现中的关键技术进行了细致的分析 ,并给出了结论 .