F. Versaci, K. Pingali:

"Processor Allocation for Optimistic Parallelization of Irregular Programs";

Talk: 12th International Conference on Computational Science and Its Applications, ICCSA 2012, Salvador de Bahia, Brazil; 2012-06-18 - 2012-06-21; in: "Computational Science and Its Applications, ICCSA 2012, Proceedings of the 12th International Conference, Part I", B. Murgante, O. Gervasi, S. Misra, N. Nedjah, A. Rocha, D. Taniar, B. Apduhan (ed.); Springer, LNCS 7333 (2012), ISBN: 978-3-642-31124-6; 1 - 14.

Optimistic parallelization is a promising approach for the

parallelization of irregular algorithms: potentially interfering tasks are launched dynamically, and the runtime system detects conflicts between concurrent activities, aborting and rolling back conflicting tasks. However, parallelism in irregular algorithms is very complex. In a regular algorithm like dense matrix multiplication, the amount of parallelism can usually be expressed as a function of the problem size, so it is reasonably straightforward to determine how many processors should be allocated to execute a regular algorithm of a certain size (this is called the processor

allocation problem). In contrast, parallelism in irregular algorithms

can be a function of input parameters, and the amount of parallelism

can vary dramatically during the execution of the irregular algorithm.

Therefore, the processor allocation problem for irregular algorithms is very difficult.

In this paper, we describe the first systematic strategy for addressing this problem. Our approach is based on a construct called the conflict graph, which (i) provides insight into the amount of parallelism that can be extracted from an irregular algorithm, and (ii) can be used to address the processor allocation problem for irregular algorithms. We show that this problem is related to a generalization of the unfriendly seating problem and, by extending Turánīs theorem, we obtain a worstcase class of problems for optimistic parallelization, which we use to derive a lower bound on the exploitable parallelism. Finally, using some theoretically derived properties and some experimental facts, we design a quick and stable control strategy for solving the processor allocation problem heuristically.

Irregular algorithms, Optimistic parallelization, Automatic parallelization, Amorphous data-parallelism, Processor allocation, Unfriendly seating, Turánīs theorem.

http://dx.doi.org/10.1007/978-3-642-31125-3_1

Created from the Publication Database of the Vienna University of Technology.