Difference between revisions of "GPU610/gpuchill"
(→Team Members) |
(→Assignment 1) |
||
| Line 12: | Line 12: | ||
== Progress == | == Progress == | ||
=== Assignment 1 === | === Assignment 1 === | ||
| + | |||
| + | ===Sudoku Brute Force Solver=== | ||
| + | |||
| + | I decided to profile a simple brute force Sudoku solver, found here (https://github.com/regehr/sudoku). The solver uses a simple back tracking algorithm, inserting possible values into cells, iterating through the puzzles thousands of times, until it eventually produces an answer which does not violate any of the rules of Sudoku. The following run of the program uses a puzzle which is specifically made to play against a back tracking algorithm. | ||
| + | |||
| + | Test run with puzzle: | ||
| + | <pre> | ||
| + | Original configuration: | ||
| + | ------------- | ||
| + | | | | | | ||
| + | | | 3| 85| | ||
| + | | 1| 2 | | | ||
| + | ------------- | ||
| + | | |5 7| | | ||
| + | | 4| |1 | | ||
| + | | 9 | | | | ||
| + | ------------- | ||
| + | |5 | | 73| | ||
| + | | 2| 1 | | | ||
| + | | | 4 | 9| | ||
| + | ------------- | ||
| + | 17 entries filled | ||
| + | solution: | ||
| + | ------------- | ||
| + | |987|654|321| | ||
| + | |246|173|985| | ||
| + | |351|928|746| | ||
| + | ------------- | ||
| + | |128|537|694| | ||
| + | |634|892|157| | ||
| + | |795|461|832| | ||
| + | ------------- | ||
| + | |519|286|473| | ||
| + | |472|319|568| | ||
| + | |863|745|219| | ||
| + | ------------- | ||
| + | found 1 solutions | ||
| + | |||
| + | real 0m33.652s | ||
| + | user 0m33.098s | ||
| + | sys 0m0.015s | ||
| + | </pre> | ||
| + | |||
| + | |||
| + | Flat profile: | ||
| + | <pre> | ||
| + | Each sample counts as 0.01 seconds. | ||
| + | % cumulative self self total | ||
| + | time seconds seconds calls s/call s/call name | ||
| + | 46.42 10.04 10.04 622865043 0.00 0.00 check_row | ||
| + | 23.52 15.13 5.09 1 5.09 21.32 solve | ||
| + | 18.26 19.08 3.95 223473489 0.00 0.00 check_col | ||
| + | 10.02 21.25 2.17 100654218 0.00 0.00 check_region | ||
| + | 0.72 21.40 0.16 2 0.08 0.08 print | ||
| + | 0.39 21.49 0.09 frame_dummy | ||
| + | </pre> | ||
| + | |||
| + | I believe that if a GPU was used to enhance this program one would see a great increase of speed. All of the check functions essentially do the same thing, iterating through possible inserted values for any that violate the rules. If one is able to unload all of these iterations onto the GPU then there should be a corresponding increase in speed. | ||
| + | |||
=== Assignment 2 === | === Assignment 2 === | ||
=== Assignment 3 === | === Assignment 3 === | ||
Revision as of 12:28, 14 February 2019
GPU610/DPS915 | Student List | Group and Project Index | Student Resources | Glossary
Contents
GPU n' Chill
Team Members
- Daniel Serpa, Some responsibility
- Abdul Kabia, Some responsibility
- Josh Tardif, Some responsibility
- Andrew Faux, Some responsibility
- Fardad Soleimanloo, Some other responsibility
- ...
Progress
Assignment 1
Sudoku Brute Force Solver
I decided to profile a simple brute force Sudoku solver, found here (https://github.com/regehr/sudoku). The solver uses a simple back tracking algorithm, inserting possible values into cells, iterating through the puzzles thousands of times, until it eventually produces an answer which does not violate any of the rules of Sudoku. The following run of the program uses a puzzle which is specifically made to play against a back tracking algorithm.
Test run with puzzle:
Original configuration: ------------- | | | | | | 3| 85| | 1| 2 | | ------------- | |5 7| | | 4| |1 | | 9 | | | ------------- |5 | | 73| | 2| 1 | | | | 4 | 9| ------------- 17 entries filled solution: ------------- |987|654|321| |246|173|985| |351|928|746| ------------- |128|537|694| |634|892|157| |795|461|832| ------------- |519|286|473| |472|319|568| |863|745|219| ------------- found 1 solutions real 0m33.652s user 0m33.098s sys 0m0.015s
Flat profile:
Each sample counts as 0.01 seconds. % cumulative self self total time seconds seconds calls s/call s/call name 46.42 10.04 10.04 622865043 0.00 0.00 check_row 23.52 15.13 5.09 1 5.09 21.32 solve 18.26 19.08 3.95 223473489 0.00 0.00 check_col 10.02 21.25 2.17 100654218 0.00 0.00 check_region 0.72 21.40 0.16 2 0.08 0.08 print 0.39 21.49 0.09 frame_dummy
I believe that if a GPU was used to enhance this program one would see a great increase of speed. All of the check functions essentially do the same thing, iterating through possible inserted values for any that violate the rules. If one is able to unload all of these iterations onto the GPU then there should be a corresponding increase in speed.
