## How about a Sudoku high performance programming challenge?

Programs which generate, solve, and analyze Sudoku puzzles
What is your definition of cycle?

An example will clarify. Let's assume a Pentium 4 processor is running at a (clock) speed of 3.2 gigahertz. This means this CPU uses (consumes) 3,200,000,000 clock cycles per second. If all machine instructions could execute in a single cycle each, this CPU could execute 3,200,000,000 machine instructions per second. In a 1.6 gigahertz similar processor, it would require 2 seconds to execute the same 3,200,000,000 machine instructions.

Of course, there are many machine instructions which require more than a cycle to execute like the integer division instruction or the floating point square root instruction. Therefore, the overall performance of a program can be more accurately measured in cycles because this measurement is independant of the clock speed of the processor. Regardless of the clock speed, a typical machine instruction will consume the same amount of cycles when executed on the same type and brand of computer.

So, part of the optimization process in the art of programming, the clever selection of specific machine instructions to achieve a given task is crucial for the creation of the fastest programs. The fastest programs consumes the smallest amount of cycles.
ovaltrade

Posts: 19
Joined: 03 September 2005

### Example

So, since I have a computer with a 2Ghz processor, it would be processing instructions at approximately 2,000,000,000 cycles per second (2 x 109)?
tbailey

Posts: 3
Joined: 22 September 2005

So, since I have a computer with a 2Ghz processor, it would be processing instructions at approximately 2,000,000,000 cycles per second (2 x 109)?

The 2Ghz means 2,000,000,000 cycles per second. Assuming it is a Pentium IV (P4), this processor can execute 125,000,000 multiply instructions/sec (each multiply requires 16 cycles) or 46,511,627 square root instructions/sec (each requires 43 cycles) or 4,000,000,000 addition instructions/sec (each requires half a cycle only).

The P4 can also execute some instructions in parallel execution units like the additions/subtracts (2 at the same time) but some constraints exist which prevent to achieve the theoratical maximum performances.
ovaltrade

Posts: 19
Joined: 03 September 2005

### Process

Sounds like you know what you're talking about! What process do you use in programming to define the approximate amount of cycles it takes for a particular program, to solve a sudoku puzzle?

I'm currently using the Visual Basic for DOS language.
tbailey

Posts: 3
Joined: 22 September 2005

What process do you use in programming to define the approximate amount of cycles it takes for a particular program, to solve a sudoku puzzle?

Easy because I use the assembler instruction:

RDTSC ;Read Time Stamp Counter into EDX:EAX. This is the amount of
;cycles since the machine is powered up

...Then I save the value of EDX:EAX (64 bits) into memory.

Next, I solve the Sudoku.

As soon as the solution is found, I read again the 64-bit time stamp counter and subtract the memory saved value for the differential.
ovaltrade

Posts: 19
Joined: 03 September 2005

Previous

Return to Software