11

The title says it all:

How to En-/Decode Z22/Z23 Instructions?

(History and Linkage:
The question was raised by Wilson in a comment on my answer to his question "Why are PDP-7-style microprogrammed instructions out of vogue?", where I mentioned the Z22 as an early example for discrete function encoding and (V)LIW. I felt that answering this would better fit a question in its own right.)

13

[Preface: this is about a very early architecture, defined way before and completely independently of today's canon, formed by IBM's /360. When reading, it might be useful to take terms used at their face value, and strip all the semantic baggage that goes with them when talking about today's architectures.]

The Zuse Z22 is in may ways unique (*1), not just by being one of the first, if not the first machine to use core memory, but also in employing techniques that have been rediscovered decades later as 'RISCy' (*2). A related feature is skipping the 'classic' decoding stage in favour of a Long Instruction Word (*3,*4) implementation.

Today's short descriptions about the Z22 (like its English Wiki entry) are often taken from the first paragraphs of the instruction encoding section of the internal operations manual, translated to English, using more common terms like here (from Wikipedia):

[I have already corrected this on the English Wiki page, but there are many other pages carrying the same error]

It was programmed in machine code with 38-bit instruction words, consisting of five fields:

the first 2 bits must always be 10
the next 5 bits contain a condition symbol
the next 13 bits contain an operation symbol
the next 5 bits contain a core memory address
the next 13 bits contain a drum memory address

The corresponding part of the manual looks like this:

enter image description here

Looking closely shows a classic translation error, as Bedingungszeichen (condition symbol(s)) and Operationszeichen (operation symbol(s)) in this context are plural not singular (*5), so these fields are not holding single symbols, but collections of symbols that can be combined at will.

What all of these short descriptions leave out is how the manual continues over two dozen pages to describe the operations in detail. The very next paragraph continues:

Jeder Befehl enthält ein Operationsteil (mindestens 1 Buchstabe) und einen Adressteil (mindestens 1 Ziffer). Die einzelnen Operationszeichen können fast beliebig untereinander zu sinnvollen Befehlen zusammengefasst werden. Jedem Befehl kann eine oder mehrere Bedingungen zugesetzt werden, und damit die Ausführung von der Erfüllung der Bedingungen abhängig gemacht werden.

In (mostly literal) English:

Every instruction contains an operation part (at least one letter) and an address part (at least one number). Singular operation symbols can be combined in almost arbitrary manner. Each instruction can contain one or more conditions to depend its execution upon these conditions.

So with this knowledge, it should better read:

  • 2 bits 10 to mark an instruction
  • 18 bits instruction field, thereof
    • 5 bits condition symbols
    • 13 bits operation symbols
  • 5 bit fast storage address
  • 13 bit (drum) memory address

It's important to know that while the 5-bit field addresses a core memory location, it's not a different address space. The core can also be addressed using the memory address as it occupied the first 32 memory locations. So this is rather a way to have two addresses in a single instruction. Think of it like having registers in memory.

Also, the 13-bit memory address should always be seen as such. While it was located on a drum, part of it could be upgraded to core - with the Z23, increasing access speed and removing the need to arrange instructions and data in special patterns to reduce access time.

But back to instruction encoding. Instead of having a short unique code for each legal operation, there are separate bits for each functional unit. Although this sounds like a waste of memory, an instruction word was 38 bits anyway, giving plenty of room.

The 18 bits were organized as

3..7: condition symbols marking an instruction executable
3 PP  if accumulator is positive (>=0; bit 1 cleared)
4 P   if memory location 2 is positive (>=0; bit 1 cleared)
5 QQ  if accumulator is negative (<0; bit 1 set)
6 Q   if memory location 2 is negative (<0; bit 1 set)
7 Y   if memory location 3 is odd (bit 38 set)

The condition symbols can be freely combined. If more than one is set, all conditions have to apply (conjunct). As a special case PPQQ is true if the accumulator content is zero. Memory location 2 is a generic scratchpad register, but also serves as persistent flag for conditional tests (*6). Memory location 3 is another special location (*7), as its lowest bit can be tested for set (condition Y). Each and every combination is possible. PPQQY for example would execute the instruction only if the accumulator is zero and the lowest bit of location 3 is set, a condition that could be true after a shift left from accumulator and loc 3 when the accumulator held the most negative number.

Now for the operation symbols:

8..20 operation symbols activating unique functions.
8  C  Constante (Constant) - Bit 20..38, which would be fields for addresses and operation V, are instead a 19-bit constant.
9  N  Nullstellen (Zeroing) - Accumulator will be zeroed
10 LL Links Links (Left Left) - Shift accumulator left by 2
11 R  Rechts (Right) - Shift accumulator right by 1
12 U  Speichern (Store) - Accumulator will be stored to address
13 A  Addition (Add) - Content of a memory location will be added

U and A also work as a pair, generating two more instructions when both are set or both are cleared. Effectively they select the base operation - everything else adds to this operation. With both cleared it becomes the pseudo operation E or Jump. If both are set, than it's the pseudo operation I or Intersektion (intersection, meaning AND).

14 S  Subtraktion (Subtract) - Negates memory content, effectively turning it into a subtract operation.
15 F  ? (?) - Copies the already incremented program counter into memory location 5 before continuing with a new/next address.
16 K  Kennzeichen (Mark) - The lower 13 bits are not interpreted, only the fast memory address is used.
17 H  ? (?) - The lowest bit of location 3 gets set
18 Z  Stop (Stop) - The machine gets stopped before the instruction gets executed, but only if the conditions are met.
19 G  Addressubstitution (Address Substitution) - Used for indirect addressing and/or indexing and/or autoincrement (this operation is so complex, it for sure needs its own article)
20 V  Verkoppeln (Couple) - Memory location 3 is to be used as extension for the accumulator when shifting.

All of these operations could be combined in a single instruction - albeit with restrictions. In fact, some seemingly 'basic' instructions had to be synthesized. For example, there is a single bit shift right (R), but no single bit shift left. Only a double shift left (LL). A single bit left shift had to be synthesized as LLR - to ease programming, the Assembler offered the pseudo operation L, which got translated into LLR.

Speaking of assembler, with such a component-based instruction set 'kit' the mnemonics itself are not fixed instructions, like we're used to today, but any combination of above operations, represented by its letters. By convention, they are written in the sequence they occur in the bitfield:

CNLL(L)RUA(IE)SFKHZGF

Although any sequence is valid (they are parallel in nature (*8)), sometimes a different ordering may improve reading.

Examples:

  • NA <loc> is a load, constructed from clearing the accumulator and adding a memory locations content
  • ANC <value> a load like above, but instead of memory content, the address field is added
  • LA 4 (= LLRA 4) multiplies the accumulator by 3
  • LLA 4 multiplies the accumulator by 5
  • RA 4takes 2/3 of the accumulator

Especially the last one would imply a real inflation of opcodes in today's ISAs, wouldn't it? It also shows some of the redundancies of instructions. For example clearing the accumulator can be achieved in many ways - like NA 0, NI <any value> and so on.

It would be possible to go on for hours, so let's close with some fun combinations around address calculations:

  • GA 11 Indirect: Add the content of the location location 11 points to
  • GKA 11+o Indexed: (Offset) 'o' will be added to content of location 11 (only fast memory possible) before adding the content of the resulting address
  • CGKA 11+1 Indirect Autoincrement: Like Indirect, but the register will be incremented
  • CGKA 11+5 like before, but now incremented by 5 - great for arrays, even more cool to incorporate the drum skew for fast accessible arrays :))
  • CGU 11+n Add 'n' to fast (core) memory location 11
  • CGA 11+n like before, and use the addressed content for the addition

