Sunday, August 28, 2016
Saturday, August 27, 2016
GPUs vs CPUs in Zcash
An 8 GB GPU could run 2.5 more threads at 8x more bandwidth by simply porting the CPU code (no special parallelizing needed). The problem with the Equihash paper is that it reverenced a 2011 GPU and did not point out that modern GPUs have a lot more on-board RAM. So 2.5 x 8 = 20x is an upper limit. But the cores are operating at 1/3 the clock speed of CPUs and my experiments in acquiring blocks on the testnest indicate core-caching and/or clock speed on the CPU matters a lot. Either way, it indicates less than 2.5 x 8, maybe 8x benefit as a minimum. The important point is that this minimum is double the Equihash paper and it does not require any special programming that was required in the 4x claim of the Equihash paper. The paper referenced a 2011 CPU for the comparison, so I did not think there was a problem in looking at an old GPU as both have advanced. So the problem (if you wanted CPUs instead of GPUs) is that Zcash has chosen parameters that are good for 2011 but not for 2016. I am not being critical as I did not realize the implications myself until now. Even without the GUI, I could not get 4 threads to run good on 4 GB, and 6GB seemed to be even worse. So 8 GB is the demand. Since 8 GB is the demand, 750 MB/thread is not good. 1.2 GB should have been the requirement in order to allow ubuntu and to hold back GPUs.
=====
update to the above:
==========
The Equihash paper was from 2016. The GPU vs CPU data was from 2011. I wanted nothing more than CPUs to win, but an 8 GB GPU should be 10x better than a CPU at launch if they are no better than the stock miner. The Equihash paper assumed the cryptocurrency developers would choose a RAM requirement that is higher than on-board GPU RAM. But with new GPUs, a GPU coder can copy the stock miner and run it on 10 cores to get 2.5x more threads than a 4 core CPU at 20x the bandwidth (a $400 GPU). It's not 20 x 2.5 = 50x faster than CPUs only because the GPU cores are so slow. The 4x statement in the Equihash has nothing to do with this: by assuming the coin's RAM requirement would be larger than the GPU RAM, they assumed advanced parallel programming would be needed to make use of the GPU's many cores. That is not the case. Zcash was not able to force larger RAM, so the Equihash paper is not relevant as far as GPUs are concerned. They might could make the RAM about 1200 MB per core if they go to 5 minute intervals. This would reduce the GPU advantage to 7.5 by my above math.
But we have not actually seen any $400 GPU results faster than a $200 desktop.
=====
update to the above:
==========
The Equihash paper was from 2016. The GPU vs CPU data was from 2011. I wanted nothing more than CPUs to win, but an 8 GB GPU should be 10x better than a CPU at launch if they are no better than the stock miner. The Equihash paper assumed the cryptocurrency developers would choose a RAM requirement that is higher than on-board GPU RAM. But with new GPUs, a GPU coder can copy the stock miner and run it on 10 cores to get 2.5x more threads than a 4 core CPU at 20x the bandwidth (a $400 GPU). It's not 20 x 2.5 = 50x faster than CPUs only because the GPU cores are so slow. The 4x statement in the Equihash has nothing to do with this: by assuming the coin's RAM requirement would be larger than the GPU RAM, they assumed advanced parallel programming would be needed to make use of the GPU's many cores. That is not the case. Zcash was not able to force larger RAM, so the Equihash paper is not relevant as far as GPUs are concerned. They might could make the RAM about 1200 MB per core if they go to 5 minute intervals. This would reduce the GPU advantage to 7.5 by my above math.
But we have not actually seen any $400 GPU results faster than a $200 desktop.
Thursday, August 11, 2016
Zcash and energy-expense in cryptocoins may not be a bad thing
I mentioned computers are using 4x more
electricity when running Zcash. It may make GPU's less capable of
competing. They are not able to access the external RAM directly, so
they are less efficient, having to compute more per hash. The 4x speed
of parallel code for GPUs of the future will come with at least 2x more
energy cost.
From measurements on the testnet and my electricity use, if there are 50,000 PCs on the network, it will cost $1 per coin in electricity above 24 hour normal-use PC costs if you have a 22 nm process CPU that is meant to be efficient ( less than 3 GHz).
Although the high energy use is against what most people consider a "good" coin, it might be an inherent necessity if POW is inherently needed. The high energy use is key to making mining widely distributed. If the only thing determining the quantity of coin obtainable is the amount of energy purchased, then most people have equal access. Electricity rates can vary a lot compared to oil (e.g. islands & remote villages), but that is a small portion of the world's population. If a government subsidizes cheap electricity by investment or allowing more pollution, then the populace of that region have paid the price that local miners gain. If they optimize code and have cheap electricity, they might get 5x more coin per dollar expense compared to small miners.
If Zcash spreads to the populace who do not have to buy equipment and do not even notice they have higher electrical costs, mining may not be feasible. This is the stated goal. This means a general-purpose CPU needs to be biased for. This means more electricity to stretch its general-purpose skills. Sorts seem very specific, but they bias everything towards a more general purpose Turing machine. The entire basis of a Turing machine is reading and writing, and sorts need it in ways that are hard optimize in a way that reduces the need to read and write.
The RAM of devices is not generally being wasted like CPU time, so it might be better to be be CPU-centric. But part of the path to the general-purpose CPU is high RAM in order to block out non-general purpose GPUs and ASICs.
So it's a coin that promotes generalized computing devices in everyone's hands without taking away too much RAM, rather than wasting money on specific equipment for specific people (miners). This is a 2nd reason a higher electrical expense is not a bad idea: CPU time is being wasted more than RAM space. And note that RAM is not electricity-free. There is a very large initial electrical expense in creating the RAM, as indicated by it's price. This indicates equal use of CPU and RAM may be better as one is an on-going time-based expense of Joules and the other is a one-time capital "space-based" expense of Joules. CPUs require a Joules per bit state change in time, and RAM requires a Joules construction cost per bit storage space in cm^3. Of course RAM has state-change energy cost and CPU has construction cost, but those energy costs are smaller.
All economic schools have said following a basket of commodities is the best currency. Those favoring gold do so only because it is the best single commodity that has the right properties. It also one of the most wasteful ways to use kinetic energy, which is key to its perceived value. A basket would require measurements and "paper" (bits on a computer). The cost of energy (like electricity) is the largest underlying factor in the cost of producing commodities. So currencies based on Joules have been proposed as ideal. Zcash is a Joules-based currency. The Joules-as-value, both kinetic and potential, has a deep connection with computation and life. (see Note at bottom).
There is a 4th "benefit" to a high electrical cost per coin, although all these points are connected. It should not sell for less than the cost to produce it, unless someone has given up on the coin and will accept a loss.
Zcash's goal is to be "democratic" in mining. The result is an ideal cryptocoin. POW should not be "might is right", but "distributed might is right". Otherwise, the ability of miners to lobby the governing coders becomes the wrong kind of might.
This is not to say an energy-intensive coin is best for society. A coin that is given based on how much a person helps society (such as Solar Coin) would be best. But that involves agreement on definition of what is "best" (are solar cells really the best use of your money to be subsidized by giving you a coin?) and then measuring it before the cryptography part can even begin. It is a type of fiat requiring a middle man (or at least a group of oracles that are doing an agreed upon measurement, governed by smart contracts that define the rules for the distribution use of a specific coin). The whole reason fiat replaced gold is because governments are able to print it and distribute it evenly based on achieving goals that are ostensibly best for that society. Coins distributed based on POW that is not connected with the betterment of society are not best unless the government is not acting in the best interest of people and/or anarchy (e.g., hyperinflation) is near.
Note: To be more correct, it is the Joules as measured by Gibb's Free Energy that is essential to life. Schrodinger even updated his "What Is Life?" book to point out that when he said "negative entropy" as being the key to life, he really meant free energy. Gibb's F.E. = U -TS where U is internal energy and TS is temp x entropy. In terms of Zcash, U=RAM+CPU capital one-shot "energy" expense and TS=CPU operating on-going energy expense. The first is energy stored in spacial RAM and CPU structures, and the second is energy spent in time. CPU computations come at an energy cost of TS/eff where eff is the efficiency of the device. This does not include algorithm efficiency. Per N bits that change state irreversibly, the number of Joules expended is T x S / eff (see Landauer's limit relating bits to physical entropy) where S=kb x ln(2) x N. For a given algorithm.
From measurements on the testnet and my electricity use, if there are 50,000 PCs on the network, it will cost $1 per coin in electricity above 24 hour normal-use PC costs if you have a 22 nm process CPU that is meant to be efficient ( less than 3 GHz).
Although the high energy use is against what most people consider a "good" coin, it might be an inherent necessity if POW is inherently needed. The high energy use is key to making mining widely distributed. If the only thing determining the quantity of coin obtainable is the amount of energy purchased, then most people have equal access. Electricity rates can vary a lot compared to oil (e.g. islands & remote villages), but that is a small portion of the world's population. If a government subsidizes cheap electricity by investment or allowing more pollution, then the populace of that region have paid the price that local miners gain. If they optimize code and have cheap electricity, they might get 5x more coin per dollar expense compared to small miners.
If Zcash spreads to the populace who do not have to buy equipment and do not even notice they have higher electrical costs, mining may not be feasible. This is the stated goal. This means a general-purpose CPU needs to be biased for. This means more electricity to stretch its general-purpose skills. Sorts seem very specific, but they bias everything towards a more general purpose Turing machine. The entire basis of a Turing machine is reading and writing, and sorts need it in ways that are hard optimize in a way that reduces the need to read and write.
The RAM of devices is not generally being wasted like CPU time, so it might be better to be be CPU-centric. But part of the path to the general-purpose CPU is high RAM in order to block out non-general purpose GPUs and ASICs.
So it's a coin that promotes generalized computing devices in everyone's hands without taking away too much RAM, rather than wasting money on specific equipment for specific people (miners). This is a 2nd reason a higher electrical expense is not a bad idea: CPU time is being wasted more than RAM space. And note that RAM is not electricity-free. There is a very large initial electrical expense in creating the RAM, as indicated by it's price. This indicates equal use of CPU and RAM may be better as one is an on-going time-based expense of Joules and the other is a one-time capital "space-based" expense of Joules. CPUs require a Joules per bit state change in time, and RAM requires a Joules construction cost per bit storage space in cm^3. Of course RAM has state-change energy cost and CPU has construction cost, but those energy costs are smaller.
All economic schools have said following a basket of commodities is the best currency. Those favoring gold do so only because it is the best single commodity that has the right properties. It also one of the most wasteful ways to use kinetic energy, which is key to its perceived value. A basket would require measurements and "paper" (bits on a computer). The cost of energy (like electricity) is the largest underlying factor in the cost of producing commodities. So currencies based on Joules have been proposed as ideal. Zcash is a Joules-based currency. The Joules-as-value, both kinetic and potential, has a deep connection with computation and life. (see Note at bottom).
There is a 4th "benefit" to a high electrical cost per coin, although all these points are connected. It should not sell for less than the cost to produce it, unless someone has given up on the coin and will accept a loss.
Zcash's goal is to be "democratic" in mining. The result is an ideal cryptocoin. POW should not be "might is right", but "distributed might is right". Otherwise, the ability of miners to lobby the governing coders becomes the wrong kind of might.
This is not to say an energy-intensive coin is best for society. A coin that is given based on how much a person helps society (such as Solar Coin) would be best. But that involves agreement on definition of what is "best" (are solar cells really the best use of your money to be subsidized by giving you a coin?) and then measuring it before the cryptography part can even begin. It is a type of fiat requiring a middle man (or at least a group of oracles that are doing an agreed upon measurement, governed by smart contracts that define the rules for the distribution use of a specific coin). The whole reason fiat replaced gold is because governments are able to print it and distribute it evenly based on achieving goals that are ostensibly best for that society. Coins distributed based on POW that is not connected with the betterment of society are not best unless the government is not acting in the best interest of people and/or anarchy (e.g., hyperinflation) is near.
Note: To be more correct, it is the Joules as measured by Gibb's Free Energy that is essential to life. Schrodinger even updated his "What Is Life?" book to point out that when he said "negative entropy" as being the key to life, he really meant free energy. Gibb's F.E. = U -TS where U is internal energy and TS is temp x entropy. In terms of Zcash, U=RAM+CPU capital one-shot "energy" expense and TS=CPU operating on-going energy expense. The first is energy stored in spacial RAM and CPU structures, and the second is energy spent in time. CPU computations come at an energy cost of TS/eff where eff is the efficiency of the device. This does not include algorithm efficiency. Per N bits that change state irreversibly, the number of Joules expended is T x S / eff (see Landauer's limit relating bits to physical entropy) where S=kb x ln(2) x N. For a given algorithm.
Thursday, August 4, 2016
Note to self: cryptocurrency difficulty settings
I estimated above that the difficulty setting's averaging of the past in order to determine if coin production is on track or off-track should be 3 x N / SQRT(N). It's almost a perfect curve fit for a coin's expected deviation from a Poisson distribution, allowing for up to 3.75 standard deviations from the Poisson distribution's expected mean. This high level of permission allows for network hiccups away from the mean that someone could profit from if they can cost-effectively shift hashing energy around to different time slots. They'll be able to detect a deviation with decent probability each hour (N=30 rule) before the code decides in a difficulty change.
Poisson distribution with 3.75 std devs from mean:
3.75 x 2 e^-N x N^(N+1) / N! =~ 3 x N / SQRT(N)
If you want to minimize profit from hiccups, you could remove the 3.75 to allow for 1 std dev from the mean. The drawback is that this means that 1/3 of the time you will be intervening with a change in difficulty where none was statistically present, instead of ~0.01% of the time with 3.75. 3.75 is too permissive.
With the current method, the algorithm appears to be intervening too much with too-large changes that are too-often. It seems like a nosy government regulator, acting beyond what the statistics requires. It is donating easy coins to slow transaction periods at the expense of the small business owner (miner), to the benefit of the more-talented, conglomerated smart businesses selling a service (shifting hash energy) to the slow transaction periods. I would use 2 std devs instead of 3.75 as a nod to statistical tradition. The current code is using something like 0.1. [edit correction: after N=6 intervals
It's not merely hiccups it's trying to fix, but also the distribution itself allows for a sparse period of transactions. The Poisson distribution says the probability of k=1 occurrence in N=6 intervals (15 minutes) is (N L)^k / k! / e^(N L) = N/e^N = 1.5% where L = the average of 1/2.5 minutes, so NL= average occurrences in N x 2.5 min intervals. So there will be an average wait of 1/0.015=67 intervals for it to take 15 minutes. It would take 30 minutes once every 23 days.
Poisson distribution with 3.75 std devs from mean:
3.75 x 2 e^-N x N^(N+1) / N! =~ 3 x N / SQRT(N)
If you want to minimize profit from hiccups, you could remove the 3.75 to allow for 1 std dev from the mean. The drawback is that this means that 1/3 of the time you will be intervening with a change in difficulty where none was statistically present, instead of ~0.01% of the time with 3.75. 3.75 is too permissive.
With the current method, the algorithm appears to be intervening too much with too-large changes that are too-often. It seems like a nosy government regulator, acting beyond what the statistics requires. It is donating easy coins to slow transaction periods at the expense of the small business owner (miner), to the benefit of the more-talented, conglomerated smart businesses selling a service (shifting hash energy) to the slow transaction periods. I would use 2 std devs instead of 3.75 as a nod to statistical tradition. The current code is using something like 0.1. [edit correction: after N=6 intervals
It's not merely hiccups it's trying to fix, but also the distribution itself allows for a sparse period of transactions. The Poisson distribution says the probability of k=1 occurrence in N=6 intervals (15 minutes) is (N L)^k / k! / e^(N L) = N/e^N = 1.5% where L = the average of 1/2.5 minutes, so NL= average occurrences in N x 2.5 min intervals. So there will be an average wait of 1/0.015=67 intervals for it to take 15 minutes. It would take 30 minutes once every 23 days.
Subscribe to:
Posts (Atom)