Compiling Distributed C++

Compiling Distributed C++ Harold Carr, Robert R. Kessler, Mark Swanson Department of Computer Science University of Utah Salt Lake City, Utah, 84112 Abstract Distributed C++ (DC++) is a language for writ- ing parallel applications on loosely coupled distributed systems in C++. Its key idea is to extend the C++ class into 3 categories: gateway classes which act as communication and synchronization entry points be- tween abstmct processors, classes whose instances ma y be passed by value between abstract processors via gate- ways, and vanilla C++ classes. DC++ code is com- piled to C++ code with calls to the DC++ runtime system. The DC++ compiler wmps gateway classes with handle classes so that remote procedure calls are transparent. It adds static variables to value classes and produces code which is used to marshal and un- marshal arguments when these value classes are used in remote procedure calls. Value classes are deep copied and preserve structure sharing. This paper shows DC++ compilation and performance. 1 Introduction DC++ is designed to exploit loosely coupled dis- tributed systems built by interconnecting multiple workstations through a local area network. DC++ is a distributed version of C++ [8] (th’ is paper assumes knowledge of C++). DC++ provides a small num- ber of simple extensions to C++: 2 built-in classes: DcDomain and DcThread; and 2 new categories of class instance usage: gateways between domains, and “value” instances which may be passed between do- mains through gateway member function invocation and return. The DC++ language is discussed in [6,5]. This paper shows how DC++ is compiled. We will use the bounded buffer problem [l] as a running example throughout this paper. We include performance mea- surements for this example. 2 Domains - Abstract Processors DC++ supports parallelism by providing 2 types: domains and threads ([13, 171). A domain is a logi- cally encapsulated address and control space, an ab- stract processor. A domain is similar to a monitor [ll]: they ensure mutual exclusion synchronization by en- forcing the rule that only one thread of control may be active in a domain at a time. If another thread at- tempts entry to an occupied domain, that thread will be queued on a FIFO queue for later entry when the domain becomes vacant. It differs from a monitor in that domains may be dynamically created and deleted. Further, a domain by itself does not have any entry points. Entry points may be dynamically created and deleted by creating gateway class instances into d* mains. A domain is created by specifying a physical processor number (@based) on which to allocate the domain. For the bounded buffer example we will cre- ate 6 domains: one each for the 3 producers, one for the buffer, and one each for 2 consumers: const nun-producers = 3; const num-consumers = 2; DcDomain+ pd[num-producersl; DcDomain* cd[num-consumers] ; DcDomainr bd = new DcDomain(num-producers + nu-consumers) ; for (int i = 0; i < nul-producers: ++i) for (i = 0 ; i < nu.-consumers; ++i) pd[i] = new DcDomain(i1; cdci] = new DcDorain(i + nun-producers); Since there may be more domains than actual phys- ical processors, the domain is allocated on i X DcNodeCount (1, where DcNodeCount (1 returns the 1- based number of physical processors available to the specific execution. This means that more than one d e main may be explicitly (by the programmer) or implic- itly (by the domain allocator) created on a processor. The DC++ runtime system supports multitasking so the programmer need not be concerned with these de- tails. 496 1063-6374/93 $03.00 0 1993 IEEE 3 Gateways - Domain Entry Points A gateway is a system-wide unique “pointer” to an object created in a specific domain. I t is treated as an ordinary C++ object: member function invoca- tions on gateway objects result in remote procedure calls (RPCs) if that gateway resides in a different do- main than the domain from which it is invoked. Oth- erwise a vanilla C++ member function invocation re- sults. Since RPCs look identical to vanilla C++ mem- ber function invocations, redistribution of gateways is possible without program modification (modulo syn- chronization characteristics of the algorithm). A gateway class is declared like a vanilla C++ class, except it inherits from DcGateway: class Producer : public DcGateway { int Bufferr buffer; public: Producer(int i, Buffer* b) { nu.-items * i, buffer = b; 1 void Produce0 { num-items; // Number items to produce. // Buffer to put them in. while (num,items--) { 1 buffer->Deposit(new Derived(num,items)); 1 1: class Buffer : public DcGateway { unsigned max-items; // Capacity of buffer. Derived** slots; // Array to contain items. unsigned head; // Where producer puts items. unsigned tail; // Where consumer gets items. unsigned size; // lumber of items in buffer. Buffer(int i){ pub1 ic : head = tail = size = 0; .ax-items = i; slots = new Derived*[max-items] ; MakeDelayQueue(Buffer: :Deposit) ; DQOpen(Buffer: :Deposit) ; MakeDelayQueue(Buffer::Fetch); 1 void Deposit (Derived* i) { slotsCtail] = i; size++; tail - (tail + 1) X max-items; if (size > 0) DQOpen(Buffer: :Fetch) ; 1 Derived* Fetch(){ Derived* retval = slotsChead] ; size-- ; head = (head + 1) % rax-items; if (size < rax-items) DQOpen(Buffer: :Deposit) ; return retval ; 1 1 : class Consumer : public DcGateway int num-items; // Number items to consume. Buffer* buffer; // Buffer to get them from. Consumer(int i, Buffer* b) { nu-items = i, buffer = b; void Consume 0 { public : 1 while (num-item--) { Derived* i = buffer->FetchO ; if (i->DataO == 0) spin0 ; return; 3 1 1: The buffer has explicit delay queues associated with its Deposit and Fetch methods. Delay queues provide condition synchronization. If the delay queue is open, calls to the method proceed as normal. If the delay queue is closed then the calls are queued on a FIFO queue for later entry to the method when the queue is opened. A call (thread) waiting on a method’s delay queue is not considered to have entered the domain. They are used in this example to ensure that producers only deposit items when there is room in the buffer, and that consumers only fetch items when there is one or more available. A gateway instance is created in a specific domain by providing an optional domain argument as the first argument to the gateway’s constructor. If not present the current domain is used: Buffer* b = new Buffer(bd, 8) ; Producer* p[num-producers] ; Consumer* c [nu-consumers] ; for (i = 0; i < nu.-producers; ++i) for (i = 0; i < nu.-consumers; ++i) pci] = new Producer(pd[i], 25, b); c[i] = new Consumer(cdCi], 25, b); Note that the type passed between the producer, buffer and consumer is Derived*. This type is a user defined “value” class and will be discussed later. Also note that the optional domain argument is not de- clared in the user’s gateway class definition. This is handled by the compiler. 4 Threads Concurrency is achieved by creating multiple threads of control. In the bounded buffer example, 497 threads are created for the producers and consumers, whereas the buffer is passively enclosed in a domain void Deposit (Derived* ; Derived* Fetch0 ; to ensure mutually exclusive access to it: 3; for (i = 0 ; i < nu-consumers; ++i) for (i = 0; i < num-producers; ++i) nev DcThread(cCil->ConsumeO) : new DcThread(p[i]->Produce~)) ; For each constructor in the user class, 2 constructors are created in the handle class: one with a type signa- ture identical to the user's definition, and one which adds a domain argument as the first parameter. In this way gateways may be created in the same domain or between domains. The handle class inherits from gateway, whose def- inition is: Threads may return values when they terminate. These values may be used by the thread which created the new thread, and/or the termination of the created thread may be detected by the creating thread. This feature is not used in this example. 5 Compiling Gateways The fundamental idea is to transform the program so that all references to user defined gateway classes are changed to references to compiler generated han- dle classes. Each user gateway class has an associated handle class which intercepts all method invocations. The handle class determines if the gateway method being invoked is for an instance in the same domain as the invoker. If so, it does a normal C++ method invocation. Otherwise, it marshals the arguments and does an RPC to the domain in which the gateway re- sides. Upon return it unmarshals the return value. The compiler generated handle class frees the pro- grammer from these details and allows gateways to be redistributed without program modification. This section shows the details of the gateway compilation process. class gateway { private : DcDomaine domain; DcObject* remote; // remote object void* local; // local object DcDomaint dorainGid0 { return domain; 1 DcObjectt remoteObj0 { return remote; 3 void* local0bjO { return local; 1 void* localPO { return local; 3 gateway(void* v) : domain(NULL), remote(WULL), local(v) gateway(DcDomain* did, DcObjectz oid) : domain(did1, remote(oid1, local(HULL) {1 // domain vhere object lives protected: 1; When creating objects derived from gateway, a gate- way is returned which either points to an instance in the domain or to an instance in a remote domain. When the handle class constructor is given an optional domain it constructs the actual object on a remote node via the compiler generated MakeRemoteOb ject routine: A unique tag is created for all gateway classes in a DcObject+ nakeRe.oteObject(unsigned type){ program: void* v = NULL; enum CLASS-TAGS { Consumer-TAG, Buffer-TAG, Producer-TAG, 1; These tags are used to indicate the type of object being made when that object is created remotely. Each user gateway class is wrapped by a handle class: class Buffer-U : public gateway { public: Buffer-U(int i) Buff er-U (DcDomain* d. int i) : gatewayhew Buffer(i1) C1 switch (type) { case Consumer-TAG : case Buffer-TAG : case Producer-TAG : default : break ; 3 return Registerobject (v, DcThisDomainO) ; v = new Consumer; break; v = new Buffer; break; v = new Producer; break: DcError ("Unknown object type") : 3 Registerobject is a DC++ runtime system routine which places the actual pointer to the newly created - . : gateway(d, object into an OutTable table, a table of entities which may be used remotely. It returns a DcObject* which is a special pointer type which is unique and valid MakeRemoteObject(Buffer-TAG, d, i)) C3 498 between domains. The bits of this pointer indicate the node on which the object resides and the index of the actual object pointer in that node’s OutTable table. This example is incomplete in that it doesn’t show how arguments to constructors are handled remotely, and it only shows one constructor per class. If there is more than one constructor they are distinguished by their type signature. Constructor arguments are handled in a manner similar to arguments to methods (shown below). A tag is created for each public method in the han- dle class (constructor tags not shown in example): enum BufferPTR-METHOD,TAGS { DerivedptrBufferFetch-TAG, VoidBufferDepositDerivedptr-TAG, 3 ; For each method in the user’s original gateway def- inition an associated method is defined in the handle class: void Buff er-U: :Deposit (Derived* a3) { if (1ocalP 0 ) HsgBuf Id f = HakeHsgBuf(100) ; SetHsgBuf (f , 0, remoteobj 0 ; SetHsgBuf(f, 1, voidBufferDepositDerivedptr-TAG); PACK-voidBufferDepoaitDerivedptr-PAMS(f, Oa3); ApplyYithinDomain(REHOTE-Buffer-HANDLER, DeleteMsgM (f ; return ((Buffer-U*)localObj O)->Deposit(aJ) ; f , domainGid0 ; 3 Derived* Buffer-Y::FetchO{ if (localPO 1 HsgBufId f = HakeHsgBuf (2) ; SetHsgBuf (f , 0, remoteobj 0 ) ; SetHsgBuf (f , 1, DerivedptrBuff erFetch-TAG) ; HsgBufId fr = (MsgBufId) return ((Buff er-U*)localObj 0 ) ->Fetch0 ; ApplyUithinDomain(REH0TE-Buffer-HANDLER, f, domainGid0 1 ; DeleteHsgBuf (f) ; Derived* result; UNPACK-DerivedptrBuff erFetch-RETVAL (f r , &result) ; DeleteHsgBuf (fr) ; return result; 3 These handle methods are how transparent RPCs are method. Otherwise it marshals the remote object ref- erence, the method tag, any arguments, and then calls the RPC handler in the domain for that handle class via ApplyVithinDomain. ApplyVithinDomain is the blocking remote procedure call routine in the DC++ runtime system. When the RPC returns, it unmar- shals the return value into a message buffer. The o p eration of compiler generated PACK and UNPACK mar- shaling routines is discussed later. They use runtime message buffers (MsgBuf Id) to contain object refer- ences, method tags, argument values, and return val- A remote method handler is created for each handle class. The method tags are used to dispatch to the appropriate method when handling RPCs: ues. void* REMOTE-Buffer-HANDLER(HsgBufId f) < Buff er* r = (Buff er*) OutTable (HsgBuf (f , 0) ; Buff erPTR-METHOD-TAGS 1 = MsgBuf (f , 1) ; suitch (1) { case DerivedptrBufferFetch-TAG : { DeleteHsgBuf (f) ; Derived* a4 = r->Fetch(); HsgBuf Id fr = return (void*) fr; PACK-Der ivedpt rBuf f erFet ch-RETVAL (&a4) ; 3 case voidBufferDepositDerivedptr-TAG : { DeleteHsgBuf (f ; Derived* a3; UNPACK-VoidBufferDepositDerivedptr-PARW(f, r->Deposit (a31 ; return NULL; Oa3) ; 3 default : 3 DcError (“Unknown method”) ; 3 This routine dispatches to the appropriate method call, marshals the arguments from the message buffer and calls the associated user operation. Return values are placed in a message buffer to be used on the other end of the RPC. 6 Value Objects Systems such as [2] provide primitives for send- ing and receiving data between processes, but require the programmer to pack and unpack aggregate data. Besides the gateway classes, which marshal and un- marshal arguments and return values, DC++ pro- vides “value” classes so that programs may pass deep, achieved. If a Buff er handle instance is created in the same domain as the invoker of its constructor then a pointer to that local object is installed in the gate- way’s local method variable. When a handle method is invoked it first checks to see if the object is local. If so it avoids the overhead of RPC by invoking the local 499 structure-preserving copies of value class instances be- tween domains. A value object is a class which inherits from the built-in DC++ class DcValue: class Base : public DcValue { publ ic : int data; Base(int i = 0 ) : data(i) { 1 int Data0 { return data; 3 3 ; class Contained : public DcValue { public: char c; Contained(char -c = lt') : c(-c) 3 1; class Derived : public Base { Contained mi, *mpl, *mp2; double d; Derived(int -i = 0, publ ic : double -d = 0 . 0 , char cl = 'U,, char c2 = ' x ' ) : Base(-i), mi(c1). d(-d), mpl (neu Contained(c2) 1 , mp2(mpl) C 1 -Derived() { delete mpl; 3 3 ; (Note that member data mpi and mp2 point to the same instance.) Inheriting from DcValue indicates that when one of these objects is passed as an argument to, or re- turn value from a gateway member function, it is to be totally copied. This means that any objects, point- ers to objects, or built-in data types contained within the passed object, must be recursively copied and any structure sharing present via pointers must be pre- served. Any member data objects or member data pointers to objects, must be objects which also derive from DcValue so the compiler can add the necessary support for the complete copy operation. The com- piler handles C++ scalar types automatically. Value objects may be passed-by-value freely be- tween domains via gateway member function argu- ments and return values. This is seen in the exam- ple by the calls to the Buffer methods Deposit and Fetch which accept and return instances of the user defined Derived class. These routines actually pass and return Derived*. In this case, the object is still copied and the pointer to the newly created object on the receiving end is used rather than the original pointer. 7 Compiling Value Objects 7.1 Runtime Type Information The compiler adds static variables and virtual func- tions to each user class which inherits from DcValue: class Base : public DcValue { DECLARE-TYPE(Base) ; int data; Base(int i = 0) : data(i) C 1 int Data0 { return data; 3 publ ic : 3; The DECLARE-TYPE macro: #def ine DECLARE-TYPE ha") \ public: \ virtual const TypeInfot Type0 const \ { return kinfo-obj; > \ static const TypeInfor Info0 \ { return &info-obj; 3 \ virtual void Uriter(ostream&) const ; \ static DcValue* Reader(istream&) ; \ static name* Read(istream& s) \ name (istred) ; \ static const TypeInfo info-obj \ { return (name*)DcValue::Read(s); 3 \ private: ', defines Type and Info methods used to obtain type in- formation at runtime. This information is contained in the private static member data info-obj. Type is used to get this information given any instance which derives from DcValue (e.g., someinstance->Type( 1). Info is used to get this information if the type is known before hand (e.g., Base: :Info()). These are used to obtain typespecific reader functions used when sending objects between domains. 7.2 Sending Objects Over Streams The Uriter, Reader, Read methods and the name(istream&) constructor are used to convert ob- jects to/from linear byte streams for transmission and reception between domains. The compiler generates these for each type that directly or indirectly inherits from DcValue: DEFIIE-TYPE(Base) ; DEFINE-TYPE(Contained); DEFINE-TYPE(Derived); The DEFINE-TYPE macro: #define DEFINE-TYPE(name) \ DcValue* name: :Reader(istream& 8 ) \ 500 { return new name(s); I \ name : :Reader) \ const TypeInfo name: : inf o-obj (STRIIGIFY (name) , \ defines the Reader method which uses the constructor from istream to create an instance of the class given a linear stream of bytes. It also initializes the static info-obj method data to contain the name of the class and a pointer to the class reader. The compiler generates a Writer method and an istream constructor for each value class: Base::Base(istream& s) : DcValueb) { I void Base::Uriter(ostred s) const s << data << endl; 1 Contained::Contained(istream& s) : DcValue (s) { s >> data; s >> c; 1 void Contained::Uriter(ostream& 8 ) const 1 1 Derived: :Derived(istream& s) s << c << endl; : Base(s) , Bib), mpl (Contained: :Read(s) 1, mp2(Contained: :Read(s)) s >> d; I void Derived::Uriter(ostrem& s) const { Base: :Uriter(s); mi.Uriter(s) ; mpl->Urite(s) ; ~p2->Urite(s) ; s << d << endl; I Derived types first call the static Writer for their base classes (only one in this example). Then they write out instances using the Writer method of the instance. Pointers to instances are written using the Write method. Write keeps a table of pointers to pre- serve structure sharing. Built-in data types are writ- ten and read to and from a stream with the normal C++ iostream operators. Data is written and read in identical order. 7.3 Argument Marshaling The compiler generated Buff er-U: :Deposit method receives a Derived* as an argument. It con- verts this to a linear byte stream via the generated PACK-voidBuf f erDepositDerivedptr9ARMS routine. This routine uses the write operations to write into an output string st