随机行走算法在IC芯片热分析中的应用

针对大规模IC芯片中局部高温热效应问题,提出一种应用随机行走算法对芯片进行热分析的技术.首先简述随机行走问题的基本概念,给出问题的理论解法;然后讨论基于三维网格划分的IC芯片热等效阻容网络模型,着重分析随机行走算法在热等效模型中的应用,并建立一个实际芯片的热等效模型,采用随机行走算法模拟计算模型的稳态温度分布和瞬态温度变化;最后针对随机行走算法应用中的不足,提出了伪并行行走和结果重用2种加速技术.实验结果表明,随机行走算法能够胜任大规模热等效网络的分析,计算精度满足热分析要求,所提出的加速技术能够显著地提高算法的执行效率.     

基于并行PLS算法的化学计量学软件研究

现有化学计量学软件普遍采用的偏最小二乘(PLS)算法均以单线程方式计算,建模速度缓慢,给应用带来较大的不便。随着多核处理器的普及,采用多线程并行计算技术可显著提高算法执行速度。本文将多线程并行计算技术引入化学计量学软件开发,提出并实现了PLS算法的并行化计算。利用标准数据集进行了性能对比实验,结果表明在四核计算机中多线程并行计算比单线程计算有大约3.1倍的速度提升。     

并行计算中的负载均衡问题研究

在多处理机系统中,任务的静态分配和进程的动态调度都要求做到负载平衡。一个负载平衡的多处理机系统,将具有较高的系统性能,使并行程序总的执行时间最短。本文介绍了并行计算中的负载均衡问题,着重对动态负载平衡算法的组成以及几种典型的动态负载平衡算法进行了讨论与分析。     

基于MPI的并行医学图像处理

本文就并行计算技术在医学图像处理领域应用的优势和现状,论述了医学图像处理算法的并行实现方法,并在并行计算集群上实现了CT图像Sobel算子边缘检测及基于互信息的单模PET图像配准的MPI并行算法。针对这两种不同应用和不同的机群规模分析了并行计算的性能,说明了并行计算技术在该领域的适用范围。     

基于SIMD—PRAM模型的分块图像匹配算法设计

该文研究了基于SIMD—PRAM计算模型的有限处理元阵列规模的并行计算算法设计,分析了求阵列和的并行算法性能,运用求阵列和、图像分块映射与四邻平移等方法提出了一种根据处理元局部可用资源进行分块计算的图像匹配算法。计算机模拟实验结果表明,该算法完整、高效地执行了图像匹配,具有良好的并行计算性能。     

分布异构工作站上的任务调度算法

讨论了在一个由高速局域网连接的高性能异构工作站平台上，如何有效地利用空闲工作站来求解计算密集型任务矩阵相乘的问题，为了获得较好的并行计算性能，文中给出了一个异构工作站群之间任务调度的模型和算法，算法中考虑了并行计算中协作任务间的通信时间、数据加栽时间、结果收集时间和各个异构工作站的任务计算时间，通过这个模型，可以在所有可利用的工作站集合中找出最适合的子集，获得最短的执行时间．     

基于算法生成树的遥感并行算法的设计与实现

对当前遥感影像处理中存在的信息提取速度慢、CPU利用率低的问题进行了分析和讨论,在此基础上提出了算法生成树的概念,并提出了对此生成树的一种并行执行方法;该方法能够提高CPU利用率、缩短算法执行时间算法能够并行执行,试验表明此种方法执行效率比常规算法的效率要高;另外,该算法已在实际项目中得到应用,系统运行稳定,执行效率高.     

基于任务复制的多关键路径任务调度算法

高效的任务调度算法使多核处理器的资源分配和并行计算能力更加高效。通过研究关键路径对任务调度算法的重要性后提出TDMCP算法。对DAG上关键任务的确定采用一种多关键路径选取的方法,使得关键路径上信息在任务调度的每一步都是实时更新的;保证调度的每一步优先执行紧迫性高的任务;对首任务采用任务复制技术,使得后续任务的调度更加的高效,从整体上提高任务调度效率。和两个经典任务调度算法进行实验性能的比较,比较结果表明TDMCP算法在任务调度时间和算法执行效率方面都要优于两种经典算法。     

