多目标动态规划时段轮换并行算法

针对SIMD和MIMD结构的并行机提出多目标动态规划时段轮换并行算法,多目标动 态规划的时段轮换迭代算法,将全过程优化问题转化成子过程优化问题,然后在子过程非劣解 集中寻找全过程非劣解.这样,将多目标动态规划内存不足的问题转化成时间问题,然后利用 并行机超高速运算的优势来有效地解决内存不足问题.通过时间复杂性、加速比分析及实例. 说明了算法的有效性及优越性.     

基于采样和MIMD结构的背包问题并行算法

背包问题属于著名的NP完全问题，在信息密码学和数论研究中有着极其重要的应用。在深入分析背包问题现有并行算法的基础上，本文提出了一种基于采样和MIMD结构的背包问题并行求解算法，并给出了算法性能的理论分析和在IBMP690超级计算机上的实验结果。实验结果表明，当背包实例的维数n≥40时，本算法的并行效率可达60％以上。因此，本并行算法具有较好的可扩展性，能应用于各种MIMD结构的并行机上有效地求解背包问题。     

带释放时间的并行机调度问题的ILS & SS算法

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search(SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果改进了6.06%,并明显优于多点下降算法.     

带释放时间的并行机调度问题的ILS & SS算法

研究工件带释放时间的两类并行机最小化总完成时间的调度问题.针对问题提出了一种新的基于变深度环交换邻域结构的Iterated local search(ILS)算法.1)提出了变深度环交换邻域结构.2)基于变深度环交换和传统Swap的混合邻域,提出了带有两种kick策略的ILS算法.3)为了加强ILS逃出局部最优的能力,将Scatter search (SS)搜索方法引入了ILS算法中;算法将当前最好解和次好解进行分散处理,再从处理后的解开始继续迭代.为了验证算法的有效性,对两类并行机问题分别随机产生100组数据进行试验.实验结果表明:对于同构并行机问题,引入SS的ILS算法的计算结果与下界的平均偏差为0.99%,而没有引入SS的ILS算法的为1.06%;对于无关并行机问题,引入SS搜索方法后,ILS算法的计算结果 改进了6.06%,并明显优于多点下降算法.     

方格取数问题的动态规划算法

动态规划算法对很多实际问题的解决是灵活和高效的.首先对方格取数问题进行分析,通过一条路径和两条路径选择的对比分析,得出了该问题的动态规划算法,并对该算法关键部分加以代码实现,最后对该算法的时间和空间复杂度进行分析和讨论,并对复杂度进行优化.试验的结果说明了该算法对于解决该类问题在时间效率上要明显优于贪心算法等一些算法.     

Internet拥塞控制系统在不同源控制算法作用下的资源竞争分析

在未来的Internet拥塞控制协议中,不同的用户群根据不同的QoS需求,可以实现不同的控制算法.系统地研究了拥塞控制系统在AIMD和MIMD两类源算法共同作用下的稳态和动态特性,这些特性揭示了配置不同源控制算法的用户群对网络资源的竞争.内容包括AIMD,MIMD算法共同作用下的系统模型、系统稳态分析、系统稳定性分析等.基于NS2系统的仿真结果,证实了给出的分析方法的有效性,并揭示了不同源算法对网络资源的竞争情况.     

基于粗糙规划的不确定加工时间的并行机调度

针对并行机调度中的不确定工件加工时间,提出用粗糙变量表示不确定量,并由此建立该问题的粗糙期望值规划模型.提出一种应用于调度问题的进化规划算法,改进了针对并行机问题的编码方式和变异方法.采用粗糙模拟的方法计算个体的适应值,即粗糙期望估计值,并加以不同规模的算例进行仿真实验.仿真结果表明,改进进化规划算法得到的解优于遗传算法得到的解.     

一种基于统计的排序算法

本文提出了一种基于统计的快速排序算法 ,并对该算法的时间复杂度和空间复杂度进行了分析 .该算法要求排序关键字满足一定的约束条件 ,其时间复杂度为 O(n) .对该算法做一些简单的修改 ,还可以将其推广到对一般关键字的排序问题 .     

复杂并行机调度问题基于分解的优化算法

针对纺织生产过程中广泛存在的带特殊工艺约束的大规模并行机调度问题，提出了一种基于分解的优化算法。首先将原调度问题分解为机台选择和工件排序两个子问题，然后针对机台选择子问题提出一种进化规划算法，并采用一种具有多项式时间复杂度的最优算法求解工件排序子问题，以得到问题特征信息（即每台机器对应拖期工件数的最小值），该问题特征信息用以指导进化规划算法的迭代过程。不同规模并行机调度问题的数值计算结果及实际制造企业应用效果表明，本文提出的算法是有效的。     

复合并行机排序问题的启发式算法研究

为有效解决复合并行机排序的极小化最大完成时间问题,提出了分支定界算法和改进的启发式动态规划算法。利用分支定界算法的3个工具:分支模型、边界和优先规则,构建出分支搜索树。按优先规则进行定界搜索,从而减小了问题求解规模。将原始作业转换为虚拟作业,根据Johnson法则,求解出原问题的最优排序。改进的动态规划算法复杂度分析和计算实验表明,这两个算法可靠性高并且可以解决实际问题。     