The last one is like a while C line in a single instruction: A += *( s += n ) - adding a simple 'QQ' even turns it into IF (A) ... . And there are many more complex operations possible. As I said before, that may need a whole book of its own.


Postscript:

So yes, much like Wilson assumed, building instructions from smaller operations is an incredible tool (*9), but it quickly gets out of hand. The Z22 uses 18 bits for encoding, but I doubt that there are more than a few hundred useful instructions. Even if it's a thousand, encoding them in a single opcode would need more like 9-10 bits instead of 18. Do the math.

Still, learning the details may be a good idea for everyone designing a new CPU. Design your operational units, link them up in a Z22-like manner and work out whatever useful combinations there are, before 'compressing' them into common opcodes.


*1 - Unlike the name suggests, the Z22 was not solely Zuse's brainchild, but imagined by Theodor Fromme (today maybe called design lead) with much help from Heinz Zemanek and Rudolf Bodo (both from the Mailüfterl team) and made the schematics for the Z22. The idea was to design the tube-based Z22 in a way that it may be transistorized later. Which happened with the Z23. Quite remarkable foresight at the time.

*2 - Like having Register 0 always produce the value 0, or having streamlined cycle, being the same for each and every instruction - even implementing the instruction pointer by inserting an addition - and many more.

*3 - This is related and the base of today's VLIW, except the VLIW definition used today is (usually) based around the idea of packing several, independent instructions into a memory word to increase throughput.

