Distribution Category(cid:0)
`Mathematics and
`Computer Science (cid:1)UC(cid:2)(cid:6)
`
`ARGONNE NATIONAL LABORATORY
`  South Cass Avenue
`Argonne(cid:9) IL 
`
`(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)
`ANL(cid:2) (cid:5) 
`Revision 
`(cid:0)(cid:0)(cid:0)(cid:0)(cid:0)(cid:1)
`
`Parallel Programming with PCN
`
`by
`
`Ian T(cid:0) Foster and Steven Tuecke
`
`Mathematics and Computer Science Division
`
`January
`
`This research was supported in part by the National Science Foundation under Contract
`NSF CCR(cid:0)  (cid:7) by the O(cid:8)ce of Scienti(cid:9)c Computing(cid:7) U(cid:10)S(cid:10) Department of Energy under
`
`Contract W(cid:0) (cid:0) (cid:0)Eng(cid:0) (cid:7) by the Air Force O(cid:8)ce for Scienti(cid:9)c Research under Contract
`AFOSR(cid:0) (cid:0)(cid:7) by the O(cid:8)ce for Naval Research under Contract ONR(cid:0)N (cid:0) (cid:0)J(cid:0)  (cid:7)
`
`and by the Defense Advanced Research Projects Agency under Contract DARPA(cid:0)N (cid:0)
` (cid:0)K(cid:0)(cid:10)
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 1
`
`

`

`Preface
`
`The PCN system is the product of the e(cid:13)orts of many people at Argonne Na(cid:2)
`tional Laboratory(cid:9) the California Institute of Technology(cid:9) and the Aerospace Corpo(cid:2)
`ration(cid:9) including Sharon Brunett(cid:9) Mani Chandy(cid:9) Ian Foster(cid:9) Steve Hammond(cid:9) Carl
`Kesselman(cid:9) Tal Lancaster(cid:9) Dong Lin(cid:9) Jan Lindhiem(cid:9) Robert Olson(cid:9) Steve Taylor(cid:9)
`and Steven Tuecke(cid:14) The Upshot trace analysis tool was provided by Ewing Lusk(cid:14)
`The expanded BNF syntax for PCN was provided by John Thornley(cid:14) The two(cid:2)point
`boundary value application was provided by Steve Wright(cid:14)
`
`ii
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 2
`
`

