Parallel computing in networks of workstations with Paralex

Modern distributed systems consisting of powerful workstations and high-speed interconnection networks are an economical alternative to special-purpose supercomputers. The technical issues that need to be addressed in exploiting the parallelism inherent in a distributed system include heterogeneity, high-latency communication, fault tolerance and dynamic load balancing. Current software systems for parallel programming provide little or no automatic support towards these issues and require users to be experts in fault-tolerant distributed computing. The Paralex system is aimed at exploring the extent to which the parallel application programmer can be liberated from the complexities of distributed systems. Paralex is a complete programming environment and makes extensive use of graphics to define, edit, execute, and debug parallel scientific applications. All of the necessary code for distributing the computation across a network and replicating it to achieve fault tolerance and dynamic load balancing is automatically generated by the system. In this paper we give an overview of Paralex and present our experiences with a prototype implementation     

Parallel techniques for information extraction from hyperspectral imagery using heterogeneous networks of workstations

Recent advances in space and computer technologies are revolutionizing the way remotely sensed data is collected, managed and interpreted. In particular, NASA is continuously gathering very high-dimensional imagery data from the surface of the Earth with hyperspectral sensors such as the Jet Propulsion Laboratory's airborne visible-infrared imaging spectrometer (AVIRIS) or the Hyperion imager aboard Earth Observing-1 (EO-1) satellite platform. The development of efficient techniques for extracting scientific understanding from the massive amount of collected data is critical for space-based Earth science and planetary exploration. In particular, many hyperspectral imaging applications demand real time or near real-time performance. Examples include homeland security/defense, environmental modeling and assessment, wild-land fire tracking, biological threat detection, and monitoring of oil spills and other types of chemical contamination. Only a few parallel processing strategies for hyperspectral imagery are currently available, and most of them assume homogeneity in the underlying computing platform. In turn, heterogeneous networks of workstations (NOWs) have rapidly become a very promising computing solution which is expected to play a major role in the design of high-performance systems for many on-going and planned remote sensing missions. In order to address the need for cost-effective parallel solutions in this fast growing and emerging research area, this paper develops several highly innovative parallel algorithms for unsupervised information extraction and mining from hyperspectral image data sets, which have been specifically designed to be run in heterogeneous NOWs. The considered approaches fall into three highly representative categories: clustering, classification and spectral mixture analysis. Analytical and experimental results are presented in the context of realistic applications (based on hyperspectral data sets from the AVIRIS data repository) using several homogeneous and heterogeneous parallel computing facilities available at NASA's Goddard Space Flight Center and the University of Maryland.     

Parallel implementation of fuzzy minimals clustering algorithm

Clustering aims to classify different patterns into groups called clusters. Many algorithms for both hard and fuzzy clustering have been developed to deal with exploratory data analysis in many contexts such as image processing, pattern recognition, etc. However, we are witnessing the era of big data computing where computing resources are becoming the main bottleneck to deal with those large datasets. In this context, sequential algorithms need to be redesigned and even rethought to fully leverage the emergent massively parallel architectures. In this paper, we propose a parallel implementation of the fuzzy minimals clustering algorithm called Parallel Fuzzy Minimal (PFM). Our experimental results reveal linear speed-up of PFM when compared to the sequential counterpart version, keeping very good classification quality.     

AprioriTid算法的MapReduce并行化实现

为解决AprioriTid算法对大数据执行效率不高的问题,根据Hadoop平台的MapReduce模型,分析了AprioriTid算法的并行化方法,给出了并行化的主要步骤和Map、Reduce函数的描述。与串行的AprioriTid算法相比,并行算法利用了多个节点的计算能力,缩短了从大数据集中挖掘关联规则的时间。对并行算法的性能进行了测试,实验结果表明,并行AprioriTid算法具有较高的执行效率和较好的可扩展性。     

Parallel merging: algorithm and implementation results