*4 - Make sure to not mix this up with synthetic instructions, which nowadays is just a fancy name for opcode synonyms.

*5 - Zeichen (Symbols) is the same in singular as well as in plural. Context defines what is meant. Here it's plural, to turn it singular an indefinite article needs to be added - much like in English - except modern English also (almost) always additionally adds the suffix 's' to the plural.

*6 - Hence often called Testspeicher 2 (test-memory 2) or Vorzeichentestregister (sign test register) throughout documentation.

*7 - While the fast memory address range is 32, only 14 of it is filled with RAM (25 with a separate available core extension, item#11), the rest are special locations

  • Loc 0 always returns 0, can not be written
  • Loc 1 always return maximum negative, which is also the marking for an instruction, can not be written.
  • Loc 2 is a scratchpad location, but its sign can be tested
  • Loc 3 is a scratchpad location, but it can be combined with the accumulator for shift operations - and its lowest bit (bit 38) can be tested for 1
  • Loc 4 is the accumulator (or more correct, the accumulator content of the last operation)
  • Loc 5 is a scratchpad location, but can also receive the last instruction's address+1. useful to create subroutines :)
  • Loc 6..15 are generic scratchpad locations without any additional meaning
  • Loc 16..31 are not present as core, still some functionality is attached
  • Loc 16 is a read only shadow of Loc 5 (return address)
  • Loc 17 is a one-bit port to read the position of a console switch
  • Loc 19 is the I/O port for extended machines (additional fast readers/punches/printers)
  • Loc 20 is the I/O port for the default console.
  • Loc 21 to 31 (11) were availible as option.

*8 - Of course just in writing, not in execution. NA <loc> loads a memory into the accumulator (after clearing), while UN <loc> stores the accumulator before clearing.

*9 - Did I already mention the incredible way of conditional debugging? There is the Z bit to stop any operation before execution, but in addition there's the option of adding the C(constant) bit to any jump (E), an otherwise useless combination. Now execution will stop before the jump is taken but only if the console switch bedingter Stop (Conditional Stopp) is set. Turning on debugging with the flip of a switch :))

  • Why does each instruction contain a Befehlskennzeichen 01? One guess is: numerical data is likely to start with 00 or 11 so accidentally trying to execute it would throw some sort of illegal instruction exception. – Wilson Apr 14 at 7:11
  • @Wilson (It's 10 - so basically a negative number) Serious? I don't know (exactly) why. I would need to check the schematics, but as far as I remember it has as well to do with the way data and instructions are shifted thru the logic. 10 makes all instructions very low negative integer. – Raffzahn Apr 14 at 12:27
  • 1
    @wizzwizz4 Revert has already be done by others. And no, for one, PPQQ is a special case, testing for all out Zero, second PP tests for Positive (high bit cleared), which includes Zero by default, while QQ test for negative (high bit set). Most important, keep in mind PPQQ isn't one of the basic operations, but an otherwise useless encoding (PP and QQ can never resolve at the same time) that got turned into the meaning of 'Test for Zero' – Raffzahn Apr 15 at 13:58
  • 1
    Quote from your answer: 8 C Constante (Constant) - Bit 20..38 are a constant, not an address (and operation V) I figured that (and operation V) somehow means that V is implied by C. I have probably misunderstood, so what does it mean? – Wilson Apr 18 at 9:48
  • 1
    @Raffzahn is better now? – Wilson Apr 18 at 10:50

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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