Visit Our UNIX and Linux User Community


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


 
Thread Tools Search this Thread
Top Forums Programming C POSIX: Analyze a Boggle board using 100% CPU on a quad core.
# 1  
Old 10-02-2009
C POSIX: Analyze a Boggle board using 100% CPU on a quad core.

I have written the worlds most advanced lexicon data structure in order to score a Boggle Board using a parallel algorithm.

I ran into a problem. Using mutexes and condition variables did not allow me to use 100% of the CPU resources on my quad core Q9450.

I wonder if the problem is that the worker threads call the same recursive function many thousands, to millions of times per second.

Should each thread have its own identical recursive function defined so that they are not all waiting to access the memory where the function is stored?

Thank You,

HeavyJ
# 2  
Old 10-02-2009
Without seeing the code I can't tell why it's doing what. Each core will have some of its own cache so reading the same memory would not be a problem.
# 3  
Old 10-02-2009
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?
# 4  
Old 10-03-2009
Quote:
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?
Who knows. You have not supplied us with any information that can enable us to help you. What operating system? What compiler and version? Which threading model? 1:1 or MxN or what? What compiler optimisations?

I will say this. POSIX threads would not be my choice for implementing a parallel algorithm.
# 5  
Old 10-03-2009
Ubuntu 9.04

g++

Done in a Terminal.

If you are serious about helping me use 100% CPU, I will send you the code (all of it). Know that I have spent a solid two months developing this work, and it is to my knowledge the most advanced program set of its kind.

Simply put, I will be very unhappy if I never hear from you again, after giving you any part of my code.

I graduated as an aerospace engineer in 2005, and I have never had a job in that industry, so I turned to an area of study with almost no material costs.

I used POSIX because it seems to be incorporated into the C standard. I have a serious problem using any code developed for particular machines or operating systems.

What would your choice be to implement a real micro-parallel algorithm such as my Boggle analysis scheme? Why is POSIX a bad choice for true parallel performance?

Thanks a lot, fpmurphy
# 6  
Old 10-04-2009
Quote:
I used POSIX because it seems to be incorporated into the C standard
POSIX is not part of either C89 or C99 standards.

I am not sure what you mean by a "micro-parallel algorithm". It is a new term to both myself and Google. Perhaps you would be kind enough to explain what you mean by this term.

Meanwhile, I suggest you look at GPGPU, CUDA and OpenCL.
# 7  
Old 10-04-2009
I suppose by standard, I mean that I don't need to download any libraries. I type g++ -pthread.

micro-parallel = algorithm cut up into its smallest independent units, so that the performance will be directly proportional to the number of processor cores up to the maximum number of independent units. Inter-thread communication needs to be close to instantaneous for this relation to hold.

Previous Thread | Next Thread
Test Your Knowledge in Computers #249
Difficulty: Easy
Senator Albert Gore, Jr. authored the High Performance Computing and Communication Act of 1991, creating what Gore referred to as the information superhighway.
True or False?

9 More Discussions You Might Find Interesting

1. 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... (1 Reply)
Discussion started by: parth_buch
1 Replies

2. 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 (2 Replies)
Discussion started by: bahjatm
2 Replies

3. 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 (2 Replies)
Discussion started by: maxim42
2 Replies

4. 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... (8 Replies)
Discussion started by: falloutsam
8 Replies

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 (4 Replies)
Discussion started by: deshaipet
4 Replies

6. 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... (0 Replies)
Discussion started by: migracho
0 Replies

7. 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 (1 Reply)
Discussion started by: vineetd
1 Replies

8. AIX

no of core in cpu for aix

is there command which will display no of core per cpu in aix? Regads, Manoj (1 Reply)
Discussion started by: manoj.solaris
1 Replies

9. 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? (1 Reply)
Discussion started by: manoj.solaris
1 Replies

Featured Tech Videos