The evolution of computer architecture has seen a significant shift in focus from instruction-level parallelism (ILP) towards more scalable and energy-efficient models for managing parallel computation. Instruction-level parallelism, once the cornerstone of processor performance improvement, relies heavily on complex hardware techniques like out-of-order execution to extract parallelism from a single thread of execution. However, as these techniques reach diminishing returns in terms of power and area efficiency, the architectural trend has increasingly favored explicit parallelism at higher levels of abstraction.
Contemporary architectures now prioritize models such as multiprocessors, thread-level parallelism (TLP), data-level parallelism (DLP), and request-level parallelism (RLP).
- Multiprocessors adopt the Multiple Instruction, Multiple Data (MIMD) paradigm, enabling independent processors to execute different instructions on different data.
- Thread-level parallelism distributes tasks across threads that can execute concurrently, often within a single processor core using simultaneous multithreading or across multiple cores.
- Data-level parallelism capitalizes on applying the same operation across large data sets, a strategy that has become increasingly relevant in scientific computing and machine learning.
- Request-level parallelism refers to the concurrent handling of independent service requests, often seen in large-scale web servers and cloud systems.
A significant alternative to the complex and power-hungry ILP designs is the use of in-order vector processors that leverage data-level parallelism. By executing a single instruction across multiple data elements, these architectures achieve comparable, if not superior, performance while consuming significantly less power. Unlike MIMD systems, which require fetching and decoding multiple instructions per cycle, vector processors fetch one instruction and apply it across data in parallel. This approach greatly reduces instruction overhead and control complexity, making it particularly appealing for energy-constrained environments such as mobile devices.
Flynn’s Taxonomy
To contextualize these architectural approaches, it is useful to revisit Flynn’s Taxonomy, a classification scheme that categorizes computer architectures based on the number of concurrent instruction and data streams. The taxonomy identifies four principal categories:
-
SISD (Single Instruction, Single Data) describes traditional sequential machines, such as scalar processors like the early MIPS architectures. These processors follow a linear execution model and include even more advanced superscalar processors that still operate on a single instruction stream, albeit with attempts to parallelize internally.
-
SIMD (Single Instruction, Multiple Data) represents architectures in which a single control unit issues instructions that are simultaneously executed across multiple data elements. Vector processors, multimedia extensions like MMX, SSE, and AVX, and modern GPUs fall under this category. SIMD architectures are well-suited for applications involving repetitive operations over large data arrays, such as in scientific computing, image processing, and neural network inference.
-
MISD (Multiple Instruction, Single Data) is a theoretical model with no known practical or commercial implementation. It describes a system where multiple instruction streams operate on the same data, a scenario that is generally infeasible or unnecessary in real-world applications. -
MIMD (Multiple Instruction, Multiple Data) includes both tightly-coupled systems with shared memory and thread-level parallelism and loosely-coupled systems with request-level parallelism. These architectures allow multiple independent processing units to execute distinct instruction streams on separate data sets, making them highly versatile for general-purpose computing tasks.
SIMD Architecture
Focusing specifically on SIMD architectures, these systems offer a streamlined and efficient way to exploit data-level parallelism. In a SIMD model, a centralized control unit broadcasts a single instruction to multiple processing elements (PEs), each operating on its own set of data. The architecture is tightly synchronized, as all PEs execute the same instruction in lockstep. This synchronization simplifies control and reduces code duplication: only one copy of the program is needed, and the overhead of managing multiple instruction streams is eliminated.
Each processing element in a SIMD system typically maintains its own registers and memory, allowing it to operate independently on its data. The single program counter across all PEs ensures consistent instruction execution, which is beneficial for workloads with high regularity in computation patterns, such as matrix operations, vector arithmetic, and convolution operations in image processing.
SIMD architectures require a fundamentally different hardware organization compared to MIMD systems. The control logic and instruction memory can be shared across all PEs, significantly reducing hardware redundancy. Moreover, since only one instruction needs to be fetched and decoded per cycle, the instruction throughput per watt is substantially higher than in MIMD architectures.
In practice, most systems that utilize SIMD do so in combination with SISD. A host processor handles the sequential part of the application and dispatches SIMD instructions to specialized SIMD units or co-processors. These SIMD units execute operations in parallel across data vectors, and often communicate via a dedicated interconnection network to exchange intermediate results.
There are three primary forms of SIMD machines in current use:
-
Vector Architectures: These are traditional SIMD systems designed specifically for high-performance computing tasks that require efficient manipulation of large vectors and matrices.
-
SIMD Extensions: These include instruction set enhancements such as MMX, SSE, and AVX in x86 architectures. These extensions allow general-purpose CPUs to accelerate multimedia, cryptography, and linear algebra operations by processing multiple data elements per instruction.
-
Graphics Processing Units (GPUs): Modern GPUs embody the SIMD paradigm at scale, featuring thousands of lightweight cores organized to perform massive parallel computation. Initially designed for rendering graphics, GPUs are now widely used in scientific computing, deep learning, and data analytics due to their ability to process data in parallel at very high throughput.
Vector Architecture
Vector architectures are a class of parallel processing designs that capitalize on data-level parallelism by enabling operations on entire arrays—or vectors—of data within a single instruction. Unlike scalar processors, which operate on one data element at a time, vector processors load blocks of data into special vector registers, perform operations on these vectors in parallel, and store the results back to memory. This approach minimizes instruction fetch overhead and allows high-throughput execution, especially useful in scientific and multimedia applications where large datasets and repetitive computations are common.
A defining characteristic of vector processors is their reliance on register-to-register operations, which help mask memory latency by working within the fast-access domain of the processor. The vector instruction set is executed under a single Program Counter, meaning all processing units operate in lockstep, and each result in a vector register is computed independently. This design allows a deep instruction pipeline and a high clock frequency since there are fewer pipeline hazards such as data dependencies or branches.
A traditional vector processor comprises several distinct components that work together to exploit parallelism:
- A scalar unit with vector extensions that manages conventional instruction execution and supports control flow.
- Vector registers, which store arrays of elements (typically between 64 to 128 elements per register).
- Vector functional units (FUs) that are pipelined to allow a new vector operation to start every cycle, supporting arithmetic and logical vector instructions.
- Load/store units that move data between memory and vector registers.
- An interleaved memory system that supports high-bandwidth, parallel memory accesses and eliminates the need for data caches.
- A cross-bar switch to connect different processor units and ensure smooth data routing.
The Cray-1, released in 1976, is a prominent example of a vector machine. It embodied a load/store architecture with pipelined execution units and achieved remarkable performance in scientific computing. It did not include virtual memory or cache, reflecting a focus on deterministic, high-throughput data operations over flexibility.
Example: VMIPS Architecture
The VMIPS vector architecture is loosely based on the Cray-1 design and incorporates a scalar architecture similar to MIPS. It features 8 vector registers, each capable of holding a vector of 64 elements, with each element being 64 bits wide. To support high throughput, the vector register file includes at least 16 read ports and 8 write ports, enabling up to 8 simultaneous accesses. The architecture also includes 5 fully pipelined vector functional units, allowing a new operation to start every cycle. Additionally, the vector load-store unit is fully pipelined, capable of transferring one word per clock cycle after the initial memory latency.
The processor is equipped with 32 general-purpose scalar registers and 32 floating-point scalar registers, providing ample resources for scalar operations. The vector and scalar registers are designed with a significant number of read and write ports to facilitate simultaneous vector operations. While the control unit and scalar integer functional units are not explicitly shown, they play a crucial role in managing the overall operation of the architecture. This design emphasizes parallelism and efficiency, making it well-suited for high-performance computing tasks.
Vector architectures can be classified into two major styles:
- Memory-memory vector processors, where all vector operations involve memory directly. While conceptually simple, they often suffer from higher memory bandwidth demands and are now obsolete.
- Vector-register processors, which perform operations between vector registers and only access memory during load/store operations. This design mirrors load/store scalar architectures and dominates modern vector systems.
DAXPY Operations
To appreciate the benefit of vector processing, consider a common operation like DAXPY, which computes
for (int i = 0; i < 64; i++){
Y[i] = a * X[i] + Y[i];
}In a scalar implementation, each iteration involves loading individual elements, performing arithmetic, and storing results—resulting in numerous instructions and pipeline stalls. For a vector length of 64 elements, this might require over 500 instructions.
L.D F0, a ; load scalar a
DADDIU R4, Rx, #512 ; last address to load
Loop:
L.D F2, 0(Rx) ; load X[i]
MULT.D F2, F2, F0 ; multiply by a
L.D F4, 0(Ry) ; load Y[i]
ADD.D F4, F4, F2 ; add to Y[i]
S.D F4, 0(Ry) ; store result
DADDIU Rx, Rx, #8 ; increment X
DADDIU Ry, Ry, #8 ; increment Y
DSUBU R20, R4, Rx ; compute the boundary
BNEZ R20, Loop ; loop until all elements are processedIn contrast, vector processors can handle this with a minimal instruction set:
L.D F0, a ; load scalar a
LV V1, Rx ; load vector X
MULVS.D V2, V1, F0 ; multiply vector X by scalar a
LV V3, Ry ; load vector Y
ADDVV.D V4, V2, V3 ; add result to vector Y
SV Ry, V4 ; store the resultOnly 6 instructions are needed per loop (1 scalar and 5 vector instructions), and once pipelined, each functional unit can produce a new result every cycle. During execution, the vectorized code require
Pipeline stalls are confined to the initial stages (e.g., memory latency), after which the vector pipeline operates at full throughput. This results in significant performance gains and a drastic reduction in instruction count compared to scalar code.
Key Optimization Concepts in Vector Processing
Vector processors offer a rich set of mechanisms to optimize performance further:
- Operation chaining allows dependent vector operations to overlap in time, increasing throughput.
- Multiple lanes enable execution of more than one vector element per cycle by replicating functional units.
- Vector length control adjusts execution dynamically for loops that don’t align with the full vector length.
- Vector mask registers provide conditional execution within loops, allowing vectorization of
ifstatements. - Stride access facilitates working with two-dimensional arrays and matrix operations.
- Gather-scatter techniques allow accessing and updating non-contiguous data in memory, essential for sparse matrix operations.
Operation Chaining
Definition
Operation chaining is a performance-enhancing technique used in vector processors that allows dependent operations to proceed in an overlapping fashion.
In a traditional execution pipeline without chaining, a dependent vector instruction must wait until the entire result vector from the preceding operation has been fully computed and written back to registers before it can begin execution. This sequential constraint introduces significant delays, especially when operating on long vectors. Operation chaining addresses this inefficiency by enabling the immediate forwarding of individual results from one vector functional unit (FU) to the next as soon as they are computed.
In essence, chaining generalizes the concept of operand forwarding to the vector level. This means that, even in the presence of data dependencies between instructions, as soon as an element of the vector result becomes available, it can be consumed by the next operation. Consequently, two instructions with a read-after-write dependency can still operate in parallel, each progressing element by element through the vector rather than waiting for the entire vector to be processed. This approach significantly reduces the overall execution time of vector sequences.
Example
For example, if a vector instruction takes 64 cycles to execute due to a vector length of 64, and a subsequent instruction is dependent on its result, the total execution time without chaining could be as high as 192 cycles (3 operations × 64 elements).
With chaining, the dependent operation can start almost immediately, leading to an estimated execution time of approximately 66 cycles (64 for the main vector operation, plus a small overhead for the startup of the chained instruction).
Convoys and Chimes
In vector processors, the concepts of convoy and chime are used to abstract and analyze the scheduling and execution of multiple vector instructions.
Definition
A convoy refers to a set of vector instructions that can be executed together without causing structural hazards. In other words, convoys group instructions that are not constrained by the availability of functional units or by read-after-write conflicts—particularly when chaining is used to mitigate such dependencies.
When analyzing vector performance, it is common to express execution time in terms of chimes.
Definition
A chime is the amount of time required to execute a single convoy.
If a sequence of vector operations can be broken down into
For instance, consider the DAXPY operation in VMIPS, expressed as
L.D F0, a ; load scalar a
LV V1, Rx ; load vector X
MULVS.D V2, V1, F0 ; multiply vector X by scalar a
LV V3, Ry ; load vector Y
ADDVV.D V4, V2, V3 ; add result to vector Y
SV Ry, V4 ; store the result- The first convoy includes the vector load and multiplication (
LV,MULVS.D), which can overlap through chaining. - The second convoy contains another vector load and the addition (
LV,ADDVV.D), again leveraging chaining. - The final convoy performs the store operation (
SV).
This results in three chimes, leading to a total of
Multiple Lanes
A vector processor can be designed with multiple parallel lanes to further improve throughput.
Definition
A lane is essentially an independent pipeline capable of executing vector operations on a subset of vector elements. Rather than processing one element per cycle in a single lane, the use of multiple lanes allows multiple elements to be processed simultaneously, reducing the execution time proportionally.
Example
For example, with a vector length of 64 and only one lane, the processor can issue one vector addition per cycle, completing the vector in 64 cycles. If the architecture supports four lanes, four vector additions can be executed in parallel, and the entire operation completes in just 16 cycles.
Multiple lanes are particularly effective when combined with operation chaining, as they enable even finer-grained parallelism. While chaining reduces latency between dependent instructions, multiple lanes reduce the latency of each individual instruction, achieving both horizontal (instruction-level) and vertical (element-level) parallelism.
Vector Length Control
The concept of vector length control ensures flexibility in processing data vectors that do not exactly match the physical capabilities of the hardware. In most vector processors, the Maximum Vector Length (MVL) defines the maximum number of elements that can be stored in a vector register. In the VMIPS architecture, for instance, the MVL is 64. However, real-world applications often involve arrays of arbitrary sizes that may be shorter or longer than the MVL.
To manage this, vector processors use a special hardware register known as the Vector Length Register (VLR). Before executing a vector operation, the VLR is set to indicate how many elements the instruction should operate on.
- If the vector is short, that is, shorter than the MVL, the processor simply uses the VLR value to limit the number of active elements, leaving the rest of the register unused.
- On the other hand, when the data vector is longer than the MVL, the processor cannot complete the operation in a single instruction. Instead, it must break the task into segments, a method known as strip mining.
This technique restructures the original loop into smaller segments of length MVL, processing one segment per iteration. The first segment often handles the remainder (
Strip mining is essential for maintaining high performance and ensuring compatibility with datasets of varying sizes. It is often implemented at the compiler level, automatically transforming loops into vectorizable segments when possible.
Vector Mask Registers
Conditional operations within loops typically pose a challenge to vectorization, as they introduce control dependencies that prevent straightforward translation into parallel vector instructions. For example, consider a loop that performs a conditional update on elements of an array only when a certain condition is met. In scalar code, this is easily expressed using an if statement. However, such control flow can inhibit vectorization because not all elements of the vector may be active in every iteration.
To overcome this limitation, vector processors implement vector mask registers.
Definition
A vector mask register is essentially a Boolean vector that specifies, for each element position, whether the corresponding operation should be executed. When vector mask functionality is enabled, instructions operate only on those elements whose mask bit is set to
1, effectively filtering the elements based on a condition.
This approach enables conditional execution within a vectorized loop without explicitly branching.
for (int i = 0; i < 64; i++){
if(X[i] != 0)
X[i] = X[i] - Y[i];
}For instance, to implement the operation X[i] = X[i] - Y[i] only for positive X[i], we load the vectors X and Y into vector registers, compare X[i] to zero, and use the result to set the vector mask. The subsequent subtraction then applies only to the positions where the mask is active.
LV V1, Rx ; load vector X into V1
LV V2, Ry ; load vector Y into V2
LD F0, #0 ; load FP zero
SNEVS.D V1, F0 ; set VM(i) to 1 if V1(i) != 0
SUBVV.D V1, V1, V2 ; subtract under vector mask
SV Rx, V1 ; store the result back to XAlthough cycles are consumed even for non-executed masked-out elements, the benefit lies in the ability to preserve vectorization, thereby maintaining high throughput.
Memory Banks and Bandwidth Considerations
In vector processing systems, memory bandwidth becomes a critical concern because vector operations typically involve transferring large blocks of data between memory and vector registers. To support the simultaneous loading and storing of multiple vector elements, memory is divided into banks, which are independent memory modules capable of servicing requests in parallel. By distributing consecutive memory addresses across different banks, multiple memory accesses can be satisfied simultaneously, avoiding bottlenecks.
The effectiveness of this approach depends on factors such as processor frequency, memory latency, and the number of banks.
For example, if a processor operates with a cycle time of
and each of its 32 vector processors performs four loads and two stores per cycle, the aggregate memory bandwidth requirement is substantial. In such cases, at least four memory banks are required to sustain the load/store throughput without stalls.
If the number of banks is insufficient or if access patterns cause contention (e.g., many requests to the same bank in quick succession), bank conflicts occur, leading to reduced performance due to pipeline stalls.
Stride Accesses and Non-Contiguous Data
In many numerical applications, especially those involving matrices, data is not always laid out in memory in a way that aligns with the access pattern. For example, in row-major order (as used in C), elements of a matrix row are contiguous in memory, while elements of a column are separated by the row size multiplied by the element size (in bytes). To vectorize access to columns or any strided data pattern, vector processors must support strided memory access.
Strided access is facilitated through instructions such as LVWS, which stands for Load Vector With Stride. This instruction loads a vector register with elements from memory using a base address and a stride offset. The stride specifies the number of bytes between successive elements in memory. For example,
LVWS V1, (R1, R2)loads elements from memory addresses R1, R1 + R2, R1 + 2*R2, and so on into the vector register V1.
In matrix multiplication, especially when accessing the elements of a matrix column inside a loop, strided access becomes essential. However, using non-unit strides increases the risk of memory bank conflicts, particularly if the stride and number of banks have a low-least common multiple (LCM). A useful condition for detecting potential conflicts is:
When this inequality holds, performance can degrade due to repeated access to the same bank before it becomes available again.
Gather-Scatter Operations for Sparse Matrices
Sparse matrix computations introduce additional complexity because many elements are zero and should be ignored to save memory and computation. To process only the nonzero elements, vector processors employ gather and scatter operations in conjunction with index vectors. These index vectors identify which memory elements are relevant for a particular computation.
The gather operation uses an index vector to load non-contiguous elements from memory into a vector register. This is achieved using the LVI (Load Vector Indexed) instruction. For instance, if we have an array A and an index vector K, then LVI Va, (Ra + Vk) loads the values at addresses Ra + K[i] into Va. The scatter operation works similarly in reverse using SVI, which stores elements from a vector register into scattered memory locations.
To illustrate, consider the code:
for (i = 0; i < n; i++) {
A[K[i]] = A[K[i]] + C[M[i]];
}In this loop, the arrays K and M serve as index vectors pointing to the relevant elements of A and C. Vectorized execution would involve loading these indices, gathering the values from A and C, performing vector addition, and then scattering the results back into the positions specified by K.
LV Vk, Rk ; load index vector K
LVI Va, (Ra + Vk) ; gather A[K[i]]
LV Vm, Rm ; load index vector M
LVI Vc, (Rc + Vm) ; gather C[M[i]]
ADDVV.D Va, Va, Vc ; add gathered values
SVI Ra, Va ; scatter result back to A[K[i]]This approach allows the processor to handle non-contiguous memory accesses efficiently, as the gather and scatter operations can be performed in parallel with vector arithmetic. The index vectors can be stored in a compact format, and the gather-scatter instructions can be pipelined to minimize latency.
This is particularly useful in applications such as graph algorithms, where the adjacency list representation often leads to irregular memory access patterns. By using gather-scatter operations, vector processors can efficiently process sparse matrices without incurring the overhead of traditional memory accesses.
SIMD Instruction Set Extensions
Single Instruction, Multiple Data (SIMD) instruction set extensions were introduced to improve the performance of multimedia and signal processing applications, which often operate on data types smaller than the machine’s native word size. These data types—such as 8-, 16-, or 32-bit integers or floating-point values—frequently occur in operations like image and audio processing, where many operations can be performed in parallel on independent data elements.
SIMD exploits data-level parallelism by applying the same operation simultaneously to multiple data elements packed into wide registers. This technique enhances performance by processing several elements in a single instruction cycle, but it is less flexible and powerful compared to full-fledged vector processors. For instance, SIMD typically lacks support for advanced features such as strided memory access, scatter-gather addressing, and masking for conditional execution. These limitations stem from the need to keep the instruction encoding compact and compatible with existing scalar architectures.
SIMD instructions operate on operands stored in aligned and consecutive memory locations, requiring data to be carefully arranged in memory to ensure correct and efficient execution. Furthermore, SIMD architectures often rely on partitioned arithmetic units—for example, by disabling carry propagation across partitions in an adder—to allow parallel processing of smaller-sized elements within a single register.
Several implementations of SIMD instruction sets have emerged over the years, each extending the capabilities of general-purpose processors:
-
Intel MMX (introduced in 1996) was one of the earliest commercial SIMD extensions. It provided support for parallel operations on packed integer data, allowing eight 8-bit or four 16-bit operations per instruction using 64-bit registers. MMX was limited to integer arithmetic and reused the floating-point register file, which posed challenges for context switching.
-
Streaming SIMD Extensions (SSE), introduced by Intel in 1999, represented a significant improvement. SSE added a new set of 128-bit registers and extended support to floating-point arithmetic, enabling operations on four 32-bit or two 64-bit floating-point numbers per instruction, as well as support for integer operations. SSE also separated floating-point and SIMD registers, improving compatibility and performance.
-
Advanced Vector Extensions (AVX), released in 2010, further extended the register width to 256 bits (and later 512 bits with AVX-512). AVX allows parallel operations on four 64-bit elements, enabling greater throughput for compute-intensive tasks like matrix multiplication or signal filtering. It introduced support for non-destructive three-operand instructions and improved floating-point performance.
Despite these improvements, SIMD instruction sets still require the programmer or compiler to manage data alignment and register usage carefully. Moreover, the lack of masking and generalized indexing restricts their adaptability to complex control flows and irregular data structures, which vector processors with features like vector length registers or masking registers handle more naturally.