Table 2 shows that the five different problem architectures are naturally suited (i.e., will run with good performance) to different parallel machine architectures.
Table 2: Parallel Computer Architectures Suitable for each Problem
Class
As described in the previous section, all problems except those in the pure asynchronous class, naturally parallelize on large scale machines as long as the application is large enough. In my 1989 analysis [2], [3] of 84 applications in 400 papers, I estimated that synchronous and loosely synchronous problems dominated scientific and engineering computations, and these two classes were rightly equal in number. This argues that both SIMD and MIMD machines are valuable. Around 50% of the surveyed problems could effectively use a SIMD architecture whereas a comparable number can exploit the additional flexibility of MIMD machines. Note that all distributed memory machines -- whether MIMD or SIMD -- are message passing and so subject to similar analysis. One views the CM-2 not as a bunch of virtual processors controlled by data parallel CMFortran, but rather as a set of 2048 WEITEK based nodes exchanging messages over a hypercube network.
We found 14% embarrassingly parallel applications and 10% asynchronous problems in [2], [3]. The latter contain some loosely synchronous complex problems, but we had not identified this separate class at the time. As parallel computing matures, we expect to see more examples of this complex heterogeneous class -- especially in commercial and government applications.