# Question
Title: What happens at the decode phase of the instruction cycle?
I am reading about the various phases of the Instruction Execution, I found out that we have three phases like below.

1. Fectch
2. Decode
3. Execute

Now if the part I don't understand is why do we need a decode phase ? The instruction will already be stored in a binary format at some memory location, why not just fetch and execute it.

# Answer
> 3 votes
Addressing the core of your question, instructions are typically stored in a format that requires some translation (decoding) to become the control signals for instruction execution. Requiring some decoding presents an abstraction layer between the hardware and the software, allowing the control signals used for execution to be changed without breaking binary compatibility.

The instruction format exposed to software is also typically denser than the final control signals used to control execution. Typically not all possible combinations of control signals will be generated by valid instructions. For example, a very simple twos-complement adder supporting addition, subtraction, and addition with carry might have two control signals — one controlling whether one operand is inverted and the carry-in value is set to one, the other controlling whether the carry-in value is used. Both signals would be asserted for subtraction, neither for regular addition, and the second signal only for addition with carry. Asserting only the first signal would produce A plus one minus B, which is not a commonly useful operation.

In addition, naming a pipeline stage Decode is a conventional simplification. With a conventional RISC instruction encoding it is relatively easy to calculate the target of a PC-relative branch during decode because the immediate offset is a fixed field in the instruction and the PC is available. (Even if it is not known that the instruction is a taken branch early enough to allow enough time for the addition, the addition can be performed speculatively and the result ignored if the instruction is not a taken branch.) It may also be possible to evaluate branch conditions during this pipeline stage (the five-stage MIPS R2000 pipeline did this to only require a single branch delay slot to keep the pipeline full).

With a direct-mapped or way-predicted cache, the tag check can also be done in parallel with decode itself. (A cache miss or way misprediction would require the instruction to effectively be converted into a nop, but supporting modestly greater instruction cache latency might allow tradeoffs in the cache design.)

The Decode pipeline stage can also be used to detect various data and structural hazards relative to previous instructions and take mitigating actions (e.g., using result forwarding) or restraining actions (e.g., stalling the pipeline).

In a simple RISC pipeline, this stage also typically includes the reading of register operands (fixed register name positions make this independent of decode; this may involve unnecessary reads when the instruction only has one register operand but excess reads do not effect correctness). (In fact, for the 8-stage MIPS R4400 pipeline, the stage which decodes the instruction is named "Register Fetch". This stage decodes the instruction, detects interlock conditions, confirms a cache hit, and fetches register operands.)

(Such parallelism in instruction processing is not the only way that processing done during a pipeline stage may not be limited to the activity for which it is named. The division the sequential activities into pipeline stages does not have to map exactly to common conceptual divisions. For example, some of the latency of instruction cache access might be moved into the Decode stage (such that actual decoding cannot begin until some time into that stage). Similarly, some of the work associated with execution (e.g., the inversion of an operand for subtraction or the shifting of an operand by a small constant) might be hoisted into the Decode stage.)

Some processors store partially decoded instructions in the instruction cache. This can reduce the time (and potentially energy) required in the later decode at the cost of additional bits in the cache. Recent high-performance Intel and AMD x86 processors include a µop cache which stores essentially fully decoded operations, saving both time and energy and facilitating the providing of more µops per cycle.

# Answer
> 3 votes
The name "decoding" is actually a bit misleading because more things take place in this stage. You can view it as a translation from the external, programmer-visible representation of the instruction, to the CPU's internal interpretation.

All CPU architecture have an encoding of instructions, usually involving the specification of a number of op-codes specifying the "action" of the instruction (as opposed to the arguments, which might be registers, memory locations etc.). Note that the op-code is just a number, often just a byte. For instance, the addition instruction might have byte value 0x01, the subtraction might be 0x02 and so on. However, note that the numbering is somewhat arbitrary. It doesn't in itself say what the instruction does - this is something you would have to look up in the instruction manual.

What the decoding stage does is to map these numbers to the actual *action* of the instruction. This often involves looking up the OP-code in a data-structure, for instance a ROM. You could compare the decode stage to you looking up the op-code in a manual, to see what the instruction actually is. Now, your instruction manual is written in a human-readable language. What is the computer's manual written in? One method used in many implementations is that the ROM maps the op-code to a value which specifies the control signals that must be sent further into the execution pipeline to cause the action that is to be executed. For instance, if the instruction involves looking up the values of registers, adding them, and storing the result in another register, the ROM will contain values for the control signals that commands the register banks into read mode and the ALU into addition mode. The details of what the control signals are, are of course implementation dependent, depending on how the CPU internally functions and what control signals its various internal units accepts. However, the point is that the decode stage maps the representation of the instruction (in the form of op-code) to the actual action, in the form of these control signals. Note that on many architectures, one instruction might actually be decoded into several such "micro-instructions" with each micro-instruction essentially being a long word of all these control signals. This allows the architecture to provide the application programmer with complex instructions with short encoding. This generating and sequencing of micro-instructions might also take place in the decode stage.

Now you could ask, why not just let the instruction op-code contain all these control signals? In that case, the decode stage might not be necessary. Only problem is, that execution of an instruction often involves a lot of control signals, meaning instructions would be very long, just got the op-code. Also, it would expose the internal workings of the CPU since the external representation of instructions would now be deeply tied to the internal workings.

By the way, some architecture have very complicated encoding scheme so here the decoding involves a lot more work than just a lookup in a ROM, but in fact rather complicated logic just to determine the length and the prefixes etc. of the instruction. Also, various tricks might be necessary to keep the ROM at an acceptable size and also to allow fast look-up. On superscalar instructions, it is even possible to do this for several instructions in parallel even for encodings with variable length instructions! So as you can see, decoders can be pretty busy!

# Answer
> 2 votes
As you say, the instruction is in binary format, say 100100111001110000000111111010101000000000 (I did not actually check the number of bits). Can you execute it ?

Well, not so easy, if you do not have somewhere a description of the instruction set, including the CPU architecture, and how it is encoded in binary. You have to understand how this sequence of bits is organized, what specifies the instruction, what are the arguments or registers involved, and that may depend on the instruction. Once you have sorted that information, you pass control over to the specialized circuitry that is supposed to actually perform the instruction, say an addition, with the data or registers you have decoded. For a different instruction, it will pass control (and data) to a different circuitry.

It is like team games. There often is one guy whose role is to dispatch the ball to the most appropriate player, after decoding what the next step of the game should be. Well, this is a bit far fetched. In the CPU, there is a specific circuitry that does it: it decodes instructions.

# Answer
> 2 votes
Download a manual for a modern processor, for example here:

http://www.intel.com/content/www/us/en/processors/architectures-software-developer-manuals.html

Look at the instruction format. And then tell me with a straight face that you can just execute it. Just for fun, try to write a function that is given an array of bytes containing an instruction for in ia64 processor in 64 bit mode, and returns the length of the instruction in bytes. Enjoy the challenge.

But the real reason that the decoder is needed: Instruction sets have been designed years in the past, and as years go by, what seemed a good idea years ago isn't a good idea today. In a typical modern processor, the instructions as described in an instruction set manual are translated into quite different instructions that the processor actually executes. Some instructions are translated into pairs of processor instructions. Sometimes multiple instructions are combined into a single processor instruction. Sometimes instructions don't get executed at all (but the instruction decoder keeps track of their effect and adjusts following instructions).

This allows the maker of the processor to change the internal instruction set, without affecting any programs written for that processor.

---
Tags: computer-architecture
---


title: Why would anyone want CISC?

text:
# Question
Title: Why would anyone want CISC?
In our computer systems lecture we were introduced to the MIPS processor. It was (re)developed over the course of the term and has in fact been quite easy to understand. It uses a RISC design, that is its elementary commands are regularly encoded and there are only few of them in order to keep the wires simple.

It was mentioned that CISC follows a different philosophy. I looked briefly at the x86 instruction set and was shocked. I can not image how anyone would want to build a processor that uses so complex a command set!

So I figure there have to be good arguments why large portions of the processor market use CISC architectures. What are they?

# Answer
> 61 votes
There is a general historical trend.

