Legion is designed to support and allow interoperation between multiple programming models. At its base, Legion prescribes the message format for inter-object communications, thereby enabling a wide variety of Legion object implementation strategies. In its most useful form Legion presents programmers with high-level programming language interfaces to the system. These high-level interfaces are supported by Legion-targeted compilers, which in turn use the services of a runtime library that enables Legion-compliant interobject communication.
We have implemented a Legion run-time library (LRTL) [36, 8], and we have ported the Mentat  programming language compiler (MPLC) to use the LRTL.1 Thus, programmers can define Legion object implementations in MPL, which can be translated by MPLC to create executable objects that communicate with one another in a Legion-compliant fashion. Figure 15 depicts this typical programming model.
The runtime library provides classes for LOIDs, Object Addresses (OAs), and bindings. A majority of library users will deal with naming only at the LOID level, leaving OAs and bindings to the low-level library code. The majority of users will dealing with the naming process at the LOID level, leaving OAs and bindings to the low-level library code. Therefore the next section discusses only the LegionLOID class, which manages all of the LOIDs in a Legion system.
In the library, the LOID is represented by the LegionLOID class, which is intended to be the starting point for derived LOID classes implementing different types of LOIDs. We imagine that the classes implementing each LOID type will enforce different properties having to do with the structure, content, and meaning of the various fields of the LOID. Therefore, LegionLOID is not intended to be directly instantiated when the internal fields of the LOID are being used and interpreted: the appropriate derived class should be instantiated instead. So far we have not implemented any derived classes that enforce special properties of the LOID fields, so until then the LegionGeneralPurposeLOID class manipulates all of the LOID fields without enforcing any structure or special meaning to the fields.
The code for the make_loid() function is presented below (Example E) as a demonstration of how to build a general purpose LOID. The function takes a string which represents the object's class identifier and an integer which represents the object's instance number as its parameters. It builds a LOID which names an object in the domain UVaL_LegionDomain_Virginia (a library-defined constant), with class identifier and instance number assigned to the values passed as parameter, and with an empty public key. The function returns a LRef to a LegionLOID.
A Legion buffer, represented by the C++ object class LegionBuffer, is the fundamental data container in the Legion Library. Legionbuffer exports operations to read and write data from and to a logical buffer. Instances of different kinds of LegionBuffers export the same interface, and perform the same basic function, but can have different characteristics from one another. For example, one LegionBuffer may copy the data it contains into heap-allocated memory, another may maintain pointers to the data, and a third may read and write its data from and to a file. Further, LegionBuffers may choose to compress or encrypt data, or both. To define its characteristics, each LegionBuffer contains a LegionStorage, a LegionPacker, a LegionEncryptor, a LegionCompressor, and MetaData.
LegionStorage determines how data is stored. One type of LegionStorage provided in the Library is LegionStorageScat, which stores its data as a linked list of pointers to chunks that it allocates, or to maintain pointers to data "owned" by other parts of the Library. Another type is LegionStoragePersistent, which stores data in a file. Different LegionStorages have unique performance and operation characteristics. So, while it might be efficient to select a LegionStorageScat that does not copy its data extra care must be taken to avoid deleting data out from under the buffer, leaving dangling pointers.
Although LegionStorage exports functions in order to directly access a buffer's data (see page 95 in the Reference Manual), these functions typically should not be directly called by a LegionBuffer user. Instead, the user should call the functions in the interface provided by the LegionPacker portion of the LegionBuffer.
where zzz names a basic C++ data type (i.e. char, short, ushort, int, long, ulong, float, or double). Thus, a LegionPacker exports put_char(), get_char(), put_short(), get_short(), etc.; source points to an array of how_many instances of type zzz; and the put_zzz() function copies this data into the buffer after first performing the acceptable data conversion operation, if it is necessary for the type of LegionPacker that is instantiated. The get_zzz() function fills the complimentary role; first converting the data and then copying it into source.
The code example below (Example G) illustrates the use of the LegionPacker interface of a LegionBuffer. It also uses the seek() function--which is actually part of the LegionStorage interface (please see section 5.4.2 in the Reference Manual)--to "rewind" the logical position within the buffer back to the beginning.
A LegionCompressor determines the compression and decompression algorithms, if any, that are applied to the data. The Library currently provides only LegionCompressionDefault, which defines empty compression and decompression operations.
Eight bytes of metadata, three of which are currently used, are associated and carried with each LegionBuffer. The metadata indicates the format in which the data is stored, and the algorithms, if any, that were used to encrypt and/or compress the data. The metadata fields and values that are supported by the Library are defined in the Reference Manual ("LegionBuffer,").
LegionBuffers enable the concept of "packable" classes in the Library. A class is packable if it is derived from the abstract base class LegionPackable (not to be confused with LegionPacker), and therefore exports the following functions:
Both pack() and unpack() take a single reference parameter, which names a LegionBuffer. The pack() function of a packable class writes its state into the LegionBuffer so that the unpack() function of the same class can read it out. The state is typically written to and read from the buffer using the LegionPacker part of a LegionBuffer interface, which encapsulates the data format conversion operations.
Classes are made packable for two reasons: so that they can be passed between heterogeneous architectures within a LegionBuffer, and so that they can be written to a LegionBuffer as part of a "save state" operation. Since these two operations are common in the Library, many parts of the Library operate only on packable classes. For instance, many of the templated data structures are packable and require the ability to call the pack() member function of the contained data. Further, in a Legion object method invocation, each function parameter is passed within a LegionBuffer, so the easiest and best way to allow an object to be a parameter of a function is to make its class packable.
Making a class packable--implementing the pack() and unpack() functions for a class--is generally quite easy. The LegionBuffer exports storage operations for the primitive C++ types. For complex types, when class X contains an instance of another packable class (Y) X's pack() function can simply contain a call to Y's pack() function. Thus, if Y is packable X does not need to know the data types Y contains in order to pack Y as part of X's state. Consider the simple example of a templated array class, depicted in Example I. Note that the Array class can be made packable, even though it doesn't know the type of the elements it contains. Array only requires that the contained elements are themselves packable.
LegionBuffer is itself a packable class. Thus, one LegionBuffer can be contained (packed) in another. This is shown at the top of Example J. If data is packed as a LegionBuffer, it should be unpacked as one. Thus the data that was packed in Example J (top) cannot be unpacked correctly, using the code in Example J (middle). This code will compile and run, but it will not have the desired effect of unpacking the ten characters--Hello World--that were packed into the buffer. This is because LegionBuffers prepend "user data" with metadata. Therefore, hello_world_buf contains metadata at the beginning of the buffer, and between Hello and World. The correct way to unpack the data is shown in Example J (bottom).
LegionBuffers pack and unpack their bytes raw (without data format conversion), so that each buffer maintains its own meta-data. This means that a LegionBuffer created on an x86 architecture can be contained in a LegionBuffer whose data is in Alpha format. When the contained buffer is unpacked, a LegionBuffer with appropriate data conversion operations will be instantiated: when the bytes are read out, the data will wind up in the correct format for the architecture of the machine upon which the data resides.
Legion objects communicate with each other via method invocation and return values. To invoke methods and return results, Legion objects send messages to one another in a standard Legion message format. A Legion message can carry: (1) part (or all) of a method invocation, (2) the function return value that resulted from an invocation, or (3) a return value for an out or in/out parameter. Every Legion message contains, in order, source and destination LOIDs, a function identifier, the number of parameters to expect, a computational tag, a list of parameters, a continuation list, and an environment.
Computational tag: A single method invocation can be split up into several Legion messages, which can come from different sources (see "Legion program graphs"). A computation tag is a long integer, packed in the message sender's data format, that uniquely identifies a computation or method function invocation within Legion for the duration of the invocation's existence. The computational tag should be assigned by the invoker. Messages that carry function return values and filled-in out and in/out parameters should contain the same computational tag as the messages that carried out the invocation, which generated the results. The invoker matches the computation tag, when awaiting results.
Although a computational tag is simply a long integer, the Library provides a C++ class called LegionComputationTag that encapsulates the integer and exports appropriate functions on computational tags. The Library also provides a class called LegionComputationTagGenerator, which can be used to generate random computational tags. Typical use of these two classes is show in Example K.
Parameters to expect: This field should contain an integer, packed in the sender's data format, that indicates the total number of parameters being passed in the message function invocation. If the message is part of a return value, this field is ignored.
Parameter list: If the message is part of an invocation, the parameter list contains the values of the parameters contained in the message. The parameter list is packed as an integer that indicates how many parameters are present, followed by the parameters themselves. Each parameter contains an integer that indicates the number of the parameters, followed by a LegionBuffer that contains the value of the parameter. Return values are passed back in a parameter list as well. The C++ object classes LegionParameter and LegionParameterList implement parameters. The code in Example L builds a parameter list that contains two parameters, an integer, and a 14-element character string.
Continuation list: A continuation list describes the location to which the results of a particular computation should be forwarded. A continuation contains a computational tag and result number, which together identify a return value. It also contains the LOID, function identifier, and parameter number to which the result should be sent. The motivation for continuation lists arises from the macro data-flow programming model that is the initial Legion target. In this model, results from method invocations are sent directly to other invocations that use these results as parameters. These data dependencies are determined through analysis of the program code (see  for more information). LegionProgramGraphs are the representation of these data dependencies, and are described in section Legion program graphs. For further information, refer to the Legion on-line documentation at <http://legion.virginia.edu/>.
The LegionMessage class implements Legion messages in the Library. Its most useful constructor takes parameters that correspond to all of the constituent parts described above. Therefore an instance of LegionMessage can be created, as shown in Example M.
Each Legion object services requests for member function invocations and returns the results of these invocations. The parameters to these functions, as well as the requests themselves, arrive in Legion messages: a complete method invocation may involve composing a number of Legion messages. Conceptually, the Legion message database is divided into two parts. The "bottom" part, called the Legion Invocation Matcher, manages a list of partially complete method invocations for the Legion object: since messages may arrive from different locations and at different times, some parts of message will arrive before other parts. The "top" part of the database, the Legion Invocation Store, maintains two separate lists. The first list contains complete method invocations (i.e., requests with a complete parameter set and security clearance). The second list contains return values that the object has received as a result of its own method invocations on other Legion objects. Once a complete method invocation has been assembled, it becomes a Legion Work Unit, and is promoted to the Invocation Store.
Each object has a server loop that continuously checks the invocation store for ready work units, extracts them as they become available, and performs the requested invocation. A partial interface to the C++ class LegionInvocationStore is given in Example N.
Suppose Legion object A (the invoker) invokes a member function on Legion object B (the invokee). This method invocation proceeds through the invoker and invokee, as shown in Figure 16. The invoker builds a Legion message containing salient information about the member function invocation. Typically, the Legion program graph interface builds this message. The Legion message is then passed to the Legion message layer, which binds the LOID of the recipient to a particular address. The binding process is a key aspect of Legion, and is described in more detail elsewhere (see "The binding mechanism"). The outcome of the binding process is a <LOID, Legion Object Address> tuple called a binding. This represents the logical name and current physical address of the referenced object. The message and its binding are then passed to the data delivery layer, which linearizes the message for transport over the wire, uses the object address to create a physical connection to the referenced object, and sends the message.
On the receiving end, the data delivery layer of the destination object unpacks the data into a new instance of LegionMessage, and passes the message up to the message layer. The message layer then inserts this message into a Legion message database. When the return result reaches its destination, it is handled like any other Legion message until it reaches the Invocation Store, which examines the work unit's contents and realizes that it is a return result, not a method request. The result is then inserted into the return result list, and from there it is available to the original invoking object through the program graph interface
The Library is implemented as a configurable protocol stack. A layer of the stack communicates with other layers through an event mechanism. The basic idea is straightforward: if layer A wishes to communicate with layer B, A announces a LegionEvent. Each LegionEvent has a tag which denotes a LegionEventKind (what kind of event it is). Each LegionEventKind has one or more associated event handlers that may be called whenever an event of its kind is announced. Handlers for a particular LegionEventKind are given a priority to determine the order in which the handlers are called. Since a LegionEvent can carry arbitrary data, this is the method by which data is passed and transformed from layer to layer. If layer B has registered a handler for the kind of event that layer A announces, layer B will get that event. (See "Implementing the configurable protocol stack: events".)
The Library announces a MethodReady event each time a ready method invocation request is inserted into the invocation store. Each request is maintained as a Legion Work Unit. The general algorithm for getting a LegionWorkUnit out of the database and invoking its requested method is as follows:
For methods that have return results, these values must be sent to the list of objects defined in the LegionContinuationList part of the work unit from which the method invocation was constructed. The most straightforward way to do this is as follows: for each return result, allocate a new LegionBuffer and insert the return value into the buffer, then call Legion_return() with the buffer, continuation list, and number of the return value as arguments. This sequence is illustrated at the bottom of Example P.
A complete example of a C++ class, its translation into the appropriate Library calls, and some sample method invocations are give in the Reference Manual, starting on page 84.
A program graph represents a set of method invocations on Legion objects and the data dependencies between those invocations and objects. The program graph is a data-flow graph whose nodes represent method invocations and whose arcs represent data dependencies between the method invocations.
Suppose that objects A and B each export methods op1() and op2(). Figure 17 shows a simple user program and the resultant data dependencies. It is clear from the code that the parameters to both A.op1() and B.op1() are available locally. Those are the constant parameters. The parameters to A.op2() are not available locally, since they are the result of method invocations that have been executed elsewhere. These are the invocation parameters.
The most straightforward mechanism for making an invocation request is to build a program graph, using the interface provided by the C++ object class LegionProgramGraph. Salient parts of the LegionProgramGraph are given in Example Q. A fuller description of the interface constituents appears in the Reference Manual (page 92).
Start-up: The call to Legion.init() initializes various data structures in the Library. Legion.AcceptMethods() is called because the invoking object may itself be accepting member function requests from other objects.
Member function invocation: For each method, we use the object's local handle to create an invocation.2 We can then add the invocation to the program graph using add_invocation(). Every added invocation becomes a node in the program graph. To create arcs parameters must first be packaged into instances of LegionParameter (see Example L). Once packaged, they are added to the graph using add_constant_parameter(). Internal arcs in the graph must be handled differently, because they represent values that are not locally available--they have not been computed yet. Internal arcs are added using add_invocation_parameter(). Once a program graph is constructed, the execute() member function must be called. Calling execute() causes every node in the program graph to be packed up as a Legion message and shipped to the appropriate object for execution. Results from this remote execution then become available and are automatically sent to the objects that require them. In Example R, the return values from A.op1() and B.op1() are forwarded directly to A, so that they can become the parameters to A.op2().;
Example R: Sample user code (top left), the corresponding program graph (top right), and the library calls needed to implement it (bottom). In this case, make_parameter() takes an integer, wraps it up in a LegionBuffer, then wraps the buffer in a LegionParameter.
Return results: Getting return values that are results of method invocation requests is straightforward. The LegionProgramGraph class has a method called get_value(), which takes the parameter number of the result value as one of its arguments. If the result is unavailable get_value() will block. The constant UVaL_METHOD_RETURN_VALUE can be passed to get_value() to obtain the return value of the function call. By default, the return values of all method invocations are returned to the invoker. For in/out parameters, add_result_dependency() (not shown) must be used to explicitly ask for the parameter to be returned. This call must be made before execute() is called on the program graph that contains the associated method invocation. Otherwise the parameter will not be returned and a call to get_value() for that parameter will block indefinitely.
The template class LRef, in concert with the class LRefCntr, is the Library's mechanism for automatic reference counting and safe dynamic memory management. The mechanism is intended for heap allocated C++ objects. It keeps track of references to each object that is shared by different parts of the library and automatically deletes the object when all meaningful references to it have disappeared. Each reference counting object--i.e., each instance of a class derived from LRefCntr--maintains an integer that indicates the number of LRefs that point to that object. When a new reference is made to point to an object the reference count within that object automatically increases. When a LRef is overwritten with another value, or when a local variable LRef falls out of scope the reference count in the object to which the reference points automatically decreases. When the reference count falls to zero the object is automatically deleted. All of this happens without any intervention by the programmer or user of LRefs.
The decision to include an automatic reference counting mechanism in the Library was motivated by two observations: memory copies are expensive and often hinder the performance of message passing code, and keeping track of shared pointers and deciding which parts of the code are responsible for deleting which chunks of heap-allocated memory is prone to error and is difficult to document effectively. It is hoped that the automatic mechanism will combine the better performance that comes from avoiding memory copies with the safety and correctness that comes from not having to worry about managing dynamically allocated memory. Obviously, the automatic reference counting mechanism introduces some overhead when compared to simple pointer copies, but we believe that the benefits will outweigh the costs.
Just about every operator that is legal on a pointer to a C++ object has been overloaded to work correctly for LRef. Example S shows that LRef can be used just as C++ object pointers would be. The implementation of the MyRCO class in Example S is unimportant beyond the fact that it is derived from LRefCntr and implements the functions that are used to illustrate the point.
LRef can also refer to non-heap-allocated memory, i.e. global and local variables. To insure that these objects are not automatically explicitly deleted by the mechanism, the programmer should call the function makeNonHeapReference() on the reference.
Exceptions are a standard structuring mechanism for building distributed robust applications, as they provide a mechanism for error detection and recovery. As the name implies, an exception has the connotation of a rare event, an assumption that no longer holds true in a wide-area distributed system such as Legion. Examples of possible common exceptions in Legion include:
In designing an exception propagation model we follow the Legion minimalist philosophy of specifying mechanisms and not policies. Thus Legion emphasizes exception propagation and not exception handling. Our view is that exception handling is specific to a particular programming language and should not be part of Legion proper. Instead, Legion provides the mechanisms to enable a wide variety of exception handling models.
In Legion, the propagation of exceptions is specified in a generic manner with computation graphs (see "Legion program graphs"). Computation graphs can express a variety of exception handling policies, from traditional policies which propagate exceptions back to the caller (as in CORBA) to policies that propagate exceptions to third-party objects. Examples of the latter policy would be to propagate all security exceptions to a Security Monitor object or propagate all Communication errors to a Fault Detector object. For a detailed description of various policies please refer to "Building Robust Distributed Applications with Reflective Transformations" .
The Legion Library comes with default functions for the common case in which users want to propagate exceptions back to the caller. To raise an exception, users must first create an instance of LegionException. Exceptions are described by a Type field and a Subtype field.
LegionExceptionCatcherDefaultEnable() catches all exceptions and does not distinguish between types and subtypes. In (1), the application immediately terminates while in (2), the application can continue execution. Most of the Legion command line utilities use (1).
Interested readers may find an application of the Legion exception propagation model in the standard Legion distribution in the $LEGION/src/Examples directory. Furthermore, more complex policies are possible and are described in "Building Robust Distributed Applications with Reflective Transformations" .
The LegionLibraryState C++ object class provides an interface to important parts of an object's Legion-related state information. This includes the object's own LOID, the object's class LOID, and so on. LegionLibraryState also provides implementations of key object control mechanisms such as object creation, activation, deactivation and deletion. Finally, the LegionLibraryState interface provides the ClassOf() operation, which encapsulates the mechanism by which a given object's class LOID can be obtained via the object's LOID. We will now examine each of these general features of the LegionLibraryState class in more detail.
An object can use the LegionLibraryState interface to report to its class when it plans to delete itself, without having been requested to do so by the class. For example, an object before exiting could execute:
Beyond object control services, the LegionLibraryState class encapsulates the important Legion ClassOf() operation, which can be used to determine the LOID of a class object based on the LOID of one of its instances, or based on just a class identifier (that part of the LOID that indicates the object's class):
Unlike simple state accessors such as GetMyLOID(), object control methods such as CreateObject() and ClassOf() all result in Legion method invocations, and thus the cost of these member functions are non-trivial.
The layered design of the Library is depicted in Figure 18 (below). The client side (left) is the invoker, the code that is requesting a method invocation on some Legion object. The server side (right) is the invokee, the Legion object upon which the method invocation has been made. While it is convenient to think of the Library in terms of clients and servers it is also artificial, since full Library functionality is provided to both parties. In many cases, an object's role changes as execution progresses--sometimes clients are servers and sometime servers are clients.
As Figure 18 illustrates, the Legion protocol stack supports a variety of functions, in order to allow modules to be easily added and configured, an approach similar to that used in the x-Kernel . The problem with the traditional approach to building protocol stacks is that each layer in the stack explicitly calls the layer below or above. This static coupling makes it difficult to dynamically configure the stack.
To provide a dynamically configurable stack, then, we have chosen a well understood technology--events --and have applied it to allow flexibility and extensibility. Four main classes implement events: LegionEventManager, LegionEventKind, LegionEvent, and LegionEventHandler. When an event occurs, the system announces an event to an Event Manager, which is an instance of class LegionEventManager. The event manager notifies interested parties (i.e., Legion Event Handlers) of the event: this can be done immediately, or at a later time.
Event handlers register themselves with a Legion Event Kind, an event template that contains a unique tag and a default list of handlers, in order to be notified of an event. Since there may be more than one event handler per event kind, a handler is given a priority when registering. In the current scheme, a handler with a lower priority number is executed before a handler with a higher number. Not all event handlers associated with a LegionEvent are guaranteed to be executed, since an event handler is allowed to prevent the execution of subsequent handlers.
The class LegionEventKind serves as a template for instance of class LegionEvent (Example U). When an event is created it obtains a list of LegionEventHandlers from its corresponding LegionEventKind. This allows users to modify the behavior of the protocol stack without having to change existing modules. To enable interlayer communication, Legion events may also carry arbitrary data, which can be updated, modified, and transformed in arbitrary ways by the event handlers processing each events.
A Legion event handler takes a reference to the LegionEvent that it is servicing as its sole argument. Thus, each LegionEventHandler associated with a particular LegionEvent may inspect and modify the data carried by the LegionEvent. In general, this is how information is shared between various LegionEventHandlers.
Users may add LegionEventHandlers to a LegionEventKind. When a LegionEvent is created, it obtains its unique event identifier and a list of suitable LegionEventHandlers from its corresponding LegionEventKind. LegionEventHandlers are ordered, and the handler with the lowest priority are executed first. An example of an event handler is in Example V.
A Legion event maintains a logical pointer to the currently executing LegionEventHandler. This allows the event to suspend the execution of its event handlers and to resume that execution at a later time.
When users wish to notify the system that something of interest has occurred, they must announce a LegionEvent to a LegionEventManager (Example W). The LegionEventManager is responsible for deciding when to execute the handlers associated with an event. In the current implementation, there are two ways to announce events to an event manager: depending on the chosen method, the event manager will either invoke the handlers immediately or will defer the execution of the event handler and store the LegionEvent in an internal queue. The available methods are: the flushEvents() method, used to execute all pending events; the blockForEventAvailable() method, used to block the thread of control until there are some pending events available; and the serverLoop() method, which repeatedly calls blockForEventAvailable(), followed by flushEvents().
On the sending side, the program graph layer generates a LegionEvent_MethodSend event. The security handler LegionEvent_Can_I may disallow the remote method invocation . If it doesn't, a following handler generates a LegionEvent_Message-Send event for each method invocation. Once the message has been successfully sent, the data delivery layer generates a LegionEvent_MessageComplete event.
On the receiving side, the data delivery layer will generate a LegionEvent_MessageReceive once it has successfully assembled a complete message. The LegionDefaultMessageHandler is the last handler for the event LegionEvent_MessageReceive and generates a LegionEvent_MethodReceive, once the invocation matcher has assembled a complete method invocation. The first handler for LegionEvent_MethodReceive is a security handler, and it implements access control on this object . If the security handler grants access, the method invocation is deposited into the LegionInvocationStore, and a LegionEvent_MethodReady event is generated.
Here, a user can add a security layer to encrypt outgoing messages and decrypt incoming messages. We first define the handlers encryptionHandler() and decryptionHandler(), and register them with the appropriate LegionEventKind (Example X).
For encryption, we would like the encryption handler to be the last handler called when sending a message. For decryption, on the other hand, we need to call the decryption handler first when a message is received. These ordering constraints are realized by registering encryptionHandler() with a high priority number and decryptionHandler() with a low priority number. The new protocol stack is shown in Figure 19.
The active messages programming model  is a message passing scheme that is intended to integrate communication and computation in order to increase the compute/communicate overlap, thereby masking the latency of message passing and increased performance. The basic idea behind active messages is simple: messages are prepended with the address of a handler routine that is automatically invoked upon receipt of the message. Active messages are not buffered and explicitly received, as is common with standard message passing interfaces. Instead, the receiving process invokes the handler routine specified for the message immediately upon message arrival. The handler may execute as a new thread of control, or may interrupt the running computation. The job of the active message handler is to incorporate the received message into the on-going computation.
A Legion version of active messages could be constructed by making Legion methods serve as message handlers, and by replacing the Legion "method ready" event handler with one that creates a new thread to service incoming methods, instead of buffering them in an invocation store. Pseudo-code for such a method invocation handler is given in Example Y.
The effect of this new method ready event handler is to provide an active messages style programming model. In some ways, the model supported here is more general than the traditional active messages model. For example, if a method (i.e., a handler) required two messages from different sources for activation, this requirement would be enforced by the Legion invocation matcher. Programs might be entirely composed of standard single-token active messages, providing a programming model as flexible as the original. On the other hand, programs might also include multi-token active messages, for a more general programming model that might best be called "active methods."
The various method invocation semantics covered thus far have offered a "one size fits all" concurrency control mechanism. For example, the supported remote procedure call model allows exactly one method to be serviced at a time by a given object. The active messages approach, on the other hand, allows any number of operations of all types to be active at the same time in the same object. A more general approach to customizing the concurrency control requirements of operations on an object can be designed based on path expressions . Path expressions permit the programmer to specify: (1) sequencing constraints among operations; (2) selection (mutual exclusion) between operations; and (3) allowable concurrency between operations. These concurrency control primitives let programmers maintain the sequential consistency of their programs and at the same time indicate potential concurrency to a run-time environment.
Path expression based method sequence could be implemented for Legion objects, again by utilizing the inherent configurability of the Library's protocol stack. As with active messages, supporting a different method invocation semantic requires replacing the Legion method ready event handler. In this case, the method ready handler must examine the function identifiers of available operations and determine if they may be safely fired, given the ordering constraints specified by the program's path expressions. If a method can be safely fired, a new thread is created and allowed to run, starting at the entry point for the given member function (as in the active messages case). On the other hand, if the ordering constraints of a newly arrived method are not satisfied, the method must be buffered (e.g. in a library-provided invocation store) and later extracted and fired, when safe. This need to defer the firing of methods requires that code be executed whenever methods complete execution. One possible way to satisfy this requirement is to use LegionEvent_MethodDone event kind, and announce events of this kind when methods complete execution. A handler for this event kind can then be used to re-evaluate buffered methods with respect to the path expression ordering constraints whenever a running operation completes.
To examine the implementation of the scheme in more detail, we assume a path expression run-time support class, PathExpressionManager, that exports methods to specify the ordering, selection, and sequencing constraints of operations (i.e., Legion method function identifiers). This class would also support methods to determine if a given method is safe to fire, and to determine which (if any) methods are ready to be fired upon the completion of a running operation. The first modification we must make to the Library configuration is to add a new method event handler that might look like that of Example Z.
This method handler would need to be registered with the Legion method ready event kind, as in the case of the active messages handler. This method handler would need to be registered with the Legion method ready event kind, as in the case of the active message handler. The other requirement of our path expression solution is that code be executed upon method completion in order to re-evaluate the safety of firing buffered methods. To accomplish this, we use method done events that must be announced whenever a method is finished running. A handler (Example AA) must be registered with the LegionEvent_MethodDone event kind that tries to fire any runnable buffered methods.
Finally, an event of this type would need to be announced upon the completion of each method by the object. The data for this event would need to be set to reflect the function identifier of the completed method.
The result of this configuration of the Library would be a run-time environment that could be used to support path expression style method invocation semantics. This run-time system might be used explicitly by a programmer, or might be the target of a compiler that accepted a Path-Pascal-like implementation language for Legion methods.
Thus far, the programming models we have examined have been variations of an object-based method-invocation-oriented model. This is natural, given the object oriented nature of the Legion system. However, Legion can support alternative programming models, such as message passing or distributed shared memory. In this section, we examine the ways in which the Legion library can be configured to support a message passing model. We describe how Legion can be used as run-time support to implement a message-passing interface such as MPI  or PVM  (see page 33 for information about the Legion PVM library and page 37 for information about the Legion MPI library in the Basic User Manual). These systems allow asynchronous send and receive operations. Messages are buffered until explicitly requested at the receiving process, and send operations are permitted to return before the destination process has received the message.
One possible implementation of such a message passing system would be to construct a message passing Legion base class which exports a single messageDeliver() method. The parameters to this method could be an integer message tag and an uninterpreted string of bytes containing the message. The operation of the send() library function would simply involve invoking the messageDeliver() Legion method on the intended destination LOID. The implementation of the messageDeliver() Legion method would accept and buffer the received message in an internal message queue. The receive() library function would then consist of a loop that could check the message queue for the desired message tag, dequeue and return it if available, or block for a messageDeliver() invocation if not.
Although the above solution is simple to implement, using the available library support mechanism, it has the potential drawback of incurring the cost of the mechanism associated with method invocation (e.g., token matching, additional event handlers, etc.) while only requiring support for message passing. An alternative implementation strategy is to insert a handler lower in the Legion Library protocol stack. The natural place for such a message passing handler would be at the Legion message receive event layer. Here, a handler could be inserted to capture a message with certain desired function identifiers (i.e., a special "message passing" function identifier), and enqueue the message contents on a message queue for use by the message passing library. Message with other function identifiers (those associated with object mandatory methods , for example) would be allowed to continue up the protocol stack and through the normal method invocation mechanism. In this scheme, the send() library operation would construct a LegionMessage object containing the message contents and reflecting the appropriate agreed upon function identifier. This Legion message would be added to a LegionMessageEventStructure, which would be placed into a new LegionEvent of the kind LegionEvent_MessageSend. This event would be announced and the message would be sent. The receive() operation would simply loop, examining the message queue utilized by the message receive handler described above, and blocking for available events. Thus, the overhead of the standard Legion method invocation mechanism is avoided for low-level message passing traffic.
Although this scheme could improve performance, it has serious security ramifications. If messages are caught before the token matching process, the automatic MayI() method will not be invoked and the object's security may be compromised. While this may be acceptable for certain performance-critical, security-optional applications, the first message passing implementation described would be more suitable for balanced security/performance applications.
1. We have also developed implementations of PVM (see section 9.0 in the Basic User Manual) and MPI (see section 10.0 in the Basic User Manual) layered on top of the LRTL, and we currently support a Java interface to the LRTL and a specialized programming interface for Fortran called Basic Fortran Support (BFS; see section 4.0). Back
2. A Legion invocation identifies a particular invocation on one of an object's member functions. An invocation is obtained through a Legion Core Handle. Core handles export functions that allow programmers to ask for invocations and to obtain a description of the corresponding object's interface. A handle can be thought of as a local representation of an object and as a generator of invocations for that object. Back