(no commit message)

[libreriscv.git] / openpower / sv / SimpleV_rationale.mdwn

[[!tag whitepapers]]

**Revision History**

* First revision 05may2021

**Table of Contents**

[[!toc]]

# Why in the 2020s would you invent a new Vector ISA

Inventing a new Scalar ISA from scratch is over a decade-long task
including simulators and compilers: OpenRISC 1200 took 12 years to
mature.  A Vector or Packed SIMD ISA to reach stable general-purpose
auto-vectorisation compiler support has never been achieved in the
history of computing, not with the combined resources of ARM, Intel,
AMD, MIPS, Sun Microsystems, SGI, Cray, and many more.  Rather: GPUs
have ultra-specialist compilers that are designed from the ground up
to support Vector/SIMD parallelism, and associated standards managed by
the Khronos Group, with multi-man-century development committment from
multiple billion-dollar-revenue companies, to sustain them.

Therefore it begs the question, why on earth would anyone consider
this task, and what, in Computer Science, actually needs solving?

First hints are that whilst memory bitcells have not increased in speed
since the 90s (around 150 mhz), increasing the datapath widths has allowed
significant apparent speed increases: 3200 mhz DDR4 and even faster DDR5,
and other advanced Memory interfaces such as HBM, Gen-Z, and OpenCAPI,
all make an effort (all simply increasing the parallel deployment of
the underlying 150 mhz bitcells), but these efforts are dwarfed by the
two nearly three orders of magnitude increase in CPU horsepower. Seymour
Cray, from his amazing in-depth knowledge, predicted that the mismatch
would become a serious limitation, over two decades ago.  Some systems
at the time of writing are now approaching a *Gigabyte* of L4 Cache,
by way of compensation, and as we know from experience even that will
be considered inadequate in future.

Efforts to solve this problem by moving the processing closer to or
directly integrated into the memory have traditionally not gone well:
Aspex Microelectronics, Elixent, these are parallel processing companies
that very few have heard of, because their software stack was so
specialist that it required heavy investment by customers to utilise.
D-Matrix and Graphcore are a modern incarnation of the exact same
"specialist parallel processing" mistake, betting heavily on AI with
Matrix and Convolution Engines that can do no other task.  Aspex only
survived by being bought by Ericsson, where its specialised suitability
for massive wide Baseband FFTs saved it from going under.  Any "better
AI mousetrap" that comes along will quickly render both D-Matrix and
Graphcore obsolete.

NVIDIA and other GPUs have taken a different approach again: massive
parallelism with more Turing-complete ISAs in each, and dedicated
slower parallel memory paths (GDDR5) suited to the specific tasks of
3D, Parallel Compute and AI. The complexity of this approach is only dwarfed
by the amount of money poured into the software ecosystem in order
to make it accessible, and even then, GPU Programmers are a specialist
and rare (expensive) breed.
 
Second hints as to the answer emerge from an article
"[SIMD considered harmful](https://www.sigarch.org/simd-instructions-considered-harmful/)"
which illustrates a catastrophic rabbit-hole taken by Industry Giants
ARM, Intel, AMD, since the 90s (over 3 decades) whereby SIMD, an
Order(N^6) opcode proliferation nightmare, with its mantra "make it
easy for hardware engineers, let software sort out the mess" literally
overwhelming programmers.  Worse than that, specialists in charging
clients Optimisation Services are finding that AVX-512, to take an
example, is anything but optimal: overall performance of AVX-512 actually
*decreases* even as power consumption goes up.

Cray-style Vectors solved, over thirty years ago, the opcode proliferation
nightmare.  Only the NEC SX Aurora however truly kept the Cray Vector
flame alive, until RISC-V RVV and now SVP64 and recently MRISC32 joined
it.  ARM's SVE/SVE2 is critically flawed (lacking the Cray `setvl`
instruction that makes a truly ubiquitous Vector ISA) in ways that
will become apparent over time as adoption increases. In the meantime
programmers are, in direct violation of ARM's advice on how to use SVE2,
trying desperately to use it as if it was Packed SIMD NEON.  The advice
not to create SVE2 assembler that is hardcoded to fixed widths is being
disregarded, in favour of writing *multiple identical implementations*
of a function, each with a different hardware width, and compelling
software to choose one at runtime after probing the hardware.

