A flexibility coupled hypercube multiprocessor for high level vision

In general, message passing multiprocessors suffer from communication overhead between processors and shared memory multiprocessors suffer from memory contention. Also, in computer vision tasks, data I/O overhead limits performance. In particular, high level vision tasks, which are complex and require nondeterministic communication, are strongly affected by these disadvantages. This paper proposes a flexibly (tightly/loosely) coupled hypercube multiprocessor (FCHM) for high level vision to alleviate these problems. A variable address space memory scheme in which a set of adjacent memory modules can be merged into a shared memory module by a dynamically partitionable hypercube topology is proposed. The architecture is quantitatively analyzed using computational models and simulated on the Intel’s Personal SuperComputer (iPSC/I), a hypercube multiprocessor. A parallel algorithm for exhaustive search is simulated on FCHM using the iPSC/I showing significant performance improvements over that of the iPSC/I. This research was supported in part by IBM corporation.     

A slowdown model for applications executing on time-shared clustersof workstations

Distributed applications executing on clustered environments typically share resources (computers and network links) with other applications. In such systems, application execution may be retarded by the competition for these shared resources. In this paper, we define a model that calculates the slowdown imposed on applications in time-shared multi-user clusters. Our model focuses on three kinds of slowdown: local slowdown, which synthesizes the effect of contention for CPU in a single workstation; communication slowdown, which synthesizes the effect of contention for the workstations and network links on communication costs; and aggregate slowdown, which determines the effect of contention on a parallel task caused by other applications executing on the entire cluster, i.e., on the nodes used by the parallel application. We verify empirically that this model provides an accurate estimate of application performance for a set of compute-intensive parallel applications on different clusters with a variety of emulated loads     

Topology mapping of irregular parallel applications on torus-connected supercomputers

Supercomputers with ever increasing computing power are being built for scientific applications. As the system size scales up, so does the size of interconnect network. As a result, communication in supercomputers becomes increasingly expensive due to the long distance between nodes and network contention. Topology mapping, which maps parallel application processes onto compute nodes by considering network topology and application communication pattern, is an essential technique for communication optimization. In this paper, we study the topology mapping problem for torus-connected supercomputers, and present an analytical topology mapping algorithm for parallel applications with irregular communication patterns. We consider our problem as a discrete optimization problem in the geometric domain of a torus topology, and design an analytical mapping algorithm, which uses numerical solvers to compute the mapping. Experimental results show that our algorithm provides high-quality mappings on 3-dimensional torus, which significantly reduce the communication time by up to 72%.     

An efficient 3-dim FFT for plane wave electronic structure calculations on massively parallel machines composed of multiprocessor nodes

Three-dimensional Fast Fourier Transforms (FFTs) are the main computational task in plane wave electronic structure calculations. Obtaining a high performance on a large numbers of processors is non-trivial on the latest generation of parallel computers that consist of nodes made up of a shared memory multiprocessors. A non-dogmatic method for obtaining high performance for such 3-dim FFTs in a combined MPI/OpenMP programming paradigm will be presented. Exploiting the peculiarities of plane wave electronic structure calculations, speedups of up to 160 and speeds of up to 130 Gflops were obtained on 256 processors.     

PRAM programming: in theory and in practice

