1 of 11

Solving the�“Grecian Computer Puzzle”�using IBM z/Architecture Vector Instructions

1

The Antikythera mechanism is an ancient orrery (a mechanical model of the solar system) discovered in a shipwreck off the Greek island of Antikythera in 1901. It is estimated to have been built around 87 BCE, making it the oldest known example of an analog computer. See https://en.wikipedia.org/wiki/Antikythera_mechanism for details.

Designed by the True Genius company, the Grecian Computer puzzle is (very) loosely designed to look (sort of) like the Antikythera mechanism. However, rather than depicting a model of the solar system, the puzzle’s goal is to align four rotors such that the numbers in each of twelve radii add up to 42. Google “Grecian computer puzzle” for links to multiple vendors of the puzzle.

As seen in this slide, the topmost rotor has one track of numbers, with the next-lower rotors having two, three, and four tracks of numbers. Each track has twelve sectors, with a sector comprising either a positive integer or a hole through which a number from a lower rotor may be observed. Depending on the alignment of the rotors, multiple holes may be on top of each other. However, the bottom (fifth) rotor has no holes, so there will always be a number visible in all sectors of all tracks on the bottom.

Having received such a puzzle for Christmas in 2020 and aggravating my already-inflamed carpals by twisting the rotors for five frustrating minutes, I remembered that this is what computers are for. A small C program solved the puzzle in nearly key-bounce response time … debugging it took somewhat longer. However, I wondered whether the vector instructions introduced into IBM’s z/Architecture could be used to solve the puzzle.

There are 14 tracks on the five rotors (1+2+3+4+4), each having twelve sectors, and 26 is the largest number. So, each track can easily fit into a vector register apportioned into byte elements (with four elements to spare in each register). The next slide illustrates an expanded view of the rotors showing all numbers on each.

2 of 11

Rotor Values

Rotor 1 (top)

Rotor 2

Rotor 4

Rotor 5 (base)

Rotor 3

8

3

6

15

7

10

6

11

9

11

14

6

7

15

17

12

7

4

3

6

5

13

9

7

13

21

17

6

15

4

9

18

10

8

7

8

12

21

9

5

9

1

14

16

4

26

11

22

10

8

3

17

14

11

14

13

12

9

6

7

3

6

2

12

9

12

6

9

7

9

20

3

26

1

2

16

9

12

3

19

10

8

14

11

14

11

14

11

10

11

12

13

14

15

4

14

21

9

4

10

7

16

8

7

8

11

14

11

14

7

8

9

5

6

3

4

12

2

5

3

4

2

3 of 11

Initial Rotor VR Specification

Initial ds 0L

* Rotor 1 (top, 1 track, with holes)

dc al1(03,00,06,00,10,00,07,00,15,00,08,00,00,00,00,00)

* Rotor 2 (2 tracks, with holes)

dc al1(03,00,06,00,11,11,06,11,00,06,17,07,00,00,00,00)

dc al1(00,07,15,00,00,14,00,09,00,12,00,04,00,00,00,00)

* Rotor 3 (3 tracks, with holes)

dc al1(04,05,00,07,08,09,13,09,07,13,21,17,00,00,00,00)

dc al1(26,14,01,12,00,21,06,15,04,09,18,11,00,00,00,00)

dc al1(00,16,00,09,00,05,00,10,00,08,00,22,00,00,00,00)

* Rotor 4 (4 tracks, with holes)

dc al1(02,07,00,09,00,07,14,11,00,08,00,16,00,00,00,00)

dc al1(00,09,20,12,03,06,00,14,12,03,08,09,00,00,00,00)

dc al1(12,03,26,06,00,02,13,09,00,17,19,03,00,00,00,00)

dc al1(00,01,00,09,00,12,00,06,00,10,00,10,00,00,00,00)

* Rotor 5 (base, 4 tracks, no holes)

dc al1(11,14,11,14,14,11,14,11,14,11,11,14,00,00,00,00)

dc al1(07,08,09,10,11,12,13,14,15,04,05,06,00,00,00,00)

dc al1(06,03,03,14,14,21,21,09,09,04,04,06,00,00,00,00)

dc al1(12,02,05,10,07,16,08,07,08,08,03,04,00,00,00,00)

Hole designated by zero.

Rightmost 4 elements ignored.

3

This slide illustrates the assembler-language encoding for the 14 tracks of rotor values shown on the preceding slide. These values are loaded into 14 contiguous vector registers.

Note that a sector with a hole is represented by a value of zero (which happens to be a key concept in the following processing). Also, there are only twelve sectors per track, so the rightmost four bytes are not part of the puzzle (but they need to be set to zeroes for subsequent processing).

