| Abstract |
Linda is an easy-to-use language for parallel programming; it is not based on shared variables or message passing, but it uses a novel communication mechanism called the tuple space. It supports (but does not enforce) a programming methodology based on distributed data structures and replicated workers. The goal of this methodology is to release the programmer from thinking in terms of parallel computations and simultaneous events, hence making parallel programming conceptually similar to sequential programming. POSYBL is a Linda implementation for Unix networks. We decided to extend this work by optimizing the various components of POSYBL. The first step was to improve the network communication between the various processes that take part in the POSYBL program. Network communication is expensive, and the available protocols that the UNIX operating system offers are not suitable for asynchronous reliable message passing between network nodes. We developed our own protocol which is a subset of the VMTP protocol used in the V distributed kernel. The second step was to design and implement an efficient protocol for asynchronous message passing between processes on the same node. For this reason we implemented a protocol that uses shared memory to transfer data between processes, and message queues for the synchronization of the shared memory accesses. The final step was the optimization of the search, distribution and storage of tuples in the tuple space. Regarding storage, a hashing algorithm that uses hashing at two levels was developed. The first level is used to segment the tuple space in orthogonal segments based on the tuple fields. The second level is used for the indexing of tuples in each segment. For the distribution of tuples, statistical information is used to discover the communication pattern of the POSYBL program. This information can be used to avoid unnecessary network traffic. This is achieved by sending the tuples directly to the node that is most likely to search for them. Using the experience of this design, we developed ISTOS Linda. ISTOS Linda is a Linda implementation on a distributed memory parallel machine based on the transputer architecture and the PARIX operating system. Furthermore, a simulator of ISTOS was developed for Sun Workstations using the Sun LWP package. ISTOS uses distributed hashing to distribute the tuples between the nodes of the parallel machine. We have also developed a precompiler that translates the Linda calls to run time library calls. ISTOS is a full implementation of the Linda model. It is a useful and reliable programming tool that can be used for educational and research purposes.
|
Σχεδιασμός και Υλοποίηση του Μοντέλου LINDA σε Μηχανές Κατανεμημένης Μνήμης