`

`Contents
`
`I A Tutorial Introduction
`
` Program Composition
` (cid:14) Core Programming Notation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Toolkit (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Cross Reference (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Getting Started
`
` An Example Program
` (cid:14) Compiling a Program (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Linking a Program (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Running a Program (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) The main(cid:1)(cid:6) Procedure (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` The PCN Language
`(cid:14) Concurrent Programming Concepts (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) PCN Syntax (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Sequential Composition and Mutable Variables (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Parallel Composition and De(cid:17)nitional Variables (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Choice Composition (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) De(cid:17)nitional Variables as Communication Channels (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Specifying Repetitive Actions (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Tuples (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Stream Communication (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Advanced Stream Handling (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Interfacing Parallel and Sequential Code (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14)  Review (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Programming Examples
`(cid:14) List and Tree Manipulation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Quicksort (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Two(cid:2)Point Boundary Value Problem (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Modules
`
` The C Preprocessor
`
` Integrating Foreign Code
`(cid:14) PCN(cid:18)Foreign Interface (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Compiling with Foreign Code (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Linking with Foreign Code (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:14) Multilingual Programming (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`iii
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
` 
`
`
`
`
`
`
` 
`
` 
` 
`
`
`
`
`
`
`
`
`
`
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 3
`
`

`

`(cid:14) De(cid:17)ciency of Foreign Interface
`
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`
`
` Higher(cid:9)Order Programs Using Metacalls
`
` Process Mapping
`
` Port Arrays
`
`  Reuse of Parallel Code
`
` Using Multiple Processors
`
`  Debugging PCN Programs
` (cid:14) Syntax Errors (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Logical Errors (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Performance Errors (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`II Reference Material
`
`  PDB(cid:11) A Symbolic Debugger for PCN
` (cid:14) The PCN to Core PCN Transformation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Obtaining Transformed Code (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Naming Processes
` (cid:14) Using the Debugger
`(cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Examining the State of a Computation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Breakpoints (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Debugger Variables (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Miscellaneous Commands (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Dynamic Loading of (cid:0)pam Files (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Orphan Processes (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`  The Gauge Execution Pro(cid:12)ler
` (cid:14) Linking a Program for Pro(cid:17)ling (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Pro(cid:17)le Data Collection (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Snapshot Pro(cid:17)les (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Data Exploration (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) The Host Database (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) X Resources (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`  The Upshot Trace Analyzer
` (cid:14) Instrumenting a Program (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Compiling and Linking the Instrumented Program (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Collecting a Log (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Analyzing a Log (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
`  Standard Libraries
`
`iv
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 4
`
`

`

` (cid:14) System Utilities (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Standard I(cid:18)O (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14)(cid:14) Reference (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14)(cid:14) Examples (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Cross(cid:9)Compiling
`
` Intel iPSC(cid:13) Speci(cid:12)cs
`
` Intel Touchstone DELTA Speci(cid:12)cs
`
` Sequent Symmetry Speci(cid:12)cs
`
` Network Speci(cid:12)cs
` (cid:14) Using rsh (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Specifying Nodes on the Command Line (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Using a PCN Startup File (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Starting net(cid:2)PCN without rsh (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Ending a Computation (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
` (cid:14) Limitations of net(cid:2)PCN (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0) (cid:0)
`
` Further Reading
`
`III Advanced Topics
`
` pcncomp and the PCN linker
`
` Make(cid:12)le
`
` Run(cid:9)Time System Debugging Options
`
`IV Appendices
`
`A Obtaining the PCN Software
`
`B Supported Machines
`
`C Reserved Words
`
`D Deprecated and Incompatible Features
`
`E Common Questions
`
`F PCN Syntax
`
`v
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
`
` 
`
`
`
`
` 
`
` 
`
` 
`
` 
`
` 
`
`
`
`
`
` 
`
`
`
` 
`
` 
`
` 
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 5
`
`

`

`Part I
`A Tutorial Introduction
`
` Program Composition
`
`Program Composition Notation (cid:1)PCN(cid:6) is both a programming language and a par(cid:2)
`allel programming system(cid:14) As the name suggests(cid:9) both the language and the pro(cid:2)
`gramming system center on the notion of program composition(cid:14)
`Most programming languages emphasize techniques used to develop individual
`components (cid:1)blocks(cid:9) procedures(cid:9) modules(cid:6)(cid:14) In PCN(cid:9) the focus of attention is the
`techniques used to put components together (cid:1)i(cid:14)e(cid:14)(cid:9) to compose them(cid:6)(cid:14) This is illus(cid:2)
`trated in the following (cid:17)gure(cid:9) which shows a combining form being used to compose
`three programs(cid:14)
`
`This focus on combining forms is important for several reasons(cid:14) First(cid:9) it encour(cid:2)
`ages reuse of parallel code(cid:0) a single combining form can be used to develop many
`di(cid:13)erent parallel programs(cid:14) Second(cid:9) it facilitates reuse of sequential code(cid:0) parallel
`programs can be developed by composing existing modules written in languages such
`as Fortran and C(cid:14) Third(cid:9) it simpli(cid:17)es development(cid:9) debugging(cid:9) and optimization(cid:9) by
`exposing the basic structure of parallel programs(cid:14)
`It appears likely that a large proportion of all parallel programs can be devel(cid:2)
`oped with a relatively small number of combining forms(cid:14) However(cid:9) PCN does not
`attempt to enumerate potential combining forms(cid:14) Instead(cid:9) it provides a core set of
`three primitive composition operators (cid:19) parallel(cid:9) sequential(cid:9) and choice composi(cid:2)
`tion (cid:19) in a core programming notation(cid:14) This is a simple(cid:9) high(cid:2)level programming
`language(cid:14) More sophisticated combining forms (cid:1)providing(cid:9) for example(cid:9) divide(cid:2)and(cid:2)
`conquer(cid:9) self(cid:2)scheduling(cid:9) or domain decomposition strategies(cid:6) can be implemented
`as user(cid:2)de(cid:17)ned extensions to this core notation(cid:14) Such extensions are referred to as
`templates or user(cid:0)de(cid:1)ned composition operators(cid:14) Program development(cid:9) both with
`the core notation and with templates(cid:9) is supported by aportable toolkit(cid:14) These three
`components of the PCN system are illustrated in Figure (cid:14)
`This tutorial provides a detailed description of the core programming notation
`and toolkit(cid:9) and an introduction to the use of templates in parallel programming(cid:14)
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 6
`
`

`

`Application−specific
`composition operators
`
`Core Programming Notation
`
`Portable Toolkit
`
`Figure (cid:0) PCN System Structure
`
` (cid:10) Core Programming Notation
`
`The core PCN programming notation is a simple(cid:9) high(cid:2)level language that pro(cid:2)
`vides three basic composition operators(cid:0) parallel(cid:9) sequential(cid:9) and choice(cid:14)
`The
`language provides two types of variable(cid:0) conventional(cid:9) or mutable variables(cid:9) and
`single(cid:2)assignment(cid:9) or de(cid:1)nitional variables(cid:14) Other distinctive features of the lan(cid:2)
`guage include extensive use of recursion(cid:9) support for both numeric and symbolic
`computing(cid:9) and an interface to sequential languages such as Fortran and C(cid:14) The
`syntax is similar to that of C(cid:14)
`
` (cid:10) Toolkit
`
`The PCN toolkit provides support for each stage of the parallel program develop(cid:2)
`ment process(cid:14) It comprises a compiler(cid:9) linker(cid:9) foreign language interface(cid:9) standard
`libraries(cid:9) process mapping tools(cid:9) programmable transformation system(cid:9) symbolic
`debugger(cid:9) execution pro(cid:17)ler(cid:9) and trace analyzer(cid:14) These facilities are all machine
`independent and can run on a wide variety of uniprocessors(cid:9) multiprocessors(cid:9) and
`multicomputers(cid:14) They are supported by a run(cid:0)time system that provides basic
`machine(cid:2)dependent facilities(cid:14)
`
`Compiler The compiler translates PCN programs to a machine(cid:2)independent(cid:9) low(cid:2)
`level form (cid:1)PCN object code(cid:6)(cid:14) An interface to the C preprocessor allows macros(cid:9)
`conditional compilation constructs(cid:9) and the like to be used in PCN programs(cid:14)
`
`Linker and Foreign Language Interface The PCN linker combines PCN ob(cid:2)
`ject code (cid:1)i(cid:14)e(cid:14)(cid:9) PCN compiler output(cid:6)(cid:9) foreign object code that is called from PCN
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 7
`
`

`

`(cid:1)i(cid:14)e(cid:14)(cid:9) C or Fortran compiler output(cid:6)(cid:9) libraries(cid:9) and the PCN run(cid:2)time system into
`a single executable program(cid:14) This permits C and Fortran procedures to be inte(cid:2)
`grated seamlessly into PCN programs(cid:9) and PCN programs to be executed similar to
`programs written in other languages(cid:14)
`
`Standard libraries A set of standard libraries provides access to Unix facilities
`(cid:1)e(cid:14)g(cid:14)(cid:9) I(cid:18)O(cid:6) and other capabilities(cid:14)
`
`Virtual Topology tools These support process mapping on a variety of virtual
`machines(cid:9) and templates for writing reusable parallel code(cid:14)
`
`PDB PDB is the PCN symbolic debugger(cid:14)
`debugging of concurrent programs(cid:14)
`
`It includes specialized support for
`
`Gauge Gauge is an execution pro(cid:17)ler for programs written in PCN and other
`languages(cid:14) It includes run(cid:2)time system support for collecting and saving pro(cid:17)les(cid:9)
`and an X windows based graphical tool for interactive exploration of pro(cid:17)le data(cid:14)
`
`Upshot Upshot is a trace analysis tool for programs written in PCN and other
`languages(cid:14) It includes run(cid:2)time system support for collecting and saving traces(cid:9) and
`an X windows based graphical tool for interactive exploration of trace data(cid:14)
`
` (cid:10) Cross Reference
`
`The basic constructs of the PCN language are described in the following sections(cid:14)
`
`(cid:0) Syntax(cid:0) x (cid:14) and Appendix F(cid:14)
`
`(cid:0) Sequential composition(cid:0) x (cid:14) (cid:14)
`
`(cid:0) Mutable Variables(cid:0) x (cid:14) (cid:14)
`
`(cid:0) Parallel composition(cid:0) x (cid:14)(cid:14)
`
`(cid:0) De(cid:17)nitional Variables(cid:0) x (cid:14)(cid:14)
`
`(cid:0) Choice composition(cid:0) x (cid:14)(cid:14)
`
`The components of the PCN toolkit are described in the following sections(cid:14)
`
`(cid:0) Compiler(cid:0) x (cid:14) (cid:9) x (cid:14)
`
`(cid:0) Foreign interface and linker(cid:0) x (cid:14)
`
`(cid:0) Process mapping tools(cid:0) x (cid:14)
`
`(cid:0) Templates(cid:0) x (cid:14)
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 8
`
`

`

`(cid:0) Debugging facilities(cid:0) x (cid:14)
`
`(cid:0) PDB(cid:0) x (cid:14)
`
`(cid:0) Gauge(cid:0) x (cid:14)
`
`(cid:0) Upshot(cid:0) x (cid:14)
`
`(cid:0) Standard libraries(cid:0) x (cid:14)
`
`Machine(cid:2)speci(cid:17)c aspects of the PCN toolkit are described in xx (cid:20) (cid:14) Ad(cid:2)
`ditional documentation on the PCN language(cid:9) toolkit(cid:9) and applications is cited in
`x (cid:14)
`The host(cid:1)control program(cid:9) a utility for managing execution of PCN programs
`on networks(cid:9) is described in a separate document(cid:14) See x  for more information(cid:14)
`
` Getting Started
`
`We assume that PCN is already installed on your computer(cid:14) (cid:1)If it is not(cid:9) read the
`documentation provided with the PCN software release(cid:14)(cid:6) You will need to know
`where PCN is installed(cid:14) Normally(cid:9) this will be (cid:2)usr(cid:2)local(cid:2)pcn(cid:9) but some systems
`may place PCN in a di(cid:13)erent location(cid:14)
`Before you can use PCN(cid:9) you must tell your Unix environment where to (cid:17)nd
`the PCN software(cid:14) If you are using the standard Unix C(cid:2)shell (cid:1)csh(cid:6)(cid:9) you add one
`line to the end of the (cid:17)le (cid:0)cshrc in your home directory(cid:14) If PCN has been installed
`in (cid:2)usr(cid:2)local(cid:2)pcn(cid:9) this line is
`
`set path (cid:3) (cid:4)(cid:5)path (cid:2)usr(cid:2)local(cid:2)pcn(cid:2)bin(cid:6)
`
`The environment variable path tells the Unix shell where to (cid:17)nd the various PCN
`programs (cid:1)compiler(cid:9) linker(cid:9) etc(cid:14)(cid:6)(cid:14) This shell command adds the directory containing
`the various PCN executables to your shell(cid:21)s search path(cid:14)
`If you use either the Bourne shell (cid:1)sh(cid:6) or the Korn shell (cid:1)ksh(cid:6) then you will
`need to add the following commands to the end of the (cid:17)le (cid:0)profile in your home
`directory(cid:14)
`
`PATH(cid:3)(cid:5)PATH(cid:7)(cid:2)usr(cid:2)local(cid:2)pcn(cid:2)bin
`export PATH
`
`You may have to log out and log in again for these changes to take e(cid:13)ect(cid:14)
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 9
`
`

`

` An Example Program
`
`We are now ready to compile and run our (cid:17)rst PCN program(cid:14) The syntax of PCN
`is similar to that of the C programming language in many respects(cid:14) Hence(cid:9) it is
`appropriate that our (cid:17)rst program print (cid:22)Hello world(cid:14)(cid:23) (cid:1)the (cid:17)rst C program in
`several well(cid:2)known texts does just this(cid:6)(cid:14)
`
`Module program (cid:0)pcn
`
`main(cid:4)argc(cid:9)argv(cid:9)exit(cid:10)code(cid:6)
`(cid:11)(cid:12) stdio(cid:7)printf(cid:4)(cid:13)Hello world(cid:0)(cid:14)n(cid:13)(cid:9) (cid:11)(cid:15)(cid:9) d(cid:6)(cid:9)
`exit(cid:10)code (cid:3)
`
`(cid:15)
`
`A PCN program consists of one or more modules(cid:14) Each module is contained in
`a separate (cid:17)le with a (cid:0)pcn su(cid:24)x(cid:14) Our example program consists of a single module(cid:9)
`program (cid:9) contained in a (cid:17)le program (cid:0)pcn(cid:14) (cid:1)We(cid:21)ll learn more about modules later(cid:14)(cid:6)
`This example program has one procedure(cid:9) main(cid:14) Its three arguments are the
`number of command line arguments (cid:1)argc(cid:6)(cid:9) a list of those arguments (cid:1)argv(cid:6)(cid:9) and
`a variable to be used for a return code (cid:1)exit code(cid:6)(cid:14) These are described in more
`detail in x (cid:14)(cid:14)
`This procedure makes what is called an intermodule call(cid:0) it calls the printf
`procedure in the stdio module to print (cid:22)Hello world (cid:14)(cid:23) The stdio module is
`distributed with the PCN system(cid:25) it provides many of the functions of the Unix
`(cid:22)standard I(cid:18)O(cid:23) library (cid:1)x (cid:14)(cid:6)(cid:14)
`
` (cid:10) Compiling a Program
`
`In general(cid:9) the
`The PCN compiler(cid:9) pcncomp(cid:9) is used to compile a PCN module(cid:14)
`PCN compiler is invoked very much like most Unix based C and Fortran compilers(cid:14)
`Because our program is contained in a (cid:17)le program (cid:0)pcn(cid:9) we type
`
`pcncomp (cid:1)c program (cid:0)pcn
`
`When compiling program (cid:0)pcn(cid:9) the PCN compiler will produce the (cid:17)le program (cid:0)pam(cid:14)
`The (cid:0)pam (cid:17)le contains PCN object code(cid:14) These (cid:0)pam (cid:17)les are analogous to the (cid:0)o
`(cid:17)les that are produced by most C and Fortran compilers(cid:14) However(cid:9) unlike (cid:0)o object
`(cid:17)les(cid:9) the (cid:0)pam (cid:17)les are completely machine independent(cid:0) the PCN object code that
`is compiled for one machine will work on any other machine without recompilation(cid:14)
`
` (cid:10) Linking a Program
`
`Now that we have program (cid:0)pam which contains the PCN object code for our ex(cid:2)
`ample program(cid:9) we must use the PCN linker to combine this (cid:0)pam (cid:17)le with libraries
`of procedures such as the stdio module and with the PCN run(cid:2)time system(cid:14) The
`result of running the PCN linker will be an executable program(cid:14)
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 10
`
`

`

`The PCN linker will be run by pcncomp when the (cid:1)c argument is not passed to
`pcncomp(cid:14) This is the same convention as is used in most C and Fortran compilers
`to invoke the Unix linker (cid:1)ld(cid:6)(cid:14)
`To link the example program(cid:9) myprogram(cid:9) we type
`
`pcncomp program (cid:0)pam (cid:1)o myprogram (cid:1)mm program
`
`As with most C and Fortran compilers(cid:9) the (cid:1)o speci(cid:17)es that the name of the
`executable produced by the linker will be named myprogram(cid:14) For the moment(cid:9) ignore
`the (cid:1)mm program (cid:26)ag(cid:14) This will be descussed in (cid:1)x (cid:14)(cid:6)(cid:14)
`The PCN linker is relatively slow(cid:14) During program development you may wish
`to use PCN(cid:21)s dynamic loading capability(cid:14) This feature allows you to avoid having
`to relink a program when PCN (cid:17)les are changed(cid:14) It is described in x (cid:14) (cid:14)
`For information on linking PCN programs that call C or Fortran procedures(cid:9)
`see x (cid:14) For more information on using the PCN compiler and linker in general(cid:9) see
`x (cid:14)
`
` (cid:10) Running a Program
`
`To execute a PCN program(cid:9) you can just run it like any other program(cid:14) For example(cid:9)
`to run myprogram you would type the following(cid:9) where (cid:17) is the Unix shell prompt(cid:0)
`
`(cid:17) myprogram
`Hello world(cid:0)
`(cid:17)
`
`In the subsequent examples(cid:9) text typed by the user is written in italic and
`program output in roman(cid:14)
`Command line arguments can be passed to PCN programs as they would be to
`a C program(cid:14) For example(cid:9) the following program prints out the (cid:17)rst few command
`line arguments(cid:14)
`
`Module program(cid:0)pcn
`
`main(cid:4)argc(cid:9) argv(cid:9) exit(cid:10)code(cid:6)
`(cid:11)(cid:19) argc (cid:3)(cid:3) (cid:9) argv (cid:19)(cid:3) (cid:21) a (cid:9) a(cid:9) a (cid:22) (cid:1)(cid:23)
`(cid:11)(cid:12)
`stdio(cid:7)printf(cid:4)(cid:13)(cid:17)s(cid:14)n(cid:17)s(cid:14)n(cid:17)s(cid:14)n(cid:13)(cid:9) (cid:11)a (cid:9) a(cid:9) a (cid:15)(cid:9) (cid:10)(cid:6)(cid:9)
`exit(cid:10)code (cid:3)
`
`(cid:15)(cid:9)
`default (cid:1)(cid:23) (cid:11)(cid:12) exit(cid:10)code (cid:3) (cid:15)
`
`(cid:15)
`
`After this program is compiled as described above(cid:9) it can be run as follows(cid:0)
`
`
`
`Patent Owner Saint Regis Mohawk Tribe
`Ex. 2028, p. 11
`
`

`

`(cid:17) program arg (cid:3)another arg(cid:4)
`program
`arg
`another arg
`(cid:17)
`
`The PCN run(cid:2)time system has a number of run(cid:2)time con(cid:17)gurable parameters
`that can be controlled by command line arguments(cid:14) In order to keep these run(cid:2)time
`system(cid:21)s arguments from interfering with the program(cid:21)s arguments(cid:9) all arguments
`up to but not including the (cid:17)rst (cid:1)pcn argument will be passed to the program(cid:14)
`All arguments after the (cid:1)pcn argument will be passed to the run(cid:2)time system(cid:14) For
`example(cid:9) suppose you run a PCN program as follows(cid:0)
`
`my program my arg my arg (cid:1)pcn (cid:1)n 
`
`This would cause my arg and my arg to be passed to the PCN program(cid:9) and (cid:1)n
`and  to the run(cid:2)time system(cid:14)
`A complete list of these run(cid:2)time system parameters(cid:9) and