Massively Parallel Probabilistic Reasoning with Boltzmann Machines

We present a method for mapping a given Bayesian network to a Boltzmann machine architecture, in the sense that the the updating process of the resulting Boltzmann machine model probably converges to a state which can be mapped back to a maximum a posteriori (MAP) probability state in the probability distribution represented by the Bayesian network. The Boltzmann machine model can be implemented efficiently on massively parallel hardware, since the resulting structure can be divided into two separate clusters where all the nodes in one cluster can be updated simultaneously. This means that the proposed mapping can be used for providing Bayesian network models with a massively parallel probabilistic reasoning module, capable of finding the MAP states in a computationally efficient manner. From the neural network point of view, the mapping from a Bayesian network to a Boltzmann machine can be seen as a method for automatically determining the structure and the connection weights of a Boltzmann machine by incorporating high-level, probabilistic information directly into the neural network architecture, without recourse to a time-consuming and unreliable learning process.     

Experiments of Fast Learning with High Order Boltzmann Machines

This work reports the results obtained with the application of High Order Boltzmann Machines without hidden units to construct classifiers for some problems that represent different learning paradigms. The Boltzmann Machine weight updating algorithm remains the same even when some of the units can take values in a discrete set or in a continuous interval. The absence of hidden units and the restriction to classification problems allows for the estimation of the connection statistics, without the computational cost involved in the application of simulated annealing. In this setting, the learning process can be sped up several orders of magnitude with no appreciable loss of quality of the results obtained.     

Parallel Processing of First Order Linear Recurrence on SMP Machines

In this paper, we propose a new algorithm that analyzes the data dependency pattern in the first-order linear recurrence (FOLR) and transforms it into algebraically equivalent expanded form so that it can be processed in parallel using the threads on symmetric multiprocessor (SMP) machines. The transformation aims to eliminate the data dependencies in the naive nested form of the FOLR. However, as this transformation may result in extra multiplication operations, our algorithm examines the immanent overhead of the expanded form of the FOLR and generates a new hybrid form of the FOLR. The hybrid form combines nested and appropriately expanded form in order to make it suitable for parallel processing. The parallel algorithm based on the hybrid form of the FOLR is analytically examined and tested through implementation on SMP machines. The implementation details, such as the workload balancing between processors and the optimization of cache performance, are also discussed. The experimental results show that the parallel algorithm based on the hybrid form of the FOLR considerably improves the performance on SMP machines that have three of more processors.     

Preemptive Scheduling on Uniform Parallel Machines with Controllable Job Processing Times

In this paper, we provide a unified approach to solving preemptive scheduling problems with uniform parallel machines and controllable processing times. We demonstrate that a single criterion problem of minimizing total compression cost subject to the constraint that all due dates should be met can be formulated in terms of maximizing a linear function over a generalized polymatroid. This justifies applicability of the greedy approach and allows us to develop fast algorithms for solving the problem with arbitrary release and due dates as well as its special case with zero release dates and a common due date. For the bicriteria counterpart of the latter problem we develop an efficient algorithm that constructs the trade-off curve for minimizing the compression cost and the makespan.     

一个并行分枝限界算法产生器的设计与实现

分枝限界算法是一种求解组合优化问题的一般性方法,并行化是提高算法性能的有效手段。文章使用［５］中提出的算法模式和结构模式的概念和思想设计并实现了一个并行分枝限界算法的产生器。该产生器通过提供并行分枝限界算法的抽象框架,将它应用于要求解的问题,可以得到问题的并行分枝限界算法。     

网络并行计算在物探数据处理中的应用

通过构建PVM的网络并行计算平台,将并行计算的环境应用于勘探地球物理的计算中,利用互联网上的计算机资源实现大问题的并行计算,使得许多优秀的算法得以体现和广泛地应用。该文介绍了系统平台的构建、任务的划分和分派、处理结果的回收及对系统效果进行评价等内容。     

一种半监督支持向量机优化方法