I’m occasionally asked why I code assembler labels, mnemonics, and symbols in lower case when many programmers continue to stick with upper-case for these. The primary answer is that (as noted earlier), I’ve got really aggravated carpals and pressing the shift key is painful. Although there may be some confusion between the lower-case “L” and the number “1”, those skilled in the art should be able to figure it out.

4 of 11

Some Handy Equates for VRs

* Equates for vector registers

vzeroes equ 0 Register of zeroes.

vtemp equ 1 Work register

vanswer equ 2 Answer register

vmask equ 3 VPERM 4th operand.

a1 equ 10 Addend for track 1.

a2 equ 11 Addend for track 2.

a3 equ 12 Addend for track 3.

a4 equ 13 Addend for track 4.

r1t1 equ 16 Rotor 1, track 1.

r2t1 equ 17 Rotor 2, track 1.

r2t2 equ 18 Rotor 2, track 2.

r3t1 equ 19 Rotor 3, track 1.

r3t2 equ 20 Rotor 3, track 2.

r3t3 equ 21 Rotor 3, track 3.

r4t1 equ 22 Rotor 4, track 1.

r4t2 equ 23 Rotor 4, track 2.

r4t3 equ 24 Rotor 4, track 3.

r4t4 equ 25 Rotor 4, track 4.

r5t1 equ 26 Base, track 1.

r5t2 equ 27 Base, track 2.

r5t3 equ 28 Base, track 3.

r5t4 equ 29 Base, track 4.

4

5 of 11

Loading the Initial State

vzero zeroes Load up some handy zeroes.

vl vanswer,forty_two,4 Load up correct answers.

vl vmask,mask,4 Load array to rotate bytes.

vlm r1t1,r5t4,initial,4 Load up tracks into VRs.

…

ds 0L Align to quadword.

zeroes dc al1(00,00,00,00,00,00,00,00,00,00,00,00,00,00,00,00)

forty_two dc al1(42,42,42,42,42,42,42,42,42,42,42,42,00,00,00,00)

mask dc al1(01,02,03,04,05,06,07,08,09,10,11,00,12,13,14,15)

loops dc f’0’

5

Throughout this exercise, various elements of a vector register are compared with zeroes. The first instruction loads vector register 0 with a comparand of all zeroes. Note, VZERO is an extended mnemonic for the VECTOR GENERATE BYTE MASK (VGBM) instruction that loads a VR with zeroes.

The first VECTOR LOAD (VL) instruction loads a vector register with the solution being sought — a value of 42 in the first 12 elements of the register (with zeroes in the rightmost four bytes).

The second VECTOR LOAD instruction loads a value that is used as the fourth operand of a VECTOR PERMUTE (VPERM) instruction. This value enables the VPERM instruction to perform a 12-byte rotation (more on this later).

The VECTOR LOAD MULTIPLE (VLM) instruction loads the initial state of the puzzle’s 14 tracks into contiguous VRs.

Also shown is a counter (loops) that counts how many iterations of rotations have occurred.

6 of 11

Setting Up Loops to Rotate the Rotors

* Load the counters for the individual rotation loops.

lhi 4,12

rotor_loop4 ds 0h

lhi 3,12

rotor_loop3 ds 0h

lhi 2,12

rotor_loop2 ds 0h

lhi 1,12

rotor_loop1 ds 0h

asi loops,1 Increment loop counter.

6

7 of 11

Extracting the Addend for Track 1

* Extract addend for track 1 (a1)

vchb vtemp,r1t1,vzeroes

vsel a1,r1t1,r2t1,vtemp

vchb vtemp,a1,vzeroes

vsel a1,a1,r3t1,vtemp

vchb vtemp,a1,vzeroes

vsel a1,a1,r4t1,vtemp

vchb vtemp,a1,vzeroes

vsel a1,a1,r5t1,vtemp

Compare rotor 1 track 1 to zeroes.

If a byte is greater than zero, the corresponding byte of vtemp is set to X’FF’; otherwise, the corresponding byte of vtemp is set to zeroes.

Use the bytes of vtemp as selector to initially set addend1 (a1). Pick bytes from rotor 1 track 1 if nonzero, or pick bytes from rotor 2 track 1 if zero.

Repeat the process of inspecting the addend for remaining bytes of zeroes. Where zeros are found, VSEL will pick from the track at the next lower rotor.

7

If there were no holes in the tracks, we could simply add up the values of rotor 1 track 1 with those of rotor 2 track 2, rotor 3 track 3, and rotor 4 track 4 (completely ignoring rotor 5) and then compare the results to bytes of 42. However, there are holes from which we need to extract numbers from lower rotors.

