ISADesign:GeneralDesign:A

Copyright 2018, Clinton A Staley

Concepts

Optimization of bit use
Prefix codes

Overview

In this topic we'll look more broadly at the design of ISAs, using the particulars we learned about the ARM ISA as a starting point.

Bits Are Precious

One of the biggest principles of ISA design is that bits are precious S1. We saw how carefully the ARM architecture uses bits, and this is typical of ISAs in general.

Big instructions are slow

The main reason for this is that larger instructions are more expensive S2. We could, for instance, gain a lot of bits to play with by increasing the ARM instruction size from 32 to 64 bits. Clearly this would make programs take twice as much memory, but the bigger problem is that loading the instructions takes time, and will take more time with longer instructions. It's easy to overlook instruction loading time as a cost, but instructions are data just like anything else, and the CPU must load each one from memory to run it; big instructions slow down the processor.

Making the most of bits

So, we make the most of the bits we have.

Question 1

Cite at least two examples from the prior topic on ARM ISA design, showing clever optimization of bit usage. Here's a copy of the instruction format chart for reference S3.

Answer 1

A number of examples are possible: the clever use of fixed bits of varying lengths S4, the design of operand2 constants in data processing instructions S5, the implied addition of a 00 to branch offsets S6, the implied "1." at the start of floating point mantissas, etc.

Question 2

Cite at least two examples where bit field constraints present a significant limit in the ARM ISA.

Answer 2

Lots of possibilities here, including: range limits on ldr/str offsets, S8 limitations on operand2 constants in data processing instructions, S9 inability to use a constant in a mul instruction, etc. S10

Question 3

S11 One way to cut down on ldr/str memory accesses, which are very slow compared to register accesses, would be to have more than 16 registers, so we can hold more data in registers. The hardware cost of doing this is negligible; registers take up very little of the CPU circuitry, and we could easily have many more. So, why not have a choice of, say, 64 registers instead of just 16? (Consider the impact on the format of the instructions.)

Answer 3

The register fields in the assembly instructions would need to be 6 bits long to count from 0 to 63 S12, adding 2-6 bits to most instructions.

Prefix Codes

S13 In the ARM design, we saw a pattern of different-length fixed-bit prefixes on instruction types, e.g. 00 for data processing, 01 for ldr/str, 100 for ldm/stm, and 101 for branch. This pattern has an underlying theory and a formal name: prefix codes. Prefix codes often show up in ISA design, and in many other contexts as well, including data transmission and compression.

A prefix code is a set of bit patterns, of varying length, designed so that no pattern is a prefix of any other. (Perhaps they should have been called "nonprefix codes".) Here's an example S14:

No code in that set is a prefix of any other. For instance, the existence of 00 as one of codes precludes other codes that start with 00 S15. Ditto for 01 <S16. And the 100 code precludes other codes with a 100 prefix, as does the 101 code for its prefix S17.

Question 4

Think about adding more codes to that set, following the rule. Can you add a 2-bit code? Can you add more than one 3-bit code?

Answer 4

You can't add any 2-bit code. All 2-bit prefix patterns are already in use S18, so a new 2-bit code would violate the no-prefix rule. You could a add 3-bit code: 111 S19. But you can't add two 3-bit codes since any other 3-bit code would either be a prefix of another code, or have another code as its prefix.

Question 5

S20It is nonetheless possible to add more than one new code, if you go to longer lengths. Can you add two more 4-bit codes, following the rules? How about four more 5-bit codes instead?

Answer 5

Two four bit codes would be 1110 and 1111 S21. Five bit codes instead could be 11100, 11101, 11110, 11111S22

A helpful way to look at prefix codes is to consider them as the first part of a longer word. Let's use a 4-bit word as an example, with all patterns shown here S23. Each prefix code you choose effectively "uses up" all bit-patterns starting with that prefix. A code of 0, for instance, "uses up" half of all patterns, since it precludes any other code starting with 0 S24. A two-bit code, like 10, uses up 1/4 of the available patterns, all those starting with 10 S25. And a 3-bit code, say 110, uses up 1/8 of the patterns S26.

Prefix codes to identify instruction formats

It's common for ISAs to distinguish machine instruction instruction formats by putting fixed bits at the start of each format. But, the fixed bits must generally be a prefix code. Otherwise if, say, instruction format A has fixed bits 10, and B has fixed bits 101 (both shown in the diagram in red), violating the non-prefix rule, then any A-format instruction whose first non-fixed bit is a 1 will look like a B-format instruction since it starts with 101.S27

A instruction 10|1-------------------------
B instruction 101|-------------------------

Format B must use a 3-bit fixed pattern that starts with something other than 10 to be distinguished from format A.

Designing prefix codes

To design a prefix code, you decide how many short codes vs how many long codes you want, budgeting how you allocate the "prefix space". If you're designing the fixed-bit parts of an ISA, you give shorter prefix codes to instructions that need more free bits to work with, and thus must have fewer fixed bits. But, the tradeoff is that other instructions must suffer with longer fixed-bit prefix codes and fewer free bits.

You can tell which instructions are more important by the number of non-fixed bits given them. For instance, the ldr/str instruction's prefix is 2 bits long. S28 The ARM designers could have made that 3 bits to permit shorter prefixes for other instructions, but that would have left one fewer free bit for the ldr/str, which would probably have come out of the offset field S29, reducing the range of address-relative offsets from 4095 to 2047. Ldr/str are so common and important that it was worth giving them just 2 fixed bits. Almost all the ARM instructions we've been learning have short fixed-bit prefixes because they are the most important in the ARM ISA.

(Note that the multiply, multiply long, and swap instruction formats in the ARM ISA violate the prefix code rule by having fixed-bit patterns that start with 00 S30, matching the fixed-bits for the data processing format. But, they have an additional 4-bit fixed 1001 pattern in bits 4-7 to distinguish them from the data processing format S31, which forbids 1001 in those bits unless it also has a 1 in the S position.) S32

Question 6

Design a prefix code for a 32-bit ISA like ARM, but without condition codes. There are three instruction formats, each with different numbers of free (non-fixed) bits: one with 31 free bits, one with 30 free bits, and one with 29 free bits, respectively. Design a fixed-bit prefix code for those three formats. Don't worry about the free bits; this is about just the fixed bits. If a fourth instruction type is needed, how many free bits can it have, at most?

Answer 6

We'll need fixed-bit prefixes like 0, 10, 110. S33 Such a prefix code "uses up" 1/2 + 1/4 + 1/8 = 7/8 of the available bit patterns. This limits the fourth format to a 3-bit code, e.g. 111, and just 29 nonfixed bits. S34

Other applications of prefix codes

Prefix codes are used in other areas than ISA design, most importantly in data compression, where it's common to set up prefix codes to represent, for instance, the letters of the alphabet, with shorter codes for common letters, and longer codes for uncommon letters. Since the shorter codes are used more frequently than the longer ones, the total data needed is reduced.