Vector Computers

Vector Computers

1. Flynn's Taxonomy

   • It is one possible classification for computer architectures.
   • Single instruction, single data (SISD)
     • One instruction working on one data at a time.
     • Ex. Single processors;
   • Single instruction, multiple data (SIMD)
     • One instruction working on multiple data at the same time, in other words, the same instruction working on multiple data at the same time.
     • Ex. Vector architectures, GPUs;
   • Multiple instruction, single data (MISD)
     • Multiple instructions working on the same data.
     • Ex. Fault-tolerant systems;
   • Multiple instruction, multiple data (MIMD)
     • Multiple instructions working on multiple data in parallel.
     • Ex. multiprocessors;

2. MIMD vs SIMD

   • MIMD
     • Fetches one instruction per data operation
     • More flexibility
   • SIMD
     • Consume less power (one instruction can launch many data operations);
     • Programmer can think sequentially and still achieves parallel speedup by having parallel data.
     • More attractive for mobile devices and servers, where power consumption is a critical aspect.

3. SIMD vector processors

   • Are processors with high level instructions operating on vectors. A single instruction performs a large amount of work.
   • RISC or CISC?
   • Common fields of application for vector architectures
     • Scientific computing
     • Engineering
     • Machine Learning
     • Multimedia applications
   • Common Applications
     • Simulations
     • Weather forecasting
     • Operations on large matrices and vectors
     • Image/video processing
     • Games
   • Characteristics
     • Loop parallelism exposed by the programmer or compiler through the vector instructions.
     • Memory
       • Adapted to provide memory access to a whole vector instead of a single element.
     • Data Hazards
       • Hardware checks for data hazards between two vectors instructions once per vector operand, not once for each element within the vector.
     • Control Hazards
       • Control hazards may be eliminated if the whole loop is replaced by a vector instruction.
   • Basic Architecture
     • Consists of
       • Scalar unit (with a common pipeline)
       • Vector units
       • Ex. RISC-V with 32 vector registers. All functional units (FU) are vector FU.
     • Components
       • Vector Registers
         • Each vector register holds a single vector.
       • Scalar Registers
         • Scalar registers hold data as input to the vector functional units. They also hold computed addresses to pass to the vector load/store unit.
       • Vector Functional Units
         • Each unit is fully pipelined, thus it is able to start a new operation on every clock cycle. Control unit is necessary to detect hazards.
         • Control unit
           • Detects structural hazards for functional units.
           • Data hazards on register accesses
         • Fully pipelined
       • Vector Load/Store Unit
         • This unit loads/stores a vector from/to memory. It is fully pipelined, thus words can be moved between vector register and memory with a bandwidth of one word per clock after some initial latency. This unit also handles scalar loads and stores.
         • Fully pipelined
         • Handles load/store
           • Vector
           • Scalar
     • Some vectorial instructions for RISC-V ISA
       • vadd v0, v1, v2
         • v0 := v1 + v2
       • vsub v0, v1, v2
         • v0 := V1 - V2
       • vdiv V0, V1, V2
         • V0 := V1/V2
       • vld V0, X0
         • Load vector register v0 from memory starting at address Reg[x0]
       • vst V0, X0
         • Store vector register v0 into memory starting at address Reg[x0]
     • Operation Example: vector loop for RV64V
       • Using general purpose register
         • N° of instructions: 32 iterations x 8 instructions + 2 setup instructions= 258
           • OBS.: notice that the overhead instructions present in the RV64G implementation represents almost half of the loop, and they are not present in the RV64V code.
       • Using vector register
         • N° of instructions: 8