An efficient parallel algorithm for merging two sorted lists is presented. The algorithm is based on a novel partitioning algorithm that splits the two lists among the processors, in a way that ensures load balance during the merge. The partitioning algorithm can itself be efficiently parallelized, allowing the solution to scale with increased numbers of processors. A shared memory multiprocessor is assumed. The time complexity for partitioning and merging is O(N/p + log N), where p is the number of processors and N is the total number of elements in the two lists. Implementation results on a twenty node Sequent Symmetry multiprocessor are also presented.     

Adaptive internal representation in circular back-propagation networks

Surface- and prototype-based models are often regarded as alternative paradigms to represent internal knowledge in trained neural networks. This paper analyses a network model (Circular Back-Propagation) that overcomes such dualism by choosing the best-fitting representation adaptively. The model involves a straightforward modification to classical feed-forward structures to let neurons implement hyperspherical boundaries; as a result, it exhibits a notable representation power, and benefits from the simplicity and effectiveness of classical back-propagation training. Artificial testbeds support the model definition by demonstrating its basic properties; an application to a real, complex problem in the clinical field shows the practical advantages of the approach.     

基于Hadoop平台的LDA算法的并行化实现

随着互联网的飞速发展,需要处理的数据量不断增加,在互联网数据挖掘领域中传统的单机文本聚类算法无法满足海量数据处理的要求,针对在单机情况下,传统LDA算法无法分析处理大规模语料集的问题,提出基于MapReduce计算框架,采用Gibbs抽样方法的并行化LDA主题模型的建立方法。利用分布式计算框架MapReduce研究了LDA主题模型的并行化实现,并且考察了该并行计算程序的计算性能。通过对Hadoop并行计算与单机计算进行实验对比,发现该方法在处理大规模语料时,能够较大地提升算法的运行速度,并且随着集群节点数的增加,在加速比方面也有较好的表现。基于Hadoop平台并行化地实现LDA算法具有可行性,解决了单机无法分析大规模语料集中潜藏主题信息的问题。     

基于并行计算的气溶胶定量遥感反演模型实现

为了加快气溶胶光学厚度(AOD)反演计算速度,基于SYNTAM串行算法,提出了循环分块划分和聚合通信的策略,利用消息传递模型,在中国气象局的IBM Cluster 1600高性能计算机系统上,并行实现了从MODIS双星(TERRA和AQUA)卫星数据反演AOD。试验结果表明该方法大大减少了计算时间,与地面太阳光度计实测AOD数据进行对比验证,发现所有站点处的AOD反演相对误差小于22%,表明这种并行方法可以满足高精度监测空气质量要求。     

Parallel dynamic programming on clusters of workstations

The standard DP (dynamic programming) algorithms are limited by the substantial computational demands they put on contemporary serial computers. In this work, the theory behind the solution to serial monadic dynamic programming problems highlights the theory and application of parallel dynamic programming on a general-purpose architecture (cluster or network of workstations). A simple and well-known technique, message passing, is considered. Several parallel serial monadic DP algorithms are proposed, based on the parallelization in the state variables and the parallelization in the decision variables. Algorithms with no interpolation are also proposed. It is demonstrated how constraints introduce load unbalance which affect scalability and how this problem is inherent to DP.     

自适应动量项BP神经网络盲均衡算法

为了消除数字信号在传输过程中产生的码间串扰,使得接收端能够正确解调,对信道畸变进行有效补偿,在基于动量项BP神经网络盲均衡算法的基础上,提出一种能够自适应调节BP神经网络动量项的盲均衡算法.该算法根据盲均衡过程中误差函数的变化情况,自适应调节BP神经网络的动量项,充分发挥动量项在避免网络训练陷于较浅的局部极小点的优势.仿真实验结果表明,该算法在稳定性及收敛性能上均优于固定动量BP神经网络盲均衡算法.     

A symbolic interpretation for back-propagation networks

Two main problems for the neural network (NN) paradigm are discussed: the output value interpretation and the symbolic content of the connection matrix. In this article, we construct a solution for a very common architecture of pattern associators: the backpropagation networks. First, we show how Zadeh's possibility theory brings a formal structure to the output interpretation. Properties and practical applications of this theory are developed. Second, a symbolic interpretation for the connection matrix is proposed by designing of an algorithm. By accepting the NN training examples as input this algorithm produces a set of implication rules. These rules accurately model the NN behavior. Moreover, they allow to understand it, especially in the cases of generalization or interference.     