针对半监督支持向量机在采用间隔最大化思想对有标签样本和无标签样本进行分类时面临的非凸优化问题,提出了一种采用分布估计算法进行半监督支持向量机优化的方法EDA_S3VM。该方法把无标签样本的标签作为需要优化的参数,从而得到一个在标准支持向量机上的组合优化问题,利用分布估计算法通过概率模型的学习和采样来对问题进行求解。在人工数据集和公共数据集上的实验结果表明,EDA_S3VM与其它一些半监督支持向量机算法相比有更高的分类准确率。     

基于算法图的并行计算优化

研究基于算法图的并行计算优化设计方法。通过引入算法图，从数学机理上算法的并行结构进行描述，针对不同要求提出了对计算网络的并行优化设计方法，为设计并行算法提供了新的有途途径。     

CUDA并行计算技术在情报信息研判中的应用

文章在研究公安情报信息研判技术的基础上,提出了一种基于CUDA并行计算技术的方法,实现对公安情报信息中文本信息快速分类的方法,实现将CUDA技术的快速计算能力应用到公安情报研判工作中。该文从介绍CUDA技术的概况出发,阐述了基于CUDA并行计算技术的文本分类方法,以及该方法的详细实现过程,解决了高效处理海量文本信息的问题。实验结果证明,CUDA并行计算技术在公安情报信息研判工作中卓有成效。     

基于网格计算技术的电力系统分布式并行计算——底层平台设计与实现

文章提出了基于网格计算来实现电力系统分布式并行计算的方案。主要涉及计算池(ComputingPool)的设计、资源的管理与动态分配,以及图论分割和稀疏数值计算库的设计和实现等。文章首先介绍了网格计算应用于电力系统分布式并行计算的概念,在此基础上,分析了基于GlobusR网格计算开发平台实现的以上功能模块。最后对测试平台和测试结果进行了简要的介绍。     

适合于多种并行计算结构的TRANSPUTER互连结构：HCCTT

本文将提出一种用于Ｔｒａｎｓｐｕｔｅｒ多机系统的Ｈａｍｉｌｔｏｎ回路连接三元树互连结构，并给出其构造算法。这种结构的Ｔｒａｎｓｐｕｔｅｒ多机系统在其通信服务程序的支持下，可以很好地适应扇型，星型，环和超环等多种并行结构的计算，并且系统的并行处理规模可扩充性强。     

网络并行计算在图象处理中的应用

当前随着计算要求的不断提高,并行计算发展方法未艾,网络并行计算更成为新的潮流,在并行处理中,图象处理是一个重要的应用领域。提出一种动态并行方法,以此实现Ｍａｎｄｅｌｂｒｏｔ图形。通过对实验数据的分析,对于任务规模和并行计算的加速比进行了研究。     

An Efficient Parallel Algorithm for Computing the Gaussian Convolution of Multi-dimensional Image Data

In this paper, we propose a parallel convolution algorithm for estimating the partial derivatives of 2D and 3D images on distributed-memory MIMD architectures. Exploiting the separable characteristics of the Gaussian filter, the proposed algorithm consists of multiple phases such that each phase corresponds to a separated filter. Furthermore, it exploits both the task and data parallelism, and reduces communication through data redistribution. We have implemented the proposed algorithm on the Intel Paragon and obtained a substantial speedup using more than 100 processors. The performance of the algorithm is also evaluated analytically. The analytical results confirming with the experimental results indicate that the proposed algorithm scales very well with the problem size and number of processors. We have also applied our algorithm to the design and implementation of an efficient parallel scheme for the 3D surface tracking process. Although our focus is on 3D image data, the algorithm is also applicable to 2D image data, and can be useful for a myriad of important applications including medical imaging, magnetic resonance imaging, ultrasonic imagery, scientific visualization, and image sequence analysis.     

计算网格中基于时间均衡的并行粗粒度任务调度算法

考虑网格资源异构、自治、动态等特性,讨论本地用户具有强占优先权情况下的任务调度问题,提出了TBBS(Time-Balancing Based Scheduling Algorithm)算法.建立调度优化模型,以期望完成时间最小为目标选择执行任务的最佳资源组合.以时间均衡策略将任务分解并调度到资源上执行,减少了子任务同步时因等待而产生的延时,获得较好的并行计算性能.采用重复调度策略,适应计算网格中资源的特性.     

Subclasses of solvable problems from classes of combinatorial optimization problems

