automatic parallelization
Mikhail Teterin
nothing comparable in Tcl (nor, as far as I know, in the two other
scripting languages).
Or is there? I'd like to, for example, have a version of foreach loop, that
would split the tasks between concurrently executing threads in order to
scale to the number of available CPUs:
For example:
pforeach image $images {
set exif($image) [extract_exif $image]
}
The script would be the same on a single- and a multi-CPU computer, but
would automatically take advantage of multiple processors, when possible.
Has anyone tried or seen anything like this?..
-mi
Michael Schlenker
> While C/C++ and Fortran have OpenMP (http://www.OpenMP.org/), there is
> nothing comparable in Tcl (nor, as far as I know, in the two other
> scripting languages).
>
> Or is there? I'd like to, for example, have a version of foreach loop, that
> would split the tasks between concurrently executing threads in order to
> scale to the number of available CPUs:
For CPython you don't get any benefit from extra CPUs even if you tried
(unless the code inside your loop is specially written C code), due to
the GIL.
For Perl i don't know, their threading model was a bit heavy last time i
looked, but i might be off with that, so maybe its doable in Perl.
For Tcl you would at least get the benefit of multiple CPUs, but its
more message passing based thread model is probably not the best for
autoparallelization like OpenMP (but you could use the tsv:: api for
shared vars if you want to).
>
> For example:
>
> pforeach image $images {
> set exif($image) [extract_exif $image]
> }
>
> The script would be the same on a single- and a multi-CPU computer, but
> would automatically take advantage of multiple processors, when possible.
Its doable in principle, but as with OpenMP you need extra annotations
to make it workable.
If you have an event style script in Tcl you might be easier able to use
threads, as the thread::send -async api fits very well with the event
based style.
Michael
Cameron Laird
.
.
There are a LOT more possibilities one might pursue, depending
on the details of Mr. Teterin's intent. I'm fond of Linda <URL:
http://www.unixreview.com/documents/s=10125/ur0704l/ >, Parallel
Python <URL: http://www.parallelpython.com/ > only one of several
initiatives which aspire to exploit multicores, and so on.
Mikhail Teterin
> There are a LOT more possibilities one might pursue, depending
> on the details of Mr. Teterin's intent.
The reason I began wondering about this is that I like a particular
image-gallery generating tool called `imageindex'
(http://www.edwinh.org/imageindex/)
Unfortunately, it processes all given pictures sequentionally ignoring my
three other cores.
The tool is written in Perl, but I would consider rewriting it in Tcl or
Python, if the language made it easy to parallelize loops...
> I'm fond of Linda <URL:
> http://www.unixreview.com/documents/s=10125/ur0704l/ >, Parallel
> Python <URL: http://www.parallelpython.com/ > only one of several
> initiatives which aspire to exploit multicores, and so on.
Linda URL does not open... I'll look into Parallel Python, but it is
an "execution server", which is a rather different approach from OpenMP's,
which I'm more familiar with.
Thanks!
-mi
tom.rmadilo
wrote:
> Linda URL does not open... I'll look into Parallel Python, but it is
> an "execution server", which is a rather different approach from OpenMP's,
> which I'm more familiar with.
So does OpenMP automatically distribute work from a single thread to
multiple processors? I guess that is the meaning of pforeach?
I use the poorly named AOLserver as my development environment.
Essentially it is an application server with fairly advanced multi-
threading programming features. The easiest example is called a
scheduled proc:
http://rmadilo.com/files/nsapi/ns_schedule_proc.html
foreach image $images {
ns_schedule_proc -once -thread 1 handle_image_proc $image
}
You could add in a limit on the number of threads using a semaphor
(sema.tcl):
# http://rmadilo.com/files/nsapi/ns_sema.html
set images {a.jpg 2 b.jpg 3 c.jpg 1 d.jpg 5 e.jpg 2 f.jpg 7 g.jpg 9
h.jpg 1 i.jpg 3}
set sema [ns_sema create 2]
foreach {image delay} $images {
ns_sema wait $sema
ns_schedule_proc -once -thread 1 "ns_log Notice \"image = $image
\";ns_sleep $delay;ns_sema release $sema"
}
# end sema.tcl
$ /web/nsd45/bin/nstclsh
% source sema.tcl
[13/Sep/2007:23:05:28][29226.1082206528][-sched-] Notice: sched:
starting
[13/Sep/2007:23:05:29][29226.1082280256][-sched:idle0-] Notice:
starting
[13/Sep/2007:23:05:29][29226.1082280256][-sched:1-] Notice: image =
b.jpg
[13/Sep/2007:23:05:32][29226.1082280256][-sched:0-] Notice: image =
a.jpg
[13/Sep/2007:23:05:33][29226.1082353984][-sched:idle1-] Notice:
starting
[13/Sep/2007:23:05:33][29226.1082353984][-sched:2-] Notice: image =
c.jpg
[13/Sep/2007:23:05:35][29226.1082353984][-sched:4-] Notice: image =
e.jpg
[13/Sep/2007:23:05:35][29226.1082280256][-sched:3-] Notice: image =
d.jpg
[13/Sep/2007:23:05:38][29226.1082353984][-sched:5-] Notice: image =
f.jpg
[13/Sep/2007:23:05:41][29226.1082280256][-sched:6-] Notice: image =
g.jpg
[13/Sep/2007:23:05:46][29226.1082353984][-sched:7-] Notice: image =
h.jpg
[13/Sep/2007:23:05:48][29226.1082353984][-sched:8-] Notice: image =
i.jpg
If you look at the numbers [29226.1082280256] this is the
process_id.thread_id, so only two threads were actually created to do
the work (sema count = 2), plus one thread for the scheduler.
tom.rmadilo
> > There are a LOT more possibilities one might pursue, depending
> > on the details of Mr. Teterin's intent.
>
> The reason I began wondering about this is that I like a particular
> image-gallery generating tool called `imageindex'
> (http://www.edwinh.org/imageindex/)
Imageindex uses imagemagick. I have found with Tcl that exec'ing the
imagemagick unix commands is much faster than the Tcl interface. There
are also some speedups with certain options (using both -size and -
resize). I have an online form for producing an efficient command line
for 'convert'. These details will nearly make up for only using 1/4 of
your cores.
http://rmadilo.com/albums/tom/coptions-form
Mark Janssen
wrote:
Strange the URL does work for me. But you can also have a look at
http://wiki.tcl.tk/3947 for some implementations of Linda inspired
tuplespaces in Tcl. If you use the sqlite backed tuplespace I
implemented, parallel execution can be achieved by starting multiple
instances of the image processing script. This leaves scheduling of
the processes on different CPU's to the OS.
The main script will then just post jobs in the tuplespace and reread
the results from the tuplespace.
e.g. Main script
out Jobs "process img1"
out Jobs "process img2"
out Jobs "process img3"
.
.
out Jobs "process imgXX"
while {not all results read} {
in Results *
}
e.g. Multiple instances of process script (possibly on different
machines)
while {still images to be processed} {
in Jobs *
# process image
out Results $res
}
Mark
Donal K. Fellows
> While C/C++ and Fortran have OpenMP (http://www.OpenMP.org/), there is
> nothing comparable in Tcl (nor, as far as I know, in the two other
> scripting languages).
OpenMP is fundamentally a shared-memory parallelism model, and that's
not really compatible with the way Tcl manages threads. The MPI approach
may be better as it uses message passing (which is conceptually close to
what Tcl does) but I don't know offhand of anyone doing this for real.
> pforeach image $images {
> set exif($image) [extract_exif $image]
> }
The tpool sub-package of the Thread package is probably the easiest way
to do this sort of thing, though you couldn't actually write it as above
because Tcl doesn't share much between threads at all. You'd need to
size the pool correctly for your system, of course. The tsv sub-package
might also help by allowing you to transfer large values between the
pooled workers and the master more efficiently. Documentation for the
whole Thread package is pointed to from http://wiki.tcl.tk/thread
Donal (not experienced enough to offer more help than this!)
Cameron Laird
Mikhail Teterin <usene...@aldan.algebra.com> wrote:
.
.
.
>> I'm fond of Linda <URL:
>> http://www.unixreview.com/documents/s=10125/ur0704l/ >, Parallel
>> Python <URL: http://www.parallelpython.com/ > only one of several
>> initiatives which aspire to exploit multicores, and so on.
>
>Linda URL does not open... I'll look into Parallel Python, but it is
.
.
It comes and goes. It seems to have been OK the last several hours.
Mikhail Teterin
> So does OpenMP automatically distribute work from a single thread to
> multiple processors? I guess that is the meaning of pforeach?
Yes, it does. For example:
#pragma omp parallel for
for (i = 0; i < N; i++)
foo[i] = pow(i, 0.3333);
The pragma will cause an OpenMP-supporting compiler to arrange for
automaticly distributing chunks of the loop between available processors.
The above example is too simple, do browse through http://www.openmp.org/
and through a host of good article on the subject on AMD.com:
http://developer.amd.com/articlex.jsp?id=82
http://developer.amd.com/articlex.jsp?id=79
It almost makes me want to go back to C from the scripting languages :-)
Just for fun I intend to try to implement "pforeach" using OpenMP over the
weekend.
-mi