Automatic partitioning of parallel loops and data arrays fordistributed shared-memory multiprocessors

Presents a theoretical framework for automatically partitioning parallel loops to minimize cache coherency traffic on shared-memory multiprocessors. While several previous papers have looked at hyperplane partitioning of iteration spaces to reduce communication traffic, the problem of deriving the optimal tiling parameters for minimal communication in loops with general affine index expressions has remained open. Our paper solves this open problem by presenting a method for deriving an optimal hyperparallelepiped tiling of iteration spaces for minimal communication in multiprocessors with caches. We show that the same theoretical framework can also be used to determine optimal tiling parameters for both data and loop partitioning in distributed memory multicomputers. Our framework uses matrices to represent iteration and data space mappings and the notion of uniformly intersecting references to capture temporal locality in array references. We introduce the notion of data footprints to estimate the communication traffic between processors and use linear algebraic methods and lattice theory to compute precisely the size of data footprints. We have implemented this framework in a compiler for Alewife, a distributed shared-memory multiprocessor     

Compile-time partitioning of iterative parallel loops to reducecache coherency traffic

Adaptive data partitioning (ADP) which reduces the execution time of parallel programs by reducing interprocessor communication for iterative parallel loops is discussed. It is shown that ADP can be integrated into a communication-reducing back end for existing parallelizing compilers or as part of a machine-specific partitioner for parallel programs. A multiprocessor model to analyze program execution factors that lead to interprocessor communication and a model for the iterative parallel loop to quantify communication patterns within a program are defined. A vector notation is chosen to quantify communication across a global data set. Communication parameters are computed by examining the indexes of array accesses and are adjusted to reflect the underlying system architecture by compensating for cache line sizes. These values are used to generate rectangular and hexagonal partitions that reduce interprocessor communication     

基于复杂连续系统并行仿真的自动任务划分

有效地进行任务划分、控制并行粒度,才能充分利用并行计算机的资源,通过对复杂连续系统仿真程序特点的分析,提出了以状态方程为核心、以右函数段的计算为主要对象的自动任务划分算法,使用结果表明具有很好的并行效果。     

Automatic detection of sluggish control loops

This paper describes a procedure for the automatic detection of sluggish control loops obtained from conservatively tuned controllers. A measure, the Idle index, of the sluggishness of the control loop is defined. The Idle index describes the relation between times of positive and negative correlation between the control and measurement signal increments. It can be determined with a very small amount of process knowledge, and is suitable for both on-line and off-line applications.     

Automatic partitioning of full-motion video

Partitioning a video source into meaningful segments is an important step for video indexing. We present a comprehensive study of a partitioning system that detects segment boundaries. The system is based on a set of difference metrics and it measures the content changes between video frames. A twin-comparison approach has been developed to solve the problem of detecting transitions implemented by special effects. To eliminate the false interpretation of camera movements as transitions, a motion analysis algorithm is applied to determine whether an actual transition has occurred. A technique for determining the threshold for a difference metric and a multi-pass approach to improve the computation speed and accuracy have also been developed.     

Semi-automatic process partitioning for parallel computation

Automatic process partitioning is the operation of automatically rewriting an algorithm as a collection of tasks, each operating primarily on its own portion of the data, to carry out the computation in parallel. Hybrid shared memory systems provide a hierarchy of globally accessible memories. To achieve high performance on such machines one must carefully distribute the work and the data so as to keep the workload balanced while optimizing the access to nonlocal data. In this paper we consider a semi-automatic approach to process partitioning in which the compiler, guided by advice from the user, automatically transforms programs into such an interacting set of tasks. This approach is illustrated with a picture processing example written in BLAZE, which is transformed by the compiler into a task system maximizing locality of memory reference.Research supported by an IBM Graduate Fellowship.Research supported under NASA Contract No. 520-1398-0356.Research supported by NASA Contract No. NAS1-18107 while the last two authors were in residence at ICASE, NASA, Langley Research Center.     

Compiling global name-space parallel loops for distributedexecution

