Scheduling parallel dedicated machines with the speeding‐up resource

We consider a problem of scheduling jobs on m parallel machines. The machines are dedicated, i.e., for each job the processing machine is known in advance. We mainly concentrate on the model in which at any time there is one unit of an additional resource. Any job may be assigned the resource and this reduces its processing time. A job that is given the resource uses it at each time of its processing. No two jobs are allowed to use the resource simultaneously. The objective is to minimize the makespan. We prove that the two‐machine problem is NP‐hard in the ordinary sense, describe a pseudopolynomial dynamic programming algorithm and convert it into an FPTAS. For the problem with an arbitrary number of machines we present an algorithm with a worst‐case ratio close to 3/2, and close to 3, if a job can be given several units of the resource. For the problem with a fixed number of machines we give a PTAS. Virtually all algorithms rely on a certain variant of the linear knapsack problem (maximization, minimization, multiple‐choice, bicriteria). © 2008 Wiley Periodicals, Inc. Naval Research Logistics, 2008     

JPEG2000遥感图像实时压缩系统中基于并行机制的“零时间”数据搬移策略

为了满足JPEG2000遥感图像实时压缩设备的实时性要求,提出了一种基于并行机制的“零时间”数据搬移策略。通过对EBC算法结构进行拆分,并采用EDMA方式进行数据搬移,使得算法运算与数据搬移过程完全并行,搬移时间等效为零。实验结果表明,采用新的数据搬移策略后,编码效率可以提升到100％,EBC算法实现的总时间可缩短46％以上。该搬移机制已成功应用于JPEG2000星载遥感图像实时压缩系统中,系统的实时性达到了设计要求。     

双正交重叠变换系数基于上下文的算术编码算法

提出了一种双正交重叠变换(LBT)系数基于上下文的算术编码算法.针对二进整数LBT在DSP实现过程中出现的精度和计算复杂度问题,提出了一种适于DSP并行处理的LBT定点实现方法.编码算法包含60种上下文概率模型,熵编码采用MQ编码,并根据并行处理的需要,将MQ编码从位平面扫描过程中分离,根据分离后的结构特点,设计了改进的MQ编码器.并对算法的DSP实现进行了研究.实验结果表明,本压缩算法压缩性能和SPIHT相当,稍逊于JPEG2000,算法容易并行,硬件计算复杂度很低.     

On allocating one active redundancy to coherent systems with dependent and heterogeneous components' lifetimes

This article studies coherent systems of heterogenous and statistically dependent components' lifetimes. We present a sufficient and necessary condition for a stochastically longer system lifetime resulted by allocating a single active redundancy. For exchangeable components' lifetimes, allocating the redundancy to the component with more minimal path sets is proved to produce a more reliable system, and for systems with stochastic arrangement increasing components' lifetimes and symmetric structure with respect to two components, allocating the redundancy to the weaker one brings forth a larger reliability. Several numerical examples are presented to illustrate the theoretical results as well. © 2016 Wiley Periodicals, Inc. Naval Research Logistics 63: 335–345, 2016     

基于改进QPSO-NN的冗余机械臂逆运动学算法

针对某种冗余机械臂逆运动学求解的问题,提出了一种基于改进量子粒子群神经网络的求解算法。以冗余机械臂末端位姿为输入,经神经网络求得其逆解;针对神经网络输出结果误差较大的问题,把神经网络求初值加入初始化的粒子群中,通过基于Metropolis准则改进量子粒子群算法,避免了量子粒子群算法的早熟现象;以关节坐标经正向运动学求得的末端位姿和期望位姿的误差为适应度函数,对机械臂关节坐标迭代寻优。仿真结果表明该方法结合了神经网络算法的快速性和改进量子粒子群算法的精确性,满足求冗余机械臂逆运动学问题的速度和精度要求。     

长向量处理器高效RNN推理方法