In the olden days, memories were small, and so programs were perforce small. Also, compilers were not very smart, and many programs were written in assembler, so it was considered a good thing to be able to write a program using few instructions. Instruction pipelines were simple, and processors grabbed one instruction at a time to execute it. The machinery inside the processor was quite complex anyway; decoding instructions was not felt to be much of a burden.

In the 1970s, CPU and compiler designers realized that having such complex instructions was not so helpful after all. It was difficult to design processors in which those instructions were really efficient, and it was difficult to design compilers that really took advantage of these instructions. Chip area and compiler complexity was better spent on more generic pursuits such as more general-purpose registers. The Wikipedia article on RISC explains this in more detail.

MIPS is the ultimate RISC architecture, which is why it's taught so often.

The x86 family is a bit different. It was originally a CISC architecture meant for systems with very small memory (no room for large instructions), and has undergone many successive versions. Today's x86 instruction set is not only complicated because it's CISC, but because it's really a 8088 with a 80386 with a Pentium possibly with an x86\_64 processor.

In today's world, RISC and CISC are no longer the black-and-white distinction they might have been once. Most CPU architectures have evolved to different shades of grey.

On the RISC side, some modern MIPS variants have added multiplication and division instructions, with a non-uniform encoding. ARM processors have become more complex: many of them have a 16-bit instruction set called Thumb in addition to the “original” 32-bit instructions, not to mention Jazelle to execute JVM instructions on the CPU. Modern ARM processors also have SIMD instructions for multimedia applications: some complex instructions do pay after all.

On the CISC side, all recent processors are to some extent RISC inside. They have microcode to define all these complex macro instructions. The sheer complexity of the processor makes the design of each model take several years, even with a RISC design, what with the large number of components, with pipelining and predictive execution and whatnot.

So why do the fastest processors remain CISC outside? Part of it, in the case of the x86 (32-bit and 64-bit) family, is historical compatibility. But that's not the whole of it. In the early 2000s, Intel tried pushing the Itanium architecture. Itanium is an extreme case of complex instructions (not really CISC, though: its design has been dubbed EPIC). It even does away with the old-fashioned idea of executing instructions in sequence: all instructions are executed in parallel until the next barrier. One of the reasons Itanium didn't take is that nobody, whether at Intel or elsewhere, could write a decent compiler for it. Now a good old mostly-sequential processor like x86\_64, that's something we understand.

# Answer
> 16 votes
The x86 instruction set is a bit of a special case. I think that Motorola's 68K and DEC's VAX are somewhat better examples of CISC. In the days of a lot of assembly-language code, people thought that a very regular, very inclusive ISA was better: I believe they called the difference between assembly code and the way people thought the "Semantic Gap". Theoretically, you wanted an instruction set that matched the way you thought.

The other big design driver for CISC seems to be "orthogonality": every instruction would work with every addressing mode (register, absolute address, relative offset, etc etc). You can see the bogey man of orthogonality show up in API design in Distributed Computing Environment (DCE) and in CORBA. That idea isn't limited to instruction set design.

# Answer
> 7 votes
One reason for CISC was to have dense encoding for instructions (memory was *expensive*). The whole RISC idea was to speed up the CPU by fetching the same size instructions all the time (no complex, slow "figure out instruction size" step), have them do simple things (so it is fast to figure out what to do). Memory was cheap. This freed circuitry area on the CPU for other stuff (more registers, more processing units so several instructions could be done in parallel if they were independent). As the CPU was much slower than RAM, this paid off. But CPUs got faster (and did more in parallel, and ...) while RAM didn't get faster (at least not at the same rate than the CPU's consumption of data due to increased parallelism). Meet cache memory, fast as the CPU but small. So now memory is at a premium again, not for cost reasons but for speed. CISC revival time. Meanwhile, CPUs got more complex, to the point that today's microprocessor does much of what a RISC compiler did: Break down operations into elementary parts, reorder internal RISCy instructions so they can be done concurrently whenever possible. RISC was badmouthed as "Relieve Important Stuff to Compiler" for a reason...

# Answer
> 5 votes
The real advantage of CISC is reduced memory and cache pressure and that alone makes it better for demanding high performance applications since a major bottleneck in such systems is the memory bandwidth. Given equally sized cache memory, CISC processors can describe more information than RISC. Also, since CISC instructions involve several micro-operations, architectural improvements may be possible that may provide the fastest execution path for that instruction that writing out individual instructions could ever provide. In short, CISC processors are more efficient at utilizing memory bandwidth which often translates to performance gains for memory intensive applications.

For example, to perform `R1 = R2 + R3 + R4 + R5 + R6` and push the result onto stack, say the RISC code is written out as,

```
ADD  R1, R2, R3 (4-byte)
ADD  R1, R4, R5 (4-byte)
ADD  R1, R6, R0 (4-byte, R0=0)
PUSH R1         (4-byte)

```

and as such requires 16-bytes of space.

Coming to CISC, due to the possibility of different styles of encoding, the same information may be represented as follows...

```
ADD R1, R2, R3 (4-byte)
ADD R1, R4, R5 (4-byte)
ADD R1, R6     (2-byte)
PUSH R1        (1-byte)

```

which takes only 12 bytes of memory. Thus, memory utilization is improved allowing the processor to see more instructions and thus reduce idle cycles.

# Answer
> 2 votes
An important aspect that no one has brought up thus is that almost all CISC CPUs are microcoded architectures. A microsequencer and a control store consume far less real estate than a hardwired controller, and the instruction set can be modified without modifying the hardware.

Microprocessors were novelty devices when I entered the field. A very common practice back in the seventies and early eighties was to assemble a CPU using bit-slice ALUs, a microsequencer-based control unit, and a control store into which the microcoded instruction set was either loaded or blown. These computers were based on 7400 series transistor-transistor logic (TTL). The 78181 4-bit ALU was used to construct a lot of processors, including the DEC PDP-11 and early VAX 11 computers, the Data General Nova, Xerox Alto, and the Wang desktop computer.

# Answer
> 2 votes
You will have a hard time finding any desktop computer that isn't using an x86 compatible processor. That instruction set has beaten MIPS, it has beaten Sparc, it has beaten Alpha, it has beaten Titanic (I may have spelled that name wrong). MIPS on the other hand is barely existing today. So no matter what you think today, very clever people thought that the x86 instruction set was a really good idea, and they have made a ton of money with it.

Computers started as RISC because a complex instruction set was just beyond the abilities of implementors. If you want to see a RISC instruction set, look at the CDC 6400-6600 and CDC Cyber 170-175 instruction set. That's proper RISC. About 10 years ago I asked some chip designers how much space that would require (in the corner of a reasonable advanced GPU chip). They told me about 1mm2 - including the machine's RAM, which would take 99% of that space.

When people *could* build CISC machines, they were actually at an advantage. Remember that x86 was released long before MIPS, 1978 vs. 1985. At that time you needed processor cycles for reading instructions, decoding them, performing them. MIPS in 1978 would have taken four cycles per instruction, and per operation. If you take an x86 instruction like "add register to memory", that would take maybe 7 cycles for the instruction, but performing 3 operations. That was a major advantage. And the more different instructions you have, and the more powerful each instruction, the greater the advantage.

And when the x86 64 bit instruction set with its nightmarish prefix codes was developed, the complexity of the instruction set didn't matter anymore. CISC nowadays is just translated into RISC, and the whole translation business is maybe one percent of the chip.

# Answer
> 1 votes
This question has a lot to do with very recent trends in computing that favor a massive shift to mobile and tablet computing, thereby favoring RISC cpus, and has caught Intel (probably worlds largest CISC purveyor) at a disadvantage in a so-called "inflection point" exactly like the kind Grove drew attention to and warned of. The short story is that CISC seems to be starting to melt away under the massive paradigm-shifting/gamechanging onslaught of mobile computing because of its apparently intrinsically high energy consumption.

CISC will presumably always be around on the desktop but mobile is widely regarded as the new future of computing. Many developing countries (with large potential computer-using populations) will actually largely skip the desktop phase. See, for example, Rise and Fall of desktop computing

An excellent case study of this question is to read about Mike Bell who is working for Intel in a new position attempting to position Intel better in the mobile market via the Atom CPU via a "skunkworks"-like project/initiative, with very strong executive support. The mobile market is highly tightly coupled to RISC architecture, and mainly ARM processors, due largely to their high energy efficiency (power consumption), a new key criteria for computing which the question & no other answers mention. Here are two recent articles along these lines that reveal a lot of the internal corporate thinking (and ensuing scramble!) on the subject:

