How about a Sudoku high performance programming challenge?

Programs which generate, solve, and analyze Sudoku puzzles

Postby ovaltrade » Fri Sep 23, 2005 2:20 pm

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

Postby tbailey » Sun Sep 25, 2005 10:48 am

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

Postby ovaltrade » Sun Sep 25, 2005 2:23 pm

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

Postby tbailey » Sun Sep 25, 2005 11:39 pm

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

Postby ovaltrade » Mon Sep 26, 2005 1:46 pm

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