View Single Post
Old 2019-12-18, 15:15   #5
kriesel
 
kriesel's Avatar
 
"TF79LL86GIMPS96gpu17"
Mar 2017
US midwest

23·3·13·19 Posts
Default GIMPS Glossary

See also the background post. https://www.mersenneforum.org/showpo...65&postcount=3

Software application names are intentionally omitted from this glossary. See the "Available Mersenne prime hunting software" table for those. http://www.mersenneforum.org/showpos...91&postcount=2

100Mdigit: There's an Electronic Frontier Foundation prize for finding the first prime large enough to occupy 100 million digits (100 megadigits). A GIMPS subproject is to search for such a prime and win that prize. This requires an exponent of at least 100,000,000/log10(2) = 332,192,807 for the Mersenne number. The smallest prime exponent above that minimum is 332,192,831.

assignment: designation by the PrimeNet server, through either automated or manual operation, of a specific computation task as reserved to one GIMPS user. See https://www.mersenneforum.org/showpo...8&postcount=22 for what the various forms look like. Manual assignments are obtained through https://www.mersenne.org/manual_assignment/ or https://www.mersenne.org/manual_gpu_assignment/. Note these assignments can expire before completion and result report.

base: in P-1 or PRP, the starting number which is raised to successive powers. Usually 3.

bit level: in TF, indication of how far TF has been performed. For example, 74 corresponds to attempting factors up to 274 in size.. A single bit level would be advancing the TF performed by one, such as from 273 to 274.

bound: a limit. Specific to P-1 factoring, an upper limit on the set of primes used in a stage of factoring, referred to as B1 and B2.

certificate a file showing completion of a PRP proof verification. Such a file can be very rapidly verified as valid by a server.

CERT depending on context, a worktype, or the performance of the work. Mprime / prime95 support receiving CERT assignments via the PrimeNet API, receiving the required hashed input file generated by the PrimeNet server (from a proof file the server received from a client earlier), and computing from the received hashed file a CERT type result record for upload to the PrimeNet server.

counterfeit a deliberate fake, a fraud (crime) perpetrated seeking fame or fortune. In GIMPS results, a fabricated result for work not performed, or only slightly performed. In computing hardware, devices disguised and sold to seem to be more than they are. USB external SSDs are one current example, and high capacity flash drives appear to be another. The PrimeNet server implements some anti-counterfeiting measures. Hardware buyers beware, and be prepared to test hardware upon receipt.

CPU: central processing unit. Can be used for any GIMPS computation, although CPUs have largely been supplanted by GPUs for trial factoring within the p<232 exponent range.

CUDA: "CUDA is a parallel computing platform and programming model invented by NVIDIA." https://www.geforce.com/hardware/technology/cuda It is proprietary and only usable on NVIDIA GPUs. There are many different version levels. As of 2021-05-29, latest is v11.3.

DC: abbreviation for double-check

double-checking: running a second primality test on an already tested exponent, with the same primality test type, seed, residue-type, as applicable. If the runs are independent, and error counts are low, matching res64 values are presumed to both be correct.

ECM: Elliptic curve method of factoring. This is suitable for Mersenne numbers with exponents below 40 x 106. It is not suitable at the current GIMPS wavefronts or above.

expiration: the end of an assignment before it's completed, because time ran out. Expiration occurs earlier if there's no progress reported. Time from assignment to expiration depends on the assignment type, exponent, and last date of progress reported if any.

exponent: for a Mersenne number, the power, or number of times 2 is multiplied together, as the 3 in 23=2x2x2=8 before subtracting a 1, yielding M(3)=23-1=7

extension: adding additional time to complete an assignment. See https://www.mersenne.org/manual_extension/

FFT: Fast Fourier Transform; Finite Fourier Transform

fft length: number of double precision words length of an FFT used for computing products or squares. In the range of exponents of current GIMPS wavefront interest, fft length ~ exponent/17.5. For more, see https://www.mersenneforum.org/showpo...21&postcount=7

FPGA Field programmable gate array. To my knowledge there have been many suggestions/proposals to use FPGAs in GIMPS over the years, but no working designs or compatible software created or announced or demonstrated or shared. See https://mersenneforum.org/showthread.php?t=2674 for a recent iteration.

