liu.seSearch for publications in DiVA
Change search
Link to record
Permanent link

Direct link
BETA
Suri, Bharath
Publications (2 of 2) Show all publications
Suri, B., Bordoloi, U. D. & Eles, P. (2012). A Scalable GPU-Based Approach to Accelerate the Multiple-Choice Knapsack Problem. In: Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012.: . Paper presented at Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012. (pp. 1126-1129). IEEE
Open this publication in new window or tab >>A Scalable GPU-Based Approach to Accelerate the Multiple-Choice Knapsack Problem
2012 (English)In: Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012., IEEE , 2012, p. 1126-1129Conference paper, Published paper (Refereed)
Abstract [en]

Variants of the 0-1 knapsack problem manifest themselves at the core of several system-level optimization problems. The running times of such system-level optimization techniques are adversely affected because the knapsack problem is NP-hard. In this paper, we propose a new GPU-based approach to accelerate the multiple-choice knapsack problem, which is a general version of the 0-1 knapsack problem. Apart from exploiting the parallelism offered by the GPUs, we also employ a variety of GPU-specific optimizations to further accelerate the running times of the knapsack problem. Moreover, our technique is scalable in the sense that even when running large instances of the multiple-choice knapsack problems, we can efficiently utilize the GPU compute resources and memory bandwidth to achieve significant speedups.

Place, publisher, year, edition, pages
IEEE, 2012
Series
Design, Automation and Test in Europe, ISSN 1530-1591
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-72206 (URN)10.1109/DATE.2012.6176665 (DOI)978-1-4577-2145-8 (ISBN)978-3-9810801-8-6 (ISBN)
Conference
Design Automation and Test in Europe (DATE12) (short paper), Dresden, Germany, March 12-16, 2012.
Available from: 2011-11-22 Created: 2011-11-22 Last updated: 2014-11-14
Bordoloi, U. D., Suri, B., Nunna, S., Chakraborty, S., Eles, P. & Peng, Z. (2012). Customizing Instruction Set Extensible Reconfigurable Processors using GPUs. In: 25th International Conferennce on VLSI Design, Hyderabad, India, January 07-11, 2012.: . Paper presented at 25th International Conferennce on VLSI Design, Hyderabad, India, January 07-11, 2012. (pp. 418-423). IEEE
Open this publication in new window or tab >>Customizing Instruction Set Extensible Reconfigurable Processors using GPUs
Show others...
2012 (English)In: 25th International Conferennce on VLSI Design, Hyderabad, India, January 07-11, 2012., IEEE , 2012, p. 418-423Conference paper, Published paper (Refereed)
Abstract [en]

Many reconfigurable processors allow their instruction sets to be tailored according to the performance requirements of target applications. They have gained immense popularity in recent years because of this flexibility of adding custom instructions. However, most design automation algorithms for instruction set customization (like enumerating and selecting the optimal set of custom instructions) are computationally intractable. As such, existing tools to customize instruction sets of extensible processors rely on approximation methods or heuristics. In contrast to such traditional approaches, we propose to use GPUs (Graphics Processing Units) to efficiently solve computationally expensive algorithms in the design automation tools for extensible processors. To demonstrate our idea, we choose a custom instruction selection problem and accelerate it using CUDA (CUDA is a GPU computing engine). Our CUDA implementation is devised to maximize the achievable speedups by various optimizations like exploiting on-chip shared memory and register usage. Experiments conducted on well known benchmarks show significant speedups over sequential CPU implementations as well as over multi-core implementations.

Place, publisher, year, edition, pages
IEEE, 2012
Series
VLSI Design : Proceedings / the ... International Conference on VLSI Design, ISSN 1063-9667
National Category
Engineering and Technology
Identifiers
urn:nbn:se:liu:diva-72205 (URN)978-0-7695-4638-4 (ISBN)978-1-4673-0438-2 (ISBN)
Conference
25th International Conferennce on VLSI Design, Hyderabad, India, January 07-11, 2012.
Available from: 2011-11-22 Created: 2011-11-22 Last updated: 2013-09-10
Organisations

Search in DiVA

Show all publications