patternMinor
Information theory of instruction set architecture design?
Viewed 0 times
architecturetheorydesigninstructionsetinformation
Problem
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 doesn't seem obvious to me how information theory can be used to understand instruction set architectures. Has information theory been applied to understand instruction set architectures? (I didn't find anything after a quick Google search.)
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 doesn't seem obvious to me how information theory can be used to understand instruction set architectures. Has information theory been applied to understand instruction set architectures? (I didn't find anything after a quick Google search.)
Solution
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.
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.
Context
StackExchange Computer Science Q#120379, answer score: 2
Revisions (0)
No revisions yet.