GEC:
Gerbicz error check: a highly reliable error check on the PRP test, identified by Robert Gerbicz, with nearly 100% detection for errors in the PRP iteration process, which allows resuming from an earlier saved state and trying again. It is independent of earlier error detection methods. The high detection rate for software or hardware error in computing PRP iterations provides MUCH higher reliability for completed tests than a Lucas-Lehmer test on the same software and hardware for large exponents. See https://www.mersenneforum.org/showpo...17&postcount=9 Other errors not caught by this are possible and have been observed, rarely. The check is built into PRP code of recent versions of gpuowl, Mlucas, mprime, prime95.

GHzDay: in GIMPS, a unit of computing work equivalent to what a 1 Ghz Core2 processor core would accomplish in a day with efficient GIMPS code.

GhzD/day: in GIMPS, a computing rate equivalent to what a 1 GHz Core2 processor core would accomplish. Note that the same hardware may have very different ratings for very different computation types. CPUs generally have ratios between TF and other computations that are near one, while GPUs can be very different; ratios of 11:1 to 40:1 faster TF have been observed.

GIMPS: the Great Internet Mersenne Prime Search

GPU: graphics processing unit. https://en.wikipedia.org/wiki/Graphics_processing_unit

hoard: to obtain assignments, especially a large number of them, and do nothing with them for much of the assignment lifetime. Manual assignments performed on applications which are not PrimeNet interfaced for status update may appear to be hoarded while actually quietly making unreported progress toward completion.

IGP: integrated graphics processor. A CPU and IGP together on one chip or in one package share power budget and memory bandwidth. IGPs tend to be low performance compared to discrete GPUs. For more see https://hexus.net/tech/tech-explaine...processor-igp/

Jacobi check: computation of a Jacobi symbol value. Applied to the LL interim full residue, it has a 50% chance of detecting a software or hardware error affecting the LL iterations, which allows resuming from an earlier saved state and trying again. It is independent of earlier error detection methods. If applied after every iteration, it would have a 75% chance of detecting error. It is too computationally expensive for that. It is typically applied every several hours. It is not applicable to TF or PRP. It is also somewhat applicable to P-1 but quite expensive to do there. See also https://www.mersenneforum.org/showpo...1&postcount=10
The check is built into LL code of recent versions of gpuowl, Mlucas, mprime, prime95, except that LL has been dropped from gpuowl versions V7.0 and higher.

latency: the time from beginning to end of a specific computing task. Reducing latency can come at the cost of lowered throughput.

LL: Lucas-Lehmer test which is a conclusive primality test for Mersenne numbers if performed accurately. Without the Jacobi check, the LL test observed residue error rate is about 2% historically, increasing with run time. Beginning with seed value 4 is standard.

LLDC: Repeating the LL on the same exponent, ideally by a different participant, shift, software, and hardware, but same seed value, in an attempt to verify the first LL test by producing a matching final Res64 value. See DC and double checking above. If either LL test has an error affecting the final result, a triple check (or more) becomes necessary.

Mx: see (1) below.

Mx: in the GIMPS context,
(1) the Mersenne number with exponent x. For example, M7 would represent 27-1 = 127, the fourth entry in the list of known Mersenne primes https://www.mersenne.org/primes/
(2) the xth known Mersenne prime. Note this usage, while historically common, both conflicts with (1) and creates ambiguity.
Generally the ambiguity can be resolved by context, or noting suffix values significantly greater than that for the highest known Mersenne prime exponent, #51*, p=82589933, very likely indicate exponent, not sequence number. The ambiguity remains for small prime x for which 2x-1 is also prime; 2 3 5 7 13 17 19 31.
To reduce ambiguity, and the need for every reader to reason out which is meant, please avoid the second usage going forward.

Mpx or Mp#x: the x-th known Mersenne prime in sorted order. Its ranking is regarded as provisional and it is followed customarily by an asterisk * or sometimes a question mark "?" if verification of all others below its exponent has not yet completed. For example, Mp48 but Mp49* and above currently, since double-checking has not yet completed up to 74207281 as of 6 October 2021. Mp#4 is 27-1 = 127.
(There is not to my knowledge, usage of the analogous Mnx, which would be the Mersenne number (composite or prime) given by the x-th prime exponent.)

