Computational Process Networks

Computational Process Networks is a model and a framework library for real-time high-throughput signal and image processing. The model combines:

• Process Networks [1], a formal, concurrent model for functional parallelism
• Bounded Scheduling [2] for realization in finite memory
• Firing Thresholds from Computation Graphs [3]

Computational Process Networks model algorithms on overlapping continuous streams of data (such as digital filters and overlap-and-save fast Fourier transforms), and provides liveness and determinate execution. Our C++ implementation provides a portable, high-performance, scalable framework using POSIX Threads.

The March 2000 issue of IEEE Transactions on Signal Processing contains a paper [4] which prototypes a 3-D sonar beamfomer using Computational Process Networks. The beamfomer sustains a real-time 4 GFLOPS on a Sun Ultra Enterprise 4000 with 12 336 MHz UltraSPARC-II processors.

The Computational Process Network source code is publicly available, under the GNU GPL.

Original releases of CPN worked only on symmetric multiprocessing workstations. It is available here.

We are in the process of a complete rewrite of the CPN framework, adding the capability for execution on a distributed network of computers, as well as distributed dynamic deadlock detection and resolution (D4R). D4R algorithm examples are available here.

1. G. Kahn, "The Semantics of a Simple Language for Parallel Programming," Information Processing, pp. 471-475, Stockholm, Aug. 1974.
2. T. M. Parks, "Bounded Scheduling of Process Networks," Technical Report UCB/ERL-95-105, Ph.D. Dissertation, EECS Department, University of California, Berkeley, CA 94720-1770, Dec. 1995.
3. R. M. Karp and R. E. Miller, "Properties of a Model for Parallel Computations: Determinacy, Termination, Queueing," SIAM Journal, vol. 14, pp. 1390-1411, Nov. 1966.
4. G. E. Allen and B. L. Evans, "Real-Time Sonar Beamforming on a Unix Workstation Using Process Networks and POSIX Threads", IEEE Transactions on Signal Processing, pp. 921-926, March 2000.