1
\$\begingroup\$

Why most of processor only provide finite number of logic operations (NAND/NOR/XOR) while there are clearly 14 different logic gates available? I understand that we can implement any Boolean logic with only NAND/NOR . But practically, providing less gates make operations such as NIMPLY/IMPLY takes more than 1 cycle to finish as we need to implement them with composition of other gates. It seems to me that if ALU provides the whole set of hardware optimized logic gates we might be able to optimize software performance. Fanout might be an issue if all logic gates' output drive the same bus, but it seems logic operations aren't always the bottleneck of a modern processor because there are much more time consuming operations such as multiplication that limit the clock cycle. So my question is why we seldom see processors provide the full set of logic gates? What are the considerations involved? How do processor designers reach the optimal number of different logic operations the ALU is going to provide?

\$\endgroup\$
  • 2
    \$\begingroup\$ In order of importance 1. Because CMOS gates are very neat when you stick to NAND/NOR (4 transistors vs 6 for AND/OR) 2. All logic gates can be built with some combination of nand gates 3. Pipelining is already a necessary component of most modern CPU so an extra ALU cycle is not a big deal 4. x86 has lots of legacy implications \$\endgroup\$ – crasic Oct 29 '15 at 23:59
  • 1
    \$\begingroup\$ Nobody cares about the other operations, basically. The main use of the common 5 is setting or clearing bit fields. \$\endgroup\$ – pjc50 Oct 30 '15 at 0:13
  • 4
    \$\begingroup\$ I think you are pretty confused between logic gates and instruction set. \$\endgroup\$ – Fizz Oct 30 '15 at 0:17
  • \$\begingroup\$ @crasic If you need to do manipulation of large data-set, you identify some performance bottleneck and try to implement the core part using bit level manipulation, the result might be in the form of an accumulator, the additional 1 cycle will accumulates and the program might be slowed down by twice the amount of time and twice power. \$\endgroup\$ – Eagle Shou Oct 30 '15 at 0:31
5
\$\begingroup\$

If you would like to understand how processor designers reach their 'optimal' instruction set, you might want to look at some books, for example "Computer Architecture, A Quantitative Approach" by Hennessy & Patterson

There are quite a lot of papers freely available on the web about computer architecture, and Instruction Set Architecture (ISA).

I'd suggest read the papers and watch the videos at http://riscv.org

As a concrete example, look at the The RISC-V Compressed Instruction Set Manual

Their process for the "RISC-V Compressed Instruction Set Manual" was to gather sets of recognised, representative, 'benchmark' programs, in high level languages like C, and run analysis across them. For example, they might use an existing C compiler, modify its code generation to generate their prototype ISA, pass their benchmark programs through it, and analyse the results. That relies to some extent on the compiler having a rich enough model to make use of their ISA's instructions.

In the specific case of that compressed instruction set analysis, they wanted to identify which instructions were sufficiently common, that providing a compressed instruction would have reduce the code significantly. However, that analysis uses techniques which have been applied before.

The compressed instruction set analysis showed that only 31 instructions accounted for the vast majority of code, so compressing those by 50% reduced total program size by 25%. As quite a lot of code is data, that suggests that a lot of instructions are rarely used.

Remember, adding more instructions, and expanding the ALU is not necessarily free. To maximise throughput (i.e. doing useful work) we try to get a balance between latency (delay) through the ALU, power consumption, and overall instruction time. Adding an instruction which might make the CPU run 5% slower on every instruction, for 0.1% of the code to run 2x faster makes no sense.

This is a version of Amdahl's Law, which essentially says no matter how much one part of a system is improved, if it only accounts for 1% of (a programs) resources (time or space), then the improvement can only benefit the system's performance by 1%.

The vast majority of instructions executed by a program are loads, stores, simple arithmetic, jumps and conditional branches. As long as they execute well, adding a few specialised instructions to make rarely used operations faster will make virtually no difference. Worse, if the addition of specialised instructions slows the common instructions by a tiny amount, then it's likely better to remove them.

To learn more, look for older (1980s) RISC research papers. Maybe start with John L. Hennessy and David Patterson as they were quite prolific publishers, and Hennesey founded MIPS, and Patterson's work became SUN SPARC.

