[ News | IPCA | Mirrors | Add | Search | Mail | Help | WoTUG ]
The CODE system can produce parallel programs for PVM-based networks of machines as well as for the Sequent Symmetry. The newest version (pre-release available) supports the Cray J-series, Sun SMPs, and MPI.
See also <URL:http://www.cs.utexas.edu/users/code/>.
Abstract: CODE 2.0 is a graphical parallel programming system that targets the three goals of ease of use, portability, and production of efficient parallel code. Ease of use is provided by an integrated graphical/textual interface, a powerful dynamic model of parallel computation, and an integrated concept of program component reuse. Portability is approached by the declarative expression of synchronization and communication operators at a high level of abstraction in a manner which cleanly separates overall computation structure from the primitive sequential computations that make up a program. Execution efficiency is approached through a systematic class hierarchy that supports hierarchical translation refinement including special case recognition. This paper reports results obtained through experimental use of a prototype implementation of the CODE 2.0 system. CODE 2.0 represents a major conceptual advance over its predecessor systems (CODE 1.0 and CODE 1.2) in terms of the expressive power of the model of computation which is implemented and in potential for attaining efficiency across a wide spectrum of parallel architectures through the use of class hierarchies as a means of mapping from logical to executable program representations.
Authors: Peter Newton (newton@cs.utexas.edu) and James C. Browne (browne@cs.utexas.edu). Department of Computer Sciences, University of Texas at Austin, Austin, TX 78712, USA.
Abstract: Debugging is a process that involves establishing relationships between several entities: The behavior specified in the program, P, the model/predicate of the expected behavior, M, and the observed execution behavior, E. The thesis of our approach is that a consistent representation for P, M and E greatly simplifies the problem of concurrent debugging, both from the viewpoint of the programmer attempting to debug a program and from the viewpoint of the implementer of debugging facilities. Provision of such a consistent representation becomes possible when sequential behavior is separated from concurrent or parallel structuring. Given this separation, the program becomes a set of sequential actions and relationships among these actions. The debugging process, then, becomes a matter of specifying and determining relations on the set of program actions. The relations are specified in P, modeled in M and observed in E. This simplifies debugging because it allows the programmer to think in terms of the program which he understands. It also simplifies the development of a unified debugging system because all of the different approaches to concurrennt debugging become instances of the establishment of relationships between the actions. We define a formal model of concurrent debugging in which the entire debugging process is specified in terms of program actions. This unified model of concurrent debugging places all of the approaches to debugging of parallel programs such as execution replay, race detection, model/predicate checking, execution history displays and animation, which are commonly formulated as disjoint facilities, in a single, uniform framework. We have also developed a feasibility demonstration prototype of a debugger implementing this unified model of concurrent debugging in the context of the CODE 2.0 parallel programming system. This implementation demonstrates and validates the claims of integration of debugging facilities in a single framework. It is further the case that the unified model of debugging greatly simplifies the construction of a concurrent debugger. All of the capabilities previously regarded as separate for debugging of parallel programs, both in shared memory models of execution and distributed memory models of execution, have been given an implementation in this prototype.
Author: Syed Irfan Hyder
Abstract: Writing parallel programs which are both efficient and portable has been a major barrier to effective utilization of parallel computer architectures. One means of obtaining portable parallel programs is to express the parallelism in a declarative abstract manner. The conventional wisdom is that the difficulty of translation of abstract specifications to executable code leads to loss of efficiency in execution. This thesis demonstrates that programs written in the CODE 2.0 representation where parallel structure is defined in declarative abstract forms can be straightforwardly compiled to give efficient execution on the distributed execution environment defined by the Parallel Virtual Machine (PVM) system. The CODE 2.0 model of programming casts parallel programs as dynamic hierarchical dependence graphs where the nodes are sequential computations and the arcs define the dependencies among the nodes. Both partitioned and shared name spaces are supported. This abstract representation of parallel structure is independent of implementation architecture. The challenge is to compile this abstract parallel structure to an efficient executable program. CODE 2.0 was originally implemented on the Sequent Symmetry shared memory multiprocessor and was shown to give executable code which was competitive with good hand coded programs in this environment. This thesis demonstrates that CODE 2.0 programs can be compiled for efficient execution on a distributed memory execution environment with a modest amount of effort. The environment chosen for this demonstration was PVM. PVM was chosen because it is available on a variety of distributed memory parallel computer architectures. Development of the translator from CODE 2.0 to the PVM execution environment required only a modest amount of effort. Translations to other distributed execution environments can probably be accomplished with a few man-weeks of effort. The efficiency of the executable is demonstrated by comparing the measured execution time of several parallel programs to hand-coded versions of the same algorithms.
Author: Rajeev Mandayam Vokkarne
Abstract: Visual programming has particular appeal for explicit parallel programming, particularly coarse grain MIMD programming. Explicitly parallel programs are multi-dimensional objects; the natural representations of a parallel program are annotated directed graphs: data flow graphs, control flow graphs, etc. where the nodes of the graphs are sequential computations. A visually based `directed graph' representation of parallel programs is thus more natural than a pure text string language where multi-dimensional structures must be implicitly defined. The naturalness of the annotated directed graph representation of parallel programs enables methods for programming and debugging which are qualitatively different and arguably superior to the conventional practice based on pure text string languages. Two visually-oriented parallel programming systems, CODE 2.0 and HeNCE, will be used to illustrate these concepts. The benefits of visually-oriented realizations of these models for program structure capture, performance analysis and debugging will be explored. It is only by actually implementing and using visual parallel programming languages that we have been able to fully evaluate their merits.
Authors: James C. Browne (browne@cs.utexas.edu); Jack Dongarra; Syed I. Hyder; Keith Moor and Peter Newton (newton@cs.utexas.edu).
Abstract: This paper describes a high level language for specifying programming environments for programming languages that are based on directed attributed graphs. The high level language allows the specifier to describe views of portions of a program written in such a graph-based language, the editing operations used to create the program, animations of the execution of the program, and sufficient detail of the execution semantics to support the animations. We demonstrate the use of the specification language with two simple examples of graph-based languages: Petri Nets, and an extension of Petri Nets which includes the ability to nest nets hierarchically. We further describe how to generate the programming environment for graph-based languages from descriptions made in the specification language. This work is the basis for developing a compiler for generating programming environments for graph-based languages automatically. We wish to remedy the add-hoc re-inventing of such systems by providing the high-level domain-specific set of abstractions for specifying them. The specification language is based on using a grammar to describe the components of the graph-based language and using a first-order logic based language to describe state changes in editing, execution, and animation.
Authors: M.F. Kleyn (kleyn@cs.utexas.edu) and J.C. Browne (browne@cs.utexas.edu).
Abstract: This dissertation addresses the problem of creating interactive graphical programming environments for visual programming languages that are based on directed graph models of computation. Such programming environments are essential to using these languages but their complexity makes them difficult and time consuming to construct. The dissertation describes a high level specification language, Glide, for defining integrated graphical/textual programming environments for such languages. It also describes the design of a translation system, Glider , which generates an executable representation from specifications in the Glide language. Glider is a programming environment generator; it automates the task of creating the programming environments used for developing programs in graphbased visual languages. The capabilities supported by the synthesized programming environments include both program capture and animation of executing programs. The significant concepts developed for this work and embodied in the abstractions provided by the Glide language are: an approach to treating programs as structured data in a way that allows an integrated representation of graph and text structure; a means to navigate through the structure to identify program components; a query language to concisely identify collections of components in the structure so that selective views of program components can be specified; a unified means of representing changes to the structure so that editing, execution, and animation semantics associated with the language can all be captured in a uniform way; and a means to associate the graphical capabilities of user interface libraries with displaying components of the language. The data modeling approach embodied in the Glide specification language is a powerful new way of representing graph-based visual languages. The approach extends the traditional restricted mechanisms for specifying composition of text language structure. The extensions allow programming in visual languages to be expressed as a seamless extension of programming in text-based languages. A data model of a graph-based visual language specif ied in Glide forms the basis for specifying the program editing, language execution semantics, and program animation in a concise and abstract way.
Author: Michiel Florian Eugene Kleyn
Abstract: This paper argues the appropriateness of using data types with sharing to characterize the underlying data structures of a large category of graphical programming interfaces - those interfaces which include building programs by interactively manipulating graphical elements in graphs as well as editing characters and words in text. The paper examines the difficulties in providing direct formal representations of the definitions and manipulations of such 'graph' data types that allow sharing of structure. The problem of formalizing the class is shown to be closely related to similar problems that arise in many different areas including the specification of abstract data types, functional programming, and models of object-oriented and network databases. The paper presents the particular approach used in the context of our work on a high-level specification language for describing interactive graphical programming environments and an associated generator.
Author: Michal F. Kleyn (kleyn@cs.utexas.edu), Department of Computer Sciences, The University of Texas at Austin, Austin TX 78712, USA
Abstract: Events are occurrence instances of actions. The thesis of this paper is that the use of "actions", instead of events, greatly simplifies the problem of concurrent debugging. Occurrence instances of actions provide a debugger with a unique identifier for each event. These identifiers help the debugger in recording the event orderings. The recorded orderings indicate much more than a mere temporal order. They indicate the dependences that "cause" the actions to execute. A debugger can, then, collect the dependence information from the orderings of different instances of the same action, and deduce the conditions that govern the execution of the action. This provides a framework for representing and checking the expected behavior. Unlike existing approaches, we cover all parts of the debugging cycle. Our unified model, therefore, allows a single debugger to support different debugging facilities like execution replay, race detection, assertion/model checking, execution history displays, and animation.
Authors: S.I. Hyder; J.F. Werth and J.C. Browne. University of Texas at Austin, Austin, Texas, USA.
Abstract: This dissertation addresses the problem of facilitating the development of efficiently executing programs for multiple-instruction multi-datastream (MIMD) parallel computers. The family of MIMD parallel computer architectures is the most flexible and most widely applicable means of meeting requirements for very high performance computation. It is widely accepted, however, that current methods of preparing programs for these systems are inadequate and are the primary bottleneck for attainment of these machines' potential.
It is difficult to write programs which are both correct and efficient even for a single MIMD parallel architecture. A program which is efficient in execution on one member of this architecture class is often either not portable at all to different members of the architecture class, or if portability is possible, the efficiency attained is usually not satisfactory on any architecture.
The conceptual basis of the approach we have taken to providing a solution for the problem of programming MIMD parallel architectures is based upon raising the level of abstraction at which parallel program structures are expressed and moving to a compositional approach to programming. The CODE 2.0 model of parallel programming permits parallel programs to be created by composing basic units of computation and defining relationships among them. It expresses the communication and synchronization relationships of units of computation as abstract dependencies. Runtime determined communications structures can be expressed.
Ready access to these abstractions is provided by a flexible graphical interface in which the user can specify them in terms of extended directed graphs. Both ease of preparation of correct programs and compilation to efficient execution on multiple target architectures is enabled. The compositional approach to programming focuses the programmer's attention upon the structure of the program, rather than development of small unit transformations. In the CODE 2.0 system, the units of computation are prepared using conventional sequential programming languages along with declaratively specified conditions under which the unit is enabled for execution.
The system is built upon a unique object-oriented model of compilation in which communication and synchronization mechanisms are implemented by parameterized class templates which are used to custom tailor the translation of abstract specifications in communication and synchronization to efficient local models.
The attainment of the goals of the research is measured in the following ways. There have been several uses of the CODE 2.0 system by casual users in parallel programming classes. The results are uniformly positive; the programs which are developed are simple and easy to read, and execute at least as efficiently as programs written in conventional parallel languages. Experimental measurement of the execution behavior of benchmark programs has shown that the executable code generated by CODE 2.0 is efficient, often within 5% or less, and sometimes more efficient than hand-generated parallel programs. Portability with retention of efficiency of execution has been demonstrated by implementations on two different execution environments; an implementation on the synchronous message paradigm given by Ada and in the shared-memory environment of the Sequent Dynix operating system.
Author: Peter Newton (newton@cs.utexas.edu)
Abstract: Visual programming arguably provides greater benefit in explicit parallel programming, particularly coarse grain MIMD programming, than in sequential programming. Explicitly parallel programs are multi-dimensional objects; the natural representations of a parallel program are annotated directed graphs: data flow graphs, control flow graphs, etc. where the nodes of the graphs are sequential computations. The execution of parallel programs is a directed graph of instances of sequential computations. A visually based `directed graph' representation of parallel programs is thus more natural than a pure text string language where multi-dimensional structures must be implicitly defined. The naturalness of the annotated directed graph representation of parallel programs enables methods for programming and debugging which are qualitatively dif ferent and arguably superior to the conventional practice based on pure text string languages. Annotation of the graphs is a critical element of a practical visual programming system; text is still the best way to represent many aspects of programs. This paper presents a model of parallel programming and a model of execution for parallel programs which are the conceptual framework for a complete visual programming environment including capture of parallel structure, compilation and behavior analysis `performance and debugging'. Two visually-oriented parallel programming systems, CODE 2.0 and HeNCE, each based on a variant of the model of programming, will be used to illustrate the concepts. The benefits of visually-oriented realizations of these models for program structure capture, software component reuse, performance analysis and debugging will be explored and hopefully demonstrated by examples in these representations. It is only by actually implementing and using visual parallel programming languages that we have been able to fully evaluate their merits.
Authors: James C. Browne; Jack Dongarra; Syed I. Hyder; Keith Moore and Peter Newton.
Abstract: Visual programming languages have a number of advantages for parallel computing. They integrate well with programming environments and graphical program behavior visualization tools, and they present programmers with useful abstractions that aid them in understanding the large-scale structure of their programs. Such understanding is important for achieving good execution performance of parallel programs. Furthermore, graphical programming languages can be easier for non-specialists to use than other explicitly parallel languages since they relieve the programmer of the need to directly use low-level primitives such as message sends or locks. This paper discusses some of these general advantages and presents simple examples in the existing visual parallel programming languages, HeNCE and CODE 2.0.
Author: Peter Newton