View source for Very long instruction word

{{Short description|Computer architecture to aid parallelism}}
{{More citations needed|date=March 2014}}

'''Very Long Instruction Word (VLIW)''' is a type of  [[instruction set architecture]]  designed to exploit  [[instruction-level parallelism]] (ILP) by explicitly specifying, in advance, which instructions execute in parallel. 

VLIW architectures contrast with [[superscalar]] architectures, the predominant approach for exploiting ILP, where hardware dynamically discovers and schedules parallel execution at runtime. VLIW's primary motivation is achieving higher performance without the hardware complexity of superscalar designs. The circuitry needed to repeatedly analyze instruction streams and schedule parallel execution at runtime increases chip area, cost, and power consumption while potentially reducing clock speeds.

The name VLIW derives from the instruction format found in almost all implementations, where the [[compiler]] bundles operations intended to execute simultaneously into a single, wide instruction word dispatched to execution units as one unit. These words can be extremely wide—implementations have used instruction words of 1 kilobit or more. But this is only a side effect of the natural way to implement a VLIW. The distinguishing feature of a VLIW is that the exact execution order and parallelism are discovered and specified in advance.

VLIW shifts the burden of identifying parallelism from hardware to the compiler. This increases compiler complexity substantially, as it must schedule instructions while ensuring correctness, resolving resource conflicts (for execution units, registers, and memory ports), and exploiting the greater parallelism that simpler VLIW hardware exposes.

== History ==

