PSB graphs for simulating cooperative and distributed program behavior

ABSTRACT

There are many areas of investigation where it is necessary to model the structure and behavior of distributed programs. Many models exist, though most tend to focus on some particular aspect of program behavior. For many problems, such as task mapping in real-world systems, it is necessary to coalesce all major features of distributed program structure and behavior into a single model. This paper presents a model called a Program Structure and Behavior graph which provides a basis for simulating cooperative and distributed programs. A facility which can simulate these distributed programs has been developed and tested. The paper describes this facility along with example runs.

REFERENCES

• 1: W. Shen and A.Y. Oruc, "Systolic Arrays for Multidimensional Discrete Transforms", To appear in: IEEE Transactions on Computers, in late 1989.
• 2: Yi-Hsiu Wei , Jean-Luc Gaudiot, Demand-Driven Interpretation of FP Programs on a Data-Flow Multiprocessor, IEEE Transactions on Computers, v.37 n.8, p.946-966, August 1988 [doi>10.1109/12.2246]
• 3: Marco Ajmone Marsan , Gianni Conte , Gianfranco Balbo, A class of generalized stochastic Petri nets for the performance evaluation of multiprocessor systems, ACM Transactions on Computer Systems (TOCS), v.2 n.2, p.93-122, May 1984 [doi>10.1145/190.191]
• 4: G. Balbo , S. C. Bruell , S. Ghanta, Combining Queueing Networks and Generalized Stochastic Petri Nets for the Solution of Complex Models of System Behavior, IEEE Transactions on Computers, v.37 n.10, p.1251-1268, October 1988 [doi>10.1109/12.5986]
• 5: C.V. Ramaoorthy, K.M. Chandy, and M.J. Gonzales, "Optimal Scheduling Strategies in a Multiprocessor System", IEEE Transactions on Computers, Vol. C-21, No. 2, Feb. 1972, pp 137-146.
• 6: W.W. Chu, L.J. Holloway, M. Lan, and K. Ere, "Task Allocation in Distributed Data Processing", IEEE Computer, Vol. 13, No. l l, Nov. 1980, pp 57-69.
• 7: M. J. Berger , S. H. Bokhari, A partitioning strategy for nonuniform problems on multiprocessors, IEEE Transactions on Computers, v.36 n.5, p.570-580, May 1987 [doi>10.1109/TC.1987.1676942]
• 8: J.M. Butler and A.Y. Oruc, "Intelligent Synthesis of Distributed Processing Architectures", to appear in the Proceedings o{ the ISMM International Symposium on Intelligent Distributed Processing, Dec. 1989.
• 9: J.M. Butler and A.Y. Oruc, "Program Structure and Behavior Graphs for Modeling Distributed Software", tech. report, Dept. of Electrical Engineering, University of Maryland, College Park, MD., Mar. 1989.
• 10: Michael R. Garey , David S. Johnson, Computers and Intractability; A Guide to the Theory of NP-Completeness, W. H. Freeman & Co., New York, NY, 1990

INDEX TERMS

Primary Classification:
  D. Software
  D.1 PROGRAMMING TECHNIQUES

Additional Classification:
  D. Software
  D.2 SOFTWARE ENGINEERING

  G. Mathematics of Computing
  G.2 DISCRETE MATHEMATICS

General Terms:
Design, Performance