You normally don't have to limit yourself to the internals of the cache
coherency of the processor. Different processors either have individual
caches that snoops the memory bus, or the different cores have a common
cache. This is noramly only important when developing efficient lock and
wait functions (signals, mutexes, ...) and the implementation is normally
supplied by the OS or the RTL.
The big question here is: How do you rewrite an algorithm to allow the job
to be split between multiple threads. The big problem isn't how the
individual processors or cores keeps track of read or written memory, but
how you can produce large execution blocks that do not need any
synchronization with a different thread. When you can split the job into
lengthy runs without synchronization, then the next optimization step is
to think about locality-of-reference - how you can make maximum use of the
processor cache.
For sorting, you can look into multi-pass merge-sorts. This is an
algorithm used when you don't have enough memory to perform in-memory sort
of all data, so you split it into multiple blocks that you sort. Then you
merge the sorted blocks into a final result.
http://en.wikipedia.org/wiki/Merge_sort
If you want to, you can modify the merge sort to perform quick-sort of
sub-blocks before the merge, instead of running merge sort all the way.
/pwm
On Thu, 7 Aug 2008, Felix Schmidt wrote:
> Dear,
>
> I've some questions to c++ and parallism.
>
> Is there any body who knows something about the parallism algorithm of an intel core duo or core quad processor? How Intel implements shared memory access? How implement intel memory or data locality?
>
> How can I use all my cores for a multithreaded program or algorithm (i.e. parallel merge or quick sort)
>
> Please Help me
>
> Best regards
> pontix
>
> -------------------------------------------------------------------------
> This SF.Net email is sponsored by the Moblin Your Move Developer's challenge
> Build the coolest Linux based applications with Moblin SDK & win great prizes
> Grand prize is a trip for two to an Open Source event anywhere in the world
> http://moblin-contest.org/redirect.php?banner_id=100&url=/
> _______________________________________________
> Dev-cpp-users mailing list
> Dev...@li...
> TO UNSUBSCRIBE: http://www23.brinkster.com/noicys/devcpp/ub.htm
> https://lists.sourceforge.net/lists/listinfo/dev-cpp-users
>
|
