Grant: Engage Grants Program
University of Waterloo
$21,970.00
Theoretical models for parallel computation in CMP and GPU architectures: algorithm analysis & design, cache efficiency and performance prediction
EF 2010-11
Résumé
In recent years, we have witnessed a shift in computer processor development away from higher clock
frequency sequential processors to multicore processors, also known as chip multiprocessors (CMP).
CMPs have become the dominant architecture in current computer platforms, and programmers face the
difficult challenge of developing applications that exploit the parallel processing capabilities of the
architecture. In order for these applications to reach high efficiency standards we require new models and tools
for the design and implementation of multicore algorithms. A Graphic Processing Unit (GPU) is a highly
parallel architecture primarily designed for assisting computer processors with the processing of graphic tasks.
Recently the use of GPUs has been extended to other applications, where the massively parallel power of these
units has been used to boost the performance of applications that require vast computational resources.
Currently, there are no established theoretical models for the design and analysis of algorithms in these
architectures. We have already developed a model of computation for multicore processors that has been used
to prove that optimal speedups for key building blocks of computation can be easily obtained for CMP
architectures via simple changes to sequential algorithms. In this project we plan to: 1) extend the CMP model
to enable the design and analysis of algorithms for GPUs and 2) evaluate strategies to manage shared caches in
CMP architectures. The development of efficient strategies for this key resource is fundamental to obtaining
full speedup from the parallel processing aspect of the architecture.
The development of an accurate theory of parallel computing in CMPs and GPUs will enable the design of
algorithms with provable performance that fully benefit from the power of these novel architectures. In
addition, the proposed model will enable AMD to analytically evaluate the performance of their multicore and
GPU products, identifying bottlenecks and key design features impacting performance, leading ultimately to
the development of more efficient computational solutions, both in hardware and software.
Programme
Engage Grants Program
Bénéficiaire
Emplacement
Ontario, Canada
Type de bénéficiaire
Academia
Type
Grant
Source
NSERC's Awards Data
Tel que publié
Application id
411866-2010
Name nom
LopezOrtiz, Alejandro
Department département
Computer Science, David R. Cheriton School of
Organization id
33
Institution établissement
University of Waterloo
Province en
Ontario
Province fr
Ontario
Country en
CANADA
Country fr
CANADA
Fiscal year exercice financier
2010
Competition year année de concours
2010
Award amount
21970
Program id
EGP
Program name en
Engage Grants Program
Program name fr
Programme de subventions d'engagement partenariat
Group en
Research partnerships programs
Group fr
Programmes de partenariat
Committee code
1553
Committee name en
Ontario Internal Decision Committee
Committee name fr
Comité de décision interne pour l'Ontario
Area of application code
1207
Area of application group en
Advancement of knowledge
Area of application group fr
Avancement des connaissances
Area of application en
Information, computer and communication technologies
Area of application fr
Technologie de l'information, des ordinateurs et des réseaux de communications
Research subject code
2713
Research subject group en
Information technology
Research subject group fr
Technologie de l'information
Research subject en
Algorithms
Research subject fr
Algorithmes
Partie
1
Nb partie
1
Application title
Theoretical models for parallel computation in CMP and GPU architectures: algorithm analysis & design, cache efficiency and performance prediction
Keyword
NSERC
Application summary
In recent years, we have witnessed a shift in computer processor development away from higher clock
frequency sequential processors to multicore processors, also known as chip multiprocessors (CMP).
CMPs have become the dominant architecture in current computer platforms, and programmers face the
difficult challenge of developing applications that exploit the parallel processing capabilities of the
architecture. In order for these applications to reach high efficiency standards we require new models and tools
for the design and implementation of multicore algorithms. A Graphic Processing Unit (GPU) is a highly
parallel architecture primarily designed for assisting computer processors with the processing of graphic tasks.
Recently the use of GPUs has been extended to other applications, where the massively parallel power of these
units has been used to boost the performance of applications that require vast computational resources.
Currently, there are no established theoretical models for the design and analysis of algorithms in these
architectures. We have already developed a model of computation for multicore processors that has been used
to prove that optimal speedups for key building blocks of computation can be easily obtained for CMP
architectures via simple changes to sequential algorithms. In this project we plan to: 1) extend the CMP model
to enable the design and analysis of algorithms for GPUs and 2) evaluate strategies to manage shared caches in
CMP architectures. The development of efficient strategies for this key resource is fundamental to obtaining
full speedup from the parallel processing aspect of the architecture.
The development of an accurate theory of parallel computing in CMPs and GPUs will enable the design of
algorithms with provable performance that fully benefit from the power of these novel architectures. In
addition, the proposed model will enable AMD to analytically evaluate the performance of their multicore and
GPU products, identifying bottlenecks and key design features impacting performance, leading ultimately to
the development of more efficient computational solutions, both in hardware and software.