#7013: [with patch, needs work] prime_pi and nth_prime
-----------------------------+----------------------------------------------
Reporter: kevin.stueve | Owner: kevin.stueve
Type: enhancement | Status: needs_work
Priority: major | Milestone: sage-4.3
Component: number theory | Keywords: primes, sieve, table,LMO
Work_issues: | Author: Kevin Stueve
Upstream: N/A | Reviewer: was,robertwb,GeorgSWeber
Merged: |
-----------------------------+----------------------------------------------
Comment(by kevin.stueve):
Andrew,
I would again like to praise you for your great work on this program. You
have done a good job at converting the code from Python to Cython (which
improves the speed of the non-c parts of the program), improving the style
of the code, and integrating table/sieving prime_pi and nth prime with the
rest of Sage in a patch.
The parallel processing code I implemented has been removed.
I think it would be very well worth the effort to re-implement parallel
processing code. Dual core processors are common today. Quad and greater
numbers of cores are becoming more common. As it is becoming harder to
make components on a silicon chip smaller and faster (clock-rate), the
semiconductor industry has partially responded by making more cores per
chip. It is reasonable to assume that in the foreseeable future this
trend will continue and many more cores will be available than are now.
I believe that the almost 2-times speedup offered by parallel processing
on dual core machines is worth the extra coding effort. This is even more
true for quad and greater numbers of cores. Companies spend great amounts
of money and time to make their programs just 10% faster. An algorithm
which is trivially parallelizable such as sieving is rare. Every such
opportunity for improvement should be given the utmost attention.
In any project it is important to look toward the future and what
technology will be available. Let's look at the future of multi-core
processors.
"Intel's researchers have produced a research prototype 80-core chip that
uses less energy than a quad-core processor and has teraflop performance
capabilities.
It expects to be able to produce a chip with 80 cores in five to eight
years."
Intel builds 80-core chip
EE Times, Jan. 16, 2007
http://www.eetimes.com/news/latest/showArticle.jhtml;?articleID=196901229
"Chinese researchers have unveiled details of Godson-3, a scalable
microprocessor with four cores (work in parallel) that they hope will
bring personal computing to most ordinary people in China by 2010, with an
eight-core version in development."
A Chinese Challenge to Intel
Technology Review, Sep. 1, 2008
http://www.technologyreview.com/Infotech/21322/?a=f
"Intel Larrabee to have 32 cores, ship in 2010"
May 15th, 2009
http://blogs.zdnet.com/gadgetreviews/?p=4336
The opportunity to almost double or quadruple the speed of a program is
enough to implement multiprocessing. But when Intel's road-map includes a
32 core chip in 2010 and an 80 core chip a few years away, it becomes
absolutely ridiculous not to implement multiprocessing.
I spent a lot of time and effort optimizing the use of multiprocessing. I
did benchmarking to determine at what point the time savings from
multiprocessing outweighs the overhead needed. This is time sacrificed
that I could have spent doing many other things.
Now I find that my multiprocessing code has been removed. It is not my
responsibility to put it back in. I already put it in once.
Let me remind you that the purpose of this project is the fastest possible
implementation of the prime counting function. Let's not miss a large
factor of difference (that will grow exponentially as the years go by)
from neglecting a few lines of trivial multiprocessing code.
Sincerely,
your friend,
Kevin Stueve
--
Ticket URL: <http://trac.sagemath.org/sage_trac/ticket/7013#comment:20>
Sage <http://www.sagemath.org>
Sage: Creating a Viable Open Source Alternative to Magma, Maple, Mathematica,
and MATLAB
--
You received this message because you are subscribed to the Google Groups
"sage-trac" group.
To post to this group, send email to [email protected].
To unsubscribe from this group, send email to
[email protected].
For more options, visit this group at
http://groups.google.com/group/sage-trac?hl=en.
