𝔖 Bobbio Scriptorium
✦   LIBER   ✦

On the parallelization of irregular and dynamic programs

✍ Scribed by Oscar Plata; Rafael Asenjo; Eladio Gutiérrez; Francisco Corbera; Angeles Navarro; Emilio L. Zapata

Publisher
Elsevier Science
Year
2005
Tongue
English
Weight
279 KB
Volume
31
Category
Article
ISSN
0167-8191

No coin nor oath required. For personal study only.

✦ Synopsis

Current compilers show ineffective when optimizing complex applications, both analyzing dependences and exploiting data locality and extracting parallelism. Complex applications may be characterized as irregular and dynamic. Irregular applications arrange data as multidimensional arrays and memory is referenced through array indirections. Dynamic applications organize data as pointer-based structures (lists, trees, . . .) and memory is referenced through pointers. In this paper we discuss a methodology we designed to develop efficient parallelization techniques for irregular and dynamic applications, that proceeds in three stages: recognizing the complex program structure, data analysis and program parallelization based on code/data transformations. Two case examples are analyzed in detail in the context of this methodology: irregular reductions and shape analysis for dynamic data structures.

📜 SIMILAR VOLUMES

On the parallelization of single dynamic
On the parallelization of single dynamic conditional loops
✍ Zaher Mahjoub; Mohamed Jemni 📂 Article 📅 1996 🏛 Elsevier Science 🌐 English ⚖ 568 KB

Considering a dynamic conditional loop S~, i.e. involving an if-then-else with a dynamic condition, our aim is to restructure ~ in order to extract the inherent parallelism. Assuming the dependence distances (DD) carried by ~ to be non-constant, we first study their corresponding signs. This leads t

Dynamic programming, decision tables, an
Dynamic programming, decision tables, and the Hawaii Parallel Computer
✍ A. Lew; R. Halverson Jr. 📂 Article 📅 1994 🏛 Elsevier Science 🌐 English ⚖ 527 KB

The use of decision tables to express concurrent algorithms, and the use of concurrent processors to execute decision table programs, are discussed. As a specific application, we show how dynamic programming algorithms can be implemented ss decision tables. The Hawaii Parallel Computer (HPC) is a p

A fast parallel Poisson solver on irregu
A fast parallel Poisson solver on irregular domains applied to beam dynamics simulations
✍ A. Adelmann; P. Arbenz; Y. Ineichen 📂 Article 📅 2010 🏛 Elsevier Science 🌐 English ⚖ 593 KB

We discuss the scalable parallel solution of the Poisson equation within a Particle-In-Cell (PIC) code for the simulation of electron beams in particle accelerators of irregular shape. The problem is discretized by Finite Differences. Depending on the treatment of the Dirichlet boundary the resultin

From the theory to the tools: parallel d
From the theory to the tools: parallel dynamic programming
✍ Gonz�lez, D.; Almeida, F.; Roda, J.; Rodr�guez, C. 📂 Article 📅 2000 🏛 John Wiley and Sons 🌐 English ⚖ 129 KB

Dynamic programming is an important paradigm that has been widely used to solve problems in various areas such as control theory, operation research, biology and computer science. We generalize the finite automaton formal model for dynamic programming deriving pipeline parallel algorithms. The optim