Withdraw
Loading…
Automatic algorithm derivation and exploration in linear algebra for parallelism and locality
Duchateau, Alexandre
Loading…
Permalink
https://hdl.handle.net/2142/45394
Description
- Title
- Automatic algorithm derivation and exploration in linear algebra for parallelism and locality
- Author(s)
- Duchateau, Alexandre
- Issue Date
- 2013-08-22T16:38:53Z
- Director of Research (if dissertation) or Advisor (if thesis)
- Padua, David A.
- Barthou, Denis
- Doctoral Committee Chair(s)
- Padua, David A.
- Committee Member(s)
- Barthou, Denis
- Kale, Laxmikant V.
- Heath, Michael T.
- Garzaran, Maria J.
- Department of Study
- Computer Science
- Discipline
- Computer Science
- Degree Granting Institution
- University of Illinois at Urbana-Champaign
- Degree Name
- Ph.D.
- Degree Level
- Dissertation
- Keyword(s)
- Autotuning
- Linear Algebra
- Parallelism
- Multicore
- Tiling
- Abstract
- "Parallelization is one of the major challenges for programmers. But parallelizing existing code is a hard task that can lead to less than optimal solutions since sequential programs can su er from impediments to parallelization resulting from the semantic of the languages or the data structures used rather than the nature of the problem being solved. To avoid such artifacts, programmers can analyze the algorithms to decide which dependencies are ""real"" and which can be ignored. But even then, conventional algorithms were developed with speci c objectives in mind, such as reducing the total number of operations, which while good to achieve sequential performance, may not be the primary objective when considering parallel machines. We propose to focus on a speci c domain and attack the parallelizing issue at the source, starting from a high level description of the equations without any knowledge of existing algorithms to solve the problem and automatically derive parallel solutions. Hydra accepts an equation written in terms of operations on matrices and automatically produces highly e cient code to solve these equations. Processing of the equation starts by tiling the matrices. This transforms the equation into either a single new equation containing terms involving tiles or into multiple equations some of which can be solved in parallel with each other. Hydra continues transforming the equations using tiling and seeking terms that Hydra knows how to compute or equations it knows how to solve. The end result is that by transforming the equations Hydra can produce multiple solvers with di erent locality behavior and/or di erent parallel execution pro les. Next, Hydra applies empirical search over this space of possible solvers to identify the most e cient version. In this way, Hydra enables the automatic production of e cient solvers requiring very little or no coding at all and delivering performance approximating that of the highly tuned library routines such as Intels MKL. With faster development time for modern architecture, the time available for hand-tuning of high performance libraries diminishes. Intel already started o ering auto-tuned library routines (From Spiral) in their IPP library, to broaden the scope of application of the collection, without having to increase the man hours required to hand-tune everything."
- Graduation Semester
- 2013-08
- Permalink
- http://hdl.handle.net/2142/45394
- Copyright and License Information
- Copyright 2013 Alexandre Xavier Duchateau
Owning Collections
Dissertations and Theses - Computer Science
Dissertations and Theses from the Dept. of Computer ScienceGraduate Dissertations and Theses at Illinois PRIMARY
Graduate Theses and Dissertations at IllinoisManage Files
Loading…
Edit Collection Membership
Loading…
Edit Metadata
Loading…
Edit Properties
Loading…
Embargoes
Loading…