New subfield search

Message boards : News : New subfield search
Message board moderation

To post messages, you must log in.

1 · 2 · Next

AuthorMessage
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1820 - Posted: 4 Mar 2017, 17:03:58 UTC

As you may have noticed, the search over ℚ(√2) (subfield 3) has started to slow down and waiting for results is like watching paint dry. At the current rate it will probably take over 10 years to finish that search. In the interest of making progress, I have decided to start the search over subfield ℚ(√-2). This is the 4th of 7 subfields for the set {2,5}. We will continue to process subfield 3 in parallel, but at least we will be able to maintain progress on other subfields for the overall goal of this project.

The hope is that I can find time this year to develop a GPU app that will help to speed up the search. Of course I've been saying this for years...
ID: 1820 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Bytebit

Send message
Joined: 15 Nov 11
Posts: 3
Credit: 1,004,910
RAC: 0
Message 1821 - Posted: 4 Mar 2017, 23:11:55 UTC

Good News. GPU Apps, i can't wait. :-))
ID: 1821 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Stephen Uitti

Send message
Joined: 9 May 15
Posts: 2
Credit: 1,351,620
RAC: 0
Message 1822 - Posted: 5 Mar 2017, 15:31:15 UTC

I've recently been looking at a new-ish computer language: Julia. It has a pretty easy mathematical syntax (3 * a in FORTran can be 3a in Julia). It also has syntax for parallel processing and vector processing. Parallel can mean co-routines on a single core (helping I/O and CPU overlap), multi-core shared memory, or systems on a network. Vector processing can be using the vector instructions that the processor (especially x86) has, a video card (nVidia or Radeon), on-chip video (like AMD's APU or an Arm's DSP or whatever Intel calls their on-chip video). The parallel syntax is fairly non-invasive, and mainly gives the language hints that you're not going to go wild with pointer references, etc. By new, i mean that the current release is 0.5. While the language has a JVM, with garbage collection and Just-In-Time compiling, it also can compile to the bare metal, and has, as a goal, near-C performance. The C language has been the gold standard for performance since the 80s. It can also either call other languages like C, or be called by other languages. Perhaps there's no need to recode any BOINC interfaces. Anyway, i'm looking at it specifically because it's a higher level language, and it looks like it can produce video card code without having to learn or code in video card instructions. Perhaps a good fit for NumberFields.

So far, i've read the 645 page manual (available online or in PDF) and have written a couple tens-of-lines programs and gotten them to get correct results. One of these is the Collatz core (which is real simple). Julia has easy arbitrary precision arithmetic support (it's an integer type), which helps here.

http://julialang.org/

I personally have _no idea_ what math NumberFields uses. I'm not totally ignorant about discrete math, but I mostly studied continuous Calculus stuff. Perhaps there are users who would be interested in helping out. That could speed things up.

Stephen.
ID: 1822 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1823 - Posted: 5 Mar 2017, 17:48:46 UTC - in response to Message 1822.  

I hadn't heard of Julia. It sounds interesting. NumberFields uses the Pari library for several number theoretic functions. This has been the biggest stumbling block that people have run into trying to make a GPU app for this project; and the main reason I am hesitant to try myself. You infer that Julia may have issues with pointer references; as it turns out, Pari makes frequent use of pointers (one thing that makes it powerful is the global stack workspace that all functions have access to via pointers). So Julia may not play nice with Pari.

If anyone wants to attempt the GPU app, just let me know. But be forewarned, that many have tried before and were unsuccessful. This is not a trivial task.
ID: 1823 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Dj Ninja

Send message
Joined: 23 Feb 13
Posts: 29
Credit: 21,480,710
RAC: 0
Message 1824 - Posted: 9 Mar 2017, 12:05:15 UTC

The gold standard for raw speed back in the 80's and I think in the 90's too is assembler, designed and optimized for the platform it should run on. A couple of years ago I wrote a 3x+1 application using x86 assembler, the complete win32 executable was only around 4kbytes in size and awful fast, especially on older machines.

Unfortunately I don't know anything on the "subfield math" used here either. But if it needs a big and mysterious mathematical library (pari), it seems to be complicated.

Is this needed to handle very big integers only or which mathematical functions or operations are necessary?

Are there any explanations on the internet where a very small field is displayed, so that this field and the mathematics behind it can be fully understood?
ID: 1824 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1825 - Posted: 9 Mar 2017, 15:34:53 UTC - in response to Message 1824.  

