Livelocks in parallel programs

This paper is the second of a two-part series exploring the subtle correctness criterion of the absence of livelocks in parallel programs. In this paper we are concerned with the issue of proving this correctness criterion. It is shown that livelocks are not preserved by reduction, implying that reduction cannot be used directly in proving the absence of livelocks. Two applicable proof techniques are also presented. One is based on the notion of establishing sufficient conditions for livelock-freedom; the other is an extension of the well-founded set method for proving termination in sequential programs.     

循环算法程序的推导及其应用

算法要求将现实可行的处理事情的方法抽象化,最终用程序设计语言来描述.而不少初学者学习程序设计往往是摸不着头脑.掌握恰当的算法推导方法将有助于学习程序设计.旨在教导学生掌握循环算法推导的一般方法.     

Deriving parallel programs from specifications using cost information

A major step towards practical use of parallel computers is the integration of cost into transformational or derivational software development methods. The difficulties with doing this come from the wide variety of parallel architectures possible and the effects of memory access and congestion phenomena. This paper presents a model of costs for uniform architectures that is compatible with refinement-based methods of development, that is much simpler than those previously suggested, but which accurately assesses the costs of an implemented computation. Decisions about architecture type and machine size can be made at any stage in the development, even at the end.     

An efficient block parallel AMR method for two phase interfacial flow simulations

The direct numerical simulation of two phase interfacial flows can be computationally challenging, as the strong resolution needed to follow the deformations of the interface leads to a lot of time spent solving the whole computation domain. Efficient solution of such problems requires an adaptive mesh refinement capability to concentrate computational effort where it is most needed. In this paper a parallel adaptive algorithm to solve incompressible two-phase flows with surface tension is presented: the AMR is handled with the help of the PARAMESH package. The free interface between fluids is tracked via Level Set approach; the jump conditions at the interface for pressure and velocity are imposed by the Ghost Fluid method. A multigrid preconditioned BiCG-stab solver adapted to the AMR data structure has been developed to allow high density ratio computations (up to 1:1000). Special treatment has been done at the refinement jumps to maintain the fine mesh accuracy. Computational results are compared in different test cases with analytical solutions or literature, and show very good agreement with the references. The effectiveness of PARAMESH parallelization has been quite well maintained, as shown in the strong and weak scaling tests. Speed-up capabilities of the AMR are demonstrated.     

The applicability of program schema results to programs

Several classes of programs, which are the analogues of previously investigated classes of program schemas, are defined. Decidability and translatability questions are considered for these classes of programs, as well as the applicability of these results to the theories of optimization and program testing. The usefulness of the schema model is studied by considering the inheritability of schema properties by programs, and conversely, the inheritability of program properties by schemas.     

A method for pogram analysis and Its applications to program-correctness problems

Described in this paper is a program-analysis method that can be used to effectively determine the logical structure of a program, explicate the computation a program will perform, and show the equivalence of programs. Applications to the problem areas in test-case generation, proving program correctness, and translation of “GOTO” programs into “GOTO-less” programs are discussed.     

Using true concurrency to model execution of parallel programs

Parallel execution of a programR (intuitively regarded as a partial order) is usually modeled by sequentially executing one of the total orders (interleavings) into which it can be embedded. Our work deviates from this serialization principle by usingtrue concurrency to model parallel execution. True concurrency is represented via completions ofR tosemi total orders, called time diagrams. These orders are characterized via a set of conditions (denoted byCt), yielding orders or time diagrams which preserve some degree of the intended parallelism inR. Another way to express semi total orders is to use re-writing or derivation rules (denoted byCx) which for any programR generates a set of semi-total orders. This paper includes a classification of parallel execution into three classes according to three different types ofCt conditions. For each class a suitableCx is found and a proof of equivalence between the set of all time diagrams satisfyingCt and the set of all terminalCx derivations ofR is devised. This equivalence between time diagram conditions and derivation rules is used to define a novel notion of correctness for parallel programs. This notion is demonstrated by showing that a specific asynchronous program enforces synchronous execution, which always halts, showing that true concurrency can be useful in the context of parallel program verification.     

Continuation-based control in the implementation of parallel logic programs

Continuations are used to define the flow of messages between low level tasks in a parallel logic programming language. A combination of compiler and runtime operations reduces message traffic by up to 50% when success continuations are passed as parameters in messages that start new processes. Continuations are also the key to fast task switching, a critical operation in this fine grain parallel system. Data from sample programs shows the effectiveness of continuations in reducing message traffic and the speed with which task switches are performed on a typical host architecture.Supported by NSF Grant CCR-8707177 and grants from Motorola, Inc, and Hewlett-Packard Corp.     

An integrated family of amino acid sequence analysis programs

