O trabalho apresenta o projeto e o desenvolvimento de uma ferramenta para visualização lógica da execução de programas paralelos, a TFPS de Trace File Preprocessor System, cujo objetivo é a analise de desempenho de tais programas. 0 projeto é baseado no pré-processamento de arquivos de traces de execução dos programas. A idéia básica consiste em aproveitar as informações fornecidas pela monitoração. Estas informações, que em geral são utilizadas apenas para dirigir animação post-mortem destes programas, neste caso são utilizadas também na montagem das janelas de visualização. Assim, são descritos o pré-processador e a montagem das janelas de visualização. O primeiro, e responsável principalmente pela leitura e analise das informações contidas no arquivo de trace e pela geração de um arquivo de saída com todas as informações necessárias a montagem das janelas. Estas foram concebidas levando em consideração o tipo de informação que pode ser obtido de um arquivo de trace. Desta forma, foi possível aproximar o conteúdo das janelas de visualização o máximo possível do programa paralelo em analise. Com o objetivo de demonstrar esta aproximação foi construído um protótipo tanto para o pré-processador quanto para a ferramenta de visualização. Ambos os protótipos são descritos neste trabalho. / This study presents the project and development of a logical visualization tool for parallel programs. the TFPS of Trace File Preprocessor System, whose goal is the performance analysis of such programs. The project is based on the preprocessing of trace files of programs' execution. The basic idea consists in making use of the information given by the monitoring process. This information, whose general application is only to drive the post-mortem animation of these programs, is in this case also used to create the visualization displays. Thus, the preprocessor and the creation of visualization displays are described. The first is mainly responsible for reading and analyzing the information present in the trace file and for generating an output file with all information necessary for creating the views. The latter was conceived by taking into consideration the type of information that can be obtained from a trace file. Therefore it was possible to make the content of the visualization displays close to the parallel program that is being analyzed. A prototype of the preprocessor as well as of the visualization tool was built up in order to demonstrate the described approach. Both prototypes are described in this study.

Typescript (photocopy).

Parallel architectures, like the transputer-based multicomputer network, offer potentially enormous computational power at modest cost. However, writing programs on a multicomputer to exploit parallelism is very difficult due to the lack of tools to help users understand the run-time behavior of the parallel system and detect performance bottlenecks in their programs. This thesis examines the performance characteristics of parallel programs in a multicomputer network, and describes the design and implementation of a real-time performance monitoring tool on transputers. We started with a simple graph theoretical model in which a parallel computation is represented as a weighted directed acyclic graph, called the execution graph. This model allows us to easily derive a variety of performance metrics for parallel programs, such as program execution time, speedup, efficiency, etc. From this model, we also developed a new analysis method called weighted critical path analysts (WCPA), which incorporates the notion of parallelism into critical path analysis and helps users identify the program activities which have the most impact on performance. Based on these ideas, the design of a real-time performance monitoring tool was proposed and implemented on a 74-node transputer-based multicomputer. Major problems in parallel and distributed monitoring addressed in this thesis are: global state and global clock, minimization of monitoring overhead, and the presentation of meaningful data. New techniques and novel approaches to these problems have been investigated and implemented in our tool. Lastly, benchmarks are used to measure the accuracy and the overhead of our monitoring tool. We also demonstrate how this tool was used to improve the performance of an actual parallel application by more than 50%. / Science, Faculty of / Computer Science, Department of / Graduate

Although networked-based computational environments such as Linda-LAN provide parallel processing capability, performance is still a major concern. One critical factor that can hinder the performance of any parallel processing environment is the high cost of interprocess communication. The goal of this project is to increase the performance of C-Linda programs executed in the Linda-LAN environment. With the current two packet message passing scheme, a receiving process listens for a header packet to arrive on a socket connection. Once the header packet has been received, the process then reads the data packet that follows. Reading the data packet may cause the process to block since the data may not have arrived. By modifying the two packet scheme to use only a single packet, the potential for blocking is removed since the header and data packets are guaranteed to arrive at the same time. Hence, the time spent waiting for the data is nullified, thus producing an increase in performance. / Master of Science

A graph is a data structure that contains a set of nodes and a set of edges connecting these nodes. Nodes represent objects while edges model relationships among these objects. Graphs are used in various domains due to their ability to model complex relations among several objects. Given an input graph, the Frequent Subgraph Mining (FSM) task finds all subgraphs with frequencies exceeding a given threshold. FSM is crucial for graph analysis, and it is an essential building block in a variety of applications, such as graph clustering and indexing. FSM is computationally expensive, and its existing solutions are extremely slow. Consequently, these solutions are incapable of mining modern large graphs. This slowness is caused by the underlying approaches of these solutions which require finding and storing an excessive amount of subgraph matches. This dissertation proposes a scalable solution for FSM that avoids the limitations of previous work. This solution is composed of four components. The first component is a single-threaded technique which, for each candidate subgraph, needs to find only a minimal number of matches. The second component is a scalable parallel FSM technique that utilizes a novel two-phase approach. The first phase quickly builds an approximate search space, which is then used by the second phase to optimize and balance the workload of the FSM task. The third component focuses on accelerating frequency evaluation, which is a critical step in FSM. To do so, a machine learning model is employed to predict the type of each graph node, and accordingly, an optimized method is selected to evaluate that node. The fourth component focuses on mining dynamic graphs, such as social networks. To this end, an incremental index is maintained during the dynamic updates. Only this index is processed and updated for the majority of graph updates. Consequently, search space is significantly pruned and efficiency is improved. The empirical evaluation shows that the proposed components significantly outperform existing solutions, scale to a large number of processors and process graphs that previous techniques cannot handle, such as large and dynamic graphs.

No description available.

No description available.

No description available.

No description available.

No description available.