This is where some of the vector magic starts to appear:

Recall that within a vector register representing a track, a hole is indicated by a byte element of zero. Beginning with vector register containing rotor 1 track 1 (r1t1), we use VECTOR COMPARE HIGH (VCH) to compare its elements to zeros. The mnemonic VCHB sets the instruction’s M₄ field to indicate byte-sized elements. For each element of r1t1 compared, the resulting byte element in the first operand (vtemp) is either X’FF’ (i.e., TRUE) if the corresponding r1t1 byte element is greater than zero, or X’00’ (i.e., FALSE) if the r1t1 byte element is zero.

The resulting byte elements of X’FF’s and X’00’s are the perfect values to feed into the fourth operand of a VECTOR SELECT (VSEL) instruction. The first VSEL instruction selects a byte from r1t1 when the selector byte is X’FF’ (that is, when the compared r1t1 byte is greater than zero), or it selects a byte from track 1 of the next-lower rotor (r2t1) when the selector byte is X’00’ (that is, when the compared r1t1 byte is zero). The result is an initial attempt at an addend for the rotor 1. But wait …

… depending on the position of the rotors, the addend may still have zeroes in it (that is, a lower rotor’s corresponding sector may also be a hole). So, the process continues by comparing the addend with zeroes, and feeding that result into a VSEL instruction that selects bytes from either the current addend or from the next-lower rotor. Once this section of code is completed, we have a complete set of addends for track 1.

This process is repeated for all possible tracks of a rotor in the next slide.

8 of 11

Extracting the Addends Tracks 2-4

* Extract addend for track 2 (a2).

vchb vtemp,r2t2,vzeroes

vsel a2,r2t2,r3t2,vtemp

vchb vtemp,a2,vzeroes

vsel a2,a2,r4t2,vtemp

vchb vtemp,a2,vzeroes

vsel a2,a2,r5t2,vtemp

* Extract addend for track 3 (a3).

vchb vtemp,r3t3,vzeroes

vsel a3,r3t3,r4t3,vtemp

vchb vtemp,a3,vzeroes

vsel a3,a3,r5t3,vtemp

* Extract addend for track 4 (a4).

vchb vtemp,r4t4,vzeroes

vsel a4,r4t4,r5t4,vtemp

8

9 of 11

Found the Answer to�Life, the Universe, and Everything?

* Elements all add up to 42?

vab vtemp,a1,a2

vab vtemp,vtemp,a3

vab vtemp,vtemp,a4

vceqbs vtemp,vtemp,vanswer

je gotta_winner

9

In the Hitchhiker’s Guide to the Galaxy, the late British author Douglas Adams wrote that the answer to “Life, the Universe, and Everything” — as calculated by the computer Deep Thought over 7 million years — is, in fact, 42! It is unknown whether the designers of the Grecian computer puzzle took this into account in their solution to the puzzle … but it gives one pause to ponder deep thoughts.

The four VRs representing addends for the tracks (a1, a2, a3, and a4) are added together into the VR labelled vtemp. Note, VAB is the extended mnemonic for VECTOR ADD (VA) that sets the M₄ field to indicate byte-sized elements.

Then the VECTOR COMPARE EQUAL (VCEQ) instruction is used to compare the 12 sums with the VR containing the answer: bytes 0-11 containing 42, with the rightmost 4 bytes of zeroes. Note, VCEQBS is the extended mnemonic for VCEQ; VCEQBS sets the M₄ field to indicate byte-sized elements, and it also sets the M₅ field to indicate that the condition code is to be set (CC0 indicates all elements are equal).

If all elements are equal to 42, a solution has been found! The reader is left with the exercise of figuring out how to store the results and format them. (Hint, use VECTOR STORE MULTIPLE.) Or, you can just look at the VRs using a debugger like I did. After formatting, you can proceed to the next slide to see if there are any other solutions.

If the answer has not yet been found, then we need to rotate one or more rotors and try again, as shown on the next slide.

10 of 11

Rotating the Rotors

* Rotate rotor 1.

rotate ds 0h

vperm r1t1,r1t1,vzeroes,vmask

jct 1,rotor_loop1

* Rotate rotor 2.

vperm r2t1,r2t1,vzeroes,vmask

vperm r2t2,r2t2,vzeroes,vmask

jct 2,rotor_loop2

* Rotate rotor 3.

vperm r3t1,r3t1,vzeroes,vmask

vperm r3t2,r3t2,vzeroes,vmask

vperm r3t3,r3t3,vzeroes,vmask

