Distributed simulation language modelled after SIMCAL but written as a preprocessor to C++

Related languages
SIMCAL => ARACHNE   Influence

  • Dimitrov, Bozhidar "ARACHNE: A COMPILER-BASED PORTABLE THREADS ARCHITECTURE SUPPORTING MIGRATION ON HETEROGENEOUS NETWORKED SYSTEMS" MSc view details Abstract: Since the early 1980s, a large variety of distributed programming environments have been developed and used. These mostly run on homogeneous or heterogeneous computer clusters that decompose the problem in some way and then work in parallel on distinct portions of the data. If a thread requires access to remote data, the data is sent over the network. On such systems, speedup is a direct result of data parallelism.

    In recent years, another paradigm has been explored--migrating computations to the data instead of migrating data to computations. Obviously, depending on the size of the data and the thread's state, this method may be more efficient in its use of network bandwidth and may yield even greater speedups. In addition, migrating computations allows for simplified program development, load balancing, and dynamic changes of the network topology. Arachne explores this paradigm.

    2 1.2 Related Work

    There exist many threads systems capable of thread migration on homogeneous architectures. In general, these are runtime-only systems that in some form or another are based on the C language library routines setjmp() and longjmp(). Basically, migration is accomplished by copying the local machine stack to some remote machine and then restarting the computation. Examples of such systems are Ariadne [MR96] and Pthreads [IEE95, Mue92].

    Because the contents of a machine stack are meaningless across hardware platforms, some help is needed in interpreting the sequence of binary digits. At the very least, we need information about the types of the data stored on the stack, and one obvious way of obtaining it is using a compiler or a code preprocessor.

    The underlying idea behind Arachne is based on work done by Malloy and Soffa in [MS90]. By augmenting the recursive language Pascal with some Simula control structures, the authors defined the language SimCal. They then developed a preprocessor that accepts SimCal input and produces Pascal output. The preprocessor's main job is to extract all local variables of a function f() into a global record specific to f(). The preprocessor also produces a new version of f() that accesses its local variables through a pointer to this global record. In addition to all local variables, every such record contains an integer field state, used as a simple "program counter." The preprocessor's duties also include the insertion of a series of labels and goto statements. As the preprocessed function executes, the value of state is incremented each time a label is reached. Thus if f() is suspended at exactly one of these labels (using a return statement, for example), the contents of f()'s global record completely describe the function's computational state. If f() is restarted at some later time, it can continue execution as if it had not been interrupted. Since these "suspension" points are well-known, the process of building the record, inserting the labels and incrementing state is fully automated.

    3 In a project called Ythreads, Sang extended the above idea to facilitate heterogeneous migration [San94]. Since the state of a function is described as a global struct and the types of all data fields are known, it is possible to generate a platformindependent representation of that state, migrate it, and restart the computation on a different machine



    An alternative to writing a preprocessor for an existing language is creating an entirely new compiler or inventing a new language. A group of researchers at the University of Copenhagen have developed their own compiler for the Emerald language that produces native code for Sun 3, Sun SPARC, VAX and HP machines. Just before statements causing migration, the compiler inserts code to pack all local variable values, and thus allows threads and objects to freely migrate between these four architectures [SJ95]. However, in addition to having to learn a new language and having to port an entire compiler to the different architectures, the authors found 60% longer times for migrating and subsequently invoking a function through code generated by their compiler as compared to the original Emerald compiler.