That the influence of the PRAM model is ubiquitous in parallel algorithm design is as clear as the fact that it is technologically infeasible for the forseeable future. The current generation of parallel hardware prominently features distributed memory and high‐performance interconnection networks—very much the antithesis of the shared memory required for the PRAM model. It has been shown that, in spite of communication costs, for some problems very fast parallel algorithms are available for distributed‐memory machines—from embarassingly parallel problems to sorting and numerical analysis. In contrast it is known that for other classes of problem PRAM‐style shared‐memory simulation on a distributed‐memory machine can, in theory, produce solutions of comparable performance to the best possible for such architectures. The Bulk Synchronous Parallel (BSP) model accurately represents most parallel machines—theoretical and actual—in an execution and cost model. We introduce a scalable portable PRAM realization appropriate for BSP computers and a methodology for usage. Our system is fast and built upon the familiar sequential C++ coupled with the new standard BSP library of parallel computation and communication primitives. It is portable to and predictable on a vast number of parallel computers including workstation clusters, a 256‐processor Cray T3D, an 8‐node IBM SP/2 and a 4‐node shared‐memory SGI Power Challenge machine. Our approach achieves simplicity of programming over direct‐mode BSP programming for reasonable overhead cost. We objectively compare optimized BSP and PRAM algorithms implemented with our C++ PRAM library and provide encouraging experimental results for our new style of programming. Copyright © 2000 John Wiley & Sons, Ltd.     

A scalable approach to solving dense linear algebra problems on hybrid CPU‐GPU systems

Aiming to fully exploit the computing power of all CPUs and all graphics processing units (GPUs) on hybrid CPU‐GPU systems to solve dense linear algebra problems, we design a class of heterogeneous tile algorithms to maximize the degree of parallelism, to minimize the communication volume, and to accommodate the heterogeneity between CPUs and GPUs. The new heterogeneous tile algorithms are executed upon our decentralized dynamic scheduling runtime system, which schedules a task graph dynamically and transfers data between compute nodes automatically. The runtime system uses a new distributed task assignment protocol to solve data dependencies between tasks without any coordination between processing units. By overlapping computation and communication through dynamic scheduling, we are able to attain scalable performance for the double‐precision Cholesky factorization and QR factorization. Our approach demonstrates a performance comparable to Intel MKL on shared‐memory multicore systems and better performance than both vendor (e.g., Intel MKL) and open source libraries (e.g., StarPU) in the following three environments: heterogeneous clusters with GPUs, conventional clusters without GPUs, and shared‐memory systems with multiple GPUs. Copyright © 2014 John Wiley & Sons, Ltd.     

A Compiler-Directed Approach to Network Latency Reduction for Distributed Shared Memory Multiprocessors

In distributed shared memory multiprocessor systems, parallel tasks communicate through sharing memory data. As the system size increases, such communication cost becomes the main factor that limits the overall parallelism and performance. In this paper, we propose a new solution to the problem through judiciously managing the relevant resource, namely, the shared data and the interconnection network (IN) through which the sharing is carried out. In this approach, communication cost is minimized by means of data migration/allocation which is based on analyzing general layered task graphs, sharing behavior of parallel tasks, and network topology. Our method is not applicable for read only variables. Further, for the time being, the usefulness of the method is limited to multiprocessors where no cache coherence mechanism is implemented. Four typical interconnection topologies for multiprocessors are considered, namely, shared-bus, hierarchical-bus, 2-D mesh, and fat-tree structures. Efficient data allocation algorithms for each of the four network topologies are developed that make decision on data allocation/migration at the compile time. The complexity of one algorithm isO(np) for shared-bus andO(n²p) for the remaining three in a system withnprocessors executing ap-layer task graph for one shared variable. We have also given an algorithm to determine optimal allocation/migration scheme for multiple shared variables. However, the cost of the algorithm become prohibitive when the number of shared variables is high. Therefore, a heuristic of low complexity is suggested. The heuristic is optimal for some topologies.     

基于Flink的任务调度策略

针对大数据流式计算平台拓扑中因各关键节点上任务间不同类型的通信方式导致的通信开销较大问题,提出一种Flink环境下的任务调度策略。通过各任务间数据流大小确定拓扑边权重,将有向无环图转化为拓扑关键路径模型,在保证关键路径上节点负载差异较小的同时,最小化关键任务的节点间通信开销。实验结果表明,该算法与Flink平台现有的任务调度策略相比,在WordCount和TwitterSentiment作业执行过程中计算平均时延降低了13.09%,有效提升了系统性能。     

