A transformation approach to derive efficient parallelimplementations

The construction of efficient parallel programs usually requires expert knowledge in the application area and a deep insight into the architecture of a specific parallel machine. Often, the resulting performance is not portable, i.e., a program that is efficient on one machine is not necessarily efficient on another machine with a different architecture. Transformation systems provide a more flexible solution. They start with a specification of the application problem and allow the generation of efficient programs for different parallel machines. The programmer has to give an exact specification of the algorithm expressing the inherent degree of parallelism and is released from the low-level details of the architecture. We propose such a transformation system with an emphasis on the exploitation of the data parallelism combined with a hierarchically organized structure of task parallelism. Starting with a specification of the maximum degree of task and data parallelism, the transformations generate a specification of a parallel program for a specific parallel machine. The transformations are based on a cost model and are applied in a predefined order, fixing the most important design decisions like the scheduling of independent multitask activations, data distributions, pipelining of tasks, and assignment of processors to task activations. We demonstrate the usefulness of the approach with examples from scientific computing     

Evaluating the performance of a SISAL implementation of the abingdon cross image processing benchmark

There are many paradigms being promoted and explored for programming parallel computers, including modified sequential languages, new imperative languages and applicative languages. SISAL is an applicative language which has been designed by a consortium of industrial and research organizations for the specification and execution of parallel programs. It allows programs to be written with little concern for the structure of the underlying machine, thus the programmer is free to explore different ways of expressing the parallelism. A major problem with applicative languages has been their poor efficiency at handling large data structures. To counter this problem SISAL includes some advanced memory management techniques for reducing the amount of data copying that occurs. In this paper we discuss the implementation of some image processing benchmarks in SISAL and C to evaluate the effectiveness of the memory management code. In general, the SISAL program was easier to code than the C (augmented with the PARMACS macros) because we were not concerned with the parallel implementation details. We found that the SISAL performance was in general comparable to C, and that it could be brought in line with an efficient parallel C implementation by some programmer-specified code transformations.     

Very high-level language design: A viewpoint

Recent developments in very high-level language design indicate that these languages hold great promise for improving the level of man-machine communication, and hence improving computer and programmer utilization. (Essentially, a very high-level language one which allows the programmer to specify what to do, rather than how to do it.) This paper surveys these developments, outlines the goals to which an “ideal” very high-level language should aspire, and then presents the design of a very high-level language that would meet these goals. This design is presented in the interest of laying bare some basic design and implementation questions that are inherent to such an achievement. The paper then discusses these questions, indicating both old and new research problems which they suggest.     

Taskmaster: an interactive, graphical environment for task specification, execution and monitoring

Taskmaster is an interactive environment that employs a unique blend of graphic technologies and iconic images to support user task specification. In this environment, problem solving is based on the selection, specification, and composition of tools that correspond to natural sets of ordered operations. The Taskmaster environment is novel in that it

