Did any 16-bit or 36-bit computer instruction set ever include 4x4 or 6x6 bit-matrix operations?

Question

Donald Knuth's 64-bit MMIX architecture includes several novel instructions that operate matrixwise on an 8x8 square matrix (MOR, MXOR).

(MMIX also has instructions like BDIF that operate vectorwise on 8x 8-bit integers, which is less novel; x86 does that just fine.)

Treating your 64-bit word as a square matrix is possible only when the word size is a perfect square.

Back in the day, there were computers with a 36-bit word length. That's famously enough to store 6x 6-bit (pre-ASCII) characters in a single word. Did any historical 36-bit computer ever offer operations that were best understood by reading machine words as 6x6 matrices?

How about any historical 16-bit computer?

Besides complicated instructions like MMIX's MOR and MXOR, the simplest example of a "matrix operation" in the sense I mean would be a unary TRANSPOSE operation:

TRANSPOSE(1001'1010'1010'1011) = 1111'0000'0111'1001
TRANSPOSE(1001'0010'1011'0100) = 1010'0001'0110'1010

Answer 1

I don't know if it counts as a 16-bit historical computer, but there were a number of 80287 clones. One of them, from IIT, added a F4x4 instruction that operated on the entire FP stack to perform matrix operations (the IIT chip had not one, but four stacks of eight FPU registers each).

A friend of mine had one of these coprocessors back in the day, and it came with a demo program showing a speed test of this F4x4 instruction. The leafsheet that served as fitting and user guide also mentioned this feature.

The only information I have found so far is from the COPRO16A.TXT file, by Norbert Juffa. Excerpts from that document include:

The IIT 2C87 provides extra functions not available on any other 287 chip [38]. It has 24 user-accessible floating-point registers organized into three register banks. Additional instructions (FSBP0, FSBP1, FSBP2) allow switching from one bank to another. (Transfers between registers in different banks are not supported, however, so this feature by itself is of limited usefulness. Also, there seems to be only one status register (containing the stack top pointer), so it has to be manually loaded and stored when switching between banks with a different number of registers in use [40]). The register bank's main purpose is to aid the fourth additional instruction the 2C87 has (F4X4), which does a full multiply of a 4x4 matrix by a 4x1 vector, an operation common in 3D- graphics applications [39]. The built-in matrix multiply speeds this operation up by a factor of 6 to 8 when compared to a programmed solution according to the manufacturer [38]. Tests show the speed-up to be indeed in this range [40]. For the 3C87, I measured the execution time of F4X4 to be about 280 clock cycles; the execution time on the 2C87 should be somewhat larger - I estimate it to be around 310 clock cycles due to the higher CPU-NDP communication overhead in instruction execution in 286/287 systems (~45-50 clock cycles) compared with 386/387 systems (~16-20 clock cycles). As desirable as the F4X4 instruction may seem, however, there are very few applications that make use of it when an IIT coprocessor is detected at run time (among them Schroff Development's Silver Screen and Evolution Computing's Fast-CAD 3-D [25]).

And a routine showing how to use the F4x4 instruction:

  ;---------------------------------------------------------------------
  ;
  ; IIT_MUL_4x4 multiplicates a four-by-four matrix by an array of four
  ; dimensional vectors. This operation is needed for 3D transformations
  ; in graphics data processing. There are arrays for each component of
  ; a vector.  Thus there is an array containing all the x components,
  ; another containing all the y components and so on. Each component is
  ; an 8 byte IEEE floating-point number. Two indices into the array of
  ; vectors are given. The first is the index of the vector that will be
  ; processed first, the second is the index of the vector processed
  ; last. This subroutine uses the special instructions only available
  ; on IIT coprocessors to provide fast matrix multiply capabilities.
  ; So make sure to use it only on IIT coprocessors.
  ;
  ;---------------------------------------------------------------------

  IIT_MUL_4x4   PROC    NEAR

        AddrX   EQU DWORD PTR [BP+24] ; address of X component array
        AddrY   EQU DWORD PTR [BP+20] ; address of Y component array
        AddrZ   EQU DWORD PTR [BP+16] ; address of Z component array
        AddrW   EQU DWORD PTR [BP+12] ; address of W component array
        AddrT   EQU DWORD PTR [BP+8]  ; addr. of 4x4 transf. matrix
        F       EQU WORD  PTR [BP+6]  ; first vector to process
        K       EQU WORD  PTR [BP+4]  ; last vector to process
        RetAddr EQU WORD  PTR [BP+2]  ; return address saved by call
        SavdBP  EQU WORD  PTR [BP+0]  ; saved frame pointer
        SavdDS  EQU WORD  PTR [BP-2]  ; caller's data segment
        Ctrl87  EQU WORD  PTR [BP-4]  ; caller's 80x87 control word

        PUSH    BP                    ; save TURBO-Pascal frame ptr
        MOV     BP, SP                ; new frame pointer
        PUSH    DS                    ; save TURBO-Pascal data seg.
        SUB     SP, 2                 ; make local variabe
        FSTCW   [Ctrl87]              ; save 80x87 ctrl word
        LES     SI, AddrT             ; ptr to transformation matrix
        FINIT                         ; initialize coprocessor
        FSBP2                         ; set register bank 2
        FLD     QWORD PTR ES:[SI]     ; load a[0,0]
        FLD     QWORD PTR ES:[SI+32]  ; load a[1,0]
        FLD     QWORD PTR ES:[SI+64]  ; load a[2,0]
        FLD     QWORD PTR ES:[SI+96]  ; load a[3,0]
        FLD     QWORD PTR ES:[SI+8]   ; load a[0,1]
        FLD     QWORD PTR ES:[SI+40]  ; load a[1,1]
        FLD     QWORD PTR ES:[SI+72]  ; load a[2,1]
        FLD     QWORD PTR ES:[SI+104] ; load a[3,1]
        FINIT                         ; initialize coprocessor
        FSBP1                         ; set register bank 1
        FLD     QWORD PTR ES:[SI+16]  ; load a[0,2]
        FLD     QWORD PTR ES:[SI+48]  ; load a[1,2]
        FLD     QWORD PTR ES:[SI+80]  ; load a[2,2]
        FLD     QWORD PTR ES:[SI+112] ; load a[3,2]
        FLD     QWORD PTR ES:[SI+24]  ; load a[0,3]
        FLD     QWORD PTR ES:[SI+56]  ; load a[1,3]
        FLD     QWORD PTR ES:[SI+88]  ; load a[2,3]
        FLD     QWORD PTR ES:[SI+120] ; load a[3,3]

                                      ; transformation matrix loaded

        MOV     AX, F                 ; index of first vector
        MOV     DX, K                 ; index of last vector

        MOV     BX, AX                ; index 1st vector to process
        MOV     CL, 3                 ; component has 8 (2**3) bytes
        SHL     BX, CL                ; compute offset into arrays

        FINIT                         ; initialize coprocessor
        FSBP0                         ; set register bank 0

  $mat_loop:LES     SI, AddrW             ; addr. of W component array
        FLD     QWORD PTR ES:[SI+BX]  ; W component current vector
        LES     SI, AddrZ             ; addr. of Z component array
        FLD     QWORD PTR ES:[SI+BX]  ; Z component current vector
        LES     SI, AddrY             ; addr. of Y component array
        FLD     QWORD PTR ES:[SI+BX]  ; Y component current vector
        LES     SI, AddrX             ; addr. of X component array
        FLD     QWORD PTR ES:[SI+BX]  ; X component current vector
        F4X4                          ; mul 4x4 matrix by 4x1 vector
        INC     AX                    ; next vector
        MOV     DI, AX                ; next vector
        SHL     DI, CL                ; offset of vector into arrays

        FSTP    QWORD PTR ES:[SI+BX]  ; store X comp. of curr. vect.
        LES     SI, AddrY             ; address of Y component array
        FSTP    QWORD PTR ES:[SI+BX]  ; store Y comp. of curr. vect.
        LES     SI, AddrZ             ; address of Z component array
        FSTP    QWORD PTR ES:[SI+BX]  ; store Z comp. of curr. vect.
        LES     SI, AddrW             ; address of W component array
        FSTP    QWORD PTR ES:[SI+BX]  ; store W comp. of curr. vect.

        MOV     BX, DI                ; ofs nxt vect. in comp. arrays
        CMP     AX, DX                ; nxt vector past upper bound?
        JLE     $mat_loop             ; no, transform next vector
        FLDCW   [Ctrl87]              ; restore orig 80x87 ctrl word

        ADD      SP, 2                ; get rid of local variable
        POP      DS                   ; restore TP data segment
        POP      BP                   ; restore TP frame pointer
        RET      24                   ; pop parameters and return
  IIT_MUL_4x4   ENDP

  CODE      ENDS

  END

Answer 2

I think the big question you have to ask here is: What would such an instruction have been useful for? Single-bit data types don't usually go together with matrix operations.

I've looked at some examples where the MMIX instructions are used, and they don't seem to be very compelling, given the hardware complexity of doing so. For example, if you want a ROL instruction, you can add a few gates to a SHL instruction's implementation and avoid all the gymnastics needed to emulate it with a MOR instruction. Another example given involves spacing out a narrow character string (eg. ASCII) into a wider one (eg. UTF-16), which strikes me as not a common enough operation to justify using anything more clever than the obvious scalar loop.

The best examples of this type of operation I know of come from relatively recent CPUs with SIMD units, such as ARM NEON (a 32-bit architecture with 64-bit and 128-bit SIMD registers). These often include both "horizontal" (eg. sum all elements in a single register) and "vertical" (eg. multiply two registers element-wise and accumulate into a third) operations that can be used to efficiently support matrix arithmetic by combining a relatively small number of instructions. There are also instructions for interleaving and de-interleaving data (aka. zip and unzip operations) which can be very useful for transposing matrices.