# Answer
> 1 votes
A factor not mentioned in other answers is economic. It is also about Intel. The CISC architecture is largely represented by the x86 and x64 families. These all descend from the humble 8088 used in the original IBM PC. The early market dominance of that series of computers meant that Intel had a solid revenue stream for R&D. Coupled with the fact that Intel was able to curb competition by reneging on/canceling it's second source agreements meant the CPU prices could rise to extreme levels ensure very rich gross profit margins.

Thus while other CPU manufacturers struggled to keep pace, Intel was able to pour billions of dollars into developing newer, faster products. The RISC competition could not spend nearly that much money. Many RISC processors went off the market. Some were:

DEC Alpha, Fairchild Clipper, AMD 29000, SPARC, MIPS, POWER (for PC use), Hitachi SuperH...

I recall pundits of that era announcing that the RISC vs CISC war was over and CISC had won. It had not. It just outspent everybody else.

Can this dynamic ever change? It already is. No economic advantage is absolute.

The one Achilles heel of the x86 is it's voracious appetite for power. This has allowed a smaller, more nimble competitor (ARM) to thrive in markets (like phones/tablets/etc) where energy thriftiness mattered.

A great video about this from a member of the ARM team is ARM Processor - Sowing the Seeds of Success - Computerphile at around 8:30

The second problem for x86 is the success of Intel's strategy. They managed to eliminate almost all competition. They slowed down. For years now, new Intel processors have delivered only very modest improvements. Worse still, super rich margins are a tough diet to give up for any corporation.

Today, ARM based Systems on Chip (SOC) and competing x64 chips from AMD are again making the CPU market an interesting place. (IMHO)

# Answer
> 0 votes
There are many reasons one would choose to implement a CISC. The most prominent reason is for binary compatibility with an existing CISC instruction set. While software binary translation technology has improved, hardware-based compatibility has some technical advantages (as well as the disadvantage of less translation caching) and the less technical advantage of seeming more reliable.

Code density is perhaps the second most significant reason for choosing CISC. The Renesas RX was designed as a CISC specifically for code density as it targets microcontrollers where code memory size is a significant cost factor. Variable length instructions, complex instructions (mainly more addressing modes), implicit operands, and lower register count all benefit code density.

An historical (and in my opinion misguided) reason for choosing CISC was to close the semantic gap between programmers using a higher level language and the processor. Since complex instructions can generally be replaced by a sequence of simpler instructions, the complexity of a higher level language compiler for a RISC need not be much more complex than for a language-matching CISC. RISC avoids "semantic clash" (where a processor instruction does more or less work than a corresponding language statement) and facilitates strength reduction and scheduling optimizations. (See "What are the tradeoffs in compiler development effort related to CISC vs. RISC?" for more details.)

There can be a significant fixed cost associated with executing an instruction. This encourages the use of relatively complex instructions to spread this overhead over more actual work; reducing the dynamic instruction count can improve performance. When the cost of logic and RAM was much greater than the cost of ROM, the incentive for complex instructions was significant since an instruction was decoded by looking up microcode.

A reason to use CISC that is perhaps contradicted by historical evidence is that microcode can be optimized for each microarchitecture whereas standard libraries may be slow to exploit features of a new implementation. The optimization level of software implementations of memcopy versus that of the microcode for REP MOVSB implies that libraries can get more attention than microcode. Part of this may come from the processor vendor targeting a broader user base so justification of effort may be more difficult compared to open source or internal software where localized interests of developers or users can bias implementation effort.

Being able to ship an optimized standard library with the processor does have significant attractions. The storage and execution of a platform standard library can be significantly optimized by software-hardware codesign. The distinction between a complex instruction and a Platform Abstraction Layer call can be subtle (or non-existent). A RISC design could use the same implementation techniques for handling PAL calls as a CISC does for complex instructions, including using operations not provided in the general instruction set with specialized hardware, using clever caching and decoding, and specifying register operands (though a CISC would often use dedicated registers similar to a per-function ABI). The mental model associated with CISC can encourage such optimizations. In addition, users may be less offended by the forced inclusion of a "hardware" standard library (CISC) than by forced inclusion of a specific PAL library.

Decoding relatively complex instructions can have less overhead (and possibly more reliably be correct in discerning intent) than the comparable RISC technique of idiom recognition where a sequence of instructions is recognized as a semantic unit. This overhead difference would be most noticeable in a smaller implementation, but the overhead to use this information reduces the significance of the decode savings.

Additional contextual information can facilitate hardware optimization. For example, when incrementing a value in memory, hardware could recognize that the memory address is used twice (for the load and the store) providing an opportunity for cache way memoization and translation caching. Complex instructions can provide such information explicitly. In a complex instruction, intermediate values have an explicit lifetime (that of the instruction); with a traditional RISC register values must be explicitly overwritten to indicate the end of liveness. (Note: A RISC could specify a register which is always zeroed after each use, providing a means to specify a single-use temporary value. Such instructions would be moderately more complex.)

If implementation details are not hidden behind an abstraction layer, it becomes more difficult to use different microarchitectures to optimize for different tradeoffs. Exposing microarchitectural details as architectural guarantees locks the microarchitecture into the compatibilty guarantee. While PAL software could be optimized the same as complex instructions, such requires hardware-software codesign. Organizational separation and diversity make codesign more difficult.

Complex instructions can provide guarded access to privileged state. For example, complex instructions are often atomic with respect to interrupts. While a RISC instruction set could provide a user-level mechanism to temporarily suspend interrupts, possibly even something like linked-load so that software explicitly retries the operation if interrupted, providing such is not typical for RISCs.

Similarly, a complex instruction could provide controlled access and/or use of privileged information. Because the executed operation has controlled semantics, actual privilege violation can be avoided. RISC-oriented alternatives include PAL code (which typically has significant overhead) and masked access to configuration registers (or shadow copies of registers) that have some privileged state. Providing a general solution (RISC) is more difficult than providing a solution to one or a few special cases (CISC), but is more powerful and less vulnerable to accumulation of special cases. If one believes that the important special cases are few, CISC can be more attractive.

Complex instructions can also hide state from software. One prominent advantage of such would be for context saving and restoring. With instructions that save and restore state, the architecture only needs to communicate the context size to the OS not the specific mechanisms for transferring state to memory. This allows applications running on a legacy OS to use ISA extensions which add state. (Again, PAL software could provide the same functionality.)

---

Much of the complexity of x86 comes from compatibility across many extensions. With complex and less orthogonal instructions (useful for code density), removing some work that turned out not to be commonly needed, avoiding unnecessary dependency chains (e.g., only one carry bit, only one dynamic shift amount register), adding some work that turned out to be commonly used and that can be optimized within the complex instruction — any of these would require adding a new instruction and making the ISA less aesthetically pleasing.

In many cases a RISC would not encounter such issues because instructions are highly orthogonal and primitive. In some cases a RISC might need to add new primitives but such would typically be applicable to more than one use.

In addition, once the infrastructure is in place to support complex instructions, the barriers are reduced for additional complex instructions. That is, much of the cost of complex instructions in non-recurring. Strongly RISC ISAs suffer a complementary hinderance to introducing CISCy features.

The frequency of extension of x86 may also be partially attributed to its popularity for general-purpose computing and the merchant processor model (these also increase the importance of binary compatibility). RISC ISAs have often been tied to sysem vendors which encourages a narrower focus on applications and the lack of competition for implementations of a specific RISC ISA somewhat discourages the use of instruction set extensions for marketing. Popularity also makes the cost of developing new extensions less significant (non-recurring expenses are less important at higher volume).

The x86 compatibility philosophy probably also biases toward extending existing mechanisms rather than providing a more clean break which means that new features are more influenced by existing features. Higher frequency of extension also encourages more incremental changes, which encourages reusing mechanisms, tending to reduce orthogonality.

Comparing an academic presentation of classic MIPS (which is a subset of modern versions of MIPS and excludes various optional ISA extensions) to modern x86 (which traces binary compatibility back to the 16-bit 8086 and assembly-level quasi-compatibility even further back) with all its historical baggage does not present the best case for CISC nor a realistic case for RISC.

