Repositório Digital

A- A A+

Estratégias de computação seqüenciais e paralelas sobre espaços coerentes

.

Estratégias de computação seqüenciais e paralelas sobre espaços coerentes

Mostrar registro completo

Estatísticas

Título Estratégias de computação seqüenciais e paralelas sobre espaços coerentes
Outro título Sequential and parallel computational strategies of coherence spaces
Autor Schneider Sellanes, Ruben Gerardo
Orientador Costa, Antonio Carlos da Rocha
Data 1996
Nível Mestrado
Instituição Universidade Federal do Rio Grande do Sul. Instituto de Informática. Curso de Pós-Graduação em Ciência da Computação.
Assunto Algoritmos sequenciais
Paralelismo
Teoria : Ciência : Computação
Teoria : Domínios
[en] Coherence spaces
[en] Concrete data structures
[en] Concrete domains
[en] Events domains
[en] Events structures
[en] Linear algorithms
[en] Linear functions
[en] Parallelism
[en] Semantic
[en] Sequential algorithms
[en] Sequential functions
[en] Sequentiality
[en] Stables functions
Resumo As estruturas de dados concretas (cds) são quaternas (C, V, E, l-) que contêm um conjunto C de células, um conjunto V de valores, um conjunto E de eventos e uma relação de habilitação l-. O conjunto de estados de uma cds é um domínio concreto que pode ser considerada a parte "abstrata" das cds. Da mesma maneira tem-se que os domínios de eventos (que são generalizações dos domínios concretos) são a parte abstrata das estruturas de eventos. Mostra-se a relação dos domínios concretos e domínios de eventos com os espaços coerentes, assim como também das teias de espaços coerentes com as cds e estruturas de eventos. Intuitivamente, uma cds é uma teia de um espaço coerente se toda célula c de C não é habilitada por nenhum evento (ou equivalentemente, é habilitada pelo conjunto vazio), isto é, V C E C, 0 F c. Outra forma de expressar isto é dizer que uma cds e uma teia de um espaço coerente se o conjunto de estados da cds é um espaço coerente. Definem-se os algoritmos lineares como sendo estados de uma cds no estilo dos algoritmos seqüenciais do Curien ([CUR 86]). Em particular as cds consideradas são teias de espaços coerentes. Mostra-se como obter a cds !A—>B, a partir de uma função estável f. A —> B. O algoritmo linear desta cds possui todas as estratégias de computação (seqüenciais e paralelas) que computam a função subjacente f, o que implica que os algoritmos lineares podem ser considerados meta-algoritmos. Mostra-se que para toda estratégia de computação seqüencial de um algoritmo linear, existe um algoritmo seqüencial de Curien que computa a mesma função, e vice-versa. A definição de estratégia de computação é dada de maneira tal que permite se dar semântica a segmentos de programas. Define-se uma operação de composição de estratégias, de forma tal que se pode obter uma estratégia de computação de um programa, a partir da composição das estratégias dos segmentos.
Abstract The concrete data structures, or cds, (C, V, E, l-) consists of a set C of cells, a set V of values. a set E of events and an enabling relation l-. The set of states of a cds is a concrete domain, that can be considered the "abstract" counterpart of the cds. In the same way we have that the events domains (that are more general that the concretes domains) are the abstract counterpart of the events structures. We show the relation between the concretes domains and events domains with the coherence spaces, as just as the relation between the cds and events structures with webs of coherence spaces. Intuitivelly, a cds is a web of a coherence space if any cell c is not enabled for any event, i.e. Vce C, 0 F c. We can say that a cds is a web of a coherence space if the set of states of the cds is a coherence space. We define the linear algorithms as states of a cds following the Curien's sequential algorithms ([CUR 86]). In particular the cds considered are webs of coherence spaces. We show how to obtain a cds !A—>B from a stable function f. A —> B. The linear algorithm of this cds contain all the computational strategies (sequentials and parallels) that compute the subjacent function f; this implies that the linear algorithms can be considered a kind of meta-algorithms. We show that for all sequential computational strategy of a linear al gorithm exists a Curien's sequential algorithm that compute the same function and conversely. We define the computational strategies in such a way that we can give semantic of segments of programs. We define a composition operation for strategies. This operation has the advantage that we can obtain the computational strategy of a program as the composition of the segments of it.
Tipo Dissertação
URI http://hdl.handle.net/10183/24495
Arquivos Descrição Formato
000149597.pdf (16.31Mb) Texto completo Adobe PDF Visualizar/abrir

Este item está licenciado na Creative Commons License

Este item aparece na(s) seguinte(s) coleção(ões)


Mostrar registro completo

Percorrer



  • O autor é titular dos direitos autorais dos documentos disponíveis neste repositório e é vedada, nos termos da lei, a comercialização de qualquer espécie sem sua autorização prévia.
    Projeto gráfico elaborado pelo Caixola - Clube de Criação Fabico/UFRGS Powered by DSpace software, Version 1.8.1.