Data Structures and Algorithms

1106 Submissions

[3] viXra:1106.0033 [pdf] submitted on 15 Jun 2011

Towards a Group Theoretical Model for Algorithm Optimization

Authors: Sven de Smet
Comments: 4 Pages.

This paper proposes to use a group theoretical model for the optimization of algorithms. We first investigate some of the fundamental properties that are required in order to allow the optimization of parallelism and communication. Next, we explore how a group theoretical model of computations can satisfy these requirements. As an application example, we demonstrate how this group theoretical model can uncover new optimization possibilities in the polyhedral model.
Category: Data Structures and Algorithms

[2] viXra:1106.0023 [pdf] submitted on 12 Jun 2011

A Lattice Model for the Optimization of Communication in Parallel Algorithms

Authors: Sven de Smet
Comments: 12 pages. This paper is a slightly modified version of a draft paper that was submitted to ParCo 2011 and is very preliminary. Since I do not have the resources to complete this paper by increasing its clarity, extending the experimental evaluation and adding a section on related work, I'm making it available so that it may be useful to others.

This paper describes a unified model for the optimization of communication in parallel algorithms and architectures. Based on a property that provides a unified view of locality in space and time, an algorithm is constructed that generates a parallel architecture that is optimized for communication for a given computation. The optimization algorithm is constructed using the lattice algebraic properties of congruence relations and is therefor applicable in a general context. An application to a bio-informatics algorithm demonstrates the value of the model and optimization algorithm.
Category: Data Structures and Algorithms

[1] viXra:1106.0022 [pdf] submitted on 12 Jun 2011

Parallelisation with a Grid Abstraction

Authors: Sven de Smet
Comments: 16 pages, This paper is a slightly modified version of a draft paper that was submitted to ParCo 2011 (with added proofs) and is very preliminary. Since I do not have the resources to complete this paper by increasing its clarity, adding examples, adding an experimental evaluation and adding a section on related work, I'm making it available so that it may be useful to others.

This paper describes a new technique for automatic parallelisation in the Z-polyhedral model. The presented technique is applicable to arbitrarily nested loopnests with iteration spaces that can be represented as unions of Z-polyhedra and affine modular data-access functions. The technique partitions both iteration and data spaces of the computation. The maximal amount of parallelism that can be represented using grid partitions is extracted.
Category: Data Structures and Algorithms