The gold standard for raw speed back in the 80's and I think in the 90's too is assembler, designed and optimized for the platform it should run on. A couple of years ago I wrote a 3x+1 application using x86 assembler, the complete win32 executable was only around 4kbytes in size and awful fast, especially on older machines.

Unfortunately I don't know anything on the "subfield math" used here either. But if it needs a big and mysterious mathematical library (pari), it seems to be complicated.

Is this needed to handle very big integers only or which mathematical functions or operations are necessary?

Are there any explanations on the internet where a very small field is displayed, so that this field and the mathematics behind it can be fully understood?


To anyone with an undergraduate degree in math it would not be "mysterious". But the mathematics is not trivial either. Among other things, it computes polynomial discriminants, field discriminants, irreducibility, and number factorization. Anyone understanding the math could code up these things, but the pari library is very efficient at doing it and it has been extensively tested so you can be confident that there are no bugs in the code. You mentioned assembly- as it turns out pari uses platform dependent assembly for many of it's core functions.
ID: 1825 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Dj Ninja

Send message
Joined: 23 Feb 13
Posts: 29
Credit: 21,480,710
RAC: 0
Message 1826 - Posted: 9 Mar 2017, 20:47:08 UTC

Maybe it's language-related that it is hard to understand for me. If you have a german article about it or "real hard math" to run and see what it is doing, it could be easier.

If anybody could code these things without using the PARI library, I don't understand why anybody failed creating a GPU app. I aspect modern compilers come very close to the speed of a pure-assembler program, but some years ago this was different.
ID: 1826 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1827 - Posted: 10 Mar 2017, 0:21:36 UTC - in response to Message 1826.  

Not just anybody could do it though - they would need an understanding of the math. I think many of those who volunteered to help had more of a computer science background. One person came close - they actually got a hybrid CPU/GPU version working and it speeded things up by about 30%. If memory serves, it still used a CPU core to do the hard math (using Pari). For this reason we never implemented it in the project.
ID: 1827 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Dj Ninja

Send message
Joined: 23 Feb 13
Posts: 29
Credit: 21,480,710
RAC: 0
Message 1828 - Posted: 10 Mar 2017, 1:18:21 UTC

Are you able to fully explain the math?
ID: 1828 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1829 - Posted: 10 Mar 2017, 1:55:09 UTC - in response to Message 1828.  

Yes. But it would be very time consuming to try to explain it here. I would suggest Wikipedia; their explanation might be better than mine anyways. I listed the main topics above. You could start with the polynomial discriminant and build from there:
https://en.wikipedia.org/wiki/Discriminant
ID: 1829 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Vitaly

Send message
Joined: 5 Jan 13
Posts: 43
Credit: 41,024,048
RAC: 628
Message 1832 - Posted: 15 Mar 2017, 13:13:32 UTC - in response to Message 1829.  
Last modified: 15 Mar 2017, 13:16:16 UTC

It is interesting, are you thought about double checking of the tasks. Many projects have double checking.

Or it is no need because of specific scientific needs that we have in this project?

Thanks.
ID: 1832 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1833 - Posted: 15 Mar 2017, 16:36:36 UTC - in response to Message 1832.  

I don't do double checking because that would mean the project would have to wait twice as long to complete a search. The most likely reason for someone returning a faulty result would be deliberate maliciousness; do you know of any studies that show what percentage of users do that? Most of the "cheaters" find ways to artificially increase their FLOPS and/or compute time (like running many VMs in parallel) without compromising the results themselves.

With that said, my combiner scripts have checks in place to flag suspicious results. It has flagged numerous results, which I then run again, but so far none of these have been fallacious.

Also, the algorithm itself has some built in redundancy in the sense that it finds about 100 times as many polynomial representatives as there are actual fields. The theorems that the algorithm uses guarantee that there exist polynomial representatives within certain coefficient bounds, these bounds are sufficiently large that it picks up the field 100 times (on average). As a side note, finding tighter bounds would be one way to speed up the algorithm, as this would reduce the search space.

In addition to all that, once a search is complete, there are relationships between the numbers of fields of various Galois groups. This would most likely detect a missing field. For example, the number of decic fields with Galois group 10T17 must be even. But like a parity bit, the check can fail if there are multiple errors.
ID: 1833 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Aurel
Avatar