模型深度的不断增加和处理序列长度的不一致对循环神经网络在不同处理器上的性能优化提出巨大挑战。针对自主研制的长向量处理器FT-M7032,实现了一个高效的循环神经网络加速引擎。该引擎采用行优先矩阵向量乘算法和数据感知的多核并行方式,提高矩阵向量乘的计算效率;采用两级内核融合优化方法降低临时数据传输的开销;采用手写汇编优化多种算子,进一步挖掘长向量处理器的性能潜力。实验表明,长向量处理器循环神经网络推理引擎可获得较高性能,相较于多核ARM CPU以及Intel Golden CPU,类循环神经网络模型长短记忆网络可获得最高62.68倍和3.12倍的性能加速。     

栅格地理数据并行格式转换引擎

如今大规模地理数据正在社会各个部门和组织中迅速积累,但是由于部门利益和历史沿袭等原因,大规模地理数据共享仍然极具挑战,相应共享技术需求仍然极其旺盛。作为地理数据共享的基础方式之一,传统单机地理数据格式转换技术,一方面受限于磁盘读写及带宽瓶颈,另一方面面对日趋庞大的数据规模,已很难满足实际应用需求。因此提出一种针对栅格地理数据的并行格式转换引擎,采用高性能计算集群环境支持大规模栅格地理数据转换共享,大幅降低了大规模栅格地理数据转换过程的时间成本。栅格地理数据并行格式转换引擎采用基于公共接口的设计理念,框架灵活、具有良好的扩展性,支持地理数据格式的读写自定义以及新数据格式添加,能够实现接入数据格式间的任意两两转换。为验证引擎框架及其处理效率,在Lustre并行集群环境下以格网数据交换格式(国家地理空间数据交换格式)向常见栅格地理格式的转换为示例进行了测试实验。结果表明,栅格地理数据并行格式转换引擎能够在8个节点Lustre集群中达到7.54的良好并行加速比。     

Asymptotically optimal component assembly plans in repairable systems and server allocation in parallel multiserver queues

T identical exponential lifetime components out of which G are initially functioning (and B are not) are to be allocated to N subsystems, which are connected either in parallel or in series. Subsystem i, i = 1,…, N, functions when at least K_i of its components function and the whole system is maintained by a single repairman. Component repair times are identical independent exponentials and repaired components are as good as new. The problem of the determination of the assembly plan that will maximize the system reliability at any (arbitrary) time instant t is solved when the component failure rate is sufficiently small. For the parallel configuration, the optimal assembly plan allocates as many components as possible to the subsystem with the smallest K_i and allocates functioning components to subsystems in increasing order of the K_i's. For the series configuration, the optimal assembly plan allocates both the surplus and the functioning components equally to all subsystems whenever possible, and when not possible it favors subsystems in decreasing order of the K_i's. The solution is interpreted in the context of the optimal allocation of processors and an initial number of jobs in a problem of routing time consuming jobs to parallel multiprocessor queues. © John Wiley & Sons, Inc. Naval Research Logistics 48: 732–746, 2001     

基于SHARC流水集束型多处理器板研制

结合某重点工程课题 ,设计和实现了基于 SHARC流水集束型多处理器板即研制出了具有 5个 SHARC的高速并行数字信号处理机。板上处理器数量可实现重配置以获得高的性价比。当板上前端 4个 SHARC用于 FFT时 ,研究和分析了板上前端 4个 SHARC用于 FFT时的三种不同缓冲数据模式下 FFT节点处理性能     

数据库中关联规则的并行/分布式采掘技术

高效的并行/分布式采掘方法是数据库中关联规则发现技术的重要的研究方向,首先给出了关联规则的并行/分布式采掘的相关描述,针对关联规则并行/分布式采掘的基本思想,分析算法中可以改进效能的环节,提出生成更少候选集、局部剪枝、减少通讯量和优化扫描等提高性能和降低复杂度的方法。