Newsgroups: comp.parallel From: Stephen Barnard Subject: Re: Parallelism Organization: InterNex Information Services 1-800-595-3333 Date: 6 Jan 1997 13:11:34 GMT Message-ID: <5aqtm6$p0n@server1.ctc.com> Alberto C Moreira wrote: > To the extent that the difference between "serial" and "parallel" is > the complexity of the objects we handle with our primops, math is > what matters; parallelism emanates from the mathematical model we > use to formulate our algorithms. There are some very simply stated problems that have utterly trivial serial solutions but very non-obvious parallel solutions. Two well-known examples are finding the connected components of a graph and finding a maximal independent set of vertices of a graph. The serial solutions involve, respectively, depth-first search and a trivial greedy algorithm. The parallel solutions are too complex to describe here. We just have to face it that parallelism is an added contraint that will always make a problem harder. Some problems aren't so much harder that parallel solutions aren't still easy. Some problems, however, are essentially immune to parallel speedup. The vast majority of really interesting problems are somewhere in between. Steve Barnard -- Articles to bigrigg+parallel@pitt.edu (Administrative: bigrigg@cs.pitt.edu) Archive: http://www.hensa.ac.uk/parallel/internet/usenet/comp.parallel