A computing system for modeling of large-scale markov chains
Yousry Saber El-Gamal · 1985
Discrete Markov chain representation of the random walk scheme is proved to be useful in simulation of physical problems, operations research, and information processing. This method of simulation lends itself directly to parallel processing by virtue of its uniform sequence of operations, small intermediate storage requirements, low accuracy, and simple control. A highly parallel systolic architecture is developed for modeling of large-scale Markov chains. The proposed architecture is mainly composed of a number of identical and independent cells arranged as a pipeline. The computation process is organized as a continous data flow. This eliminates the need for addressing, pointers, broadcasting of data, scheduling, and control. The simplicity of the cell structure, combined with the modularity of the system, makes it well suited to VLSI and the potential WSI implementation. The main features of the Monte Carlo method of simulation are highlighted. Problem solutions by random walk modeling are discussed, with emphasis on the representation of the random walk scheme as the state transition matrix of a discrete Markov chain. A discussion of the impact of large-scale integration on computer architecture is presented, followed by a brief review of some of the existing and proposed parallel architectures, especially systolic arrays and associative pipelines. The main aspects of the proposed pipeline architecture are specified, with a discussion of the means of supplying random numbers and associated data format. In order to estimate the hardware complexity of the advocated processor and the feasibility of its VLSI implementation, the detailed logic equations for a typical cell are developed. The main components of a computing system, based on the proposed pipeline processor, are described. To demonstrate the applicability of this architecture to simulation problems, a number of algorithms for the solution of both stationary and nonstationary boundary-value problems are provided. In conclusion, a theoretical evaluation of performance is given, followed by several suggestions for more extensions and further research.