Exploiting fine-grained idle periods in networks of workstations

Studies have shown that for a significant fraction of the time, workstations are idle. In this paper, we present a new scheduling policy called Linger-Longer that exploits the fine-grained availability of workstations to run sequential and parallel jobs. We present a two-level workload characterization study and use it to simulate a cluster of workstations running our new policy. We compare two variations of our policy to two previous policies: Immediate-Eviction and Pause-and-Migrate. Our study shows that the Linger-Longer policy can improve the throughput of foreign jobs on a cluster by 60 percent with only a 0.5 percent slowdown of local jobs. For parallel computing, we show that the Linger-Longer policy outperforms reconfiguration strategies when the processor utilization by the local process is 20 percent or less in both synthetic bulk synchronous and real data-parallel applications     

High-performance routing in networks of workstations with irregulartopology

Networks of workstations are rapidly emerging as a cost-effective alternative to parallel computers. Switch-based interconnects with irregular topology allow the wiring flexibility, scalability, and incremental expansion capability required in this environment. However, the irregularity also makes routing and deadlock avoidance on such systems quite complicated. In current proposals, many messages are routed following nonminimal paths, increasing latency and wasting resources. In this paper, we propose two general methodologies for the design of adaptive routing algorithms for networks with irregular topology. Routing algorithms designed according to these methodologies allow messages to follow minimal paths in most cases, reducing message latency and increasing network throughput. As an example of application, we propose two adaptive routing algorithms for ANI (previously known as Autonet). They can be implemented either by duplicating physical channels or by splitting each physical channel into two virtual channels. In the former case, the implementation does not require a new switch design. It only requires changing the routing tables and adding links in parallel with existing ones, taking advantage of spare switch ports. In the latter case, a new switch design is required, but the network topology is not changed. Evaluation results for several different tapologies and message distributions show that the new routing algorithms are able to increase throughput for random traffic by a factor of up to 4 with respect to the original up*/down* algorithm, also reducing latency significantly. For other message distributions, throughput is increased more than seven times. We also show that most of the improvement comes from the use of minimal routing     

Design optimization with back-propagation neural networks

A methodology with back-propagation neural network models is developed to explore the artificial neural nets (ANN) technology in the new application territory of design optimization. This design methodology could go beyond the Hopfield network model, Hopfield and Tank (1985), for combinatorial optimization problems In this approach, pattern classification with back-propagation network, the most demonstrated power of neural networks applications, is utilized to identify the boundaries of the feasible and the infeasible design regions. These boundaries enclose the multi-dimensional space within which designs satisfy all design criteria. A feedforward network is then incorporated to perform function approximation of the design objective function. This approximation is performed by training the feedforward network with objective functions evaluated at selected design sets in the feasible design regions. Additional optimum design sets in the classified feasible regions are calculated and included in the successive training sets to improve the function mapping. Iteration is continued until convergent criteria are satisfied. This paper demonstrates that the artificial neural nets technology provides a global perspective of the entire design space with good and near optimal solutions. ANN can indeed be a potential technology for design optimization.     

Parallel volume rendering on a network of workstations

An algorithm for parallel volume rendering on general-purpose workstations connected to a local area network (LAN) is presented. The algorithm is based on an efficient scan-line algorithm for volume rendering of irregular meshes. This algorithm computes images by intersecting the mesh with successive planes defined through each scan line and perpendicular to the screen. These planes are called scan planes. Image coherency from one scan plane to the next, and within each scan plane, speeds up image computation. The proposed algorithm is a modified version of the scan-line algorithm, suitable for parallelization and for handling large data sets efficiently. Based on an efficiency analysis of this version, it is concluded that minimal additional computing and communication are required if each processor is given the task of computing sequences of successive lines in the image. Ways of achieving good load balancing on a group of heterogeneous workstations that have arbitrary loads by other users are suggested     

新型总线中并行CRC算法的设计与实现

