Parallelcomputingandmessage-passinginJava

1、Parallel computing and message-passing in JavaBryan CarpenterNPAC at Syracuse UniversitySyracuse, NY 13244Goals of this lecturenSurvey approaches to parallel computing in Java.nDescribe a Java binding of MPI developed in the HPJava project at Syracuse.nDiscuss ongoing activities relat

2、ed to message-passing in the Java Grande ForumMPJ.Contents of LecturenSurvey of parallel computing in JavanOverview of mpiJavanAPI and ImplementationnBenchmarks and demosnObject Serialization in mpiJava nMessage-passing activities in Java GrandenThoughts on a Java Reference Implementation for MPJSur

3、vey of Parallel Computing in JavaSung Hoon KoNPAC at Syracuse UniversitySyracuse, NY 13244Java for High-Performance ComputingnJava is potentially an excellent platform for developing large-scale science and engineering applicationsnJava has advantages.nJava is descendant of C+.nJava

4、omits various features of C and C+ that are considered difficult - e.g pointer.nJava comes with built-in multithreading.nJava is portable.nJava has advantages in visualisation and user interfaces .The Java Grande ForumnJava has some problems that hinder its use for Grande applications.nJava Grande F

5、orum created to make Java a better platform for Grande applications.nCurrently two working groups are exist.nNumeric Working Groupncomplex and floating-point arithmetic, mulitidimensional arrays, operator overloading, etc.nConcurrency/Applications Working Groupnperformance of RMI and object serializ

6、ation, benchmarking, computing portals, etc.Approaches to Parallelism in JavanAutomatic parallelization of sequential code.nJVM for SMP can be schedule the threads of a multi-threaded Java code. nLanguage extensions or directive akin to HPF or provision of librariesMessage Passing with JavanJava soc

7、ketsnunattractive to scientific parallel programmingnJava RMInIt is restrictive and overhead is high.n(un)marshaling of data is costly than socket.nMessage passing libraries in JavanJava as wrapper for existing librariesnUse only pure Java libraries Java Based FrameworksnUse Java as wrapper for exis

8、ting frameworks.n(mpiJava, Java/DSM, JavaPVM)nUse pure Java libraries.n(MPJ, DOGMA, JPVM, JavaNOW)nExtend Java language with new keywords.nUse preprocessor or own compiler to create nJava(byte) code. (HPJava, Manta, JavaParty, Titanium)nWeb oriented and use Java applets to excute parallel task. (Web

9、Flow, IceT, Javelin) Use Java as wrapper for existing frameworks. (I) nJavaMPI : U. of WestminsternJava wrapper to MPInWrappers are automatically generated from the C MPI header using Java-to-C interface generator(JCI).nClose to C binding, Not Object-oriented.nJavaPVM(jPVM) : Georgia Tech.nJava wrap

10、per to PVMUse Java as wrapper for existing frameworks. (II) nJava/DSM : Rice U.nHeterogeneous computing system.nImplements a JVM on top of a TreadMarks Distributed Shared Memory(DSM) system.nOne JVM on each machine. All objects are allocated in the shared memory region.nProvides Transparency : Java/

11、DSM combination hides the hardware differences from the programmer.nSince communication is handled by the underlying DSM, no explicit communication is necessary.Use pure Java libraries(I)nJPVM : U. of VirginianA pure Java implementation of PVM. nBased on communication over TCP sockets.nPerformance i

12、s very poor compared to JavaPVM.njmpi : Baskent U.nA pure Java implementation of MPI built on top of JPVM. nDue to additional wrapper layer to JPVM routines, its performance is poor compared to JPVM. (JavaPVM JPVM jmpi)Use pure Java libraries(II)nMPIJ : Brigham Young U.nA pure Java based subset of M

13、PI developed as part of the Distributed Object Group Meta-computing Architecture(DOGMA)nHard to use.nJMPI : MPI Software TechnologynDevelop a commercial message-passing framework and parallel support environment for Java. nTargets to build a pure Java version of MPI-2 standard specialized for commer

14、cial applications.Use pure Java libraries(III)nJavaNOW : Illinois Institute Tech.nShared memory based system and experimental message passing framework.nCreates a virtual parallel machine like PVM.n Provides nimplicit multi-threading nimplicit synchronization ndistributed associative shared memory s

15、imilar to Linda.nCurrently available as standalone software and must be used with a remote (or secure) shell tool in order to run on a network of workstations.Extend Java Language(I)nUse pre-processor to create Java code.nOwn compiler to create Java Byte code or executable code that loose portabilit

