The equihash paper’s 4x benefit refers to parallel sorting, not a bunch of CPU-like threads on GPUs. GPU wattage is not being maxed, giving me the impression parallel work can be done.
Parallel (GPUs): Quick sort and merge sort
Sequential (CPUs): Radix
Equihash paper’s citations mention radix and merge sort, and their [49] upon which their 4x was based cited the above paper by CUDPP researchers Satish and Harris.
Here is a very good comparison of sequential and parallel sorting, again Citing Harris and Satish for radix and merge sorts. Quicksort also did well for parallel
radixSort using Satish and Harris results is in the CUDA SDK using CUDPP.
Yes, but it generates lots of tiny scattered writes, which wastes memory bandwidth. GPUs cannot write less than 256 contiguous bits at a time. Even an entire row of the 200,9 table is less than that, and a single cell (the unit used in sorting) is only 20 bits.
Mergesort and radix (for “normal” digit sizes) saturate the memory bus with long streaming reads and writes. Here, “normal” means smaller than log_2(sram_size).
The slots that are written to random memory locations vary in size from 28 bytes in the first round down to 8 bytes in the last round.
My GPU code for slot writing looks like this
slot1 &xs = htl.hta.trees1[r/2][xorbucketid][xorslot]; // RANDOM ACCESS
xs.attr = tree(bucketid, s0, s1, xhash);
for (u32 i=htl.dunits; i < htl.prevhashunits; i++)
xs.hash[i-htl.dunits].word = pslot0->hash[i].word ^ pslot1->hash[i].word;
xs.attr is 4 bytes and so is each xs.hash[…].word
I remember doing a test where I replace the random access by a sequential one (just to see performance; while producing bogus results). I was kind of surprised that it was only 2 to 3 times faster.
So avoiding the random writes by doing what those radix sorts are doing, even at 2 bits at a times would take 10 steps to cover 20 bits, and thus be way slower…
Hi, I don’t remember how it was called, but I saw reserchers bind multiple servers together as one for use with hashcat. But I’m not sure It would be of any use for mining.
Thanks @lexele for prompt reply,
I would be thankful if someone could guide me in this regards. Moreover is it advisible to solo mine when someone have greater Hash rate like 500-700 H/s.
Someone to please guide me.
Such large memory transfers are not necessary. You only need to sort the current 20-bit-wide column.
If the switch to 144,5 occurs this effect will become even more pronounced.
Can you express this statement in terms of concepts in the Equihash paper?
Well sure if you insist on shipping around “28 bytes in the first round down to 8 bytes in the last round” that’s between 224 and 64 bits per access, which is around 3x to 10x more data than actually needs to cross the memory bus. So it’s not surprising that adjusting the access order didn’t improve things.
You can radix sort on digits which are quite a bit larger than 2 bits!
PS congratulations on your election victory. I am available for cabinet appointments.
The “world record holder” in many sorts is CUDA’s CUDPP radixSort developed in 2009 and it uses 4 bits. Thrust and CLOGS (OpenCL) are second. I believe 4-bits is ideally fast on 4^2 = 16 bits, so 20 bits should be a lot faster than 32. It does not seem a lot better than merge sort for key-values, but it’s about 20x faster than the next fastest sort on GPUs if it is keys-only uniform. It pulls away from the pack as the keys get longer.
No, if you can fit (2^5)*DRAM_ACCESS_GRANULARITY bits in on chip memory then 5-bit digits will definitely be faster than 4-bit digits, since you’ll do one less round trip. And so too on with 6-bit digits, etc, until you run out of on-die memory to hold one almost-full-DRAM-granular transaction for every possible digit.
The optimal digit size depends on many things – in particular the amount of on-die SRAM (aka cache) and the size of the dataset being sorted.
Of course. But that doesn’t mean you need to shuffle them back and forth from one part of the DRAM to another through that GDDR5 bottleneck as you do the sorting (or bucketing, if you prefer). See below.
Yes, it seems everybody on the face of the planet independently rediscovered this within a few hours of reading the paper, and yet it never occured to the authors. Would be funny it it weren’t so disturbing. But I guess it’s par for the course when it comes to allegedly-memory-hard proofs of work. For some reason authors always get away with pretending their algorithm is the only one that could possibly be used.
But the paper still states the problem, and I was hoping you might express your earlier comment in terms of that problem as stated there. Honestly I don’t know what “xsatrrs” are. I can’t say I devoted a lot of effort to reading your code (code is fun to write, prose is fun to read), but you say that “all data is stored in two heaps” – maintaining a heap invariant involves h-many O(log(h)) operations for an h-entry heap, and if a round’s “RESTBITS” are included in these operations for each round even though they do not influence the current round in any way that is a lot of wasted memory bandwidth.
and view N-bit words as having K+1 “digits” of n bits each
Ah, this terminology is unfortunate when comparing with radix sorting. Hopefully everybody here realizes that the digits of a radix sort being used to produce equihash solutions are not the same as these digits except in the absurd limiting case where each item being sorted is considered to be one huge digit.
[quote=“krunkalunk, post:444, topic:2465”] “all data is stored in two heaps” – maintaining a heap invariant involves h-many O(log(h)) operations for an h-entry heap
[/quote]
It seems quite appropriate.
The 20-bit bucket sort that some solvers use is exactly like one round
of radix sorting with a 20-bit digit (rather than the usual 1, 2, or 4-bit digits).
Or maybe I misunderstand your terminology.
That’s what I thought. I don’t understand why they are not using existing sort packages for GPUs that people dedicated half their lives to creating.
Tromp, is there going to be any speedup for CPUs? GPUs are now $5 per S/s and 2 W per S/s (not counting “nobody”). Used Desktops are stuck as $8 and 3 W.
Since nicehashdev pointed out to me that my duplicate index test was suboptimal, I decided to study the nature of duplicates that it found.
It turns out that duplicates usually end up as the leftmost leaves of a left- and right-subtree. This insight leads to a vastly simpler duplicate test, which I implemented in both equi_miner.h and equi_miner.cu
The latter went from 23.6 to 24.7 Sol/s.
Gains are much smaller on the CPU side.
Thanks to nicehashdev for inspiring this optimization.
Your solver is great tromp can’t thanks you enough.
I tried a lot of cpu and a lot of nheqminer implementations. For now it looks like a 4 core cheap cpu intel is the way to go, there is not a lot of gain from avx1 to avx2 (for me) or from a cpu with hyperthreading, all cpu I tried are between 20-25 sol/s (only tried intel 4 cores, avx 1 or 2 with and without hyperthreading), my 4790K is not faster than my oc 2500k, maybe I should try with two memory stick or faster ddr. Anyway any little gain is good to take, thanks again
I’m equally thankful that my I did not have to sell all my desktops right away, and that I can keep them indefinitely compared to GPUs thanks to GPUs not improving much more on watts and depreciation of desktops being a lot slower. This is my first attempt at mining and I would not have been able to get GPUs running and I see people with more skill have not caught up to my 760 S/s. There’s been no hassle no tweaking and no instability (using xenoncat version). They just run and I forget about them.
What are the basics to choose a GPU for mining ? what one should check before choosing the GPU keeping in view the future improvements?
is it either CUDA core
base clock
boost clock
memory clock
memory rate
memory interface
fabrication processes
TDP
and what all have to be given importance while choosing a card?
can any one offer his in-depth analytical response
