C POSIX: Analyze a Boggle board using 100% CPU on a quad core. Post: 302358513

Sponsored Content

Top Forums Programming C POSIX: Analyze a Boggle board using 100% CPU on a quad core. Post 302358513 by HeavyJ on Friday 2nd of October 2009 07:55:28 PM

10-02-2009

Registered User

Allow me to make myself very clear:

- The lexicon data structure is immutable.
- I have named it the ADTDAWG - Adamovsky Direct Tracking Directed Acyclic Word Graph, contained in 4 arrays of basic number types.
- The character set I have chosen is 14 of the best English letters.
- There is a thread that is responsible for words that begin with each of the letters in the character set.
- The threads all call the same recursive word-discovery function, and then modify a set of global time-stamps to eliminate the duplicate word problem.
- They will never try to modify the same time-stamp because they are responsible for a different subset of the lexicon.

- I used mutexes, and condition variables to communicate when work on the current board should begin, and when it has finished.

- My question is this - Do POSIX multi-threads really allow for an optimal implementation of a micro-parallel algorithm? Or am I doing something wrong, because I am only using 45% of the power of my Quad-Core, when I should be maxing it out?

Do you really want to look at the code that I wrote? At this point, I have every reason to believe that it will introduce mass confusion. It is well written, but it requires an in-depth knowledge of lexicon data structure optimization.

So you suggest that each core has a private cache? I would love to see a block diagram of how the Core2 layout works, so that I could stop spinning my wheels on this problem.

A single thread can score 1277 of the best 23 boards found to date, each with a score around 10769 points for the TWL06 lexicon.

That means that the recursive function is being called many, many, many times per second. Should this fact be a concern?

HeavyJ

View Public Profile for HeavyJ

Find all posts by HeavyJ

9 More Discussions You Might Find Interesting

1. AIX

cpu and core

Hi, what is concept of core in ibm platform? I want to know how to find out no of core in cpu in aix i.e command how to find out value of core? Wheather any specification is there?

2. AIX

no of core in cpu for aix

is there command which will display no of core per cpu in aix? Regads, Manoj

3. UNIX for Advanced & Expert Users

Distinguishing between CPU and Core

Hi, I want to know if in UNIX is it possible to distinguish between a CPU and a core through any command? Thanks, Vineet

4. Linux Benchmarks

AMD Phenom(tm) 9950 Quad-Core Processor, Ram: 3.6 GB, Foxconn 7da-s and Linux 2.6.26-2-amd64

CPU/Speed: AMD Phenom(tm) 9950 Quad-Core Processor Ram: 3.6 GB Motherboard: Foxconn 7da-s Bus: Cache: Controller: Disk: Load: Kernel: Linux 2.6.26-2-amd64 Kernel ELF?: pgms: ============================================================== BYTE UNIX Benchmarks (Version...

5. AIX

What is a cpu core ?

Hi Friends- What does it mean by 2 cpu cores, 3 cpu cores? Does it mean 2 separate cpus or what is it exactly ? Kindly explain a bit in detail. Thanks panditt

6. Solaris

Share CPU core

Hi, I have 2 physical processor UltraSPARC-T2 with 32 virtual processors I want to execute a perl program on 10 virtual processors. I try prset command, but I don't see a difference. psrset -c "created processor set 2" 1 2 3 4 5 6 7 8 9 10" psrset -b 2 `pgrep program.pl` Maybe...

7. HP-UX

how can i know this processor quad or dual core ?

hi every body i want to know if i have server with hp-ux os if i did "machinfo" i will see no of cpu = for example 16 how can i know this is dual or quad core . thanks

8. Solaris

does a cpu/memory board have a firmware ??

please help does a cpu/memory module have a firmware ?? and do i need to check it before install the cpu/memory module in the motherboard ?? thnx

9. Red Hat

No of CPU's and No of Core

I would like to understand how many number of CPUs and cores do I have on my server based on following out put.. Few observations... Please correct me if I am wrong Since Physical ID is same CPU is singe It has 8 virtual processors Hyper thrading is enabled since no of siblings are...

LEARN ABOUT NETBSD

boggle

BOGGLE(6)							 BSD Games Manual							 BOGGLE(6)

NAME

     boggle -- word search game

SYNOPSIS

     boggle [-bd] [-s seed] [-t time] [-w length] [+ [+]] [boardspec]

DESCRIPTION

     The object of boggle is to find as many words as possible on the Boggle board within the three minute time limit.	A Boggle board is a four
     by four arrangement of Boggle cubes, each side of each cube displaying a letter of the alphabet or `qu'.  Words are formed by finding a
     sequence of cubes (letters) that are in the game's dictionary.  The (N+1)th cube in the word must be horizontally, vertically, or diagonally
     adjacent to the Nth cube.	Cubes cannot be reused.  Words consist solely of lower case letters and must be at least 3 letters long.

     Command line flags can be given to change the rules of the game.

     -b 	Run boggle in batch mode.  A boardspec must also be given.  The dictionary is read from stdin and a list of words appearing in
		boardspec is printed to stdout.

     -d 	Enable debugging output.

     -s seed	Specify a seed seed other than the time of day.

     -t time	Set the time limit for each game from the default 3 minutes to time seconds.

     -w length	Change the minimum word length from 3 letters to length.

     +		This flag allows a cube to be used multiple times, but not in succession.

     ++ 	This flag allows the same cubes to be considered adjacent to itself.

     boardspec	A starting board position can be specified on the command line by listing the board left to right and top to bottom.

     Help is available during play by typing '?'.  More detailed information on the game is given there.

AUTHORS

     Boggle is a trademark of Parker Brothers.

     Barry Brachman

     Dept. of Computer Science

     University of British Columbia

BUGS

     If there are a great many words in the cube the final display of the words may scroll off of the screen.  (On a 25 line screen about 130
     words can be displayed.)

     No word can contain a 'q' that is not immediately followed by a 'u'.

     When using the + or ++ options the display of words found in the board doesn't indicate reused cubes.

     The dictionary that NetBSD installs omits many words that belong in the English language, most notably inflected forms.

BSD
								September 23, 2006							       BSD