Send message
Joined: 25 Feb 13
Posts: 216
Credit: 9,899,302
RAC: 0
Message 1835 - Posted: 18 Mar 2017, 14:20:04 UTC

WHOA, just saw the new informations from sf3 DS16. Holy, thats a lot of work.
ID: 1835 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Vitaly

Send message
Joined: 5 Jan 13
Posts: 43
Credit: 41,024,048
RAC: 628
Message 1841 - Posted: 29 Mar 2017, 17:45:15 UTC - in response to Message 1833.  
Last modified: 29 Mar 2017, 17:45:49 UTC

I don't do double checking because that would mean the project would have to wait twice as long to complete a search. The most likely reason for someone returning a faulty result would be deliberate maliciousness; do you know of any studies that show what percentage of users do that? Most of the "cheaters" find ways to artificially increase their FLOPS and/or compute time (like running many VMs in parallel) without compromising the results themselves.

With that said, my combiner scripts have checks in place to flag suspicious results. It has flagged numerous results, which I then run again, but so far none of these have been fallacious.

Also, the algorithm itself has some built in redundancy in the sense that it finds about 100 times as many polynomial representatives as there are actual fields. The theorems that the algorithm uses guarantee that there exist polynomial representatives within certain coefficient bounds, these bounds are sufficiently large that it picks up the field 100 times (on average). As a side note, finding tighter bounds would be one way to speed up the algorithm, as this would reduce the search space.

In addition to all that, once a search is complete, there are relationships between the numbers of fields of various Galois groups. This would most likely detect a missing field. For example, the number of decic fields with Galois group 10T17 must be even. But like a parity bit, the check can fail if there are multiple errors.



So do you mean that it is impossible for an incorrect result to be accepted for the project?
ID: 1841 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1842 - Posted: 29 Mar 2017, 18:27:35 UTC - in response to Message 1841.  

If a field is returned that is "incorrect", my combiner script will catch that.
It also has ways to detect when a field is missing from the data.
ID: 1842 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Forretrio

Send message
Joined: 26 Jun 13
Posts: 11
Credit: 8,735,592
RAC: 0
Message 1843 - Posted: 6 Apr 2017, 0:06:50 UTC - in response to Message 1841.  

If my understanding were correct it's like doing probabilistic primality test - the chance of getting it wrong decrease exponentially with the number of trials. Getting error of it is not impossible but virtually impossible.
ID: 1843 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
icyDRFT

Send message
Joined: 7 Jun 15
Posts: 2
Credit: 135,196
RAC: 0
Message 1845 - Posted: 12 Apr 2017, 17:09:32 UTC - in response to Message 1820.  

Are there any plans for numberfields@home, or any BOINC project for that matter, to add GPU support for integrated GPUs instead of exclusively AMD and Nvidia dedicated GPUs. It seems like an untapped resource.
ID: 1845 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile Eric Driver
Project administrator
Project developer
Project tester
Project scientist

Send message
Joined: 8 Jul 11
Posts: 1341
Credit: 498,285,116
RAC: 576,798
Message 1848 - Posted: 13 Apr 2017, 0:36:12 UTC - in response to Message 1845.  

I don't know about other projects, but my plan is to start by programming apps using Cuda/openCL first. I don't know enough about GPUs to know if the code is easily modified for integrated GPUs.
ID: 1848 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
icyDRFT

Send message
Joined: 7 Jun 15
Posts: 2
Credit: 135,196
RAC: 0
Message 1855 - Posted: 13 Apr 2017, 16:55:36 UTC - in response to Message 1848.  

As far as I know newer integrated processors from Intel and AMD APUs support opencl, but then coding for them compared to dedicated processors may be more difficult. SETI is one project that provides work units for integrated GPUs due to the recent addition of opencl 1.2+ support, but then again it would benefit them more than other projects due to their size. It's worth a thought though in my opinion, any additional resources is a plus.
ID: 1855 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
Profile [AF>Amis des Lapins] Phil1966

Send message
Joined: 14 Sep 13
Posts: 1
Credit: 3,372,625
RAC: 3
Message 1856 - Posted: 14 Apr 2017, 14:33:19 UTC

Looking Forward to try the GPU app.
ID: 1856 · Rating: 0 · rate: Rate + / Rate - Report as offensive     Reply Quote
1 · 2 · Next

Message boards : News : New subfield search


Main page · Your account · Message boards


Copyright © 2024 Arizona State University