# Answer
> -1 votes
Simply before there were Reduced Instruction Set Configurations there were Instruction Set Configurations. They have their applications. particularly in very large memory block transfers with high capacity chipsets, which would only need 4-16 bytes to transfer an entire video page, instead of an long for ever loop. that is changing and RISC is becoming the status quo as chip sets are becoming more sophisticated, like the incredible GPU's found in the high end video cards.

# Answer
> -2 votes
CISC cpu has more advantages than RISC. Because CISC use less hardware register and XNOR/XOR gates than RISC many times!!!! Imagine the instruction bytes in CISC will be executed-sequence, there is only one logic gate and register is used. If 1 bilion transistors can produce about 300 million logic gates, so you can process 300 milion operators or processes (IF, equal, mathematic, variable, addressing... etc) and more program can run in CISC. But in RISC, it takes dozen times of logic gates for running a program in pipelined design. So 300 milion x 50 times (50 instructions) + 15000000000 bit counters!!! in so-called RISC. CISC use more hardware to reduce software algothrim which slow down the cpu.

---
Tags: computer-architecture
---


# Question
Title: What happens if the associativity level is greater than the cache size?
I am working on a computer organization caching problem
**The Problem:** What happens if the associativity level is greater than the cache size?

I know that associativity level is how many blocks are in a set. Say we have a 16 way set associative cache and a cache size of 15. What would happen? Would the cache break or would it turn into a fully associative cache(1 set)

# Answer
> 1 votes
Since the associativity is equal to the number of cache blocks in a set, in a traditional cache design there is no sensible interpretation of having associativity greater than capacity; a set cannot have more cache blocks than are in the entire cache.

Having more tags than full-sized blocks in a set can make sense.

If the data in a block can be compressed (possibly in a lossy manner), then data from multiple blocks may fit in the storage provided in a single block. In this case having more tags than uncompressed cache blocks allows such compressed data to be cached and indexed normally. For example, with twice as many tags, a 64-byte cache block compressed to 24 bytes and one compressed to 40 bytes could fit into a single 64-byte storage (with some metadata overhead beyond just the extra tag).

Related to compression, extra tags can also be used to facilitate use of large cache blocks with sectors allocated to different tags. For example, each tag could include a full set of valid bits for all subblocks (sectors) in a cache block, reducing the tag overhead (a valid bit is smaller than a tag) at the cost of less effective allocation. This was proposed for off-chip DRAM caches with on-chip SRAM tags (i.e., limited tag storage budget relative to cache capacity).

Extra tags can also be used to reduce back invalidation in a cache that is tag-inclusive of another cache. Tag inclusion allows the inclusive cache to be probed and avoid accessing the included cache unless the data is present there (this is a form of snoop filtering), but a replacement in an inclusive cache that victimizes an entry shared in the included cache forces the block to be removed (back invalidation) from the included cache to maintain the inclusion property.

Extra tags can also be used to improve replacement policy by keeping a record of recent victims. For example, on a tag hit but data miss, the block might be allocated with a "sticky" bit set that would be unset when the block would normally be evicted using the standard (LRU-oriented) replacement policy (this is not the best replacement policy helped by extra tags but it is a clear example).

Similarly, extra tags might be used to improve prefetch accuracy. For example, a proposed prefetch to an address that is a tag hit is more likely to be used than one that is a tag miss.

Extra tags can also be used in decoupling indexing of tags and storage of data. For example, Moinuddin K. Qureshi et al.'s "The V-Way Cache : Demand-Based Associativity via Global Replacement" proposes using twice as many sets as a cache of the capacity and associativity would normally have. This has the benefit of reducing conflict misses under a constant number of tag comparisions because generally some blocks would be allocated to the alternate set that would map to a single set normally (the number of currently used ways in a set can vary). This excess associativity also allows global replacement with full utilization of data storage capacity; if the capacity was equal to the product of associativity and number of sets, then an victimized block (invalidated tag) would mean fewer valid tags than data storage blocks.

---
Tags: computer-architecture, sets, memory-management, cpu-cache, memory-access
---


# Question
Title: Why do we have to trade abstraction for speed?
Why can high-level languages seemingly never reach lower-level languages in terms of speed? Examples of high-level languages would be Python, Haskell, and Java. Low-level languages would be trickier to define, but let's say C. Comparisons can be found all around the Internet$^1$ and they all agree that C is a lot faster, sometimes by a factor of 10 or more.

**What is it that causes such big difference in performance and why can't high-level languages catch up?**

Initially I believed that this is all the compilers' fault and that things will improve in the future, but some of the most popular higher-level languages have been around for decades and they still lag behind when it comes to speed. Can't they simply compile to a similar to C syntax tree and then follow the same procedures that generate the machine code? Or perhaps it's something to do with the syntax itself?

---

$^1$ Examples:

# Answer
> 21 votes
## Debunking some myths

1. There is no such thing as a fast langauge. A language can generally produce fast code, but different languages will excel on different benchmarks. We can rank languages on a particular set of flawed benchmarks, but cannot rank languages in a vacuum.
2. C code tends to be faster because people who need every inch of performance use C. A statistic that C is faster "by a factor of 10" might be inaccurate, because it might be that the people using Python just don't care as much about speed and didn't write optimal Python code. We see this in particular with languages like Haskell. If you try *really hard*, you can write Haskell that performs on par with C. But most people don't need that performance, so we have a bunch of flawed comparisons.
3. Sometimes, it is unsafety, not abstraction, that makes C fast. Its lack of array-bounds and null-pointer checks save time, and have been the cause of numerous security holes throughout the years.
4. Languages aren't fast, implementations are fast. Many abstract languages start slow, because speed is not their goal, but get faster as more and more optimizations are added.

The abstraction vs speed tradeoff is perhaps inaccurate. I would suggest a better comparison:

## Simplicity, speed, abstraction: Choose two.

If we're running identical algorithms in different languages, the question of speed comes down to the problem of "How much stuff do we need to do at runtime to make this work?"

In a highly abstract language *that is simple*, such as Python or JavaScript, because we don't know about the representation of data until runtime, there end up being lots of pointer de-referencing and dynamic checks happening at runtime, which are slow.

Likewise, there are a lot of checks that need to be done to ensure that you don't wreck your computer. When you call a function in python, it needs to make sure that the object you're calling actually is a function, since otherwise you could end up executing random code that does terrible things.

Finally, most abstract languages have overhead from garbage collection. Most programmers have agreed that having to track the lifetimes of dynamically allocated memory is a pain, and they'd rather have a garbage collector do it for them at run time. This takes time, that a C program doesn't need to spend on GC.

## Abstract Doesn't mean slow

However, there are languages which are both abstract and fast. The most dominant in this era is Rust. By introducing a borrow checker and a sophisticated type system, it allows for abstract code, and uses compile-time information to reduce the amount of work that we need to do at runtime (i.e. garbage collection).

Any statically typed language saves us time by reducing the number of runtime checks, and introduces complexity by requiring us to please a typechecker at compile-time. Similarly, if we have a language that encodes whether a value can be null into its type system, we can save time with compile time null-pointer checks.

# Answer
> 3 votes
By its nature abstraction reduces the communcation of information, both to the programmer and to the lower layers of the system (the compiler, libraries, and runtime system). In favor of abstraction, this generally allows the lower layers to assume that the programmer is not concerned with any unspecified behavior, providing greater *flexibility* in supplying the behavior that is specified.

An example of a potential benefit from this "don't care" aspect is in data layout. In C (low abstraction), the compiler is more constrained in data layout optimizations. Even if the compiler could discern (e.g., through profile information) that hot/cold or false-sharing-avoidance optimizations would be beneficial, it is generally prevented from applying such. (There is some freedom in specifying "as if", i.e., treating the specification more abstractly, but deriving all the potential side effects adds a burden to the compiler.)

A more abstract specification is also more robust against changes in tradeoffs and uses. The lower layers are less constrained in reoptimizing the program for new system characteristics or new uses. A more concrete specification must either be rewritten by a programmer or additional effort must be made by the lower layers to guarantee "as if" behavior.

