Ternary circuits: R=3 is not the Optimal Radix for Computation (2019)
arxiv.org
arxiv.org
Not sure what the author was thinking when he wrote the paper but this is one of the cases where peer review would have helped him a lot to make less grand statements.
>Until tri-state transistors are mass produced binary encoding of numbers is the natural system for computers to work in.
From memory the Setun used vacuum tubes which could natively handle three states at the hardware level.
The high clock speeds we get rely on fast switching of power levels, this is generally done by targeting a voltage well beyond the switching threshold. The smallest transistors we produce generally have a big variability in amplification, they would be really bad for analogue circuitry, but in digital they just have to amplify enough, and it is ok if some of them amplify way better than that.
Now consider tri-state, we have to target a voltage in the middle band if we are to produce the middle signal, so less room for over-targeting means slower switching. We probably also need to supply the whole circuit a higher voltage to make proper room for the signal levels, that is a big L in efficiency.
One could build a circuit with three levels of input current, but that ends up more or less doubling the transistor count, so not an obvious win. I guess that is what the Setun did. If adding this complexity to a tube doesn't increase its cost much I guess that makes sense, but in the transistor world it is just a doubling.
Ternary logic is used in data converters (Analog-to-digital and digital-to-analog) with succes. This is because these circuits are often differential, so for each 1 there is a -1 on the complementary side. Let's say it's a current steering DAC. For 1 the positive end will sink +1 unit current while negative end is sourcing +1 (effectively -1). We get -1 if we flip the positive and negative. 0 can be created by turning off the currents. The beauty of it is the 3-levels we created are inherently linear, which doesn't extend to higher bases! The DAC unit in this example is in logic terms a CML ternary inverter! It doesn't consume any power when in 0 state, so it improves CML power cobsumption too (>50% for uniform data activity).
Now we established that it is possible to implement ternary logic: why is it not used? Because CMOS logic only consumes power during transition (dynamic power) while CML consumes quite a bit higher static power always. Actually CML can work at much higher speeds but it's gobe out of fashion because Moore's law till recently gave more transistors in the same area operating faster than the previous generation. When the Moore's law is died a slow death we went for increasing the die sizes by doing more in parallel than faster logic, because for complicated reasons CMOS is quite efficient when operating much slower than the speed limits of technology. This being said, there might be areas CMOS logic can be replaced but people don't do it because they don't think about the possibility. At least this is my observation in the field.
The primary point of CML is that a differential signal is interference resistant. Therefore it can be used for higher data rates in out-of-chip buses. It does not provider faster ALUs than CMOS.
CMOS logic can also be differentially routed, and often is routed against interference. That + a full shield around sensitive routing like clock lines are standard practice. Both have the advantage of cobtaining the return current too.
I'm not suggesting we switch to 3 wires for ternary. That would be stupid. Ternary CML is 2 wires. 10, 00, 01 with 11 being the forbidden state or having the same functionality of 00. This isn't efficient from routing perspective compared to single-ended CMOS.
For large routing distances any kind of encoding can be used. I often use 2 dimensional (row-column) encoding/decoding for multi-GHz data busses travelling over long distances (like 500um to couple of mm). It's very easy to calculate the power cost and routing area cost of not using any emcoding with respect to doing an n-dimensional encoding (incl. the power and area of encoder/decoder). I even used a 3D encoding which reduced total routing channel area and power in a routing dense setup like 50%. Using a simple kind of coding like parity bit and multiplying the data with a random sequence is also used against interference but people often don't do this and regret it..
Anyhow, the point I'm trying to make is local logic and long distance routing are two problems with different optimization parameters.
Fun fact unrelated to your main point: some ancient peoples counted on their knuckles, using their thumb to point to each one. This let them count in multiples of 12 (3 knuckles on each of 4 fingers), then use their other hand to count out multiples! You can count as high as 72 this way, which was great for ancient cultures oriented around highly composite numbers like 12, 24, and 60.
I don’t know how “ancient” you’re talking about: my mother (b. 1937) used such a system and taught it to us as kids. FWIW she grew up in south east Asia.
12 knuckles/finger segments, incrementing by 1 on the left hand for each completed counting of 12 on the right = 12 * 12 + 12 = 144 + 12
I may have misunderstood the proposed counting method however.
Therefore any transistor, triode or any other controllable device has only 2 states, i.e. on and off, where the power consumption is negligible.
Any kind of logic circuits that use transistors or triodes that stay in any other intermediate states between on and off (like in analog circuits) would consume too much power and would overheat. A MOSFET can have any intermediate state between on and off, the current through it can be varied continuously as a function of the gate voltage, but it will dissipate a great amount of power in any of the intermediate states. There is no difference from this point of view between MOSFETs and vacuum tubes. Setun just had too few and too big vacuum tubes to worry about the power consumption.
The kinds of logic circuits where not all transistors or triodes are on or off have been abandoned 40 years ago and there is no chance for them to ever come back, because at the current component densities their power consumption would be enormous.
The only way to use devices with more than 2 states in logic circuits would be to use devices with a variable reactance, for instance varicap diodes, because those do not consume active power.
However the devices with controllable reactance cannot use DC power supplies, they need AC power supplies, which creates a lot of problems for which there are no known solutions at this time, so nobody has designed yet a complex logic circuit based on controllable reactances instead of transistors.
As long as electronic devices with DC power supplies will be used, binary logic is the only kind of logic permitted by the energetic constraints.
Only in the non-volatile flash memories, multiple values of electric charge can be stored in a capacitor, because it does not consume any power for storage.
DRAM also uses a capacitor to store data so it could support more than one bit per cell too.
Using multiple values for the stored charge would force a drastic reduction in the refresh time, which would increase the power consumption and diminish the read/write throughput.
That was the original intent, but they could never make it work reliably. The machine that ran had all the ternary logic implemented on top of the usual binary circuits (effectively wasting one state out of four).
A paper about high efficiency tri-level logic cell which is cheap and energy-efficient would be very interesting but sadly I don't think this is possible, at least I haven't seen one nor even have a clue about how one would go about making one. And I have been watching this area with interest.
I'd be curious whether the same result holds for balanced ternary, as used in some early Soviet computers. https://en.wikipedia.org/wiki/Balanced_ternary
I did notice the paper hinging on a lot of implementation details. For one, they only propose using voltage dropping resistors, but no discussion of having three power rails (eg +1, 0, -1), or some hybrid approach. Maybe some part of power regulation belongs outside the chip, folks!
They also implement a ternary adder by.... converting it back and forth to binary! They justify this by saying this is the only way to implement an "arbitrary" truth table. Okay. You don't need an arbitrary table, just one! The truth table, of course, depends on the choice of balanced vs. unbalanced. This seems like an unforced error.
The paper's result (if confirmed) might indeed hold for balanced ternary, but it's not immediately clear that this is a trivial extension of the existing paper.
The Setun computer, mentioned in the introduction, however, used balanced ternary with values -1, 0 and 1. Balanced odd bases consist of digits centered around zero.
Could balanced ternary redeem it's position with logic cirtuits in mind?
Here's a little ternary logic riddle for the HN community:
Two people are sitting at a restaurant, deciding what to order. Neither had communicated with one another when the waiter appears and asks one of them "Is everyone ready to order?". They reply "Hm, I don't know". The other person immediately then says "Now we are." Why?
(As in, how did the second person know?)
If the first person did not want to eat, he would have answered "No, we are not ready". Him not being ready is enough to negate the whole thing. He doesn't know if the both of them are ready to eat though, because he doesn't know that the second man is ready or not (the second man hasn't revealed his state yet).
Therefore, the second man knows that the first is ready to eat, since the first's answer is "I don't know". Since the second man knows that he himself is ready to eat, he can answer: "we are both ready to eat".
Person B then can safely assume Person A is ready and if they are ready themselves they are now indeed ready.
So the second person knows that the first person is ready
Not sure if I explained that part well, but I can write the riddle somewhere and share it one day, since it needs to be explained more precisely to demonstrate this N-people effect.
It also assumes they're directly answering the question instead of indirectly answering it.
Not sure I understand that. Did you mean it assumes that person B has figured out that person A is ready?
The way Bob found out that Alice was ready was because Alice was uncertain about group readiness.
Maybe Alice was uncertain because she knew her own readiness but not Bob's readiness. This is the way the riddle works.
But maybe Alice wasn't sure of her own readiness. In that case Bob should not answer.
-
And, second issue, what if Alice was saying "Hm, I don't know [what to pick]." as a way to tell the waiter that no, everyone is not ready.
I'm not sure I understand how Alice could be unsure of her own readiness. If she's not ready, then she would have said "no, everybody is not ready to order."
> And, second issue, what if Alice was saying "Hm, I don't know [what to pick]." as a way to tell the waiter that no, everyone is not ready.
Because the riddle is "how did he [Bob] know?". We are told from the start that Bob is right, and asked to explain why.
You don't understand how someone can be unsure if they're ready? Have you never been kind of anxious or indecisive before? (The answer is definitely not "you're not ready until the anxiety and indecision are gone".)
> Because the riddle is "how did he [Bob] know?". We are told from the start that Bob is right, and asked to explain why.
There's a reason I said "in the real world".
Modern comms systems are heading in that direction with OFDM and large QAM constellations with lots of ECC to get more data throughput for the same transmit power on the same channel.
One day we might get to need to do that for computation too - but for now, binary is doing well.
They are not at all efficient from the point of view of the energy consumption.
The best energy efficiency is achieved with quadrature phase modulation (QPSK), which allows very low transmission powers relative to the noise of the communication channel.
Any increase of speed above that is obtained by a worse energy efficiency.
Despite that, OFDM and large QAM constellations are very frequently used because for the modern WiFi or mobile phone communication it is typical to be very close to the access point or to the cell phone tower so the transmitter is able to use a power much greater than the minimum necessary, in order to increase the data throughput.
For logic circuits, the constraints are very different than for communication channels. If the logic circuits use DC power supplies, then the controllable elements, like transistors or vacuum tubes, must use only 2 states, on and off, otherwise they would consume too much power. So even if one would want to make a gate with ternary logic, it would have to be composed of transistors with binary states, otherwise it will overheat at the current circuit densities.
In fact, QPSK is just a type of QAM with a constellation size of 2.
At some point, maybe you end up not doing exact computation but basically creating neural-like architectures that learn responsibilities, which compose up to a fully functional computer.
More than that, the ratio of channel energy (or cost) requirement to computational energy can vary :) For example, if you're transmitting a message to a space probe, the energy and costs associating with message transmission are enormous, such that the decoding energy will be a lower proportion (favoring more complex decoding systems). For a computer bus transmitting signals internally at short distances, the energy cost of encoding (and even using QAM or non-binary encoding at all) and statistical decoding will probably be less than the energy gains.
Credit to Christopher Blake et. al in this paper: (as seen on Canadian Workshop on Information Theory :) )
https://tspace.library.utoronto.ca/bitstream/1807/69482/1/IT...
From the abstract: "This implies that the average energy per decoded bit must approach infinity for any sequence of decoders that approaches capacity" (valid for the VLSI model in question, and binary channel model, but I'd guess this generalizes to any physical computational medium)[2]
It's really interesting how in the context more complex isn't always better.
[1] Usually the complexity of the whole system, in more practical terms, is determinant as well -- because engineering and maintaining complex systems is difficult
[2] More precisely: "It is shown that for any sequence of increasing-block-length decoder circuits implemented according to this model, if the probability of block error is asymptotically less than 1/2 then the energy of the computation scales at least as Ω (n√log n), and so the energy of decoding per bit must scale at least as Ω (√log n)"
Now, if you are going to build trenary circuits out of binary flip flops, you are wasting one state available out of 4 with two flip flops, so clearly suboptimal. You need unique interfaces and physics for each element to benefit from efficiency. Even unique programming languages - binary if/else logic is common, it could be that in real world if/else/unknown is common and can be handled more efficiently by trenary circuits, or new algorithms can be created to utilize a hardware-implemented trenary bit.
Of course, a likely answer is that, now that binary hardware and software is highly developed, it's not worth it to do complete redesigns for modest efficiency gains.
And "existing software" never stopped innovations: we get all-new computation models all the time.. there are FPGAs and IRAMs and transputers and memristors and analog AI, and perhaps even GPU and DSP. None of them can use existing binary software and some of them have non-binary hardware. They don't all work well all the time, and yet people keep innovating and trying to find ways to make them work.
And yet no one (outside of hobbyists) works on ternary computers. Physics is harsh.
Is this some weird attempt at humour, or meant as a serious statement? I mean the mention of e of course.
So assuming x > 1, this is minimized precisely when b/log(b) is minimized. The derivative of b/log(b) is (log(b) - log(e))/log(b)^2, so this is zero when b = e. (The second derivative is 1/(e log(e)) > 0, so this is a minimum).
To me this seems like the weak point in the argument.
Simple example, base 1 is obviously inefficient once counting past 1. Similarly base 1 million is inefficient (until you're counting in the bazillions)
But it's about 20 times more efficient when it comes to storage of whole numbers because you can store number up to a million in a single physical elements while binary needs 20 elements.
In the example you gave, I'm assuming by 'physical element' you mean 'placeholder' or digit. Storing more numbers in a single placeholder seems like you're just getting efficiency for free, but that's not how information works. You have to come up with a unique symbol for one million numbers (0 - 999,999). Which you have to pay for.
base 64 is a more realistic example. With 64 characters per digit, it may seem like it's more efficient, since you require less digits to express the same number as base 10 or 2, but you still have to encode 64 unique characters, and it ends up being less efficient. That doesn't mean less efficient is worse. It just means it is more specialized and used for different things. For example, base64 gets used when you want to encode information in a small amount of space. Otherwise, for the actual storage and computation of data, lower bases are preferred, and base 64 is still obviously stored as binary.
For what it's worth, the base integer with the best radix economy is 3, followed by 2.
I see that radix economy makes some sense if you assume that the "cost" of the "element" is not fixed but linearly proportional to the number of different states it needs to hold. It was apparently linear for the computers built with triodes but log2(n) to hold n states seems more realistic in electronics. Maybe little more for error resiliency.
Repeating the calculation (for k bits and b values) using square values, you get E = b^2 * log_b(k) and dE/db = 2b/ln(b) - b^2 / (ln(b))^2 / b = b/ln(b) * (2 - 1/ln(b)). Setting dE/db to 0, we get 2 - 1/ln(b) = 0, ln(b) = 1/2,
b_opt = sqrt(e) = 1.6487...
Which base is optimal then? 2? Any?
In this case, the average voltage used would be the average of 0, 1, 2^2, 3^2, which is 0+1+...+(b-1)^2 / b ~ b^2 (proportional to b^2). I showed that in this case in theory the "optimal" base would be sqrt(e), but I can't think of simple representations of a variable with less than 2 states (you could have say 2 variables representing less than 4 states, for example the 3 pairs { 0V/1V, 1V/0V, 0V/0V }, but that seems a tad complicated![1]), so the least non-trivial integer base is just 2.
I think in reality this kind of argument doesn't apply to real computers in a straightforward way, because there are many other factors at play than what I would call a 'dynamic power consumption' associated with the square voltage. There are things like leakage currents (that consume some fixed power per transistor) and other effects that significantly complicates things, so that such simple claims of being "optimal" don't apply (so I agree with the other comment about avoiding absolute claims!). But they can inspire designs and we can see if there are any advantages in more realistic cases.
[1] Further analysis: In our example, the 3 voltage pairs have mean square voltage 1/3. If we instead use the pairs { 0V/0V, 0V/1V, 1V/0V, 1V/1V }, the mean squared voltage is 1/2. In the first case, we encode log2(3)/2 bits of information per voltage value, in the second, 1 bit per value. So the energy per bit is (energy per value)/(bits per value) = (1/3)/(log2(3)/2) = 0.420... for the first case, and 0.5 for the second case. Unfortunately, it's a loss!
As an exercise, I believe that if we delete the state 1V/1V/.../1V of a k-voltage tuple, for large enough k-tuple, we come out ahead (probably not by much), although again that's not necessarily useful in practice.
This paper is just showing that with real technology it's still less efficient than 2. I don't think anyone was really suggesting that we switch to base 3 hardware so it's a completely academic result, but still interesting.
S.L. Hurst, “Multiple-Valued Logic - Its Status and Its Future“, IEEE Trans. on Computers, VOL. C-33, No 12, December 1984.
According to that demonstration, e would be optimal, but it is impossible because it is not integer. Among integers, 3 is best, followed by 2 and 4, which are equally good.
However, as mentioned in the article, the difference between 2 and 3 is very small and that classic demonstration does not take into account the difference in the complexity of the logic gates and registers for binary and ternary logic.
So no, some people really clamor for all of us to switch to ternary logic.
> For computation, radix R = 3 would be more economical than R = 2 because the “optimal” radix would be R = e = 2.718, according to a demonstration presented in [1].
Where [1] is "S.L. Hurst, “Multiple-Valued Logic - Its Status and Its Future“, IEEE Trans. on Computers, VOL. C-33, No 12, December 1984." I can't find that one for free anywhere, but there's your lead.
“100 in decimal has three digits, so its radix economy is 10×3 = 30; its binary representation has seven digits (1100100 2) so it has radix economy 2×7 = 14 in base 2; in base 3 its representation has five digits (10201 3) with a radix economy of 3×5 = 15; in base 36 (2S 36) its radix economy is 36×2 = 72.” https://en.wikipedia.org/wiki/Radix_economy
The idea being that there’s a tradeoff between the cost of each digit vs the number of digits you need. However we use base 2 because the cost of base 3 is more than 50% higher than using base 2.
This was a ternary computer built by Soviet mathematicians
> Between 1965 and 1970, a regular binary computer was used at Moscow State University to replace it [setun] Although this replacement binary computer performed equally well, it was 2.5 times the cost of the Setun.[2]
> Due to the low reliability of the computer elements on vacuum tubes and inaccessibility of transistors the fast elements on miniature ferrite cores and semiconductor diodes were designed.
Perhaps trinary is a good idea if you don't have access to transistors or to reliable vacuum tubes, but do have access to diodes and miniature ferrite cores.
I don't see however how this is relevant today - we certainly have access to great transistors now, and as the paper shows with transistors, binary rules.
Those who understand ternary. Those who don't understand ternary. And...