Vector processor ================ In computing, a vector processor is a central processing unit (CPU) that implements an instruction set where its instructions are designed to operate efficiently and architecturally sequentially on large one-dimensional arrays of data called vectors. When integrated as a hardware component the vector processor is often called a vector processing unit (VPU). This is in contrast to scalar processors, whose instructions operate on single data items only, and in contrast to some of those same scalar processors having additional single instruction, multiple data (SIMD) or SIMD within a register (SWAR) Arithmetic Units. Vector processors can greatly improve performance on certain workloads, notably numerical simulation, compression and similar tasks. Vector processing techniques also operate in video-game console hardware and in graphics accelerators but these are invariably Single instruction, multiple threads (SIMT) and occasionally Single instruction, multiple data (SIMD). Vector machines appeared in the early 1970s and dominated supercomputer design through the 1970s into the 1990s, notably the various Cray platforms. The rapid fall in the price-to-performance ratio of conventional microprocessor designs led to a decline in vector supercomputers during the 1990s. In computing, a vector processor is a central processing unit (CPU) that implements an instruction set where its instructions are designed to operate efficiently and architecturally sequentially on large one-dimensional arrays of data called vectors. When integrated as a hardware component the vector processor is often called a vector processing unit (VPU). This is in contrast to scalar processors, whose instructions operate on single data items only, and in contrast to some of those same scalar processors having additional single instruction, multiple data (SIMD) or SIMD within a register (SWAR) Arithmetic Units. Vector processors can greatly improve performance on certain workloads, notably numerical simulation, compression and similar tasks. Vector processing techniques also operate in video-game console hardware and in graphics accelerators but these are invariably Single instruction, multiple threads (SIMT) and occasionally Single instruction, multiple data (SIMD). Vector machines appeared in the early 1970s and dominated supercomputer design through the 1970s into the 1990s, notably the various Cray platforms. The rapid fall in the price-to-performance ratio of conventional microprocessor designs led to a decline in vector supercomputers during the 1990s. ===Computer for operations with functions=== A computer for operations with functions was presented and developed by Kartsev in 1967. Hypothetical RISC machine assume a, b, and c are memory locations in their respective registers add 10 numbers in a to 10 numbers in b, store results in c move $10, count ; count := 10 loop: load r1, a load r2, b add r3, r1, r2 ; r3 := r1 + r2 store r3, c add a, a, $4 ; move on add b, b, $4 add c, c, $4 dec count ; decrement jnez count, loop ; loop back if count is not yet 0 ret But to a vector processor, this task looks considerably different: assume we have vector registers v1-v3 with size equal or larger than 10 move $10, count ; count = 10 vload v1, a, count vload v2, b, count vadd v3, v1, v2 vstore v3, c, count ret Note the complete lack of looping in the instructions, because it is the hardware which has performed 10 sequential operations: effectively the loop count is on an explicit per-instruction basis. Cray-style vector ISAs take this a step further and provide a global "count" register, called vector length (VL): again assume we have vector registers v1-v3 with size larger than or equal to 10 setvli $10 # Set vector length VL=10 vload v1, a # 10 loads from a vload v2, b # 10 loads from b vadd v3, v1, v2 # 10 adds vstore v3, c # 10 stores into c ret There are several savings inherent in this approach. Only three address translations are needed. Depending on the architecture, this can represent a significant savings by itself. Another saving is fetching and decoding the instruction itself, which has to be done only one time instead of ten. The code itself is also smaller, which can lead to more efficient memory use, reduction in L1 instruction cache size, reduction in power consumption. With the program size being reduced branch prediction has an easier job. With the length (equivalent to SIMD width) not being hard-coded into the instruction, not only is the encoding more compact, it's also "future-proof" and allows even embedded processor designs to consider using vectors purely to gain all the other advantages, rather than go for high performance. Additionally, in more modern vector processor ISAs, "Fail on First" or "Fault First" has been introduced (see below) which brings even more advantages. But more than that, a high performance vector processor may have multiple functional units adding those numbers in parallel. The checking of dependencies between those numbers is not required as a vector instruction specifies multiple independent operations. This simplifies the control logic required, and can further improve performance by avoiding stalls. The math operations thus completed far faster overall, the limiting factor being the time required to fetch the data from memory. Not all problems can be attacked with this sort of solution. Including these types of instructions necessarily adds complexity to the core CPU. That complexity typically makes other instructions run slower—i.e., whenever it is not adding up many numbers in a row. The more complex instructions also add to the complexity of the decoders, which might slow down the decoding of the more common instructions such as normal adding. (This can be somewhat mitigated by keeping the entire ISA to RISC principles: RVV only adds around 190 vector instructions even with the advanced features. ) Vector processors were traditionally designed to work best only when there are large amounts of data to be worked on. For this reason, these sorts of CPUs were found primarily in supercomputers, as the supercomputers themselves were, in general, found in places such as weather prediction centers and physics labs, where huge amounts of data are "crunched". However, as shown above the efficiency of vector ISAs brings other benefits which are compelling even for Embedded use-cases. void iaxpy(size_t n, int a, const int x[], int y[]) { for (size_t i = 0; i In each iteration, every element of y has an element of x multiplied by a and added to it. The program is expressed in scalar linear form for readability. loop: load32 r1, x ; load one 32bit data load32 r2, y mul32 r1, a, r1 ; r1 := r1 * a add32 r3, r1, r2 ; r3 := r1 + r2 store32 r3, y addl x, x, $4 ; x := x + 4 addl y, y, $4 subl n, n, $1 ; n := n - 1 jgz n, loop ; loop back if n > 0 out: ret The STAR-like code remains concise, but because the STAR-100's vectorisation was by design based around memory accesses, an extra slot of memory is now required to process the information. Two times the latency is also needed due to the extra requirement of memory access. ; Assume tmp is pre-allocated vmul tmp, a, x, n ; tmp[i] = a * x[i] vadd y, y, tmp, n ; y[i] = y[i] + tmp[i] ret splatx4 v4, a ; v4 = a,a,a,a The time taken would be basically the same as a vector implementation of described above. vloop: load32x4 v1, x load32x4 v2, y mul32x4 v1, a, v1 ; v1 := v1 * a add32x4 v3, v1, v2 ; v3 := v1 + v2 store32x4 v3, y addl x, x, $16 ; x := x + 16 addl y, y, $16 subl n, n, $4 ; n := n - 4 jgz n, vloop ; go back if n > 0 out: ret Note that both x and y pointers are incremented by 16, because that is how long (in bytes) four 32-bit integers are. The decision was made that the algorithm shall only cope with 4-wide SIMD, therefore the constant is hard-coded into the program. Unfortunately for SIMD, the clue was in the assumption above, "that n is a multiple of 4" as well as "aligned access", which, clearly, is a limited specialist use-case. Realistically, for general-purpose loops such as in portable libraries, where n cannot be limited in this way, the overhead of setup and cleanup for SIMD in order to cope with non-multiples of the SIMD width, can far exceed the instruction count inside the loop itself. Assuming worst-case that the hardware cannot do misaligned SIMD memory accesses, a real-world algorithm will: first have to have a preparatory section which works on the beginning unaligned data, up to the first point where SIMD memory-aligned operations can take over. this will either involve (slower) scalar-only operations or smaller-sized packed SIMD operations. Each copy implements the full algorithm inner loop. perform the aligned SIMD loop at the maximum SIMD width up until the last few elements (those remaining that do not fit the fixed SIMD width) have a cleanup phase which, like the preparatory section, is just as large and just as complex. Eight-wide SIMD requires repeating the inner loop algorithm first with four-wide SIMD elements, then two-wide SIMD, then one (scalar), with a test and branch in between each one, in order to cover the first and last remaining SIMD elements (0 vloop: # prepare mask. few ISAs have min though min t0, n, $4 ; t0 = min(n, 4) shift m, $1, t0 ; m = 1 0 out: ret Here it can be seen that the code is much cleaner but a little complex: at least, however, there is no setup or cleanup: on the last iteration of the loop, the predicate mask will be set to either 0b0000, 0b0001, 0b0011, 0b0111 or 0b1111, resulting in between 0 and 4 SIMD element operations being performed, respectively. One additional potential complication: some RISC ISAs do not have a "min" instruction, needing instead to use a branch or scalar predicated compare. It is clear how predicated SIMD at least merits the term "vector capable", because it can cope with variable-length vectors by using predicate masks. The final evolving step to a "true" vector ISA, however, is to not have any evidence in the ISA at all of a SIMD width, leaving that entirely up to the hardware. vloop: setvl t0, n # VL=t0=min(MVL, n) vld32 v0, x # load vector x vld32 v1, y # load vector y vmadd32 v1, v0, a # v1 += v0 * a vst32 v1, y # store Y add y, t0*4 # advance y by VL*4 add x, t0*4 # advance x by VL*4 sub n, t0 # n -= VL (t0) bnez n, vloop # repeat if n != 0 This is essentially not very different from the SIMD version (processes 4 data elements per loop if MVL is 4), or from the initial Scalar version (processes just the one). n still contains the number of data elements remaining to be processed, but t0 contains the copy of VL – the number that is going to be processed in each iteration. t0 is subtracted from n after each iteration, and if n is zero then all elements have been processed. A number of things to note, when comparing against the Predicated SIMD assembly variant: The instruction has embedded within it a instruction Where the SIMD variant hard-coded both the width (4) into the creation of the mask and in the SIMD width (load32x4 etc.) the vector ISA equivalents have no such limit. This makes vector programs both portable, Vendor Independent, and future-proof. Setting VL effectively creates a hidden predicate mask that is automatically applied to the vectors Where with predicated SIMD the mask bitlength is limited to that which may be held in a scalar (or special mask) register, vector ISA's mask registers have no such limitation. Cray-I vectors could be just over 1,000 elements (in 1977). Thus it can be seen, very clearly, how vector ISAs reduce the number of instructions. Also note, that just like the predicated SIMD variant, the pointers to x and y are advanced by t0 times four because they both point to 32 bit data, but that n is decremented by straight t0. Compared to the fixed-size SIMD assembler there is very little apparent difference: x and y are advanced by hard-coded constant 16, n is decremented by a hard-coded 4, so initially it is hard to appreciate the significance. The difference comes in the realisation that the vector hardware could be capable of doing 4 simultaneous operations, or 64, or 10,000, it would be the exact same vector assembler for all of them and there would still be no SIMD cleanup code. Even compared to the predicate-capable SIMD, it is still more compact, clearer, more elegant and uses less resources. Not only is it a much more compact program (saving on L1 Cache size), but as previously mentioned, the vector version can issue far more data processing to the ALUs, again saving power because Instruction Decode and Issue can sit idle. Additionally, the number of elements going in to the function can start at zero. This sets the vector length to zero, which effectively disables all vector instructions, turning them into no-ops, at runtime. Thus, unlike non-predicated SIMD, even when there are no elements to process there is still no wasted cleanup code, or preamble: not even when n=0. VLVCU GR4 # Load VCT, update GR4 & CCode vloop: vld32 v0, x, v0 # load vector x, update v0 vld32 v1, y # load vector y (no update v1) vmadd32 v1, v0, a # v1 += v0 * a vst32 v1, y, v1 # store Y, now update v1 VLVCU GR4 # Load VCT, update GR4 & CCode BC 3,vloop # Branch back if VCT>0 The instruction would not only set the Vector Count Length ( ) but it would then subtract the new Vector Length from the Scalar register and update a Condition Code that the Branch could test. In effect combined two (three if including Condition Code setting) into one: # IBM 370 VLVCU does the following: setvl GR4 # VL=min(MVL, GR4) sub GR4, VL # n -= VL (GR4), also set CC Further, both the Vector-Load and Vector-Store instructions could perform the update of the address registers, saving on explicit instructions to perform address-calculations that in effect had already been done, behind the scenes, when loading/storing each element of the Vector. The exact same principle is used in Libre-SOC, illustrated with a DAXPY (64-bit floating-point) example: r5: n count; r6: x ptr; r7: y ptr; fp1: a mtctr 5 # move n to CTR vloop: setvl MAXVL=32,VL=CTR # actually VL=MIN(MAXVL,CTR) # DAXPY is 8-byte, hence 8(r6) and 8(r7) sv.lfdup *32,8(r6) # load x into fp32-63, incr x sv.lfd/els *64,8(r7) # load y into fp64-95, NO INC sv.fmadd *64,*64,1,*32 # (*y) = (*y) * (*x) + a sv.stfdup *64,8(r7) # store at y, post-incr y sv.bc/ctr vloop # decr CTR by VL, jump !zero Post-update modes are added to Vectorised versions of Load-with-Update and Store-with-Update, again saving on the need for a separate instruction for address computation when the CPU's Load/Store internals has already done it. Note again that as with the IBM 370 example: the Vector y address is updated by the Store-with-Update, not a Load-with-Update. The Power ISA CTR register is used for the total count instead of a scalar register, and the instruction performs the reduction of CTR by the current Vector Length (VL) followed by testing CTR for being zero and branching if it is not. The approach is different but achieves the same end-result as the IBM 3090: a significant compacting of instructions that are already considered highly compact. a RISC-V Vector DAXPY inner loop example is 10 instructions, where Libre-SOC and IBM 370 as shown above are both 6: a 40% reduction. void (size_t n, int a, const int x[]) { int y = 0; for (size_t i = 0; i Here, an accumulator (y) is used to sum up all the values in the array, x. set y, 0 ; y initialised to zero loop: load32 r1, x ; load one 32bit data add32 y, y, r1 ; y := y + r1 addl x, x, $4 ; x := x + 4 subl n, n, $1 ; n := n - 1 jgz n, loop ; loop back if n > 0 out: ret y ; returns result, y This is very straightforward. "y" starts at zero, 32 bit integers are loaded one at a time into r1, added to y, and the address of the array "x" moved on to the next element in the array. addl r3, x, $16 ; for 2nd 4 of x load32x4 v1, x ; first 4 of x load32x4 v2, r3 ; 2nd 4 of x add32x4 v1, v2, v1 ; add 2 groups At this point four adds have been performed: - First SIMD ADD: element 0 of first group added to element 0 of second group - Second SIMD ADD: element 1 of first group added to element 1 of second group - Third SIMD ADD: element 2 of first group added to element 2 of second group - Fourth SIMD ADD: element 3 of first group added to element 3 of second group but with 4-wide SIMD being incapable by design of adding for example, things go rapidly downhill just as they did with the general case of using SIMD for general-purpose IAXPY loops. To sum the four partial results, two-wide SIMD can be used, followed by a single scalar add, to finally produce the answer, but, frequently, the data must be transferred out of dedicated SIMD registers before the last scalar computation can be performed. Even with a general loop (n not fixed), the only way to use 4-wide SIMD is to assume four separate "streams", each offset by four elements. Finally, the four partial results have to be summed. The problems compound as the SIMD hardware width increases (an entirely new set of instruction is introduced), and, worse, some instructions to do Horizontal-sum such as the AMD XOP_instruction_set, were removed after a few years. Some techniques involve shuffle: examples online that involve highly detailed knowledge can be found for AVX-512 and SSE of how to do "Horizontal Sum" Aside from the size of the program and the complexity, an additional potential problem arises if floating-point computation is involved: the fact that the values are not being summed in strict order (four partial results) could result in rounding errors. setvl t0, n # VL=t0=min(MVL, n) vld32 v0, x # load vector x vredadd32 y, v0 # reduce-add into y The code when n is larger than the maximum vector length is not that much more complex, and is a similar pattern to the first example ("IAXPY"). set y, 0 vloop: setvl t0, n # VL=t0=min(MVL, n) vld32 v0, x # load vector x vredadd32 y, y, v0 # add all x into y add x, t0*4 # advance x by VL*4 sub n, t0 # n -= VL (t0) bnez n, vloop # repeat if n != 0 ret y The simplicity of the algorithm is stark in comparison to SIMD. Again, just as with the IAXPY example, the algorithm is length-agnostic (even on Embedded implementations where maximum vector length could be only one). Implementations in hardware may, if they are certain that the right answer will be produced, perform the reduction in parallel. Some vector ISAs offer a parallel reduction mode as an explicit option, for when the programmer knows that any potential rounding errors do not matter, and low latency is critical. This example again highlights a key critical fundamental difference between true vector processors and those SIMD processors, including most commercial GPUs, which are inspired by features of vector processors. Reduction and Iteration – operations that perform mapreduce on a vector (for example, find the one maximum value of an entire vector, or sum all elements). Iteration is of the form x[i] = y[i] + x[i-1] where Reduction is of the form x = y[0] + y[1]… + y[n-1] Matrix Multiply support – either by way of algorithmically loading data from memory, or reordering (remapping) the normally linear access to vector elements, or providing "Accumulators", arbitrary-sized matrices may be efficiently processed. IBM POWER10 provides MMA instructions although for arbitrary Matrix widths that do not fit the exact SIMD size data repetition techniques are needed which is wasteful of register file resources. NVidia provides a high-level Matrix CUDA API although the internal details are not available. The most resource-efficient technique is in-place reordering of access to otherwise linear vector data. Advanced Math formats – often includes Galois field arithmetic, but can include binary-coded decimal or decimal fixed-point, and support for much larger (arbitrary precision) arithmetic operations by supporting parallel carry-in and carry-out Bit manipulation – including vectorised versions of bit-level permutation operations, bitfield insert and extract, centrifuge operations, population count, and many others. Let r be the vector speed ratio and f be the vectorization ratio. If the time taken for the vector unit to add an array of 64 numbers is 10 times faster than its equivalent scalar counterpart, r = 10. Also, if the total number of operations in a program is 100, out of which only 10 are scalar (after vectorization), then f = 0.9, i.e., 90% of the work is done by the vector unit. It follows the achievable speed up of: r/[(1-f)*r+f] So, even if the performance of the vector unit is very high ( r=\infty ) there is a speedup less than 1/(1-f) , which suggests that the ratio f is crucial to the performance. This ratio depends on the efficiency of the compilation like adjacency of the elements in memory. REFERENCES ---------- BIBLIOGRAPHY (BibTeX) -------------------- @article{ref0, title = {Vector processor}, url = {https://encyclopegia.org/a/vector-processor} } BIBLIOGRAPHY (RIS) ------------------- TY - JOUR TI - Vector processor UR - https://encyclopegia.org/a/vector-processor ER - CITE THIS ARTICLE ---------------- Cite this article: Vector processor Derived from: https://en.wikipedia.org/w/index.php?oldid=1378437849 Licence: CC BY-SA 4.0 Snapshot: enwiki-001378437849 Permalink: /a/vector-processor