2
$\begingroup$

Information theory to a large extent deals with how to efficiently encode messages given a probability distribution over messages.

Intuitively, it seems like we can think of machine instructions (or programs) as "messages to the CPU". Some messages are more probable than others. E.g. "add numbers x and y" is more probable than "compute the y'th square root of x", which is maybe one of the reasons why we don't have an instruction like the latter.

However there are obviously other considerations involved like computational complexity, so it doesnt seem obvious to me how information theory can be used to understand instruction set architectures. Has information theory been apllied to understand insteuction set archtectures? (I didnt find anything after a quick google search.)

Improve this question
$\endgroup$
0

1 Answer 1

Reset to default
1
$\begingroup$

It seems you are interested in how to represent instructions in the most compact size. But that is quite a secondary consideration.

The most important two considerations are: 1. Being able to decode an instruction in the shortest possible time. 2. Determine the length of an instruction in the shortest possible time.

Why is this so important? Let's say you have an instruction to add two integers. This can be done very fast, say 300 picoseconds. Now when you decode that instruction, the decoding must be done in a time comparable to that of an addition, or the decode time becomes what limits the speed of your CPU, instead of the time that is actually needed to do the work.

The time to determine the length of an instruction is even more critical. Modern CPUs will often execute up to four instructions per processor cycle. So they must be able to decode four instructions per cycle. To do that, they must be able to determine the length of the first instruction, the second instruction, and the third instruction, before they can figure out where the fourth instruction starts, and start decoding that instruction. So we need to determine the length of three instructions, and decode a fourth, in the time it takes to add two integers!

So you can see how decoding must be absolutely fast. You just don't have the time to use any decent compression algorithm because it would slow down everything.

Update: ARM processors with fixed instruction length can decode 9 instructions per cycle, while variable length x86 instructions are limited to 4 decodes per cycle. So this is not something that can be solved by throwing transistors at the problem.

Improve this answer
$\endgroup$
5
  • $\begingroup$ It seems to me that there are other ways that information theory might be relevant than "compression of instruction length", which is not what I was thinking of. I was thinking more of, using information theory to decide which instructions are even there, and how computational resources are allocated to instructions. For example, addition is a very common operation, so we want it to have its own instruction and its own functional unit. On the other hand, in a bitcoin miner ASIC, we want a specific functional unit for solving a particular crptographic problem. $\endgroup$
    – user56834
    Feb 9, 2020 at 4:32
  • $\begingroup$ The probability distribution over programs is different for a bitcoin miner than for a cpu, so they allocate transistors differently to functional units and their basic operations are different. I can imagine that this can (at least theoretically and approximately) be modelled uaig information theory. $\endgroup$
    – user56834
    Feb 9, 2020 at 4:34
  • $\begingroup$ This was part of the thinking behind RISC, of course: analyse real instruction streams to find which instructions actually needed to be optimised for. See also ARM Thumb, for an ISA encoding example. But I have to disagree on one point in @gnasher729's answer. To a first approximation, decoding instructions isn't really the bottleneck (we can just throw a lot of transistors at the problem), and nor is getting instructions into the CPU. The biggest bottleneck is the instruction window, because this limits parallelism. $\endgroup$
    – Pseudonym ♦
    Feb 9, 2020 at 22:36
  • $\begingroup$ @pseudonym, "we can just throw a lot of transistors at the problem", doesnt this assume decoding can be perfectly parallelized? $\endgroup$
    – user56834
    Feb 10, 2020 at 4:12
  • $\begingroup$ @user56834 Instruction decoding is a constant-time operation whatever way you think about it, because there's a finite number of bits in a L1 cache line (which is the typical unit of instruction decoding in a modern CPU). In practice, for complex ISAs, instruction boundaries are often marked as extra bits when an instruction is inserted into L1 cache, which is as example of "instruction predecoding". $\endgroup$
    – Pseudonym ♦
    Feb 10, 2020 at 4:36

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge that you have read and understand our privacy policy and code of conduct.

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