The performance hindering aspect of information hiding abstraction is "can't express", which the lower layers will typically handle as "don't know." This means that the lower layers must discern information useful for optimization from other means such as typical general use, use targeted by the language or library, or specific profile information.

The impact of information hiding works in the other direction as well. The programmer can be more productive by not having to consider and specify every detail, but the programmer may have less information about the impact of higher level design choices.

On the other hand, when code is more specific (less abstract), the lower layers of the system can more simply do what they are told to do as they are told to do it. If the code is well-written for its targeted use, it will fit its targeted use well. A less abstract language (or programming paradigm) allows *the programmer* to optimize the implementation by detailed design and by the use of information which is not easily communicated in a given language to the lower layers.

As has been noted, less abstract languages (or programming techniques) are attractive when additional programmer skill and effort can produce worthwhile results. When more programmer effort and skill are applied, results will typically be better. In addition, a language system which is used less for performance-critical applications (instead emphasizing development effort or reliability — bounds checks and garbage collection are not just about programmer productivity but about correctness, reducing via abstraction the mental load on the programmer can improve reliability) will have less pressure to improve performance.

Specificity (lower abstraction) also works against the principle of don't repeat yourself, but tailoring code to a specific use is a common optimization technique. This reduced abstraction has obvious reliability and programming effort implications.

The abstractions provided by a language may also include undesired or unnecessary work with constrained ability to choose a less heavyweight abstraction. While unnecessary work can sometimes be discovered and removed by the lower layers (e.g., bounds checks may be extracted from the body of a loop and entirely removed in some cases), determining that such is a valid optimization requires more "skill and effort" by the compiler.

Language age and popularity are also noteworthy factors both in availability of skilled programmers and the quality of the lower layers of the system (including mature libraries and code examples).

Another conflating factor in such comparisons is the somewhat orthogonal difference between ahead-of-time compilation and just-in-time compilation. While just-in-time compilation may more easily exploit profile information (not relying on the programmer to provide profile runs) and system-specific optimization (ahead-of-time compilation may target broader compatibility), the overhead of aggressive optimization is accounted as part of the runtime performance. JIT results can be cached (reducing the overhead for commonly used code) but typically not persistently.

For ahead-of-time compilation, binary reoptimization can provide some advantages of JIT compilation, but traditional binary distribution formats drop most source-code information potentially forcing the system to attempt to discern intent from a specific implementation.

(Install-time compilation/finalization is an intermediate choice with intermediate trade-offs.)

Lower abstraction languages, because of their emphasis on programmer control, favor the use of ahead-of-time compilation. Install-time compilation might be tolerated, though link-time implementation selection would provide greater programmer control. JIT compilation sacrifices significant control.

There is also the issue of benchmarking methodology. Equal effort/skill is effectively impossible to establish, but even if such could be achieved the language goals would bias the results. If a low maximum programming time was required, a program for a less abstract language might fail even to be completely written compared to a simple idiomatic expression in a more abstract language. If a high maximum programming time/effort was allowed, lower-abstraction languages would have an advantage. Benchmarks presenting best-effort results would naturally be biased in favor of less abstract languages.

It is sometimes possible to program in a less idiomatic manner in a language to gain the advantages of other programming paradigms, but even when the expressive power is available the tradeoffs for doing such may not be favorable.

# Answer
> 1 votes
here are a few key ideas on this.

* an easy comparison/ case study to make wrt abstraction vs speed is java vs c++. java was designed to abstract away some of the lower-level aspects of c++ such as memory management. in early days (around the invention of the language mid 1990s), java garbage detection was not very fast, but after a few decades of research, the garbage collectors are extremely finetuned/ fast/ optimized, so the garbage collectors are largely eliminated as a performance drain on java. eg see even this 1998 headline: Performance tests show Java as fast as C++ / javaworld
* programming languages and their long evolution have an inherent "pyramidal/ hierarchical structure" as a sort of transcendant design pattern. at the top of the pyramid is something that controls other lower sections of the pyramid. in other words, building blocks are made out of building blocks. this can be seen in API structure also. in this sense, greater abstraction always leads to some new component at the top of the pyramid controlling other components. so in a sense its not so much that all the languages are level with each other, but that languages call upon routines in other languages. eg a lot of scripting languages (python/ ruby) often call C or C++ libraries, numerical or matrix routines are a typical example of this. so there are higher level and lower level languages and the high level languages call lower level languages so to speak. in this sense measuring relative speed is not really comparable.
* one might say that new languages are being invented all the time to try to optimize the abstraction/ speed tradeoff, ie its key design goal. maybe its not so much that greater abstraction always sacrifices speed but that a better balance is always being sought with newer designs. eg Google Go was in many ways specifically optimized with the tradeoff in mind, to be simultaneously both high-level and performant. see eg Google Go: Why Google’s programming language can rival Java in the enterprise / techworld

# Answer
> 0 votes
The way I like to think about performance is "where the rubber meets the road". The computer executes instructions, not abstractions.

What I want to see is this: is every instruction that is executed "earning its keep" by contributing substantially to the end result? As a too-simple example, consider looking up an entry in a table of 1024 entries. That is a 10-bit problem because the program has to "learn" 10 bits before it knows the answer. If the algorithm is binary search, every iteration contributes 1 bit of information, because it shrinks the uncertainty by a factor of 2. So it takes 10 iterations, one for each bit.

Linear search, on the other hand, is initially very inefficient because the first iterations shrink the uncertainty by a very small factor. So they are not learning much for the effort expended.

OK, so if the compiler can allow the user to wrap good instructions in a way considered "abstract", that's fine.

---
Tags: programming-languages, performance
---


# Question
Title: Is automatic multicore support at the hardware or compiler level possible?
Due to technical constraints, single thread performance has been increasing more slowly and adding cores has been adopted to offer greater potential increase in performance.

However, multicore support currently appears to require the programmer to manually divide the work, control communication/synchronization, etc. For many processor intensive games and simulations (such as DCS), such complicated multithreading effort has been limited, and these programs depend extremely heavily on single thread performance.

Could a processor with multiple cores divide the work automatically?

Alternatively, could a compile convert single-threaded code to mulithreaded code? In the current world, multicore support has to be done by hand as far as I know, with a result being that many processor intensive games and simulations (such as DCS) depend extremely heavily on one CPU core to avoid complicated multithreading.

# Answer
> 1 votes
The short answer: yes it's possible, but right now it generates slower code.

The long answer: the thing to keep in mind here synchronization. Computation is not just a bunch of independent computations. The results of one computation are used in other ones. Sometimes the order doesn't matter, and sometimes it does.

Take for example, some hard to evaluate function $f$. If we want to compute $f(f(10) + f(20))$, we can evaluate $f(10)$ and $f(20)$ in parallel, but we can't evaluate the final result until we've done the two inner evaluations and added them together.

This process of making sure things happen in the right order is called synchronization. There are many ways to ensure synchronization happens and that the code produces the same result even if some operations are moved around.

There are many models of concurrency: some have shared memory with locks on variables, some have totally separate processes that pass messages. But in every model, the synchronization carries some overhead. Acquiring a lock, sending a message between processes, each of these adds time that wouldn't be required if you evaluated the code sequentially.

Likewise, scheduling causes some overhead. If you have 200 processes and only 8 cores, you will probably be slower than if you have, say 20 processes and 8 cores, since you have to do a lot more work scheduling, but don't get additional parallelism.

The key, then, is to adjust the "granularity" of your concurrency. Too coarse and you don't make use of all the processors, but too fine and you get too much overhead from synchronization and scheduling.

This sort of analysis is hard, and right now compilers don't do it well enough to make general code faster, but I suspect with heuristics, and maybe even a bit of AI/machine learning, in the future we'll be able to automatically adjust the granularity automatically.

I'm not a hardware person, but my guess is that computing these sorts of things are way too complicated and time-consuming to be done on-the-fly at the CPU level.

At a compiler level, it's possible, but depends on your language constructs. I'm fairly certain finding the "optimal" parallelization of a program is undecidable, since you can probably construct some example where you can parallelize a program iff an arbitrary program halts.

However, like most program analyses, we can do "safe" approximations. In particular, there has been interesting research into automatically parallelizing "pure" functional languages like Haskell. When any side-effects of a function are captured by the type system, it's a lot easier for the compiler to know what operations can safely be performed in parallel. But to my knowledge, none of these efforts have succeeded so far in producing fast code.