16、y of Java.nManta : Vrije UniversitynCompiler-based high-performance Java system. nUses native compiler for aggressive optimisations.n Has optimised RMI protocol(Manta RMI).Extend Java Language(II)nTitanium : UC Berkeley nJava based language for high-performance parallel scientific computing. nTitani

17、um compiler translates Titanium into C.nExtends Java with additional features like nimmutable classes which behave like existing Java primitive types or C structs.nmultidimensional arraysnan explicitly parallel SPMD model of computation with a global address spacena mechanism for programmer to contr

18、ol memory management. Extend Java Language(III)nJavaParty : University of Karlsruhe nProvides a mechanism for parallel programming on distributed memory machines.nCompiler generates the appropriate Java code plus RMI hooks.nThe remote keywords is used to identify which objects can be called remotely

19、.Web orientednIceT : Emory UniversitynEnables users to share JVMs across a network.nA user can upload a class to another virtual machine using a PVM-like interface.nBy explicitly calling send and receive statements, work can be distributed among multiple JVMs.nJavelin : UC Santa BarbaranInternet-bas

20、ed parallel computing using Java by running Java applets in web browsers.nCommunication latencies are high since web browsers use RMIs over TCP/IP, typically over slow Ethernets.Object Serialization and RMInObject SerializationnProvides a program the ability to read or write a whole object to and fr

21、om a raw byte stream.nAn essential feature needed by RMI implementation when method arguments are passed by copy.nRMInProvides easy access to objects existing on remote virtual machines.nDesigned for Client-Server applications over unstable and slow networks.nFast remote method invocations with low

22、latency and high bandwidth are required for high performance computing.Performance Problems of Object SerializationnDoes not handle float and double types efficiently.nThe type cast which is implemented in the JNI, requires various time consuming operations for check-pointing and state recovery.nflo

23、at arrays invokes the above mentioned JNI routine for every single array element.nCostly encoding of type informationnFor every type of serialized object, all fields of the type are described verbosely.nObject creation takes too long. nObject output and input should be overlapped to reduce latency.E

24、fficient Object Serialization(I)nUKA-serialization (as part of JavaParty)nSlim Encoding type informationnApproach : When objects are being communicated, it can be assumed that all JVMs that collaborate on a parallel applications use the same file system(NSF).nIt is much shorter to textually send the

25、 name of the class including package prefix.nUses explicit (un)marshaling instead of reflection (by writeObject) nFor regular users of object serialization, programmers do not implement (un)marshaling, instead they rely on Javas reflection.Efficient Object Serialization(II)nUKA-serialization (as par

26、t of JavaParty)(cont.)nBetter buffer handling and less copying to achieve better performance.nJDK External Buffering problemsnOn the recipient side, JDK-serialization uses buffered stream implementation that does not know byte representation of objects.nUser can not directly write into External Buff

27、er, instead use special write routines.n UKA-serialization handles the buffering Internally and Public.nBy making the buffer Public, explicit marshaling routines can write their data immediately into the buffer. nWith Manta: The serialization code is generated by the compiler nThis makes it possible

28、 to avoid the overhead of dynamic inspection of the object structure.mpiJava: A Java Interface to MPIMark Baker, Bryan Carpenter, Geoffrey Fox, Guansong Zhang. /projects/pcrc/HPJava/mpiJava.htmlThe mpiJava wrappernImplements a Java API for MPI suggested in late 97.nBuilds on work on

29、Java wrappers for MPI started at NPAC about a year earlier.nPeople: Bryan Carpenter, Yuh-Jye Chang, Xinying Li, Sung Hoon Ko, Guansong Zhang, Mark Baker, Sang Lim.mpiJava features.nFully featured Java interface to MPI 1.1nObject-oriented API based on MPI 2 standard C+ interfacenInitial implementatio

30、n through JNI to native MPInComprehensive test suite translated from IBM MPI suitenAvailable for Solaris, Windows NT and other platformsClass hierarchyMPIGroupCommDatatypeStatusRequestPackage mpiIntracommIntercommPrequestCartcommGraphcommMinimal mpiJava programimport mpi.*class Hello static public v

31、oid main(String args) MPI.Init(args) ; int myrank = MPI.COMM_WORLD.Rank() ; if(myrank = 0) char message = “Hello, there”.toCharArray() ; MPI.COMM_WORLD.Send(message, 0, message.length, MPI.CHAR, 1, 99) ; else char message = new char 20 ; MPI.COMM_WORLD.Recv(message, 0, 20, MPI.CHAR, 0, 99) ; System.

