+------------------------------------------------------------------------------+ | | | | | M o d u l a - 2 * Programming Environment | | | | created by | | | | Thomas Gauweiler, Stefan U. Haenssgen, Ernst A. Heinz | | Paul Lukowicz, Hendrik Mager, Michael Philippsen | | | | email: msc@ira.uka.de | | | | | | registration email: ipdm2s@ira.uka.de | | | | | | Institute for Program Structures and Data Organization (IPD) | | Department of Informatics | | University of Karlsruhe | | F.R. Germany | | | | April 10, 1994 | | | | | +------------------------------------------------------------------------------+ +------------------------------------------------------------------------------+ | | | | | IPD Modula-2* Non - commercial License | | | | IPD Modula-2* is distributed by the Institute for Program Structures and | | Data Organization (hereafter called "IPD") from the Dept. of Informatics | | at the University of Karlsruhe, a public institution in the German federal | | state of Baden-Wuerttemberg. IPD hereby grants to you a non-transferable, | | non-exclusive, royalty free worldwide license to use, copy, modify, | | prepare integrated and derivative works of, and distribute IPD Modula-2* | | for non-commercial purposes, subject to your agreement to the following | | terms and conditions: | | | | - The IPD Modula-2* Non-commercial License shall be included in the code | | and must be retained in all copies of IPD Modula-2* (full or partial; | | original, modified, derivative, or otherwise). | | | | - You acquire no ownership right, title, or interest in IPD Modula-2* | | except as provided herein. | | | | - You agree to make available to IPD all improvements, enhancements, | | extensions, and modifications to IPD Modula-2* which are made by you or | | your sublicensees and distributed to others and hereby grant to IPD an | | irrevocable, fully paid, worldwide, and non-exclusive license under | | your intellectual property rights, including patent and copyright, to | | use and sublicense, without limititation, these modifications. | | | | - IPD Modula-2* is a research work which is provided ``as is''. IPD and | | its contributors herewith disclaim all warranties with regard to this | | software, including all implied warranties of merchantability and | | fitness of purpose. In no event shall IPD or any of its contributors be | | liable for any special, direct, indirect, or consequential damages or | | any damages whatsoever resulting from loss of use, data, or profits, | | whether in an action of contract, negligence, or other tortious action, | | arising out of or in connection with the use or performance of this | | software. | | | | | +------------------------------------------------------------------------------+ +------------------------------------------------------------------------------+ | | | | | I P D M o d u l a - 2 * M a n u a l | | | | Part I --- General Topics | | | | | | written by Ernst A. Heinz | | | | | +------------------------------------------------------------------------------+ +---------+ | Credits | +---------+ The Modula-2* environment was developed at the Institute for Program Structures and Data Organization (IPD), Department of Informatics, University of Karlsruhe, F.R. Germany. During the long time of its creation the IPD Modula-2* system engaged many people as the following list of kernel contributors demonstrates: - Thomas Gauweiler (distribution, documentation, msmfg, test suite) - Stefan U. Haenssgen (debugger, msXDW, xmsp) - Ernst A. Heinz (compiler, demos, documentation, drivers, libraries) - Paul Lukowicz (compiler, demos) - Hendrik Mager (semantic analysis) - Michael Philippsen (benchmarks, compiler, test suite) We thank Walter F. Tichy and Christian G. Herter for their initial definition of the Modula-2* language extensions. Furthermore, Juergen Fritsch deserves due credits for his corrections and extensions of the Modula-2* parallel libraries "msEnum", "msReduce", and "msScan" --- thank you, Juergen! +---------------+ | Functionality | +---------------+ We have experienced our Modula-2* system to be a very useful tool for research, education, and even large scale program development. The outstanding advantages of the IPD Modula-2* system follow from its unique support of explicitly parallel high-level language constructs on a variety of parallel and sequential machines. This and the fact that it does not cost anything if solely used for research and/or educational purposes, make our Modula-2* system an attractive and valuable platform for classes and courses in parallel programming. The Modula-2* parallel libraries "msEnum", "msReduce", and "msScan", included in the system with complete source codes, surely add to this attraction. These libraries efficiently implement various primitive parallel operations like reductions and scans for one-dimensional arrays. But the IPD Modula-2* system is n o t only directed towards parallel programming. Beside its explicitly parallel features, it is a complete sequential Modula-2 programming environment offering: - an optimizing compiler translating Modula-2 source programs to portable C, - transparent interfacing and full integration of foreign modules written in C, - a sophisticated cross-architecture make facility generating standard Unix makefiles that trigger the separate compilation of Modula-2 and generated or foreign C modules (including automatic re-compilation whenever necessary), - X Windows and Emacs development support, - and some basic libraries (e.g. "msFIO", "msIO", "msMath", and "msTimer"). Although the translation to C causes some complications and disadvantages, mainly the missing option of runtime range and index checking, we are still convinced that its gains clearly outnumber the associated problems. The central arguments for C as an "intermediate" language are availability, portability, and resulting native code quality. Furthermore, many real parallel computer systems do not even support lower-level languages than C which was quite important for our Modula-2* effort. The biggest drawback of the IPD Modula-2* system is the lack of good and consistent symbolic debugging support in terms of the language. Naturally, you can always use your favourite C debugger to investigate the generated C codes. Beside "debugging by value printing" this is what we usually do. It actually works fine because the generated C programs resemble the Modula-2 originals very closely as for structure, readability, and identifiers. But the scheme is far from satisfactory, of course! +--------------+ | Availability | +--------------+ The IPD Modula-2* system is available for 386/486/Pentium PCs running Linux, R3000/R4000 DECStations running Ultrix, SPARC Sun-4s or SparcStations running SunOS, 680x0 Sun-3s running SunOS, and MasPar MP-1/MP-2 massively parallel systems with DECStation frontends running MP-Ultrix. In addition to the above platforms on which the IPD Modula-2* environment actually runs, it is able to generate code for 386/486/Pentium PCs running BSDI/386 Unix and Kendall Square Research KSR-1/KSR-2 parallel systems running KSR-OS. Program development for these target machines is supported by an easy-to-use and fully automatic cross-architecture make facility. The following table lists all the machines and their symbolic architecture names currently supported by the IPD Modula-2* system. I386 = 386/486/Pentium PC running BSDI/386 Unix (sequential) KSRP = Kendall Square Research KSR-1/KSR-2 running KSR-OS (parallel) KSRS = Kendall Square Research KSR-1/KSR-2 running KSR-OS (sequential) LINX = 386/486/Pentium PC running Linux (sequential) MASP = MasPar MP-1/MP-2 with DECStation frontend running MP-Ultrix (parallel) MIPS = R3000/R4000 DECStation running Ultrix (sequential) SUN3 = 680x0 Sun-3 running SunOS (sequential) SUN4 = SPARC Sun-4/SparcStation running SunOS (sequential) +--------------+ | Distribution | +--------------+ You can get the IPD Modula-2* distributions for all supported architectures by anonymous ftp from "ftp.ira.uka.de" [129.13.10.90] in the directory "pub/programming/modula2star". Please do not forget to use binary mode when retrieving any of them! Their names and functionalities are listed below. - "ipdm2s-install" (installation script) - "ipdm2s.doc.tar" (documentation archive) - "ipdm2s...tgz" (distribution archives) The IPD Modula-2* distribution contains only binaries. Unfortunately, we cannot make the sources of our system publicly available. (:-Considering the state of our sources and the many hacks contained therein, this seems to be a wise scheme anyhow ...-:) The documentation archive features abundant gzip'ed documentation (well, at least sort of) and comes in "tar" format. The distribution archives are in gzip'ed "tar" format and consist of: - compiler "msc", - symbolic source-level debugger prototype "msdb" (available for SUN4 only), - makefile generator "msmfg", - main cross-architecture make facilty driver "mm", - several useful command scripts (e.g. "mmclean", "msdel", "msrun", "msproj"), - graphical X Windows environment panel "xmsp", - Emacs elisp-mode "m2s.el" for Modula-2*, - parallel libraries "msEnum", "msReduce", and "msScan", - some basic libraries (e.g. "msFIO", "msIO", "msMath", "msTimer"), and - collected Modula-2* example programs. +--------------+ | Registration | +--------------+ Although IPD Modula-2* does not cost anything if solely used for research and/or educational purposes, we ask you to send a registration email to our electronic registration secretary "ipdm2s@ira.uka.de". Please clearly state your name and current affiliation as well as all archives you retrieved, installed, and intend to use. Thank you very much for your co-operation in advance! Keeping such a registration database is advantageous for both you and us. In case of bug fixes and updates, we can directly inform each registered user. As for funding the future of IPD Modula-2*, evidence of a world-wide user base may decide between "life and death". For further information and bug reports please contact the IPD Modula-2* team at "msc@ira.uka.de". +---------------------+ | Language Extensions | +---------------------+ The programming language Modula-2* was developed to support high-level and machine-independent parallel programming. As described in [1], it embodies the following features: - An arbitrary number of processes operate on data in the same s i n g l e address space. Note that shared memory is not required. The single address space merely permits all memory to be addressed uniformly but not necessarily at uniform speed. - Synchronous and asynchronous parallel computations as well as arbitrary nestings thereof can be formulated in a totally machine-independent way. - Procedures may be called in any context, sequential or parallel, and at any nesting depth. Additional parallel computations can be spawned inside procedures (recursive parallelism). - All abstraction mechanisms of Modula-2 are available for parallel programs. Despite its many achievements, Modula-2* extends Modula-2 with just two new language constructs of simple and compact nature: 1. The distribution of array data may optionally be specified by so-called a l l o c a t o r s. These are machine-independent layout hints for the compiler without any semantic meaning. Allocator ::= LOCAL | SPREAD | CYCLE | SBLOCK | CBLOCK . ArrayType ::= ARRAY [] {"," []} OF . Date arrays will only be physically distributed over the available processor memories if any of their dimensions are decorated with allocators other than LOCAL. If no allocator is specified at all it defaults to LOCAL. Therefore, the below declarations of B and C are effectively equivalent. VAR A: ARRAY[1..n] SPREAD OF INTEGER; B: ARRAY[1..n], [1..n] OF INTEGER; C: ARRAY[1..n] LOCAL, [1..n] LOCAL OF INTEGER; D: ARRAY[1..n] SBLOCK, [1..n] SBLOCK OF INTEGER; 2. To support explicitly parallel computations, Modula-2* introduces the F O R A L L statement in a synchronous and an asynchronous version. ForallStatement ::= FORALL ":" IN (PARALLEL | SYNC) [ BEGIN ] END . Here, denotes an enumeration or a possibly non-static subrange, i.e. the boundary expressions may contain variables. The FORALL creates as many (conceptual) processes as there are elements in . The identifier introduced by the FORALL statement is local to it and serves as a runtime constant for every created process. The runtime constant of each process is initialized to a unique value of . All processes created by a FORALL obtain private instances of variables declared in the optional part. Then they execute the statements in . The END of a FORALL imposes a synchroni- zation barrier on the participating processes; termination of the whole FORALL is delayed until all created processes have finished their execution of . The processes of a synchronous FORALL execute in lock-step, while they run concurrently in the asynchronous case. Hence, for non-overlapping vectors X, Y, Z an asynchronous FORALL statement suffices to implement the vector addition X=Y+Z. FORALL i: [1..n] IN PARALLEL Z[i] := X[i] + Y[i]; END; In contrast to the above, parallel modifications of overlapping data structures may require synchronization. Here, synchronous FORALLs even allow for easy formulation of arbitrary irregular data permutations. FORALL i: [1..n] IN SYNC X[i] := X[p(i)]; END; The above synchronous FORALL permutes vector X according to permutation function p(). The synchronous semantics ensure that all RHS elements X[p(i)] are read and temporarily stored before any LHS variable X[i] is written. The behaviour of branches and loops inside synchronous FORALLs is defined with a MSIMD (multiple SIMD) machine in mind. Consequently, Modula-2* does not require any synchronization between different branches of synchronous CASE or IF statements. The exact synchronous semantics of all Modula-2* statements, including nested FORALLs, and the effects of allocator declarations are described in [2] and [3]. To illustrate the syntax and semantics of private variable declarations inside FORALLs we close this section with an example of a naively parallel matrix multiply combined with a matrix transposition that computes the resulting matrix C according to C=trans(A*B). FORALL i: [1..n] IN PARALLEL FORALL j: [1..n] IN PARALLEL VAR Cij, k: INTEGER; BEGIN Cij := 0; FOR k:=1 TO n DO (* calculate vector product of i-th row *) INC(Cij, A[i,k]*B[k,j]); (* of A and j-th column of B in local Cij *) END; C[j,i] := Cij; (* transposition by storing Cij in C[j,i] *) END; END; +------------+ | Literature | +------------+ [1] S.U. Haenssgen, E.A. Heinz, P. Lukowicz, M. Philippsen, and W.F. Tichy. "The Modula-2* environment for parallel programming." In Proceedings of the Working Conference on Programming Models for Massively Parallel Computers, Berlin, Germany, September 20-22, 1993. (available by anonymous ftp from i41s10.ira.uka.de [129.13.13.110] in directory "pub/m2s" as "pmmp93.ps", "pmmp93.ps.gz", or "pmmp93.ps.Z") [2] W.F. Tichy and C.G. Herter. "Modula-2*: An extension of Modula-2 for highly parallel, portable programs." Technical Report No. 4/90, Department of Informatics, University of Karlsruhe, January 1990. (available by anonymous ftp from i41s10.ira.uka.de [129.13.13.110] in directory "pub/m2s" as "m2s90.ps", "m2s90.ps.gz", or "m2s90.ps.Z") [3] J.R. Smith. "The design and analysis of parallel algorithms. Chapter 3: Modula-2*." Oxford University Press, December 1992. [4] M. Philippsen, E.A. Heinz, and P. Lukowicz. "Compiling machine-independent parallel programs." ACM SIGPLAN Notices, Volume 28, No. 8, pages 99-108, August 1993. [5] M. Philippsen, T.M. Warschko, W.F. Tichy, C.G. Herter, E.A. Heinz, and P. Lukowicz. "Project Triton: Towards improved programmability of parallel computers." In D.J. Lija and P.L. Bird (editors), The Interaction of Compilation Technology and Computer Architecture, Kluwer Academic Publishers, 1994. +------------------------------------------------------------------------------+ | | | | | I P D M o d u l a - 2 * M a n u a l | | | | Part II --- Using the Software | | | | | | written by Thomas Gauweiler | | | | | +------------------------------------------------------------------------------+ +--------------+ | Installation | +--------------+ You get the package with two files: a tar file and the script ipdm2s-install 1) use ipdm2s-install with two arguments: 1st: the architecture (eg.SUN4, MIPS) 2nd: the directory where msc should be installed, further called ipdm2s-install untars the files and generates several files and scripts. 2) edit the file "architectures" for your system (see below). 3) if you want cross compilation, make sure that rlogin doesn't require the password. Otherwise rsh breaks with "Permission denied". 4) every user has to extend his paths with /bin +---------------+ | File Concepts | +---------------+ The programs "msc" and "msmfg" assume a fixed pre-defined directory structure. You can use msproj with the argument for the target architecture to create this structure. The suffix of definition modules is .msd and the files are in the directory ./msd. The suffix of the main module is .msm, found in ./msm and the suffix of the implementation modules is .msi, you can find them in ./msi. ./msd and ./msi contain machine independent files. The following files depend on the used machine, therefore they are stored in different architecture directories. After compiling using the script mm you find the generated definitions (*.h) in ./sym/, the generated implementations (*.c) in ./imp/, the (by the c-compiler) generated objects (*.o) in ./obj/ and last but not least the linked binaries in ./bin/. The generated makefile is in ./mkf/. At this time there are the following architectures available: for sequential: SUN3 for Sun 680x0, SUN4 for Sparc, I386 for BSD386, LINX for 386/486/Pentium PC running Linux, MIPS for DECstation, KSRS for KSR sequential real parallel: MASP for Maspar, KSRP for KSR parallel. The msc compiler binary is available for SUN4 for Sparc, MIPS for DECstation, LINX for Linux +---------------------+ | Compiling and so on | +---------------------+ 1) create a working directory. 2) type msproj (ex. msproj SUN4) to create the directory structure. 3) Copy your Modula-2* sources to ./msd and ./msi, foreign modules (.c) to ./imp/, their headers (.h) to ./sym/ 4) if you don't use Xwindows: 4a) Compile on your own machine for its architecture: type /mm 4b) If you want cross compiling for architecture : type /mm : 4c) If you want cross compiling on machine for your own architecture type /mm @ 4d) If you want cross compiling on machine for architecture type /mm @: or type /mm :@ 4) if you use XWindows type xmsp for a panel, it calls mm. "mm" looks on what architecture you are, determine several parameters for "msmfg" and invokes it. "msmfg" parses your sources, looks for their dependencies and generates a makefile "mm" invokes "make" for compiling. If you give "mm" more than one parameter, "mm" passes them as additional parameters to "msmfg". Therefore there is no blank between and : or @ ! +---------+ | Options | +---------+ a) common options for "msmfg" and "msc" -target_arch set the architecture for generated code -verbose verbose - control messages -help help -path add new paths -noproject the project dir structure is not used -tab set the path for syntax tables only for msc developers -silent nearly no output is generated -msm, -msd, -msi, -sym, set the file extensions for different compiler phases -imp, -obj (defaults: .msm, .msd, .msi, .h, .c, .o) set in the architecture file b) options only for msmfg -source_arch necessary for finding the right msc-compiler ($MSC_HOME/bin/$SOURCE_ARCH/msc.$SOURCE_ARCH) -system generate $SYSTEMMODULE.o etc. only for msc developer -compiler set the value for $CC -linker set the value for $LN -machine set the value of machine name for rsh command -master_mkf for using another master makefile (default: master) -debug using debug mode (analog for '-master_mkf master.debug') -optimize using optimize mode (analog '-master_mkf master.optimize') -profile using profile mode (analog '-master_mkf master.profile') -oforc generates -o Option for cc *.c too if not set then mv command will be generated -rlo remote link only -list prints the import structure of your program c) options only for msc be careful, they may be obsolete -c generate type casts to make programs lint free -g1 generate GRL description of the dependence graph including only SYNC dependences -g2 generate GRL description of the dependence graph including pseudo and SYNC dependences (pseudo dependences are shown in dotted style) -g3 generate GRL description of the dependence graph including normalized and SYNC dependences (normalized dependences are shown in dashed style) -g4 generate GRL description of the dependence graph including normalized, pseudo, and SYNC dependences (normalized dependences are shown in dashed style, pseudo dependences are shown in dotted style) -h print help information -i generate header files for imported modules -ldir specify directory where msc finds its tables -m print test output (memory) -P specify number of PEs to generate code for -r generate runtime checks -s print test output (dependence analysis statistics) -s1 print test output (SYNC dependences) -s2 print test output (pseudo dependences) -s0 no sync point optimization -q quiet - don't print the header -t print test output (time) -w suppress warning diagnostics -z do not perform subscript analysis -_ try to generate code in spite of errors (no direct exit) +---------+ | Scripts | +---------+ all script work with the schema: