I think there's some good info in this article covered by various degrees of misinformation. For some reason, the article starts off with this totally wrong definition of big-O, and proceeds to make conclusions with this wrong definition. Let me provide the accurate definition:
The statement "f is O(g)" means there exists some input, call it t, such that for every x >= t, it only takes some constant multiplier M (i.e., constant in x) to always have g absolutely no smaller than f. In notation:
|f(x)| <= M * |g(x)|, where x is at least t.
This bit about "x is at least t" is very important and notifies us that this is "asymptotic behavior".
It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything.
Furthermore, according to the above definition, big-O has nothing to do with any tangible quantity whatsoever. It's a method for comparing functions. The functions may represent whatever is of tangible or intangible interest: memory, time, money, instructions, ...
Big-O analysis usually posits that the details below t aren't the details that matter. (Of course, there are situations where they do, but in such you would not use big-O.) If you want to have some analysis that is global, you don't need asymptotic analysis (though it might help as a start). You can just talk about functions that are strictly greater than or less than your function of interest everywhere. But these analyses are difficult because a much higher level of understanding of your function of interest is required.
> It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything.
Yes, but if you continue reading the next post, the author is essentially arguing that the cache hierarchy extends indefinitely due to 1) the speed of light and 2) the amount of information that can fit within a light cone of a certain radius.
In that case, cache hierarchy effects aren't 'weird things that happen below t', they represent the asymptotic behavior we can expect due to the laws of physics, no matter how far out to the right we go.
I think it's great to make such arguments but a bit more rigor would be appreciated in such theoretical constructions. If the main point to get across is in Part II, and Part I does not support Part II, as a matter of convenience, I would elide Part I.
I wouldn't. It's nice to show these effects in practice. In fact, I would have added a part 1.5 that gave theoretical bounds for how much heat can be dissipated from a volume that contains N bits.
Heat dissipation is proportional to the surface area, so this suggests a reason that information density is (physically) bound by surface area, rather than volume.
Another factor that gives the same limit in theory is gravity. If you have a volume of space and start shoving hard drives in it, eventually the hard drives will collapse into a black hole, and your information density is limited by the surface area of the black hole—again, giving you O(R^2) bits of storage for a volume with radius R.
Interesting. Perhaps a stupid question but is this somehow related to the recently proposed theory which says that the universe is essentially a hologram?
One way it's related: if a volume's information only depends on its surface area, then you can imagine the volume is really just a hologram with the same number of bits, and the bits are directly embedded on the surface of that hologram.
How are those counterexamples? I'm not talking about abstract mathematical geometry, I'm talking about actual physics. A paper that says "just drill infinite holes in a cube" isn't relevant here.
Stuffing hard drives together until they form a perfect Schwartzchild black hole is hardly "actual physics", so I posited we're long into abstract constructs giving theoretical upper bounds.
Worrying about the speed of light in processor caching these days is like putting a spoiler on your cart and horse to reduce drag. It might matter eventually, and that's kind of cool to think about, but it's absurdly negligible with the technology of today. Processors today are orders of magnitude slower than that.
"Even if signals in the chip were moving at the speed of light, a chip running above 5GHz wouldn't be able to transmit information from one side of the chip to the other". Note that a light-nanosecond is about a foot, so I'm assuming this is talking about the propagation delay of electrons in silicon that need to go through gates, which I'm sure is much slower than light in a vacuum.
To put this another way, you can view the scaling law as a hard upper bound on the speed of access to data; engineers can only approach that bound from below as technology improves.
But given a certain level of technology, it's easier to make a faster L1 cache than an L2 cache, and that will hold even as we approach theoretical limits.
A bit of a nit: We're not worried about the propagation of electrons over distance as much as we're worried about the propagation of the electric field. Electrons move too slow, the electric field moves much faster.
> which I'm sure is much slower than light in a vacuum.
Speed of signal in copper is about ⅔c, I suspect silicon will be in a similar ballbark – and the metal layers linking the silicon layers are made of copper anyway. So it's about 8"/ns… and the (three dimensional, 10+ layer) signal routes are anything but a straight line.
The speed of the signal depends on the properties of the surrounding medium though, right? You get one speed through copper in air but another speed entirely for copper in silicon.
And another for pure silicon, and others for the various doped silicons, …
I don't even know what the actual materials are with current technologies, but whatever it is, the speed will be much lower than the vacuum speed of light.
Well, that depends on the context. You're totally right in general, but for the purpose of order-of-magnitudes of maximal clock rates, the speed of light hardly varies. I can't find any normal, plausible processor material with a refractive index of 4, let alone 10. So while light in silicon may well travel [almost 3.5 times](http://refractiveindex.info/?shelf=main&book=Si&page=Chandle...) more slowly than in a vacuum - which is hardly nothing, at the granularity we're talking about I think it's not a huge issue. But that's just perspective - clearly the materials matter and will affect signal transmission speeds, and probably even today impose significant (if indirect) limitations.
It's possible weird dopings or quantum effect change this dramatically, I suppose. But if I had to guess, they don't.
And that's such a hard problem that you don't even have to go down to CPU scale for it to matter.
If you look at mainboards (or some smaller PCBs), the connecting lanes between e.g. RAM and CPU closer to the centre are often zigzagged, to match the lengths – and delays – of the necessarily longer outer lanes. The speed of light is actually really damn slow.
Well, not entirely. For data signals in general you just need all the lines to resolve to the desired value before the clock. You do need to be very careful about the clock, though.
Surprisingly, the behavior at that speeds is fairly well known. I don't even think you need to move from FR4 to a more controlled material (e.g.generally in mmWave, Isola FR408, along with sometimes Rogers stuff, IME, is what is used). Allegro PCB SI(Signal Integrity) even models high speed timing fairly well at the design stage.
You've got plenty of stuff at the test stage too. E.g., the gear on high-end Lecroy's metrology test gear is at 100ghz. Agilent (Keysight, whatever, it's still HP to me) has a full test rig for USB3.1[0] at 10gbps for their consumer level gear (again, fairly slow). Step it up to FPGA speeds and here's[1] an app-note by Altera with way higher speeds.
Here's a really brief overview of 'rules of thumb' that work up to PCI-e[2] by TI. 50 minutes and worth a watch. Clean power that won't couple in, matching lines lengths on diff pairs, proper isolated ground planes (give AGND and DGND their own layers) and proper termination will easily get you 95% of the way there.
(Shameless promotion-- available for high-speed design, pre-EMC compliance testing, fault diagnostics, etc).
>"Even if signals in the chip were moving at the speed of light, a chip running above 5GHz wouldn't be able to transmit information from one side of the chip to the other".
That's almost completely misleading. Except for the clock itself, nothing that happens inside a processor takes a single clock cycle. And clock distribution delays need compensation anyway.
That's also true of memory. No one has ever seen 1-0-0-0 CAS RAM. (And no one ever will.)
It's true that pushing up against distribution times makes topology more complicated and lowers the maximum possible speed.
But that's actually the difference between electronics and photonics, which promise to run many orders of magnitude faster than EM-based silicon design. (I've seen "millions" quoted, but that may turn out to be hyperbole. Even so - optical fibre can run at tens of Tbps.)
Of course there's a difference between transmission speed, which is a function of the speed of light, and maximum data rate, which is a function of bandwidth.
But unlike electrons-in-silicon connections, photonics may not need to be 100% serial. It's entirely possible to get multiple data channels down a single line with frequency multiplexing, and perhaps also by phase rotation.
That has huge potential to change the packing density and the speed of processor designs; potentially you could have processor elements that were massively parallel but connected with single lines.
There's also some hope that because power dissipation shouldn't be such a problem, it will be easier to make 3D designs - although that's probably more speculative.
Bottom line is silicon is nearly done, but photonics is just getting started. Like fusion power it's probably a couple of decades away, but when it arrives it will be huge.
Most stuff that happens inside processors takes a single cycle, and we used to have single-cycle RAM until the CPUs ran away with increasing speed.
Photonics has a serious density problem: visible light is too large in terms of wavelength. This is already an issue with etching silicon. It's also at best at the 1950s stage where people have developed single photonic transistors in the lab but not yet photonic VLSI.
Anyway, the main factor of delay in chips is capacitance, both between wires and on the gates of FETs. This must be charged through the on resistance of the driving FET and all the intermediate wiring.
So, what you're really saying is that it's quite accurate, there are just details and more details but in the end - as long as we use a single clock - signals need to be able to travel from one end to the other in a single clock cycle.
Now, if we had (partially) clockless processors...
Also, your details are a lot more misleading than those in the article. lots of things in a modern processor take 1 clock cycle. Agner has lovely tables:www.agner.org/optimize/ and note that most basic integer and floating point operations on a skylake processor take 1 cycle - things like bit shuffling, moving, adding (not floats), and quite a few incidental other operations. Now, I'm sure you can quibble that a latency of 1 cycle in that table isn't really 1 cycle under some unusual interpretation of what's going on, but at that point you're quibbling about what "doing something" means, which isn't helpful. What programmers/compiler writers call 1 clock cycle can execute what most people call 1 instruction for many common instructions, even today.
On the massively-parallel-connected-with-single-lines theme, there's been some interesting work done with on-chip RF, which does essentially the same thing with conventional silicon.
If anyone talks about signals crossing the chip in a single cycle, they're barking up the wrong tree. It's absolutely unnecessary. It would not take a tremendous engineering work to make a CPU where signals go no more than 3mm or even 1mm in a cycle. (At 5GHz you have a distance budget of over 40mm.) The most important constraint for single-threaded operation is transistor switching time. It's likely the most important constraint will always be transistor switching time.
Transistor switching time is limited mostly by electrical capacity which is determined by the permittivity of the material the transistor is made from. And permittivity and permeablity are the only things determining the speed of light in a material. So saying that speed of light is the limiting factor of transistor switching time is valid.
The downforce isn't there to counteract air under the car (actually fast flowing air under the car produces downforce; read up on ground effect and Bernoulli).
The downforce is there so the car can go around corners quicker; the downforce increases the friction (Ff<=mu x Fn), i.e. the force of friction is less than or equal to the coefficient of friction (mu / μ) multiplied by the normal force. In the case of a tire the normal force is the downward force (provided by the wings or spoilers). Therefore the more downward force the higher the friction hence the more the tire can exert lateral force (cornering force). For example a F1 car at high speed can exert approximately 4Gs of lateral force when cornering, or 5Gs of force when breaking (at slower speeds a F1 car can't brake as hard).
Dragsters don't go around corners (not while racing, anyway), but they still benefit from the extra weight on the drive wheels produced by the air hitting the top of the spoiler.
It's the same effect though - the F1 car cornering needs to maintain sufficient friction to prevent the tyres slipping laterally, whereas the F1 car braking or the dragster accelerating needs to maintain sufficient friction to prevent the tyres slipping longitudinally.
The air hitting the top of the spoiler isn't generating anywhere near the suction created on the bottom of the spoiler with air underneath having to speed up (and hence have much lower pressure compared to the top).
Aerospace engineer here: Producing lift in either the up (airplane) or down (spoiler) direction generates induced drag. The amount depends on your design, in that a large real or effective AR can reduce it, but it's going to be there.
I think what happens in automotive designs, which are not always penned with the same attention to aerodynamics as aerospace designs, is that they often have unintentional lift at the rear. Adding a small spoiler, then, doesn't add actual downforce, it just reduces lift -- and therefore reduces drag into the bargain.
Basically, big-O is a claim that your process is at least -this- fast. Small-o is a claim that your process can't be faster than -this-. He means the latter.
> Still not convinced? Think I'm misunderstanding Big-O?
That page says o(f) == O(f) and not Theta(f). When you say "small-o is a claim that your process can't be faster than -this-", that seems to match the definition of Omega(f). Did you mean that the author should have used big-Omega?
As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
>As a side-note, I've always thought that {big-O,Theta,Omega,small-o} notation was very confusing. We should just have a notation for "the asymptotic equivalence class of a function", let's say A(f). Then to say f \in O(g), we say A(f) <= A(g). To say f \in Theta(g), we say A(f) = A(g). f \in o(g) becomes A(f) < A(g). And so forth. Instead of lots of new notation, we add a single function A and re-use notation for orderings which everyone already knows. (Of course, I'm omitting the definition of the ordering on these equivalence classes, so maybe there is some difficulty in defining that...)
Your A is pretty much equivalent to \Theta. Saying f \in \Theta(g) is equivalent to saying \Theta(f) = \Theta(g).
Edit: as an aside O(f) = O(g) is also equivalent to f \in \Theta(g), and O(f) \subset O(g) is equivalent to f \in O(g).
For equality, yes, Theta works! But I care not just about equality but about comparison. In particular, it would be nice if the "natural" ordering on A(f) had the property that
A(f) <= A(g) iff f is O(g)
Theta(g) is a set, and the most natural ordering on sets is subsetting/inclusion. However, Theta(x) is not a subset of Theta(x^2), even though x is O(x^2)! So the natural ordering on sets doesn't do what I want.
It might be possible to define an ordering on Theta-classes that does what I want, though.
Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use
O(f) <= O(g) for f is O(g)
O(f) = O(g) for f is Theta(g)
O(f) >= O(g) for f is Omega(g)
>Edit: I just saw your comment about O. I think O might just work! So instead of remembering big-O, Theta, and Omega, I can just use
> O(f) <= O(g) for f is O(g)
> O(f) = O(g) for f is Theta(g)
> O(f) >= O(g) for f is Omega(g)
>Is that true?
Yeah, I'm pretty sure that will work (haven't checked it very rigorously though). The definition of O(f) <= O(g) would simply be O(f) \subset O(g), which immediately satisfies almost all criteria (only tricky bit is proving that either O(f) is a subset of O(g) or the other way around).
For little o I think you should be able to use O(f) < O(g), using the ordering defined above.
I'm afraid the author is correct in using big-O here instead of Omega or little-o.
For comparison, suppose that someone claims that for all x, sin(x) ≤ 1/2. That would just be wrong. If someone claims that sin(x) ≤ 2, then that is true, but not as informative as saying that sin(x) ≤ 1. There's something special about 1 here. If you want to highlight that, you can say that 1 is the least upper bound for sin(x). This is a bit of a mouthful, but we cannot achieve the same meaning by just replacing "≤" by "≥" or "=" or "<". Any of these replacements would just make the statement incorrect.
Big-O is something like the asymptotic version of ≤. For example, how many comparisons does heapsort need to sort an array of length n? If someone says O(n), that's just wrong. If someone says O(n^2), then that's correct, but not as informative as saying O(n log n). O(n log n) is special here, since it is the smallest complexity class that contains the number of comparisons. Again, it is a bit of a mouthful, but we cannot say the same thing by just replacing big-O by Omega, Theta, or little-o (the asymptotic versions of ≥, =, and <, respectively). For example, Theta(n log n) and Omega(n log n) are incorrect, since heapsort only requires a linear number of comparisons if the array already happens to be sorted.
The author argues that random memory access time is O(sqrt(n)), meaning that for large n, it might take up to constant * sqrt(n) time, but might also be faster if the memory to be accessed happens to be very close. Using Omega(sqrt(n)) instead would mean that random memory access can take an arbitrarily long time, but at least constant * sqrt(n). This is not what the author is trying to say.
Yea, I thought about that, but he doesn't mean theta, either. What he's giving is a physical impossibility proof -- you can't do memory access better than sqrt(N). When he gives a physical example of a machine of arbitrary size that accesses memory in sqrt(N) time, then we can talk about theta.
The speed of light limitation on distance to DRAM memory is real, but so far seems to affect mostly supercomputers. Are there any large server boards where speed of light lag is the limit on memory capacity?
I wonder if this is what one interviewer was trying to get at when he asked me over and over again if a binary search was worst case O(log N). I just kept saying that if you took more than log N steps to perform a binary search then you by definition did not perform a binary search. He was off his rocker so I kind of doubt he was looking for the difference between little-o, theta, and big-O. It's good stuff to remember and might impress a more sane interviewer some day though.
Big-O is valid notation for _many aspects_ of an algorithm. The author applied it to a very practical one and explained what exactly he describes very well.
The best/worst/average issue is orthogonal to the definition of what big-O means. The time it take an algorithm has best/worst/average cases, and each of these is a function and thus is a member of big-O classes.
The definition of big-O has a completely standardized and unambiguous definition, and the author of the article somehow has a four-part blog post on big-O without knowing it.
I'm not entirely sure what you are referring to. You might be referring to the fact that the author's definition of big-O doesn't say anything about constant factors or asymptotics. This makes the definition incorrect, or at least sloppy. But judging by usage, it seems that he actually knows and is using the standard definition. The error is just in that one sentence, and it doesn't affect the rest of the argument.
You might also be objecting to the fact that he makes a distinction between time and instruction count, and is using big-O notation for both. I don't think there's anything nonstandard about making this distinction when it needs to be made. Take, for example, Karmarkar's algorithm:
The statement "f is O(g)" means there exists some input, call it t, such that for every x >= t, it only takes some constant multiplier M (i.e., constant in x) to always have g absolutely no smaller than f. In notation:
|f(x)| <= M * |g(x)|, where x is at least t.
This bit about "x is at least t" is very important and notifies us that this is "asymptotic behavior".
It does not make a difference how wacky or weird f is compared to g below t. It can contain all these crazy memory hierarchy artifacts, it could contain a short burst of exponential slowdown, it could contain anything.
Furthermore, according to the above definition, big-O has nothing to do with any tangible quantity whatsoever. It's a method for comparing functions. The functions may represent whatever is of tangible or intangible interest: memory, time, money, instructions, ...
Big-O analysis usually posits that the details below t aren't the details that matter. (Of course, there are situations where they do, but in such you would not use big-O.) If you want to have some analysis that is global, you don't need asymptotic analysis (though it might help as a start). You can just talk about functions that are strictly greater than or less than your function of interest everywhere. But these analyses are difficult because a much higher level of understanding of your function of interest is required.