32、out.println(“received:” + new String(message) + “:”) ; MPI.Finalize() ; MPI datatypesnSend and receive members of Comm: void send(Object buf, int offset, int count, Datatype type, int dst, int tag) ; Status recv(Object buf, int offset, int count, Datatype type, int src, int tag) ;nbuf must be an arr

33、ay. offset is the element where message starts. Datatype class describes type of elements.Basic DatatypesMPI Datatype Java DatatypeMPI.BYTEbyteMPI.CHARcharMPI.SHORTshortMPI.BOOLEANbooleanMPI.INTintMPI.LONGlongMPI.FLOATfloatMPI.DOUBLEdoubleMPI.OBJECTobjectmpiJava implementation issuesnmpiJava is curr

34、ently implemented as Java interface to an underlying MPI implementation - such as MPICH or some other native MPI implementation.nThe interface between mpiJava and the underlying MPI implementation is via the Java Native Interface (JNI).mpiJava - Software LayersMPIprog.javaImport mpi.*;JNI C Interfac

35、eNative Library (MPI)mpiJava implementation issuesnInterfacing Java to MPI not always trivial, e.g., see low-level conflicts between the Java runtime and interrupts in MPI.nSituation improving as JDK matures - 1.2nNow reliable on Solaris MPI (SunHPC, MPICH), shared memory, NT (WMPI).nLinux - Blackdo

36、wn JDK 1.2 beta just out and seems OK - other ports in progress.mpiJava - Test MachinesP P r ro oc ce es ss so or rM M e em m o or ry yO O S SI In nt te er rc co on nn ne ec ct tD ual PII 200 M H z128 M BN T 4(SP3)10 M bpsEthernetD ual U l traSparc200 M H z256 M BSol ari s2. 510 M bpsEthernet450 M H

37、 z PII &100 M H z P5256 M B &64 M BLi nux2. X100 M bpsEthernetmpiJava performanceW sockW sockW M PI-CW M PI-CW M PI-JW M PI-JM PIC H -CM PIC H -CM PIC H -JM PIC H -JLi nux-CLi nux-CLi nux-JLi nux-JSMSM144.8 s67.2s161.4s148.7s374.6s- s- sD MD M244.9 s623.3s689.7s679.1s961.2s- s- smpiJava perf

38、ormance1. Shared memory modempiJava performance2. Distributed memorympiJava demos1. CFD: inviscid flowmpiJava demos2. Q-state Potts modelObject Serialization in mpiJavaBryan Carpenter, Geoffrey Fox, Sung-Hoon Ko, and Sang L/projects/pcrc/HPJava/mpiJava.htmlSome issues in design of

39、a Java API for MPInClass hierarchy. MPI is already object-based. “Standard” class hierarchy exists for C+.nDetailed argument lists for methods. Properties of Java language imply various superficial changes from C/C+.nMechanisms for representing message buffers.Representing Message Buffers Two natura

40、l options:nFollow the MPI standard route: derived datatypes describe buffers consisting of mixed primitive fields scattered in local memory.nFollow the Java standard route: automatic marshalling of complex structures through object serialization.Overview of this part of lecturenDiscuss incorporation

41、 of derived datatypes in the Java API, and limitations.nAdding object serialization at the API level.nDescribe implementation using JDK serialization.nBenchmarks for nave implementation.nOptimizing serialization.Basic DatatypesMPI datatypeJava datatypeMPI.BYTEMPI.CHARMPI.SHORTMPI.BOOLEANMPI.INTMPI.L

42、ONGMPI.FLOATMPI.DOUBLEMPI.OBJECTbytecharshortbooleanintlongfloatdoubleObjectDerived datatypesMPI derived datatypes have two roles:nNon-contiguous data can be transmitted in one message.nMPI_TYPE_STRUCT allows mixed primitive types in one message.Java binding doesnt support second role. All data come

43、 from a homogeneous array of elements (no MPI_Address).Restricted modelA derived datatype consists ofnA base type. One of the 9 basic types.nA displacement sequence. A relocatable pattern of integer displacements in the buffer array: disp , disp , . . . , disp 0 1 n-1LimitationsnCant mix primitive t

44、ypes or fields from different objects.nDisplacements only operate within 1d arrays. Cant use MPI_TYPE_VECTOR to describe sections of multidimensional arrays.Object datatypesnIf type argument is MPI.OBJECT, buf should be an array of objects.nAllows to send fields of mixed primitive types, and fields

45、from different objects, in one message.nAllows to send multidimensional arrays, because they are arrays of arrays (and arrays are effectively objects).Automatic serializationnSend buf should be an array of objects implementing Serializable.nReceive buf should be an array of compatible reference type

