ken%aiai.edinburgh.ac.uk@NSFnet-Relay.AC.UK (Ken Johnson) (02/23/90)
Until someone asked me the question, I had just been parallelising algorithms for the fun of it. But: what sort of application is really worth all the effort of parallelising? A sub-question: What sort of application is worth parallelising with a parallel logic language like Strand-88 or Parlog?
eugene@eos.arc.nasa.gov (Eugene Miya) (02/26/90)
To quote Alan Karp: "Embarassingly parallel." Some image processing problems. Some other science problems with very regular, geometric structure, which also depends on the specific hardware architecture and connectivity.
izahi@portia.Stanford.EDU (Raul Izahi Lopez Hernandez) (02/26/90)
In article <8117@hubcap.clemson.edu> ken%aiai.edinburgh.ac.uk@NSFnet-Relay.AC.UK (Ken Johnson) writes: >Until someone asked me the question, I had just been parallelising >algorithms for the fun of it. But: what sort of application is really >worth all the effort of parallelising? > Well, I can tell you that low level Real Time Image Processing offers a lot of room for parallelizing. By Low Level I mean operations like Automatic Contrast Enhancement,Low Pass, High Pass filtering on stored images. The predictability and simplicity of his operations allows for a nice array or group of processors to incorporate its power in SIMD or Single Operation Multiple Step (SOMS) configurations. My Thesis deals with this aspects and I have been finding a lot of nice surprises once you get to dig into algorithms and implementation. The memory management has to be very smart though. |||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||||| Raul Izahi Lopez Hernandez izahi@portia.stanford.edu Graduate Student, EE Dept. "Nun, ich war und ich bin noch Student, Stanford University denn ein Student bleibt ewig Student!" -DG
ernstl@dnlunx.pttrnl.nl (Lubach E.) (02/27/90)
ken%aiai.edinburgh.ac.uk@NSFnet-Relay.AC.UK (Ken Johnson) writes: >Until someone asked me the question, I had just been parallelising >algorithms for the fun of it. But: what sort of application is really >worth all the effort of parallelising? Well, the answer to this question is fairly simple. You want to parallelise application because it takes to @##%%$%^ long to do it sequentially. Name every heavy duty application in terms of computational effort and in principle it is worth parallelising. This does not mean however that every application is well-suited for parallelising. This depends on the ordering of the operations in an algorithm. For correctness of the algorithm some operations have to be executed in a strict order, thus imposing constraints on the parallelising. If you want to map parallel algorithms onto chip, preferably your algorithm should be very regular. In general, however this is not necessary? Irregular parallel algorithms just require more inventive thinking to map them onto some kind of multiprocessor configuration. >A sub-question: What sort of application is worth parallelising with a >parallel logic language like Strand-88 or Parlog? Ernst Lubach --------------------------------------------------------------------------------E_Lubach@pttrnl.nl "Beam me up,Scottie" J. Kirk
mmh@cs.qmw.ac.uk (Matthew Huntbach) (03/02/90)
In article <8117@hubcap.clemson.edu> ken%aiai.edinburgh.ac.uk@NSFnet-Relay.AC.UK (Ken Johnson) writes: >A sub-question: What sort of application is worth parallelising with a >parallel logic language like Strand-88 or Parlog? A lot of the things these languages are useful for aren't really parallel. They are just easy to express in a pseudo-parallel style. For real parallelism using Strand/Parlog, anything which doesn't involve array access (which cuts out a lot of traditional parallel applications which are often based on array processors). The languages work fine on most divide-and-conquer type algorithms. However the current versions of Strand/Parlog are not much use for OR-parallel type operations or speculative computation i.e. the sort of thing where you know you need the result of calculating A or B, but having the spare processors you calculate both before you know which is required. The reason is that usually you know that you are more likely to need say A than B. The languages don't give you a construct which says "calculate A, and calculate B if you have the spare processing capacity to do so". Such a construct could easily be added to Strand/Parlog - I've been working on it but so far haven't had much luck persuading people it would be useful. At the moment all you can say is "evaluate A and B in parallel" and it is up to the underlying system which is given preference if there are no spare processors available. Matthew Huntbach