The concept of VLIW architecture, and the term ''VLIW'', were invented by [[Josh Fisher]] in his research group at [[Yale University]] in the early 1980s.<ref name="eli512">{{ cite conference | first = Joseph A. | last = Fisher | author-link= Josh Fisher | year = 1983 | title = Very Long Instruction Word architectures and the ELI-512 | conference= International Symposium on Computer Architecture | book-title = Proceedings of the 10th annual international symposium on Computer architecture | publisher = [[Association for Computing Machinery]] (ACM) | location = New York, NY, USA | pages = 140–150 | doi = 10.1145/800046.801649 | isbn = 0-89791-101-6 | doi-access= free }}</ref> His original development of [[trace scheduling]] as a compiling method for VLIW was developed when he was a graduate student at [[New York University]]. Before VLIW, the notion of prescheduling [[execution unit]]s and instruction-level parallelism in software was well established in the practice of developing [[Microcode#Horizontal microcode|horizontal microcode]]. 

Fisher's innovations involved developing a compiler that could target horizontal microcode from programs written in an ordinary [[programming language]]. He realized that to get good performance and target a [[wide-issue]] machine, it would be necessary to find parallelism beyond that generally within a [[basic block]]. He also developed [[region scheduling]] methods to identify parallelism beyond basic blocks. Trace scheduling is such a method, and involves scheduling the most likely path of basic blocks first, inserting compensating code to deal with speculative motions, scheduling the second most likely trace, and so on, until the schedule is complete.

Fisher's second innovation was the notion that the target CPU architecture should be designed to be a reasonable target for a compiler; that the compiler and the architecture for a VLIW processor must be codesigned. This was inspired partly by the difficulty Fisher observed at Yale of compiling for architectures like [[Floating Point Systems]]' FPS164, which had a [[complex instruction set computing]] (CISC) architecture that separated instruction initiation from the instructions that saved the result, needing very complex scheduling algorithms. Fisher developed a set of principles characterizing a proper VLIW design, such as self-draining pipelines, wide multi-port [[register file]]s, and [[memory architecture]]s. These principles made it easier for compilers to emit fast code.

The first VLIW compiler was described in a Ph.D. thesis by John Ellis, supervised by Fisher. The compiler was named Bulldog, after Yale's mascot.<ref name="acmaward">{{ cite web | title = ACM 1985 Doctoral Dissertation Award | publisher = [[Association for Computing Machinery]] (ACM) | access-date = 2007-10-15 | url = http://awards.acm.org/citation.cfm?id=9267768&srt=year&year=1985&aw=146&ao=DOCDISRT | quote = For his dissertation ''Bulldog: A Compiler for VLIW Architecture''. | url-status = dead | archive-url = https://web.archive.org/web/20080402020350/http://awards.acm.org/citation.cfm?id=9267768&srt=year&year=1985&aw=146&ao=DOCDISRT | archive-date = 2008-04-02 }}</ref>

Fisher left Yale in 1984 to found a startup company, [[Multiflow]], along with cofounders John O'Donnell and John Ruttenberg. Multiflow produced the TRACE series of VLIW [[minisupercomputer]]s, shipping their first machines in 1987. Multiflow's VLIW could issue 28 operations in parallel per instruction. The TRACE system was implemented in a mix of [[Integrated circuit#Generations|medium-scale integration (MSI), large-scale integration (LSI), and very large-scale integration (VLSI)]], packaged in cabinets, a technology obsoleted as it grew more cost-effective to integrate all of the components of a processor (excluding memory) on one chip.

Multiflow was too early to catch the following wave, when chip architectures began to allow multiple-issue CPUs.{{clarify|date=January 2015|reason=does 'multiple-issue' mean pipelining?}} The major semiconductor companies recognized the value of Multiflow technology in this context, so the compiler and architecture were subsequently licensed to most of these firms.

== Motivation ==

A processor that executes every instruction one after the other (i.e., a non-[[instruction pipelining|pipelined]] scalar architecture) may use processor resources inefficiently, yielding potential poor performance. The performance can be improved by executing different substeps of sequential instructions simultaneously (termed ''pipelining''), or even executing multiple instructions entirely simultaneously as in [[superscalar]] architectures. Further improvement can be achieved by executing instructions in an order different from that in which they occur in a program, termed [[out-of-order execution]].<ref name=":0">{{Cite web |date=2020-12-01 |title=Very Long Instruction Word (VLIW) Architecture |url=https://www.geeksforgeeks.org/very-long-instruction-word-vliw-architecture/ |access-date=2022-10-14 |website=GeeksforGeeks |language=en-us}}</ref>

These three methods all raise hardware complexity. Before executing any operations in parallel, the processor must verify that the instructions have no [[dependence analysis|interdependencies]]. For example, if a first instruction's result is used as a second instruction's input, then they cannot execute at the same time and the second instruction cannot execute before the first. Modern out-of-order processors have increased the hardware resources which schedule instructions and determine interdependencies.

In contrast, VLIW executes operations in parallel, based on a fixed schedule, determined when programs are [[compiler|compiled]]. Since determining the order of execution of operations (including which operations can execute simultaneously) is handled by the compiler, the processor does not need the scheduling hardware that the three methods described above require. Thus, VLIW CPUs offer more computing with less hardware complexity (but greater compiler complexity) than do most superscalar CPUs.<ref name=":0" /> This is also complementary to the idea that as many computations as possible should be done before the program is executed, at compile time.

== Design ==

In superscalar designs, the number of execution units is invisible to the instruction set. Each instruction encodes one operation only. For most superscalar designs, the instruction width is 32 bits or fewer.

In contrast, one VLIW instruction encodes multiple operations, at least one operation for each execution unit of a device. For example, if a VLIW device has five execution units, then a VLIW instruction for the device has five operation fields, each field specifying what operation should be done on that corresponding execution unit. To accommodate these operation fields, VLIW instructions are usually at least 64 bits wide, and far wider on some architectures.

For example, the following is an instruction for the [[Super Harvard Architecture Single-Chip Computer]] (SHARC). In one cycle, it does a floating-point multiply, a floating-point add, and two autoincrement loads. All of this fits in one 48-bit instruction:

<code>f12 = f0 * f4, f8 = f8 + f12, f0 = dm(i0, m3), f4 = pm(i8, m9);</code>

Since the earliest days of computer architecture,<ref>{{cite web|title=Control Data 6400/6500/6600 Computer Systems Reference Manual|url=http://ed-thelen.org/comp-hist/CDC-6600-R-M.html|access-date=2013-11-07|date=1969-02-21|url-status=dead|archive-url=https://web.archive.org/web/20140102194752/http://ed-thelen.org/comp-hist/CDC-6600-R-M.html|archive-date=2014-01-02}}</ref> some CPUs have added several [[arithmetic logic unit]]s (ALUs) to run in parallel. [[Superscalar]] CPUs use hardware to decide which operations can run in parallel at runtime, while VLIW CPUs use software (the compiler) to decide which operations can run in parallel in advance. Because the complexity of instruction scheduling is moved into the compiler, complexity of hardware can be reduced substantially.{{clarify|date=May 2016|reason=Please quantity this, as a factor or fraction or percentage, of area or cost or some other useful variable.}}

A similar problem occurs when the result of a parallelizable instruction is used as input for a branch. Most modern CPUs ''guess'' which branch will be taken even before the calculation is complete, so that they can load the instructions for the branch, or (in some architectures) even start to [[speculative execution|compute them speculatively]]. If the CPU guesses wrong, all of these instructions and their context need to be ''[[pipeline flush |flushed]]'' and the correct ones loaded, which takes time.

This has led to increasingly complex instruction-dispatch [[branch predictor | logic that attempts to guess correctly]], and the simplicity of the original [[reduced instruction set computing]] (RISC) designs has been eroded. VLIW lacks this logic, and thus lacks its energy use, possible design defects, and other negative aspects.

In a VLIW, the compiler uses heuristics or [[profile-guided optimization | profile information to guess]] the direction of a branch. This allows it to move and preschedule operations speculatively before the branch is taken, favoring the most likely path it expects through the branch. If the branch takes an unexpected way, the compiler has already generated compensating code to discard speculative results to preserve program semantics.

[[Vector processor]] cores (designed for large [[Array (data structure)|one-dimensional arrays]] of data called ''vectors'') can be combined with the VLIW architecture such as in the Fujitsu [[FR-V]] microprocessor, further increasing [[throughput]] and [[Algorithmic efficiency#Speed|speed]].{{CN|date=July 2022}}

== Implementations ==

[[Cydrome]] was a company producing VLIW numeric processors using [[emitter-coupled logic]] (ECL) integrated circuits in the same timeframe (late 1980s). This company, like Multiflow, failed after a few years.

One of the licensees of the Multiflow technology is [[Hewlett-Packard]], which [[Josh Fisher]] joined after Multiflow's demise. [[Bob Rau]], founder of Cydrome, also joined HP after Cydrome failed. These two would lead computer architecture research at Hewlett-Packard during the 1990s.

Along with the above systems, during the same time (1989–1990), Intel implemented VLIW in the [[Intel i860]], their first 64-bit microprocessor, and the first processor to implement VLIW on one chip.<ref name="nxp">{{Cite web| url=http://www.nxp.com/acrobat_download2/other/vliw-wp.pdf |archive-url=https://web.archive.org/web/20110929113559/http://www.nxp.com/acrobat_download2/other/vliw-wp.pdf |title=An Introduction To Very-Long Instruction Word (VLIW) Computer Architecture |archive-date=2011-09-29 |publisher=Philips Semiconductors}}</ref> This processor could operate in both simple RISC mode and VLIW mode:
<blockquote>
In the early 1990s, Intel introduced the i860 RISC microprocessor. This simple chip had two modes of operation: a scalar mode and a VLIW mode. In the VLIW mode, the processor always fetched two instructions and assumed that one was an integer instruction and the other floating-point.<ref name="nxp"/>
</blockquote>

The i860's VLIW mode was used extensively in [[Embedded system|embedded]] [[digital signal processor]] (DSP) applications since the application execution and datasets were simple, well ordered and predictable, allowing designers to fully exploit the parallel execution advantages enabled by VLIW. In VLIW mode, the i860 could maintain floating-point performance in the range of 20-40 double-precision MFLOPS; a very high value for its time and for a processor running at 25-50Mhz.

In the 1990s, Hewlett-Packard researched this problem as a side effect of ongoing work on their [[PA-RISC]] processor family. They found that the CPU could be greatly simplified by removing the complex dispatch logic from the CPU and placing it in the compiler. Compilers of the day were far more complex than those of the 1980s, so the added complexity in the compiler was considered to be a small cost.

VLIW CPUs are usually made of multiple RISC-like [[execution unit]]s that operate independently. Contemporary VLIWs usually have four to eight main execution units. Compilers generate initial instruction sequences for the VLIW CPU in roughly the same manner as for traditional CPUs, generating a sequence of RISC-like instructions. The compiler analyzes this code for dependence relationships and resource requirements. It then schedules the instructions according to those constraints. In this process, independent instructions can be scheduled in parallel. Because VLIWs typically represent instructions scheduled in parallel with a longer instruction word that incorporates the individual instructions, this results in a much longer [[opcode]] (termed ''very long'') to specify what executes on a given cycle.

Examples of contemporary VLIW CPUs include the [[TriMedia (mediaprocessor)|TriMedia]] media processors by [[NXP Semiconductors|NXP]] (formerly Philips Semiconductors), the [[Super Harvard Architecture Single-Chip Computer]] (SHARC) DSP by Analog Devices, the [[ST200 family]] by STMicroelectronics based on the Lx architecture (designed in Josh Fisher's HP lab by Paolo Faraboschi), the [[FR-V]] from [[Fujitsu]], the BSP15/16<ref name="pixelworks">{{cite web |url=http://www.pixelworks.com/ |archive-url=https://web.archive.org/web/19961224073554/http://www.pixelworks.com/ |archive-date=1996-12-24 |url-status=dead |title=Pixelworks &#124; BSP15/16 |access-date=2016-07-28 }}</ref> from [[Pixelworks]], the [[CEVA-X DSP]] from CEVA, the [[Jazz DSP]] from Improv Systems, the HiveFlex<ref>{{cite web |title=silicon hive Products |url=http://www.siliconhive.com/Flex/Site/Page.aspx?SectionID=867&Lang=UK |website=Silicon Hive |publisher=Silicon Hive BV |access-date=2012-01-28 |archive-url=https://web.archive.org/web/20120128101047/http://www.siliconhive.com/Flex/Site/Page.aspx?SectionID=867&Lang=UK |archive-date=2012-01-28 |url-status=dead}}</ref> series from Silicon Hive, and the MPPA Manycore family by Kalray. The Texas Instruments [[TMS320]] [[Digital signal processor|DSP]] line has evolved, in its [[Texas Instruments TMS320#C6000 series|C6000]] family, to look more like a VLIW, in contrast to the earlier [[Texas Instruments TMS320#C5000 series|C5000]] family. One or more [[Qualcomm Hexagon]]s can be found in most cell phones today. These contemporary VLIW CPUs are mainly successful as embedded media processors for consumer electronic devices.

VLIW features have also been added to configurable processor cores for [[system-on-a-chip]] (SoC) designs. For example, Tensilica's [[Xtensa]] LX2 processor incorporates a technology named Flexible Length Instruction eXtensions (FLIX) that allows multi-operation instructions. The Xtensa C/C++ compiler can freely intermix 32- or 64-bit FLIX instructions with the Xtensa processor's one-operation RISC instructions, which are 16 or 24 bits wide. By packing multiple operations into a wide 32- or 64-bit instruction word and allowing these multi-operation instructions to intermix with shorter RISC instructions, FLIX allows SoC designers to realize VLIW's performance advantages while eliminating the [[code bloat]] of early VLIW architectures.
The Infineon Carmel DSP is another VLIW processor core intended for SoC. It uses a similar code density improvement method called ''configurable long instruction word'' (CLIW).<ref name="eembc">{{cite web|url=https://www.eembc.org/press/pressrelease/020313.htm |title=EEMBC Publishes Benchmark Scores for Infineon Technologies' Carmel - DSP Core and TriCore - TC11IB Microcontroller |publisher=eembc.org|access-date=2016-07-28}}</ref>

Outside embedded processing markets, Intel's [[Itanium]] IA-64 [[explicitly parallel instruction computing]] (EPIC) and [[Elbrus 2000]] appear as the only examples of a widely used VLIW CPU architectures. However, EPIC architecture is sometimes distinguished from a pure VLIW architecture, since EPIC advocates full instruction predication, rotating register files, and a very long instruction word that can encode non-parallel instruction groups. VLIWs also gained significant consumer penetration in the [[graphics processing unit]] (GPU) market, though both [[Nvidia]] and [[AMD]] have since moved to RISC architectures to improve performance on non-graphics workloads.

[[ATI Technologies]]' (ATI) and [[Advanced Micro Devices]]' (AMD) [[TeraScale (microarchitecture)|TeraScale]] microarchitecture for [[graphics processing unit]]s (GPUs) is a VLIW microarchitecture.

In December 2015, the first shipment of PCs based on VLIW CPU [[Elbrus-2S+|Elbrus-4s]] was made in Russia.<ref name="tass">{{cite web|url=https://tass.ru/ekonomika/2498729|title=ТАСС|publisher=tass.ru|access-date=2016-07-28}}</ref>

The Neo by REX Computing is a processor consisting of a 2D mesh of VLIW cores aimed at power efficiency.<ref>{{cite web |title=The Tiny Chip That Could Disrupt Exascale Computing |url=https://www.nextplatform.com/2015/03/12/the-little-chip-that-could-disrupt-exascale-computing/ |website=The Next Platform |date=12 March 2015 |publisher=Stackhouse Publishing Inc |access-date=26 April 2021}}</ref>

The [[Elbrus 2000]] ({{langx|ru|Эльбрус 2000}}) and its successors are Russian 512-bit wide VLIW microprocessors developed by [[Moscow Center of SPARC Technologies]] (MCST) and fabricated by [[TSMC]].

== Backward compatibility ==
{{refimprove section|date=June 2016}}

When silicon technology allowed for wider implementations (with more execution units) to be built, the compiled programs for the earlier generation would not run on the wider implementations, as the encoding of binary instructions depended on the number of execution units of the machine.

[[Transmeta]] addressed this issue by including a binary-to-binary software compiler layer (termed ''[[Binary translation|code morphing]]'') in their [[Transmeta Crusoe|Crusoe]] implementation of the [[x86]] architecture. This mechanism was advertised to basically recompile, optimize, and translate x86 opcodes at runtime into the CPU's internal machine code. Thus, the Transmeta chip is ''internally'' a VLIW processor, effectively decoupled from the x86 CISC [[instruction set]] that it executes.

Intel's [[Itanium]] architecture (among others) solved the backward-compatibility problem with a more general mechanism. Within each of the multiple-opcode instructions, a bit field is allocated to denote dependency on the prior VLIW instruction within the program instruction stream. These bits are set at [[compile time]], thus relieving the hardware from calculating this dependency information. Having this dependency information encoded in the instruction stream allows wider implementations to issue multiple non-dependent VLIW instructions in parallel per cycle, while narrower implementations would issue a smaller number of VLIW instructions per cycle.

Another perceived deficiency of VLIW designs is the [[code bloat]] that occurs when one or more execution unit(s) have no useful work to do and thus must execute ''No Operation'' [[NOP (code)|NOP]] instructions. This occurs when there are dependencies in the code and the instruction pipelines must be allowed to drain before later operations can proceed.

Since the number of transistors on a chip has grown, the perceived disadvantages of the VLIW have diminished in importance. VLIW architectures are growing in popularity, especially in the [[embedded system]] market, where it is possible to customize a processor for an application in a [[system-on-a-chip]].

== See also ==

* {{Annotated link|No instruction set computing}}
* {{Annotated link|One-instruction set computer}}
* {{Annotated link|Complex instruction set computer}}
* {{annotated link|Explicitly parallel instruction computing}}
* {{Annotated link|Minimal instruction set computer}}
* {{Annotated link|Reduced instruction set computer}}
* {{annotated link|Elbrus (computer)}}
* {{annotated link|Itanium}}
* {{annotated link|Movidius}}
* {{annotated link|Single instruction, multiple data}}
* {{annotated link|Single instruction, multiple threads}}
* {{annotated link|Transport triggered architecture}}

== References ==

{{refs}}

== External links ==

* [http://doi.acm.org/10.1145/800046.801649 Paper That Introduced VLIWs]
* [http://www.multiflowthebook.com Book on the history of Multiflow Computer, VLIW pioneering company]
* [http://www.hpl.hp.com/news/2005/jul-sep/VLIW_retrospective.pdf ISCA "Best Papers" Retrospective On Paper That Introduced VLIWs] {{Webarchive|url=https://web.archive.org/web/20120310074119/http://www.hpl.hp.com/news/2005/jul-sep/VLIW_retrospective.pdf |date=2012-03-10 }}
* [http://www.vliw.org/ VLIW and Embedded Processing]
* [https://web.archive.org/web/20080818033118/http://www.fujitsu.com/downloads/MAG/vol36-1/paper06.pdf FR500 VLIW-architecture High-performance Embedded Microprocessor]
* [https://people.cs.clemson.edu/~mark/epic.html Historical background for EPIC instruction set architectures]
* [http://opac.lib.rpi.edu/search~S6?/Xyerazunis&m=t&m=r&m=g&m=a&m=o&SORT=D&searchscope=6/Xyerazunis&m=t&m=r&m=g&m=a&m=o&SORT=D&searchscope=6&SUBKEY=yerazunis/1%2C14%2C14%2CB/frameset&FF=Xyerazunis&m=t&m=r&m=g&m=a&m=o&SORT=D&searchscope=6&1%2C1%2C DIS: an Architecture for fast LISP execution.] A similar VLIW architecture, with a parallelizing compiler directed toward LISP.

{{CPU technologies}}

[[Category:Very long instruction word computing| ]]
[[Category:Digital signal processing]]
[[Category:Instruction processing]]
[[Category:Instruction set architectures| ]]
[[Category:Parallel computing]]