PGMT Documentation Synopsis

This table provides a very high overview of the files associated with the PGM Software. These files, in the form of PDF documents, give information to the user to make it possible for that user to install PGMT, understand the purpose of PGMT, understand how to use the PGMT, and understand some of the design principles that were used in writing PGMT. The date given in the " Name, Author(s), Date" column indicate the last modification made to that document. These documents have a genesis in projects that began in 1987 but can be more directly traced to documents that were drafted in 1995.

File Name Name, Author(s), Date


Intro_to_PGM.pdf An Introduction to the Processing Graph Method
D. J. Kaplan

March 24, 1997

The Processing Graph Method (PGM) technology is a paradigm that provides the engineer/system designer with an environment to specify and maintain applications in a form which is invariant over a wide range of MIMD message passing parallel architectures.

We will give the reader the flavor of this approach by providing a description of an application; illustrating how that application is represented; showing typical results obtained by running the application; providing a short description of the atoms that are used to build the application; and providing a short discussion of the technical issues to which PGM must respond.


Processing Graph Method 2.1 Semantics
David J. Kaplan & Richard S. Stevens

July 29, 2002

The purpose of this document is to specify the Processing Graph Method (PGM). We will tell you what problem PGM is supposed to help solve. Then we will tell you what PGM is.

Specifying PGM is a complicated proposition because PGM has many related parts. We will tell you in a general way, what the parts are, how they fit together, and how certain assembled parts (processing graphs) of PGM operate. Then we will describe how command program procedures are used to help build and control graphs. Finally we list and describe the functionality of the command program procedures.


Implementation of Families in the Processing Graph Method Tool
Dick Stevens

August 29, 2002

One fundamental concept that we use extensively in PGMT is the family, which we use in place of the more common array or vector. A family may be thought of as a multidimensional array with 0 or more dimensions. The number of dimensions is called the height. Intuitively, we may think of a family as a rooted tree. A tree with height 0 comprises a single leaf. A tree wi th height 1 comprises a one- dimensional array of leaves (i. e., height 0 families), each leaf having a single index t o identify it. A family with height 2 comprises an array of height 1 families. In general, a family with height n comprises an array of height n- 1 families. In every family at every level, the indexing has a specified lower bound. If one were to take a given family and remove the leaves, then what remains is the family tree. For a complete discussion of the family concept, see the PGM Spec [1].

Graph_Construction.pdf Graph_ Construction Graph Construction In the Processing Graph Method Tool
Dick Stevens

September 9, 2002

We assume the reader is familiar with the PGM Spec [1 ], the GUI user manual [2], and Implementation of Families [3]. In this document we describe the various structures and procedures used in PGMT for constructing a processing graph. Our approach is to construct and maintain t wo levels of the processing graph.
PGMT_Users_Manual.pdf Processing Graph Method Tool (PGMT) Userís Manual
Wendell L. Anderson

October 31, 2002

This report describes the process required for a user to write and run a data flow program using the Processing Graph Method Tool (PGMT). It assumes that the user is familiar with UNIX commands and directory structures, has access to a PGMT installation built by the procedures specified in the PGMT Installation Instructions. A basic understanding of data flow concepts is assumed and the user should read the PGM2 specification before reading this manual or writing data flow programs. The PGM specification is available in these documents as "Processing Graph Method 2.1 Semantics".


Processing Graph Method Tool (PGMT) Installation Manual

Wendell L. Anderson

October 31, 2002

This report describes the steps necessary to install the Processing Graph Method Tool (PGMT) onto a system of computers operating in a UNIX/LINUX environment. PGMT is an implementation of the PGM specification that includes the software necessary to run a data flow graph on a collection of processors. The tool contains a Graphical User Interface for inputting and saving graphs and then translating them into C++ code, libraries to support the linking and run-time execution of the graph , debugging aids, and a tool for generating the code necessary to transfer user-defined data type between computers using MP.


Processing Graph Method - GUI Handbook
Michal Iglewski

June 26, 2002

