Concurrent programming in VISO

Concurrent programming is more difficult to use and understand than sequential programming. In order to simplify this type of programming a number of approaches have been developed such as visual programming. Visual Occam (VISO) is a visual programming language for concurrent programming. It has a graphical syntax based on the language Occam and its semantics is represented both in petri net and process calculus. This paper presents a modular visual approach to write concurrent programs using the VISO language. Concurrent programs in VISO are specified graphically at different levels of abstraction. This paper describes this modular visual approach by constructing two examples in VISO. The first example is a simple concurrent program and it is mainly used to show the details of constructing a concurrent program in VISO. The second example is a larger concurrent program with more levels of abstraction. Copyright © 2000 John Wiley & Sons, Ltd.     

A Structured Synchronization and Communication Model Fitting Irregular Data Accesses

In this paper, we present a parallel programming and execution model based on alogicalordering of control flows. We show that it is possible to provide a unifying framework consisting of a synchronous programming model, thereby facilitating the mastery of programs, and an asynchronous execution model yielding efficient executions. Our approach is based on a SPMD and task parallel programming language, called –Chan. Communications take place through channels and rely on explicit send/receive instructions. In contrast to classical message passing models, synchronizations and communications are dissociated. We show that it is possible to perform a data-driven automatic translation of sequential and arbitrary DOACROSS loops into –Chan, by using nonmatching send/receive instructions. Our parallelization technique allows us to handle irregular control and leads to optimizations of communications in irregular computations.     

Distributed dynamic programming using concurrent object-orientedness with actors visualized by high-level Petri nets

This paper deals with application of concurrent object-oriented programming with Actors to solve dynamic programming problems in a distributed computing environment. This area of research is often called distributed artificial intelligence. Using a dynamic programming example of chained matrix multiplication, a method of managing dynamic programming searches in a distributed programming environment with Actors is presented. Distributed computations with Actors are visualized by means of Time-Varying Automata (for cases with no intra-actor concurrency) or using a class of high-level nets called Hierarchical Colored Petri Nets (for cases with intra-actor concurrency). Design and implementation features of the specific Actor-based programming environment, using a concurrent extension of C++, are also discussed.     

ParC—An Extension of C for Shared Memory Parallel Processing

ParC is an extension of the C programming language with block-oriented parallel constructs that allow the programmer to express fine-grain parallelism in a shared-memory model. It is suitable for the expression of parallel shared-memory algorithms, and also conducive for the parallelization of sequential C programs. In addition, performance enhancing transformations can be applied within the language, without resorting to low-level programming. The language includes closed constructs to create parallelism, as well as instructions to cause the termination of parallel activities and to enforce synchronization. The parallel constructs are used to define the scope of shared variables, and also to delimit the sets of activities that are influenced by termination or synchronization instructions. The semantics of parallelism are discussed, especially relating to the discrepancy between the limited number of physical processors and the potentially much larger number of parallel activities in a program.     

Asynchronous communication model based on linear logic

We propose a new framework called ACL for concurrent computation based on linear logic. ACL is a kind oflinear logic programming framework, where its operational semantics is described in terms ofproof construction in linear logic. We also give a model-theoretic semantics based onphase semantics, a model of linear logic. Our framework well captures concurrent computation based on asynchronous communication. It will, therefore, provide us with a new insight into other models of asynchronous concurrent computation from alogical point of view. We also expect ACL to become a formal framework for analysis, synthesis and transformation of concurrent programs by the use of techniques for traditional logic programming. ACL's attractive features for concurrent programming paradigms are also discussed.     

A definition of and linguistic support for partial quiescence

The global quiescence (GQ) of a distributed computation (or distributed termination detection) is an important problem. Some concurrent programming languages and systems provide GQ detection as a built‐in feature so that programmers do not need to write special synchronization code to detect quiescence. This paper introduces partial quiescence (PQ), which generalizes quiescence detection to a specified part of a distributed computation. PQ is useful, for example, when two independent concurrent computations that both rely on GQ need to be combined into a single program. The paper describes how we have designed and implemented a PQ mechanism within an experimental version of the JR concurrent programming language, and have gained experience with several representative applications. Our early results are promising qualitatively and quantitatively. Copyright © 2007 John Wiley & Sons, Ltd.     

Pascal-plus—another language for modular multiprogramming

This paper informally describes the programming language Pascal-Plus. The language is an extended version of Pascal, incorporating the envelope construct which is an aid to program modularization and data abstraction, the process, monitor and condition constructs which provide a means for representing multiprocessing programs, and a simulation monitor which provides pseudo-time control facilities for multiprocessing programs.     

OpenGR: A directive-based grid programming environment