为了对动态可重构高速串行总线UM-BUS进行差错控制,提出了一种用于新型总线数据校验的四通道并行CRC算法.根据UM-BUS的多通道并发通信方式和通道动态组织特点,采用四体FIFO进行数据缓冲存储,并设计了满足总线特点的四通道并行CRC编解码器.在此基础上,给出了它的FPGA实现方案和仿真结果.该并行CRC编解码器,可实时计算总线通信数据的CRC校验码,已成功的应用于动态可重构高速串行总线系统中,实现对突发错误的实时检测,通信速率达到100Mbps/通道.     

基于Spark的改进K-means算法的并行实现

针对K-means聚类算法存在的不足,提出了改进K-means来提高算法的性能,利用简化后的轮廓系数作为评估标准衡量K-means算法中◢k◣值,采用K-means++完成K-means算法初始中心点的选择。设置好◢k◣值以及初始中心点后使用形态学相似距离作为相似度测量标准将数据点归属到距离最近的中心点形成的簇中,最后计算平均轮廓系数确定合适的◢k◣值,并在Spark上实现算法并行化。通过对四个标准数据集在准确性、运行时间和加速比三个方面的实验表明,改进后的K-means算法相对于传统的K-means算法和SKDK-means算法不仅提高了聚类划分质量,缩短了计算时间,而且在多节点的集群环境下表现出良好的并行性能。实验结果分析出提出的改进算法能有效提高算法执行效率和并行计算能力。     

大规模生物网络马尔可夫聚类的并行化算法

马尔可夫聚类算法（MCL）是在大规模生物网络中寻找模块的一个有效方法，能够挖掘网络结构和功能影响力较大的模块。算法涉及到大规模矩阵计算，因此复杂度可达立方阶次。针对复杂度高的问题，提出了基于消息传递接口（MPI）的并行化马尔可夫聚类算法以提高算法的计算性能。首先，生物网络转化成邻接矩阵；然后，根据算法的特性，按照矩阵的规模判断并重新生成新矩阵以处理非平方倍数矩阵的计算；其次，并行计算通过按块分配的方式能够有效地实现任意规模矩阵的运算；最后，循环并行计算直至收敛，得到网络聚类结果。通过模拟网络和真实生物网络数据集的实验结果表明，与全块集体式通信（FCC）并行方法相比，平均并行效率提升了10个百分点以上，因此可以将该优化算法应用在不同类型的大规模生物网络中。     

AODV算法在无线Mesh网络中的开发与实现

为了在Linux嵌入式系统平台上实现AODV路由协议,提出了基于Netfilter功能框架的AODV协议在Linux平台上实现的具体方法.根据AODV路由协议的特点,采用比较有代表性的UU实现方法.该方法使用Netfilter来截获本地外及本地内的报文,采用内核可加载模块来实现对操作系统的扩充.通过视频监控系统对AODV路由协议进行验证,验证结果表明了该方案的可行性和算法的有效性.     

Parallel implementation of backpropagation neural networks on aheterogeneous array of transputers

This paper analyzes parallel implementation of the backpropagation training algorithm on a heterogeneous transputer network (i.e., transputers of different speed and memory) connected in a pipelined ring topology. Training-set parallelism is employed as the parallelizing paradigm for the backpropagation algorithm. It is shown through analysis that finding the optimal allocation of the training patterns amongst the processors to minimize the time for a training epoch is a mixed integer programming problem. Using mixed integer programming optimal pattern allocations for heterogeneous processor networks having a mixture of T805-20 (20 MHz) and T805-25 (25 MHz) transputers are theoretically found for two benchmark problems. The time for an epoch corresponding to the optimal pattern allocations is then obtained experimentally for the benchmark problems from the T805-20, TS805-25 heterogeneous networks. A Monte Carlo simulation study is carried out to statistically verify the optimality of the epoch time obtained from the mixed integer programming based allocations. In this study pattern allocations are randomly generated and the corresponding time for an epoch is experimentally obtained from the heterogeneous network. The mean and standard deviation for the epoch times from the random allocations are then compared with the optimal epoch time. The results show the optimal epoch time to be always lower than the mean epoch times by more than three standard deviations (3sigma) for all the sample sizes used in the study thus giving validity to the theoretical analysis.