Parallel Algorithms for Dynamic Shortest Path Problems

The development of intelligent transportation systems (ITS) and the resulting need for the solution of a variety of dynamic traffic network models and management problems require faster‐than‐real‐time computation of shortest path problems in dynamic networks. Recently, a sequential algorithm was developed to compute shortest paths in discrete time dynamic networks from all nodes and all departure times to one destination node. The algorithm is known as algorithm DOT and has an optimal worst‐case running‐time complexity. This implies that no algorithm with a better worst‐case computational complexity can be discovered. Consequently, in order to derive algorithms to solve all‐to‐one shortest path problems in dynamic networks, one would need to explore avenues other than the design of sequential solution algorithms only. The use of commercially‐available high‐performance computing platforms to develop parallel implementations of sequential algorithms is an example of such avenue. This paper reports on the design, implementation, and computational testing of parallel dynamic shortest path algorithms. We develop two shared‐memory and two message‐passing dynamic shortest path algorithm implementations, which are derived from algorithm DOT using the following parallelization strategies: decomposition by destination and decomposition by transportation network topology. The algorithms are coded using two types of parallel computing environments: a message‐passing environment based on the parallel virtual machine (PVM) library and a multi‐threading environment based on the SUN Microsystems Multi‐Threads (MT) library. We also develop a time‐based parallel version of algorithm DOT for the case of minimum time paths in FIFO networks, and a theoretical parallelization of algorithm DOT on an ‘ideal’ theoretical parallel machine. Performances of the implementations are analyzed and evaluated using large transportation networks, and two types of parallel computing platforms: a distributed network of Unix workstations and a SUN shared‐memory machine containing eight processors. Satisfactory speed‐ups in the running time of sequential algorithms are achieved, in particular for shared‐memory machines. Numerical results indicate that shared‐memory computers constitute the most appropriate type of parallel computing platforms for the computation of dynamic shortest paths for real‐time ITS applications.     

Performance‐based parallel loop self‐scheduling using hybrid OpenMP and MPI programming on multicore SMP clusters

Parallel loop self‐scheduling on parallel and distributed systems has been a critical problem and it is becoming more difficult to deal with in the emerging heterogeneous cluster computing environments. In the past, some self‐scheduling schemes have been proposed as applicable to heterogeneous cluster computing environments. In recent years, multicore computers have been widely included in cluster systems. However, previous researches into parallel loop self‐scheduling did not consider certain aspects of multicore computers; for example, it is more appropriate for shared‐memory multiprocessors to adopt Open Multi‐Processing (OpenMP) for parallel programming. In this paper, we propose a performance‐based approach using hybrid OpenMP and MPI parallel programming, which partition loop iterations according to the performance weighting of multicore nodes in a cluster. Because iterations assigned to one MPI process are processed in parallel by OpenMP threads run by the processor cores in the same computational node, the number of loop iterations allocated to one computational node at each scheduling step depends on the number of processor cores in that node. Experimental results show that the proposed approach performs better than previous schemes. Copyright © 2010 John Wiley & Sons, Ltd.     

面向高维特征和多分类的分布式梯度提升树

梯度提升树算法由于其高准确率和可解释性,被广泛地应用于分类、回归、排序等各类问题.随着数据规模的爆炸式增长,分布式梯度提升树算法成为研究热点.虽然目前已有一系列分布式梯度提升树算法的实现,但是它们在高维特征和多分类任务上性能较差,原因是它们采用的数据并行策略需要传输梯度直方图,而高维特征和多分类情况下梯度直方图的传输成为性能瓶颈.针对这个问题,研究更加适合高维特征和多分类的梯度提升树的并行策略,具有重要的意义和价值.首先比较了数据并行与特征并行策略,从理论上证明特征并行更加适合高维和多分类场景.根据理论分析的结果,提出了一种特征并行的分布式梯度提升树算法FP-GBDT.FP-GBDT设计了一种高效的分布式数据集转置算法,将原本按行切分的数据集转换为按列切分的数据表征;在建立梯度直方图时,FP-GBDT使用一种稀疏感知的方法来加快梯度直方图的建立;在分裂树节点时,FP-GBDT设计了一种比特图压缩的方法来传输数据样本的位置信息,从而减少通信开销.通过详尽的实验,对比了不同并行策略下分布式梯度提升树算法的性能,首先验证了FP-GBDT提出的多种优化方法的有效性;然后比较了FP-GBDT与XGBoost的性能,在多个数据集上验证了FP-GBDT在高维特征和多分类场景下的有效性,取得了最高6倍的性能提升.     