During the last years abundant sequence data has become available due to the rapid progress in protein and DNA sequencing techniques. The exact three-dimensional structures, however, are available only for a fraction of proteins with known sequences. For many purposes the primary amino acid sequence of a protein can be directly used to predict important structural parameters. However, mathematical presentation of the calculated values often makes interpretation difficult, especially if many proteins must be analysed and compared. Here we introduce a broad-based, user-defined analysis of amino acid sequence information. The program package is based on published algorithms and is designed to access standard protein data bases, calculate hydropathy, surface probability and flexibility values and perform secondary structure predictions. The data output is in an 'easy-to-read' graphic format and several parameters can be superimposed within a single plot in order to simplify data interpretations. Additionally, this package includes a novel algorithm for the prediction of potential antigenic sites. Thus the software package presented here offers a powerful means of analysing an amino acid sequence for the purpose of structure/function studies as well as antigenic site analyses. These algorithms were written to function in context with the UWGCG (University of Wisconsin Genetics Computer Group) program collection, and are now distributed within that package.     

Semantic analysis of program initialisation in genetic programming

Population initialisation in genetic programming is both easy, because random combinations of syntax can be generated straightforwardly, and hard, because these random combinations of syntax do not always produce random and diverse program behaviours. In this paper we perform analyses of behavioural diversity, the size and shape of starting populations, the effects of purely semantic program initialisation and the importance of tree shape in the context of program initialisation. To achieve this, we create four different algorithms, in addition to using the traditional ramped half and half technique, applied to seven genetic programming problems. We present results to show that varying the choice and design of program initialisation can dramatically influence the performance of genetic programming. In particular, program behaviour and evolvable tree shape can have dramatic effects on the performance of genetic programming. The four algorithms we present have different rates of success on different problems.

并行程序开发流程及其辅助工具设计

并行程序开发大多遵循"开发-执行-验证和分析"的流程,开发周期较长,效率低下,而正确性和高性能是使用并行程序的首要条件.为此,提出了一种贯彻算法设计、程序开发到结果分析全过程的、可以同时进行正确性验证和性能分析的开发流程,给出了较完善的计算机辅助开发工具设计的原则和方法,并开发了消息传递并行程序设计的辅助工具原型.实验证明,该流程和方法提高了并行程序开发效率,简化了程序员的工作.     

PProto: An environment for prototyping parallel programs

This paper describes Parallel Proto (PProto), an integrated environment for constructing prototypes of parallel programs. Using functional and performance modeling of dataflow specifications, PProto assists in analysis of high-level software and hardware architectural tradeoffs. Facilities provided by PProto include a visual language and an editor for describing hierarchical dataflow graphs, a resource modeling tool for creating parallel architectures, mechanisms for mapping software components to hardware components, an interactive simulator for prototype interpretation, and a reuse capability. The simulator contains components for instrumenting, animating, debugging, and displaying results of functional and performance models. The Pproto environment is built on top of a substrate for managing user interfaces and database objects to provide consistent views of design objects across system tools.     

Software engineering: An example of misuse

Managers of programmers and designers are sometimes wont to adopt the new and shiny. This paper describes a situation in which managers at several levels grasped for the ‘new and shiny’ in the form of software engineering. This approach was not without its hidden dangers, especially when established guidelines were ignored or violated. The results of an experience with a large software project are reported. This project dealt with a sophisticated inventory control system. The effects on the project of ignorance and the violation of rules are described. Several measures of the final product are reported. Observations of the authors conclude the paper.     

A methodology for designing proof rules for fair parallel programs

We propose a methodology for designing sound and complete proof systems for proving progress properties of parallel programs under various fairness assumptions. Our methodology begins with a branching time temporal logic formula (CTL^*) formula that expresses progress under a fairness assumption. The next step obtains an equivalent fixpoint characterization of this CTL^* formula in the-calculus. The final step uses the fixpoint characterizations to extract proof systems for proving progress under the fairness constraint. The methodology guarantees that the proof rules so obtained are sound and relatively complete in the sense of Cook.     

An efficient tool for genetic experiments: agarose gel image analysis

Repeatability of many genetic analysis experiments can be improved by the application of signal processing and image-processing tools. Most of the experiments in genetics result in some sort of digital signal or image patterns that are subjectively analyzed by the geneticists. This paper presents an example project where image-processing techniques are applied for automation of most of the routine processes of agarose gel image analysis. Result of applying this program has shown that the time taken for the analysis has been reduced by about 70% and the result is reproducible.     

Parallel programming: An axiomatic approach

This paper develops some ideas expounded in [1]. It distinguishes a number of ways of using parallelism, including disjoint processes, competition, cooperation, and communication. In each case an axiomatic proof rule is given.     

An efficient implementation of parallel eigenvalue computation for massively parallel processing

This paper describes an efficient implementation and evaluation of a parallel eigensolver for computing all eigenvalues of dense symmetric matrices. Our eigensolver uses a Householder tridiagonalization method, which has higher parallelism and performance than conventional methods when problem size is relatively small, e.g., the order of 10,000. This is very important for relevant practical applications, where many diagonalizations for such matrices are required so often. The routine was evaluated on the 1024 processors HITACHI SR2201, and giving speedup ratios of about 2–5 times as compared to the ScaLAPACK library on 1024 processors of the HITACHI SR2201.