OpenMP多核技术在颗粒流体力学方法GHM中的应用

为了达到提高颗粒流体动力学方法 GHM计算效率的目标,分析了GHM模型的主要计算模块,抽取其中的可并行计算模块,基于多核计算机的硬件环境,应用OpenMP多线程并行计算模型,对采用数值积分方法求解颗粒运动方程的部分,实现求解过程的并行计算。最后通过多次实验验证程序的正确性及算法性能。实验结果表明,在Windows 7系统4核8线程处理器的计算机上,并行程序的并行加速比最高达到了2.5,说明OpenMP多核并行技术能较显著地提高GHM方法的计算性能。     

基于性能预测的并行软件模块设计研究

并行计算软件库,如scalapack和plapack,通过提供大量并行计算子过程来提高并行计算软件开发效率。为方便用户使用并行软件库,该文提出了一种基于性能预测技术来开发并行计算软件库的方法,这是一种隐藏并行计算细节的有效途径。并就构成该软件库的神威超级计算机系统并行软件开发工具,并行线性代数软件库的数据自动分布的方法和供用户调用并行软件库的接口设计技术进行了讨论。实验结果表明,这种技术能有效提高并行计算软件效率。     

基于GPU的芯片热分析方法研究

针对大规模IC芯片中局部高温热效应问题,提出基于网格的随机行走方法分析稳态温度分布。该算法只计算热源附近的点,从而大幅减少计算量。首先对金字塔型非规则热分析模型进行了研究,然后提出了一种预先保存概率表的加速策略。将随机行走算法在CUDA上实现了并行,得出了最大限度使用GPU资源并保证最大加速比的最优配置。实验结果表明,提出的并行随机行走算法,使总体计算性能提升了7-10倍。     

一个面向神经计算的并行计算机系统的性能分析与测试

文中主要以一个面向神经计算的并行计算机系统ＮｅｕｒｏＣ为背景，讨论一种并行计算机性能分析模型，并对ＮｅｕｒｏＣ进行性能分析．根据实际并行神经计算模型、ＮｅｕｒｏＣ的结构和计算特点，给出了并行神经计算中一些与性能相关的结论，最后给出了一些系统实际测试结果．     

Transputer simulation of decoupled electrical circuits

This paper describes a parallel simulation of an electrical circuit using the Transmission Line Modelling (TLM) method. The TLM method is used to decouple the circuit into sub-circuits which are then simulated concurrently in a parallel processing system. This approach not only simplifies the circuit formulation process but also reduces the overall computing time of the circuit simulation when compared with traditional sequential method. The techniques for decoupling the circuit and implementing the parallel algorithm are described. The method is demonstrated in an electrical circuit simulation. Comparison of the computing time and simulated results with the sequential approach confirms the computing efficiency and accuracy of the proposed method.     

A parallel algorithm for random walk construction with applicationto the Monte Carlo solution of partial differential equations

Random walks are widely applicable in statistical and scientific computations. In particular, they are used in the Monte Carlo method to solve elliptic and parabolic partial differential equations (PDEs). This method holds several advantages over other methods for PDEs as it solves problems with irregular boundaries and/or discontinuities, gives solutions at individual points, and exhibits great parallelism. However, the generation of each random walk in the Monte Carlo method has been done sequentially because each point in the walk is derived from the preceding point by moving one grid step along a randomly selected direction. A parallel algorithm for random walk generation in regular as well as irregular regions is presented. The algorithm is based on parallel prefix computations. The communication structure of the algorithm is shown to ideally fit on a hypercube of n nodes, where n is the number of processors     

基于FP-Growth的图上随机游走推荐方法

