SC13 Denver, CO

The International Conference for High Performance Computing, Networking, Storage and Analysis

Algorithmic Choice in Optimization Problems: A Performance Study.


Authors: Hammad Rashid (Texas State University), Clara Novoa (Texas State University), Richard Hay (Texas State University), Apan Qasem (Texas State University)

Abstract: To harness the full potential of emerging manycore platforms, the compiler needs to play a key role in exploiting the available on-chip parallelism. Since the amount of extracted parallelism is directly influenced by the selection of the algorithm, algorithmic choice plays a critical role in achieving scalable high performance. This research investigates the impact of algorithmic choice on performance of parallel implementations of optimization problems. The study implements several algorithmic variants of the integral knapsack problem and evaluates each one based on a range of performance characteristics including thread affinity, task granularity and data reuse. Experimental results reveal that selection of the algorithm does have a significant impact on parallel performance. Furthermore, the study provides insight into the relationship of algorithm selection and specific aspects of performance including HW prefetch activity and exploited data locality through favorable cache sharing.

Poster: pdf
Two-page extended abstract: pdf


Poster Index