University of Macau / Faculty of Science and Technology. / Department of Computer and Information Science

Public resource computing (PRC) is an innovative approach to high performance computing that relies on volunteers who donate their personal computers' unused resources to a computationally intensive research project. Prominent PRC projects include SETI@home, Folding@Home, and distributed.net. Many PRC projects are built upon a PRC framework that abstracts functionality that is common to all PRC projects, such as network communications, database access, and project management. These PRC frameworks tend to be complex, limiting, and difficult to use. We have designed and implemented a new PRC framework called the Simple Light-weight Infrastructure for Network Computing (SLINC) that addresses the disadvantages we identified with existing frameworks. SLINC is a flexible and extensible PRC framework that will enable researchers to more easily build PRC projects.

Data warehousing is becoming an increasingly important technology for information integration and data analysis. Given the dynamic nature of modern distributed environments, both source data updates and schema changes are likely to occur autonomously and even concurrently in different data sources. Current approaches to maintain a data warehouse in such dynamic environments sequentially schedule maintenance processes to occur in isolation. Furthermore, each maintenance process is handling the maintenance of one single source update. This limits the performance of current data warehouse maintenance systems in a distributed environment where the maintenance of source updates endures the overhead of network delay as well as IO costs for each maintenance query. In this thesis work, we propose two different optimization strategies which can greatly improve data warehouse maintenance performance for a set of source updates in such dynamic environments. Both strategies are able to support source data updates and schema changes. The first strategy, the parallel data warehouse maintainer, schedules multiple maintenance processes concurrently. Based on the DWMS_Transaction model, we formalize the constraints that exist in maintaining data and schema changes concurrently and propose several parallel maintenance process schedulers. The second strategy, the batch data warehouse maintainer, groups multiple source updates and then maintains them within one maintenance process. We propose a technique for compacting the initial sequence of updates, and then for generating delta changes for each source. We also propose an algorithm to adapt/maintain the data warehouse extent using these delta changes. A further optimization of the algorithm also is applied using shared queries in the maintenance process. We have designed and implemented both optimization strategies and incorporated them into the existing DyDa/TxnWrap system. We have conducted extensive experiments on both the parallel as well as the batch processing of a set of source updates to study the performance achievable under various system settings. Our findings include that our parallel maintenance gains around 40 ~ 50% performance improvement compared to sequential processing in environments that use single-CPU machines and little network delay, i.e, without requiring any additional hardware resources. While for batch processing, an improvement of 400 ~ 500% improvement compared with sequential maintenance is achieved, however at the cost of less frequent refreshes of the data warehouse content.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1981. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Bibliography: leaves 250-252. / by Stephen Thomas Kent. / Ph.D.

