segall%surfers.rutgers.edu@RELAY.CS.NET (Ed Segall) (12/30/87)
[this reply is being cross-posted to comp.hypercube] Re your posting... ------------------------------------------------------------------------------ >> As for >> parallelism being harder to exploit than vectorization, the reverse is >> more likely to hold. Parallel execution can be applied to practically any >> vectorizable structure, while the reverse is decidedly not true. > If you are doing even moderately efficient methods of generating non-uniform > random numbers, this is likely to be false. A flexible vector structure like > the CYBER 205 makes the acceptance-rejection step trivial. A rigid vector > structure like the CRAY makes it somewhat harder. On a MIMD machine, we > have to wait for the unluckiest processor to finish. On a SIMD machine, we > have this cost, and also must have both an acceptance and a rejection step > for each cycle which has a rejection, as well as testing at each cycle > whether a rejection has occurred _on any processor_. ------------------------------------------------------------------------------ I don't know much at all about generation of random numbers, so I would like to know how vectorization is more efficient than MIMD procesing. Is the flexible vector structure you refer to the capability for 'gather/scatter/mask/etc' ? Would you detail the basics of the algorithm you have in mind, so that it is clear how a vector machine can process each of its numbers in the same amout of time, but a MIMD machine needs a varying amount of time? If this looks like a leading question, it is. I suspect that the reason for the difference is that in the MIMD algorithm you've partitioned a vector in equal sized chunks among a set of processors, and the processor that gets stuck with the most activity in its interval has to do the most work. This is just a guess, however, and I'd really like to know what the actual reason is. Is this the only practical way to partition the problem, or might there be a different partitioning that would take better advantage of a MIMD machine's structure? In other words, are you trying to program a MIMD machine like a vector machine, because that's what you are used to? Perhaps the currently available MIMD machines are too inefficient at solving this sort of problem, while future machines need not be. If you will be so kind as to tell us more about your problem, perhaps some ideas for improving MIMD machine performance will come out of it. (Gee, I hope this hasn't been discussed recently) Thanks, Ed PS By the way, your posting does not refute the point that was made, since you were able to choose between parallizing and vectorizing your algorithm, and (I surmise) the degree to which it was parallelizable was not trivial. The original point was that there are problems for which vectorization is totally impractical that may be readily parallelized, but that any problem which can be executed on a vector machine should be able to be parallelized. Simulation of a vector pipeline on a MIMD machine is only the most obvious way to do this. uucp: ...{harvard, ut-sally, sri-iu, ihnp4!packard}!topaz!caip!segall arpa: SEGALL@CAIP.RUTGERS.EDU