# Answer
> 0 votes
Automatic parallelization of software (at the source code level down to the hardware level) has been actively researched and in some areas has achieved significant speed-ups. This effort can roughly be divided into three types: compiler autoparallelization, parallel runtime systems/libraries, and speculative multithreading.

Compiler autoparallelization currently is most effective on easily parallelized (e.g., vector-heavy) code. The Intel compiler's autoparallelization is able to substantially improve performance of the SPEC CPU2006 subbenchmark 462.libquantum (effectively breaking the benchmark as a measure of single thread performance). For example, this 36-core system has a 1.55x speedup (for 2.25x more cores) relative to 403.gcc (the least broken SPEC CPU2006 subbenchmark) compared to this 16-core system. This is nearly a 69% parallelization efficiency. Since the 36-core processor had 12.5% higher turboboost frequency (applied to 403.gcc but not 462.libquantum), the compiler actually achieved higher parallelization.

Compiler autoparallelization faces similar difficulties to compiler autovectorization in discovering the potential parallelism and expressing it in a manner that does not substantively change program semantics and is likely to improve performance. (Interestingly, recent x86 SIMD extension implementations have introduced warm-up and cool-off overheads somewhat conceptually similar to thread initialization overheads.) Processors ability to exploit unused power/thermal budget to increase clock frequency (e.g., Intel turboboost) makes the performance tradeoff more complex; a modest speed-up from parallel execution can result in a net slowdown due to lower clock frequency. Shared resources other than power/thermal budget can also bottleneck performance.

Runtime systems and libraries can also provide some support for parallel execution. A simple example of this is parallel garbage collection; simply by changing the run-time system or library, parallel execution (in a very limited context) can be provided. While such parallelization opportunities are generally limited and do not apply to the application code itself, the benefit is not insignificant.

Speculative multithreading, whether provided by hardware, by a software run-time system, or by some combination of these, can speculatively execute loop iterations and even function calls in parallel. Speculative execution has the advantage of being able to use parallelism that cannot be staticly guaranteed to be dependency-free by the compiler. While significant work has been done in this area, substantial research and development remains before significant adoption is practical.

Hardware support can substantially reduce the cost of conflict detection and thread activation. Versioned memory could provide multithreaded benefits similar to those register renaming provides for out-of-order execution (reducing name dependencies and facilitating roll-back after wrong speculation).

Before it was bought by Intel, Soft Machines was developing what it called VISC, which transparently translated single-threaded binaries to run on multiple cores with a different ISA. This February 2016 AnandTech article provides some information on VISC.

### Side Note: Making Parallel Programming Easier

Obviously, if a compiler can seek opportunities for parallelization, it could also provide feedback to the programmer about cases where the compiler could not autoparallelize but might be able to do so with modest changes to the source code. Just as performance tuning tools have improved for single-threaded code, it should be expected that performance tuning (and correctness checking) tools for multithreading should improve, even if more gradually.

Hardware mechanisms such as hardware transactional memory can make some aspects of multithreaded programming easier. Transactional memory simplifies locking by facilitating the use of coarser-grained locks. Hardware transactional memory is still very young, so there is likely significant potential for improvement is hardware implementation and software use. Reducing the cost of system calls and interprocessor interrupts (or interprocessor procedure call) could make irregularity of work availability less problematic by reducing the cost of activating a thread. Faster handling of buffer-based inter-thread communication could increase the performance of simpler pipeline-based parallelism (e.g., instead of the reader pulling from the writer on demand, buffer writes could be pushed closer to their consumer).

Languages and libraries (as well as programmer education and hardware availability) are also likely to *slowly* make multithreaded programming easier and more common for performance-constrained software.

---
Tags: parallel-computing
---


# Question
Title: Are hardware specs relevant in software performance comparisons?
I notice occasionally in blogs or articles comparing different languages, algorithms, etc. that the author will divulge info about the processor used in the testing. Is this meaningful?

Shouldn't the relative performance differences be hardware-agnostic? That is, if Language A executes in twice the time as Language B, shouldn't that roughly persist no matter the hardware?

# Answer
The answer to your question is much dependent on specifics.

I certainly agree with D.W. answer that for comparing performances of complex systems, you need at least that kind of information (hardware specs), if you are interested in software performance through blackbox measurements. If box A has CPU, memory and disks that are twice as fast as box B, while being otherwise identical, it is clear that the same program will run twice as fast on A than it does on B. So if you compare two programs, one running on A and the other on B, you have to be aware of that.

However, the information you get from blackbox testing is very limited. For one thing, you may have a faster CPU, but a slower disk. Then, it is much harder to compare two software variants,

Generally the observed performance depends on very many factors that are hard to identify, and hardware specs may be grossly insufficient. Among other factors you have the quality of the algorithms used, the quality of the programming, the quality of the compiler (optimizing or not), the bias of the benchmark used, and probably some more.

Then the techniques for comparing a system (say a word processor), for comparing language implementations and for comparing algorithms may be quite different, due to complexity and also to formal definibility.

My personal opinion is that comparison of algorithms should, as much as possible, not be hardware dependent. If possible, it should use formal *cost analysis*, but that is not always simple to achieve. Short of doing that, it should be based on benchmarking on a virtual machine with appropriate primitives, so that the virtual machine can count precisely the number of instructions of each type executed. Of course that leaves the implementation quality bias and the benchmark bias, but the process is formal enough to be disputable on objective grounds. And the results are sometimes surprising.

It is to be noted that I refer here to *cost analysis*, rather than *asymptotic complexity analysis*. *Asymptotic complexity analysis is cost unit independent* and can only measure computational cost scaling with input size, i.e. compare an algorithm with itself as input changes. But comparing two algorithms, or two algorithm implementations, requires defining common computational unit(s), which implies a precisely defined common computational framework (as discussed also in this answer). A common virtual machine seems the right way to do it.

Regarding more complex software, I know of cases where the benchmark bias plays an important role. I have a friend who participates in natural language parsing competitions, and his technology is clearly put at a disadvantage by the way the benchmarks are provided (though that is by no means intentional). Implicit assumption in benchmark creation can play an important role. And this has nothing to do with harware specs.

To conclude, hardware specs can be very important in some cases, and it is usually better to divulge it. But it is far from being the whole story, and should not be taken as such. And there are situations when it should be irrelevant and may just be an indication that no proper evaluation technique has been actually used for comparisons. Or at least, you should be wary of hasty conclusions regarding the technology used in the software and its quality.
> 1 votes

# Answer
Yes, hardware specs are relevant. No, relative performance differences are not hardware-agnostic.

Suppose I find that editing a certain movie on my laptop takes twice as long as printing a certain Word document on my laptop. Does this mean if I do those two tasks on my desktop computer, the movie editing task will also take twice as long as printing the Word document? No, not necessarily.

Maybe my desktop computer has a great GPU (graphics card) but my laptop doesn't have a GPU. The GPU can be expected to speed up the movie-editing task, but it won't speed up printing from Word. So, on my desktop it's even possible that the movie-editing task might be faster than the printing task.

This is one reason why hardware specs are relevant.
> 2 votes

# Answer
Performance comparisons are not hardware agnostic because performance does not scale proportionately for all applications across all computers.

Even if the relative performance of a particular program is believed to be independent of hardware reasonably likely to be used for the problem the program addresses, providing this information can help when attempting to reproduce results. Just as one would include compiler, libraries, runtime environment, data set, and other software aspects used in the test system even if one believed their impact was minor.

If one's belief about hardware independence is wrong or *becomes* wrong, not providing information about the hardware makes it more difficult to determine whether failure to reproduce results was a consequence of an improper run or of other factors.

Many hardware aspects can disproportionately impact performance.

If one algorithm uses a multi-target indirect branch where another uses conditional branches, a processor which uses a target predictor with one entry per jump instruction address will likely favor the latter program more than a processor with an indirect jump target predictor using some global history (allowing multiple targets per jump instruction).

The amount of memory available to the program can influence the frequency of garbage collection and this frequency can be linked to the algorithm. One algorithm might be significantly faster if memory capacity can be profligately wasted while another might take care (costing performance) to be thrifty with memory.

The size, indexing methods, and associaitivity of various levels of cache can influence performance differently for different algorithms: the active working set and conflict rate can differ. (Similarly, hardware prefetching and cache replacement policies can have different impacts on different algorithms.)

The execution width and pipeline depth of a processor can have dramatically different performance impacts on different algorithms. A scalar (one-wide) processor with a shallow pipeline favors reducing executed instruction count; a wide and deep processor decreases the cost of executing instructions but increases the cost of branch mispredictions and cache misses (more execution opportunities are lost).

The optimizing ability of compilers also varies among different hardware targets. An implementation that maps simply to a compiler's model of the hardware may perform artificially better (and a later compiler improvement may remove this artificial difference).

One factor that may not be well-recognized relates to the full use of system resources. Single-threaded programs run on an unloaded system may utilize cache capacity and memory bandwidth that would be shared if the system was running other tasks. Such a test would favor using these free resources for small performance benefits, clearly introducing a potential unintended bias in a comparison. (This is similar to the garbage collection/memory capacity consideration.)

Performance comparisons are also not merely about determining relative speed. Absolute runtimes are significant. A slower program may be preferred if the performance is good enough and other factors (e.g., ease of integrating with an existing system, generality of the algorithm, scaling) favor the slower program. In addition, the faster program may still be too slow for the considered use.
> 1 votes

---
Tags: algorithm-analysis, memory-hardware
---


