Newsgroups: comp.parallel From: wittmann@Informatik.TU-Muenchen.DE (Marion Wittmann) Subject: Classification of algorithms Organization: Technische Universitaet Muenchen, Germany Date: Mon, 25 Oct 1993 13:33:01 +0100 A few very nice people have answered to my news : I'm trying to classify parallel algorithms. Especially I'm interested in their characteristial SVM-properties. Therefor I need some literature about application schemes and classification of algorithms, not only of parallel ones. If you know any literature dealing with this subject, please mail wittmann@informatik.tu-muenchen.de Thanks for your help Below you can find a summary of all answers I got till now %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% From: Carlos Falco Korn To: wittmann@informatik.tu-muenchen.de Subject: Classification of algorithms Hi Marion, I'll write in english in case you want to collect and send all responses to the net. We have developed in Basel a methodology for classifying parallel algortihms; we call it BACS (Basel Algorithm Classification scheme). The latest report is available through anonymous ftp from lucy.ifi.unibas.ch, subdirectory baks It is in Postscript format and prints out nicely on NeXT and Macs. If you have problems with it, you can obtain a hardcopy by writing to Prof. Dr. H. Burkhart Institut fuer Informatik, Uni. Basel Mittlere Str. 142 4056 Basel, Schweiz and asking for the report. The classification concentrates on 3 major parts relevant to parallel algorithms: processes, interactions and data. We have identified the most usual attributes related to these three aspects. Work on this project is still going on: things have focused lately on the development of tools based on the classification (see report). But now, there is also major work on giving the terminology a major overview, ie. concretizing several points that have been a little bit neglected. If everything works well, the new report should be finished before X-mas. Note that it will represent ONLY a revision, this means that the structure of the classification (given in the actual report) will NOT change. I left Basel 1 month ago, and am now at Manchester University. I intend to relate BACS to SVM programming models (we have a KSR in Manchester), and check the consequences: BACS relies heavily on message passing, and I would like to generalize it by regarding SVM. Therefore I am naturally interested in your work. Could you explain a bit further what you intend to do, ie. what you expect to find out? I would appreciate a short comment. Cheers, Carlos PS: feel free to contact me on any question on BACS. ************************************************************* * Dr. Carlos Falco Korn | * * Center for Novel Computing | * * Dept. of Computer Science | tel: +44-61-2756144 * * The University | fax: +44-61-2756204 * * Manchester, M13 9PL | email: korn@cs.man.ac.uk * * United Kingdom | * ************************************************************* %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% From: A.D.Ben-Dyke@computer-science.birmingham.ac.uk To: " (Marion Wittmann)" Subject: Re: classification of algorithms You can try the following: @Book{Parallel:Algorithms, author = {Alan Gibbons and Wojciech Rytter}, title = {Efficient Parallel Algorithms}, publisher = {Cambridge University Press}, year = {1988}, annote = {Gives an overview of the techniques used in developing parallel algorithms - it uses the PRAM as the underlying computational model, and describes some of the more basic paradigms (DC, graph stuff) before going on to cover some more complicated structures. All the usual stuff on sorting, parsing, string matching and graph algorithms, as well as a chapter on P-completeness - the class of hardly parallelisable algorithms.}, got = {In Simon's Collection}, } This has a fairly comprehensive bibliography and the PRAM style is close(ish) to the SVM approach. The following is interesting, but not directly relevant: @TechReport{BACS:Skeletons, author = {Helmar Burkhart and Carlos Falco Korn and Stephan Gutzwiller and Peter Ohnacker and Stephan Waser}, title = {{BACS}: Basel Algorithm Classification Scheme}, institution = {University of Basel, Switzerland}, number = {93-3}, year = {1993}, month = {March}, email = {bacs@ifi.unibas.ch}, ftp = {lucy.ifi.unibas.ch:/baks/BACS_1.1_english.ps.Z}, annote = {Describes the software dilemma: learning phase is enormous, too many details required from the user, writing correct programs is very difficult (=> limit on size of manageable system), not protable. Two approaches are discussed: 1. the use of virtual machines to avoid machine dependencies, but they must be general enough to be implementable on a range of machines but not so abstract as to be inefficient. 2. orthogonality of computation and coordination (i.e. implicit parallelism). Another method, algorithmic reusability is proposed, which sits between the two previously mentioned methods (i.e. can provide an intermediate language for mapping a very HLL to a low level one such as Linda). The system defines two types of process - normal computation and demons, with the first step in the process being to develop a computation (with or without demon) and interaction graph (active and passive respectively). As the graph can change at runtime (controlled by the demon) a set of construction (for creating the processes) and destruction (for dismantling and garbage collection) rules need to be provided - one algorithm may have several different rules. A hierarchy of algorithm toplogy is developed with regular and irregular (each process has its own construction rule) and homgenous (all instructions are the same within a group) and inhomogenous (worker) providing the first two levels. Also an algorithm is static (construct/destruct ops called once) or dynamic. Getting back to comms, direct and global (more than 2 processors involved - and either being coupled (explicit involvement) or decoupled) comms are diferentiated. Now the (de)comp rules need to specify what data is distributed and how is it to be achieved and whether they're input/output/temporary. Then global atmoic variables are covered using local, global and deicated (static/dynamic) as the categories with monotone variables being supported. The data granuality is then defined as fine, medium or coarse (depending on the relationship between the total size of the struct vs the amount processed locally). Then the macroscopic program structure is defined (i.e. skeletonish) and the process granuality (fine => SIMD, medium, coarse) and the algorithm is then classified (Static/Dynamic Process, Global/Static/Dynamic Data with more than one attribute being assignable) and typical examples of each discussed. On top of this classification, other attributes are included: toplogy (data+process), time.}, got = {yes}, } Cheers, Andy. %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%% From: Fethi A Rabhi To: wittmann@informatik.tu-muenchen.de Subject: Classification I have made a classification but for a different purpose. I can send you a paper if you give me your address, you might find useful references. Regards, --------------------------------------------------------------------- Dr Fethi A. Rabhi Email : far@dcs.hull.ac.uk Computer Science University of Hull Tel : +44 (0)482 465744 Hull HU6 7RX (UK) Fax : +44 (0)482 466666 %%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%%