The major advantages of parallel processing sys tems are their great reliability and high perfor mance. A class of massively parallel computing systems is the data flow machines. These machines work on the basis of data flow rather than control flow. This paper presents a reliability analysis of data flow machines using a graph theoretical ap proach. Three machines are considered here. They are the MIT, DDP and LAU static data flow ma chines. The data flow graph has been employed as a natural tool for representing that class of ma chines. The isomorphism between Petri nets and data flow graphs has been exploited to detect whether the consistency constraints are satisfied during various operational conditions. Such a graph is extended so that a timed data flow model has been constructed. This model integrates both the reliability features dependent on the system structure and the performance characteristics dependent on the components behavior. More over, a productivity index is introduced for evaluating the three machines.
Herath, J. , Yamaguchi, Y., Saito, N. and Yuba, T. "Data Flow Computing Models, Languages, and Machines for Intelligence Computations." IEEE Transactions on Software Engineering, Vol. 14, No. 12, Dec. 1988.
Ramamoorthy, C.V. and Ho, G.S. "Performance Evaluation of Asynchronous Concurrent System Using Petri Nets." IEEE Transactions on Software Engineering, Vol. SE6, No. 5, Sept. 1980.
4.
Duncan, R. , Control Data Corporation. "Survey of Parallel Computer Architectures." IEEE Computer, pp 5-16, Feb. 1990 .
5.
Haynes, L.S. , Low, R.L., Siewiorek, D.P. and Mizall, D.W. "A Survey of Highly Parallel Computing." IEEE Computer, Jan. 1982.
6.
Hwang, K. and Briggs, F.A.Computer Architecture and Parallel Processing, New York , McGraw-Hill1985.
Baer, J.L.Computer System Architecture, Computer Science Press, 1980.
9.
Srini, V.P. "A Fault-Tolerant Data Flow System." IEEE Computer, Vol. 18, No. 3, March 1985.
10.
Hong, Y.V. , Payne, T.H. and Ferguson, B. "An Architecture For A Data Flow Muliprocessor ." IEEE Computer, 1985.
11.
Srini, V.P. "An Architecture Comparison of Data Flow Systems." IEEE Computer, pp 68-87, March 1986.
12.
Kavi, K.M., Buckles, B.P. and Bhat, U.N. "A Formal Definition of Data Flow Graph Models." IEEE Transactions on Computers, Vol. C-35, No. 11, Nov. 1986.
13.
Randell, B. and Anderson, T. (eds.). Computing System Reliability, Cambridge University Press, 1979.
14.
Das, C.R., Kreulen, J.T., Thazhuthaveetil, M.J. and Bhuyan, L.N. "Dependability Modeling for Multiprocessors." IEEE Computer, pp 7-19, Oct. 1990.
15.
Aho, A.V., Hopcroft, J.E. and Ullman, J.D.The Design and Analysis of Computer Algorithms, Addison-Wesley , Reading, MA, 1974.
16.
Kavi, K.M. and Bhat, U.N. "Reliability Analysis of Computer Systems Using Data Flow Graph Models ." IEEE Transactions on Reliability, Vol. R-35, pp 529-531, Dec. 1986.
17.
Shooman, M.L.Software Engineering Design—Reliability and Management, McGraw-Hill, New York, 1983.
18.
Rai, S."A Cutset Approach to Reliability Evaluation in Communication Networks." IEEE Transactions on Reliability, Vol. R-31, Dec. 1982.
19.
Misra, K.B. and Rao, T.S.M. "Reliability Analysis of Redundant Networks Using Flow Graphs." IEEE Transactions on Reliability, Vol. R-19, No. 1, Feb. 1970.
20.
Rai, S. and Aggarwal, K.K. "An Efficient Method for Reliability Evaluation of General Network ." IEEE Transactions on Reliability, Vol. R-27, No. 3, Aug. 1978.
21.
Jones, C.V. "An Introduction to Graph-Based Modeling Systems ; Part I: Overview." ORSA Journal on Computing, Vol. 2, No. 2, 1990.
22.
Jones, C.V. "An Introduction to Graph-Based Modeling Systems ; Part II: Implementation." ORSA Journal on Computing, Vol. 3, No. 3, 1991.
23.
Meyer, J.F. "On Evaluating the Performability of Degradable Computing Systems." IEEE Transactions on Computers, Vol. C-29, No. 8, 1980.
24.
Kavi, K.M. , Buckles, B.P. and Bhat, U.N. "Isomorphisms Between Petri Nets and Data Flow Graphs." IEEE Transactions on Computers, Vol. SE-13, No. 10, Oct. 1987.
25.
Daniel, W. and Steele, G.L. "Data Parallel Algorithms." CACM, Vol. 29, No. 12, Dec. 1986.
26.
Dennis, J.B. and Misunas, D.P. "A Preliminary Architecture for a Basic Data Flow Processor." Proceedings of the Second Annual Symposium on Computer Architecture , New York, 1975.
Abramson, D. and Egan, G. "The RMIT Data Flow Computer: A Hybrid Architecture ." The Computer Journal, Vol. 33, No. 3, 1990.
29.
Gostelow, K.P. and Thomas, R.E. "Performance of a Simulated Data Flow Computer ." IEEE Transactions on Computers, Vol. C-29, Oct. 1980.
30.
Carlson, W.W. and Hwang, K. "Algorithmic Performance of Data Flow Multiprocessors ." IEEE Computer, pp 30-40, Dec. 1985.
31.
Ghosal, D. and Bhuyan, L.N. "Performance Evaluation of a Data Flow Architecture ." IEEE Transactions on Computers, Vol. 39, No. 5, May 1990.
32.
Baase, S.Computer Algorithms: Introduction to Design and Analysis, Addison-Wesley, Reading, MA, 1988 .
33.
Burkhart, H. and Millen, R. "Performance-Measurment Tools in a Multiprocessor Environment." IEEE Transactions on Computers, Vol. 38, No. 5, May 1989.
34.
Nussbaum, D. and Agarwal, A. "Scalability of Parallel Machines." CACM, Vol. 34, No. 3, March 1991.
35.
Elboraey, M.M. "Reliability of Parallel Processing Systems ." PhD Thesis, Computers and Systems Engineering Dept., Al-Azhar University, Cairo, Egypt, 1992.
36.
Floyd, R.W. "Algorithm 97, Shortest Path" Communications of the ACM, Vol. 5, 1962.
37.
Reed, D.A. and Fujimoto, R.M.Multicomputer Networks: Message-Based Parallel Processing, The MIT Press, Cambridge, MA, and London, England, 1987.
