Language and Debugging Support for Multi
Contents
1. Application MASS Library mnode0 uwb edu mnode1 uwb edu Figure 1 Parallel execution with MASS library 2 2 Library Specification A user designs behaviors of a place and an agent by ex tending the Place and Agent base classes respectively pop ulates them through the Places and Agents classes and per forms their computation through the following methods Places Class e public Places int handle String primitive String className Object argument int size instantiates a shared array with size from className or a primi tive data type as passing an argument to the className constructor This array receives a user given handle public Object callAll String functionName Ob ject arguments calls the method specified with functionName of all array elements as passing argu ments i to element i and receives a return value from it into Object i Calls are performed in paral lel among multi processes threads In case of a multi dimensional array i is considered as the index when the array is flattened to a single dimension public Object callSome String functionName Ob ject argument int index calls a given method of one or more selected array elements If index i is not negative it indexes a particular element a row or a column If index i is negative say x it indexes every x h element Calls are performed in parallel e public void exchangeAll int handle String function2. 17 return null 18 Figure 2 Two MASS methods and their preprocessor generated code 1 element in each place 12 elements in each place Figure 3 Communication among neighboring Place objects computation amount per Place Anew MASS library func tion named exchangeBulk exchanges such boundary infor mation among neighboring Places As shown in Figure 4 we achieve it by translating exchangeBulk into a combina tion of exchangeAll and callAll lines 6 7 the former calls a given function of all neighboring Place objects to retrieve their boundary information and the latter put the informa tion into the local Place s boundary space The MASS pre processor assumes that a user defines exchangeArray and putArray where Array is a user defined Place object each actually achieving data retrieval and saving operations If not the preprocessor generates simple stub functions lines 9 15 Thereafter it converts this pair of exchangeAll and callAll into those calling the user functions with their func tion IDs as described in Figure 2 3 2 Design Strategies We design and implement the MASS preprocessor based on the following two strategies First we use an existing Java compiler compiler tools JavaCC and JJTree Anew MASS method to exchange boundary data myPlaces exchangeBulk h Array neighbors preprocessor generated exchange callAll from exchangeBulk myPlaces exchangeAll h exchangeArray neighbors
3. myPlaces callAll h putArray neighbors OMAANNBRWNK public Object exchangeArray Object src 10 return Object Array getBoundary int src 11 12 public Object putArray Object arg 13 Array putBoundary inMessages 14 return null 15 Figure 4 exchangeBulk and its preprocessor generated code for parsing and optimizing MASS user programs Sec ond we carry out two passes of MASS program transla tion pass 1 converts exchangeBulk into a combination of exchangeAll callAll and pass 2 generates additional code to call a user function from a MASS library method with its function ID The following details an implementation of our MASS preprocessor 3 3 Implementation The preprocessor performs its optimizations by running the input code through a Java parser The parser emits to kens in response to the input code Actions are taken on specific tokens to check conditions set flags and mod ify output A grammar defines a roughly correct version of Java It has been modified to create Abstract Syntax trees From the grammar a parser is generated as Unpar seVisitor java which by default will output any input which matches the Java language as defined by the grammar As shown in Figure 5 the parse methods can be overwritten with MASSOptimizer ExchangeBulkOptimizer or Reflec tionOptimizer to perform MASS optimizations For exam ple when parsing a MethodDeclaration token a flag will be set to indicate t
4. Name Vector lt int gt destinations calls from all ele ments a given method of all destination elements each indexed with a different Vector element Each vector element say destination is an array of integers where destination i includes a relative index or a distance on the coordinate 7 from the current caller to the callee element The caller passes its outMessage data mem ber to the callee as a set of arguments and receives return values in its inMessage e public void exchangeSome int handle String func tionName Vector lt int gt destinations int index calls each of the elements indexed with index The rest of the specification is the same as exchangeAll Agents Class e public Agents int handle String className Object argument Places places int population instantiates a set of agents from className passes the argument to their constructor associates them with a given Places matrix and distributes them over these places based on map that is defined within the Agent class e public void manageAll updates each agent s status based on its latest calls of migrate spawn kill sleep wakeup and wakeupAll These methods are defined in the Agent base class and may be in voked from other functions through callAll and ex changeAll 2 3 Design Issues From the user viewpoint Places and Agents are theoret ically considered as an array or a collection of Place and Agent
5. in generat ing get and put methods to automate entire boundary to boundary element transfers Javassist facilitates a compiler assisted Java bytecode manipulation that defines new classes freezes existing classes and customizes class members 1 Therefore Javassist can works as another option to optimize the ex changeBulk function and to match user function names in the MASS library and their actual function bodies by directly manipulating a user program However it would be the same amount of work required if our preprocessor were redesigned to introspect and manipulate all MASS keywords with Javassist 5 2 Debuggers The MASS debugger is a framework oriented library based visualization focused and data parallel application debugger In these categories we found similarities to and differences from the following four products Hadoop and the MASS debugger are both framework oriented debugging utilities Hadoop uses a Java class based on the JUnit3 test case and performs testing using a virtual map cluster 8 The MASS debugger debugs through the actual execution of the MASS program as MASS controls where its computational spaces run Hadoop Test Case out put is console output shown through the user s IDE MASS debugger output uses its own graphical interface MPI Debugging Interface is used to provide the concep tual message passing state of the program 2 The debug ger implementation studies the communicator
6. relied on an iterative approach that focused on de sign planning and prioritization of features A basic goal is to implement features as simply as possible Early in the process it became apparent that there were two challenges accessing MASS and creating the graphical interface Com paring the two using MASS was simpler than creating the graphics but had yet to be thoroughly explored The de bugger is the first application to demonstrate that multiple classes can utilize MASS concurrently 4 3 Implementation The debugger program exists separately from the MASS library Therefore it is not affected by changes in the MASS implementation that don t affect MASS function signatures In effect it serves as an intermediary layer that wraps MASS functions In addition to the debugger class there are classes for graphical control objects the display win dows and buttons When data is returned from the MASS classes in addition to returning the data to the user the de bugger also instantiates graphical objects using Java s awt classes and displays the results The organization of the re sults are based on the user defined sizes of the arrays that are passed to MASS when it is initialized In this context the implementation of the debugging features only has to use simple private counters and Booleans to keep track of it erations and breakpoints When a breakpoint is hit further function calls to MASS are suspended Since all MASS
7. results are returned in single arrays there is no latency in updating individual node results from the debugger or user perspective Depiction of exchange results are more dif ficult because MASS does not provide return values for Relationship of the Debugger utility to MASS Application Layer Displays results to user in a GUI Calls MASS functions through a debugger object Debugger Sends and receives calculations through the MASS Library MASS Class Library Middleware Layer Figure 8 Interaction between the debugger a user application and MASS them The user provides a vector of relative node coordi nates where data is exchanged The debugger applies the vector to each computational node to determine the coor dinates where the data exchange occurred and shows the last computation from a MASS CallAll function as the data that is sent Checkpoints take the return values from a computation and store them in a file The file is read back into an array of objects when the checkpoint is restored and passed to MASS It is important to note that this method of restoring a checkpoint is only valid if the user s places do not rely on local resources such as a local system clock for their calculations The debugger offers three general types of public methods as shown in the sample code of a simple driver application in Figure 9 e MASS equivalent functions with identical signatures e MASS equivalent functions
8. through a 2D or 3D graphical view 4 1 Debugging Features The basic objective of the debugger is to display the con tents of computational nodes in a human understandable format as shown in Figure 7 Its features are designed to support this goal Displays results in a flat view or hawk s eye view Opens windows to display additional dimensionality Allows debugging in code or in GUI Sets break points and defines iteration points Advances to next break point or by iteration Shows communication between logical nodes Saves and restores computational values The developer can set break points in program iteration This differs from traditional debugging code break points and is more akin to setting break points based on variable values However the developer can specify when in the driving code that an iteration occurs allowing a more fine grained approach than might be initially apparent MASS Debugger Version 1 00 Toon oo on ft Next Break Continue to End Iterations 244 Save Restore Change Perspective Exchange View Figure 7 Debugger GUI s hawk s eye view of computational node values 4 2 Design Strategies Design of the debugger followed a twofold strategy The debugger wraps functions of the MASS class library as shown in Figure 8 and development is driven by the need for features to show information in terms of the MASS ap plication developer s perspective The development of the debugger
9. with extended signatures for the debugger e Debugger only functions such as setting break points The MASS functions with extended signatures combine MASS equivalent functions with debugger functions trad ing fewer function calls for ones with more parameters Control buttons also implement debugger functions for fea tures such as advancing one iteration or continuing to the next break point while the user s program is running Initialization of MASS through debugger debugger degubInit totalSize totalDimensions DebuggerDriver threads 0 999 Pure debugger functions debugger setTotalIterations iterations debugger setBreakPoint 20 debugger setStopOnBreakPoint true OMAANNBWNR 10 Use of MASS through debugger 11 while debugger isFinished 12 MASS equivalent function called through 13 debugger shows results in GUI by default 14 debugger debugCallAll 0 Object null 15 16 with iteration set separately 17 debugger iterate 18 19 MASS function with debugger parameters 20 ticks iterator shows results in GUI 21 debugger debugIterateCallAll 0 Object null 22 true 23 24 25 end debugger operations and clean up graphics 26 debugger finish Figure 9 Code using debugger breakpoint set for every 20 iterations 5 Related Work 5 1 Preprocessors Our MASS library and preprocessor design involves library assisted parallel execution prep
10. At present our preprocessor has the following limitations and issues 1 MASS applications to be processed should not contain a method named callMethod or use a trailing underscore _ as part of a method name 2 all meth ods to be called from callAll Some or exchangeAll Some must accept the same set of parameters in the same order 3 user owned non MASS methods should not have names identical to MASS methods and 4 MASS variables may not be recognized if they are cast or assigned to other classes at runtime We believe that these limitations are acceptable As our future work items we are developing C C and CUDA C versions of the MASS library Since C and C allow programmers to use dynamic linking and func tion pointers we do not see any necessity of developing a MASS preprocessor for them However CUDA C has its own extensions to C Although these extensions are quite unique to GPUs we are planning to develop a preprocessor that assists C programmers in running MASS applications on GPUs Our ultimate goal is to facilitate a Java or C version of the MASS library for GPU computation through a cascading code translation to CUDA C 6 2 Debugger Currently the MASS debugger focuses on the step by step display of computational node data and communica tion The limitations include 1 agents and their migration are not displayed 2 the interface is still only a proof of concept design 3 break points are not b
11. Language and Debugging Support for Multi Agent and Spatial Simulation Niko Simonson Sean Wessels Munehiro Fukuda Computing amp Software Systems University of Washington Bothell 18115 NE Campus Way Bothell WA 98011 Abstract The MASS Multi Agent Spacial Simulation library fa cilitates parallelization of applications that are viewed as interaction among up to millions of agents behaving over a shared virtual space and that are thus fitted to simula tion of ecological social and physical mechanisms The li brary invokes user defined functions of all agents and array elements as well as exchanges data among them in paral lel The key to success of this library implementation is to accelerate function invocation with preprocessor generated code and to facilitate an application debugging environ ment This paper presents the design strategy implemen tation and usability of the MASS library preprocessor and debugger 1 Introduction Multi agent individual based models view computation as interaction among agents and individuals each au tonomously behaving in a shared simulation environment They have been used for years to simulate ecological so cial and physical mechanisms that are generally difficult only with mathematical formulae To parallelize these mod els we are developing the MASS Multi Agent Spatial Sim ulation library that updates the status of all objects at once with the callAll method and exchange
12. MASS li brary to capture all the library calls so that it graphically shows each object s status monitors inter object communi cation keeps track of agent migration and stops resumes the user program at a break point This paper describes the preprocessor assisted MASS performance improvement and library extension presents the features and internal design of the MASS debugger and demonstrates the uniqueness and usability of these software tools in comparison with related work 2 MASS Library 2 1 Execution Model Places and Agents are keys to the MASS library Places is a multi dimensional array of elements that are dynam ically allocated over a cluster of multi core computing nodes Each element called a place is pointed to by a set of network independent array indices and is capable of ex changing information with any other place objects Agents are a set of execution instances that can reside on a place migrate to any other place with array indices and interact with other agent objects as well as multiple places As shown in Figure 1 parallelization with the MASS li brary uses a set of multithreaded communicating processes that are forked over a cluster and are connected to each other through ssh tunneled TCP links The library spawns the same number of threads as the number of CPU cores per node Those threads take charge of method call and infor mation exchange among places and agents in parallel A Bag of Agents
13. ased on computa tional node values and 4 analysis and step through of the developer code itself is not implemented Implementation of agent status and migration view is the immediate next step in terms of future development The interface must be improved for the overall user experience Allowing break points based on computational node values will give the user more flexibility However the goal of the MASS debugger is to provide an easy way to view MASS computations not to become a commercial debugger with a full feature set Consequently certain debugger features the ability to step through code and to set break points in the code itself are not prioritized for future development 7 Conclusions The MASS library eases parallelization of multi agent individual based models as well as data intensive applica tions In this paper we analyzed the current issues in code development and execution with the library addressed them with our preprocessor approach and debugger design The MASS library and tools will be made available upon an email request sent to dslab uw edu References 1 S Chiba and M Nishizawa An easy to use toolkit for ef ficient java bytecode translators In Proc of 2nd Int l Conf on Generative Programming and Component Engineering GPCE 03 volume LNCS 2830 pages 364 376 Erfurt Ger many September 2003 Springer Verlag 2 J Cownie and W Gropp A standard interface for debugger access to messa
14. eAll Some methods as well as adding additional graphics code into their application programs In particular it is tedious work for application designers to keep track of migrating Agent objects over different computing nodes We address these debugging issues by designing a wrapper that covers the original MASS library and facilitates GUI based debugging features The next two sections explain these solutions 3 Preprocessor Design 3 1 Library Extension We extend MASS to avoid Java reflection and to accel erate message exchange among Place objects as follows Eliminating Java Reflection Given a function name in the MASS methods we need to quickly identify its func tion body to invoke A trivial but naive idea is to store user function names in a symbol table at compile time and there after to compare each symbol table entry with a function name specified in a MASS method each time it is invoked at run time The problem is repetitive string comparisons that may weigh more than actual computation at each place or agent Instead we use integer comparisons where user func tion names found in MASS methods receive a different inte ger 1 e a function id at compile time and a MASS method invokes the user function corresponding to a given function id Figure 2 shows preprocessor generated example code that jumps from two MASS methods to a different user function two user function names such as exchangeAr ray and putArray in
15. exchangeAll and callAll lines 1 2 receive a function ID respectively lines 6 7 the original exchangeAll and callAll calls the preprocessor generated callMethod line 12 and the control branches off to the corresponding user function based on the function id lines 14 15 Exchanging Each Place s Boundary Information The MASS library originally assumes that a Place object is used as an individual element of a distributed array How ever the cost for exchangeAll Some is substantial to fine grained computation at each Place object because data exchange generally takes place with multiple neighbors Therefore a user wants to include a collection of array el ements in each Place object that then exchanges its bound ary elements or shadow elements in fewer packets with neighbors as shown in Figure 3 This reduces the frequency of communication over an entire array while increasing the the original MASS methods myPlaces exchangeAll h exchangeArray neighbors myPlaces callAll putArray args preprocessor generated code to jump user functions public static final int exchangeArrayP_ public static final int putArrayP_ 0 1 OMAANNBWNK myPlaces exchangeAll h exchangeArrayP_ neighbors 10 myPlaces callAll putArrayP_ arggs 12 public Object callMethod int funcId Object args 13 switch funcId 14 case exhangeArrayP_ return exchageArray args 15 case putArrayP_ return putArray args 16
16. ge queue information in MPI In Proc of Re cent Advances in Parallel Virtual Machine and Message Pass ing Interface 6th European PVM MPI Users Group Meeting PVMMPI 99 volume LNCS 1697 pages 51 58 Barcelona Spain September 1999 Springer 3 Y Ichisugi and Y Roudier The extensible Java preproces sor kit and a tiny data parallel Java In Proc of the Scien tific Computing in Object Oriented Parallel Environments IS COPE 97 volume LNCS 1343 pages 153 163 Marina del Rey CA December 1997 Springer Verlag 4 A Kaminsky Parallel Java A unified API for shared memory and cluster parallel programming in 100 Java In Proc 21st IEEE Int Parallel and Distributed Processing Symposium IPDPS pages 1 8 Long Beach CA March 2007 IEEE CS 5 M Krishnan B Palmer A Vishnu S Krishnamoorthy J Daily and D Chavarria The global arrays user manual Technical report number pnnl 13130 Pacific Northwest Na tional Laboratory Richland WA November 2010 6 E Renault and C Parrot MPI pre processor generating MPI derived datatypes from C datatypes automatically In Proc 2006 Int l Conf on Parallel Processing Workshops pages 248 256 Columbus OH September 2006 IEEE CS 7 Rogue Wave Software Inc Totalview User Guide Version 8 9 2 Boulder Colorado November 2011 8 J Venner Pro Hadoop chapter 7 Unit Testing and Debug ging pages 207 237 Apress New York NY 2009
17. hat a new method is being parsed and that a new scope must be placed on the stack Subsequently if a ResultType token is parsed while the MethodDeclaration flag remains set the return type of the parsed method can be recorded These optimizers in Figure 5 set flags in their visit methods and implement the logic to respond to those conditions in their find Token methods The preprocessor has been tested on some MASS programs including two dimensional wave simulation Wave2D and three dimensional computational fluid dy namics CFD The verification and performance evaluation has been conducted by comparing manually translated ver sus preprocessor generated code Figure 6 demonstrated the competitive performance of preprocessor generated code in ExchangeOptimizer ReflectionOptimizer MASSOptimizer Unparse Visitor Java Grammar Figure 5 MASS preprocessor implementation Code exchangeAll callAll Manual 9730 5 ms 4605 25 ms 1505 5 ms Preprocessor 9785 ms 4366 25 ms 1705 75 ms Wave2D Code Total Manual 9730 5 ms Preprocessor 9785 ms CFD Figure 6 Preprocessor generated code exe cution Wave2D and CFD when running the code four times on a 64 bit 2 27GHz Intel Core 4 Debugger Design A simple debugging program was implemented to assist MASS developers Currently the debugger uses the multi threaded Java version of MASS It allows users to view a logical arrangement of their computational spaces values
18. objects respectively However their underlying im plementation is not so simple in order to not only serve as a general simulation framework but also to work over a distributed memory cluster We need to address the two design challenges below Language Issues Unless a user implements base meth ods of the Place or Agent class Places and Agents do not know any methods of a user defined class This in turn means that the callAll Some and exchangeAll Some methods cannot invoke a user function simply through object cast ing Instead we need to use Java reflection to interrogate a user defined class The problem is that the reflection works one order slower than a direct function call in general This slow performance kills parallelization where MASS calls the same function of all objects at once To pursue both naming flexibility and high speed invocation of user func tions we design a Java preprocessor that inserts additional code to match the names of user functions defined in MASS methods and the actual function bodies to invoke so that the library calls user functions without the reflection Debugging Issues Since Places and Agents may be al located over a distributed memory cluster the status and execution of their elements is not always visible and trace able where the main program is running For debugging purposes users are responsible to collect remote element status by manually inserting combinations of callAll Some and exchang
19. queues the MASS equivalent of these are the parameters of its major functions Both applications conclude that accessing the li brary class must be led by the debugger Specific interfaces to display data are not implemented by the MPI debugger in contrast to the MASS debugger s GUI Total View is a feature heavy commercial debugging in terface designed for distributed software 7 TotalView like MASS makes use of a GUI for data visualization but lacks concurrent display of values The Total View software is more sophisticated than MASS but also more compli cated and is not free MASS in contrast is geared specifi cally to MASS users and is currently free Using Total View with MASS would strip away all the abstraction that the MASS library is providing Global Arrays are a means to solve data parallel jobs and intersects with MASS s application areas 5 It gives the user very fine grained control over the data objects it uses but at the cost of a great deal of programming com plexity in implementation In contrast MASS aims explic itly to simplify and abstract away complexity Global Ar rays do not in themselves provide explicit debugging tools while the MASS debugger is an extension of MASS that does not currently exist in Global Arrays In summary we believe that our design strategy for the MASS preprocessor and debugger fits user requirements for multi agent spatial simulation 6 Future Work 6 1 Preprocessor
20. rocessor assisted code generation and code manipulation Those techniques are found in the following four language systems Parallel Java Library promotes hybrid SMP cluster pro gramming in Java by combining multithreaded program ming constructs and MPI based message passing func tions 4 MASS and Parallel Java libraries both take a similar approach in hiding all underlying parallelization work with their Java library classes and methods How ever the major difference is that MASS does not distinguish shared and distributed memory but gives a consistent view of multi agents running on a shared array regardless of un derlying memory architectures Extensible PreProcessor EPP defines plug ins for gen erating tiny data parallel Java code 3 where the special modifier parallel given to a Java class generates addi tional multithreading code in its run method that handles all data with virtual processors in parallel Although MASS and EPP use a preprocessor approach for parallelization EPP focuses on multithreading whereas the MASS prepro cessor extends its scope to hybrid SMP cluster computing MPIPP is another preprocessor tool that converts a user defined data structure into MPI derived data types 6 It is similar that our exchangeBulk function converts a cer tain range of boundary array elements to Place outMessage as well as Place inMessages back to the original elements However our MASS preprocessor is different
21. s data among all ob jects at once with exchangeAll method These methods are attributed as 1 one sided parallel communication from the main function to all array elements and 2 one sided par allel communication from each element Therefore MASS benefits not only multi agent models but also data intensive computation with its parallelization We implemented MASS in Java from the viewpoint of its widely used and convenient graphics features How ever due to Java s nature as well as the multi agents be havioral complexity MASS encounters the following four Corresponding author Email mfukuda u washington edu Phone 1 425 352 3459 Fax 1 425 352 5216 challenges 1 parallelization is killed by the slow Java reflection that is used to identify a user function called from callAll exchangeAll 2 exchangeAll incurs substan tial communication overhead if applied to computationally fine grained elements 3 a programmer needs to check inter element communication flow at an application level and 4 agent migration is difficult to keep track of at a user level To address these problems we have developed a language preprocessor and GUI based debugger for the MASS library The preprocessor inserts additional code in a given application for calling a user function from callAll exchangeAll without using Java reflection and for transferring multi element data in bulk The debugger runs between a user application and the underlying
Download Pdf Manuals
Related Search