milestone: finding a new Mersenne prime or proving a known Mersenne prime is the nth in the sorted set is considered a major GIMPS milestone. Completing an additional range of million exponent value, in first test or successful double-check, is considered a minor milestone. There's a web page for those.

necropost: post in an existing thread which has had no posts in the past several months or years. It's mildly discouraged. Sometimes it's useful, as in cases where the hardware technology or number theory have advanced in a relevant way.

numerology: unsound or baseless mathematical reasoning. See also https://en.wikipedia.org/wiki/Numerology#In_science

OEIS: the Online Encyclopedia of Integer Sequences. OEIS includes https://oeis.org/A000668 (Mersenne primes) and https://oeis.org/A000043 (exponents of Mersenne primes)

offset: an integer number of bit positions to which the seed or base is initially shifted. Shifting the computations differently causes the expected numerical errors in floating point FFT computations to affect the operands differently. Different, pseudorandomly selected, and nonzero shift counts are preferred.

OpenCL: "OpenCL is a framework for writing programs that execute across heterogeneous platforms consisting of central processing units, graphics processing units, digital signal processors, field-programmable gate arrays and other processors or hardware accelerators." It is a standard supported by AMD, Intel, NVIDIA, and ARM. https://www.khronos.org/opencl/

OpenGL: "a cross-language, cross-platform application programming interface (API) for rendering 2D and 3D vector graphics. The API is typically used to interact with a graphics processing unit (GPU), to achieve hardware-accelerated rendering." https://en.wikipedia.org/wiki/OpenGL
(while reportedly OpenGL has been used to perform nongraphics computations, there is no known GIMPS application using OpenGL)

overclock: running computing hardware faster than the rated frequency. This tends to reduce reliability of the output, reduce performance per watt-hour, and can reduce hardware lifetime.

P-1: A factoring technique for finding factors with the special property that they are one greater than a number with many small prime factors; a standard part of the TF, P-1, primality test, and verification sequence applied in the GIMPS hunt for new Mersenne primes https://en.wikipedia.org/wiki/Pollar...92_1_algorithm

P+1: A factoring technique for finding factors with the special property that they are one less than a number with many small prime factors. This method is thought to be too unproductive to be a part of the GIMPS hunt for new Mersenne primes, but may be useful in searching for additional factors of smaller Mersenne numbers, as an additional capability introduced in mprime / prime95 v30.6 https://en.wikipedia.org/wiki/Willia...2B_1_algorithm

poach: work on and report a result for an exponent and computation type combination that was currently assigned to someone else. This is frowned upon, both because it can irritate the person with the assignment, and because it often results in wasteful duplication of computation.

PrimeNet: the API, software, and server that enables automated issuance of assignments and submission of results from GIMPS client software such as mprime and prime95 and updating of a central GIMPS database.

Proof computations accompanying a PRP test, after preserving residues at selected points, creating a file allowing independent verification of the PRP test's completion and correctness. Generating a proof requires (a) software that supports it (currently sufficiently recent versions of gpuowl, mprime, prime95), (b) configured to use sufficient available disk space to hold all the needed temporary files, (c) a PRP run not LL, (d) from (almost) the beginning of the test. Proof-capable software is required before the iterations reach ~p/2proof_power.

PRP: Probably prime test, a primality test that is conclusive when performed accurately and indicating composite, and highly likely to have identified a prime if it indicates probably prime, but requiring a conclusive primality test, such as LL, be run to confirm the prime. PRP tests are much more reliable than LL, when guarded by the excellent GEC error detection. There are several different PRP test types. For final residues to match for the same exponent, tests must use the same PRP test type and seed. See residue type.

relative prime, or relatively prime
Two (or more) numbers are said to be relatively prime if they have no factors in common, i.e. their greatest common divisor is 1.

QA: quality assurance, the act of testing computations on a wide variety of exponents, fft lengths in primality testing or P-1, bit levels in TF, unusual hardware, and reporting in detail any anomalies encountered, and testing one software against another for matching results, relying on the likelihood they are both right rather than both wrong in such a way as to give matching results

res64: 64-bit residue, the least 64 bits of a larger number, usually represented in ASCII hexadecimal in console output

