Parallel calculations
Many programming languages allow you to specify computations to be run in parallel. While Concurrent computing is focused on concurrency, the purpose of this task is to distribute time-consuming calculations on as many CPUs as possible.
Assume we have a collection of numbers, and want to find the one with the largest minimal prime factor (that is, the one that contains relatively large factors). To speed up the search, the factorization should be done in parallel using separate threads or processes, to take advantage of multi-core CPUs.
Show how this can be formulated in your language. Parallelize the factorization of those numbers, then search the returned list of numbers and factors for the largest minimal factor, and return that number and its prime factors.
For the prime number decomposition you may use the solution of the Prime decomposition task.
PicoLisp
The 'later' function is used in PicoLisp to start parallel computations. The following solution calls 'later' on the 'factor' function from Prime decomposition#PicoLisp, and then 'wait's until all results are available: <lang PicoLisp>(let Lst
(mapcan '((N) (later (cons) # When done, (cons N (factor N)) ) ) # return the number and its factors (quote 188573867500151328137405845301 # Process a collection of 12 numbers 3326500147448018653351160281 979950537738920439376739947 2297143294659738998811251 136725986940237175592672413 3922278474227311428906119 839038954347805828784081 42834604813424961061749793 2651919914968647665159621 967022047408233232418982157 2532817738450130259664889 122811709478644363796375689 ) ) (wait NIL (full Lst)) # Wait until all computations are done (maxi '((L) (apply min L)) Lst) ) # Result: Number in CAR, factors in CDR</lang>
Output:
-> (2532817738450130259664889 6531761 146889539 2639871491)
Tcl
With Tcl, it is necessary to explicitly perform computations in other threads because each thread is strongly isolated from the others (except for inter-thread messaging). However, it is entirely practical to wrap up the communications so that only a small part of the code needs to know very much about it.
<lang tcl>package require Tcl 8.6 package require Thread
- Pooled computation engine; runs event loop internally
namespace eval pooled {
variable poolSize 3; # Needs to be tuned to system size
proc computation {computationDefinition entryPoint values} {
variable result variable poolSize # Add communication shim append computationDefinition [subst -nocommands { proc poolcompute {value target} { set outcome [$entryPoint \$value] set msg [list set ::pooled::result(\$value) \$outcome] thread::send -async \$target \$msg } }]
# Set up the pool set pool [tpool::create -initcmd $computationDefinition \ -maxworkers $poolSize]
# Prepare to receive results unset -nocomplain result array set result {}
# Dispatch the computations foreach value $values { tpool::post $pool [list poolcompute $value [thread::id]] }
# Wait for results while {[array size result] < [llength $values]} {vwait pooled::result}
# Dispose of the pool tpool::release $pool
# Return the results return [array get result]
}
}</lang> This is the definition of the prime factorization engine: <lang tcl># Code for computing the prime factors of a number set computationCode {
namespace eval prime {
variable primes [list 2 3 5 7 11] proc restart {} { variable index -1 variable primes variable current [lindex $primes end] }
proc get_next_prime {} { variable primes variable index if {$index < [llength $primes]-1} { return [lindex $primes [incr index]] } variable current while 1 { incr current 2 set p 1 foreach prime $primes { if {$current % $prime} {} else { set p 0 break } } if {$p} { return [lindex [lappend primes $current] [incr index]] } } }
proc factors {num} { restart set factors [dict create] for {set i [get_next_prime]} {$i <= $num} {} { if {$num % $i == 0} { dict incr factors $i set num [expr {$num / $i}] continue } elseif {$i*$i > $num} { dict incr factors $num break } else { set i [get_next_prime] } } return $factors }
}
}
- The values to be factored
set values {
188573867500151328137405845301 3326500147448018653351160281 979950537738920439376739947 2297143294659738998811251 136725986940237175592672413 3922278474227311428906119 839038954347805828784081 42834604813424961061749793 2651919914968647665159621 967022047408233232418982157 2532817738450130259664889 122811709478644363796375689
}</lang> Putting everything together: <lang tcl># Do the computation, getting back a dictionary that maps
- values to its results (itself an ordered dictionary)
set results [pooled::computation $computationCode prime::factors $values]
- Find the maximum minimum factor with sorting magic
set best [lindex [lsort -integer -stride 2 -index {1 0} $results] end-1]
- Print in human-readable form
proc renderFactors {factorDict} {
dict for {factor times} $factorDict {
lappend v {*}[lrepeat $times $factor]
} return [join $v "*"]
} puts "$best = [renderFactors [dict get $results $best]]"</lang>