Thesis (Ph. D.)--University of Washington, 2001. / Vita. Includes bibliographical references (p. 104-113).

Pointer analysis is a fundamental enabling technology for program analysis. By improving the scalability of precise pointer analysis we can make a positive impact across a wide range of program analyses used for many different purposes, including program verification and model checking, optimization and parallelization, program understanding, hardware synthesis, and more. In this thesis we present a suite of new algorithms aimed at improving pointer analysis scalability. These new algorithms make inclusion-based analysis (the most precise flow- and context-insensitive pointer analysis) over 4x faster while using 7x less memory than the previous state-of-the-art; they also enable flow-sensitive pointer analysis to handle programs with millions of lines of code, two orders of magnitude greater than the previous state-of-the-art. We present a formal framework for describing the space of pointer analysis approximations. The space of possible approximations is complex and multidimensional, and until now has not been well-defined in a formal manner. We believe that the framework is useful as a method to meaningfully compare the precision of the multitude of existing pointer analyses, as well as aiding in the systematic exploration of the entire space of approximations. / text

This work gives the overview of particularities of parallel programming for the personal computer and the observation of the possibilities and advantages of the Hyper-Threading technology and new Pentium 4 processors. The work proves that the creation of the Hyper-Threading technology and dual-core processors helps to make parallel computing more available for the usual personal computer. Parallel programming becomes not only the way of solving difficult tasks but gives a real possibility to speed up the work of personal computer and to use its hardware resources more effectively. The work gives the review of the possibilities of creation of parallel programs by using OpenMP standard and particularities of the application of the set of SSE2 processor commands. The results of practical tests are given. They indicate that the floating point computing is more effective without using of multiple threads and Hyper-Treading technology shows best results working with different types of processes or working with new processor possibilities.

Šis magistrinis darbas skirtas lygiagrečių programų efektyvumo analizei atlikti, pasinaudojant sukurta lygiagrečių programų efektyvumo tyrimo programine įranga. Pagrindinis darbo tikslas – sukurti, ištirti bei pritaikyti mokymo programinę įrangą, skirtą lygiagrečių programų analizei. Tam tikslui buvo atliekamas sukurtos programos galimybių tyrimas bei suplanuoti ir vykdomi programinės įrangos tobulinimo darbai. Taip pat buvo atliekami pavyzdinių lygiagrečių programų tyrimai, naudojant sukurtą programinę įrangą, norint parodyti lygiagrečių programų efektyvumo tyrimo būdus bei sukurtos lygiagrečių programų efektyvumo tyrimo programinės įrangos galimybes. / Parallel program execution is often used to overcome the constraints of processing speed and memory size when executing complex and time-consuming algorithms. The downside to this approach is the increased overall complexity of programs and their implementations. Parallel execution introduces a new class of software bugs and performance shortcomings, that are usually difficult to trace using traditional methods and tools. Hence, new tools and methods need to be introduced, which deal specifically with problems encountered in parallel programs. The goal of this project is the development of MPI-based parallel program performance monitoring tool and research into the ways this tool can be used for measuring, comparing and improving the performance of target programs.

The IMAPCAR2 from Renesas Electronics is an embedded realtime image processor, combining a single core with a 128-way SIMD array. At runtime, sections of the SIMD array can be retasked as additional CPU cores, interconnected via a message passing ring. Using these cores effectively, however, is made difficult by the low-level nature of the message passing API and the lack of cache coherency between processors. Developing and debugging software for this platform is a difficult task. The AutoPilot library addresses this by providing a high-level message-oriented parallel programming model for the IMAPCAR2. AutoPilot's API is closely based on that of Pilot, a wrapper around the Message Passing Interface (MPI) for cluster computing. By reimplementing the Pilot API for the IMAPCAR2, AutoPilot shows that its processes-and-channels architecture is a viable choice for parallel programming on cache-incoherent multicore architectures. At the same time, it provides a simpler API for programmers, with builtin safety checks that eliminate some common sources of errors.

No description available.

No description available.

El objetivo de este trabajo es mostrar la aceleración en el tiempo de cómputo del algoritmo criptográfico Advanced Encryption Standard (AES) con clave de tamaño 128bits, que se obtiene al aprovechar el paralelismo que proveen las arquitecturas multicores actuales utilizando herramientas de programación paralela. AES es uno de los algoritmos de criptografía más usados en la actualidad, con el crecimiento de las redes y la información que se maneja hoy en día puede ser necesario cifrar un volumen muy grande de información para lo que se requiere mayor velocidad en los procesadores, pero esto actualmente no es posible debido a que los procesadores han llegado al límite de velocidad por problemas térmicos y de consumo, por esta razón se está incrementando la cantidad de procesadores en los equipos. Como aporte de la concreción de este trabajo se pretende presentar un análisis de rendimiento que muestre cómo a pesar de las limitaciones de velocidad de los procesadores, es posible, mediante herramientas de programación paralela, aprovechar las arquitecturas multicore para acelerar el cómputo del algoritmo AES y así reducir el tiempo de cifrar información ya sea para almacenarla o enviarla por la red.

No description available.

Writing efficient parallel programs is a difficult and error-prone process. The Standard Template Adaptive Parallel Library (STAPL) is being developed to make this task easier for programmers with little experience in parallel programming. STAPL is a C++ library for writing parallel programs using a generic programming approach similar to writing sequential programs using the C++ Standard Template Library (STL). STAPL provides a collection of parallel containers (pContainers) to store data in a distributed fashion and a collection of pViews to abstract details of the data distribution. STAPL algorithms are written in terms of PARAGRAPHs which are high level descriptions of task dependence graphs. Scheduling plays a very important role in the efficient execution of parallel programs. In this thesis, we present our work to enable efficient scheduling of parallel programs written using STAPL. We abstract the scheduling activities associated with PARAGRAPHs in a software module called the scheduler which is customizable and extensible. We provide support for static scheduling of PARAGRAPHs and develop mechanisms based on migration of tasks and data to support dynamic scheduling strategies for PARAGRAPHs with arbitrary dependencies. We also provide implementations of different scheduling strategies that can be used to improve the performance of applications suffering from load imbalance. The scheduling infrastructure developed in this thesis is highly customizable and can be used to execute a variety of parallel computations. We demonstrate its usefulness by improving the performance of two applications: a widely used synthetic benchmark (UTS) and a Parallel Motion Planning application. The experiments are conducted on an Opteron cluster and a massively parallel Cray XE6 machine. Experimental results up to 6144 processors are presented.