Parallel implementation of finite-element/newton method for solution of steady-state and transient nonlinear partial differential equations

Domain decomposition by nested dissection for concurrent factorization and storage (CFS) of asymmetric matrices is coupled with finite element and spectral element discretizations and with Newton's method to yield an algorithm for parallel solution of nonlinear initial-and boundary-value problem. The efficiency of the CFS algorithm implemented on a MIMD computer is demonstrated by analysis of the solution of the two-dimensional, Poisson equation discretized using both finite and spectral elements. Computation rates and speedups for the LU-decomposition algorithm, which is the most time consuming portion of the solution algorithm, scale with the number of processors. The spectral element discretization with high-order interpolating polynomials yields especially high speedups because the ratio of communication to computation is lower than for low-order finite element discretizations. The robustness of the parallel implementation of the finite-element/Newton algorithm is demonstrated by solution of steady and transient natural convection in a two-dimensional cavity, a standard test problem for low Prandtl number convection. Time integration is performed using a fully implicit algorithm with a modified Newton's method for solution of nonlinear equations at each time step. The efficiency of the CFS version of the finite-element/Newton algorithm compares well with a spectral element algorithm implemented on a MIMD computer using iterative matrix methods.Submitted toJ. Scientific Computing, August 25, 1994.     

A parallel algorithm for the enumeration of the spanning trees of a graph

As is well known, the strategy of divide-and-conquer is widely used in problem solving. The method of partitioning is also a fundamental strategy for the design of a parallel algorithm. The problem of enumerating the spanning trees of a graph arises in several contexts such as computer-aided design and computer networks. A parallel algorithm for solving the problem is presented in this paper. It is based on the principle of the inclusion and exclusion of sets, and not directly based on the partitioning of the graph itself. The results of the preliminary experiments on a MIMD system appear promising.     

The parallel odd-even merge algorithm

This paper briefly describes the implementation of the odd-even merge algorithm on a parallel MIMD computer and discusses its computational complexity.     

绝对时钟智能控制器的研制

介绍了一种日常参数智能控制器的研制及研制过程中的几个重要问题的解决方法。特别是用于城市照明及美化城市的彩灯的开、关时间智能控制方面，给出了依据当地绝对时间、经度、纬度进行昼夜时间计算的方法，使之在不接光电传感器情况下可跟踪季节的昼夜变化。控制系统采用８９Ｃ２０５１单片机，配有时钟日历芯片ＤＳ１２８８７，系统体积小、功能强、可靠性高。     

Parallel rendering of fractal surfaces

Fractal surfaces are a sueful modeling technique for terrain in computer graphics. Although an algorithm exists for ray tracing (Mandelbrot) fractal surfaces, the technique is computationally very expensive. The large degree of parallelism inherent in the problem suggests the use of parallel architectures for generating these images. We describe a parallel rendering algorithm for shared memory MIMD machines which takes advantage of image coherence to reduce computation. This algorithm has, on a Sequent Balance 2100 with 20 processors, demonstrated a near-linear speedup. We examine the possible synchronization bottlenecks by statically assigning different numbers of CPUs to sections of the screen.This work was supported in part by DARPA under contract MDA903-86-C-0182.     

Asynchronous self-organizing maps

A recently defined energy function which leads to a self-organizing map is used as a foundation for an asynchronous neural-network algorithm. We generalize the existing stochastic gradient approach to an asynchronous parallel stochastic gradient method for generating a topological map on a distributed computer system (MIMD). A convergence proof is presented and simulation results on a set of problems are included. A practical problem using the energy function approach is that a summation over the entire network is required during the computation of updates. Using simulations we demonstrate effective algorithms that use efficient sampling for the approximation of these sums.     

Computing biconnected components on a hypercube

We describe two hypercube algorithms to find the biconnected components of a dense connected undirected graph. One is a modified version of the Tarjan-Vishkin algorithm and the other is an adaptation of Read's sequential algorithm. The two hypercube algorithms were experimentally evaluated on an NCUBE/7 MIMD hypercube computer. The two algorithms have comparable performance, and efficiencies as high as 0.7 were observed on dense graphs.This research was supported in part by the National Science Foundation under grants DCR84-20935 and MIP 86-17374.     

Performance of lattice QCD programs on CP-PACS

The CP-PACS is a massively parallel MIMD computer with the theoretical peak speed of 614 GFLOPS which has been developed for computational physics applications at the University of Tsukuba, Japan. We report on the performance of the CP-PACS computer measured during recent production runs using our quantum chromodynamics code for the simulation of quarks and gluons in particle physics. With the full 2048 processing nodes, our code shows a sustained speed of 237.5 GFLOPS for the heat-bath update of gluon variables, 264.6 GFLOPS for the over-relaxation update, and 325.3 GFLOPS for quark matrix inversion with an even–odd preconditioned minimal residual algorithm.