Este trabalho a dedicado ao estudo da exploração de paralelismo OU na programação em lógica com restrições em ambientes distribuídos. A programação em lógica, cuja linguagem mais significativa 6 Prolog, tem como premissa a utilização da lógica de predicados como linguagem computacional. A programação em lógica com restrições (CLP) é uma extensão da programação em lógica, onde busca-se a eficiência e a possibilidade de executar novas classes de problemas. Variáveis em CLP podem pertencer a domínios específicos como, por exemplo, reais ou booleanos. O principal conceito introduzido é a restrição. Restrição a uma equação que representa uma certa informação sobre uma variável e a sua relação com outras variáveis. o uso de restrições foi proposto para diminuir o espaço de busca na execução dos programas. Apesar de mais eficientes que a programação em lógica clássica, para algumas aplicações reais o desempenho das linguagens CLP ainda é insatisfatório. Por isso, é necessário buscar alternativas novas como a execução em paralelo. A exploração de paralelismo implícito em programas em 1ógica já demonstrou resultados promissores. Vários modelos foram propostos e implementados utilizando as duas principais fontes de paralelismo — E e OU — de forma isolada ou combinada. O objetivo principal desse trabalho é apresentar o modelo pclp(FD) de exploração de paralelismo OU multi-sequêncial para um ambiente com memória distribuída. O modelo pclp(FD) caracteriza-se pela existência de vários trabalhadores, cada um deles possuindo uma maquina abstrata completa. O escalonamento de tarefas a realizado por uma política dinâmica e distribuída. Uma tarefa em pclp(FD) equivale a um ponto de escolha e a um contexto de execução. O contexto de execução a formado por porções da pilha do exportador. Para que o importador tenha acesso ao contexto de execução utiliza-se a cópia incremental, que a uma das varias técnicas possíveis. Cada trabalhador possui a sua própria copia privada das pilhas de execução. A cópia caracteriza-se pelo envio das pilhas de execução do exportador para uma área privada do importador. A cópia incremental é uma técnica mais otimizada que verifica a existência de partes comuns entre os trabalhadores, copiando apenas as panes novas. O algoritmo de cópia incremental proposto no modelo a feito sem nenhuma centralização de informação do estado das pilhas. O projeto e implementação de um prot6tipo para esse modelo, utilizando a linguagem clp(FD), que implementa CLP sobre domínios finitos, permitirá uma analise das vantagens e desvantagens do modelo proposto. Os resultados obtidos com a análise servirão de base para trabalhos futuros, visando aprimorar a implementação e o modelo. / This work is dedicated to the study of the exploration of OR parallelism in Constraint Logic Programming for distributed environment. Logic Programming, which the most meaningful language is Prolog, has as premise the use of the logic of predicates as computational language. Constraint Logic Programming or CLP is an extension of the logic programming, where efficiency and the possibility to execute new kinds of problems are searched. A variable in CLP can belong to specific domains as, for example, Real or Boolean. The main concept introduced is the constraint. Constraint is an equation that represents a certain information over a variable and its relation with others variables. The use of constraints was proposed to decrease search space in the program execution. Although it is more efficient than classic logic programming, for some real applications, the performance of CLP languages still is unsatisfactory. So, it is necessary to search alternatives as parallel execution. The exploration of implicit parallelism in programs in logic has already demonstrated promising results. Several models have been proposed and implemented using the two main sources of parallelism - AND and OR — in an isolated or combined form. The main objective of this work is to present the pclp(FD) model of exploration of multi-sequential OR parallelism for a distributed memory environment. The pclp(FD) model is characterized for the existence of some workers, each one of them possessing a complete abstract machine. Task scheduling is executed by one dynamic and distributed policy. A task in pclp(FD) is equivalent to a choice point and an execution context. Execution context is formed by portions of the stack of the exporter. So that importer has access to the execution context, it uses incremental copy, which is one of the several possible techniques. The copy is characterized for sending execution stacks of the exporter to a private area of the importer, that is, each worker possesses its private copy of the execution stacks. The incremental copy is a more optimized technique that verifies the existence of common parts between workers, copying only the new ones. The incremental copy algorithm proposed in the model executes without centralized information of the state of the stacks. A prototype project and implementation for this model, using the language clp(FD), that implements CLP over finite domains, will allow an analysis of advantages and disadvantages of the considered model. The results gotten with the analysis will serve of base for future works, aiming to improve the implementation and the model.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1982. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Includes bibliographical references. / by Eliezer Menahem Gafni. / Ph.D.

Thesis (Ph.D.)--Massachusetts Institute of Technology, Dept. of Electrical Engineering and Computer Science, 1980. / MICROFICHE COPY AVAILABLE IN ARCHIVES AND ENGINEERING. / Includes bibliographical references. / by Seyyed Jamaaloddin Golestaani. / Ph.D.

This thesis details PPerfXchange’s approach for querying geographically dispersed heterogeneous data stores. While elements of PPerfXchange’s method have been implemented for other application areas, PPerfXchange shows how these elements can be applied to parallel performance analysis. The accomplishments of this thesis are: The design of an architecture for PPerfXchange, giving a uniform method to query heterogeneous data stores; A proof of concept prototype implementation of PPerfXchange including a partial implementation of an XQuery processor and a relational database virtual XML document; and Evaluation of PPerfXchange using example parallel performance analysis data.

Distributed-memory machines offer a very high level of performance, flexibility and scalability. But the memory organization of this kind of machine determines that processes on different processors must communicate explicitly by sending and receiving messages. As a result, the programmer faces the enormously difficult task of detailed planning of algorithm-irrelevant, low-level communication issues. This level of programming resembles writing assembly programs for a sequential machine. ACE is a message-passing language with abstract communication statements. It was defined by Dr. Jingke Li at Portland State University. The communication in ACE is still explicit, but it is abstracted to a higher level. The abstraction can help balance the needs of ease of programming and high performance. This thesis discusses how those high-level communication abstractions can be transformed into low-level communication routines. It presents the design and implementation of a compiler that transforms an ACE program into a C program with low-level communication routines. The compiler is implemented for the Intel iPSC/2 hypercube multiprocessor machine. Compared to their low-level counterparts, ACE programs are easier to write and are more understandable. Compared to their high level counterparts, more efficient code can be generated since the communication information is expressed explicitly in ACE and the compiler itself is much less complex. ACE also enables the users to fine tune some critical communication segments. Some well known parallel algorithms written in ACE are compiled by the compiler as examples, and experimental results of their performance are included.

Abstract not available