David Patterson Says It’s Time for New Computer Architectures and Languages
spectrum.ieee.org
spectrum.ieee.org
https://software.intel.com/en-us/articles/coding-for-perform...
But I'm not aware of languages where e.g. declaring alignments is part of the base language. Awareness of L1, L2, L3 cache characteristics, plus NUMA nodes, is increasingly important to writing high performance code. Every language I've ever used exposes nothing of that hierarchy; it's all just "memory".
People who write performance-critical code are already aware of these issues and can measure/hint/optimize to work with the memory hierarchy in existing languages. But I feel like this could be better if we had languages that modeled these issues up front instead of only exposing the abstracted view. Maybe such languages already exist and I just haven't encountered them yet.
Abstract:
"We present Sequoia, a programming language designed to facilitate the development of memory hierarchy aware parallel programs that remain portable across modern machines featuring different memory hierarchy configurations. Sequoia abstractly exposes hierarchical memory in the programming model and provides language mechanisms to describe communication vertically through the machine and to localize computation to particular memory locations within it. We have implemented a complete programming system, including a compiler and runtime systems for Cell processor-based blade systems and distributed memory clusters, and demonstrate efficient performance running Sequoia programs on both of these platforms."
[1] DOI: 10.1109/SC.2006.55 [2] http://graphics.stanford.edu/papers/sequoia/sequoia_sc06.pdf
Sequoia has been largely superseded by its spiritual successor Legion [1], another programming system by Alex Aiken. Legion doesn't focus so much on low-level memory hierarchies, but it does a very, very good job of scaling to very large machines, and taking advantage of heterogeneous processors such as GPUs. It is also incomparably better at working with dynamic programs, whereas Sequoia needed to know basically everything about the program up front (including what machine it will run on).
If you're looking for a modern version of Sequoia that actually runs on modern hardware, I would strongly recommend looking at Legion. (Or the language component of Legion, Regent [2].)
How much of this could get handled by PGO (profile guided optimization) to observe locality and access patterns?
Do you think AI has a place in directing scheduling given enough semantic information so that "bad hypothesis" can get pruned?
Does it rely on a static description of machine (latencies and bandwidth) or does it evolve over time? Can it handle things that are dynamic but are thought of as static like memory bandwidth in a cloud environment?
How does Legion compare to cache oblivious techniques?
Are there changes at the processor level that could fuse operations given the existence of data in the cache, much like hyperthreading can do a context switch on a cache miss.
Do we need to modify what constitutes a Basic Block? Is modern hardware too low level?
Have you read the "Collapsing Towers of Interpreters" paper and do you think it applies to your work?
> How does Legion differ from languages like Halide which separate scheduling from the algorithm?
Yes, that's one of the similarities. Legion, Sequoia, and Halide all share a separation between the specification of the algorithm from the mapping to any particular architecture.
The biggest difference between Legion and Halide, aside from the fact that Halide is much more domain-specific to image processing, is that Legion (being a dynamic runtime system) focuses more on higher-level orchestration of tasks executing in a distributed system.
> How much of this could get handled by PGO (profile guided optimization) to observe locality and access patterns?
Yes, this is called the Inspector/Executor technique. While it's an old technique, the most recent general-purpose implementation that I know of is this paper: [Code Generation for Parallel Execution of a Class of Irregular Loops on Distributed Memory Systems](http://web.cse.ohio-state.edu/~rountev.1/presto/pubs/sc12.pd...).
The main place where it struggles is memory capacity. It turns out that the profiles, when you're running on large distributed systems, can become very, very large. Keep in mind that modestly sized simulations these days run on hundreds to thousands of machines, and the largest run on tens of thousands of machines. So it's not hard to see why this can be problematic.
> Do you think AI has a place in directing scheduling given enough semantic information so that "bad hypothesis" can get pruned?
Yes. One nice property of Legion's approach to mapping is that no matter what mapping is chosen, the system will guarantee that the computation is still executed correctly. So the worst you can do is make yourself slower.
I think mapping, especially in the distributed setting, is one of the big unsolved problems. For domain-specific settings we have some preliminary answers. E.g. see this paper for how it applies MCMC search to find optimal mapping strategies for DNN execution: [Beyond Data and Model Parallelism for Deep Neural Networks](https://arxiv.org/pdf/1807.05358.pdf)
> Does it rely on a static description of machine (latencies and bandwidth) or does it evolve over time? Can it handle things that are dynamic but are thought of as static like memory bandwidth in a cloud environment?
Legion's model of the machine happens to be static at the moment, because that's the most expedient to implement, but explicitly designed with dynamic behavior in mind. One of the biggest cases is where you lose a machine completely (e.g. because it dies, or your spot reservation gets revoked). I'm not sure if more fine-grained behavior can be exploited in a useful way, e.g. temperature fluctuations in a CPU might very well influence performance, but unless you can predict them I don't see what you can necessarily do about that. For many of these problems, being more asynchronous helps, because at least you can turn latency-limited problems into throughput-limited ones.
> How does Legion compare to cache oblivious techniques?
I'd say that cache oblivious techniques are particular algorithms (or perhaps mapping strategies) that you could implement in Legion, but which Legion is agnostic to. Legion provides mechanism but tries to avoid hard-coding any particular policy.
> Are there changes at the processor level that could fuse operations given the existence of data in the cache, much like hyperthreading can do a context switch on a cache miss.
We don't do this on quite such a low level, but we can do it at higher levels. Mappers can select the ordering of tasks on a processor, as well as the placement and layout of data, which is in theory sufficient to play with this. In the past Legion's overheads were too high to really think about this, but we've made some significant improvements in overhead recently which could allow us to start to think about things at this granularity.
> Do we need to modify what constitutes a Basic Block? Is modern hardware too low level?
I'm not one of them, but I know there are people thinking about this. Can't recall any references at the moment.
In general, I think systems like Legion make us much less dependent on caches. If the system manages data movement in and out of explicitly managed memories, that gives us a lot more freedom to play with the architectures. And increasingly I think we'll need this flexibility if we're going to keep driving performance improvements. As one of my friends once said, "x86 is a platform for making shitty code run fast", but perhaps we don't have that luxury any more.
> Have you read the "Collapsing Towers of Interpreters" paper and do you think it applies to your work?
Haven't read it yet, but it sounds like it shares some ideas with [Terra](http://terralang.org/), which we do use heavily. In fact, the Regent language is built entirely in Terra. In general, these sorts of techniques make it much faster to build new languages, while it's not really in my direct line of research I am very grateful people are working on these things.
You mentioned Terra which is an inspiration of mine, I really enjoy mixing high level and low level code and being able to do so in the same program which is one of the major affordances of LuaJIT.
Hugo M. Gualandi and Roberto Ierusalimschy have released the core Lua teams' version of Terra, in Pallene [1] [2] which has the austere aesthetic of Lua applied to ideas of Terra. Pallene looks to be the next incarnation of Titan [3].
[1] http://www.inf.puc-rio.br/~roberto/docs/pallene-sblp.pdf
Sequoia was basically an answer to the question, "what could a compiler do for you if it knew everything about your program?" And I do mean everything: in addition to your source code Sequoia had to be given, at compile time, the sizes of every input array in addition to the exact layout of the machine it was to execute on. While these restrictions were lifted to some degree later on, Sequoia basically had to be able to statically compute every task that it would execute along with the exact sizes of all inputs and outputs. And with this information it was able to do some pretty [fantastic optimizations](http://theory.stanford.edu/~aiken/publications/papers/ppopp0...). I believe, though I can't find the reference at the moment, that the compiler was able to generate (from completely hardware agnostic source code) implementations of BLAS routines competitive with Intel MKL. This was a pretty mind-blowing achievement and to this day I'm not aware of any work that has really been able to equal it.
Requiring programs to be fully static also had a dramatic cost, one which it turned out not to be so easy to lift. In what I believe was the [final paper to be published on Sequoia](http://theory.stanford.edu/~aiken/publications/papers/ppopp1...), Mike Bauer and others showed how to extend Sequoia to support limited forms of dynamic behavior. But the solution wasn't all that satisfying and the work to get there was fairly excruciating. Instead of continuing to work with the language, Mike ended up switching gears to start a new project entirely, Legion.
As an aside, one of the other lessons learned from the Sequoia project is that research projects tend to be tied to the Ph.D. students who work on them. In the Sequoia project, there was a gap in continuity between the first and second generations of students to work on the project. This meant that second-generation students like Mike basically ended up picking up a big legacy code base on their own. This turned out to be a huge drain on productivity and was among the reasons that Sequoia was eventually abandoned.
The biggest decision made about Legion up front was that it had to be dynamic. This was a huge risk because the analysis performed by Sequoia simply could not have been performed at runtime with reasonable cost. Sequoia relied on knowing every single task that would ever execute and the exact bounds of every array input and output. This meant that Sequoia could do perfect alias analysis on these input and output arrays. Because Legion would be a dynamic system, any analysis would have to be performed during the execution of the program. There was no way we were going to do this in Legion without fundamentally changing the abstractions of the programming model, and frankly it wasn't obvious up front if this would even be possible to make tractable.
One of the central insights of Legion was to [explicitly reify the notion of data partitioning](http://legion.stanford.edu/pdfs/oopsla2013.pdf) in the programming model. Sequoia didn't need this because it simply knew the inputs and outputs to every task. Legion couldn't afford to pay the $O(N \operatorname{log} N)$ cost to perform this analysis at runtime. By lifting partitioning into a first-class primitive, we were able to radically reduce the runtime cost of this analysis by leveraging what the user already know about their data partitioning. Originally this required users to declare certain properties of their partitions, such as disjointness, in order to make things efficient. Eventually we discovered a [partitioning sublanguage](http://legion.stanford.edu/pdfs/dpl2016.pdf) which allowed us to statically discover most of these important properties, and to provide many static guarantees even in the presence of data-dependent behavior.
The other big insight of Legion was what we call index tasks. Index tasks are basically collections of tasks that can be described in $O(1)$ space. This turns out to be essential if you want to scale your system to very large distributed machines. Any representation which is $O(N)$ inevitably becomes a scalability bottleneck, either because of memory-capacity constraints or because of runtime complexity. By making the index task representation $O(1)$ we were able to design an [optimization to keep the runtime analysis complexity $O(1)$ as well](http://legion.stanford.edu/pdfs/cr2017.pdf).
One consequence of being a dynamic runtime system is that Legion itself isn't able to optimize the low-level code executed by the system. It seems to be a general principle that the closer you are to the hardware, the more static you need to be. Conceptually, Legion solves this problem by splitting it into two parts: the kernels, or low-level code that has to execute as efficiently as possible on the processor, and the orchestration of the parallelism that exists between those kernels. Legion focuses nearly entirely on the upper layer, leaving the lower layer to be handled by programmers. We've recovered some of this capability via the [Regent programming language](http://regent-lang.org/) which sits on top of Legion, but we haven't taken this nearly as far as Sequoia did.
Despite being a dynamic runtime system, we still put a lot of effort into making sure that it had a principled foundation. Legion is one of the few runtime systems I'm aware of that has its own [type system and operational semantics](http://legion.stanford.edu/pdfs/oopsla2013.pdf). This also made it relatively easy to develop Regent.
With Regent in some ways we've now come full circle, since we're back to having a programming language again. However, one key difference between Regent and Sequoia is what happens when the compilers run into behavior they can't analyze. In Sequoia, it's of the utmost importance that the compiler understand your program, because if the compiler can't prove that parallelism is safe, then it will serialize that part of the program. In contrast, if Regent can't determine that parallelism is safe, it will simply fall back to the runtime system. This means that in general Regent suffers from fewer performance cliffs, or places where performance can suddenly (and sometimes inexplicably) degrade.
There were some lessons we failed to learn from Sequoia. Sequoia made big use of [graph-based IRs](http://theory.stanford.edu/~aiken/publications/papers/ppopp0...) for its compiler. This was a design I copied when developing the [RDIR format](https://github.com/StanfordLegion/rdir) for Regent, a decision I now consider to be a mistake. Graph-based IRs are superficially appealing because they seem to represent the fundamental invariants that you want to reason about. That is, if two tasks are mutually unreachable in the IR, then they are provably safe to execute in parallel. However, working with the graph-based IR as a representation of the program turns out to be a huge pain. RDIR has been by far the biggest source of bugs in Regent and continues to be largest maintenance burden. The other big motivation for a graph-based IR, that it makes certain aliasing properties of the program more explicit than a traditional CFG, is something that I now think could be done adequately well in more traditional formats.
One final note about hardware support: Sequoia made a big bet on the [Roadrunner supercomputer](https://en.wikipedia.org/wiki/IBM_Roadrunner). Roadrunner was an excellent match for Sequoia's programming model, because it used scratchpads (instead of caches) for the compute-heavy processing units. This meant that data (and even instructions!) had to be explicit copied in and out of the memories of the individual processors, something which Sequoia excelled at. Unfortunately, Roadrunner ended up not being so representative of the machines that would follow, and the effort required to retool all the infrastructure ended up being a big drain on the project. Though it would not surprise anyone if these ideas ended up resurfacing in the future, a project like this simply can't afford not to work on contemporary hardware.
In contrast, Legion made its bet on GPUs and heterogeneous architectures more generally. So far this appears to be turning out well and has positioned us to work well on architectures such as [Summit](https://en.wikipedia.org/wiki/Summit_(supercomputer)). However, investment in technologies such as LLVM mean that we're also in a better position to adapt if future technologies end up going in a different direction.
and since C++17 has std::hardware_destructive_interference_size and std::hardware_constructive_interference_size https://en.cppreference.com/w/cpp/thread/hardware_destructiv...
which you can use together to either make sure that 2 variables are not in the same cache line (if you are making a lock-free list for example) or to make sure at compile-time that 2 variables are close enough to share a cache-line.
http://scala-miniboxing.org/ldl/
Basically you can write an algorithm that is independent of the exact data layout, and then the compiler has some flexibility to work with.
I haven't worked with it all, just read the paper awhile ago. But I'm pretty sure they did something with SoA - AoS transformation (structure of arrays/array of structures). At the very least, the compiler can make the data smaller, which fits better in cache. Not sure if it can do anything more advanced than that (i.e. scaling to multiple levels of memory hierarchy rather than compacting data).
My memory of Sequoia is that it's very very far semantically from "Python" (mentioned in the original article). Their example was matrix multiplication, and the language had much more of a functional flavor (perhaps unsurprisingly). I'll have to go back and check it out again.
You can also think of MapReduce as a programming model that is locality-aware, and there have been several papers about multicore (not distributed) MapReduce.
You partition your data into smaller sections, then a user-defined "mapper" runs on each segment. The shuffle is an efficient distributed sort which you don't have to write -- it can be specialized to different problem sizes. And then the user-defined reducer also operates on a (different) small partition of data.
I think the real problem is that the ISA doesn't really expose the memory hierarchy to the programming language, not necessarily that the programming language doesn't expose it to the programmer. GPGPU might change that but I'm not entirely familiar with it.
I thought it was something fairly specific to game programming, but I guess it shouldn't be surprising that other performance sensitive domains might also find it useful.
Some embedded systems had scratchpads and it is possible to 'wire down cache' on some architectures to similar effect. But it would be tricky in general at the language level.
I have a project half on the boil that's aiming to produce a language aimed at these kind of usages. I'm figuring that the supposed insult hurled at C ("structured assembly") isn't really an insult at all but that someone should actually do that. At the moment C, with its giant raft of Undefined Behavior, isn't really that language any more.
https://scholar.google.com/scholar?cites=1705642111681573037...
I see Halide and several interesting projects. Let me know if you find anything interesting :)
It does seem to confirm that locality aware programming models are probably going to look like "big data" programming models (i.e. MapReduce and family).
https://github.com/rust-lang/rfcs/blob/master/text/1358-repr...
Original post:
As does C++ as of 11. [0] For heap allocations, one used the POSIX (not stdlib) posix_memalign until C++17/C11, when std::aligned_alloc became standard. [1] The other option was manually aligning heap memory; it’s so much more convenient to use a transparent aligned allocator.
[0] https://en.cppreference.com/w/cpp/language/alignas
[1] https://en.cppreference.com/w/cpp/memory/c/aligned_alloc
I also dislike the tendency to only expose the abstract view, although I think that trend is due to the difficulties involved in designing a language and compiler whose job is to output code for multiple architectures. Well, at least I hope that's why, because I don't know why you'd choose to offer less control in your language otherwise.
I have notions that there can be something 'between' assembly and, for instance, C, but that's a daydream of mine without any details worked out yet.
But maybe thats fine if the language can express architectural-specific decisions (like memory layout) and abstract it away in a more sane fashion than ifdefsc and the rest of the codebase can maintain the pretense of portability.
the8472, RcouF1uZ4gsC, stochastic_monk: Thanks for highlighting the language-level alignment support in Rust and newer revisions of C and C++.
glangdale, regarding "I have a project half on the boil that's aiming to produce a language aimed at these kind of usages. I'm figuring that the supposed insult hurled at C ("structured assembly") isn't really an insult at all but that someone should actually do that." -- That's great! I would like to see that language.
https://en.cppreference.com/w/cpp/language/bit_field
If you don't need the full precision or range of a 64-bit integer you can pack multiple of them together to get multiple integers transferred in a single cache line read. Compressing in this manner also means you are more likely to get a cache hit.
It is part of the base language in zig: https://ziglang.org/documentation/master/#Alignment
The problem is that general-purpose architectures don't expose the cache hierarchy very well.
GPUs, though. Those have turned out to be very successful, they can be parallelized as much as you're willing to pay for, and they're good for some non-graphics tasks.
Much of machine learning is a simple repetitive computation running at low precision. Special purpose hardware can do that very well.
So what's the next useful thing in that area?
For some guess on the next big thing, I would imagine that stuff that avoid the need of memory coherence have nice odds.
The main lesson I would take away from Cell is that you want to design an architecture that allows gradual performance refinement. With the Cell, it was more of a step function: good performance came from using the SPEs well, but using the SPEs well was hard. There wasn't much of an in-between.
I still don't think the Cell had much future, but we will never be sure. (Also, the Cell had complete memory coherence.)
In a single system there is precedent in virtual memory systems using software-managed page mappings rather than static page table data structures. In HPC there is of course the precedent of distributed parallel systems with message-passing rather than shared memory abstractions. And the separation of GPU memory from system memory is certainly common today. Similar things are happening in software-defined storage (i.e. RAM/SSD/disk/tape tiering).
Computation libraries and frameworks help straddle the gap between application programmer needs and current language/runtime/architecture semantics. I think one problem of current markets is that people tend to want to evaluate hardware independently of software, or in terms of yesterday's software.
There is also a strange history of wanting to discard the software/firmware offered by the hardware vendor (for being insecure/inept/whatever), but blindly accepting the complex hardware design that enables our naive/platform-independent software to run well. The whole Spectre debacle shows how that may have been wishful thinking that we can divorce the software and hardware designs...
I take the same exact C code, compile it with Visual Studio, and then run the same ASCII files locally on my 7th-gen 4c/8t i7 desktop and am not seeing any improvement. That's about the best I can do as far as benchmarking goes.
[1] https://secure64.com/dns-products/secure64-platforms/secure-...
It did also have a fair bit of security acceleration built-in. As I recall, one of the principals behind Secure64 was one of the HP leads associated with the original IA64 announcement. Secure64 pushed Itanium for security applications when it was becoming clear that it was never going to be a mainstream 64-bit architecture.
- The simulation suite that I used most heavily was developed in-house at the same lab that bought the hardware. It was profiled and tuned specifically for our hardware. The development team was a real software development team with experience writing parallel simulation code since the early 1990s. It wasn't just a bunch of PhD students trying to shove new features into the software to finish their theses.
- There was also close cooperation between the lab, the system vendor (HP), and Intel.
- Other software (like all the packages shipped with RHEL for Itanium) didn't seem particularly fast.
- God help you if you needed to run software that was available only as binary for x86. The x86 emulation was not fast at all.
It was great for numerical code that had been specifically tuned for it. It was pretty good for numerical code that had been tuned for other contemporary machines. Otherwise I didn't see particularly good performance from it. I don't know if it really was a design that was only good for HPC or if (e.g.) it also would have been good for Java/databases, given sufficient software investments.
Maybe it would have been competitive against AMD64, even considering the difficulty of architecture-switching, if it had not been so expensive. But I'm not sure Intel had wiggle room to price Itanium to pressure AMD64 even if they had wanted to; Itaniums were quite big, complicated chips.
Well, why not.
> Q: I feel like deja vu - at Hot Chips, Intel introduced VLIW-concept Itanium that pushed complexity onto the compiler. I see traces of that here. What are you doing to avoid the Itanium traps? How will you avoid IP from Intel?
> A: Itanium was in-order VLIW, hope people will build compiler to get perf. We came from opposite direction - we use dynamic scheduling. We are not VLIW, every node defines sub-graphs and dependent instructions. We designed the compiler first. We build hardware around the compiler, Intel approach the opposite.
https://www.anandtech.com/show/13255/hot-chips-2018-tachyum-...
It's interesting to compare the Itanium's approach to a VLIW contemporary from TI: the C6x VLIW DSP ISA. The C6x ISA took on very little controller complexity. Instead, it exposed a very clear operational and optimization model for the VLIW instruction blocks. An optimizing compiler did a decent first-step job at generating code. That was complemented by clear documentation of the optimization workflow, from compiler-stage iteration down to good guidance on the nuts and bolts of hand-optimizing. By comparison, IA64 was just ... a big head-scratching moment all around. I never got to work with C6x code professionally, but dang it looked like a blast to code and optimize for.
GPUs, though. Those have turned out to be very successful, they can be parallelized as much as you're willing to pay for, and they're good for some non-graphics tasks.
Not all CPU architectures are equally successful. Likewise, not all highly parallel architectures will be equally successful. If progress in hardware is going to be characterized by more parallelization, things like Erlang Actors are going to become more important.
Things can already target X64/Arm but with a minimal kernel and a foundation without C at the base.
---
Even with a complete new CPU/Arch (that weirdly, I dream about that!) you can solve compatibility with VM/Containers. And provide a better user-land.
Java is in the process of doing it as part of Arrays 2.0 roadmap.
If it wasn't for that AMD stunt we would all be using Itaniums by now.
Competition from other architectures was always there.
Hence Intel's mistake.
I think the problem with those is that they failed to build anything compelling -- not that people didn't come.
To really shake things up at a fundamental level will probably require running into an alien species that does basic things differently than us.
Even creative people with lots and lots of spare time and resources at their disposal will still be too "colored" by existing human knowledge and established practices to really try anything new (and without falling into the trap of needlessly reinventing the wheel.)
Compilers make optimizations using detailed instruction timing information, but as far as I know, these details do not bubble up to the surface in any programming language.
It may be wise to keep these details under the surface at the compiler level, but for 8-bit architectures, it would be awesome to have a language where you have explicit control of time.
Never thought about that. That would be so cool.
That being said I have personally yet to see non-toy static analysis tools for performance (although I suspect they exist at least in some limited fashion or operating in some constrained domains). This is probably due to the nature of certain pathological inputs and code paths as you point out.
There may nonetheless be hope if you guide the way users can write programs as a sibling comment points out.
Any statically typed language necessarily has to prevent some well-formed programs from being represented. This language would just need to reject programs where it can't prove the attributes that it is suppose to prove in addition to programs that are actually malformed.
It is really ergonomics that prevents a language like this from taking off, not any theoretical concerns. Languages that let you prove a lot of complex properties at compile-time take too much work to use, but they are not impossible to create.
Idris, for instance, disallows recursion unless it can prove an argument "smaller" in the recursive call. For instance:
fib : Nat -> Nat
fib Z = Z
fib (S Z) = (S Z)
fib (S (S n)) = fib (S n) + fib n
As such, a proof system which incorporates behavioural specification is highly desirable.
If a language let you say, "this chunk of code here should run in 7 cycles", what happens when a new optimization finds a way to reduce that, or a new architecture comes up where that operation gets slower but lots of others get faster?
I'm not arguing against your desire, just explaining that it's not unreasonable that we're where we are now. We've gotten so used to language portability, that it's good to remember how painful it can be to lose that. It's no fun having to rewrite all your code every time a new chip comes out.
You write an algorithm that seems reasonable. And you encode timing constraints into the thing. Now you re-target to a different machine, and the compiler re-checks those constraints. A much cheaper way of dealing with weird timing bugs than doing a post-mortem of why the fuel valves didn't quite close on the day of the rocket test.
But this only works if the CPU is knowable to the compiler. Which is why it is only even remotely feasible in the embedded world (where it is also the most useful).
That's already an extremely niche set of processors. Further, the number of bits of code you're likely to care about this kind of extremely precise timing for, you'll either examine the emitted assembly, or just hand-write the ASM yourself.
It seems like a huge amount of effort for an extremely niche scenario. Remember, the ISA is still just an abstraction, after all.
In practice I think hard real-time systems use extremely conservative estimates of cpu performance.
I mean it's nice for compilers to count instructions, but that is far more likely to work on some "primitive" embedded CPU than it is to work on the modern spectre-pipelined goliath CPUs that we use in personal computers and datacentres.
For example, see links at https://www.reddit.com/r/haskell/comments/2zqtfk/why_isnt_an...
Personally, I was briefly involved in the T-CREST[0] project where a complete ISA, network on a chip and compiler where devolved in tandem to support deterministic timing and well understood worst case execution times (WCET).
As an example, the ISA explicitly defines multiple caches with different write-rules. So for example the stack cache is write-back to lower WCET.
The whole project is available as a VM image[1] where the HDL can be compiled to an emulator and/or synthesized to hardware.
[0]: http://www.t-crest.org/page/overview [1]: http://patmos.compute.dtu.dk
[0] https://twitter.com/pkamenarsky/status/961666713900249088?s=...
Dedalus is an evolution of datalog, incorporating the notion of time in the type system. You're better off working with an abstract version of time, for portability reasons - the compiler can look at the timing specs to optimize resource usage, otherwise you're into VHDL territory and your only recourse is simulation of your system to reason about it, due to complexity .
Fine grained energy usage would be specific to say the SOC you're using, eg. for the CC1310 there are specific modes for low power. The compiler could potentially take care of this, but you would probably require an abstract state machine for it to optimize, eg. identify periods to go in to low power mode.
Hard realtime nearly precludes many languages due to their need for GC - there are a few realtime GCs around, but really it's better to use a language that has managed memory without GC. So after all that, you're down to a handful of suitable languages for realtime eg. Rust or Composita.
Lastly, guaranteeing program correctness is something you need to do in a high level language, to be able to capture the semantics you're tying to prove. ie. you need a language that can express higher order logic. Whether this proof step is intrinsic to the language is up to you, but you then need to map the higher-level model to your low level language. Several projects do this eg. CakeML, but the full self-verified OS doesn't exist as yet.
Interestingly there is a linguistic solution for all of this which I'm working on, just not got anything concrete to share yet - maybe in 6 months :)
As an aside, most of the stuff I've on my account is higher level eg. https://github.com/alexisread/noreml deals more with a new method of visually programming cross-plaform UIs ie. using nodered dashboards and flow-based programming in a drag and drop fashion.
Main influences at the moment are Maru, Composita, Ferret and Maude:
http://piumarta.com/software/maru/ http://concurrency.ch/Research/Composita https://github.com/nakkaya/ferret http://maude.cs.uiuc.edu/overview.html
We have SQL of course, but SQL is not a general purpose language and is (intentionally) often not Turing-complete.
I'm imagining something like Go, Ruby, JavaScript, or Rust with native tables, queries, and other SQL-ish relational data structures.
The long term goal would be to kill the age-old impedance mismatch problem and eliminate CRUD code. Toward this long term end the language runtime or standard library could actually contain a full database engine with replication/clustering support.
Besides its data structures, R is surprisingly similar to JavaScript -- it's has Scheme-like semantics but C-like syntax.
For certain problems, it's a pleasure to program in. You don't have to go through "objects" to get to your tables; you just have tables!
The examples here might give you a flavor:
https://cran.r-project.org/web/packages/dplyr/vignettes/dply...
R itself has a lot of flaws, but the tidyverse [1] is collection of packages that provide a more consistent interface.
FWIW I agree that more mainstream languages should have tables natively. It is an odd omission. Somehow they got coupled to storage, but they're also useful for computation.
Most "normal things" have designs that are deeply inefficient and compromised by bad under-powered data models.
And I agree that what you want should exist -- R is proof that it's perfectly possible and natural!
Although, people are using (abusing) R to write web apps:
They mostly display data, but they have non-trivial interaction done in the style of JS.
The ideas within SQL are powerful but the syntax would need a dust off and would need to be integrated into a modern language.
In fact Moore’s law must have been the reason why Python is what it is today: “Who cares if it’s slow, tomorrow’s computers will be faster!”
Given how machine learning is going to kick in in lots of fields quite soon there will be a lot of real world applications that are not ambivalent about performance (if not else then from energy use point of view).
We're going to get Clippy the Clipper 2.0 who can actually do something usefull, and how long he spends figuring out his suggestions and how good they are are likely to be dependent on the available CPU resources and how fast Clippy can think.
Well, that’s a misrepresentation of history, the Python ethos has always been to drop into C for performance critical sections. That’s why NumPy won, and why Numba is highly competitive with Julia, and you can keep your existing code.
It is "nice" to be able to slap components together like magic legos and/or a Dagwood Sandwich rather than smartly tune and coordinate everything, but doing such is often computationally inefficient. The speed of light will probably put a hard upper limit on this practice that no clever language or architecture can work around to a notable degree.
Software is a gas; it expands to fill its container - Nathan Myhrvold
Bad performance isn't really a software design problem; it's an economics problem (ditto for security). You could speed up the browser by 2x now, or reduce it's memory usage by 2x, and websites would be exactly as slow after a few months.
I'm not trying to be negative here, just stating an unfortunate systems dynamic.
Quantum computing does not magically speed up general purpose computing tasks. We only know a handful of algorithms where quantum computers provide algorithmic complexity reductions and even that that does not mean they necessarily calculate fast in terms of IPC, they just calculate previously intractable problems in reasonable timescales.
TL;DR: you won't pop quantum GPUs/CPUs into your computer and suddenly get 50 times the framerates in DOOM.
If I can represent screen state as quibits, and I have a whole lot of quibits, I can represent a game as a little list of player inputs.
Set up an enormous superposition, and as players hit keys, collapse the next frame. The imaginary hardware could be super quick!
TL;DR: yeah probably, but you never know.
If you really cared about security without regard to any other property, you would probably be using DJB's software to serve your website and such.
But you probably don't, because it doesn't have the features you want and you might not want to spend the time figuring out how to set it up.
Why do you say so?
Faster machines and tools only really matters to people who are trying to do things that are currently never fast enough to put into production.
But the market does not value their software; we use slower and less secure alternatives.
Slack is a great example. There are probably 99 other chat services that perform better than Slack. (Apparently it makes fans spin on laptops, which is kind of shocking for a chat app.)
But the market doesn't necessarily care -- it values the features that Slack provides more.
Part of it is a bad network effect. I care about speed, but I might have to use Slack because the people I want to talk to on Slack don't care about speed.
There is probably an economics term I can cite to explain this better, like some kind of equilibrium (I appreciate any help explaining this).
But the sibling basically got it half-right -- software developers and designers are always making cost-benefit decisions.
The other half of it is that consumers tend to choose features rather than security. The are ALREADY faster and more secure alternatives to every piece of software you use -- you just don't use them because they don't have the features you want!
People vote with their feet, and what we end up with is not the fastest or most secure situation, because there are tradeoffs.
This applies to developers too -- not just end users. I mean why do people choose Python, PHP, or JavaScript? There are faster languages out there. There are languages that could help you write more secure applications.
But those languages have the features and library ecosystem we want, so we use them.
----
I'm one of those people who laments slow and insecure software. But doing my own open source project has kind of brought home the tradeoffs. I've been working for over 2 years on an open source Unix shell. It's written in Python [1], which is not exactly the right tool for the job. But if I wrote it in C or C++ or Rust, it would take 4 or 6 or 10 years.
So unforunately it is too slow, but there's a tradeoff between being slow and being fast but not existing and nobody using it. (Although I have a plan to fix it, basically outlined in that blog post. Not sure how much effort it will take, but I think less than rewriting from scratch.)
It's an economics problem -- if it doesn't have the features people already use, then they'll have to rewrite their software. Rewriting shell scripts costs a lot of money and it doesn't have a lot of advantages. It's more economical for one person/team to emulate bash in a new shell, than for the entire world to rewrite their scripts.
This recent blog post has the same sentiment buried in there:
https://apenwarr.ca/log/20180914
XHTML didn't succeed because it's more economical for a single browser vendor to make a really complicated parsing algorithm than it is for every single person in the world to change how they write HTML.
It's not like we don't KNOW how to design strict data formats, or we don't KNOW how to make secure software. (e.g. ask yourself why more people aren't using DJB's software.) It's matter of economics -- how much effort are the people making decisions willing to put in, and how much the market rewards them for it.
We can certainly improve the situation by valuing secure and fast software, and that has happened in the past. Windows used to be an utter disaster security-wise, but Microsoft realized that it was more than the market would bear, and they changed their whole attitude toward security.
Although if you want to be cynical, you can also say they made the "right" move to ship first and make things secure later :-(
I see this a lot. Is this a real phenomenon? Seems like an inevitability to me. Who would build a freeway they didn't expect people to use?
I do hope a lot that Mill will succeed, it's an incredibly promising architecture.
He compares Python to C. Come on, please. It would have been more relevant to speak about the LLVM project and how that enables architects to build more expressive languages which can still make use of 30 years of optimization wisdom (most of which was built when CPU's were much slower)
What about mentioning languages like Rust which are designed for high concurrency and zero overhead which let developers write software with the safety of python but the performance of C.
What about mentioning that some old languages, like c++, have evolved though new language features AND guidelines into much more effective languages to guide us into the future of concurrent programming (the easiest way to enjoy the speedups of yesteryear)
That family was launched mid-2012!
I think Dr. Patterson makes a great point on there being plenty of headroom in the increase in software efficiency.
Sounds similar to Micron Automata Processor.
i.e. analyzing and modifying the huge legacy of existing code base ?
This is a very difficult area of course (both financially and technologically). But the pay off can be very large. Imagine a vmware-like transformation at the source code level.
I'm not sure what you mean by this, but I'm interested. Could you explain?
they site some numbers by Gartner (from '99, when 2K scare was on everyone's mind)
"...
Cost of doing a manual migration:The Gartner Group notes that the cost for manual code conversion can range from $6 - $26 per LOC and is accomplished at a rate of 160 LOC per day (Gartner Group study "Forecasting the Worldwide IT Services Industry: 1999,1").
An assumption is that the migration is going between two relatively similar languages (e.g., not trying to go from COBOL to full object-oriented Java). Using Gartner's numbers, a million lines of code costs $6-$26 million to migrate.
Time to do a manual migration: Again, using Gartner's numbers, a legacy system with a million lines of code requires some 28+ man-years of labor to convert. With a team of 10, this takes 3 elapsed years if done well. With larger systems, one has larger teams. Larger teams require more interactions, slowing them down further.
A 10 million line application simply doesn't have any practical manual migration due to time frames.
"
Never used their services.
But I do think this will continue to be difficult, yet beneficial option, for the migrations from legacy/less secure software.
Every forth core can pass forth to its neighbors, forth is very expressive yet tiny since it's a stack language.
Anyway my 2cents
> The centerpiece of the new architecture is word-based array of tiles made up of VLIW vector processors, each with local memory and interconnect.
> tiles communicate with each other to create data paths that best suit their application.
https://www.eetimes.com/document.asp?doc_id=1333632
So GA144 is going to mainstream finally.
ps: funny reading 'post-moore' in the linked article :)
Fundamentally though it's a transputer-on-a-chip so there is an existing base of research on writing/optimizing that sort of thing.
Lots of small processors with local work ram, cached ram, shared ram.
Each processor has a numerical id, communicates with each processor with one bit different in the id by optical link plus an additional link with to the processor complimenting all bits. They send messages and fill their caches from the pool of shared ram.
Place even parity processors on one board and odd parity processors on another board facing towards the first. Thus all processors have line of sight on their communication partners. Messages go back and forth with processors relaying messages by fixing one bit in the message address. All neighbours with a one bit better address are candidates for relaying. If any are busy, they have options to use another path.
This means the most number of hops a 2^19 core system would have to do is 9. If more than half of the bits are wrong then jump to the compliment.
So the example with half a million processors, each talking to 20 neigbours by optical links. Messages can be sent anywhere with a latency of up to HopTime*9. Filling a cache from anywhere in the shared memory pool would have a latency of twice that. If speed of light is the latency factor a 150ms latency would get you 9 hops across a 5 meter gap. Smaller is of course always going the make it better.
This is the sort of thing that would also probably need a new language. I'm not entirely sure you could come up with an appropriate language without at least a simulation of the architecture.
I have a good idea for a name of that new language: occam ;)
I had envisioned every link comminicating independantly. what would be the advantage of communicating syncronously?
Information-theorically at least, I bet that is another 10-100x speedup opportunity right there (and next multi-billion dollar industry, perhaps)...
Is this a recent photo? Do they have a computer history museum @ UCB or is that datacenter actually running production workloads on that kit?
Instead, future of computing turns toward optimizing for the experience. With 3D printed form factors and smart haptics. European startup Canatu provides a glimpse of what carbon nano tube (CNT) sheets make possible:
> I'm just not sure end users are clamoring for more photo-realism.
People are definitely making fun of characters looking waxy, fire effects looking cheap, shadows being pixelated etc.
Plus this is just the first generation of realtime raytracing. It's not like the entire scenes will be raytraced, just some parts will be raytracing-assisted, e.g. lighting. The next generations will most likely enable a higher percentage of the scenes being based on tracing.
Actually Intel has even wider view of the things and interest to non-(yet?)-mainstream tech, like e.g. async circuit design. They has bought Achronix, Fulcrum, Timeless Design Automation. Fulcrum in 2002 made things like "a fully asynchronous crossbar switch chip that achieves 260-Gbit/second cross-section bandwidth in a standard 180-nanometer CMOS process" - https://www.eetimes.com/document.asp?doc_id=1145012
So we have finally reached some sustainability. Good.
On the other hand, web or mobile first frameworks/platforms, are often high level, and have been a little ornery when digging into the weeds.
Our paradigm has shifted from desktop-first, to web-first, to mobile-first a while ago, but our frameworks are still often anchored from a desktop-first world perspective.
If there's examples that do, or do not highlight this, would love to see and discuss :)
https://github.com/Unity-Technologies/EntityComponentSystemS...
It makes sense from a hardware perspective but it seems software development is not keeping pace. General purpose languages have trouble targeting this kind of hardware.
Is this true? According to https://ourworldindata.org/technological-progress it looks like we are maybe a factor of 2 or 4 off.
Another point is that processors are already now incredibly fast and the performance is caped by the peripherals. This is were the huge potential is hiding for some time.
>"Google has its Tensor Processing Unit (TPU), with one core per chip and software-controlled memory instead of caches"
Is have heard of software-controlled caches before but I am imagining this is not the same thing? Could someone say? Might anyone have any decent resources on software-controlled memory architectures?
A good application of SOC looks not just "intelligent" but wise, prudent, brilliant, and prescient.
There have been claims that necessarily SOC is the most powerful version of learning there can be -- a bit much but ... maybe.
For computing architectures, the computing that SOC can soak up makes the computing needs of current deep learning look like counting on fingers in kindergarten.
The subject is no joke and goes back to E. Dynkin (student of Kolmogorov and Gel'fand), D. Bertsekas (used neural nets for approximations for some of the huge tables of data), R. Rockafellar (e.g., scenario aggregation), and, sure, R. Bellman. Some of the pure math is tricky, e.g., measurable selection.
I did my Ph.D. dissertation in SOC and there actually made the computing reasonable, e.g., wrote and ran the software -- ran in a few minutes, with my progress in algorithms down from an estimate of 64 years. For larger problems, can be back to taking over all of Amazon for 64 years. More algorithmic progress is possible, and, then, some specialized hardware should also help, sure, by factors of 10; right, we want lots of factors of 10.
If want to think ambitious computing, past Moore's law, past anything like current AI, with special purpose hardware, go for SOC.
SOC Applications 101. For your company, do financial planning for the next 50 years, 60 months. So, set up a spreadsheet with one column for each month, one column for the current state of the company and then 60 more columns. Goal is, say, to maximize the expected value of something, maybe the value of the company, in the last column, right, with control over the probability of going broke, if a bank always be able to meet reserve requirements and pass stress tests; if a property-casuality insurance company, stay in business after hurricane Florence, etc.
For each variable of interest, have a row.
In the cells, put in the usual expressions in terms of the values of cells in earlier columns.
Also have some cells with random numbers -- the stochastic part.
Also have some cells empty for the business decisions, the control part.
This is the 101 version; the 201 version has more detail!
Can't get the solution with just the usual spreadsheet recalc because the best solution is optimal and varies through the 60 months as more information is gathered -- and that is the core of the need for more in algorithms and taking over all of Amazon for the computing.
Really, the work comes too close to looking at all possible business state scenarios over the 60 months yet still is astronomically faster than direct or naive ways to do this.
Or, a little like football, don't call the play on 2nd down until see the results of the play on 1st down, BUT the play called on 1st down was optimal considering the options for the later downs and plays.
The optimality achieved is strict, the best possible, not merely heuristic: No means of making the decisions using only information available when the decisions are made can do better (proved in my dissertation).
Intel, AMD, Qualcomm, DARPA, NSF, Microsoft, etc., think SOC!!! You just heard it here -- I might not bother to tell you again.
D&L show a nice result that could be used for some first cut approximations: If are minimizing a quadratic cost, if the algebraic expressions in that spreadsheet I mentioned are all linear, and if the randomness is all just Gaussian, then get "certainty equivalence" -- that is, get to f'get about the Gaussian, random, stochastic part and use just the expectations themselves. Huge speedup.
For more, there is Dynkin and Yushkevich, Controlled Markov Processes -- one of the key assumptions that permits treating the spreadsheet columns one at a time is that the stochastic part obeys a Markov assumption (the past and future are conditionally independent given the present).
There is, from MIT and CMU,
Dimitri P. Bertsekas and Steven E. Shreve, Stochastic Optimal Control: The Discrete Time Case.
And there is
Wendell H. Fleming and Raymond W. Rishel, Deterministic and Stochastic Optimal Control.
There are papers by R. Rockafellar, long at U. Washington.
There is now an ambitious program at Princeton in the department of Operations Research and Financial Engineering.
I tried to get IBM's Watson lab interested; by now they would have been nicely ahead. The guys I was working for wanted me to do software architecture for the OSI/ISO CMIS/P data standards. Garbage direction. A really big mistake for Big Blue, not so big now.
One of the reasons for IBM to have done SOC was that they had some vector hardware instructions, that is, that would do an inner product, that is, for positive integer n, given arrays A and B, each of length n, find the sum, i = 1, 2, ..., n of
A(i)*B(i).
Commonly can get some nice gains by finding non-inferior points -- so will want some fast ways to work with those. The software for my dissertation did that; got a speedup of maybe 100:1; on large problems, commonly could get much more.
There is some compiling that can get some big gains -- some of the big gains I got were from just my doing the compiling by hand, but what I did could be a feature in a compiler -- there's likely still a stream of publications there if anyone is interested in publications (my interests are in business, the money making kind, now my startup).
There is a cute trick if, say, all the spreadsheet column logic is the same -- can "double up on number of stages".
There are lots of speedup techniques known. A big theme will be various approximations.
If there's an opportunity to exploit sufficient statistics, then that could yield big speedups and shouldn't be missed. Having the compiling, sufficient statistics, and non-inferior exploitation all work together could yield big gains -- that should all be compiled. Get some papers out of that! No doubt similarly for other speedups.
There's lots to be done.
As I suggested, I do believe that some progress in execution time could be had from some new machine instructions, new language features to use those instructions, and some compiling help. For the compiling part, the language would have some well defined semantics the compiler could exploit. E.g., for something simple, the semantics could let the compiler exploit the idea of non-inferior sets.
E.g., say have 100,000 points in 2-space. Say, just for intuitive visualization, plot them on a standard X-Y coordinate system. Say that the X coordinate is time and the Y direction is fuel. Part of the work is to minimize the cost of time and fuel. At this point in the computation, we don't know how the costs of time and fuel trade off, but we do know that with time held constant, less fuel saves cost, and with fuel held constant, less time saves cost.
So, in the plot of the 100,000 options, we look at the lower left, that is, the south-west parts of the 100,000 points.
Point (X2,Y2) is inferior to point (X1,Y1) if X1 <= X2 and Y1 <= Y2. That is, point (X2,Y2) is just equal to point (X1,Y1) or is to the upper right, north east of (X1,Y1). If point (X1,Y1) is not inferior to any other of the 100,000 points, then point (X1,Y1) is non-inferior.
So, there in the work, can just discard and ignore all the inferior points and work only with the non-inferior points. May have only 100 non-inferior points. Then, presto, bingo, just saved a factor of 1000 in the work. Okay, have sufficiently restricted programming language semantics that the compiler could figure out all that and take advantage of it. When I wrote my code in Fortran, I had to write and call a subroutine to find the non-inferior points -- bummer, that work should be automated in the compiler, but to do that the compiler will need some help from some semantic guarantees.
The above is for just two dimensions, but in practice might have a dozen or more. So, what's the fast way with algorithms, programming language semantics, and hardware to find the non-inferior points for a dozen dimensions?
Non-inferior points are simple -- lots more is possible.
I would start by throwing away all the interpreted/GC'ed languages because even after decades of massive effort they are frequently lucky if they even manage to keep up with unoptimized C.. But that really isn't the problem, the problem is that they cannot be debugged for performance without directly hacking the GC/interpreter. At least in C when you discover your data structures are being trashed by insufficient cache associativity (for example), you can actually fix the code.
Put another way, up front people need to know that if they write in python/Java/etc to save themselves a bit of engineering effort and its anything more than throwaway low volume code, the effort to optimize or rewrite it will dwarf any savings they might have gotten by choosing python.
Personally I agree about dynamically typed languages not being great for large projects but that's more about maintainability than perf.
The point is that we literally have dozens and dozens of languages active on any given machine with absolutely massive frameworks duplicating functionality. Here is a few hundred meg ruby runtime, with a few hundred meg node.js runtime, with a few hundred meg python2 runtime (and another for python3), with a few hundred meg perl runtime, etc, etc, etc. Its insane because in most cases you can't even statically bind the whole thing into a single .jar like file.
Not only is the cognitive load incredible, but the code quality in most of them is horrendous. Then there is the issue, that most of these language runtimes have for most purposes have zero documentation outside of the actual code.
Then when someone says "what language should I choose" they are presented with a whole bunch of square pegs to pound into their round hole. If your going to work with a square peg, it should probably be one well understood and polished enough to actually have documentation for more than the 100 most common functions being called.
What I'm trying to say is that we don't need yet another over-hyped language, and we should probably try to kill a few more of them off. Object Pascal is a better language than probably 1/2 the ones on common use, but its pretty much dead. Inventing another language that is _worse_ than object pascal is just stupid.
Yeah right, let's just burn down the Web.
The biggest performance hog on my machine isn't Python code.
The problem is that we already have too many languages trying to be generic, and languages like C++, and openMP can be wrangled into nearly any programming paradigm in common use and the results tend to also be significantly faster.
If your talking about performance, the minimum baseline requirement should be running faster than a language in common use, say C++. There are a few languages that might take this (Cuda/OpenCL) but they also tend to be somewhat domain specific. Similarly verilog/VHDL can produce fast results. There have been calls for languages that can express parallelism better and are both expressive, and safe for decades. But what we have actually gotten haven't been better in most objective measures. What we have gotten are a pile of "scripting like" languages with very similar characteristics (tcl, ruby, perl, python, javascript, PHP, lua, go, applescript, etc).