FAQ
I have a math algorithm that I'm trying to run parts of in *parallel*.

I read Effective Go, and it said this:

http://golang.org/doc/effective_go.html#parallel

"The current implementation of the Go runtime will not parallelize this
code by default. It dedicates only a single core to user-level processing.
An arbitrary number of goroutines can be blocked in system calls, but by
default only one can be executing user-level code at any time. It should be
smarter and one day it will be smarter, but until it is if you want CPU
parallelism you must tell the run-time how many goroutines you want
executing code simultaneously. There are two related ways to do this.
Either run your job with environment variable GOMAXPROCS set to the number
of cores to use or import the runtime package and call
runtime.GOMAXPROCS(NCPU). A helpful value might be runtime.NumCPU(), which
reports the number of logical CPUs on the local machine. Again, this
requirement is expected to be retired as the scheduling and run-time
improve.

Be sure not to confuse the ideas of concurrency—structuring a program as
independently executing components—and parallelism—executing calculations
in parallel for efficiency on multiple CPUs. Although the concurrency
features of Go can make some problems easy to structure as parallel
computations, Go is a concurrent language, not a parallel one, and not all
parallelization problems fit Go's model. For a discussion of the
distinction, see the talk cited in this blog post
<http://blog.golang.org/2013/01/concurrency-is-not-parallelism.html>."

1) Currently, will Go allow me to run in parallel the following code
(excuse formatting)?

func segint(b uint32) {

   seg[b] = 0 // set every byte bit to prime (0)

}

func ressieve(r uint32, Kn uint32) {

     biti := byte(1 << uint32(r)) // set the ith residue track bit mask

     row := r * pcnt // set address to ith row in
next[]

     for j := uint32(0); j < pcnt; j++ {// for each prime <= sqrt(N) for
restrack

       if (next[row+j] < uint64(Kn)) { // if 1st mult resgroup index <= seg
size

k := uint32(next[row+j]) // get its resgroup value

prime := primes[j] // get the prime

         for k=k; k < Kn; k += prime { // for each primeth byte < segment
size

   seg[k] |= biti } // set ith residue in byte as nonprime

         next[row+j] = uint64(k - Kn) // 1st resgroup in next eligible
segment

       } else {next[row+j] -= uint64(Kn) }// if 1st mult resgroup index >
seg size

     }

}

func countprimes(byt byte) {

   primecnt += uint64(pbits[byt]) // count the '0' bits as primes

}

func segsieve(Kn uint32) {

   for b := uint32(0); b < Kn; b++ {// for all the bytes in a segment

     go segint(b) } // set every byte bit to prime (0)

   for r := uint32(0); r < rescnt; r++ { // for each restrack in
resgroup|byte

     go ressieve(r,Kn) } // mark prime multiples on res tracks

   for _, byt := range seg[:Kn] { // for the Kn resgroup bytes

     go countprimes(byt) } // count the '0' bits as prime

}

When I run this code without using go routines I get the correct answer,
but when I experimented using go routines on the functions inside segsieve
I get (as expected) incorrect results using much more time (that wasn't
expected). When I tried making just one function at a time use 'go'
routines I still get incorrect results still taking a lot of time.

The EG example uses channels to communicate, but I don't see why (yet) that
necessity.

So is it even theoretically possible to perform this code in parallel (with
go 1.3) that will be faster than the none parallel version?

2) The above statement in EG alluded to things getting better for parallel
operations in the future. Since I want (nice, easly, simpel) true parallel
operations should I wait to see where Go goes on this or take the time to
figure it out now because it ain't really gonna change?

Here is the full code. Remove the 'go' statements inside segsieve and you
get the correct results.

http://play.golang.org/p/FP6PQnGgH2



--
You received this message because you are subscribed to the Google Groups "golang-nuts" group.
To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
For more options, visit https://groups.google.com/d/optout.

