Project: Task Division using Multi-threading
1 billion - An estimate on the number of personal computers in the world in June of 2008.1
Even assuming that the average computer is only capable of 0.1 GFLOP2, there is a lot of computing power around the globe that, for the majority of the time, is resting uselessly. If there was some way to harvest this technology at no cost or disconvenience to the owner, how many more problems could we tackle? From seemingly inconsequential tasks such as spell-checking the entire world wide web, to more serious uses, like analyzing gigabytes of information on cancerous DNA strands to find a malignant strain, without doubt there are uses for computing power in the modern world.
This is what inspired the project: the potential power of high performance parallel computing. I wanted to harvest many computers to tackle a problem which perhaps a single processor couldn't on its own. So what problem? Solving a Sudoku Puzzle.
Although your typical Sudoku puzzle (with maybe 60 or so squares missing) can be solved by a typical PC in seconds or less, I could make the computer dumb enough so that the computer couldn't. In essence, I'm "faking it" to make it seem as though solving a Sudoku Puzzle were a daunting task. In fact, just by following a systematic trial and error method, a Sudoku Puzzle with just 10 blanks (one which humans could solve in under a minute) took my personal computer at home over 5 and half hours to solve.
After familiarizing myself with Java's multi-threading capabilities, I was able to effectively "parallelize" my Sudoku solver. After winning first-place and perfect-score awards in PJAS regional, state, and PRSEF competitions, my project inspired a PSC-taught class: Computation Exploration: An Introduction to High Performance Computing.
The project was taken to the next step at PSC where I familiarized myself with MPI and wrote a parallel Sudoku Solver in C as well.
Interested in this project? Let me know!
1 http://en.wikipedia.org/wiki/Personal_computer
2 What is a FLOPS? Yes, FLOPS is singular.