A new grid programming environment for remote procedure call (RPC) based master–worker type task parallelization is presented. The environment is realized through the use of a set of compiler directives, called OpenGR, and is implemented in the present study based on the Omni OpenMP compiler system and Ninf-G grid-enabled RPC system as a parallel execution mechanism. Using OpenGR directives, existing sequential applications can be readily adapted to the grid environment as master–worker parallel programs using the RPC architecture. The combination of OpenGR and OpenMP directives also allows for the hybrid parallelization of sequential programs, supporting both synchronous and asynchronous parallelism.     

A timed semantics of Orc

Orc is a kernel language for structured concurrent programming. Orc provides three powerful combinators that define the structure of a concurrent computation. These combinators support sequential and concurrent execution, and concurrent execution with blocking and termination.Orc is particularly well-suited for task orchestration, a form of concurrent programming with applications in workflow, business process management, and web service orchestration. Orc provides constructs to orchestrate the concurrent invocation of services while managing time-outs, priorities, and failures of services or communication.Our previous work on the semantics of Orc focused on its asynchronous behavior. The inclusion of time or the effect of delay on a computation had not been modeled. In this paper, we define an operational semantics of Orc that allows reasoning about delays, which are introduced explicitly by time-based constructs or implicitly by network delays. We develop a number of identities among Orc expressions and define an equality relation that is a congruence. We also present a denotational semantics in which the meaning of an Orc program is a set of traces, and show that the two semantics are equivalent.     

CONSAT: A parallel constraint satisfaction system

In this paper we describe the parallelization of a medium-size symbolic fixed-point computation, CONSAT. CONSAT is a constraint satisfaction system that computes globally consistent solutions. The parallel version of CONSAT is implemented using abstractions from a parallel programming toolbox we developed. The toolbox is intended for novice parallel programmers, and programs based on abstractions from this toolbox may be executed on both uniprocessors and shared-memory multiprocessors without modifications. We explain how parallelism is introduced, and how concurrent accesses to shared data structures are handled. We will also describe the performance of CONSAT on sample inputs.     

Parallelizing genetic linkage analysis: a case study for applying parallel computation in molecular biology

Parallel computers offer a solution to improve the lengthy computation time of many conventional, sequential programs used in molecular biology. On a parallel computer, different pieces of the computation are performed simultaneously on different processors. LINKMAP is a sequential program widely used by scientists to perform genetic linkage analysis. We have converted LINKMAP to run on a parallel computer, using the machine-independent parallel programming language, Linda. Using the parallelization of LINKMAP as a case study, the paper outlines an approach to converting existing highly iterative programs to a parallel form. The paper describes the steps involved in converting the sequential program to a parallel program. It presents performance benchmarks comparing the sequential version of LINKMAP with the parallel version running on different parallel machines. The paper also discusses alternative approaches to the problem of "load balancing," making sure the computational load is shared as evenly as possible among the available processors.     

Parallel algorithm design for workstation clusters

Clusters of workstations connected by local area networks are in common use in many organizations. The combined processing power of these clusters is rarely exploited owing to the lack of suitable parallel algorithms. The paper describes a parallel programming paradigm called supervisor-worker, suitable for the workstation environment, which can be used to speed up the execution of a large class of existing sequential programs. Simple formulae are developed to predict the speed-up of a parallel algorithm developed in this way. The predictions depend on two easily-determined parameters of the sequential program and the characteristic communication cost of the workstation cluster. Consequently, it is possible to estimate the benefits of the parallel program before proceeding with detailed implementation. As an example, the parallel version of a travelling salesman program is developed and the measured speed-up compared with the predicted speed-up.     

User accessible reply capabilities in invoking and servicing operations

Many message passing languages and packages include some form of synchronous invocation. In a synchronous invocation, the invoker waits for the invocation's servicer to pass back results. A synchronous invocation can be viewed as a pair of asynchronous invocations: one—initiating the computation—with parameter values from the invoker to the servicer and the other—once the requested computation has completed—with the ‘go‐ahead’ and return value from the servicer to the invoker. The target of the latter invocation is known as the reply operation, and a reference to it is known as a reply capability. This paper addresses the issues of making such reply capabilities directly accessible to user code. It presents the design and prototype implementation of a new version of the JR concurrent programming language, called xJR, in which the reply capability can be explicit. This paper gives xJR examples, including realistic ones, to highlight the additional flexibility the new features offer (such as a non‐lexical reply). These additional features do not impact the run‐time performance of existing JR features and can even lead to more efficient code in some programming scenarios. Our experience with the prototype implementation indicates that an actual implementation would be fruitful and would preserve the prototype's performance advantages. Copyright © 2015 John Wiley & Sons, Ltd.     

Generic programming techniques for parallelizing and extending procedural finite element programs

