Paper Info
Title
Efficient Parallel Solutions To The Integral Knapsack Problem On Current Chip-Multiprocessor Systems
Abstract
The emergence of chip-multiprocessor systems has dramatically increased the performance potential of computer systems. However, harnessing the full potential of these systems depends largely on the effectiveness of system software, such as compilers, in exploiting the on-chip parallelism. Additionally, since the amount of parallelism extracted by a compiler is directly influenced by the selection of the algorithm, algorithmic choice also plays a critical role in achieving a high fraction of peak performance. Hence, in the era of multicore computing, it is imperative that we re-evaluate and rethink algorithms for key problem domains. This paper investigates the impact of algorithmic choice on the performance of parallel implementations of the integral knapsack problem on multicore architectures. The study considers two classes of algorithms and several algorithmic variants and evaluates each implementation based on a variety of performance metrics including data locality and sharing, granularity of parallelism and scalability. The paper presents experimental results that show how each performance factor is affected by the selection of algorithm, changes in the input data-set and variations in architectural characteristics such as cache capacity and degree of cache sharing.
Year
DOI
Venue
2012
10.1080/17445760.2011.577432
INTERNATIONAL JOURNAL OF PARALLEL EMERGENT AND DISTRIBUTED SYSTEMS
Keywords
Field
DocType
parallel algorithms, optimisation problems, multicore, data locality, compilers
System software,Locality,Parallel algorithm,Computer science,Parallel computing,Continuous knapsack problem,Compiler,Multiprocessing,Knapsack problem,Multi-core processor,Distributed computing
Journal
Volume
Issue
ISSN
27
1
1744-5760
Citations 
PageRank 
References 
0
0.34
11
Authors
4
Name
Order
Citations
PageRank
Hammad Rashid120.70
Clara Novoa2715.34
Mark McKenney300.34
Apan Qasem412716.34