residue type: in PRP, there are at least 6 identified residue types. For the residues to match, the residue types must match. Those obtaining manual assignments for PRP DC should take care to ensure they reserve assignments that fit in residue type the capability of the software they intend to use to run the double-checks. For PRP, type 1 is standard. For PRP-CF, type 5 is standard. See also https://www.mersenneforum.org/showpo...32&postcount=8

scaling: how run-time or memory requirements vary with exponent or other relevant variables for a given software application. Number theory provides lower limits to what is possible scaling. Testing by sampling at widely spaced variable values provides an indication of achieved scaling.

Schrodinger number: a number which someone has claimed is prime and has also claimed is composite, without proof in either case, or has claimed that the discovery of a prime factor is irrelevant. Analogous to Schrodinger's cat. Sort of like an illegitimate child; it's not their doing either. Two examples.

seed: in LL testing, the starting value to which the LL iterations are successively applied. Standard seed for GIMPS LL primality testing is 4. Other values, such as 10 or 2/3, are valid for finding a Mersenne prime, but are not used, since differing seed values make full-residue values, res2048 values, and res64 values for composites not match between tests of differing seed values, with serious negative consequences for double-checking. In PRP testing, the starting value on which successive powerings are performed. Standard seed for GIMPS PRP primality testing is 3.

shift: an alternate term for offset

smooth: having small factors. A number that has no factors greater than n is called n-smooth. For example, 42 = 2 * 3 * 7 is 7-smooth.

straggler: exponent that is late in completing, delaying reaching minor milestones.

TC: triple check. When a doublecheck residue does not match the first-test residue, for the same test type and seed, a tie breaker is needed, so a third check is run, and occasionally a fourth, etc, until matches are obtained, with acceptably low error counts. Around 2% of LL tests get triple checks. (More if the exponent is much larger than wavefront exponents or the hardware is unusually slow.) A much lower fraction of PRP tests get triple checks since the Gerbicz error check performed along the way in most PRP tests makes PRP test results much more reliable.

TF: trial factoring

throughput: the long term rate of production of computational results. See also latency

TPU: "Tensor Processing Units (TPUs) are Google’s custom-developed application-specific integrated circuits (ASICs) used to accelerate machine learning workloads. TPUs are designed from the ground up with the benefit of Google’s deep experience and leadership in machine learning." https://cloud.google.com/tpu/docs/tpus
There is currently no known GIMPS application that makes use of TPUs.

tuning: adjusting various parameters in the command line or ini file or configuration file of an application, usually to increase throughput

underclock: running computing hardware slower than the rated frequency. This tends to increase reliability of the output, increase performance per watt-hour, and can cause equipment to run at lower temperatures and extend hardware lifetime.

undervolt: operating computing hardware at lower than the nominal voltage, to reduce power dissipation. The reduced power at a given clock rate may in turn allow additional overclocking.

VDF:
verifiable delay function. The function that made the low cost PRP proof generation and independent certification possible, and in turn, allowed reducing DC work required per PRP test to less than 0.5% from 100%.

verification generally, confirming correctness of a first primality test by repetition independently. More recently, performing the independent "CERT" check beginning with a PRP proof file that has been processed by the PrimeNet server and downloaded to a CERT-capable client.

wavefront: the range of exponents, for a given computation type, where the bulk of the activity is occurring. It moves upward over time. See https://www.mersenneforum.org/showpo...73&postcount=2 for a definition and some historical values

wildcat: (proposed; not in common use) work on tasks without assignments to anyone. This is relatively low but not zero risk in P-1 or primality testing above ~350M. TF this way is both more common and more problematic. This is sometimes less than accurately referred to as poaching, which is activity in conflict with assignments to others. Possible synonyms or variants are squat, or "working off the books" (which is also a term for tax evasion, so has a negative connotation not justified in context, and it's just too long and wordy); pioneer if working somewhat ahead of the wavefront; scout if working substantially ahead of the wavefront; explorer if working all over the mersenne.org range.

zombie: (proposed; not in common use) exponent or system that is making little or no progress. It could be the hardware is slow, the assignment follows another being worked on, the error rate and retry is high, or the application has stopped or the system was upgraded and application not relaunched. See also straggler.


Top of reference tree: https://www.mersenneforum.org/showpo...22&postcount=1

Last fiddled with by kriesel on 2021-10-06 at 09:25 Reason: Mp#48
kriesel is online now