Utilizing GPGPUs for design validation with a modified Ant Colony Optimization

Author

Li, Min ; Gent, Kelson ; Hsiao, Michael S.

Author_Institution

Bradley Dept. of Electr. & Comput. Eng, Virginia Tech, Blacksburg, VA, USA

fYear

2011

fDate

9-11 Nov. 2011

Firstpage

128

Lastpage

135

Abstract

In this paper, we propose a novel parallel state justification tool, GACO, utilizing Ant Colony Optimization (ACO) on Graphical Processing Units (GPU). With the high degree of parallelism supported by the GPU, GACO is capable of launching a large number of artificial ants to search for the target state. A novel parallel simulation technique, utilizing partitioned navigation tracks as guides during the search, is proposed to achieve extremely high computation efficiency for state justification. We present the results on a GPU platform from NVIDIA (a GeForce GTX 285 graphics card) that demonstrate a speedup of up to 228× compared to deterministic methods and a speedup of up to 40× over previous state-of-the-art heuristic based serial tools.

Keywords

graphics processing units; integrated circuit design; optimisation; GPGPU utilization; GeForce GTX 285 graphics card; NVIDIA; artificial ants; design validation; extremely high computation efficiency; general purpose computation on graphics processing unit; modified ant colony optimization; parallel state justification tool; partitioned navigation tracks; Computational modeling; Graphics processing unit; Instruction sets; Integrated circuit modeling; Kernel; Logic gates; Synchronization; Ant Colony Optimization; Compute Unified Device Architecture (CUDA); Design Validation; General Purpose Computation on Graphics Processing Unit (GPGPU); Single Instruction Multiple Threads (SIMT);

fLanguage

English

Publisher

ieee

Conference_Titel

High Level Design Validation and Test Workshop (HLDVT), 2011 IEEE International

Conference_Location

Napa Valley, CA

ISSN

1552-6674

Print_ISBN

978-1-4577-1744-4

Type

conf

DOI

10.1109/HLDVT.2011.6113988

Filename

6113988