This document describes the Graphic User Interface (GUI) of the Processing Graph Method Tool (PGMT). In the following, we refer to the human using the GUI as the user, and a GUI session refers to the editing of a GUI graph. While the user is editing the GUI graph, the internal data structures in the GUI memory are called the parse tree. The user may elect to save the GUI graph in a file, called the Graph State File, or GSF. After saving the GUI graph in a GSF, the user may start a new GUI session and open the previously saved GSF. The state of the parse tree and the information presented to the user are identical to what they were when the GUI graph was saved.


Design Notes for GUI Forms
Dick Stevens

Thursday, July 18, 2002

Included in this document are descriptions of the menus and the various forms associated with the icons. Not included in this draft is a description of the icons and how they may be laid out and connected. We will discuss the following:

  • The menus, the items in each menu, and the function of each menu item.
  • The information to be presented to the operator in each form.
  • The syntax rules of each field in each form, and how the GUI shall enforce the syntax rules.
  • The semantics rules of the fields in the forms, and how the GUI shall enforce the semantics rules.
  • The mapping between fields in the forms and the syntax elements of the Graph State File (GSF) as defined in the Graph State File Specification, by Kalpana Bharadwaj, January 27, 2000.
  • The dynamics of clear, cut, copy, and paste in the forms.


The Graph State File Specification
Kalpana Bharadwaj
Revised by Dick Stevens

January 27, 2000,
May 26, 2001

A GSF is an ASCII file which describes the layout, and associated data values, of graph objects that comprise a PGM2 application. This description is sufficient to store and retrieve a complete graph across different invocations of the graph editor application. This document is a formal specification of the GSF language.


Translator Output Specification
Dick Stevens

January 25, 2002

This document describes the C++ code to be generated by the translator (Petor). The specification defines a set of functions that prescribe how the C++ code is to be generated.. Arguments of functions will be in terms of the EBNF specification of the Graph State File (GSF), dated August 17, 1999, together with calls to other functions.

Documentation_of_the_GCL.pdf Documentation of the Graph Class Library (GCL)
Richard S. Stevens

November 3, 2001

In this document we attempt to capture the overall design and structure of the GCL, so that others may understand the code and improve on it. We wrote this document after the GCL code was written and tested. There was no formal design document or collection of design documents for the entire GCL. Instead, there were individual design documents for some parts of the GCL. Other parts were designed "on the fly" after discussions with others on the PGMT team


Handbook for Authors of Transition Statements
Dick Stevens

July 28, 2002

The purpose of this handbook is to describe for the PGMT (Processing Graph Method Tool) GUI (Graph User Interface) operator how to write a transition statement.



Distributed Processing in PGMT
Richard S. Stevens

Tuesday, August 13, 2002

At the Naval Research Laboratory (NRL) we designed and implemented a system to support the execution of dataflow graphs on a network of processors. We use a scheme of automatic static assignment of nodes to processors. During execution, the system monitors performance. If necessary, a different static assignment is chosen to improve performance. Reassignment occurs "on the fly" while execution continues with little interruption. The continual monitoring of performance and reassignment continues until an assignment with acceptable performance is achieved. In this paper we describe how we accomplish the change from one static reassignment to another with little interruption of execution.


Scheduling in PGMT
Joseph Collins
Ali Boroujerdi
Richard S. Stevens

September 29, 2002

April 8, 2002

In PGMT, the execution of a Processing Graph involves interaction between the code of the Graph Class Library (GCL) and the PGM Execution Program (PEP). Graph execution in the GCL is described in the paper about distributed processing [2]. Also discussed there is the interaction between the GCL and PEP, as seen from the GCL point of view. We assume the reader has read that paper and is familiar with the ideas presented there. I t would also be helpful to have read the paper on Graph construction.


Tuning a Timer
Rudolph A. Krutar

March 31, 1998

The purpose of this note is to explain some fine points regarding performance measurement, especially the timing of computer software. As with any tool, understanding what the tool does and what it does not do is important to practical use of the tool. Therefore it is necessary to understand in detail what a timing function really does.


An Approach to Scheduling Task Graphs with Contention in Communication
Joseph B. Collins

June 4, 2001

Algorithms that schedule task graphs for execution on parallel processors frequently use simplifying assumptions about the behavior and performance of networks that pass data between tasks. When there is a high communications- to- computations ratio for a parallel application some of these assumptions may fail. The result is that the network may become a bottleneck in executing the application and the scheduling algorithm may not be sufficiently valid to be useful. We examine this problem for scheduling real- time applications and draw some conclusions on how to do scheduling for general parallel processing.


