Modular average case analysis: Language implementation and extension

Motivated by accurate average-case analysis, MOdular Quantitative Analysis (MOQA) is developed at the Centre for Efficiency Oriented Languages (CEOL). In essence, MOQA allows the programmer to determine the average running time of a broad class of programmes directly from the code in a (semi-)automated way. The MOQA approach has the property of randomness preservation which means that applying any operation to a random structure, results in an output isomorphic to one or more random structures, which is key to systematic timing. Based on original MOQA research, we discuss the design and implementation of a new domain specific scripting language based on randomness preserving operations and random structures. It is designed to facilitate compositional timing by systematically tracking the distributions of inputs and outputs. The notion of a labelled partial order (LPO) is the basic data type in the language. The programmer uses built-in MOQA operations together with restricted control flow statements to design MOQA programs. This MOQA language is formally specified both syntactically and semantically in this thesis. A practical language interpreter implementation is provided and discussed. By analysing new algorithms and data restructuring operations, we demonstrate the wide applicability of the MOQA approach. Also we extend MOQA theory to a number of other domains besides average-case analysis. We show the strong connection between MOQA and parallel computing, reversible computing and data entropy analysis.

Paral·lelització especulativa de programes sobre un clúster

Estudi sobre la millora de rendiment (en temps d’execució) a l'algorisme de gràfics Fast Multipath Radiosity Using Hierarchical Subscenes gràcies a l’execució paral•lela especulada que ens permet obtenir el motor d'especulació per a clústers desenvolupat en el grup de recerca BCDS de la Universitat de Girona

Técnicas de paralelização em GPGPU aplicadas em algoritmo para remoção de ruído multiplicativo

Coordenação de Aperfeiçoamento de Pessoal de Nível Superior (CAPES)

Techniques for improving the inherent parallelism in programs /

Thesis (M.S.) - University of Illinois at Urbana-Champaign.

An algorithm for solving linear recurrence systems on parallel and pipelined machines /

"UILU-ENG 78 1745."

Adaptive merging by parallel disjoint comparisons /

Includes bibliographical references.

A parallel QR-algorithm for tridiagonal symmetric matrices /

"NSF-OCA-GJ-36936-000008."

Parallel techniques.

Originally presented as the author's thesis, University of Illinois at Urbana-Champaign.

Parallel direct Poisson and biharmonic solvers /

"NSF - OCA - GJ-36936 - 000006."

Parallel algorithms for network routing problems and recurrences /

"Grant no. US NSF MCS75-21758."

Speedup of iterative programs in multiprocessing systems /

Originally presented as the author's thesis, University of Illinois at Urbana-Champaign.

Techniques for parallel computer design /

Vita.

Control structures for parallel machines /

"UILU-ENG 79 1724"

Solving triangular systems on a parallel computer /

Includes bibliographical references.

Scheduling on parallel processors for weighted-node graphs.

Extra t.p. with thesis statement inserted.