Yali : uma extensão do modelo linda para programação paralela em redes heterogêneas

Abstract

Com a disponibilidade de redes que ligam estações cada vez mais poderosas a baixos custos, o interesse em torno de ferramentas que suportam a programação paralela em arquiteturas deste tipo tem aumentado significativamente. Esta dissertação trata do projeto e implementação de YALI (Yet Another Linda Implementation), uma ferramenta destinada ao desenvolvimento e execução de programas paralelos em redes heterogêneas de computadores. Com o objetivo de oferecer uma interface simples e flexível para os usuários programadores, YALI baseia-se no modelo Linda[GEL85], que destaca-se por utilizar uma abstração de alto nível para a cooperação entre processos. Em Linda, processos interagem por intermédio de uma memória associativa logicamente compartilhada, denominada Espaço de Tuplas. Entre outras vantagens deste modelo pode-se citar a simplicidade de suas primitivas e a possibilidade de incorporá-las a uma linguagem seqüencial conhecida, o que contribui fortemente para sua fácil assimilação, mesmo por usuários com pouca experiência em programação paralela. Após uma descrição detalhada do modelo Linda, este trabalho discute varias questões envolvidas no projeto e implementação de sistemas nele baseados. Para oferecer uma visão pratica das soluções mais freqüentemente adotadas para estas questões, quatro sistemas que implementam o modelo para programação paralela em redes são apresentados e avaliados. São eles: Glenda, uma implementacao do modelo baseada na ferramenta PVM (Parallel Virtual Machine); POSYBL (PrOgramming SYstem for distriButed appLications), um sistema construído através de recursos de sistemas operacionais compatíveis com Unix; p4-Linda, construído a partir da ferramenta de programação paralela p4 e, por fim, Network-Linda, uma implementação comercial do modelo. Depois do estudo dos quatro sistemas acima, o projeto de YALI e discutido detalhadamente. Decidiu-se, inicialmente, que YALI deveria incorporar o modelo Linda a linguagem C, que é largamente utilizada no desenvolvimento de programas de propósito geral. Além disso, optou-se por estender o modelo com algumas novas primitivas, de modo a oferecer maior poder de expressão ao usuário. Basicamente, as primitivas que YALI acrescenta ao modelo servem para dar suporte a operações globais e a criação dinâmica de threads. Operações globais servem para expressar a comunicação e a sincronização entre múltiplos processos, sendo utilizadas com bastante freqüência em vários tipos de programas paralelos. YALI suporta operações globais de maneira totalmente ortogonal ao modelo Linda, garantindo melhor desempenho sem afetar o nível de abstração oferecido. o suporte a criação dinâmica de threads, por outro lado, tem o objetivo de permitir a exploração de um paralelismo de granularidade fina, adequado ate mesmo a execução de rotinas simples em paralelo. Para suportar o desenvolvimento e execução de aplicações paralelas, YALI e implementado através de três componentes distintos. O primeiro e um pré-processador, que garante uma interface simplificada com o usuário. 0 segundo e uma biblioteca, que contem as rotinas de suporte as primitivas YALI e deve ser ligada aos programas de usuários. O terceiro componente, por fim, e um utilitário destinado a controlar a inicialização e o termino de aplicações paralelas, que baseia-se em uma configuração estabelecida pelo usuário para distribuir processos sobre uma rede de computadores. Ao contrário da maioria dos sistemas baseados em Linda, YALI implementa um espaço de tuplas distribuído entre os processos que compõem uma aplicação paralela, dispensando o use de processos especializados no gerenciamento de tuplas. Para isso, YALI utiliza múltiplas threads em cada processo definido pelo usuário, e distribui tuplas sobre estes processos através de um mecanismo baseado em hashing. A implementação de YALI leva em conta a heterogeneidade inerente a ambientes de rede, permitindo que maquinas com diferentes arquiteturas e sistemas operacionais sejam utilizadas na execução de programas paralelos. Por fim, YALI é totalmente implementado a partir de recursos presentes em sistemas compatíveis com Unix, de modo a aumentar sua portabilidade e garantir sua eficiência.

With the availability of networks connecting powerful workstations at a low cost, increasing interest has been devoted to systems that support parallel programming in such architectures. This document describes the design and implementation of YALI (Yet Another Linda Implementation), a tool that allows the development and execution of parallel programs in heterogeneous computer networks. Aiming to provide a simple and flexible interface for its users, YALI is based on the Linda parallel programming model[GEL85], that outstands in providing a high level abstraction for cooperation between processes. In Linda, communication and synchronization take place through an associative, logically shared memory called Tuple Space. Among the advantages of this model, one can mention the simplicity of its primitives, and the possibility of incorporate them in a well-known sequential language. These characteristics make Linda easy to learn, even to users with little experience in parallel programming. After a detailed description of the Linda model, this document discusses some design and implementation issues related to Linda-based systems. In order to provide a practical view of some usual solutions to address these issues, four Linda-based systems are presented and evaluated. These systems are: Glenda, an implementation of Linda built on top of PVM (Parallel Virtual Machine); POSYBL (PrOgramming SYstem for distriButed appLications), that relies on features provided by Unix-like operating systems to implement the model; p4-Linda, built on top of p4 parallel programming tool and, at last, Network-Linda, a comercial product based on Linda. All these systems, as YALI, are specially tailored to parallel programming in computer networks. Following the study of the four systems, this documents presents the design of the YALI system. One of the first design decisions was to incorporate the Linda primitives to the C language, that is broadly used as a general purpose programming language. In addition, a set of new primitives was designed as an extension to the original model, in order to increase YALI's expressivenes. Basically, the new primitives support global operations and dynamic thread creation. Global operations are useful to express communication and synchronization among multiple processes, and are frequently used many classes of parallel programs. YALI gives support to global operations in a way that is totally ortoghonal to the Linda model, ensuring better performance without affecting the abstraction level inherent to Linda-based systems. The support to dynamic thread creation, on the other hand, is helpful to explore lightweight parallelism, which allows the execution of simple routines in parallel. To support the development and execution of parallel applications, YALI is made up of three distinct components. The first is a pre-processor, that provides a simple user interface. The second is a library, that must be linked to the user programs since it's where YALI primitives are actuall y implemented. Finally, the third component is an utility that controls initialization and termination of parallel applications, which takes configuration parameters from the user to distribute processes over a newtork. In contrast with most Linda-based systems, YALI relies on a tuple space that is distributed among the processes in the same parallel application, so that intermediate tuple managers are not necessary To implement that, multiple threads are embedded in each user process, and tuples are spread over the processes in the basis of a hashing mechanism. YALI's implementation takes in account the inherent heterogeneity of network environments, allowing machines with different architectures and operating systems to be used in the execution of parallel programs. Finally, YALI is build on top of common features of Unix-like operating systems, in order to increase its efficiency and portability.