基于温度感知任务调度的3D NoC混合拓扑结构*

3D NoC较高的功率密度容易造成温度过高,对系统性能和芯片可靠性造成负面影响。利用温度感知任务调度来控制节点温度的思路是在运行时把“热”节点上的任务迁移到“冷”节点上,这不可避免会出现迁移之后任务间通信距离变大进而影响整体性能。因此,在任务调度的过程中保持通信开销已经成为迫切需求。提出了分层次的ring/mesh 混合拓扑结构RMH,可以在任务迁移的同时保持原来较小的通信延迟。仿真结果表明,相比于3D NoC拓扑结构,RMH拓扑可以有效缓解散热问题,并且平均减少31.1%的网络延迟。     

异构计算环境下基于优先队列划分的调度算法

人工智能的飞速发展对高性能计算提出了更高的要求,异构计算环境下任务调度问题一直是高性能计算中的关键问题.本文提出一种基于优先队列划分的调度算法(PQDSA),该算法根据DAG(有向无循环图)任务集的入口节点数量确定优先队列数,通过任务的通信开销和计算开销划分任务队列,进而将关键节点任务分配给合适的队列,以产生效果较佳的任务调度队列,从而提高任务间的并行性,降低任务集的完工时间.与此同时,进一步基于插入策略将任务调度到处理器上,使任务调度更加高效地执行.PQDSA算法可以减少任务间的时间消耗,提高处理器的调度效率.通过与两个经典算法的性能对比,实验结果表明本文提出的PQDSA算法在任务完工时间和调度效率方面都要明显优于对比的算法.     

SCHEDULING PARALLEL PROGRAM TASKS WITH NON-NEGLIGIBLE INTERTASK COMMUNICATIONS ON TO NUMA MULTIPROCESSOR SYSTEMS

The purpose of this paper is to examine the impact of scheduling parallel tasks onto non-uniform memory access (NUMA) shared-memory multiprocessor systems by considering non-negligible intertask communications and communication contentions. Communication contentions arise from the communication medium having insufficient capacity to serve all transmissions, thereby causing significant contention delays. Therefore, a new scheduling algorithm, herein referred to as the Extended Critical Path (ECP) algorithm is proposed. The proposed algorithm schedules parallel tasks by considering non-negligible intertask communications and the contentions among shared communication resources. Moreover, it ensures performance within a factor of two of the optimum for general directed acyclic task graphs (DATGs). Experimental results demonstrate the superiority of the ECP algorithm over the scheduling algorithms presented in previous literature.     

Linux高性能计算集群的设计与实现

计算机和网络硬件设备逐步实现商品化和标准化,PC机或工作站的性能越来越高而价格越来越便宜,同时开源Linux微内核及集群工具中间件技术也日趋成熟稳定,高性能计算集群逐渐发展起来,并成为主流的高性能计算平台。高性能计算集群逐渐替代专用、昂贵的超级计算机对大规模并行应用构建原型、调试和运行。基于PCs或工作站的高性能计算快速部署及其可靠性和可管理性研究,对高性能计算集群在科学研究和工程计算等领域的应用,促进高性能计算技术的应用方面具有深远的意义。本文以OSCAR集群为实例,部署一个五结点的集群环境并运行简单的并行测试例子。     

