Figure 1. Processing Graph Method Time Line
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.
This work was partially supported by the Office of Naval Research Computer Science Program.
The Processing Graph Method uses an iconic description to cut parallel-processor software costs and schedule. Because processing graphs are independent of parallel computer architectures. The intention is to eliminate the need to rewrite programs when upgrading from one parallel computer hardware architecture to another. Because a processing graph is iconic, closely resembling a block diagram, scientists and engineers quickly learn the technique and are able to produce good programs.
The Processing Graph Method is a technology to facilitate the architecture independent programming of MIMD systems with a small to large number of processing elements. The PGM approach is intended for general system building, including signal processing. PGM has emphasized the signal processing domain because implementing signal processing systems depends on successfully programming multiple processing element systems. The systems supported by this technology are meant to encompass differing heterogeneous processing elements that are connected in a fashion ranging from low to high communication bandwidths and from small to large time latencies. The initial funding and implementation of PGM has been through acoustic signal processing systems.
PGM now supports C4I's front end process, signal processing. The next step for PGM in C4I is to support the building of a high-tech moving picture version of a plot board. To apply PGM to that problem we must identify and implement the fusion-center multisensor correlation primitives that will support the building of such a plot board.
The Processing Graph Method Tool (PGMT) is a high performance computing software development environment. This environment helps translate an engineer's design of a weapon system into software for the weapon system's computers and this approach is specifically applicable to massively parallel distributed-computer processing.
For the application software developer, PGMT will provide:
"http://www.ait.nrl.navy.mil/pgmt/pgm2.html" is the PGMT homepage.
Background
Fig. 1 depicts PGM's maturation over twenty years.
Figure 1. Processing Graph Method Time Line
PGM includes three components:
Industry involvement with PGM includes CNA who suggested that PGM become a software standard for embedded processors; Dynetics, Inc who marketed a subset of PGM as DataFLO; Lockheed Martin through RASSP; Lockheed Martin through GE; IBM Manassas and LORAL Rolm acquisitions; MCCI which was founded to develop PGM technology; and JRS Laboratories who uses PGM technology with ARPA/AF/ARMY/RASSP.
NRL is identified by computer manufacturers as the center for this technology and PGM 2.0 is being standardized by IEEE.
Fig. 2 indicates the process flow of PGM ideas.
Figure 2. Process flow of PGM process
The PGMT Project Schedule time-table is:
Since this is an np-complete scheduling problem, heuristics will be used to obtain a suboptimal solution.
The PGMT project's exit criterion is to obtain results consistent with 80% of what a skilled human programming team could produce.
This is often referred to as narrow-band processing with beamforming and is a widely use basic process in acoustic surveillance systems. The processing graph accepts user selections for various process parameters including frequency resolution, frequency range and beam direction.
The application, gramGraph, proceeds as follows:
Fig. 3 is gramGraph.
Figure 3. gramGraph
Fig. 3 is a flat structure, it has no hierarchical structure. In fact PGM is capable of expressing a hierarchical structure. To see how this is done we first construct Fig. 4
Figure 4. gramGraph (segmented)
We now abstract the hierarchical structure contained in Fig. 4 and produce the tree shown in Fig.5.
Figure 5. gramGraph tree
Figure 6. Member of spectrum family
In order to use gramGraph we produced an operator interface illustrated in Fig. 7.
Figure 7 gramGraph Operator Interface
Figure 8. Demonstration LOFAR Gram
A processing graph is constructed by calling an instantiation procedure (IP). An IP calls a graph procedure to include a node (place or transition) in a graph; initialize (place or transition input port); connect a pair of ports. An IP calls another IP to construct an included graph. Command Program may call IPs. Among graph procedures are start and suspend graph; unlink a linked pair of ports; delete a node or included graph; save a suspended graph and subsequently reload it; read tokens from a graph output place port; and write tokens to a graph input place port.
Figure 9. Processing Graph Icon Taxonomy
On the left edge of Fig. 9 are the icons that represent the listed nodes. We will indicate the pairing as we discuss each icon.
Any iconic part of a processing graph application may occur in familys.
A family is special kind of structure that resembles a list limited to
some basetype. The parts that may constitute familys are places,
transitions, included graphs, and graph ports. Directed arcs are not really
objects and don't make up familys.
However, two familys of ports may be connected pairwise. Familys are indicated by icons with dropped shadows as indicated.
Directed arcs and ports. A directed arc connects two ports. Ports have
three attributes, two of which have binary valued attributes. These attributes
are direction which has the value "output" or "input"; and category which has
the value "transition" or "place". The third attribute is mode; mode is the
type of the token that goes through the port. For an arc to connect two ports,
the ports must be of opposite direction, opposite category and same mode. An
arc is represented by an arrow from output port to input port. Tokens pass
from output port to input port.
Places. There are two kinds of places, queues and graph variables.
Places capture state.
Queues store a family of tokens first-in-first-out. Each queue has an attribute called capacity which is the maximum content of its associated token family. There is at most one transition port connected to each queue port.
Graph variables store a single token. The value of the old token is destroyed
when a new token is supplied. The value read is the most recent token. Any
number of transition ports can be connected to each port.
Transitions. There are ordinary transitions and special transitions. There are several kinds of special transitions. Transitions capture function.
The most frequently encountered transitions are ordinary transitions.
Ordinary transition ports are simple. There are no familys of ports and
one token is read and consumed at each input port followed by an associated
transition statement being executed. Please note that embedded within the
transition statement may be any number of primitive functions. After the
transition statement is executed, one token is produced at each output port.
The remaining transitions are classified as special.
The first special transition we will consider is the pack transition. The pack transition has an input port named INPUT which may be of any mode.
The Pack transition has four other input ports:
The Unpack transition has an output port named OUTPUT that may be of any mode.
It has another output port named PRODUCE of mode int. Unpack has a single
input port named INPUT whose mode is "family of OUTPUT mode". Unpack
accepts a token which constitutes a family. It unpacks that tokens and
sends the resultant tokens to OUTPUT. It places on PRODUCE the number of
tokens that were in the input token. Please note that the content of the input
tokens may be zero.
A Fanin transition has as input a single family of input ports; these
ports may be of any mode and that mode is common to all members of the
family. The transition has one output port whose mode is
"family of mode of input port ". Execution may take place when each
member of the input family has at least one token and the capacity of
the output place is at least one greater than its content. One token is read
and consumed from each input port. One token is produced at the output port.
That token is a family constructed from the read tokens and indexed in
the same order as the index of the family of input ports.
The Fanout transition has as output a single family of output ports
which may be of any mode and that mode is common to all members of the
family. The transition has one input port whose mode is "family
of mode of output port ".
Execution may take place when the input port has available to it at least one token and the capacity of each output place is at least one greater than its content. One token is read and consumed from the input port. One token is produced to each member of the output family of ports. Those tokens are obtained by disassembling the input token into its individual subtokens. The indices of the subtokens are the same as the indices of family of output ports.
An Uncontrolled Merge has a family of INPUT ports which may be of any
mode. It has one OUTPUT port of the same mode as the family of INPUT
ports. To execute, there must exist at least one INPUT token on some INPUT
port, and there must be space for one OUTPUT token on the output. Execution
consists of one INPUT token being read and consumed and one token produced to
OUTPUT of the same value as the INPUT token.
Graph exterior. A Graph exterior is an icon which serves as the
interface to the world exterior to the processing graph. Its semantics are
that it consists of the graph ports of the processing graph, where each graph
port has the attributes of Mode, Direction (with the possible values of
"input" or "output") and Category (with the possible values of "Transition",
"Place").
Included graph. An Included graph is an icon which represents the
interface between an embedded graph and the processing graph which supports it.
Its semantics are that it consists of the graph ports of the embedded graph.
For every Included graph there is a corresponding Graph exterior. The
processing graph which has that Graph exterior is called the support graph of
the Included graph. For every port in an Included graph, its direction is
opposite the direction of that port in the corresponding Graph exterior. For
every port in an Included graph, its mode is opposite the direction of that
port in its Support graph. For every port in an Included graph, its category is
opposite the direction of that port in the Support graph. For every port in an
Included graph, its mode is the same as that port in the Support graph.
Graph tree. In the example shown earlier, the topmost graph was the root of a tree and is referred to as the main graph. In our example the Main graph had three included graphs and a family of included graphs. One of the Main graph's included graphs had two included graphs. Two of included graphs had the same support graph.
We gave 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 responds.
[2] Erner, K.A. and Gorline, J.L., The Processing Graph Method Tool C++ Reference Manual, U.S. Naval Research Laboratory, 1996.
[3] Erner, K.A. and Gorline, J.L. The Processing Graph Method Tool C++ Programming Tutorial Version 2.0, U.S. Naval Research Laboratory, 1996.
[4] Gilbert Christopher Sih, Multiprocessor Scheduling to account for interprocessor communication, University of California, Berkeley, Memorandum No. UCB/ERL M91/29, 22 April 1991.
[5] Richard M. Karp & Raymond E. Miller, Properties of a Model for Parallel Computations: Determinacy, Termination, Queuing, SIAM J. Appl. Math. v14, pp 1390-1410, 1966.
[6] J. Aylor, R. Klenke, and R. Hillson and D. J Kaplan, VHDL-Based Performance Modeling for the Processing Graph Method Tools (PGMT), Proceedings of the VHDL International Users Forum (VIUF Spring 1996), Feb 28 - March 2, Santa Clara, CA.