\$\endgroup\$
  • \$\begingroup\$ Excellent answer. Thank you very much! \$\endgroup\$ – Eagle Shou Oct 30 '15 at 9:20
  • \$\begingroup\$ The ALU likely won't [directly] run slower, but you'll need more die area for (1) the instruction decoder (2) actual execution unit. So more expensive both as die and as power consumption with little benefit. And since power is the real [per socket] limit to how fast CPUs runs these days: more wasted power, less speed indeed. By the way, modern CISC machines (x86) have RISC execution engines (micro-ops) under the hood; they just come with a beefy decoder. \$\endgroup\$ – Fizz Oct 30 '15 at 10:32
  • \$\begingroup\$ I should add: that beefy CISC-to-uops decoder is practical enough on laptop/desktop/server systems [these days], but once you get to microcontrollers or even smartphones... its power consumption is a real brick. That's why Intel is having trouble getting anything x86-based to scale down. \$\endgroup\$ – Fizz Oct 30 '15 at 10:38
  • \$\begingroup\$ @RespawnedFluff exactly what do you mean by "The ALU likely won't [directly] run slower"? What is intended by the qualification [directly]? AFAIK, semiconductor manufacturing processes are highly optimised for the specific devices and devices structures being manufactured. I assume that either, the extra types of logic gate are combinations of devices and so will consume more area, power and increase latency, or they are new devices, or device structures which may affect all those, and affect manufacturing optimisation. That's all. \$\endgroup\$ – gbulmer Oct 30 '15 at 19:24
  • \$\begingroup\$ @RespawnedFluff - I understand some of how CISCs work. CISC typically have many pipeline stages, cache, execution units, branch prediction, etc. to offset the extra latency. That isn't 'for free'. Introducing extra complexity will be paid for. We can have the CPU fast, cheap, or cool, chose any two. \$\endgroup\$ – gbulmer Oct 30 '15 at 19:36
3
\$\begingroup\$

There are sixteen basic bitwise logic operations available with 0, 1 or 2 inputs. (Zero inputs constitute constant values 0 and 1.) The 74LS181 4-bit ALU, used in such classic computers as the PDP-11, VAX 11/780 and many others computers implemented all of them. I am using this chip as an example because its datasheet exposes the internals circuitry and other details of the ALU. Such information is generally not available for microprocessors today. The sixteen operations (listed in the order they are addressed in the 74LS181) are:

~A          NOT A
~(A&B)      NAND
~A+B        A IMPLY B     can also be written ~(A & ~B)
1           constant 1
~(A+B)      NOR
~B          NOT B
~(A^B)      XNOR
A+~B        B IMPLY A     can also be written ~(~A & B) 
~A&B        B NIMPLY A
A^B         XOR
B           B
A+B         OR
0           constant 0
A&~B        A NIMPLY B
A&B         AND
A           A 

where ~ = bitwise NOT, & = AND, | = OR, and ^ = XOR as used in C and other languages.

IMPLY and NIMPLY are fairly specialized instructions mostly used in biology; see for example this paper and also this one. In hardware, they look like this:

enter image description here

I am not sure whether modern ALU's provide all sixteen operations, since there is no way to get to many of them via their processors' instruction sets.

Virtually all processors provide the four basic bitwise logic operations NOT, AND, OR and XOR in their machine level instruction sets, since all the other operations can be built up from them, as shown in the above table.

So a compiler generating code for the high level statement:

C = A & ~B;     // A NIMPLY B

might generate something like (using a hypothetical instruction set):

mov   R0, A    ; A => R0
mov   R1, B    ; B => R1
not   R1       ; ~R1 => R1
and   R0, R1   ; R0 & R1 => R0
mov   C, R0    ; R0 => C

Now it would be nice when a compiler recognized a pattern like C = A & ~B it was able to generate an instruction to tell the ALU to perform the A & ~B operation in one cycle (avoiding having to complement B first):

mov   R0, A    ; A => R0
mov   R1, B    ; B => R1
nimply R0, R1  ; R0 NIMPLY R1 => R0
mov   C, R0    ; R0 => C

but without the machine instruction for NIMPLY, it can't do this. However doing so only saves one instruction, is it worth it?

With the exception of the 80x86 family, whose CISC (Complex instruction set) dates back almost 40 years (1978), most processors today use some version of RISC (Reduced instruction set). Thus specialized, seldom used instructions like IMPLY and NIMPLY have no place in RISC processors.

\$\endgroup\$
  • \$\begingroup\$ That is very informative. I never heard of this chip before. Thank you very much for your answer ! I was thinking some "if else" logic might be able to be avoided and we can use NIMPLY instead... Anyway gbulmer's answer is more complete so I selected his answer. \$\endgroup\$ – Eagle Shou Oct 30 '15 at 9:33
  • \$\begingroup\$ @EagleShou Okay, since you had mentioned IMPLY and NIMPLY (which most people have never heard of), I was mostly trying to show you how they fit in with the ALU's set of 16 operators (which you also mentioned) and how they might look in an assembly program if a processor actually implemented them. \$\endgroup\$ – tcrosley Oct 30 '15 at 9:38

Your Answer

By clicking "Post Your Answer", you acknowledge that you have read our updated terms of service, privacy policy and cookie policy, and that your continued use of the website is subject to these policies.

Not the answer you're looking for? Browse other questions tagged or ask your own question.