Compiler support required to allow programmers to express their algorithms using a global name-space is discussed. A general method for the analysis of a high-level source program and its translation into a set of independently executing tasks that communicate using messages is presented. It is shown that if the compiler has enough information, the translation can be carried out at compile time; otherwise; run-time code is generated to implement the required data movement. The analysis required in both situations is described, and the performance of the generated code on the Intel iPSC/2 hypercube is presented     

Data partitioning for parallel solid modelling

Solid modelling involves processing large amounts of geometric data. Distributed processing is a promising technique for improving the speed of computationally intensive processes. Solid modelling is thus a good candidate for parallel processing. We present a method for distributing entities of solid models in an array of processors for intersection tests in evaluating boolean operations. We employ distributed boundary representation and a recursive spatial subdivision technique for data partitioning. Parallel algorithms distribute entities among the array of processors mapped to a set of 3D rectangular regions in the object space. Entities intersecting or residing in the intersection regions of the objects are distributed. An experimental system was implemented on a DECmpp 12000/Sx/8K distributed memory SIMD computer.     

Adaptively scheduling parallel loops in distributed shared-memorysystems

Using runtime information of load distributions and processor affinity, the authors propose an adaptive scheduling algorithm and its variations from different control mechanisms. The proposed algorithm applies different degrees of aggressiveness to adjust loop scheduling granularities, aiming at improving the execution performance of parallel loops by making scheduling decisions that match the real workload distributions at runtime. They experimentally compared the performance of the algorithm and its variations with several existing scheduling algorithms on two parallel machines: the KSR-1 and the Convex Exemplar. The kernel application programs used for performance evaluation were carefully selected for different classes of parallel loops. The results show that using runtime information to adaptively adjust scheduling granularity is an effective way to handle loops with a wide range of load distributions when no prior knowledge of the execution can be used. The overhead caused by collecting runtime information is insignificant in comparison with the performance improvement. The experiments show that the adaptive algorithm and its five variations outperformed the existing scheduling algorithms     

On the parallel execution time of tiled loops

Many computationally-intensive programs, such as those for differential equations, spatial interpolation, and dynamic programming, spend a large portion of their execution time in multiply-nested loops that have a regular stencil of data dependences. Tiling is a well-known compiler optimization that improves performance on such loops, particularly for computers with a multilevel hierarchy of parallelism and memory. Most previous work on tiling is limited in at least one of the following ways: they only handle nested loops of depth two, orthogonal tiling, or rectangular tiles. In our work, we tile loop nests of arbitrary depth using polyhedral tiles. We derive a prediction formula for the execution time of such tiled loops, which can be used by a compiler to automatically determine the tiling parameters that minimizes the execution time. We also explain the notion of rise, a measure of the relationship between the shape of the tiles and the shape of the iteration space generated by the loop nest. The rise is a powerful tool in predicting the execution time of a tiled loop. It allows us to reason about how the tiling affects the length of the longest path of dependent tiles, which is a measure of the execution time of a tiling. We use a model of the tiled iteration space that allows us to determine the length of the longest path of dependent tiles using linear programming. Using the rise, we derive a simple formula for the length of the longest path of dependent tiles in rectilinear iteration spaces, a subclass of the convex iteration spaces, and show how to choose the optimal tile shape.     

面向SoC的系统级并行划分方法

为缩短复杂SoC系统的设计周期,降低系统设计的复杂性,提出了一种SoC系统级的并行划分方法.引入带有信号激活率和输入输出延时的过程模型图,为SoC系统构建模型.设计一启发式算法对该过程模型图进行并行划分,同时,该算法能解决有环图的划分问题.通过大量的实验证明,划分结果同要求吻合,说明该划分方法是可行、有效的.     

Supervised pattern recognition by parallel feature partitioning

In the present paper the supervised pattern recognition problem is considered. For solving the problem a mathematical model based on parallel feature partitioning is proposed. The solution is obtained by partitioning the feature space to a minimal number of nonintersecting regions. This is achieved by solving an integer-valued optimization problem, which leads to the construction of minimal covering. Since the classes do not intersect it follows that the solution of the formulated problem exists. Computational complexity of the model and computational procedures are discussed. Geometrical interpretation of the solution is given.     