# Question
Title: Can each VLIW sub-instruction execute any instruction?
say that you have a 128 bit (32\*4) VLIW word. Can each 32 bit sub-word contain any operation (ADD,CALL,BRANCH,...) if there are no hazards or can each sub-word only specify one functional unit (so if the BRANCH functional unit doesn't get used, that sub-word becomes a NOP)?

# Answer
Usually, VLIW instruction sets dedicate bit fields to functional units (not necessary multiples of bytes, or the same width for all units), and when some parts are unused, they are configured as NOPs.

Of course, there are exceptions, sometimes execution units are coupled, or special configurations are provided for long immediates... There is no absolute rule.

You should look at sample implementations, like the 48bits SHARC DSPs, or the ST200 family.
> 6 votes

# Answer
As TEMLIB's answer indicates, VLIWs generally limit what operations can be encoded into each slot of the instruction word.

The primary constraint is actually structural hazards. The area and power cost of allowing all operations to be multiplications or all operations to be memory accesses would be excessive for most workloads.

VLIW encoding has two prominent goals. The primary goal is to express operation independence, the absence of data (and structural) hazards within an instruction word; hardware does not have to check for these hazards within an instruction word. A secondary goal is to minimize instruction routing complexity. Classic VLIW design where a single instruction word size is supported and nops are placed in unused slots provides the simplest routing of operations, a fixed mapping (as well as simple instruction fetch).

\[fetch width, operation count variability/immediates, buffering, using free space in previous instruction word as addendum for next instruction word, problem with multiple fetch cycles for single issue cycle \[immediates do not have to be decoded, so could be placed in next fetch chunk, a skewed pipeline could allow operations in a single execution word to be fetched later; these steal space from the next fetch chunk/VLIW\]

The additional cost of supporting less expensive operations along with an expensive operation can justify bundling such into a single issue port, but given support for wider execution the benefit of such flexibility is reduced. Such is also nearly indistinguishable from a wider virtual instruction word with eliding of nops with a minimum number of nops elided.

(Superscalar processors have similar issue constraints.)

Since the placement of operations within an instruction word does not imply execution ordering — all operations in a VLIW are independent (exceptions include first-taken branch escapes where multiple branches can be in a single instruction word and only the first taken branch is effective)—, flexibility in placement is typically less useful.

Fixed format instruction words not only provide simpler operation routing but also allow the size of the operation slot to match the requirements for encoding the operations available in that slot. This can improve code density. Decoding logic is also simplified by each slot's decoder only needing to support the operations and encodings allowed by that slot. Such simplifications not only reduce power and area but can also modestly reduce critical path delay which can translate into a faster clock or shallower pipeline.

It is also not uncommon for an operation slot to use encoding space from another slot to increase the size of the operation. This is primarly used to extend immediate values, using the entire operation slot, but conceptually using only part of the other slot's encoding space or using the space to encode register identifiers or opcode extensions would be possible.

Having a fixed maximum instruction word length equal to the fetch width is typical. If an instruction word crossed a fetch boundary, either the front end would have to handle stalling the pipeline when an instruction word is fetched over two cycles (modestly increasing hardware complexity) or software would have to guarantee that enough of the instruction word is buffered from the previous fetch that the next fetch chunk would complete the instruction word (restricting control flow targets, include exception return points).

(You might notice a similarity to SIMD with respect to simplification of routing: SIMD simplifies routing of operands to functional units by using a long *data* word.)

### Encoding Examples

Sun Microsystem's MAJC family of architectures may come closest to allowing every slot to provide any operation. The encoding used 32-bit operation slots with the first two bits of the first operation slot encoding how many operations were in the instruction word (between one and four). The first slot was the only one that could perform control flow and memory access operations and because of these extra operations and the loss of two bits to encode the instruction word length the first slot could not perform all compute operations. The other three slots were uniform in their support of compute operations; this was intended to simplify design by allowing simple copy-and-paste of these functional units. (One branch or memory operation per four operations seems imbalanced for more general purpose workloads, but such might be acceptable for compute-intensive workloads. MAJC ended up targeting graphics and multimedia applications.)

STMicroelectronics' ST240 ("ST240 core and instruction set Reference Manual" (PDF)) provided a "stop bit" with each 32-bit operation slot ("syllable") to indicate the end of a variable-length instruction word. Like MAJC, this helps avoid the use of padding nops; unlike MAJC, this mechanism is not constrained to a maximum instruction word length. In addition to the implementation-independent encoding constraints such as no data hazards, implementation-dependent constraints allowed control flow operations only in the first slot, multiplications only in odd *word* (not syllable) addresses, immediate extensions and a few specific operations only in even word addresses, only one operation per instruction word ("bundle") using the load-store unit, and a few other restrictions. Restricting control flow operations to the first slot facilitates quick detection and action on such operations; other restricts primarily simplify operation routing and avoiding structural hazards.

Tilera TILE-Gx used a fixed 64-bit instruction word, but used two bits to indicate if the word used two-operation X format (if both bits are zero) or three-operation Y format. The Y format provided two 24-bit operation encodings (Y0 and Y1) and one 14-bit encoding (Y2) that also used the three states from the two format-specifying bits to indicate a "mode" for the operation. The X format provided two 31-bit operation encodings. The Y2 slot could execute loads and stores; the Y1 slot could execute arithmetic, logical, and jump register operations; and the Y0 slot could execute multiply, arithmetic, and logical operations. The X1 slot combined the capabilities of the Y2 and Y1 slots and the X0 slot had the capabilities of the Y0 slot. Aside from the potential combining of slot capabilities and slight variability in slot size, this is effectively a classic VLIW encoding.

The Philips TriMedia TM3270 ("The TM3270 Media-processor", Jan-Willem van de Waerdt (PDF)) had five slots per instruction word and used a 10-bit template field to encode the size of each slot for the *next* instruction word. (Jump target instruction words are always uncompressed, avoiding the problem with multiple next instruction words following branches and register-based jumps.) A slot could be between 0 (nop) and 42 bits long. All slots could have simple ALU operations and immediates. Slot 1 could DSP ALU operations, and FP ALU operations; slot 2: jumps, multiplies, FP cmp, and hard FP; slot 3: DSP ALU, multiply, and FP cmp; slot 4: jumps, DSP ALU, FP ALU, and store; slot 5: load, store, and special operations using the load-store unit. In addition, slots could be merged to have more sources and destinations: merging slots 1 and 2 or slots 3 and 4 provides one set of operations, merging slots 2 and 3 provided another set, and merging slots 4 and 5 provided a third set of operations.

Fujitsu's FR500 ("FR500 VLIW-architecture High-performance Embedded Microprocessor", Takao Sukemura (PDF)) is interesting in have six potential issue slots but only supporting up to four operations per instruction word. The potential issue slots are: integer-0, float/media-0, integer-1, float/media-1, branch-0, and branch-1. Like the ST240, the FR500 uses a bit per 32-bit operation slot to indicate the end of the instruction word. If a potential issue slot is unused, the next slot is shifted into its place.

The Cydrome Cydra-5 ("The Cydra 5 Departmental Supercomputer: Design Philosophies, Decisions, and Trade-Offs" (PDF) was an early VLIW which used a fixed-length 256-bit "instruction container". This could hold either six 40-bit serial operations ("UniOps") or a seven operation MultiOp with different-sized slots: 39-bit FADD/ALU, 39-bit FMPY, 44-bit Mem1, 28-bit Mem2, 33-bit AADD1, 32-bit AADD2/AMPY, and 41-bit Branch.

(Other examples of VLIW encodings include the Multiflow TRACE, the Texas Instruments TMS320 C6xxx, and Intel Itanium.)
> 2 votes

---
Tags: computer-architecture
---


# Question
Title: use of unconditional transfer of control instruction
I did not understand why unconditional transfer of control instruction is used in cpu.So if we already know we have to jump to an instruction and skip some instruction irrespective of any condition then why do we not avoid writing those instruction as they will not be executed and replace them with instruction that will be executed after jump instruction

# Answer
> 6 votes
To implement if-then-else, when you get to the end of the "then" branch, you need to jump unconditionally past the "else" branch. The breaks in a C switch statement are also unconditional jumps.

You could probably also implement tail recursion by replacing "call" instructions with jumps.

# Answer
> 1 votes
As David Richerby's answer notes, the most common use is for implementing if-then-else, where the unconditional jump hops over the else code.

A related use is when the compiler knows conditional code is rarely executed and places it far from the more common executed code, so that an unconditional jump is used to return to the post-conditional code. This is a code transformation from:

```
 branch-on-cond-to-LABEL
 not-"cond"-code
 jump-to-JOIN
LABEL:
 "cond"-code
JOIN:

 branch-on-cond-to-LABEL
 not-"cond"-code

JOIN:

 ...

LABEL:
 "cond"-code
 jump-to-JOIN

```

This can enhance memory system performance by exploiting sequential prefetch and avoiding the fetching and storing of a partial cache block of code that is rarely used. (This is an extreme extension of placing the less frequently executed code of an if/else in the later position. This makes the common case a not taken branch which can avoid using a branch target buffer entry, can exploit simple static prediction (forward branches not taken), and can avoid the fetch redirection penalty in some processor implementations.)

It is common for instruction sets to provide a greater range for unconditional jumps than for conditional branches. This means that a conditional jump with a distant target might have to use a conditional jump (with an inverted condition) over an unconditional jump instruction.

An unconditional jump can also be used for hot patching. An unconditional jump to the next instruction (or other nop of the appropriate size) at the start of a block of code (typically a function) can be atomically changed to an unconditional jump to the new code replacing that block.

Another potential use for an unconditional jump instruction is to jump over inlined data. With a shared instruction and data cache, it might be useful to exploit block-granular retrieval from memory and sequential prefetching by placing data with code. This also allows the use of the program counter as a data address register, potentially avoiding the need to load a base address and slightly reducing register pressure.

In some early instruction sets there were no function return (or general indirect jump) instructions, so an unconditional jump instruction at the end of a function was (partially) overwritten to jump to the return address.

---
Tags: computer-architecture
---


# Question
Title: What are some "easy" unreasonable implications of O(1) time memory access?
If you are given a memory address $n$ bits long, then you need to at least process those bits. Hence, if you have $N$ memory available, addressed by $n$ bits, it would take $O(\mathbf{log}(N)) = O(n)$ time to access a given memory location, at best. I can see why it might be convenient to assume $O(1)$ memory access time because we don't go out of our way to abuse it in day-to-day arguments, and because $\mathbf{log}$ grows slowly. That said, what are some "easy" unreasonable implications of being able to access memory in $O(1)$?

# Answer
Memory access is assumed to be constant time, because normally you access memory that is close to each other, eg. from one hard drive or one given computer. Under that assumption there is a constant maximum amount of time to retrieve that data.

You are right. If I access data randomly accross very large amounts of data, then it's nowhere near constant, but normally you can arrange the data beforehand in a way that makes it O(1), because of it fitting onto one machine or very close machines. Another reason is that, harddrives all come with their hardware. That means normally you won't be switching hard drives in and out of one machine, and each drive comes with it's own reader. Also most machines are limited to a certain amount of drives. Those technical limitation give O(1) comlexity to most pratical applications and the software perspective of things.

One easy and unreasonable implication of O(1) time memory access is violating the assumptions above by scattering data randomly, across multiple machines in an unordered fashion or switching drives in and out of machines and expecting O(1) access times. Anything relying on wrong assumption is doomed to be wrong and thus unreasonable.
> 1 votes

# Answer
The fault in the logic here is that `n` bits are processed in parallel. Roughly speaking out of those `n` bits, `m<n` bits are used to select the chip, and on the chip `m-n` bits are used to select the memory cell.

The chip select can be envisaged as offering all chips in parallel the relevant `m` bits of the address. Each chip has a unique ID, so only one of them will match that part of the address and start decoding the next `n-m` bits.

On the chip, pretty much the same process repeats: the memory cells are arranged in rows and columns. The incoming `n-m` bits are split in two. Half of those select the correct row, half select the right column, and at the crosspoint of the two is the right memory cell.

In practice, chips are grouped in DIMM's, inside a chip there are individual pages, memory access isn't bit-by-bit but typically 64 to 256 bits at a time, but that's irrelevant for the big-O picture. All relevant address decoding happens in parallel.
> 1 votes

# Answer
The easiest unreasonable implication is that such ignores the impact of temporal and spatial locality of reference in conventional systems. Processor caches cause accesses to other addresses within a cache block to be faster (spatial locality) and repeated accesses to the same address (temporal locality) when accessed while still in cache. Conventional implementations of virtual memory also cache address translations at page granularity. Latency (and bandwidth) in accessing standard DRAM will vary based on whether the access is a row hit (this avoids the need for a row activate command) and whether the DRAM bank being accessed has an active row (this requires a precharge command before the row activate command). Conventional storage devices are high latency block devices and copy data to main memory (in some cases to last level cache), again introducing issues of spatial and temporal locality.

Random accesses may have approximately constant latency when the working set size is within the capacity of one level of the memory hierarchy but much larger than the next level closer to the processor. That is, when the vast majority of accesses are satisfied by one level of the memory hierarchy. (Even this ignores cold-start latencies.)

Even without caching (i.e., copying data into a faster memory), basic physics encourage non-uniform access delay: storage that is physically closer to the processing element can have lower latency. In addition, while the speed of light limit would imply O($\sqrt\[3\]{N}$) latency (**not** O(log(N))), something between O($\sqrt\[3\]{N}$) and O($\sqrt{N}$) is probably more realistic because of the way systems are biased toward two dimensional layout (not that a circular single processor system with a radius of tens of meters is especially realistic).

Another factor is that for larger memories, reducing cost per bit of "distant" storage at the cost of latency becomes attractive because the latency cost of a slower technology is effectively constant while the latency cost of communication is related to distance. Not only are caches requiring spatial and temporal locality effective, but programmers even have some bias toward such locality (e.g., data members of an object are typically allocated together and referenced with some temporal locality because they are conceptually related). This further encourages the use of memory hierarchies.

(Distributing work to multiple processing elements increases the complexity of memory latency considerations. Because physical distance is a factor in latency and large crossbar interconnects are expensive, local memory will be used and access latency will depend on which processing element is accessing the memory. Each processing element is likely to have its own memory hierarchy with levels of sharing. In addition to reducing local latency, distributing computation facilitates increased local bandwith.)

Another factor involves the ability to overlap latencies (memory level parallelism). An algorithm that can do other work while waiting for a slow access will hide some of the latency of that access. By introducing necessary slow accesses at a higher rate more of the latency can be hidden (the accesses are effectively pipelined). Unlimited memory level parallelism changes a latency bottleneck into a bandwidth bottleneck.

(Asymptotic notation also inherently ignores constant factors and lower order terms, but in actual systems these can be significant.)
> 1 votes

---
Tags: complexity-theory, time-complexity, memory-access
---