4. Vector Instruction Optimizations

   • Reasoning
     • Can vector instructions have the same latency of scalar instructions?
       • If so, what would be the expected performance gain?
   • About stalls
     • In the vector mode, an instruction stalls once per vector instruction rather than once per vector element. This is related to the frequency of pipeline interlocks. In vector processors, a vector instruction will stall only for the first element in each vector. The subsequent elements in the vector will smoothly run in the pipeline. In this sense, the pipeline stalls only once per vector instruction, instead of once per vector element.
   • Chaining
     • In the context of vector operations, the forwarding of element-dependent operations is named chaining.
     • Stalls only once per vector instruction. It will stall only for the first element in each vector.
   • Convoy
     • A convoy is a set of vector instructions that could potentially execute together. The set must not contain any structural hazards and must not contain any RAW hazard. However, with respect to the RAW hazard, chaining allows this set to be in the same convoy. Thus, the results from a first functional unit in the chain are forwarded to a second functional unit.
     • No structural hazards allowed in the convoy.
     • RAW data hazards only allowed if chaining is applied
     • Examples of convoys
   • Lane
     • Modern vector computers have vector functional units with multiple parallel pipelines. In multiple parallel lanes each lane contains one portion of the vector register file, and one execution pipeline from each vector functional unit.

5. Vector length registers

   • Registers
     • Maximum Vector Length (MVL)
     • Vector-length register (VL)
       • Controls the length of any vector operation, including vector length/store
       • IMPORTANT INEQUALITY
     • Vector-mask register
       • Boolean vector of size MVL. It is used in the vector-mask technique.
   • Important techniques
     • Strip Mining
       • Strip mining consists in a generation of code where each vector operation is done for a size less than or equal to mvl. On it, one loop handles any number of iterations that is a multiple of mvl, and another loop handles the remainder iteration, which must be less than the mvl size.
       • Example of code applying strip mining
         • The first cycle of the inner loop goes from i = 0 to i = VL -1. The other cycles of the inner loop go from VL to n - 1, walking through the whole vector.
     • Vector-mask control
       • This technique can be used to vectorize loops that have IF statements (which introduces control dependencies). The idea is to use a boolean vector with size MVL (vector-mask register) to indicate whether the operation will be or not performed for each element of the array.
       • • This loop can be vectorized using the vector-mask technique. X[i] is written only if the vector-mask element correspondent to element index i is TRUE.
       • Element-wise

6. Memory Banks

   • Motivation
     • A load/store operation for a vector unit is more complex than regular arithmetic FU. Startup penalty is very expensive (> 100 clock cycles).
   • Memory banks allow spreading accesses among multiple independent memory banks. The idea is to maintain one word fetched/stored per clock cycle. Various independent, or even redundant, accesses take place rather than a simple memory interleaving.
   • We want one word fetched/stored per clock cycle
   • Reasons
     • Many loads/stores per clock cycle are possible.
     • Load/store data words that are not sequential need independent bank addresses.
     • Multiple processors sharing the same memory system are equally possible.

7. Addressing

   • Sequential
     • Elements are adjacent in memory
   • Stride
     • The elements are separated by a fixed number of words.
     • Useful for merging vectors that will be operated.
   • Gather/scatter
     • The elements are addressed by another vector register, in other words, indirect addressing.
     • Useful for handling sparce matrices, for example.

8. EXAMPLES OF SIMD IMPLEMENTATIONS

   • INTEL MMX, 1996
     • 64-bit FP registers
     • eight 8-bit or four 16-bit operations
   • Streaming SIMD Extensions (SSE), 1999
     • 128-bit floating-point registers
     • sixteen 8-bit, eight 16-bit, or four 32-bit operations
   • Advanced Vector Extensions (AVX), 2010
     • 256-bit floating-point registers
     • four 64-bit integer/floating-point operations
   • AVX-512, 2017
     • 512-bit floating-point registers
     • eight 64-bit integer/floating-point operations

9. Wrap-up

   • Instructions that explore the potential parallelism among loops iterations
   • Great performance improvement, but limited to very specific type of operations, which limits the overall gain
     • Ahmdal's law
   • Strongly dependent on the existence of compilers that make use of the provided instructions
   • Demand bigger memory bandwidth
   • Vector instructions, and registers, were also included in microprocessors such as x86, PowerPC, and also in machines like Nintendo-64 and Playstation 2 to accelerate graphical operations

Imagens e arquivos do mapa