C++2MPI/PGMT Integration
Roger Hillson

Revised 23 July 2002

PGMT includes a library of Middleware. The Middleware library includes message-passing functions which can be called by functions in the Graph Class Library (GCL) or PEP (PGMT Execution Program). All of the Middleware communication functions use calls to MPI 1.1. (Message Passing Interface 1.1) function libraries to send and receive data. The MPI function calls are hidden from the GCL and PEP function calls. In order to call an MPI function to send or receive data, the MPI datatype for the data must be specified. (Note: in accordance with the MPI 1.1. specification, "datatype" is spelled as a single word.) To specify the MPI datatype of the data being sent or received, it is necessary to pass an MPI handle as an argument to the MPI function being called. An MPI handle is an opaque object of type MPI_Datatype. In order to use MPI to pass instances of PGM families i.e. PGM tokens containing families, there must be an MPI handle corresponding to the base-type of the PGM family.


PGMT Middleware Documentation
Dr. Roger Hillson

October 6, 2002

The following model summarizes the PEP-Middleware functional interactions for performance tracking.

  • As part of Machine:: Initialize(), the MW will measure the ratio of the processor speeds, using a mix of floating point division and multiplications.

  • The PEP can update timings for transition executions, keyed by GCL_ NodeID and and MW_ ProcessID. The ordered pair (MW_ ProcessID, GCL_ NodeID) will be referred to as a relative key. This history will be maintained by the Middleware. The MW will estimate the mean and variance of the timing for each transition. The mean and variance will be updated recursively. The series (recursion) for estimating the mean and variance will also be restarted if there is a significant change in the mean value.

  • Saving the results: When the timing data (mean value and standard deviation) is saved to a file, it will be keyed by processor HostName and the five- string GCL_ StringID object. The ordered pair ( HostName, GCL_ StringID) will be referred t o as the absolute key, where the HostName is a string set t o the name of the processor (e. g. " spruance"). Multiple transitions within the same family, but with different relative keys, can map onto the same absolute key if they are on the same processor. If there is a many- to- one mapping of timings onto an absolute key, the average values of the mean timing and standard deviation will be saved.

In summary: to save the records in the relative database: - translate the relative keys into absolute keys - average the data over records with different relative keys but the same absolute keys - save the absolute keys and data as file records


A Software Tool for Automatically Generating MPI Datatypes from C++ Classes
Dr. Roger Hillson
Naval Research Laboratory
Dr. Michal Iglewski
University of Quebec at Hull

The Message Passing Interface 1.1 (MPI 1.1) standard defines a library of message- passing functions for parallel and distributed computing. We have developed a new software tool called C++ 2MPI which can automatically generate MPI derived datatypes for a specified C++ class. C++ 2MPI can generate data types for derived classes, for partially and fully- specialized templated classes, and for classes with private data members. Given one or more user- provided classes as input, C++ 2MPI generates, compiles and archives a function for creating the MPI derived datatype.


Interfacing the Command Program to a PGM Graph
Christopher Scannell

June 18, 2002

This document describes information for the Processing Graph Method (PGM) Command Program writer to use in interfacing his software with a PGM Graph. It will discuss calls that need to be made to create graphs, start and stop them, write to and read from them via a Graph Port, save and restore assignments of PGM Transitions to processes, and enable and disable dynamic reassignment of PGM Transitions to processes by the PGM Execution Program (PEP). Where relevant, it will discuss the specific APIís of the PEP and the Graph Class Library (GCL) needed by the Command Program writer. Examples will be given from the PGM demonstration application (GramGraph) and from a simpler application, Sort.


GramGraph Graphical User Interface
Christopher Scannell

March 12, 2002

This document is intended to provide an overview of the GramGraph Graphical User Interface (GUI) with emphasis on the relationship between the GUI and the GramGraph application Command Program process with which it communicates. It will talk about how the GUI is started, how it communicates bi-directionally with a separate process that is under the control of the Command Program, how it is stopped and the handshaking between processes involved with starting and stopping the graph from the GUI that is used to avoid race conditions.

Date Last Modified:
By: M.Iglewski