Well-known subclasses of solvable problems from classes of combinatorial optimization are reviewed. For solvable problems such as the traveling salesman problem, location problem, assignment problem, and clustering problem, the changes in the objective function on a given ordering of combinatorial configurations are analyzed. Translated from Kibernetika i Sistemnyi Analiz, No. 2, pp. 97–105, March–April 2009.     

Modelling of a Utility Boiler Using Parallel Computing

A mathematical model for the simulation of the turbulent reactive flow and heat transfer in a power station boiler has been parallelized. The mathematical model is based on the numerical solution of the governing equations for mass, momentum, energy and transport equations for the scalar quantities. The k- model and the conserved scalar/prescribed probability density function formalism are employed. Radiative heat transfer is calculated using the discrete ordinates method. The code has been fully parallelized using the spatial domain decomposition approach and MPI. Calculations were performed using an IBM-SP2. It is shown that the computational requirements are reduced and the parallel efficiency increases if the mean temperature and density are calculated a priori, and stored. The role of the different parts of the code on the parallel performance is discussed. A speedup of 5.9 is achieved using 8 processors.     

Evaluating solution sets of <Emphasis Type="Italic">a posteriori</Emphasis> solution techniques for bi-criteria combinatorial optimization problems

The quality of an approximate solution for combinatorial optimization problems with a single objective can be evaluated relatively easily. However, this becomes more difficult when there are multiple objectives. One potential approach to solving multiple criteria combinatorial optimization problems when at least one of the single objective problems is NP-complete, is to use an a posteriori method that approximates the efficient frontier. A common difficulty in this type of approach, however, is evaluating the quality of approximate solutions, since sets of multiple solutions should be evaluated and compared. This necessitates the use of a comparison measure that is robust and accurate. Furthermore, a robust measure plays an important role in metaheuristic optimization for tuning various parameters for evolutionary algorithms, simulated annealing, etc., which are frequently employed for multiple criteria combinatorial optimization problems. In this paper, the performance of a new measure, which we call Integrated Convex Preference (ICP) is compared to that of other measures appearing in the literature through numerical experiments—specifically, we use two a posteriori solution techniques based on genetic algorithms for a bi-criteria parallel machine scheduling problem and evaluate their performance (in terms of solution quality) using different measures. Experimental results show that the ICP measure evaluates the solution quality of approximations robustly (i.e., similar to visual comparison results) while other alternative measures can misjudge the solution quality. We note that the ICP measure can be applied to other non-scheduling multiple objective combinatorial optimization problems, as well.     

一种面向多核系统的并行计算任务分配方法

随着多核处理器的普及,目前的大规模并行处理系统普遍采用多核处理器,这对于资源管理和调度提出了更高的要求.提出了基于共享Cache资源划分的方法,建立了面向多核处理器支持Cache资源分配的进程调度模型,设计并实现了并行任务到多核处理器的映射算法,更好地解决了大规模资源管理系统中面向多核处理器的任务分配问题,降低了使用共享Cache的多个进程运行时的相互干扰,提升了应用程序性能.     

Remarks on stability of solutions of the property domination problem

A class of combinatorial problems is considered whose investigation and solution require the notions of the theory of fuzzy sets. The necessary and sufficient conditions of stability are given. Translated from Kibernetika i Sistemnyi Analiz, No. 4, pp. 36–40, July–August, 1999.     

Parallel Learning of Belief Networks in Large and Difficult Domains

Learning belief networks from large domains can be expensive even with single-link lookahead search (SLLS). Since a SLLS cannot learn correctly in a class of problem domains, multi-link lookahead search (MLLS) is needed which further increases the computational complexity. In our experiment, learning in some difficult domains over more than a dozen variables took days. In this paper, we study how to use parallelism to speed up SLLS for learning in large domains and to tackle the increased complexity of MLLS for learning in difficult domains. We propose a natural decomposition of the learning task for parallel processing. We investigate two strategies for job allocation among processors to further improve load balancing and efficiency of the parallel system. For learning from very large datasets, we present a regrouping of the available processors such that slow data access through the file system can be replaced by fast memory access. Experimental results in a distributed memory MIMD computer demonstrate the effectiveness of the proposed algorithms.