Search Discussions

  • Dan Kortschak at Jul 2, 2014 at 8:23 pm
    Are you sure the three functions that you are running as goroutines can be done concurrently. It doesn't look like that to me - it looks like they must be sequential. Even if they can be, you have no synchronisation between them.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jabari Zakiya at Jul 2, 2014 at 8:44 pm
    Hi,

    Yes, all three routines can be run in parallel, and I have run the C++
    equivalent in parallel using OpenMP -- http://openmp.org/wp/.

    The first function -- segint -- just sets Kn number of bytes in the seg[]
    array to zero. These are completely independent operations which
    communicate no information between them.

    Is there some Go function that zeros' out memory efficiently?

    The last function -- countprimes -- takes each byte in the seg[] array and
    determines the number of primes (0s) in each byte and adds each of those
    values to primecnt. These are independent operations, and I expected that
    primecnt would probably be incorrect, but I didn't expect it to take so
    much longer than the serial version.

    The most (relatively) complex function -- ressieve -- also performs
    independent operations for each value of 'r' it is passed.

    What surprised me was that even if done concurrently (not in parallel) I
    didn't expect it to take so much more time ( x times more for a given value
    N compared to serial version).

    On Wednesday, July 2, 2014 4:24:05 PM UTC-4, kortschak wrote:

    Are you sure the three functions that you are running as goroutines can be
    done concurrently. It doesn't look like that to me - it looks like they
    must be sequential. Even if they can be, you have no synchronisation
    between them.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Andrey mirtchovski at Jul 2, 2014 at 8:53 pm
    rather than:

    for b := uint32(0); b < Kn; b++ { // for all the bytes in a segment
         go segint(b)
    } // set every byte bit to prime (0)

    can you try for each of your goroutines:

    go func() {
         for b := uint32(0); b < Kn; b++ { // for all the bytes in a segment
             segint(b)
         } // set every byte bit to prime (0)
    }()

    btw, all allocated memory is zeroed out in go.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jabari Zakiya at Jul 2, 2014 at 9:16 pm
    I ran this code only on this function (I left the other two funcs inside
    segsieve as non-go routines)
    and it brought the times down to be comparable without using go routines.

    However, the program still produced an incorrect prime count (the last
    prime value was correct for
    N = 1000000000), which means all the bytes in the seg[] array don't appear
    to be zeroed out each
    time segsieve is run.

    I'll continue to test it to see what is happening.
    On Wednesday, July 2, 2014 4:53:41 PM UTC-4, andrey mirtchovski wrote:

    rather than:

    for b := uint32(0); b < Kn; b++ { // for all the bytes in a segment
    go segint(b)
    } // set every byte bit to prime (0)

    can you try for each of your goroutines:

    go func() {
    for b := uint32(0); b < Kn; b++ { // for all the bytes in a segment
    segint(b)
    } // set every byte bit to prime (0)
    }()

    btw, all allocated memory is zeroed out in go.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jason Woods at Jul 2, 2014 at 9:34 pm
    Hi
    On 2 Jul 2014, at 22:16, Jabari Zakiya wrote:

    I ran this code only on this function (I left the other two funcs inside segsieve as non-go routines)
    and it brought the times down to be comparable without using go routines.

    However, the program still produced an incorrect prime count (the last prime value was correct for
    N = 1000000000), which means all the bytes in the seg[] array don't appear to be zeroed out each
    time segsieve is run.
    The go starts another routine that is NOT guaranteed to finish by the time the current routine moves forwards. So the segsieve start running before the zeroing completes.

    The same applies to all of the others. You must synchronise the go routine you call with your current routine before any data can be shared or assumptions made about the state if the go routines.

    Think how this would work with people. You send someone off to clear zeros. Then you move onto next step to modify them... Hang on she hasn't finished zeroing, you stop and wait (synchronise). Even if she had finished you would stop and check (synchronise).

    In parallel processing you must join together (synchronise) to share data, or you're in a whole world of undefined behaviour. As mentioned you may want to research parallelism.

    Hope that makes sense

    Jason
    I'll continue to test it to see what is happening.
    On Wednesday, July 2, 2014 4:53:41 PM UTC-4, andrey mirtchovski wrote:
    rather than:

    for b := uint32(0); b < Kn; b++ { // for all the bytes in a segment
    go segint(b)
    } // set every byte bit to prime (0)

    can you try for each of your goroutines:

    go func() {
    for b := uint32(0); b < Kn; b++ { // for all the bytes in a segment
    segint(b)
    } // set every byte bit to prime (0)
    }()

    btw, all allocated memory is zeroed out in go.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jonathan Lawlor at Jul 2, 2014 at 8:54 pm

    The first function -- segint -- just sets Kn number of bytes in the seg[]
    array to zero. These are completely independent operations which
    communicate no information between them.
    It is always zero after initialization:
    http://golang.org/ref/spec#The_zero_value

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Andrewchamberss at Jul 2, 2014 at 9:09 pm

    The first function -- segint -- just sets Kn number of bytes in the seg[]
    array to zero. These are completely independent operations which
    communicate no information between them.
    You need to have some... i.e. to signal when the job is complete, otherwise
    it is a race condition. Also, having a go routine to zero a single thing is
    not efficient anyway.

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Dan Kortschak at Jul 2, 2014 at 9:32 pm
    OK, each step of the three parts can be run in parallel, but you don't synchronise the parts. The easiest way to do that is make them sequential and make each test concurrent.

    This gives the same results as your non-concurrent approach and shows what I mean.

    http://play.golang.org/p/1LyHdDGwg8

    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Jabari Zakiya at Jul 6, 2014 at 8:34 pm

    On Wednesday, July 2, 2014 5:32:52 PM UTC-4, kortschak wrote:
    OK, each step of the three parts can be run in parallel, but you don't
    synchronise the parts. The easiest way to do that is make them sequential
    and make each test concurrent.

    This gives the same results as your non-concurrent approach and shows what
    I mean.

    http://play.golang.org/p/1LyHdDGwg8
    OK, I'm back.

    I ran the code at http://play.golang.org/p/1LyHdDGwg8 and it didn't give
    the correct number of primes for N = 500,000, though it gave the correct
    lastprime value of 499979.

    The code gave the number of primes as 653,774, but the correct number is
    41,538, an order of magnitude too many. This means the code wasn't
    eliminating the nonprimes correctly.

    But beyond that, I have no idea what the code is doing, and why. :-(

    It would be extremely helpful to explain the code so I can understand what
    its trying to do, why, and the technique and language idiom being used.

    In my first post I basically asked these two questions:

    1) Is it theoretically possible to perform this code in parallel (with go
    1.3)?
    2) Will it be faster than the non-parallel version?

    OpenMP has some nice video tutorials to help newbies get up and running
    with it.

    https://www.youtube.com/watch?v=nE-xN4Bf8XI&list=PLLX-Q6B8xqZ8n8bwjGdzBJ25X2utwnoEG&index=22

    I would encourage Go to provide some resources like this just around
    writing real code for concurrent AND parallel programming.


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • James Bardin at Jul 2, 2014 at 8:38 pm
    you have data races; run your code with -race
    On Wednesday, July 2, 2014 4:10:27 PM UTC-4, Jabari Zakiya wrote:

    I have a math algorithm that I'm trying to run parts of in *parallel*.

    I read Effective Go, and it said this:

    http://golang.org/doc/effective_go.html#parallel

    "The current implementation of the Go runtime will not parallelize this
    code by default. It dedicates only a single core to user-level processing.
    An arbitrary number of goroutines can be blocked in system calls, but by
    default only one can be executing user-level code at any time. It should be
    smarter and one day it will be smarter, but until it is if you want CPU
    parallelism you must tell the run-time how many goroutines you want
    executing code simultaneously. There are two related ways to do this.
    Either run your job with environment variable GOMAXPROCS set to the
    number of cores to use or import the runtime package and call
    runtime.GOMAXPROCS(NCPU). A helpful value might be runtime.NumCPU(),
    which reports the number of logical CPUs on the local machine. Again, this
    requirement is expected to be retired as the scheduling and run-time
    improve.

    Be sure not to confuse the ideas of concurrency—structuring a program as
    independently executing components—and parallelism—executing calculations
    in parallel for efficiency on multiple CPUs. Although the concurrency
    features of Go can make some problems easy to structure as parallel
    computations, Go is a concurrent language, not a parallel one, and not all
    parallelization problems fit Go's model. For a discussion of the
    distinction, see the talk cited in this blog post
    <http://blog.golang.org/2013/01/concurrency-is-not-parallelism.html>."

    1) Currently, will Go allow me to run in parallel the following code
    (excuse formatting)?

    func segint(b uint32) {

    seg[b] = 0 // set every byte bit to prime (0)

    }

    func ressieve(r uint32, Kn uint32) {

    biti := byte(1 << uint32(r)) // set the ith residue track bit
    mask

    row := r * pcnt // set address to ith row in
    next[]

    for j := uint32(0); j < pcnt; j++ {// for each prime <= sqrt(N) for
    restrack

    if (next[row+j] < uint64(Kn)) { // if 1st mult resgroup index <= seg
    size

    k := uint32(next[row+j]) // get its resgroup value

    prime := primes[j] // get the prime

    for k=k; k < Kn; k += prime { // for each primeth byte < segment
    size

    seg[k] |= biti } // set ith residue in byte as nonprime

    next[row+j] = uint64(k - Kn) // 1st resgroup in next eligible
    segment

    } else {next[row+j] -= uint64(Kn) }// if 1st mult resgroup index >
    seg size

    }

    }

    func countprimes(byt byte) {

    primecnt += uint64(pbits[byt]) // count the '0' bits as primes

    }

    func segsieve(Kn uint32) {

    for b := uint32(0); b < Kn; b++ {// for all the bytes in a segment

    go segint(b) } // set every byte bit to prime (0)

    for r := uint32(0); r < rescnt; r++ { // for each restrack in
    resgroup|byte

    go ressieve(r,Kn) } // mark prime multiples on res tracks

    for _, byt := range seg[:Kn] { // for the Kn resgroup bytes

    go countprimes(byt) } // count the '0' bits as prime

    }

    When I run this code without using go routines I get the correct answer,
    but when I experimented using go routines on the functions inside segsieve
    I get (as expected) incorrect results using much more time (that wasn't
    expected). When I tried making just one function at a time use 'go'
    routines I still get incorrect results still taking a lot of time.

    The EG example uses channels to communicate, but I don't see why (yet)
    that necessity.

    So is it even theoretically possible to perform this code in parallel
    (with go 1.3) that will be faster than the none parallel version?

    2) The above statement in EG alluded to things getting better for parallel
    operations in the future. Since I want (nice, easly, simpel) true parallel
    operations should I wait to see where Go goes on this or take the time to
    figure it out now because it ain't really gonna change?

    Here is the full code. Remove the 'go' statements inside segsieve and you
    get the correct results.

    http://play.golang.org/p/FP6PQnGgH2


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.
  • Egon at Jul 2, 2014 at 8:39 pm
    Firstly, your code is very hard to read, which means it's unlikely that
    someone will try to plow through the code out of their time. I'm not
    familiar with the algorithm, but I'm guessing that it might be
    parallelizable, regarding how to do it, search for papers describing
    similar parallel algorithms and then try to figure out a methodology for
    doing so.

    I'm guessing you are getting the wrong result because of some sort of race
    condition. Run it with the race
    detector. http://blog.golang.org/race-detector

    It also seems that you don't have a good grasp on parallelization, so you
    should study it. I currently can't remember any nice resources, but a
    google search for "parallel algorithm" comes up with several resources. The
    problems associated are similar to using
    semaphores http://greenteapress.com/semaphores/ but it really doesn't tell
    how to design a good parallel algorithm. This topic is not something you
    can easily learn via forums.

    + egon
    On Wednesday, 2 July 2014 23:10:27 UTC+3, Jabari Zakiya wrote:

    I have a math algorithm that I'm trying to run parts of in *parallel*.

    I read Effective Go, and it said this:

    http://golang.org/doc/effective_go.html#parallel

    "The current implementation of the Go runtime will not parallelize this
    code by default. It dedicates only a single core to user-level processing.
    An arbitrary number of goroutines can be blocked in system calls, but by
    default only one can be executing user-level code at any time. It should be
    smarter and one day it will be smarter, but until it is if you want CPU
    parallelism you must tell the run-time how many goroutines you want
    executing code simultaneously. There are two related ways to do this.
    Either run your job with environment variable GOMAXPROCS set to the
    number of cores to use or import the runtime package and call
    runtime.GOMAXPROCS(NCPU). A helpful value might be runtime.NumCPU(),
    which reports the number of logical CPUs on the local machine. Again, this
    requirement is expected to be retired as the scheduling and run-time
    improve.

    Be sure not to confuse the ideas of concurrency—structuring a program as
    independently executing components—and parallelism—executing calculations
    in parallel for efficiency on multiple CPUs. Although the concurrency
    features of Go can make some problems easy to structure as parallel
    computations, Go is a concurrent language, not a parallel one, and not all
    parallelization problems fit Go's model. For a discussion of the
    distinction, see the talk cited in this blog post
    <http://blog.golang.org/2013/01/concurrency-is-not-parallelism.html>."

    1) Currently, will Go allow me to run in parallel the following code
    (excuse formatting)?

    func segint(b uint32) {

    seg[b] = 0 // set every byte bit to prime (0)

    }

    func ressieve(r uint32, Kn uint32) {

    biti := byte(1 << uint32(r)) // set the ith residue track bit
    mask

    row := r * pcnt // set address to ith row in
    next[]

    for j := uint32(0); j < pcnt; j++ {// for each prime <= sqrt(N) for
    restrack

    if (next[row+j] < uint64(Kn)) { // if 1st mult resgroup index <= seg
    size

    k := uint32(next[row+j]) // get its resgroup value

    prime := primes[j] // get the prime

    for k=k; k < Kn; k += prime { // for each primeth byte < segment
    size

    seg[k] |= biti } // set ith residue in byte as nonprime

    next[row+j] = uint64(k - Kn) // 1st resgroup in next eligible
    segment

    } else {next[row+j] -= uint64(Kn) }// if 1st mult resgroup index >
    seg size

    }

    }

    func countprimes(byt byte) {

    primecnt += uint64(pbits[byt]) // count the '0' bits as primes

    }

    func segsieve(Kn uint32) {

    for b := uint32(0); b < Kn; b++ {// for all the bytes in a segment

    go segint(b) } // set every byte bit to prime (0)

    for r := uint32(0); r < rescnt; r++ { // for each restrack in
    resgroup|byte

    go ressieve(r,Kn) } // mark prime multiples on res tracks

    for _, byt := range seg[:Kn] { // for the Kn resgroup bytes

    go countprimes(byt) } // count the '0' bits as prime

    }

    When I run this code without using go routines I get the correct answer,
    but when I experimented using go routines on the functions inside segsieve
    I get (as expected) incorrect results using much more time (that wasn't
    expected). When I tried making just one function at a time use 'go'
    routines I still get incorrect results still taking a lot of time.

    The EG example uses channels to communicate, but I don't see why (yet)
    that necessity.

    So is it even theoretically possible to perform this code in parallel
    (with go 1.3) that will be faster than the none parallel version?

    2) The above statement in EG alluded to things getting better for parallel
    operations in the future. Since I want (nice, easly, simpel) true parallel
    operations should I wait to see where Go goes on this or take the time to
    figure it out now because it ain't really gonna change?

    Here is the full code. Remove the 'go' statements inside segsieve and you
    get the correct results.

    http://play.golang.org/p/FP6PQnGgH2


    --
    You received this message because you are subscribed to the Google Groups "golang-nuts" group.
    To unsubscribe from this group and stop receiving emails from it, send an email to golang-nuts+unsubscribe@googlegroups.com.
    For more options, visit https://groups.google.com/d/optout.

Related Discussions

Discussion Navigation
viewthread | post
Discussion Overview
groupgolang-nuts @
categoriesgo
postedJul 2, '14 at 8:10p
activeJul 6, '14 at 8:34p
posts12
users8
websitegolang.org

People

Translate

site design / logo © 2021 Grokbase