SCHEDULE: NOV 10-16, 2012
When viewing the Technical Program schedule, on the far righthand side is a column labeled "PLANNER." Use this planner to build your own schedule. Once you select an event and want to add it to your personal schedule, just click on the calendar icon of your choice (outlook calendar, ical calendar or google calendar) and that event will be stored there. As you select events in this manner, you will have your own schedule to guide you through the week.
High Performance GPU Accelerated TSP Solver
SESSION: Research Poster Reception
EVENT TYPE: Posters and Electronic Posters
TIME: 5:15PM - 7:00PM
SESSION CHAIR: Torsten Hoefler
AUTHOR(S):Kamil Rocki, Reiji Suda
ROOM:East Entrance
ABSTRACT:
GPU usage greatly decreases the time needed to optimize the route, however requires a complicated and well tuned implementation. With the increasing problem size, the time spent on comparing the graph edges grows significantly. We used instances from the TSPLIB library for for testing and our results show that by using our GPU algorithm, the time needed to perform a simple local search operation can be decreased approximately 5 to 45 times compared to parallel CPU code implementation using 6 cores. The experimental studies have shown that the optimization algorithm using the GPU local search converges from up to 300 times faster on average compared to the sequential CPU version, depending on the problem size. The main contributions of this work are the problem division scheme exploiting data locality which allows to solve arbitrarily big problem instances using GPU and the parallel implementation of the algorithm itself.
Chair/Author Details:
Torsten Hoefler (Chair) - ETH Zurich
Kamil Rocki - University of Tokyo
Reiji Suda - University of Tokyo
Click here to download .ics calendar file
Click here to download .vcs calendar file
Click here to add event to your Google Calendar
High Performance GPU Accelerated TSP Solver
SESSION: Research Poster Reception
EVENT TYPE:
TIME: 5:15PM - 7:00PM
SESSION CHAIR: Torsten Hoefler
AUTHOR(S):Kamil Rocki, Reiji Suda
ROOM:East Entrance
ABSTRACT:
GPU usage greatly decreases the time needed to optimize the route, however requires a complicated and well tuned implementation. With the increasing problem size, the time spent on comparing the graph edges grows significantly. We used instances from the TSPLIB library for for testing and our results show that by using our GPU algorithm, the time needed to perform a simple local search operation can be decreased approximately 5 to 45 times compared to parallel CPU code implementation using 6 cores. The experimental studies have shown that the optimization algorithm using the GPU local search converges from up to 300 times faster on average compared to the sequential CPU version, depending on the problem size. The main contributions of this work are the problem division scheme exploiting data locality which allows to solve arbitrarily big problem instances using GPU and the parallel implementation of the algorithm itself.
Chair/Author Details:
Torsten Hoefler (Chair) - ETH Zurich
Kamil Rocki - University of Tokyo
Reiji Suda - University of Tokyo
Click here to download .ics calendar file