What is ahead for parallel computing

• A clear articulation of what makes parallel algorithms hard in multicores and manycores.
• A practical classification of levels of challenges in parallel algorithms.
• An overview of practical techniques for improving parallel algorithm scalability and efficiency.
• A detailed real example of a highly optimized parallel GPU algorithm.

With the industry-wide switch to multicore and manycore architectures, parallel computing has become the only venue in sight for continued growth in application performance. In order for the performance of an application to grow with future generations of hardware, a significant portion of its computation must be done with scalable parallel algorithms. It is therefore important to develop and deploy as many scalable parallel algorithms as possible. This paper takes a critical look at the major challenges involved in the development of scalable parallel algorithms and points to needs for compiler tool innovations to help address these challenges.