Even RISC-V, for all that we can be grateful to the RISC-V Founders
for reviving Cray Vectors, has severe performance and implementation
limitations that are only really apparent to exceptionally experienced
assembly-level developers with a wide, diverse depth in multiple ISAs:
one of the best and clearest is a
[ycombinator post](https://news.ycombinator.com/item?id=24459041)
by adrian_b.

Adrian logically and concisely points out that the fundamental design
assumptions and simplifications that went into the RISC-V ISA have an
irrevocably damaging effect on its viability for high performance use.
That is not to say that its use in low-performance embedded scenarios is
not ideal: in private custom secretive commercial usage it is perfect.
Trinamic, an early adopter, created their TMC2660 Stepper IC replacing
ARM with RISC-V and saving themselves USD 1 in licensing royalties
per product are a classic case study.  Ubiquitous and common everyday
usage in scenarios currently occupied by ARM, Intel, AMD and IBM? not
so much. Even though RISC-V has Cray-style Vectors, the whole ISA is,
unfortunately, fundamentally flawed as far as power efficient high
performance is concerned.

Slowly, at this point, a realisation should be sinking in that, actually,
there aren't as many really truly viable Vector ISAs out there, as the
ones that are evolving in the general direction of Vectorisation are,
in various completely different ways, flawed.

**Successfully identifying a limitation marks the beginning of an
opportunity**

We are nowhere near done, however, because a Vector ISA is a superset of a
Scalar ISA, and even a Scalar ISA takes over a decade to develop compiler
support, and even longer to get the software ecosystem up and running.

Which ISAs, therefore, have or have had, at one point in time, a decent
Software Ecosystem? Debian supports most of these including s390:

* SPARC, created by Sun Microsystems and all but abandoned by Oracle.
  Gaisler Research maintains the LEON Open Source Cores but with Oracle's
  reputation nobody wants to go near SPARC.
* MIPS, created by SGI and only really commonly used in Network switches.
  Exceptions: Ingenic with embedded CPUs,
  and China ICT with the Loongson supercomputers.
* x86, the most well-known ISA and also one of the most heavily
  litigously-protected.
* ARM, well known in embedded and smartphone scenarios, very slowly
  making its way into data centres.
* OpenRISC, an entirely Open ISA suitable for embedded systems.
* s390, a Mainframe ISA very similar to Power.
* Power ISA, a Supercomputing-class ISA, as demonstrated by
  two out of three of the top500.org supercomputers using
  160,000 IBM POWER9 Cores.
* ARC, a competitor at the time to ARM, best known for use in
  Broadcom VideoCore IV.
* RISC-V, with a software ecosystem heavily in development
  and with rapid adoption 
  in an uncontrolled fashion, is set on an unstoppable
  and inevitable trainwreck path to replicate the
  opcode conflict nightmare that plagued the Power ISA,
  two decades ago.
* Tensilica, Andes STAR and Western Digital for successful
  commercial proprietary ISAs: Tensilica in Baseband Modems,
  Andes in Audio DSPs, WD in HDDs and SSDs. These are all
  astoundingly commercially successful
  multi-billion-unit mass volume markets that almost nobody
  knows anything about. Included for completeness.

In order of least controlled to most controlled, the viable
candidates for further advancement are:

* OpenRISC 1200, not controlled or restricted by anyone. no patent
  protection.
* RISC-V, touted as "Open" but actually strictly controlled under
  Trademark License: too new to have adequate patent pool protection,
  as evidenced by multiple adopters having been hit by patent lawsuits.
* MIPS, SPARC, ARC, and others, simply have no viable ecosystem.
* Power ISA: protected by IBM's extensive patent portfolio for Members
  of the OpenPOWER Foundation, covered by Trademarks, permitting
  and encouraging contributions, and having software support for over
  20 years.
* ARM, not permitting Open Licensing, they survived in the early 90s
  only by doing a deal with Samsung for an in-perpetuity
  Royalty-free License, in exchange
  for GBP 3 million and legal protection through Samsung Research.
  Several large Corporations (Apple most notably) have licensed the ISA
  but not ARM designs: the barrier to entry is high and the ISA itself
  protected from interference as a result.
* x86, famous for an unprecedented
  Court Ruling in 2004 where a Judge "banged heads
  together" and ordered AMD and Intel to stop wasting his time,
  make peace, and cross-license each other's patents, anyone wishing
  to use the x86 ISA need only look at Transmeta, SiS, the Vortex x86,
  and VIA EDEN processors, and see how they fared.
* s390, IBM's mainframe ISA. Nowhere near as well-known as x86 lawsuits,
  but the 800lb Gorilla Syndrome seems not to have deterred one
  particularly disingenuous group from performing illegal
  Reverse-Engineering.

By asking the question, "which ISA would be the best and most stable to
base a Vector Supercomputing-class Extension on?" where patent protection,
software ecosystem, open-ness and pedigree all combine to reduce risk
and increase the chances of success, there is really only one candidate.

**Of all of these, the only one with the most going for it is the Power ISA.**

The summary of advantages, then, of the Power ISA is that:

* It has a 25-year software ecosystem, with RHEL, Fedora, Debian
  and more.
* IBM's extensive 20+ years of patents is available, royalty-free,
  to protect implementors as long as they are also members of the
  OpenPOWER Foundation
* IBM designed and maintained the Power ISA as a Supercomputing
  class ISA from its inception.
* Coherent distributed memory access is possible through OpenCAPI
* Extensions to the Power ISA may be submitted through an External
  RFC Process that does not require membership of OPF.

From this strong base, the next step is: how to leverage this
foundation to take a leap forward in performance and performance/watt,
*without* losing all the advantages of an ubiquitous software ecosystem?

# How do you turn a Scalar ISA into a Vector one?

The most obvious question before that is: why would you want to?
As explained in the "SIMD Considered Harmful" article, Cray-style
Vector ISAs break the link between data element batches and the
underlying architectural back-end parallel processing capability.
Packed SIMD explicitly smashes that width right in the face of the
programmer and expects them to like it.  As the article immediately
demonstrates, an arbitrary-sized data set has to contend with
an insane power-of-two Packed SIMD cascade at both setup and teardown
that can add literally an order
of magnitude increase in the number of hand-written lines of assembler
compared to a well-designed Cray-style Vector ISA with a `setvl`
instruction.

Assuming then that variable-length Vectors are obviously desirable,
it becomes a matter of how, not if.  Both Cray and NEC SX Aurora
went the way of adding explicit Vector opcodes, a style which RVV
copied and modernised. In the case of RVV this introduced 192 new
instructions on top of an existing 95+ for base RV64GC.  Adding
200% more instructions than the base ISA seems unwise: at least,
it feels like there should be a better way, particularly on
close inspection of RVV as an example, the basic arithmetic
operations are massively duplicated: scalar-scalar from the base
is joined by both scalar-vector and vector-vector *and* predicate
mask management, and transfer instructions between all the sane,
which goes a long way towards explaining why there are twice as many
Vector instructions in RISC-V as there are in the RV64GC base.

The question then becomes: with all the duplication of arithmetic
operations just to make the registers scalar or vector, why not
leverage the *existing* Scalar ISA with some sort of "context"
or prefix that augments its behaviour?

Remarkably this is not a new idea.  Intel's x86 `REP` instruction
gives the base concept, but in 1994 it was Peter Hsu, the designer
of the MIPS R8000, who first came up with the idea of Vector
prefixing.  Relying on a multi-issue Out-of-Order Execution Engine,
the prefix would mark which of the registers were to be treated as
Scalar and which as Vector, then perform a `REP`-like loop that
jammed multiple scalar operations into the Multi-Issue Execution
Engine.  The only reason that the team did not take this forward
into a commercial product
was because they could not work out how to cleanly do OoO
multi-issue at the time.

In its simplest form, then, this "prefixing" idea is a matter
of:

* Defining the format of the prefix
* Adding a `setvl` instruction
* Adding Vector-context SPRs and working out how to do
  context-switches with them
* Writing an awful lot of Specification Documentation
  (4 years and counting)

Once the basics of this concept have sunk in, early
advancements quickly follow naturally from analysis
of the problem-space:

* Predication (an absolutely critical component for a Vector ISA),
  then the next logical advancement is to allow separate predication masks
  to be applied to *both* the source *and* the destination, independently.
* Element-width overrides: most Scalar ISAs today are 64-bit only,
  with primarily Load and Store being able to handle 8/16/32/64
  and sometimes 128-bit (quad-word), where Vector ISAs need to
  go as low as 8-bit arithmetic, even 8-bit Floating-Point for
  high-performance AI.
* "Reordering" of the assumption of linear sequential element
  access, for Matrices, rotations, transposition, Convolutions,
  DCT, FFT, Parallel Prefix-Sum and other common transformations
  that require significant programming effort in other ISAs.

**What is missing from Power Scalar ISA that a Vector ISA needs?**

Remarkably, very little.

* The traditional `iota` instruction may be
  synthesised with an overlapping add, that stacks up incrementally
  and sequentially.  Although it requires two instructions (one to
  start the sum-chain) the technique has the advantage of allowing
  increments by arbitrary amounts, and is not limited to addition,
  either.
* Big-integer addition (arbitrary-precision arithmetic) is an
  emergent characteristic from the carry-in, carry-out capability of
  Power ISA `adde` instruction. `sv.adde` as a BigNum add
  naturally emerges from the
  sequential chaining of these scalar instructions.
* The Condition Register Fields of the Power ISA make a great candidate
  for use as Predicate Masks, particularly when combined with
  Vectorised `cmp` and Vectorised `crand`, `crxor` etc.