基于共享存储的高可伸缩嵌入式集群模型

利用对称多处理机(SMP)作结点可为嵌入式集群带来更高的计算性价比,但多个并行和存储层次也会带来存储一致性、可伸缩性、性能差异等问题.提出一种基于共享存储的嵌入式集群模型LESC.该模型通过高度综合实现"计算单元-互连一致性模块-系统"三级高可伸缩结构,获得功耗成本有效性.LESC完成分布式共享存储的基本功能,其目录缓存一致性和扩展的共享存储机制改善了传统存储层次,并利用"共享存储虚拟网络"提供模块级的高效通信,避免了网络硬件开销,同时支持MPI编程.经该模型的真实系统平台测试,模块内MPI通信性能是传统嵌入式集群的3倍以上,单元间通信性能可达单元内性能的86%以上,Linpack测试其扩展性能在最差情况下接近理想值的70%.     

Task Scheduling in Distributed Systems Using Heap Intelligent Discrete Particle Swarm Optimization

The optimal mapping of tasks to the processors is one of the challenging issues in heterogeneous computing systems. This article presents a task scheduling problem in distributed systems using discrete particle swarm optimization (DPSO) algorithm with various neighborhood topologies. The DPSO is a recent metaheuristic population‐based algorithm. In DPSO, the set of particles in a swarm flies through the N‐dimensional search space by learning from both the personal best position and a neighborhood best position. Each particle inside the swarm belongs to a specific topology for communicating with neighboring particles in the swarm. The neighborhood topology affects the performance of DPSO significantly, because it determines the rate at which information transmits through the swarm. The proposed DPSO algorithm works on dynamic topology that is binary heap tree for communication between the particles in the swarm. The performance of the proposed topology is compared with other topologies such as star, ring, fully connected, binary tree, and Von Neumann. The three well‐known performance measures such as Makespan, mean flow time, and reliability cost are used for the comparison of the proposed topology with other neighborhood topologies. Computational simulation results indicate that the performance of DPSO algorithm has shown significant improvement with binary heap tree topology used for communication among the particles in the swarm.     

The impact of task service time variability on gang scheduling performance in a two-cluster system

Gang scheduling is a common task scheduling policy for parallel and distributed systems which combines elements of space-sharing and time-sharing. In this paper we present a migration strategy which reduces the fragmentation in the schedule caused by gang scheduled jobs. We consider the existence of high priority jobs in the workload. These jobs need to be started immediately and they may interrupt a parallel job’s execution. A distributed system consisting of two homogeneous clusters is simulated to evaluate the performance for various workloads. We study the impact on performance of the variability in service time of the parallel tasks. Our simulation results indicate that the proposed strategy can result in a significant performance gain and that the performance improvement depends on the variability of gang tasks’ service time.     

Analysis of dynamically scheduled tile algorithms for dense linear algebra on multicore architectures

The objective of this paper is to analyze the dynamic scheduling of dense linear algebra algorithms on shared‐memory, multicore architectures. Current numerical libraries (e.g., linear algebra package) show clear limitations on such emerging systems mainly because of their coarse granularity tasks. Thus, many numerical algorithms need to be redesigned to better fit the architectural design of the multicore platform. The parallel linear algebra for scalable multicore architectures library developed at the University of Tennessee tackles this challenge by using tile algorithms to achieve a finer task granularity. These tile algorithms can then be represented by directed acyclic graphs, where nodes are the tasks and edges are the dependencies between the tasks. The paramount key to achieve high performance is to implement a runtime environment to efficiently schedule the execution of the directed acyclic graph across the multicore platform. This paper studies the impact on the overall performance of some parameters, both at the level of the scheduler (e.g., window size and locality) and the algorithms (e.g., left‐looking and right‐looking variants). We conclude that some commonly accepted rules for dense linear algebra algorithms may need to be revisited. Copyright © 2011 John Wiley & Sons, Ltd.