We outline an approach for extending procedural finite-element software components using generic programming. A layer of generic software components consisting of C++ containers and algorithms is used for parallelization of the finite-element solver and for solver coupling in multi-physics applications. The advantages of generic programming in connection with finite-element codes are discussed and compared with those of object-oriented programming. The use of the proposed generic programming techniques is demonstrated in a tutorial fashion through basic illustrative examples as well as code excerpts from a large-scale finite-element program for serial and parallel computing platforms.

A novel compiler support for automatic parallelization on multicore systems

The widespread use of multicore processors is not a consequence of significant advances in parallel programming. In contrast, multicore processors arise due to the complexity of building power-efficient, high-clock-rate, single-core chips. Automatic parallelization of sequential applications is the ideal solution for making parallel programming as easy as writing programs for sequential computers. However, automatic parallelization remains a grand challenge due to its need for complex program analysis and the existence of unknowns during compilation. This paper proposes a new method for converting a sequential application into a parallel counterpart that can be executed on current multicore processors. It hinges on an intermediate representation based on the concept of domain-independent kernel (e.g., assignment, reduction, recurrence). Such kernel-centric view hides the complexity of the implementation details, enabling the construction of the parallel version even when the source code of the sequential application contains different syntactic variations of the computations (e.g., pointers, arrays, complex control flows). Experiments that evaluate the effectiveness and performance of our approach with respect to state-of-the-art compilers are also presented. The benchmark suite consists of synthetic codes that represent common domain-independent kernels, dense/sparse linear algebra and image processing routines, and full-scale applications from SPEC CPU2000.     

Beyond multi-adjoint logic programming

In ‘multi-adjoint logic programming’, MALP in brief, each fuzzy logic program is associated with its own ‘multi-adjoint lattice’ for modelling truth degrees beyond the simpler case of true and false, where a large set of fuzzy connectives can be defined. On this wide repertoire, it is crucial to connect each implication symbol with a proper conjunction thus conforming constructs of the form (←_i, &_i) called ‘adjoint pairs’, whose use directly affects both declarative and operational semantics of the MALP framework. In this work, we firstly show how the strong dependence of adjoint pairs can be largely weakened for an interesting ‘sub-class’ of MALP programs. Then, we reason in a similar way till conceiving a ‘super-class’ of fuzzy logic programs beyond MALP, which definitively drops out the need for using adjoint pairs, since the new semantics behaviour relies on much more relaxed lattices than multi-adjoint ones.     

InParS: an experimental intelligent parallelization system

In this paper we discuss the design and implementation of an intelligent program parallelization system, called InParS. This system in based on intelligent parallelization models proposed by many researchers in the area of parallelizing compilers. The presented experiment is one of few attempts toward investigating the viability of artificial intelligence techniques in automatic program parallelization. The early version of InParS was aimed at transforming Fortran-like DO loops into a vector code well-suited for vector processors. The new version of InParS targets distributed memory parallel computers. Some preliminary research results are also presented, which give an indication of how incorporating artificial intelligence techniques can contribute towards the success of automatic program parallelization.     

Visual programming support for graph‐oriented parallel/distributed processing

GOP is a graph‐oriented programming model which aims at providing high‐level abstractions for configuring and programming cooperative parallel processes. With GOP, the programmer can configure the logical structure of a parallel/distributed program by constructing a logical graph to represent the communication and synchronization between the local programs in a distributed processing environment. This paper describes a visual programming environment, called VisualGOP, for the design, coding, and execution of GOP programs. VisualGOP applies visual techniques to provide the programmer with automated and intelligent assistance throughout the program design and construction process. It provides a graphical interface with support for interactive graph drawing and editing, visual programming functions and automation facilities for program mapping and execution. VisualGOP is a generic programming environment independent of programming languages and platforms. GOP programs constructed under VisualGOP can run in heterogeneous parallel/distributed systems. Copyright © 2005 John Wiley & Sons, Ltd.     

On the Contribution of Backward Jumps to Instruction Sequence Expressiveness

We investigate the expressiveness of backward jumps in a frame work of formalized sequential programming called program algebra and characterize established non-uniform complexity classes in terms of instruction sequences, backward jumps and auxiliary registers.     

Contracts for concurrency

The SCOOP model extends the Eiffel programming language to provide support for concurrent programming. The model is based on the principles of Design by Contract. The semantics of contracts used in the original proposal (SCOOP_97) is not suitable for concurrent programming because it restricts parallelism and complicates reasoning about program correctness. This article outlines a new contract semantics which applies equally well in concurrent and sequential contexts and permits a flexible use of contracts for specifying the mutual rights and obligations of clients and suppliers while preserving the potential for parallelism. We argue that it is indeed a generalisation of the traditional correctness semantics. We also propose a proof technique for concurrent programs which supports proofs—similar to those for traditional non-concurrent programs—of partial correctness and loop termination in the presence of asynchrony. P. J. Brooke, R. F. Paige and Dong Jin Song