jct 3,rotor_loop3

* Rotate rotor 4.

vperm r4t1,r4t1,vzeroes,vmask

vperm r4t2,r4t2,vzeroes,vmask

vperm r4t3,r4t3,vzeroes,vmask

vperm r4t4,r4t4,vzeroes,vmask

jct 4,rotor_loop4

* All combinations tried; we’re done!

10

Recall a few slides ago, we set up some general registers to serve as loop counters for rotating rotors 1-4. Here is where some additional vector register magic occurs.

There are several vector rotation instructions, but each of them rotates the entire 16-byte register. We need a means by which a 12-byte rotation can be performed in the leftmost 12 bytes of the VR, while leaving the rightmost bytes unchanged.

Meet VECTOR PERMUTE (VPERM) which provides the perfect solution. VPERM creates a so-called source vector from the concatenation of the second and third operands. For each byte of the fourth operand, bits 3-5 are used as an index into the source vector to select a byte to be placed into the first-operand byte corresponding to the fourth-operand byte.

For our purposes, we only care about the first twelve bytes of the second operand; thus, the third operand (vzeroes) is irrelevant. The fourth operand (vmask) contains the values 1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 0, 12, 13, 14, 15. Thus, the results in the first operand are bytes of the second operand, shifted left one byte, except the original byte 0 ends up in the resulting byte 11 (the rightmost four bytes of zeroes are unshifted).

For rotor 1, there is only one track that needs to be rotated. After 12 rotations, we fall through to rotate rotor 2’s two tracks … after which, we fall through to rotate rotor 3’s three tracks … after which, rotor 4’s four tracks are rotated. When all the tracks have been rotated (12⁴ iterations), all possible combinations have been tried, and we’re done.

Hint: There’s only one possible solution, so once you’re found it, you can quit without doing all 20,736 possible combinations.

That’s it. To confirm the solution, you can either (a) buy the puzzle and solve it manually (if you don’t want to buy the puzzle, you can make one yourself from slide 2), or (b) use the code fragments herein to discover the results.

If you buy the puzzle and (like me) become frustrated with it, you can always re-gift it to an annoying sibling, in-law, neighbor, or co-worker.

11 of 11

Lessons Learned

SIMD processing:

Parallel extraction of sectors on the same radii of a rotor to form addends
Parallel addition of the addends for the 12 sectors
Parallel comparison for the solution

Branchless computing

Certain instructions provide true/false indications for each element in the VR compared or searched.
VECTOR SELECT (VSEL) can be fed these true/false indications to conditionally load elements … without branching!

VECTOR PERMUTE (VPERM)

Powerful translation mechanism
Used in this problem to form a 12-byte rotator
Potentially useful in crypto algorithms (e.g., AES S-box processing).

11

The solution to the Grecian Computer Puzzle is an example of a small subset of the vector-facility instructions. However, it demonstrates the power of structuring a program to use the vector facility.

The first example is single-instruction multiple-data (SIMD, i.e., parallel) processing. In this program, the numbers — and holes — of a rotor’s track are represented as byte elements in a vector register. Handily, the 14 tracks of the puzzle can easily be accommodated in 14 separate vector registers with room to spare.

The manipulation of the data in the tracks to form addends for each of the 12 radii is performed in parallel, rather than twelve separate executions of serial instructions. The addition of the four addends representing the resolved track data is also performed in parallel. And finally, the comparison of the twelve sums with the solution is done in parallel.

One of the most powerful attributes of the vector instructions is the ability to perform a long series of conditional computations without ever needing to branch. This is accomplished by a set of comparison and test instructions that set true/false indications for each element processed; these instructions include VCEQ, VCH, VCHL, VFAE, VFCE, VFCH, VFCHE, VFTCI, and VSTRC. True/false indications from these instructions — or from other indications that are programmatically derived — can be used as input to the VECTOR SELECT (VSEL) instruction to conditionally load an element from one of two operands. Reducing the number of branches may result in substantial performance improvement for a task.

Finally, the VECTOR PERMUTE (VPERM) instruction is the vector equivalent of a Swiss Army Knife for rearranging the data in a vector register. It is somewhat analogous to the classic S/360 TRANSLATE (TR) instruction, however VPERM is limited to a 32-byte translate table. In this program, VPERM provides a simple 12-byte rotator, allowing the 14 VRs containing the puzzle’s tracks to be easily rotated. VPERM has countless other applications, potentially in cryptographic algorithms (e.g., the S-box manipulations done in the AES algorithm).

We’ve explored only a handful of the numerous (nearly 200) vector instructions in this exercise. What vector applications await your curiosity?