Content deleted Content added
Removed unnecessary bold from a single letter S in the fourth paragraph |
m Removing link(s) Wikipedia:Articles for deletion/Permute instruction closed as soft delete (XFDcloser) |
||
| (39 intermediate revisions by 11 users not shown) | |||
Line 1:
{{Short description|Type of parallel processing}}
{{
{{See also|SIMD within a register|Single instruction, multiple threads}}
{{Update|inaccurate=yes|date=March 2017}}▼
{{Flynn's Taxonomy}}
▲{{Update|inaccurate=yes|date=March 2017}}
[[File:SIMD2.svg|thumb|Single instruction, multiple data]]
'''Single instruction, multiple data''' ('''SIMD''') is a type of [[parallel
Such machines exploit [[Data parallelism|data level parallelism]], but not [[Concurrent computing|concurrency]]: there are simultaneous (parallel) computations, but each unit performs exactly the same instruction at any given moment (just with different data). A simple example is to add many pairs of numbers together, all of the SIMD units are performing an addition, but each one has different pairs of values to add. SIMD is
== Confusion between SIMT and SIMD ==
{{See also|SIMD within a register|Single instruction, multiple threads|Vector processor}}
[[Image:ILLIAC_IV.jpg|thumb|[[ILLIAC IV]] Array overview, from ARPA-funded Introductory description by Steward Denenberg, July 15 1971<ref>{{Cite web | title=Archived copy | url=https://apps.dtic.mil/sti/tr/pdf/ADA954882.pdf | archive-url=https://web.archive.org/web/20240427173522/https://apps.dtic.mil/sti/tr/pdf/ADA954882.pdf | archive-date=2024-04-27}}</ref>]]
SIMD has three different subcategories in [[Flynn's taxonomy#Single instruction stream, multiple data streams (SIMD)|Flynn's 1972 Taxonomy]], one of which is [[
▲Such machines exploit [[Data parallelism|data level parallelism]], but not [[Concurrent computing|concurrency]]: there are simultaneous (parallel) computations, but each unit performs exactly the same instruction at any given moment (just with different data). A simple example is to add many pairs of numbers together, all of the SIMD units are performing an addition, but each one has different pairs of values to add. SIMD is particularly applicable to common tasks such as adjusting the contrast in a [[digital image]] or adjusting the volume of [[digital audio]]. Most modern [[Central processing unit|CPU]] designs include SIMD instructions to improve the performance of [[multimedia]] use. In recent CPUs, SIMD units are tightly coupled with cache hierarchies and prefetch mechanisms, which minimize latency during large block operations. For instance, AVX-512-enabled processors can prefetch entire cache lines and apply fused multiply-add operations (FMA) in a single SIMD cycle.
SIMD should not be confused with [[Vector processing]], characterized by the [[Cray 1]] and clarified in [[Duncan's taxonomy]]. The
▲SIMD has three different subcategories in [[Flynn's taxonomy#Single instruction stream, multiple data streams (SIMD)|Flynn's 1972 Taxonomy]], one of which is [[Single instruction, multiple threads|SIMT]]. SIMT should not be confused with [[Thread (computing)|software threads]] or [[Multithreading (computer architecture)|hardware threads]], both of which are task time-sharing (time-slicing). SIMT is true simultaneous parallel hardware-level execution. A key distinction in SIMT is the presence of control flow mechanisms like warps (NVIDIA terminology) or wavefronts (AMD terminology). These allow divergence and convergence of threads, even under shared instruction streams, thereby offering slightly more flexibility than classical SIMD.
[[Vector processor#Difference between SIMD and vector processors|difference between SIMD and vector processors]] is primarily the presence of a Cray-style {{code|SET VECTOR LENGTH}} instruction.
One key distinction between SIMT and SIMD is that the SIMD unit will not have its own memory.
Each hardware element (PU) working on individual data item sometimes also referred as SIMD lane or channel. Modern [[graphics processing unit]]s (GPUs) are often wide SIMD (typically >16 data lanes or channel) implementations.{{cn|date=July 2024}} Some newer GPUs go beyond simple SIMD and integrate mixed-precision SIMD pipelines, which allow concurrent execution of 8-bit, 16-bit, and 32-bit operations in different lanes. This is critical for applications like AI inference, where mixed precision boosts throughput.▼
Another key distinction in SIMT is the presence of control flow mechanisms like warps ([[Nvidia]] terminology) or wavefronts (Advanced Micro Devices ([[AMD]]) terminology). [[ILLIAC IV]] simply called them "Control Signals". These signals ensure that each Processing Element in the entire parallel array is synchronized in its simultaneous execution of the (one, current) broadcast instruction.
▲Each hardware element (PU, or PE in [[ILLIAC IV]] terminology) working on individual data item sometimes also referred to as a [[SIMD lane]] or channel. The ILLIAC IV PE was a scalar 64-bit unit that could do 2x32-bit [[Predication_(computer_architecture)#SIMD,_SIMT_and_vector_predication|predication]]. Modern [[graphics processing unit]]s (GPUs) are
==History==
The first known operational use to date of [[SIMD within a register]] was the [[TX-2]], in 1958. It was capable of 36-bit operations and two 18-bit or four 9-bit sub-word operations.
The first use of SIMD instructions was in the [[ILLIAC IV]], which was completed in 1972. This included 64 (of an original design of 256) processors that had local memory to hold different values while performing the same instruction. Separate hardware quickly send out the values to be processed and gathered up the results.▼
▲The first commercial use of SIMD instructions was in the [[ILLIAC IV]], which was completed in 1972. This included 64 (of an original design of 256) processors that had local memory to hold different values while performing the same instruction. Separate hardware quickly
SIMD was the basis for [[vector processor|vector supercomputers]] of the early 1970s such as the [[CDC STAR-100|CDC Star-100]] and the [[TI Advanced Scientific Computer|Texas Instruments ASC]], which could operate on a "vector" of data with a single instruction. Vector processing was especially popularized by [[Cray]] in the 1970s and 1980s. Vector processing architectures are now considered separate from SIMD computers: [[Duncan's Taxonomy]] includes them whereas [[Flynn's Taxonomy]] does not, due to Flynn's work (1966, 1972) pre-dating the [[Cray-1]] (1977).▼
▲
The first era of modern SIMD computers was characterized by [[Massive parallel processing|massively parallel processing]]-style [[supercomputer]]s such as the [[Thinking Machines Corporation|Thinking Machines]] [[Connection Machine|CM-1 and CM-2]]. These computers had many limited-functionality processors that would work in parallel. For example, each of 65,536 single-bit processors in a Thinking Machines CM-2 would execute the same instruction at the same time, allowing, for instance, to logically combine 65,536 pairs of bits at a time, using a hypercube-connected network or processor-dedicated RAM to find its operands. Supercomputing moved away from the SIMD approach when inexpensive scalar [[Multiple instruction, multiple data|MIMD]] approaches based on commodity processors such as the [[Intel i860|Intel i860 XP]] became more powerful, and interest in SIMD waned.<ref>{{cite web|url=http://www.cs.kent.edu/~walker/classes/pdc.f01/lectures/MIMD-1.pdf|title=MIMD1 - XP/S, CM-5}}</ref>▼
▲The first era of modern SIMD computers was characterized by [[
The current era of SIMD processors grew out of the desktop-computer market rather than the supercomputer market. As desktop processors became powerful enough to support real-time gaming and audio/video processing during the 1990s, demand grew for this particular type of computing power, and microprocessor vendors turned to SIMD to meet the demand.<ref name="conte">{{cite conference |title=The long and winding road to high-performance image processing with MMX/SSE |first1=G. |last1=Conte |first2=S. |last2=Tommesani |first3=F. |last3=Zanichelli |book-title=Proc. Fifth IEEE Int'l Workshop on Computer Architectures for Machine Perception |year=2000 |doi=10.1109/CAMP.2000.875989 |s2cid=13180531 |hdl=11381/2297671}}</ref> This resurgence also coincided with the rise of DirectX and OpenGL shader models, which heavily leveraged SIMD under the hood. The graphics APIs encouraged programmers to adopt data-parallel programming styles, indirectly accelerating SIMD adoption in desktop software. Hewlett-Packard introduced [[Multimedia Acceleration eXtensions|MAX]] instructions into [[PA-RISC]] 1.1 desktops in 1994 to accelerate MPEG decoding.<ref>{{cite book |first=R.B. |last=Lee |chapter=Realtime MPEG video via software decompression on a PA-RISC processor |title=digest of papers Compcon '95. Technologies for the Information Superhighway |year=1995 |pages=186–192 |doi=10.1109/CMPCON.1995.512384 |isbn=0-8186-7029-0|s2cid=2262046 }}</ref> Sun Microsystems introduced SIMD integer instructions in its "[[Visual Instruction Set|VIS]]" instruction set extensions in 1995, in its [[UltraSPARC|UltraSPARC I]] microprocessor. MIPS followed suit with their similar [[MDMX]] system.▼
▲The current era of SIMD processors grew out of the desktop-computer market rather than the supercomputer market. As desktop processors became powerful enough to support real-time gaming and audio/video processing during the 1990s, demand grew for this
The first widely deployed desktop SIMD was with Intel's [[MMX (instruction set)|MMX]] extensions to the [[x86]] architecture in 1996. This sparked the introduction of the much more powerful [[AltiVec]] system in the [[Motorola]] [[PowerPC]] and IBM's [[IBM Power microprocessors|POWER]] systems. Intel responded in 1999 by introducing the all-new [[Streaming SIMD Extensions|SSE]] system. Since then, there have been several extensions to the SIMD instruction sets for both architectures. Advanced vector extensions AVX, [[AVX2]] and [[AVX-512]] are developed by Intel. AMD supports AVX, [[AVX2]], and [[AVX-512]] in their current products.<ref>{{Cite web |title=AMD Zen 4 AVX-512 Performance Analysis On The Ryzen 9 7950X Review |url=https://www.phoronix.com/review/amd-zen4-avx512 |access-date=2023-07-13 |website=www.phoronix.com |language=en}}</ref>
Line 30 ⟶ 42:
==Advantages==
An application that may take advantage of SIMD is one where the same value is being added to (or subtracted from) a large number of data points, a common operation in many [[multimedia]] applications. One example would be changing the brightness of an image. Each [[pixel]] of an image consists of three values for the brightness of the red (R), green (G) and blue (B) portions of the color. To change the brightness, the R, G and B values are read from memory, a value is added to (or subtracted from) them, and the resulting values are written back out to memory.
With a SIMD processor there are two improvements to this process. For one the data is understood to be in blocks, and a number of values can be loaded all at once. Instead of a series of instructions saying "retrieve this pixel, now retrieve the next pixel", a SIMD processor will have a single instruction that effectively says "retrieve n pixels" (where n is a number that varies from design to design). For a variety of reasons, this can take much less time than retrieving each pixel individually, as with a traditional CPU design. Moreover, SIMD instructions can exploit data reuse, where the same operand is used across multiple calculations, via broadcasting features. For example, multiplying several pixels by a constant scalar value can be done more efficiently by loading the scalar once and broadcasting it across a SIMD register.
Line 39 ⟶ 51:
* Not all algorithms can be vectorized easily. For example, a flow-control-heavy task like code [[parsing]] may not easily benefit from SIMD; however, it is theoretically possible to vectorize comparisons and ''"batch flow"'' to target maximal cache optimality, though this technique will require more intermediate state. Note: Batch-pipeline systems (example: GPUs or software rasterization pipelines) are most advantageous for cache control when implemented with SIMD intrinsics, but they are not exclusive to SIMD features. Further complexity may be apparent to avoid dependence within series such as code strings; while independence is required for vectorization.{{Clarify|reason=You lost me. whilst this is all probably true, it is not in easy-to-follow language. which probably means it needs its own subsection, or references, or just rewriting.|date=June 2021}} Additionally, divergent control flow—where different data lanes would follow different execution paths—can lead to underutilization of SIMD hardware. To handle such divergence, techniques like masking and predication are often employed, but they introduce performance overhead and complexity.
* Large register files which increases power consumption and required chip area.
* Currently, implementing an algorithm with SIMD instructions usually requires human labor; most
* Programming with
*# SIMD may have restrictions on [[Data structure alignment|data alignment]]; programmers familiar with
*# Gathering data into SIMD registers and scattering it to the correct destination locations is tricky (sometimes requiring
*# Specific instructions like rotations or three-operand addition are not available in some SIMD instruction sets.
*# Instruction sets are architecture-specific: some processors lack SIMD instructions entirely, so programmers must provide non-vectorized implementations (or different vectorized implementations) for them.
Line 48 ⟶ 60:
*# The early [[MMX (instruction set)|MMX]] instruction set shared a register file with the floating-point stack, which caused inefficiencies when mixing floating-point and MMX code. However, [[SSE2]] corrects this.
To remedy problems 1 and 5, Cray-style [[
ARM's [[Scalable Vector Extension]] takes another approach, known in [[Flynn's taxonomy#Single instruction stream, multiple data streams (SIMD)|Flynn's Taxonomy]]
==Chronology==
{| class="wikitable"
|+
|-
! Year !! Example
|-
| 1974 || [[ILLIAC IV]] - an Array Processor comprising scalar 64-bit PEs
|-
| 1974 || [[ICL Distributed Array Processor]] (DAP)
Line 68 ⟶ 80:
| 1981 || [[Geometric-Arithmetic Parallel Processor]] from [[Martin Marietta]] (continued at [[Lockheed Martin]], then at [http://www.teranex.com Teranex] and [[Silicon Optix]])
|-
|
|-
| 1985 || [[Connection Machine]], models 1 and 2 (CM-1 and CM-2), from [[Thinking Machines Corporation]]
|-
|
|-
| 1991 ||
|-
| 2001 ||
|}
==Hardware==
Small-scale (64 or 128 bits) SIMD became popular on general-purpose CPUs in the early 1990s and continued through 1997 and later with Motion Video Instructions (MVI) for [[DEC Alpha|Alpha]]. SIMD instructions can be found, to one degree or another, on most CPUs, including [[IBM]]'s [[AltiVec]] and
Intel's [[AVX-512]] SIMD instructions process 512 bits of data at once.
Line 88 ⟶ 100:
[[File:SIMD cpu diagram1.svg|right|thumb|280px| The SIMD tripling of four 8-bit numbers. The CPU loads 4 numbers at once, multiplies them all in one SIMD-multiplication, and saves them all at once back to RAM. In theory, the speed can be multiplied by 4.]]
SIMD instructions are widely used to process 3D graphics, although modern [[Video card|graphics card]]s with embedded SIMD have largely taken over this task from the CPU. Some systems also include permute functions that re-pack elements inside vectors, making them
Adoption of SIMD systems in [[personal computer]] software was at first slow, due to a number of problems. One was that many of the early SIMD instruction sets tended to slow overall performance of the system due to the re-use of existing floating point registers. Other systems, like [[MMX (instruction set)|MMX]] and [[3DNow!]], offered support for data types that were not interesting to a wide audience and had expensive context switching instructions to switch between using the [[Floating-point unit|FPU]] and MMX [[Processor register|registers]]. Compilers also often lacked support, requiring programmers to resort to [[assembly language]] coding.
SIMD on [[x86]] had a slow start. The introduction of [[3DNow!]] by [[Advanced Micro Devices|AMD]] and [[Streaming SIMD Extensions|SSE]] by [[
[[Apple Inc.|Apple Computer]] had somewhat more success, even though they entered the SIMD market later than the rest. [[AltiVec]] offered a rich system and can be programmed using increasingly sophisticated compilers from [[Motorola]], [[IBM]] and [[GNU]], therefore assembly language programming is rarely needed. Additionally, many of the systems that would benefit from SIMD were supplied by Apple itself, for example [[iTunes]] and [[QuickTime]]. However, in 2006, Apple computers moved to Intel x86 processors. Apple's [[Application programming interface|API]]s and [[Integrated development environment|development tools]] ([[Xcode|XCode]]) were modified to support [[SSE2]] and [[SSE3]] as well as AltiVec. Apple was the dominant purchaser of PowerPC chips from IBM and [[Freescale Semiconductor]]. Even though Apple has stopped using PowerPC processors in their products, further development of AltiVec is continued in several PowerPC and [[Power ISA]] designs from Freescale and IBM.
Line 99 ⟶ 111:
===Programmer interface===
It is common for publishers of the SIMD instruction sets to make their own [[C
The [[GNU C Compiler]] takes the extensions a step further by abstracting them into a universal interface that can be used on any platform by providing a way of defining SIMD datatypes.<ref>{{cite web |title=Vector Extensions |url=https://gcc.gnu.org/onlinedocs/gcc/Vector-Extensions.html |website=Using the GNU Compiler Collection (GCC) |access-date=16 January 2020}}</ref> The [[LLVM]] Clang compiler also implements the feature, with an analogous interface defined in the IR.<ref>{{cite web |title=Clang Language Extensions |url=https://clang.llvm.org/docs/LanguageExtensions.html |website=Clang 11 documentation |access-date=16 January 2020}}</ref> Rust's {{code|packed_simd}} crate (and the experimental {{code|std::simd}}) uses this interface, and so does [[Swift (programming language)|Swift]] 2.0+.
Line 105 ⟶ 117:
C++ has an experimental interface {{code|std::experimental::simd}} that works similarly to the GCC extension. LLVM's libcxx seems to implement it.{{Citation needed|date=March 2023}} For GCC and libstdc++, a wrapper library that builds on top of the GCC extension is available.<ref>{{cite web |title=VcDevel/std-simd |url=https://github.com/VcDevel/std-simd |publisher=VcDevel |date=6 August 2020}}</ref>
[[Microsoft Corporation|Microsoft]] added SIMD to [[.NET Core|.NET]] in RyuJIT.<ref>{{cite web|url=https://devblogs.microsoft.com/dotnet/ryujit-the-next-generation-jit-compiler-for-net|title=RyuJIT: The next-generation JIT compiler for .NET|date=30 September 2013
Instead of providing an SIMD datatype, compilers can also be hinted to auto-vectorize some loops, potentially taking some assertions about the lack of data dependency. This is not as flexible as manipulating SIMD variables directly, but is easier to use. [[OpenMP]] 4.0+ has a {{code|#pragma omp simd}} hint.<ref>{{cite web |title=SIMD Directives |url=https://www.openmp.org/spec-html/5.0/openmpsu42.html |website=www.openmp.org}}</ref> This OpenMP interface has replaced a wide set of nonstandard extensions, including [[Cilk]]'s {{code|#pragma simd}},<ref>{{cite web |title=Tutorial pragma simd |url=https://www.cilkplus.org/tutorial-pragma-simd |website=CilkPlus |date=18 July 2012 |access-date=9 August 2020 |archive-date=4 December 2020 |archive-url=https://web.archive.org/web/20201204055745/https://www.cilkplus.org/tutorial-pragma-simd |url-status=dead
===SIMD multi-versioning===
Line 114 ⟶ 126:
* Library multi-versioning (LMV): the entire [[Library (computing)|programming library]] is duplicated for many instruction set extensions, and the operating system or the program decides which one to load at run-time.
FMV, manually coded in assembly language, is quite commonly used in a number of performance-critical libraries such as glibc and libjpeg-turbo. [[Intel C++ Compiler]], [[GNU Compiler Collection]] since GCC 6, and [[Clang]] since clang 7 allow for a simplified approach, with the compiler taking care of function duplication and selection. GCC and clang requires explicit {{code|target_clones}} labels in the code to "clone" functions,<ref>{{cite web |title=Function multi-versioning in GCC 6 |url=https://lwn.net/Articles/691932/ |website=lwn.net |date=22 June 2016 }}</ref> while ICC does so automatically (under the command-line option {{code|/Qax}}). The [[Rust programming language]] also supports FMV. The setup is similar to GCC and Clang in that the code defines what instruction sets to compile for, but cloning is manually done via inlining.<ref>{{cite web |title=2045-target-feature |url= https://rust-lang.github.io/rfcs/2045-target-feature.html |website=The Rust RFC Book}}</ref>
As using FMV requires code modification on GCC and Clang, vendors more commonly use library multi-versioning: this is easier to achieve as only compiler switches need to be changed. [[Glibc]] supports LMV and this functionality is adopted by the Intel-backed Clear Linux project.<ref name=clear>{{cite web |title=Transparent use of library packages optimized for Intel® architecture |url=https://clearlinux.org/news-blogs/transparent-use-library-packages-optimized-intel-architecture |website=Clear Linux* Project |access-date=8 September 2019 |language=en}}</ref>
Line 125 ⟶ 137:
Instances of these types are immutable and in optimized code are mapped directly to SIMD registers. Operations expressed in Dart typically are compiled into a single instruction without any overhead. This is similar to C and C++ intrinsics. Benchmarks for [[4×4 matrix|4×4]] [[matrix multiplication]], [[3D vertex transformation]], and [[Mandelbrot set]] visualization show near 400% speedup compared to scalar code written in Dart.
==Commercial applications==
It has generally proven difficult to find sustainable commercial applications for SIMD-only processors.
One that has had some measure of success is the [[Geometric-Arithmetic Parallel Processor|GAPP]], which was developed by [[Lockheed Martin]] and taken to the commercial sector by their spin-off [[Teranex]]. The GAPP's recent incarnations have become a powerful tool in real-time [[digital image processing|video processing]] applications like conversion between various video standards and frame rates ([[NTSC]] to/from [[PAL]], NTSC to/from [[
A more ubiquitous application for SIMD is found in [[video game]]s: nearly every modern [[video game console]] since [[History of video game consoles (sixth generation)|1998]] has incorporated a SIMD processor somewhere in its architecture. The [[PlayStation 2]] was unusual in that one of its vector-float units could function as an autonomous [[
A later processor that used vector processing is the [[Cell (
Ziilabs produced an SIMD type processor for use on mobile devices, such as media players and mobile phones.<ref>{{cite web |url=https://secure.ziilabs.com/products/processors/zms05.aspx |title=ZiiLABS ZMS-05 ARM 9 Media Processor |website=ZiiLabs |access-date=2010-05-24 |url-status=dead |archive-url=https://web.archive.org/web/20110718153716/https://secure.ziilabs.com/products/processors/zms05.aspx |archive-date=2011-07-18
Larger scale commercial SIMD processors are available from ClearSpeed Technology, Ltd. and Stream Processors, Inc. [[ClearSpeed]]'s CSX600 (2004) has 96 cores each with two double-precision floating point units while the CSX700 (2008) has 192. Stream Processors is headed by computer architect [[Bill Dally]]. Their Storm-1 processor (2007) contains 80 SIMD cores controlled by a [[MIPS architecture|MIPS]] CPU.
==See also==
Line 146 ⟶ 156:
* [[Instruction set architecture]]
*[[Flynn's taxonomy]]
*
* [[
* [[OpenCL]]
Line 159 ⟶ 169:
* [http://software.intel.com/en-us/articles/optimizing-the-rendering-pipeline-of-animated-models-using-the-intel-streaming-simd-extensions Article about Optimizing the Rendering Pipeline of Animated Models Using the Intel Streaming SIMD Extensions]
* [https://web.archive.org/web/20130921070044/http://www.yeppp.info/ "Yeppp!": cross-platform, open-source SIMD library from Georgia Tech]
* [https://computing.llnl.gov/tutorials/parallel_comp/ Introduction to Parallel Computing from LLNL Lawrence Livermore National Laboratory] {{Webarchive|url=https://web.archive.org/web/20130610122229/https://computing.llnl.gov/tutorials/parallel_comp/ |date=2013-06-10
* {{GitHub|simd-everywhere/simde}}: A portable implementation of platform-specific intrinsics for other platforms (e.g. SSE intrinsics for ARM NEON), using C/C++ headers
| |||