46、s (may be null).nJava serialization paradigm applied: nOutput objects (and objects referenced through them) converted to a byte stream. Object graph reconstructed at the receiving end.Implementation issues for Object datatypesnInitial implementation in mpiJava used ObjectOutputStream and ObjectInput

47、Stream classes from JDK.nData serialized and sent as a byte vector, using MPI.nLength of byte data not known in advance. Encoded in a separate header so space can be allocated dynamically in receiver.Modifications to mpiJavanAll mpiJava communications, including non-blocking modes and collective ope

48、rations, now allow objects as base types.nHeader + data decomposition complicates, eg, wait and test family.nDerived datatypes complicated.nCollective comms involve two phases if base type is OBJECT.Benchmarking mpiJava with naive serializationnAssume in “Grande” applications, critical case is array

49、s of primitive element.nConsider N x N arrays: float buf = new float N N ; MPI.COMM_WORLD.send(buf, 0, N, MPI.OBJECT, dst, tag) ; float buf = new float N ; MPI.COMM_WORLD.recv(buf, 0, N, MPI.OBJECT, src, tag) ;PlatformnCluster of 2-processor, 200 Mhz Ultrasparc nodesnSunATM-155/MMF networknSun MPI 3

50、.0n“non-shared memory” = inter-node commsn“shared memory” = intra-node commsNon-shared memory: byteNon-shared memory: floatShared memory: byteShared memory: floatParameters in timing model (microseconds) byte floatt = 0.043 t = 2.1 ser ser byte floatt = 0.027 t = 1.4 unser unser byte floatt = 0.062

51、t = 0.25 (non-shared) com com byte floatt = 0.008 t = 0.038 (shared) com comBenchmark lessonsnCost of serializing and unserializing an individual float one to two orders of magnitude greater than communication!nSerializing subarrays also expensive: vec vec t = 100 t = 53 ser unserImproving serializa

52、tionnSources of ObjectOutputStream, ObjectInputStream are available, and format of serialized stream is documented.nBy overriding performance-critical methods in classes, and modifying critical aspects of the stream format, can hope to solve immediate problems.Eliminating overheads of element serial

53、izationnCustomized ObjectOutputStream replaces primitive arrays with short ArrayProxy object. Separate Vector holding the Java arrays is produced.n“Data-less” byte stream sent as header.nNew ObjectInputStream yields Vector of allocated arrays, not writing elements.nElements then sent in one comm usi

54、ng MPI_TYPE_STRUCT from vector info.Improved protocolCustomized output stream classnIn experimental implementation, use inheritance from standard stream class, ObjectOutputStream. nClass ArrayOutputStream extends ObjectOutputStream, and defines method replaceObject.nThis method tests if argument is

55、a primitive array. If it is, reference to the array is stored in the dataVector, and a small proxy object is placed in the output stream.Customized input stream classnSimilarly, class ArrayInputStream extends ObjectInputStream, and defines method resolveObject.nThis method tests if argument is an ar

56、ray proxy. If it is, a primitive array of the appropriate size and type is created and stored in the dataVector.Non-shared memory: float (optimized in red)Non-shared memory: byte(optimized in red)Shared memory: float(optimized in red)Shared memory: byte(optimized in red)CommentsnRelatively easy to g

57、et dramatic improvements.nHave only truly optimized one dimensional arrays embedded in stream.nLater work looked at direct optimizations for rectangular multi-dimensional arrays-replace wholesale in stream.Conclusions on object serializationnDerived datatypes workable for Java, but slightly limited.

58、nObject basic types attractive on grounds of simplicity and generality.nNave implementation too slow for bulk data transfer.nOptimizations should bring asymptotic performance in line with C/Fortran MPI.Message-passing in Java Grande.Projects related to MPI and JavanmpiJava (S

59、yracuse)nJavaMPI (Getov et al, Westminster)nJMPI (MPI Software Technology) nMPIJ (Judd et al, Brigham Young)njmpi (Dincer et al)1. DOGMA MPIJnCompletely Java-based implementation of a large subset of MPI.nPart of Distributed Object Group Metacomputing Architecture.nUses native marshalling of primiti

60、ve Java types for performance.nJudd, Clement and Snell, 1998.2. Automatic wrapper generationnJCI Java-to-C interface generator takes input C header and generates stub functions for JNI Java interface.nJavaMPI bindings generated in this way resemble the C interface to MPI.nGetov and Mintchev, 1997.3. JMPI en