推荐是促进诸如社交网络等应用活跃度的重要模式,但 庞大 的节点规模以及复杂的节点间关系给社交网络的推荐问题带来了挑战。随机游走是一种能够有效解决这类推荐问题的策略,但传统的随机游走算法没有充分考虑相邻节点间影响力的差异。提出一种基于FP-Growth的图上随机游走推荐方法,其基于社交网络的图结构,引入FP-Growth算法来挖掘相邻节点之间的频繁度,在此基础上构造转移概率矩阵来进行随机游走计算,最后得到好友重要程度排名并做出推荐。该方法既保留了随机游走方法能有效缓解数据稀疏性等特性,又权衡了不同节点连接关系的差异性。实验结果表明,提出的方法比传统随机游走算法的推荐性能更佳。     

随机行走算法研究及其在电源/地线网络瞬态优化中的应用

实验分析了电源/地线(P/G)网络的随机行走算法,与传统的预优共轭梯度法比较发现,当随机行走求解较少节点时性能较好,但在大规模P/G网络瞬态分析中相对较慢.通过修改随机行走过程进行伴随网络的瞬态分析,提出一种快速计算灵敏度的算法.实验结果表明,该算法计算时间较短,与精确结果误差较小.     

PRAM和LARPBS模型上的近似串匹配并行算法

近似串匹配技术在网络信息搜索、数字图书馆、模式识别、文本挖掘、IP路由查找、网络入侵检测、生物信息学、音乐研究计算等领域具有广泛的应用.基于CREW-PRAM(parallel random access machine with concurrent read and exclusive write)模型,采用波前式并行推进的方法直接计算编辑距离矩阵D,设计了一个允许k-差别的近似串匹配动态规划并行算法,该算法使用(m+1)个处理器,时间复杂度为O(n),算法理论上达到线性加速;采取水平和斜向双并行计算编辑距离矩阵D的方法,设计了一个使用((m+1)个处理器和O(n/(+m)时间的、可伸缩的、允许k-差别的近似串匹配动态规划并行算法,.基于分治策略,通过灵活拆分总线和合并子总线动态重构光总线系统,并充分利用光总线的消息播送技术和并行计算前缀和的方法,实现了汉明距离的并行计算,设计了两个基于LARPBS(linear arrays with reconfigurable pipelined bus system)模型的通信高效、可扩放的允许k-误配的近似串匹配并行算法,其中一个算法使用n个处理器,时间为O(m);另一个为常数时间算法,使用mn个处理器.     

Identification of nonstationary stochastic systems using parallelestimation schemes

The parallel (multiple-model) schemes for identification of nonstationary stochastic systems are considered. First, the form of the optimal-local Bayesian predictor is derived under the assumptions that system coefficients vary according to the random walk model and that the Kalman-filter-based algorithms are used for identification purposes. A rational extension of this strategy, which can be applied to identification algorithms of any form, is discussed. Specific suggestions are made concerning the possible choice of adaptation gains of the competitive adaptive filters. Computer simulation results, confirming the good estimation robustness properties of the parallel identification schemes, are presented. It is shown that the proposed scheme can significantly decrease sensitivity of the identification algorithm to the rate of nonstationarity of the analyzed system or (alternatively) to the choice of design parameters such as adaptation gains and forgetting factors     

Benchmarking Explicit State Parallel Model Checkers

This paper presents a set of benchmarks and metrics for performance reporting in explicit state parallel model checking algorithms. The benchmarks are selected for controllability, and the metrics are chosen to measure speedup and communication overhead. The benchmarks and metrics are used to compare two parallel model checking algorithms: partition and random walk. Implementations of the partition algorithm using synchronous and asynchronous communication are used. Metrics are reported for each benchmark and algorithm for up to 128 workstations using a network of dynamically loaded workstations. Empirical results show that load balancing becomes an issue for more than 32 workstations in the partition algorithm and that random walk is a reasonable, low overhead, approach for finding errors in large models. The synchronous implementation is consistently faster than the asynchronous. The benchmarks, metrics and results given here are intended to be a starting point for a larger discussion of performance reporting in parallel explicit state model checking.