(provides an interactive, visual-based approach to user task specification;

(encourages and supports task specification and refinement processes from both the top-down and bottom-up perspectives; and

(enables one to specify parallel tasks in a natural and convenient manner

To “program” a given task within the Taskmaster environment, one decomposes it into an ordered set of conceptually simple, high-level operations, and then combines (composes) a corresponding network of software tools that implements these operations. Execution of the specified network provides a task solution. Major system components supporting user task specification include a network editor, a tools database and a network execution monitor.     

Higher-level techniques for hardware description and synthesis

The FLaSH (Functional Languages for Synthesising Hardware) system allows a designer to map a high-level functional language, SAFL, and its more expressive extension, SAFL+, into hardware. The system has two phases: first we perform architectural exploration by applying a series of semantics-preserving transformations to SAFL specifications; then the resulting specification is compiled into hardware in a resource-aware manner – that is, we map separate functions to separate hardware functional units (functions which are called multiple times become shared functional units). This article introduces the SAFL language and shows how program transformations on it can explore area-time trade-offs. We then show how the FLaSH compiler compiles SAFL to synchronous hardware and how SAFL transformations can also express hardware/software co-design. As a case study we demonstrate how SAFL transformations allow us to refine a simple specification of a MIPS-style processor into pipelined and superscalar implementations. The superset language SAFL+ (adding process calculi features but retaining many of the design aims) is then described and given semantics both as hardware and as a programming language. Published online: 17 December 2002     

A graphical development and debugging environment for parallel programs

To provide high-level graphical support for PVM (Parallel Virtual Machine) based program development, a complex programming environment (GRADE) is being developed. GRADE currently provides tools to construct, execute, debug, monitor and visualize message-passing parallel programs. It offers a high-level graphical programming abstraction mechanism to construct parallel applications by introducing a new graphical language called GRAPNEL. GRADE also provides the programmer with the same graphical user interface during the program design and debugging stages. A distributed debugging engine (DDBG) assists the user in debugging GRAPNEL programs on distributed memory computer architectures. Tape/PVM and PROVE support the performance monitoring and visualization of parallel programs developed in the GRADE environment.     

Constraint-driven development

To obtain the full benefits of model-driven development (MDD) approaches such as MDA, a suitable level of abstraction needs to be chosen which enables the core functionality and properties of a system to be expressed, independent of programming language or implementation platform, so that this specification can be reused for a wide variety of different environments.This paper describes how constraints, together with UML class diagrams and state machines, can be used as a precise and platform-independent specification language. We describe the use of constraints in UML-RSDS and tool support for the synthesis of executable systems from constraints.     

The BLAZE language: A parallel language for scientific programming

Programming multiprocessor parallel architectures is a complex task. This paper describes a block-structured scientific programming language, BLAZE, designed to simplify this task. BLAZE contains array arithmetic, ‘forall’ loops, and APL-style accumulation operators, which allow natural expression of fine grained parallelism. It also employs an applicative or functional procedure invocation mechanism, which makes it easy for compilers to extract coarse grained parallelism using machine specific program restructuring. Thus BLAZE should allow one to achieve highly parallel execution on multiprocessor architectures, while still providing the user with conceptually sequential control flow.

A central goal in the design of BLAZE is portability across a broad range of parallel architectures. The multiple levels of parallelism present in BLAZE code, in principle, allow a compiler to extract the types of parallelism appropriate for the given architecture, while neglecting the remainder. This paper describes the features of BLAZE, and show how this language would be used in typical scientific programming.     

XDSPCORE: a compiler-based configurable digital signal processor

XDSPCORE is a digital signal processor (DSP) architecture that enables time- and space-efficient execution of typical digital signal applications written in high-level languages. Our evaluation shows that the corresponding compiler can use all the DSP features as efficiently as a programmer coding in assembly language.     

Application-dependent dynamic monitoring of distributed andparallel systems

Achieving high performance for parallel or distributed programs often requires substantial amounts of information about the programs themselves, about the systems on which they are executing, and about specific program runs. The monitoring system that collects, analyzes, and makes application-dependent monitoring information available to the programmer and to the executing program is presented. The system may be used for off-line program analysis, for on-line debugging, and for making on-line, dynamic changes to parallel or distributed programs to enhance their performance. The authors use a high-level, uniform data model for the representation of program information and monitoring data. They show how this model may be used for the specification of program views and attributes for monitoring, and demonstrate how such specifications can be translated into efficient, program-specific monitoring code that uses alternative mechanisms for the distributed analysis and collection to be performed for the specified views. The model's utility has been demonstrated on a wide variety of parallel machines     

The Fork95 parallel programming language: Design, implementation, application

Fork95 is an imperative parallel programming language intended to express algorithms for synchronous shared memory machines (PRAMs). It is based on ANSI C and offers additional constructs to hierarchically divide processor groups into subgroups and manage shared and private address subspaces. Fork95 makes the assembly-level synchronicity of the underlying hardware available to the programmer at the language level. Nevertheless, it supports locally asynchronous computation where desired by the programmer. We present a one pass compiler, fcc, which compiles Fork95 and C programs to the SB-PRAM machine. The SB-PRAM is a lock-step synchronous, massively parallel multiprocessor currently being built at Saarbrücken University, with a physically shared memory and uniform memory access time. We examine three important types of parallel computation frequently used for the parallel solution of real-world problems. While farming and parallel divide-and-conquer are directly supported by Fork95 language constructs, pipelining can be easily expressed using existing language features; an additional language construct for pipelining is not required.     

A note on “schedule of n jobs on two identical machines to minimize weighted mean flor time”

In a recent paper, Alidaee [Computers ind. Engng 24, 53–55 (1993)] notes the similarity between the scheduling problems of minimizing weighted mean flow time (WMFT) on two parallel machines and minimmizing weighted earliness/tardiness (WET) about a common due date on a single machine. Based on this similarity, Alidaee descirbes how a dynamic programming algorithm proposed by Hall and Posner [Opns Res. 39, 836–846 (1991)] for the WET problem can be modified and applied to the WMFT problem. The work is an important extension of earlier results on an equivalence relationship between the WMFT and WET problems. This Note helps consolidate the literature by recognizing Rothkopf [Mgmt Sci. 12, 437–447 (1966)] as the originator of algorithm described in [Computers ind. Engng 24 53–55 (1993)].     

The Design and Implementation of a Domain-Specific Language for Network Performance Testing

CONCEPTUAL is a toolset designed specifically to help measure the performance of high-speed interconnection networks such as those used in workstation clusters and parallel computers. It centers around a high-level domain-specific language, which makes it easy for a programmer to express, measure, and report the performance of complex communication patterns. The primary challenge in implementing a compiler for such a language is that the generated code must be extremely efficient so as not to misattribute overhead costs to the messaging library. At the same time, the language itself must not sacrifice expressiveness for compiler efficiency, or there would be little point in using a high-level language for performance testing. This paper describes the CONCEPTUAL language and the CONCEPTUAL compiler's novel code-generation framework. The language provides primitives for a wide variety of idioms needed for performance testing and emphasizes a readable syntax. The core code-generation technique, based on unrolling CONCEPTUAL programs into sequences of communication events, is simple yet enables the efficient implementation of a variety of high-level constructs. The paper further explains how CONCEPTUAL implements time-bounded loops - even those that comprise blocking communication - in the absence of a time-out mechanism as this is a somewhat unique language/implementation feature.     

Exploring parafunctional programming: separating the what from thehow

A method is presented that takes functional programming one step further by letting the programmer change operational (parafunctional) details without restructuring or rewriting the program. Parafunctional programming is based on the premise that the what (specification) and the how (implementation) are separately identifiable and maintainable system components. Unlike conventional programming methods, parafunctional programming maintains this separation by metalinguistic constructs in the source language and a programming environment that supports structured editing and high-level debugging     

Equational programming in λ-calculus via SL-systems. Part 2

A system of equations in the λ-calculus is a set of formulas of Λ (the equations) together with a finite set of variables of Λ (the unknowns). A system s is said to be β-solvable (βη-solvable) iff there exists a simultaneous substitution with closed λ-terms for the unknowns that makes the equations of s theorems in the theory β (βη). A system s can be viewed as a set of specifications (the equations) for a finite set of programs (the unknowns) whereas a solution for s yields executable codes for such programs.

A class of systems for which the solvability problem is effectively decidable defines an equational programming language and a system solving algorithm for defines a compiler for such language.

This leads us to consider separation-like systems (SL-systems), i.e. systems with equations having form , wherex is an unknown and z is a free variable which is not an unknown.

It is known that the β (βη)-solvability problem for SL-systems is undecidable.

Here we show that there is a class of SL-systems (NP-regular SL-systems) for which the β-solvability problem is NP-complete. Moreover, we show that any SL-system s can be transformed into an NP-regular SL-system s. This transformation consists of adding abstractions to the LHS occurrences of the RHS variables of s. In this sense NP-regular SL-systems isolate the source of undecidability for SL-systems, namely: a shortage of abstractions on the LHS occurrences of the RHS variables.

NP-regular SL-systems yield an equational programming language in which unrestrained self-application is handled, constraints on executable code to be generated by the compiler can be specified by the user and (properties of) data structures can be described in an abstract way. However, existence of executable code satisfying a specification in such language is an NP-complete problem. This is the price we have to pay for allowing unrestrained self-application in our language.     

Scala Actors: Unifying thread-based and event-based programming

There is an impedance mismatch between message-passing concurrency and virtual machines, such as the JVM. VMs usually map their threads to heavyweight OS processes. Without a lightweight process abstraction, users are often forced to write parts of concurrent applications in an event-driven style which obscures control flow, and increases the burden on the programmer.In this paper we show how thread-based and event-based programming can be unified under a single actor abstraction. Using advanced abstraction mechanisms of the Scala programming language, we implement our approach on unmodified JVMs. Our programming model integrates well with the threading model of the underlying VM.     

MUPPET: A programming environment for message-based multiprocessors

MUPPET is a problem-solving environment for scientific computing with message-based multiprocessors. It consists of four part—concurrent languages, programming environments, application environments and man-machine interfaces. The programming paradigm of MUPPET is based on parallel abstract machines and transformations between them. This paradigm allows the development of programs which are portable among multiprocessors with different interconnection topologies.

In this paper we discuss the MUPPET programming paradigm. We give an introduction to the language CONCURRENT MODULA-2 and the graphic specification system GONZO. The graphic specification system tries to introduce graphics as a tool for programming. It is also the basis for programming generation and transformation.     

Specifying and enforcing high-level semantic obligation policies

Obligation policies specify management actions that must be performed when a particular kind of event occurs and certain conditions are satisfied. Large scale distributed systems often produce event streams containing large volumes of low-level events. In many cases, these streams also contain multimedia data (consisting of text, audio or video). Hence, a key challenge is to allow policy writers to specify obligation policies based on high-level events, that may be derived after performing appropriate processing on raw, low-level events. In this paper, we propose a semantic obligation policy specification language called Eagle, which is based on patterns of high-level events, represented as RDF graph patterns. Our policy enforcement architecture uses a compiler that builds a workflow for producing a stream of events, which match the high-level event pattern specified in a policy. This workflow consists of a number of event sources and event processing components, which are described semantically. We present the policy language and enforcement architecture in this paper.     

Interpreters from functions and grammars

The addition of context free grammar rules to a functional language simplifies the construction of interpreters from denotational semantic language definitions. Functional abstraction over grammar rules enables the specification and processing of context sensitive language syntax aspects in a functional style.     

A framework for knowledge-based temporal abstraction

A new domain-independent knowledge-based inference structure is presented, specific to the task of abstracting higher-level concepts from time-stamped data. The framework includes a model of time, parameters, events and contexts. A formal specification of a domain's temporal abstraction knowledge supports acquisition, maintenance, reuse and sharing of that knowledge.

The knowledge-based temporal abstraction method decomposes the temporal abstraction task into five subtasks. These subtasks are solved by five domain-independent temporal abstraction mechanisms. The temporal abstraction mechanisms depend on four domain-specific knowledge types: structural, classification (functional), temporal semantic (logical) and temporal dynamic (probabilistic) knowledge. Domain values for all knowledge types are specified when a temporal abstraction system is developed.

The knowledge-based temporal abstraction method has been implemented in the RÉSUMÉ system and has been evaluated in several clinical domains (protocol-based care, monitoring of children's growth and therapy of diabetes) and in an engineering domain (monitoring of traffic control), with encouraging results.