Editing Orthogonal instruction set

{{Short description|Type of computer instruction set}}
In [[computer engineering]], an '''orthogonal instruction set''' is an [[instruction set architecture]] where all instruction types can use all [[addressing mode]]s.  It is "[[Orthogonality|orthogonal]]" in the sense that the instruction type and the addressing mode may vary independently. An orthogonal instruction set does not impose a limitation that requires a certain instruction to use a specific register<ref name="NL10">{{cite book|last1=Null|first1=Linda|last2=Lobur|first2=Julia|title=The Essentials of Computer Organization and Architecture|year=2010|publisher=Jones & Bartlett Publishers|isbn=978-1449600068|pages=287–288}}</ref> so there is little overlapping of instruction functionality.<ref>{{citation|last=Tariq|first=Jamil|year=1995|issue=August/September|title=RISC vs CISC: Why less is more|journal=IEEE Potentials|url=https://www.researchgate.net/publication/3227233|access-date=7 May 2019}}</ref>

Orthogonality was considered a major goal for processor designers in the 1970s, and the [[VAX-11]] is often used as the benchmark for this concept. However, the introduction of [[reduced instruction set computer|RISC]] design philosophies in the 1980s significantly reversed the trend. 

Modern CPUs often simulate orthogonality in a preprocessing step before performing the actual tasks in a RISC-like core. This "simulated orthogonality" in general is a broader concept, encompassing the notions of [[Coupling (computer programming)|decoupling]] and completeness in [[Library (computing)|function libraries]], like in the mathematical concept: an [[orthogonal functions|orthogonal function set]] is easy to use as a basis into expanded functions, ensuring that parts don’t affect another if one part is changed.

==Basic concepts==
At their core, all general purpose computers work in the same underlying fashion; data stored in a [[main memory]] is read by the [[central processing unit]] (CPU) into a fast temporary memory (such as a set of [[Processor register|CPU registers]]), acted on, and then written back to main memory. Memory consists of a collection of data values, encoded as numbers{{efn|See [[digitization]].}} and referred to by their ''addresses'', each also a numerical value. This means the same operations applied to the data can be applied to the addresses themselves.{{efn|group="note"|address are fact simple binary numbers which may be treated as data}} While being worked on, data can be temporarily held in [[processor register]]s, scratchpad values that can be accessed very quickly. Registers are used, for example, when adding up strings of numbers into a total.<ref name=basic>{{cite web |url=http://etienne.ece.jhu.edu/etienne/teaching/ECE491/current/Lectures/chap5.pdf |title=Basic Computer Organization & Design |publisher= Computational Sensory-Motor Systems Laboratory}}</ref>

===Single instruction, single operand===
In early computers, the [[instruction set architecture]] (ISA) often used a single register, in which case it was known as the ''accumulator''. Instructions included an address for the operand. For instance, an <code>ADD ''address''</code> instruction would cause the CPU to retrieve the number in memory found at that address and then add it to the value already in the accumulator. This very simple example ISA has a "one-address format" because each instruction includes the address of the data.<ref name=format>{{cite web |url=http://cseweb.ucsd.edu/classes/wi05/cse240a/isa.pdf |title=Instruction Set Architecture |first=Dean |last=Tullsen |publisher=UCSD}}</ref>

One-address machines have the disadvantage that even simple actions like an addition require multiple instructions, each of which takes up scarce memory,{{efn|Even in modern computers, performance is maximized by keeping data in the cache, a limited resource.}} and requires time to be read. Consider the simple task of adding two numbers, 5 + 4. In this case, the program would have to load the value 5 into the accumulator with the <code>LOAD ''address''</code> instruction, use the <code>ADD ''address''</code> instruction pointing to the address for the 4, and finally <code>SAVE  ''address''</code> to store the result, 9, back to another memory location.<ref name=format/>

===Single instruction, multiple operands===
Further improvements can be found by providing the address of both of the operands in a single instruction, for instance, <code>ADD ''address 1'', ''address 2''</code>. Such "two-address format" ISAs are very common. One can further extend the concept to a "three-address format" where the  <code>SAVE</code> is also folded into an expanded <code>ADD ''address 1'', ''address 2'', ''address of result''</code>.<ref name=format/>

It is often the case that the basic [[computer word]] is much larger than needed to hold just the instruction and an address, and in most systems, there are leftover bits that can be used to hold a constant instead of an address. Instructions can be further improved if they allow any one of the operands to be replaced by a constant. For instance, <code>ADD ''address 1'', ''constant 1''</code> eliminates one memory cycle, and <code>ADD ''constant 1'', ''constant 2''</code> another.<ref name=format/>

===Multiple data===
Complexity arises when one considers common patterns in which memory is accessed. One very common pattern is that a single operation may be applied across a large amount of similar data. For instance, one might want to add up 1,000 numbers. In a simple two-address format of instructions,{{efn|assuming that the address cannot be operated on}} there is no way to change the address, so 1,000 additions have to be written in the [[machine language]]. ISAs fix this problem with the concept of ''indirect addressing'', in which the address of the next point of data is not a constant, but itself held in memory or a machine register. This means the programmer can change the address by performing addition on that memory location or register. ISAs also often include the ability to offset an address from an initial location, by adding a value held in one of its registers, in some cases a special ''index register''. Others carry out this addition automatically as part of the instructions that use it.<ref name=format/>

The variety of [[addressing mode]]s leads to a profusion of slightly different instructions. Considering a one-address ISA, for even a single instruction, <code>ADD</code>, we now have many possible "addressing modes":

* Immediate (constant): <code>ADD.C ''constant 1''</code> — adds the constant value to the result in the accumulator
* Direct address: <code>ADD.A ''address 1''</code> — add the value stored at address 1
* Memory indirect: <code>ADD.M ''address 1''</code> — read the value in address 1, use that value as another address and add that value

Many ISAs also have registers that can be used for addressing as well as math tasks. This can be used in a one-address format if a single address register is used. In this case, a number of new modes become available:

* Register direct: <code>ADD.R ''register 1''</code> — add the value stored in the address held in register one
* Displacement: <code>ADD.D ''constant 1''</code> — add the constant to the address register, then add the value found in memory at that resulting location
* Index: <code>ADD.I ''register 1''</code> — add the value in register 1 to the address register to make a new address and then adds the value at that location to the accumulator
* Autoindex: <code>ADD.AI ''register 1''</code> — as in the Index case, but automatically increments the address

==Orthogonality==
Orthogonality is the principle that every instruction should be able to use any supported addressing mode. In this example, if the direct addressing version of <code>ADD</code> is available, all the others should be as well. The reason for this design is not aesthetic, the goal is to reduce the total size of a program's [[object code]]. By providing a variety of addressing modes, the ISA allows the programmer to choose the one that precisely matches the need of their program at that point, and thereby reduce the need to use multiple instructions to achieve the same end. This means the total number of instructions is reduced, both saving memory and improving performance. Orthogonality was often described as being highly "bit efficient".<ref name=arch/>

Keeping the addressing mode specifier bits separate from the opcode operation bits produces an orthogonal instruction set.

As the ultimate end of orthogonal design is simply to allow any instruction to use any type of address, implementing orthogonality is often simply a case of adding more wiring between the parts of the processor. However, it also adds to the complexity of the instruction decoder, the circuitry that reads an instruction from memory at the location pointed to by the [[program counter]] and then decides how to process it.<ref name=arch/>

In the example ISA outlined above, the <code>ADD.C</code> instruction using direct encoding already has the data it needs to run the instruction and no further processing is needed, the decoder simply sends the value into the [[arithmetic logic unit]] (ALU). However, if the <code>ADD.A</code> instruction is used, the address has to be read, the value at that memory location read, and then the ALU can continue. This series of events will take much longer to complete and requires more internal steps.<ref name=arch/>

As a result, the time needed to complete different variations of an instruction can vary widely, which adds complexity to the overall CPU design. Therefore, orthogonality represents a tradeoff in design; the computer designer can choose to offer more addressing modes to the programmer to improve code density at the cost of making the CPU itself more complex.<ref name=arch/>

When memory was small and expensive, especially during the era of [[drum memory]] or [[core memory]], orthogonality was highly desirable. However, the complexity was often beyond what could be achieved using current technology. For this reason, most machines from the 1960s offered only partial orthogonality, as much as the designers could afford. It was in the 1970s that the introduction of [[large scale integration]] significantly reduced the complexity of computer designs and fully orthogonal designs began to emerge. By the 1980s, such designs could be implemented on a single-chip CPU.<ref name=arch/>

In the late 1970s, with the first high-powered fully orthogonal designs emerging, the goal widened to become the [[high-level language computer architecture]], or HLLCA for short. Just as orthogonality was desired to improve the bit density of machine language, HLLCA's goal was to improve the bit density of [[high-level language]]s like [[ALGOL 68]]. These languages generally used an [[activation record]], a type of complex [[Call stack|stack]] that stored temporary values, which the ISAs generally did not directly support and had to be implemented using many individual instructions from the underlying ISA. Adding support for these structures would allow the program to be translated more directly into the ISA.<ref name=arch/>

==Orthogonality in practice==

===The PDP-11===
The PDP-11 was substantially orthogonal (primarily excepting its floating point instructions).<ref name=psych>{{cite web |url=http://www.psych.usyd.edu.au/pdp-11/intro.html |title= Introduction to the PDP-11 |website=University of Sydney}}</ref> Most integer instructions could operate on either 1-byte or 2-byte values and could access data stored in registers, stored as part of the instruction, stored in memory, or stored in memory and pointed to by addresses in registers or memory. Even the [[Program counter|PC]] and the [[stack (data structure)|stack]] [[pointer (computer programming)|pointer]] could be affected by the ordinary instructions using all of the ordinary data modes. "Immediate" mode (hardcoded numbers within an instruction, such as ADD #4, R1 (R1 = R1 + 4) was implemented as the mode "register indirect, autoincrement" and specifying the program counter (R7) as the register to use reference for indirection and to autoincrement. (Encoded as ADD (R7)+,R1 .word 4.)<ref name=tor>{{cite web |url=https://www.teach.cs.toronto.edu//~ajr/258/pdp11.pdf |title=PDP-11 instruction reference |website=University of Toronto}}</ref>

The PDP-11 used 3-bit fields for addressing modes (0-7) so there were (electronically) 8 addressing modes. An additional 3-bit field specified the registers (R0–R5, SP, PC). Immediate and absolute address operands applying the two autoincrement modes to the Program Counter (R7), provided a total of 10 conceptual addressing modes.  Most two operand instructions supported all addressing modes for both parameters.<ref name=tor/>

===The VAX-11===
The [[VAX|VAX-11]] extended the PDP-11's orthogonality to all data types, including floating point numbers.<ref name=arch>{{cite book |title= Computer Architecture: A Quantitative Approach |first1= John |last1=Hennessy |first2=David |last2=Patterson |page=151 |url=https://books.google.com/books?id=XX69oNsazH4C&pg=PA151|isbn= 9780080502526 |date= 2002-05-29 |publisher= Elsevier }}</ref> Instructions such as 'ADD' were divided into data-size dependent variants such as ADDB, ADDW, ADDL, ADDP, ADDF for add byte, word, longword, packed BCD and single-precision floating point, respectively. Like the PDP-11, the Stack Pointer and Program Counter were in the general register file (R14 and R15).<ref name=another>{{cite web |title=Another Approach to Instruction Set Architecture—VAX |url=https://minnie.tuhs.org/CompArch/Resources/webext3.pdf}}</ref>

The general form of a VAX-11 instruction would be:

 [[opcode]] [ [[operand]] ] [ [[operand]] ]  ...

Each component being one [[byte]], the opcode a value in the range 0–255, and each operand consisting of two [[nibble]]s, the upper 4 bits specifying an addressing mode, and the lower 4 bits (usually) specifying a register number (R0–R15).<ref name=another/>

In contrast to the PDP-11's 3-bit fields, the VAX-11's 4-bit sub-bytes resulted in 16 [[Addressing mode|addressing modes]] (0–15).  However, addressing modes 0–3 were "short immediate" for immediate data of 6 bits or less (the 2 low-order bits of the addressing mode being the 2 high-order bits of the immediate data, when prepended to the remaining 4 bits in that data-addressing byte).  Since addressing modes 0-3 were identical, this made 13 (electronic) addressing modes, but as in the PDP-11, the use of the Stack Pointer (R14) and Program Counter (R15) created a total of over 15 conceptual addressing modes (with the assembler program translating the source code into the actual stack-pointer or program-counter based addressing mode needed).<ref name=another/>

===The MC68000 and similar===
Motorola's designers attempted to make the assembly language orthogonal while the underlying machine language was somewhat less so. Unlike PDP-11, the MC68000 (68k) used separate registers to store data and the addresses of data in memory. The ISA was orthogonal to the extent that addresses could only be used in those registers, but there was no restriction on ''which'' of the registers could be used by different instructions. Likewise, the data registers were also orthogonal across instructions. Unlike the PDP-11, the 68000 only supported one general addressing mode for two-parameter instructions. The other parameter was always a register, with the exception of MOV. The MOV instructions supported all addressing modes for both parameters.<ref name=68k>{{cite book |title= The 68000 Microprocessor |first= Andrew |last=Veronis |page=54 |url=https://books.google.com/books?id=O2DTBwAAQBAJ&pg=PA54|isbn= 9781468466478 |date= 2012-12-06 |publisher= Springer }}</ref>

In contrast, the [[NS320xx]] series were originally designed as single-chip implementations of the VAX-11 ISA. Although this had to change due to legal issues, the resulting system retained much of the VAX-11's overall design philosophy and remained completely orthogonal.<ref name="tilson198310">{{cite news | url=https://archive.org/stream/byte-magazine-1983-10/1983_10_BYTE_08-10_UNIX#page/n267/mode/2up | title=Moving Unix to New Machines | work=BYTE | date=October 1983 | access-date=31 January 2015 | author=Tilson, Michael | pages=266}}</ref> This included the elimination of the separate data and address registers found in the 68k.<ref>{{cite web |url=http://www.datormuseum.se/home/chips/ns32532 |title= NS32532 |website=Datormuseum}}</ref>

===The 8080 and follow on designs===
The 8-bit [[Intel 8080]] (as well as the 8085 and 8051) microprocessor was basically a slightly extended accumulator-based design and therefore not orthogonal. An assembly-language programmer or compiler writer had to be mindful of which operations were possible on each register: Most 8-bit operations could be performed only on the 8-bit [[Accumulator (computing)|accumulator]] (the A-register), while 16-bit operations could be performed only on the 16-bit pointer/accumulator (the HL-register pair), whereas simple operations, such as increment, were possible on all seven 8-bit registers. This was largely due to a desire to keep all opcodes one byte long.

The [[binary-compatible]] [[Z80]] later added prefix-codes to escape from this 1-byte limit  and allow for a more powerful instruction set. The same basic idea was employed for the [[Intel 8086]], although, to allow for more radical extensions, ''binary''-compatibility with the 8080 was not attempted here. It maintained some degree of non-orthogonality for the sake of high code density at the time. The 32-bit extension of this architecture that was introduced with the [[80386]], was somewhat more orthogonal despite keeping all the 8086 instructions and their extended counterparts. However, the ''encoding-strategy'' used still shows many traces from the 8008 and 8080 (and Z80). For instance, single-byte encodings remain for certain frequent operations such as [[Stack (abstract data type)|push and pop]] of registers and constants; and the primary accumulator, the [[EAX register]], employs shorter encodings than the other registers on certain types of operations. Observations like this are sometimes exploited for [[code optimization]] in both compilers and hand written code.

==RISC==
A number of studies through the 1970s demonstrated that the flexibility offered by orthogonal modes was rarely or never used in actual problems. In particular, an effort at [[IBM]] studied traces of code running on the [[System/370]] and demonstrated that only a fraction of the available modes were being used in actual programs. Similar studies, often about the VAX, demonstrated the same pattern. In some cases, it was shown that the complexity of the instructions meant they took longer to perform than the sequence of smaller instructions, with the canonical example of this being the VAX's <code>INDEX</code> instruction.<ref name=PattersonDitzel>{{Cite journal | last1 = Patterson | first1 = D. A. | author-link1 = David Patterson (scientist)| last2 = Ditzel | first2 = D. R. | author-link2 = David Ditzel| doi = 10.1145/641914.641917 | title = The case for the reduced instruction set computer | journal = [[ACM SIGARCH Computer Architecture News]] | volume = 8 | issue = 6 | pages = 25–33| year = 1980 | citeseerx = 10.1.1.68.9623| s2cid = 12034303 }}</ref>

During this same period, semiconductor memories were rapidly increasing in size and decreasing in cost. However, they were not improving in speed at the same rate. This meant the time needed to access data from memory was growing in ''relative'' terms in comparison to the speed of the CPUs. This argued for the inclusion of more registers, giving the CPU more temporary values to work with. A larger number of registers meant more bits in the computer word would be needed to encode the register number, which suggested that the instructions themselves be reduced in number to free up room.

Finally, a paper by [[Andrew S. Tanenbaum|Andrew Tanenbaum]] demonstrated that 97% of all the constants in a program are between 0 and 10, with 0 representing between 20 and 30% of the total. Additionally, between 30 and 40% of all the values in a program are constants, with simple variables (as opposed to arrays or such) another 35 to 40%.<ref>{{cite journal |first=Andrew |last= Tanenbaum |journal=Communications of the ACM |volume=21 |issue=3 |pages=237–246 |doi=10.1145/359361.359454 |title= Implications of structured programming for machine architecture |year= 1978 |hdl= 1871/2610 |s2cid= 3261560 |url= https://research.vu.nl/en/publications/5d0953e3-569e-4fa3-924a-0e56a80b550b |doi-access=free }}</ref> If the processor uses a larger instruction word, like 32-bits, two register numbers and a constant can be encoded in a single instruction as long as the instruction itself does not use too many bits.

These observations led to the abandonment of the orthogonal design as a primary goal of processor design, and the rise of the [[RISC]] philosophy in the 1980s. RISC processors generally have only two addressing modes, direct (constant) and register. All of the other modes found in older processors are handled explicitly using load and store instructions moving data to and from the registers. Only a few [[addressing mode]]s may be available, and these modes may vary depending on whether the instruction refers to data or involves a [[Branch (computer science)|transfer of control]].

==Notes==
{{notelist}}

==References==
<references/>

{{CPU technologies}}

[[Category:Instruction processing]]
[[Category:Instruction set architectures| ]]