Problem partitioning in parallel processor simulation systems

Problem partitioning to solve ordinary differential equations on a parallel processor system using classical numerical integration methods involves defining and ordering computation tasks and scheduling the tasks for execution, In defining tasks there is a tradeoff between decomposing a computation into a large number of primitive tasks to expose all potential parallelism and decomposing it into a smaller number of tasks to simplify scheduling. Scheduling is an intractable problem; heuristic scheduling algorithms reduce the effort required to schedule tasks but cannot guarantee that the parallel solution will execute in minimum time. An example illustrates difficulties encountered in scheduling tasks for parallel computation and use of a dependency graph as a tool in problem partitioning. The need for an efficient mechanism for asynchronous data exchanges among processors is demonstrated.     

Automatic on-line estimation of backlash in control loops

This paper describes a new method for detection and estimation of backlash in control loops. The detection procedure is based on normal operating data. It is not assumed that the output from the backlash is measured. The procedure is automatic in the sense that no information has to be provided from the user to run the procedure. Since an estimate of the dead band caused by the backlash is provided by the procedure, the procedure gives all information needed to compensate for the backlash.     

Automatic transformation of iterative loops into recursive methods

ContextIn software engineering, taking a good election between recursion and iteration is essential because their efficiency and maintenance are different. In fact, developers often need to transform iteration into recursion (e.g., in debugging, to decompose the call graph into iterations); thus, it is quite surprising that there does not exist a public transformation from loops to recursion that can be used in industrial projects (i.e., it is automatic, it handles all kinds of loops, it considers exceptions, etc.).ObjectiveThis article describes an industrial algorithm implemented as a Java library able to automatically transform iterative loops into equivalent recursive methods. The transformation is described for the programming language Java, but it is general enough as to be adapted to many other languages that allow iteration and recursion.MethodWe describe the changes needed to transform loops of types while/do/for/foreach into recursion. We provide a transformation schema for each kind of loop.ResultsOur algorithm is the first public transformation that can be used in industrial projects and faces the whole Java language (i.e., it is fully automatic, it handles all kinds of loops, it considers exceptions, it treats the control statements break and continue, it handles loop labels, it is able to transform any number of nested loops, etc.). This is particularly interesting because some of these features are missing in all previous work, probably, due to the complexity that their mixture introduce in the transformation.ConclusionDevelopers should use a methodology when transforming code, specifically when transforming loops into recursion. This article provides guidelines and algorithms that allow them to face different problems such as exception handling. The implementation has been made publicly available as open source.     

基于并行图计算的社区划分方法

以图计算形式研究社交网络由来已久,但对于如何提升图计算应用于大规模社交网络的计算速度和扩展性,一直是研究的难点。谱图论的应用为社交网络在图计算方面的研究带来新的研究热点,谱图分割为社交网络社区划分带来基于结构的支撑。为了解决谱图论在处理大规模社交网络时存在计算缓慢、内存溢出等问题,本文提出了谱聚类改进算法结合矩阵方式在并行环境下的处理方法。首先,利用Spark对网络数据进行并行化预处理,将社交网络以图结构表示,再将图转化为Spark分布式稀疏矩阵。然后,将谱聚类改进算法在Spark环境下,实现并行化社交网络社区快速划分,并以分布式方式持久化存储源数据、中间计算数据和计算结果,提高图计算在社交网络中的可靠性。最后,通过实验证明并行化图计算方法能有效提高计算速度和扩展性,支持大规模社交网络的挖掘分析,实现并行算法下高并发、高吞吐的特点。     

面向并行负载平衡的数据剖分技术*

对传统的数据剖分技术和负载平衡对大规模并行计算性能的影响进行了综述,介绍了目前典型的几何剖分方法和图剖分方法的特点,并分析比较各种剖分算法及常用剖分软件包(ParMETIS、Zoltan、JOSTLE等)在实际应用中的优缺点,深入探讨了数据剖分技术是如何对超大规模数值模拟计算任务进行高效划分以解决负载平衡问题的,以期为开展并行计算研究和并行性能优化的研究人员提供参考。